- bool needs_further_processing=false;
-
- // combine same terms, drop term with coeff 0
- 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);
- }
- }
-
- /*
- cout << "after combine" << std::endl;
- for (epvector::const_iterator cit=seq.begin(); cit!=seq.end(); ++cit) {
- (*cit).printraw(cout);
- }
- cout << std::endl;
- cout.flush();
- */
-
- if (needs_further_processing) {
- epvector v=seq;
- seq.clear();
- construct_from_epvector(v);
- }
-}
-
-#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;
- }
- }
- }
-}