gaddag

package
v0.0.9 Latest Latest
Warning

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

 Go to latest Published: Sep 5, 2017 License: GPL-3.0 Imports: 8 Imported by: 1

Documentation

Overview

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

Here we have utility functions for creating a GADDAG.

This is the RPC API for the gaddag package.

Utility functions for doing cool things with gaddags.

Index

Constants

View Source 
const (
	MAX_DEPTH      = 16
	LETTER_BUCKETS = 100
)
View Source 
const (
	BackHooks      = 0
	FrontHooks     = 1
	BackInnerHook  = 2
	FrontInnerHook = 3
)
View Source 
const LetterBitLoc = 24
View Source 
const (
	// MaxAlphabetSize is the maximum size of the alphabet, and is also
	// the "code" for the separation token.
	MaxAlphabetSize = 31
)
View Source 
const NumArcsBitLoc = 24
View Source 
const SeparationToken = '^'

SeparationToken is the GADDAG separation token.

Variables

This section is empty.

Functions

func FindHooks added in v0.0.4 

func FindHooks(g SimpleGaddag, word string, hookType int) []rune

func FindInnerHook added in v0.0.4 

func FindInnerHook(g SimpleGaddag, 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 added in v0.0.4 

func FindPrefix(g SimpleGaddag, prefix string) bool

FindPrefix returns a boolean indicating if the prefix is in the GADDAG. This function is meant to be exported.

func FindWord added in v0.0.4 

func FindWord(g SimpleGaddag, word string) bool

func FindWordDawg added in v0.0.5 

func FindWordDawg(g SimpleGaddag, word string) bool

Finds a word in a SimpleGaddag that is a DAWG. The word can just be found verbatim.

Types

type Alphabet added in v0.0.4 

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

This file defines an alphabet. For now, don't create gaddags for alphabets with more than 31 unique runes. Our file format will not yet support it. The vals map has uint32 values for simplicity in serialization. It's ok to waste a few bytes here and there...

func (*Alphabet) Init added in v0.0.4 

func (a *Alphabet) Init()

func (Alphabet) Letter added in v0.0.5 

func (a Alphabet) Letter(b byte) rune

Return the letter that this position in the alphabet corresponds to.

func (Alphabet) NumLetters added in v0.0.5 

func (a Alphabet) NumLetters() uint8

Return the number of letters in this alphabet.

func (*Alphabet) Reconcile added in v0.0.4 

func (a *Alphabet) Reconcile()

Reconcile will take a populated alphabet, sort the glyphs, and re-index the numbers.

func (*Alphabet) Serialize added in v0.0.4 

func (a *Alphabet) Serialize() []uint32

func (Alphabet) Val added in v0.0.5 

func (a Alphabet) Val(r rune) (uint32, error)

Return the 'value' of this rune in the alphabet; i.e. a number from 0 to 31

type Arc 

type Arc struct {
	Letter      rune
	Destination *Node
}

Arc is also a temporary type.

type ArcPtrSlice 

type ArcPtrSlice []*Arc

func (ArcPtrSlice) Len 

func (a ArcPtrSlice) Len() int

func (ArcPtrSlice) Less 

func (a ArcPtrSlice) Less(i, j int) bool

func (ArcPtrSlice) Swap 

func (a ArcPtrSlice) Swap(i, j int)

type Gaddag added in v0.0.2 

type Gaddag struct {
	Root               *Node
	AllocStates        uint32
	AllocArcs          uint32
	SerializedElements []uint32
	Alphabet           *Alphabet
}

Gaddag is a temporary structure to hold the nodes in sequential order prior to writing them to file. It should not be used after making the gaddag.

func GenerateDawg added in v0.0.5 

func GenerateDawg(filename string, minimize bool, writeToFile bool) *Gaddag

GenerateDawg makes a GADDAG with only one permutation of letters allowed per word, the spelled-out permutation. We still treat it for all intents and purposes as a GADDAG, but note that it only has one path!

func GenerateGaddag 

func GenerateGaddag(filename string, minimize bool, writeToFile bool) *Gaddag

GenerateGaddag makes a GADDAG out of the filename, and optionally minimizes it and/or writes it to file.

func (*Gaddag) Minimize added in v0.0.2 

func (g *Gaddag) Minimize()

Minimize is a method to minimize the passed-in GADDAG! It works by first calculating the depths and letter sums of all nodes. It uses these values to sort the nodes into a two-dimensional array, to greatly minimize the number of required comparisons.

func (*Gaddag) Save added in v0.0.2 

func (g *Gaddag) Save(filename string)

Saves the GADDAG to a file.

type GaddagService 

type GaddagService struct{}

func (*GaddagService) Generate 

func (g *GaddagService) Generate(r *http.Request, args *GaddagServiceArgs,
	reply *GaddagServiceReply) error

func (*GaddagService) GenerateDawg added in v0.0.5 

func (g *GaddagService) GenerateDawg(r *http.Request, args *GaddagServiceArgs,
	reply *GaddagServiceReply) error

type GaddagServiceArgs 

type GaddagServiceArgs struct {
	Filename string `json:"filename"`
	Minimize bool   `json:"minimize"`
}

type GaddagServiceReply 

type GaddagServiceReply struct {
	Message string `json:"message"`
}

type LetterSlice added in v0.0.4 

type LetterSlice []rune

func (LetterSlice) Len added in v0.0.4 

func (a LetterSlice) Len() int

func (LetterSlice) Less added in v0.0.4 

func (a LetterSlice) Less(i, j int) bool

func (LetterSlice) Swap added in v0.0.4 

func (a LetterSlice) Swap(i, j int)

type Node 

type Node struct {
	Arcs      []*Arc
	NumArcs   uint8
	LetterSet uint32
	// contains filtered or unexported fields
}

Node is a temporary type used in the creation of a GADDAG. It will not be used when loading the GADDAG.

func (*Node) Equals added in v0.0.2 

func (node *Node) Equals(other *Node) bool

Equals compares two nodes. They are the same if they have the same letter sets, the same arc letters, and all their children are the same.

type NodeArr added in v0.0.2 

type NodeArr []*Node

type NodeBucket added in v0.0.2 

type NodeBucket [][]NodeArr

type SimpleDawg added in v0.0.5 

type SimpleDawg SimpleGaddag

type SimpleGaddag added in v0.0.3 

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

func LoadGaddag added in v0.0.2 

func LoadGaddag(filename string) SimpleGaddag

LoadGaddag loads a gaddag from a file and returns the slice of nodes.

func (SimpleGaddag) ArcToIdxLetter added in v0.0.3 

func (g SimpleGaddag) ArcToIdxLetter(arcIdx uint32) (
	uint32, rune)

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

func (SimpleGaddag) GetAlphabet added in v0.0.5 

func (g SimpleGaddag) GetAlphabet() *Alphabet

func (SimpleGaddag) GetLetterSet added in v0.0.4 

func (g SimpleGaddag) GetLetterSet(nodeIdx uint32) uint32

GetLetterSet gets the letter set of the node at nodeIdx.

func (SimpleGaddag) GetRootNodeIndex added in v0.0.4 

func (g SimpleGaddag) GetRootNodeIndex() uint32

GetRootNodeIndex gets the index of the root node.

func (SimpleGaddag) InLetterSet added in v0.0.4 

func (g SimpleGaddag) InLetterSet(letter rune, nodeIdx uint32) bool

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

func (SimpleGaddag) LetterSetAsRunes added in v0.0.4 

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

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

func (SimpleGaddag) NumArcs added in v0.0.5 

func (g SimpleGaddag) NumArcs(nodeIdx uint32) byte

func (*SimpleGaddag) SetAlphabet added in v0.0.4 

func (g *SimpleGaddag) SetAlphabet()

SetAlphabet recreates the Alphabet structure stored in this SimpleGaddag, and stores it in g.alphabet

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.