I am new to the language.
How to implement Trie data structure? https://en.wikipedia.org/wiki/Trie
I don't understand how to create an object that references itself. Example:
Node
Children Node[Alphabet-Size]
Is-Terminal Boolean
Value Data-Type
end structure
I don't understand how to create an object that references itself
You just use ref object
type
Node* = ref object
children: seq[Node]
name: string
var x = Node(name: "x", children: @[Node(name: "y")])
There is a more fully worked out example in https://github.com/c-blake/cligen/blob/master/cligen/trie.nim -- the core idea is over by line 63.
I may soon be lifting the ternary search tree, that unordered trie, and that which uses both, the automatic glob-abbreviation system, into their own package.
Also note that since I use seq[ref NodeOb[T]] instead of array[AlphaSize, ..] the "memory indirection depth" is 2X larger to get space savings that is, well, dependent upon the memory allocator in use. Using less space for all those alphabet pointers is a cottage industry of digital search tree optimization.
Juste object works ?
type
Node* = object
children: seq[Node]
name: string
var x = Node(name: "x", children: @[Node(name: "y")])