GitHub

Words

AbstractWord interface

KnuthBendix.Words.AbstractWord — Type
AbstractWord{T} <: AbstractVector{T}

Abstract type representing words over an Alphabet.

AbstractWord is just a string of integers and as such gains its meaning in the contex of an Alphabet (when integers are understood as pointers to letters). The subtypes of AbstractWord{T} need to implement the following methods which constitute AbstractWord interface:

  • a constructor from AbstractVector{T} with check optional argument (true implies checking the validity of input),
  • linear indexing (1-based) consistent with iteration returning pointers to letters of an alphabet (getindex, setindex, size).
Note
  • It is assumed that eachindex(w::AbstractWord) returns Base.OneTo(length(w))
  • the lenght(w) must represented the length of the word as it is written in an alphabet, and neither its shortest form (e.g. the normal form) nor the length of the freely reduced form.
  • Base.push!/Base.pushfirst!: append a single value at the end/beginning,
  • Base.pop!/Base.popfirst!: pop a single value from the end/beginning,
  • Base.append!/Base.prepend!: append a another word at the end/beginning,
  • Base.resize!: drop/extend a word at the end to the requested length
  • Base.similar: an uninitialized word of a similar type/storage.

The following are implemented for AbstractWords but can be overloaded for performance reasons:

  • Base.==: the equality (as words),
  • Base.hash: simple uniqueness hashing function
  • Base.view: creating SubWord e.g. based on subarray.
source

Auxillary functions

KnuthBendix.Words.longestcommonprefix — Function
longestcommonprefix(u::AbstractWord, v::AbstractWord)

Returns the length of longest common prefix of two words (and simultaneously the index at which the prefix ends).

source

Implementations

KnuthBendix.Words.Word — Type
Word{T} <: AbstractWord{T}

Word as written in an alphabet storing only letters indices in an Alphabet.

The letters are stored in a plain Vector{T} field.

If type is not specified in the constructor it will default to UInt16.

source
KnuthBendix.Words.SubWord — Type
SubWord{...}

A non-copying view into an existing word.

SubWords are note intended to be constructed by other means than view function or the @view macro.

julia> w = Word(1:5)
Word{UInt16}: 1·2·3·4·5

julia> v = @view w[3:5]
KnuthBendix.Words.SubWord{UInt16, SubArray{UInt16, 1, Vector{UInt16}, Tuple{UnitRange{Int64}}, true}}: 3·4·5

julia> length(v)
3
source
KnuthBendix.Words.BufferWord — Type
BufferWord{T} <: AbstractWord{T}
BufferWord{T}([content::AbstractVector],
    free_before::Integer = 8,
    free_after::Integer = 8,
    [check = true])

A word type with constant complexity push! and popfirst! operations. Ideal for Rewriting(@ref).

The letters are stored in a plain Vector{T} field. In contrast to Word(@ref Words.Word) the push! pop!, pushfirst!, popfirst! etc. operations are (amortized) O(1) complexity. BufferWord achieves this by storing pointers to the beginning and the end of the valid part of the storage and consistent indexing.

If type is not specified in the constructor it will default to UInt16.

source