A red/black binary search tree
Types
RedBlackTree[T; K] = object root: Node[T]
-
A Red/Black tree
- T is the type of value being stored
- K is the type of key used to index those values
TreeElem = concept e ## An individual element stored in a RedBlackTree cmp(e, e) is int
Procs
proc `$`[T: TreeElem; K](self: RedBlackTree[T, K]): string
- Returns a tree as a string
proc ceil[T: TreeElem; K](tree: RedBlackTree[T, K]; key: K): Option[T]
- Returns the value in this tree that is equal to or just greater than the given value
proc contains[T: TreeElem; K](tree: RedBlackTree[T, K]; value: T | K): bool
- Returns whether this tree contains the specific value or key
proc delete[T: TreeElem; K](self: var RedBlackTree[T, K]; value: T)
- Deletes a value from the tree
proc find[T: TreeElem; K](tree: RedBlackTree[T, K]; key: K): Option[T]
- Searches for a value by its key
proc floor[T: TreeElem; K](tree: RedBlackTree[T, K]; key: K): Option[T]
- Returns the value in this tree that is equal to or just less than the given value
proc insert[T: TreeElem; K](self: var RedBlackTree[T, K]; one: T; two: T; more: varargs[T])
- Adds multiple values to this tree
proc insert[T: TreeElem; K](self: var RedBlackTree[T, K]; value: T)
- Adds a value to this tree
proc isEmpty[T: TreeElem; K](tree: RedBlackTree[T, K]): bool
- Returns whether this tree is empty of any nodes
proc max[T: TreeElem; K](tree: RedBlackTree[T, K]): Option[T]
- Returns the minimum value in a tree
proc min[T: TreeElem; K](tree: RedBlackTree[T, K]): Option[T]
- Returns the minimum value in a tree
proc newRBTree[T: TreeElem; K](): RedBlackTree[T, K]
- Creates a new Red/Black tree
proc validate[T: TreeElem; K](tree: RedBlackTree[T, K])
- Raises an assertion exception if a red/black tree is corrupt. This is primarily for testing purposes and isn't something you should need to call from an application.
Iterators
iterator items[T: TreeElem; K](tree: RedBlackTree[T, K]): T
- Iterates over each value in a tree
iterator reversed[T: TreeElem; K](tree: RedBlackTree[T, K]): T
- Iterates over each value in a tree in reverse order
Templates
template defineIndex(name, source, extractIt, cmpAB: untyped)
-
Defines a distinct type with custom extract and cmp methods. This makes it easy to index the same data in different ways. It also defines converters to make the new type fairly transparent.
- name: The name of the type to define
- source: The type to derive from. This is done via distinct
- extractIt: The body of the extract function. There will be a variable named it defined that is the value from which a key needs to be pulled.
- cmpAB: The body of the cmp function. There will be two variables named a and b defined. These are the arguments to the cmp proc that need to be compared.