-void expairseq::combine_same_terms_sorted_seq(void)
-{
- bool needs_further_processing = false;
-
- if (seq.size()>1) {
- epvector::iterator itin1 = seq.begin();
- epvector::iterator itin2 = itin1+1;
- epvector::iterator itout = itin1;
- epvector::iterator last = seq.end();
- // must_copy will be set to true the first time some combination is
- // possible from then on the sequence has changed and must be compacted
- bool must_copy = false;
- while (itin2!=last) {
- if ((*itin1).rest.compare(itin2->rest)==0) {
- (*itin1).coeff = ex_to<numeric>(itin1->coeff).
- add_dyn(ex_to<numeric>(itin2->coeff));
- if (expair_needs_further_processing(itin1))
- needs_further_processing = true;
- must_copy = true;
- } else {
- if (!ex_to<numeric>(itin1->coeff).is_zero()) {
- if (must_copy)
- *itout = *itin1;
- ++itout;
- }
- itin1 = itin2;
- }
- ++itin2;
- }
- if (!ex_to<numeric>(itin1->coeff).is_zero()) {
- if (must_copy)
- *itout = *itin1;
- ++itout;
- }
- if (itout!=last)
- seq.erase(itout,last);
- }
-
- if (needs_further_processing) {
- epvector v = seq;
- seq.clear();
- construct_from_epvector(v);
- }
-}
-
-#if 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) {
- std::cout << "tried to erase " << element-seq.begin() << std::endl;
- std::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, epvector::const_iterator elem)