-#ifdef EXPAIRSEQ_USE_HASHTAB
-
-unsigned expairseq::calc_hashtabsize(unsigned sz) const
-{
- unsigned size;
- unsigned nearest_power_of_2 = 1 << log2(sz);
- // if (nearest_power_of_2 < maxhashtabsize/hashtabfactor) {
- // size=nearest_power_of_2*hashtabfactor;
- size=nearest_power_of_2/hashtabfactor;
- if (size<minhashtabsize) return 0;
- GINAC_ASSERT(hashtabsize<=0x8000000U); // really max size due to 31 bit hashing
- // hashtabsize must be a power of 2
- GINAC_ASSERT((1U << log2(size))==size);
- return size;
-}
-
-unsigned expairseq::calc_hashindex(const ex & e) const
-{
- // calculate hashindex
- unsigned hash=e.gethash();
- unsigned hashindex;
- if (is_a_numeric_hash(hash)) {
- hashindex=hashmask;
- } else {
- hashindex=hash & hashmask;
- // last hashtab entry is reserved for numerics
- if (hashindex==hashmask) hashindex=0;
- }
- GINAC_ASSERT(hashindex>=0);
- GINAC_ASSERT((hashindex<hashtabsize)||(hashtabsize==0));
- return hashindex;
-}
-
-void expairseq::shrink_hashtab(void)
-{
- unsigned new_hashtabsize;
- while (hashtabsize!=(new_hashtabsize=calc_hashtabsize(seq.size()))) {
- GINAC_ASSERT(new_hashtabsize<hashtabsize);
- if (new_hashtabsize==0) {
- hashtab.clear();
- hashtabsize=0;
- canonicalize();
- return;
- }
-
- // shrink by a factor of 2
- unsigned half_hashtabsize=hashtabsize/2;
- for (unsigned i=0; i<half_hashtabsize-1; ++i) {
- hashtab[i].merge(hashtab[i+half_hashtabsize],epp_is_less());
- }
- // special treatment for numeric hashes
- hashtab[0].merge(hashtab[half_hashtabsize-1],epp_is_less());
- hashtab[half_hashtabsize-1]=hashtab[hashtabsize-1];
- hashtab.resize(half_hashtabsize);
- hashtabsize=half_hashtabsize;
- hashmask=hashtabsize-1;
- }
-}
-
-void expairseq::remove_hashtab_entry(epvector::const_iterator element)
-{
- if (hashtabsize==0) return; // nothing to do
-
- // calculate hashindex of element to be deleted
- unsigned hashindex=calc_hashindex((*element).rest);
-
- // find it in hashtab and remove it
- epplist & eppl=hashtab[hashindex];
- epplist::iterator epplit=eppl.begin();
- bool erased=false;
- while (epplit!=eppl.end()) {
- if (*epplit == element) {
- eppl.erase(epplit);
- erased=true;
- break;
- }
- ++epplit;
- }
- if (!erased) {
- printtree(cout,0);
- cout << "tried to erase " << element-seq.begin() << std::endl;
- cout << "size " << seq.end()-seq.begin() << std::endl;
-
- unsigned hashindex=calc_hashindex((*element).rest);
- epplist & eppl=hashtab[hashindex];
- epplist::iterator epplit=eppl.begin();
- bool erased=false;
- while (epplit!=eppl.end()) {
- if (*epplit == element) {
- eppl.erase(epplit);
- erased=true;
- break;
- }
- ++epplit;
- }
- GINAC_ASSERT(erased);
- }
- GINAC_ASSERT(erased);
-}
-
-void expairseq::move_hashtab_entry(epvector::const_iterator oldpos,
- epvector::iterator newpos)
-{
- GINAC_ASSERT(hashtabsize!=0);
-
- // calculate hashindex of element which was moved
- unsigned hashindex=calc_hashindex((*newpos).rest);
-
- // find it in hashtab and modify it
- epplist & eppl=hashtab[hashindex];
- epplist::iterator epplit=eppl.begin();
- while (epplit!=eppl.end()) {
- if (*epplit == oldpos) {
- *epplit=newpos;
- break;
- }
- ++epplit;
- }
- GINAC_ASSERT(epplit!=eppl.end());
-}
-
-void expairseq::sorted_insert(epplist & eppl, epp elem)
-{
- epplist::iterator current=eppl.begin();
- while ((current!=eppl.end())&&((*(*current)).is_less(*elem))) {
- ++current;
- }
- eppl.insert(current,elem);
-}
-
-void expairseq::build_hashtab_and_combine(epvector::iterator & first_numeric,
- epvector::iterator & last_non_zero,
- vector<bool> & touched,
- unsigned & number_of_zeroes)
-{
- epp current=seq.begin();
-
- while (current!=first_numeric) {
- if (is_ex_exactly_of_type((*current).rest,numeric)) {
- --first_numeric;
- iter_swap(current,first_numeric);
- } else {
- // calculate hashindex
- unsigned currenthashindex=calc_hashindex((*current).rest);
-
- // test if there is already a matching expair in the hashtab-list
- epplist & eppl=hashtab[currenthashindex];
- epplist::iterator epplit=eppl.begin();
- while (epplit!=eppl.end()) {
- if ((*current).rest.is_equal((*(*epplit)).rest)) break;
- ++epplit;
- }
- if (epplit==eppl.end()) {
- // no matching expair found, append this to end of list
- sorted_insert(eppl,current);
- ++current;
- } else {
- // epplit points to a matching expair, combine it with current
- (*(*epplit)).coeff = ex_to_numeric((*(*epplit)).coeff).
- add_dyn(ex_to_numeric((*current).coeff));
-
- // move obsolete current expair to end by swapping with last_non_zero element
- // if this was a numeric, it is swapped with the expair before first_numeric
- iter_swap(current,last_non_zero);
- --first_numeric;
- if (first_numeric!=last_non_zero) iter_swap(first_numeric,current);
- --last_non_zero;
- ++number_of_zeroes;
- // test if combined term has coeff 0 and can be removed is done later
- touched[(*epplit)-seq.begin()]=true;
- }
- }
- }
-}
-
-void expairseq::drop_coeff_0_terms(epvector::iterator & first_numeric,
- epvector::iterator & last_non_zero,
- vector<bool> & touched,
- unsigned & number_of_zeroes)
-{
- // move terms with coeff 0 to end and remove them from hashtab
- // check only those elements which have been touched
- epp current=seq.begin();
- unsigned i=0;
- while (current!=first_numeric) {
- if (!touched[i]) {
- ++current;
- ++i;
- } else if (!ex_to_numeric((*current).coeff).is_equal(_num0())) {
- ++current;
- ++i;
- } else {
- remove_hashtab_entry(current);
-
- // move element to the end, unless it is already at the end
- if (current!=last_non_zero) {
- iter_swap(current,last_non_zero);
- --first_numeric;
- bool numeric_swapped=first_numeric!=last_non_zero;
- if (numeric_swapped) iter_swap(first_numeric,current);
- epvector::iterator changed_entry;
-
- if (numeric_swapped) {
- changed_entry=first_numeric;
- } else {
- changed_entry=last_non_zero;
- }
-
- --last_non_zero;
- ++number_of_zeroes;
-
- if (first_numeric!=current) {
-
- // change entry in hashtab which referred to first_numeric or last_non_zero to current
- move_hashtab_entry(changed_entry,current);
- touched[current-seq.begin()]=touched[changed_entry-seq.begin()];
- }
- } else {
- --first_numeric;
- --last_non_zero;
- ++number_of_zeroes;
- }
- }
- }
- GINAC_ASSERT(i==current-seq.begin());
-}
-
-bool expairseq::has_coeff_0(void) const
-{
- for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
- if ((*cit).coeff.is_equal(_ex0())) {
- return true;
- }
- }
- return false;
-}
-
-void expairseq::add_numerics_to_hashtab(epvector::iterator first_numeric,
- epvector::const_iterator last_non_zero)
-{
- if (first_numeric==seq.end()) return; // no numerics
-
- epvector::iterator current=first_numeric;
- epvector::const_iterator last=last_non_zero+1;
- while (current!=last) {
- sorted_insert(hashtab[hashmask],current);
- ++current;
- }
-}
-
-void expairseq::combine_same_terms(void)
-{
- // combine same terms, drop term with coeff 0, move numerics to end
-
- // calculate size of hashtab
- hashtabsize=calc_hashtabsize(seq.size());
-
- // hashtabsize is a power of 2
- hashmask=hashtabsize-1;
-
- // allocate hashtab
- hashtab.clear();
- hashtab.resize(hashtabsize);
-
- if (hashtabsize==0) {
- canonicalize();
- combine_same_terms_sorted_seq();
- GINAC_ASSERT(!has_coeff_0());
- return;
- }
-
- // iterate through seq, move numerics to end,
- // fill hashtab and combine same terms
- epvector::iterator first_numeric=seq.end();
- epvector::iterator last_non_zero=seq.end()-1;
-
- vector<bool> touched;
- touched.reserve(seq.size());
- for (unsigned i=0; i<seq.size(); ++i) touched[i]=false;
-
- unsigned number_of_zeroes=0;
-
- GINAC_ASSERT(!has_coeff_0());
- build_hashtab_and_combine(first_numeric,last_non_zero,touched,number_of_zeroes);
- /*
- cout << "in combine:" << std::endl;
- printtree(cout,0);
- cout << "size=" << seq.end() - seq.begin() << std::endl;
- cout << "first_numeric=" << first_numeric - seq.begin() << std::endl;
- cout << "last_non_zero=" << last_non_zero - seq.begin() << std::endl;
- for (unsigned i=0; i<seq.size(); ++i) {
- if (touched[i]) cout << i << " is touched" << std::endl;
- }
- cout << "end in combine" << std::endl;
- */
-
- // there should not be any terms with coeff 0 from the beginning,
- // so it should be safe to skip this step
- if (number_of_zeroes!=0) {
- drop_coeff_0_terms(first_numeric,last_non_zero,touched,number_of_zeroes);
- /*
- cout << "in combine after drop:" << std::endl;
- printtree(cout,0);
- cout << "size=" << seq.end() - seq.begin() << std::endl;
- cout << "first_numeric=" << first_numeric - seq.begin() << std::endl;
- cout << "last_non_zero=" << last_non_zero - seq.begin() << std::endl;
- for (unsigned i=0; i<seq.size(); ++i) {
- if (touched[i]) cout << i << " is touched" << std::endl;
- }
- cout << "end in combine after drop" << std::endl;
- */
- }
-
- add_numerics_to_hashtab(first_numeric,last_non_zero);
-
- // pop zero elements
- for (unsigned i=0; i<number_of_zeroes; ++i) {
- seq.pop_back();
- }
-
- // shrink hashtabsize to calculated value
- GINAC_ASSERT(!has_coeff_0());
-
- shrink_hashtab();
-
- GINAC_ASSERT(!has_coeff_0());
-}
-
-#endif // def EXPAIRSEQ_USE_HASHTAB
-