WordTable.hpp File Reference

WordTable / WordWithDataTable — leading-word indices for non-commutative Gröbner basis lookup. More...

#include <cstddef>
#include <ostream>
#include <tuple>
#include <utility>
#include <vector>
#include "MemoryBlock.hpp"

Go to the source code of this file.

Classes
class	WordTable
	Index of Words (non-commutative monomials) with subword, prefix/suffix, and overlap lookup used by the NC Groebner code. More...
class	WordWithDataTable
	Variant of WordTable where each stored monomial carries an additional ecart-degree datum that gates subword matches. More...

Typedefs
using	Overlap = std::tuple<int,int,int,bool>

Functions
std::ostream &	operator<< (std::ostream &o, const WordTable &wordTable)
std::ostream &	operator<< (std::ostream &o, const WordWithDataTable &wordWithDataTable)

Detailed Description

WordTable / WordWithDataTable — leading-word indices for non-commutative Gröbner basis lookup.

Note

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

Declares the two structures NCGroebner and NCF4 consult to answer "does some basis leading word occur as a contiguous subword of this target?" — the non-commutative analogue of monomial divisibility. Storage is a parallel pair: std::vector<Word> mMonomials for the words themselves and std::vector<int> mIndices with -1 marking retired entries; the actual word bytes live in MemoryBlock mMonomialSpace. The soft-delete mechanism is fully wired in the companion WordWithDataTable (whose clear() resets both vectors) but only partially wired in WordTable itself — the in-file TODO at the top tracks the missing retire(index) / search-skipping work. Public surface: insert(w) / insert(w, newRightOverlaps) extends the table while harvesting the right-overlaps the new entry generates with every existing word; subword(target, out) reports the first match used to drive reduction; subwords(target, out) collects all of them; superwords does the reverse direction; isPrefix/isSuffix/ isNontrivialSuperword check the boundary cases; leftOverlaps / rightOverlaps enumerate overlap pairs.

WordWithDataTable is the ecart-degree-aware variant — subword matches additionally require the matched word's ecart to be at most the target's, so inhomogeneous GB computations can pick the right reducer. The string-matching subword search is the hot path of the entire NC GB engine; the naive walk is O(|target| * |table|) per query and is the production choice today. SuffixTree is the experimental constant-O(|target|) alternative the engine is staged to swap in (commented-out alternative in NCGroebner / NCF4).

See also

Word.hpp

SuffixTree.hpp

NCGroebner.hpp

NCF4.hpp

MemoryBlock.hpp

Definition in file WordTable.hpp.