gaddag

package
v0.0.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 4, 2022 License: GPL-3.0 Imports: 13 Imported by: 0

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

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

Variables

This section is empty.

Functions

func CacheLoadFunc 

func CacheLoadFunc(cfg *config.Config, key string) (interface{}, error)

CacheLoadFunc is the function that loads an object into the global cache.

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 FindMachineWord 

func FindMachineWord(d GenericDawg, word alphabet.MachineWord) bool

FindMachineWord finds a word in a dawg or gaddag.

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

func Set 

func Set(name string, data []byte, t GenericDawgType) error

Set loads a gaddag from bytes and populates the cache

Types

type DawgAnagrammer 

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

zero value works. not threadsafe.

func (*DawgAnagrammer) Anagram 

func (da *DawgAnagrammer) Anagram(dawg GenericDawg, f func(alphabet.MachineWord) error) error

func (*DawgAnagrammer) InitForMachineWord 

func (da *DawgAnagrammer) InitForMachineWord(dawg GenericDawg, machineTiles alphabet.MachineWord) error

supports 0-25 and alphabet.BlankMachineLetter only

func (*DawgAnagrammer) InitForString 

func (da *DawgAnagrammer) InitForString(dawg GenericDawg, tiles string) error

supports A-Z and ? only

func (*DawgAnagrammer) IsValidJumble 

func (da *DawgAnagrammer) IsValidJumble(dawg GenericDawg, word alphabet.MachineWord) (bool, error)

checks if a word with no blanks has any valid anagrams.

func (*DawgAnagrammer) Subanagram 

func (da *DawgAnagrammer) Subanagram(dawg GenericDawg, f func(alphabet.MachineWord) error) error

func (*DawgAnagrammer) Superanagram 

func (da *DawgAnagrammer) Superanagram(dawg GenericDawg, f func(alphabet.MachineWord) error) error

type GenericDawg 

type GenericDawg interface {
	GetLetterSet(nodeIdx uint32) alphabet.LetterSet
	InLetterSet(letter alphabet.MachineLetter, nodeIdx uint32) bool
	GetAlphabet() *alphabet.Alphabet
	LexiconName() string
	Nodes() []uint32
	NumArcs(nodeIdx uint32) byte
	ArcToIdxLetter(arcIdx uint32) (uint32, alphabet.MachineLetter)
	GetRootNodeIndex() uint32
	NextNodeIdx(uint32, alphabet.MachineLetter) uint32
	Type() GenericDawgType
}

type GenericDawgType 

type GenericDawgType string
const (
	TypeGaddag GenericDawgType = "gaddag"
	TypeDawg   GenericDawgType = "dawg"
)

type Lexicon 

type Lexicon struct {
	GenericDawg
}

func (Lexicon) HasAnagram 

func (l Lexicon) HasAnagram(word alphabet.MachineWord) bool

func (Lexicon) HasWord 

func (l Lexicon) HasWord(word alphabet.MachineWord) bool

func (Lexicon) Name 

func (l Lexicon) Name() string

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 GetDawg 

func GetDawg(cfg *config.Config, name string) (*SimpleDawg, error)

GetDawg loads a named dawg from the cache or from a file

func LoadDawg 

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

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

func ReadDawg 

func ReadDawg(data io.Reader) (*SimpleDawg, error)

func (*SimpleDawg) Reverse 

func (s *SimpleDawg) Reverse() bool

Reverse returns true if this is a "reverse" dawg

func (*SimpleDawg) Type 

func (s *SimpleDawg) Type() GenericDawgType

type SimpleGaddag 

type SimpleGaddag struct {
	// 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 Get 

func Get(cfg *config.Config, name string) (*SimpleGaddag, error)

Get loads a named gaddag from the cache or from a file

func LoadGaddag 

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

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

func ScanGaddag 

func ScanGaddag(data io.Reader) (*SimpleGaddag, error)

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) Nodes 

func (g *SimpleGaddag) Nodes() []uint32

func (*SimpleGaddag) NumArcs 

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

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

func (*SimpleGaddag) Type 

func (g *SimpleGaddag) Type() GenericDawgType

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.