OverlapTable.hpp File Reference

OverlapTable — degree-sorted queue of pending word overlaps for non-commutative GB drivers. More...

#include "Polynomial.hpp"
#include <deque>
#include <map>
#include <ostream>
#include <tuple>
#include <utility>

Go to the source code of this file.

Classes
class	OverlapTable
	Per-degree FIFO queue of pending overlaps for the NC Groebner basis driver to process. More...

Typedefs
using	Overlap = std::tuple<int,int,int,bool>
using	OverlapMap = std::map<std::pair<int,bool>,std::deque<Overlap>>

Functions
std::ostream &	operator<< (std::ostream &ostr, const OverlapTable &overlapTable)
auto	operator<< (std::ostream &o, Overlap &a) -> std::ostream &

Detailed Description

OverlapTable — degree-sorted queue of pending word overlaps for non-commutative GB drivers.

Note

AI-generated documentation. Verify against the source before relying on it.

Declares the non-commutative analogue of the commutative SPair set. An Overlap = std::tuple<int, int, int, bool> is (i, j, k, computed) recording that a suffix of basis word i matches a prefix of basis word k starting at position j in i; the trailing bool flags whether the corresponding S-polynomial has been computed yet. The container is OverlapMap = std::map<std::pair<int, bool>, std::deque<Overlap>> where the key bool is isGenerator (distinguishing overlaps coming from original input generators from overlaps derived from basis-element pairs) — not the per-Overlap computed flag. nextDegreeOverlaps pops the lowest-degree std::deque in one go, insert(deg, isGenerator, o) appends, removeLowestDegree advances the cursor (with an in-source TODO flagging a logic bug in the inhomogeneous case), and isFinished() / isFinished(topDegree) are the termination tests the NCGroebner / NCF4 outer loop uses.

Each Buchberger-style pair in the commutative case becomes potentially many overlaps in the NC case, since a leading word can overlap a partner at every suffix-prefix match position. The class also stores a bare ConstPolyList* mPolyList (received via the second constructor) for callers that need to consult the actual polynomial data — the only method in this header that exposes overlap metadata is overlapWordLength; the chain-criterion-style pruning lives outside this class.

See also

WordTable.hpp

NCGroebner.hpp

NCF4.hpp

Polynomial.hpp

Definition in file OverlapTable.hpp.