dawg

Documentation

Index

• type AnagramSearcher
  • func NewAnagramSearcher(anagram []byte, blank byte) *AnagramSearcher
  • func (p AnagramSearcher) AllowStep(b byte) bool
  • func (p AnagramSearcher) AllowWord() bool
  • func (p *AnagramSearcher) Backstep()
  • func (p AnagramSearcher) Chosen()
  • func (p *AnagramSearcher) Step(b byte)
• type Builder
  • func (db *Builder) Add(b []byte) error
  • func (db *Builder) Finish() (*Dawg, error)
  • func (db *Builder) Initialise()
• type Dawg
  • func New(s [][]byte) (*Dawg, error)
  • func (t *Dawg) GobDecode(b []byte) error
  • func (t *Dawg) GobEncode() ([]byte, error)
  • func (t *Dawg) Lookup(word []byte) (int, bool)
  • func (t *Dawg) NumberOfWords() int
  • func (t *Dawg) Search(searchers ...Searcher) (solns [][]byte, ids []int)
• type PatternSearcher
  • func NewPatternSearcher(pattern []byte, blank byte) *PatternSearcher
  • func (p PatternSearcher) AllowStep(b byte) bool
  • func (p PatternSearcher) AllowWord() bool
  • func (p *PatternSearcher) Backstep()
  • func (p PatternSearcher) Chosen()
  • func (p *PatternSearcher) Step(b byte)
• type Searcher

Types

type AnagramSearcher

type AnagramSearcher struct {
	// contains filtered or unexported fields
}

AnagramSearcher searches a dawg for words which have the same multiset of letters as the target. Any letters with the value blank are assumed to be wildcards and match any letter.

func NewAnagramSearcher

func NewAnagramSearcher(anagram []byte, blank byte) *AnagramSearcher

NewAnagramSearcher returns an anagram searcher to find anagrams of a word in a dawg with blanks.

func (AnagramSearcher) AllowStep

func (p AnagramSearcher) AllowStep(b byte) bool

AllowStep checks if taking the step b is valid from the current position.

func (AnagramSearcher) AllowWord

func (p AnagramSearcher) AllowWord() bool

AllowWord checks if the current position is allowed as a matching word.

func (*AnagramSearcher) Backstep

func (p *AnagramSearcher) Backstep()

Backstep undoes the last step from the searcher.This modifies the searcher.

func (AnagramSearcher) Chosen

func (p AnagramSearcher) Chosen()

Chosen notifies the searcher that the current position has been chosen as a valid word.

func (*AnagramSearcher) Step

func (p *AnagramSearcher) Step(b byte)

Step takes the step b from the current position. This modifies the searcher.

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder is a structure to incrementally build a Dawg by repeatedly adding words (using Add) until all words have been added and then calling Finish(). Words but be added in strictly increasing lexicographic order and duplicate words are not allowed. It is safe to add words directly to zero value without calling Initialise().

func (*Builder) Add

func (db *Builder) Add(b []byte) error

Add adds b to the dawg. Words but be added in lexicographic order with no duplicates and words cannot be added to a builder that has already finished.

func (*Builder) Finish

func (db *Builder) Finish() (*Dawg, error)

Finish returns the finished dawg. No further modifications may be made to the dawg and finish can only be called once.

func (*Builder) Initialise

func (db *Builder) Initialise()

Initialise sets up the internal state ready for use. This will be called automatically when calling Add() or Finish().

type Dawg

type Dawg struct {
	// contains filtered or unexported fields
}

Dawg is a directed acyclic word graph (also known as a deterministic acyclic finite state automaton) is a data structure for storing a set of []byte in efficiently while still being easy to query.

func New

func New(s [][]byte) (*Dawg, error)

New is a helper function which creates a dawg with the words in s. The words in s must be in lexicographic order with no duplicates.

func (*Dawg) GobDecode

func (t *Dawg) GobDecode(b []byte) error

GobDecode decodes the dawg given in b into t, replacing the current contents of t.

func (*Dawg) GobEncode

func (t *Dawg) GobEncode() ([]byte, error)

GobEncode encodes the dawg as a []byte suitable for sending or storage. It preserves the id of the nodes in case they are relevant for other data.

func (*Dawg) Lookup

func (t *Dawg) Lookup(word []byte) (int, bool)

Lookup returns the id of the node where the given word ends if it is present and a boolean representing indicating if the word is in the dawg.

func (*Dawg) NumberOfWords

func (t *Dawg) NumberOfWords() int

NumberOfWords returns the number of words stored in the dawg.

func (*Dawg) Search

func (t *Dawg) Search(searchers ...Searcher) (solns [][]byte, ids []int)

Search is used to find words which are accepted by all searchers simultaneously. It returns the solutions as words and also the indices of the words in lexicographic order.

type PatternSearcher

type PatternSearcher struct {
	// contains filtered or unexported fields
}

PatternSearcher searches the dawg for words where each letter matches the letter in the pattern except in the positions of the pattern which contain a blank.

func NewPatternSearcher

func NewPatternSearcher(pattern []byte, blank byte) *PatternSearcher

NewPatternSearcher returns a pattern searcher for searching with the given pattern and blank.

func (PatternSearcher) AllowStep

func (p PatternSearcher) AllowStep(b byte) bool

AllowStep checks if taking the step b is valid from the current position.

func (PatternSearcher) AllowWord

func (p PatternSearcher) AllowWord() bool

AllowWord checks if the current position is allowed as a matching word.

func (*PatternSearcher) Backstep

func (p *PatternSearcher) Backstep()

Backstep undoes the last step from the searcher.This modifies the searcher.

func (PatternSearcher) Chosen

func (p PatternSearcher) Chosen()

Chosen notifies the searcher that the current position has been chosen as a valid word.

func (*PatternSearcher) Step

func (p *PatternSearcher) Step(b byte)

Step takes the step b from the current position. This modifies the searcher.

type Searcher

type Searcher interface {
	AllowStep(b byte) bool
	Step(b byte)
	Backstep()

	AllowWord() bool
	Chosen()
}

Searcher is the interface for searching a dawg for words which match a condition.