gaddagmaker

Documentation

Overview

Here we have utility functions for creating a GADDAG.

Index

• Constants
• type Arc
• type ArcPtrSlice
  • func (a ArcPtrSlice) Len() int
  • func (a ArcPtrSlice) Less(i, j int) bool
  • func (a ArcPtrSlice) Swap(i, j int)
• type Gaddag
  • func GenerateDawg(filename string, minimize bool, writeToFile bool, reverse bool) *Gaddag
  • func GenerateGaddag(filename string, minimize bool, writeToFile bool) *Gaddag
  • func GenerateGaddagFromStream(stream io.Reader, lexName string) *Gaddag
  • func (g *Gaddag) Minimize()
  • func (g *Gaddag) Save(filename string, magicNumber string)
  • func (g *Gaddag) SerializeElements()
  • func (g *Gaddag) Write(stream io.Writer)
• type Node
  • func (node *Node) Equals(other *Node) bool
• type NodeArr
• type NodeBucket

Constants

const (
	GaddagMagicNumber      = "cgdg"
	DawgMagicNumber        = "cdwg"
	ReverseDawgMagicNumber = "rdwg"
)

const (
	MaxDepth      = 35
	LetterBuckets = 997
)

const LetterBitLoc = 24

LetterBitLoc is the location where the letter starts. An Arc has a letter and a next node.

const LetterSetBitMask = (1 << NumArcsBitLoc) - 1

const NodeIdxBitMask = (1 << LetterBitLoc) - 1

const NumArcsBitLoc = 24

NumArcsBitLoc is the bit location where the number of arcs start. A Node has a number of arcs and a letterSet

Types

type Arc

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

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

type Gaddag struct {
	Root        *Node
	AllocStates uint32
	AllocArcs   uint32

	SerializedAlphabet   []uint32
	NumLetterSets        uint32
	SerializedLetterSets []alphabet.LetterSet
	SerializedNodes      []uint32
	Alphabet             *alphabet.Alphabet
	// contains filtered or unexported fields
}

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

func GenerateDawg(filename string, minimize bool, writeToFile bool, reverse 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 GenerateGaddagFromStream

func GenerateGaddagFromStream(stream io.Reader, lexName string) *Gaddag

func (*Gaddag) Minimize

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

func (g *Gaddag) Save(filename string, magicNumber string)

Save saves the GADDAG or DAWG to a file.

func (*Gaddag) SerializeElements

func (g *Gaddag) SerializeElements()

Serializes the elements of the gaddag into the various arrays.

func (*Gaddag) Write

func (g *Gaddag) Write(stream io.Writer)

Write writes serialized elements to the given stream.

type Node

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

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

type NodeArr []*Node

type NodeBucket

type NodeBucket [][]NodeArr