- 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)
-{
- epplist::const_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,
- std::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;
- }
- }