gaddag

Documentation

Overview

Package gaddag implements the GADDAG, a pretty cool data structure invented by Steven Gordon.

Utility functions for doing cool things with gaddags.

Index

• Constants
• func FindHooks(d *SimpleDawg, word string, hookType int) []rune
• func FindInnerHook(d *SimpleDawg, word string, hookType int) bool
• func FindPrefix(d *SimpleDawg, prefix string) bool
• func FindWord(d *SimpleDawg, word string) bool
• type SimpleDawg
  • func LoadDawg(filename string) (*SimpleDawg, error)
  • func (s *SimpleDawg) Reverse() bool
• type SimpleGaddag
  • func GaddagToSimpleGaddag(g *gaddagmaker.Gaddag) *SimpleGaddag
  • func LoadGaddag(filename string) (*SimpleGaddag, error)
  • func (g *SimpleGaddag) ArcToIdxLetter(arcIdx uint32) (uint32, alphabet.MachineLetter)
  • func (g *SimpleGaddag) GetAlphabet() *alphabet.Alphabet
  • func (g *SimpleGaddag) GetLetterSet(nodeIdx uint32) alphabet.LetterSet
  • func (g *SimpleGaddag) GetRootNodeIndex() uint32
  • func (g *SimpleGaddag) InLetterSet(letter alphabet.MachineLetter, nodeIdx uint32) bool
  • func (g *SimpleGaddag) LetterSetAsRunes(nodeIdx uint32) []rune
  • func (g *SimpleGaddag) LexiconName() string
  • func (g *SimpleGaddag) NextNodeIdx(nodeIdx uint32, letter alphabet.MachineLetter) uint32
  • func (g *SimpleGaddag) NumArcs(nodeIdx uint32) byte

Constants

const (
	BackHooks      = 0
	FrontHooks     = 1
	BackInnerHook  = 2
	FrontInnerHook = 3
)

Functions

func FindHooks

func FindHooks(d *SimpleDawg, word string, hookType int) []rune

func FindInnerHook

func FindInnerHook(d *SimpleDawg, word string, hookType int) bool

FindInnerHook finds whether the word has a back or front "inner hook", that is, whether if you remove the back or front letter, you can still make a word.

func FindPrefix

func FindPrefix(d *SimpleDawg, prefix string) bool

FindPrefix finds a partial word in the Dawg.

func FindWord

func FindWord(d *SimpleDawg, word string) bool

FindWord finds a word in a SimpleDawg

Types

type SimpleDawg

type SimpleDawg struct {
	SimpleGaddag
	// contains filtered or unexported fields
}

SimpleDawg is basically a SimpleGaddag, but with only one pathway. The structures are otherwise totally compatible. The SimpleDawg should only be used by anagramming utilities due to its smaller size.

func LoadDawg

func LoadDawg(filename string) (*SimpleDawg, error)

LoadDawg loads a dawg from a file and returns a *SimpleDawg

func (*SimpleDawg) Reverse

func (s *SimpleDawg) Reverse() bool

Reverse returns true if this is a "reverse" dawg

type SimpleGaddag

type SimpleGaddag struct {
	// Nodes is just a slice of 32-bit elements, the node array.
	Nodes []uint32
	// The bit-mask letter sets
	LetterSets []alphabet.LetterSet
	// contains filtered or unexported fields
}

SimpleGaddag is the result of loading the gaddag back into memory. Rather than contain an entire tree of linked nodes, arcs, etc it will be easier and faster to do bitwise operations on a 32-bit array. A SimpleGaddag.Nodes is just a slice of 32-bit elements. It is created by serializeElements in make_gaddag.go. File Schema: [4-byte magic number] [1-byte length (LX_LEN)] [utf-8 encoded bytes with lexicon name, length of bytes being LX_LEN] [alphabetlength] [letters...] (up to 60+?) [lettersetlength] [lettersets] (64-bit binary bit masks) a set of [node] [arcs...] Where node is a 32-bit number: LetterSetIdx + (NumArcs << NumArcsBitLoc) Each arc is a 32-bit number: (letter << LetterBitLoc) + index of next node, where letter is an index from 0 to MaxAlphabetSize into alphabet (except for MaxAlphabetSize, which is the SeparationToken), and the index of the node is the index of the element in the SimpleGaddag.Nodes array.

If the node has no arcs, the arc array is empty.

func GaddagToSimpleGaddag

func GaddagToSimpleGaddag(g *gaddagmaker.Gaddag) *SimpleGaddag

func LoadGaddag

func LoadGaddag(filename string) (*SimpleGaddag, error)

LoadGaddag loads a gaddag from a file and returns a *SimpleGaddag structure.

func (*SimpleGaddag) ArcToIdxLetter

func (g *SimpleGaddag) ArcToIdxLetter(arcIdx uint32) (uint32, alphabet.MachineLetter)

ArcToIdxLetter finds the index of the node pointed to by this arc and returns it and the letter.

func (*SimpleGaddag) GetAlphabet

func (g *SimpleGaddag) GetAlphabet() *alphabet.Alphabet

GetAlphabet returns the alphabet for this gaddag.

func (*SimpleGaddag) GetLetterSet

func (g *SimpleGaddag) GetLetterSet(nodeIdx uint32) alphabet.LetterSet

GetLetterSet gets the letter set of the node at nodeIdx.

func (*SimpleGaddag) GetRootNodeIndex

func (g *SimpleGaddag) GetRootNodeIndex() uint32

GetRootNodeIndex gets the index of the root node.

func (*SimpleGaddag) InLetterSet

func (g *SimpleGaddag) InLetterSet(letter alphabet.MachineLetter, nodeIdx uint32) bool

InLetterSet returns whether the `letter` is in the node at `nodeIdx`'s letter set.

func (*SimpleGaddag) LetterSetAsRunes

func (g *SimpleGaddag) LetterSetAsRunes(nodeIdx uint32) []rune

LetterSetAsRunes returns the letter set of the node at `nodeIdx` as a slice of runes.

func (*SimpleGaddag) LexiconName

func (g *SimpleGaddag) LexiconName() string

LexiconName returns the name of the lexicon.

func (*SimpleGaddag) NextNodeIdx

func (g *SimpleGaddag) NextNodeIdx(nodeIdx uint32, letter alphabet.MachineLetter) uint32

NextNodeIdx is analogous to NextArc in the Gordon paper. The main difference is that in Gordon, the initial state is an arc pointing to the first node. In our implementation of the GADDAG, the initial state is that first node. So we have to think in terms of the node that was pointed to, rather than the pointing arc. There is something slightly wrong with the paper as it does not seem possible to implement in exactly Gordon's way without running into issues. (See my notes in my `ujamaa` repo in gaddag.h)

func (*SimpleGaddag) NumArcs

func (g *SimpleGaddag) NumArcs(nodeIdx uint32) byte

NumArcs is simply the number of arcs for the given node.