- 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;
-
- // 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 hashindex;
- if (is_a<numeric>(e)) {
- hashindex = hashmask;
- } else {
- hashindex = e.gethash() & hashmask;
- // last hashtab entry is reserved for numerics
- if (hashindex==hashmask) hashindex = 0;
- }
- GINAC_ASSERT((hashindex<hashtabsize)||(hashtabsize==0));
- return hashindex;
-}
-
-void expairseq::shrink_hashtab()
-{
- 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_exactly_a<numeric>(current->rest)) {
- --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,
- std::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();
- size_t i = 0;
- while (current!=first_numeric) {
- if (!touched[i]) {
- ++current;
- ++i;
- } else if (!ex_to<numeric>((*current).coeff).is_zero()) {
- ++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());
-}
-
-/** True if one of the coeffs vanishes, otherwise false.
- * This would be an invariant violation, so this should only be used for
- * debugging purposes. */
-bool expairseq::has_coeff_0() const
-{
- epvector::const_iterator i = seq.begin(), end = seq.end();
- while (i != end) {
- if (i->coeff.is_zero())
- return true;
- ++i;