Documentation
¶
Index ¶
- Constants
- func AVLInOrder(root *AVLNode, action action)
- func AVLMax(a, b int) int
- func AVLPostOrder(root *AVLNode, action action)
- func AVLPreOrder(root *AVLNode, action action)
- type AVLNode
- type BTree
- func (t *BTree) Ascend(iterator ItemIterator)
- func (t *BTree) AscendGreaterOrEqual(pivot BTreeItem, iterator ItemIterator)
- func (t *BTree) AscendLessThan(pivot BTreeItem, iterator ItemIterator)
- func (t *BTree) AscendRange(greaterOrEqual, lessThan BTreeItem, iterator ItemIterator)
- func (t *BTree) Clear(addNodesToFreelist bool)
- func (t *BTree) Clone() (t2 *BTree)
- func (t *BTree) Delete(item BTreeItem) BTreeItem
- func (t *BTree) DeleteMax() BTreeItem
- func (t *BTree) DeleteMin() BTreeItem
- func (t *BTree) Descend(iterator ItemIterator)
- func (t *BTree) DescendGreaterThan(pivot BTreeItem, iterator ItemIterator)
- func (t *BTree) DescendLessOrEqual(pivot BTreeItem, iterator ItemIterator)
- func (t *BTree) DescendRange(lessOrEqual, greaterThan BTreeItem, iterator ItemIterator)
- func (t *BTree) Get(key BTreeItem) BTreeItem
- func (t *BTree) Has(key BTreeItem) bool
- func (t *BTree) Len() int
- func (t *BTree) Max() BTreeItem
- func (t *BTree) Min() BTreeItem
- func (t *BTree) ReplaceOrInsert(item BTreeItem) BTreeItem
- type BTreeItem
- type BinarySearchTree
- func (t *BinarySearchTree) Delete(node *TreeNode)
- func (t *BinarySearchTree) InOrderTreeWalk() []int
- func (t *BinarySearchTree) Insert(item int)
- func (t *BinarySearchTree) Invert() *BinarySearchTree
- func (t *BinarySearchTree) Join(other *BinarySearchTree) *BinarySearchTree
- func (t *BinarySearchTree) Minimum() *TreeNode
- func (t *BinarySearchTree) PostOrderTreeWalk() []int
- func (t *BinarySearchTree) PreOrderTreeWalk() []int
- func (t *BinarySearchTree) Replace(src, dest *TreeNode)
- func (t *BinarySearchTree) Search(item int) *TreeNode
- func (t *BinarySearchTree) Size() int
- type FreeList
- type Graph
- type HeapPriorityQueue
- func (pq HeapPriorityQueue) IsEmpty() bool
- func (pq HeapPriorityQueue) Len() int
- func (pq HeapPriorityQueue) Less(i, j int) bool
- func (pq HeapPriorityQueue) Next() interface{}
- func (pq *HeapPriorityQueue) Pop() interface{}
- func (pq *HeapPriorityQueue) Push(i interface{})
- func (pq HeapPriorityQueue) Swap(i, j int)
- type Int
- type ItemIterator
- type LinkedList
- type Node
- type Path
- type Paths
- type PriorityQueue
- type PriorityQueueItem
- type Queue
- type Stack
- type TreeNode
- func (n *TreeNode) InOrderTreeWalk() []int
- func (n *TreeNode) Insert(item int)
- func (n *TreeNode) IsContinous() bool
- func (n *TreeNode) IsFoldable() bool
- func (n *TreeNode) Minimum() *TreeNode
- func (n *TreeNode) PostOrderTreeWalk() []int
- func (n *TreeNode) PreOrderTreeWalk() []int
- func (n *TreeNode) Search(item int) *TreeNode
- func (n *TreeNode) Size() int
- func (n *TreeNode) Sucessor() *TreeNode
- type Vertex
- type WeightedEdge
- type WeightedGraph
- type WeightedVertex
Constants ¶
const (
DefaultFreeListSize = 32
)
Variables ¶
This section is empty.
Functions ¶
func AVLInOrder ¶
func AVLInOrder(root *AVLNode, action action)
func AVLPostOrder ¶
func AVLPostOrder(root *AVLNode, action action)
func AVLPreOrder ¶
func AVLPreOrder(root *AVLNode, action action)
Types ¶
type BTree ¶
type BTree struct {
// contains filtered or unexported fields
}
BTree is an implementation of a B-Tree.
BTree stores Item instances in an ordered structure, allowing easy insertion, removal, and iteration.
Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are.
func New ¶
New creates a new B-Tree with the given degree.
New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items and 2-4 children).
func NewWithFreeList ¶
NewWithFreeList creates a new B-Tree that uses the given node free list.
func (*BTree) Ascend ¶
func (t *BTree) Ascend(iterator ItemIterator)
Ascend calls the iterator for every value in the tree within the range [first, last], until iterator returns false.
func (*BTree) AscendGreaterOrEqual ¶
func (t *BTree) AscendGreaterOrEqual(pivot BTreeItem, iterator ItemIterator)
AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until iterator returns false.
func (*BTree) AscendLessThan ¶
func (t *BTree) AscendLessThan(pivot BTreeItem, iterator ItemIterator)
AscendLessThan calls the iterator for every value in the tree within the range [first, pivot), until iterator returns false.
func (*BTree) AscendRange ¶
func (t *BTree) AscendRange(greaterOrEqual, lessThan BTreeItem, iterator ItemIterator)
AscendRange calls the iterator for every value in the tree within the range [greaterOrEqual, lessThan), until iterator returns false.
func (*BTree) Clear ¶
Clear removes all items from the btree. If addNodesToFreelist is true, t's nodes are added to its freelist as part of this call, until the freelist is full. Otherwise, the root node is simply dereferenced and the subtree left to Go's normal GC processes.
This can be much faster than calling Delete on all elements, because that requires finding/removing each element in the tree and updating the tree accordingly. It also is somewhat faster than creating a new tree to replace the old one, because nodes from the old tree are reclaimed into the freelist for use by the new one, instead of being lost to the garbage collector.
This call takes:
O(1): when addNodesToFreelist is false, this is a single operation.
O(1): when the freelist is already full, it breaks out immediately
O(freelist size): when the freelist is empty and the nodes are all owned
by this tree, nodes are added to the freelist until full.
O(tree size): when all nodes are owned by another tree, all nodes are
iterated over looking for nodes to add to the freelist, and due to
ownership, none are.
func (*BTree) Clone ¶
Clone clones the btree, lazily. Clone should not be called concurrently, but the original tree (t) and the new tree (t2) can be used concurrently once the Clone call completes.
The internal tree structure of b is marked read-only and shared between t and t2. Writes to both t and t2 use copy-on-write logic, creating new nodes whenever one of b's original nodes would have been modified. Read operations should have no performance degredation. Write operations for both t and t2 will initially experience minor slow-downs caused by additional allocs and copies due to the aforementioned copy-on-write logic, but should converge to the original performance characteristics of the original tree.
func (*BTree) Delete ¶
Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns nil.
func (*BTree) DeleteMax ¶
DeleteMax removes the largest item in the tree and returns it. If no such item exists, returns nil.
func (*BTree) DeleteMin ¶
DeleteMin removes the smallest item in the tree and returns it. If no such item exists, returns nil.
func (*BTree) Descend ¶
func (t *BTree) Descend(iterator ItemIterator)
Descend calls the iterator for every value in the tree within the range [last, first], until iterator returns false.
func (*BTree) DescendGreaterThan ¶
func (t *BTree) DescendGreaterThan(pivot BTreeItem, iterator ItemIterator)
DescendGreaterThan calls the iterator for every value in the tree within the range (pivot, last], until iterator returns false.
func (*BTree) DescendLessOrEqual ¶
func (t *BTree) DescendLessOrEqual(pivot BTreeItem, iterator ItemIterator)
DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until iterator returns false.
func (*BTree) DescendRange ¶
func (t *BTree) DescendRange(lessOrEqual, greaterThan BTreeItem, iterator ItemIterator)
DescendRange calls the iterator for every value in the tree within the range [lessOrEqual, greaterThan), until iterator returns false.
func (*BTree) Get ¶
Get looks for the key item in the tree, returning it. It returns nil if unable to find that item.
func (*BTree) ReplaceOrInsert ¶
ReplaceOrInsert adds the given item to the tree. If an item in the tree already equals the given one, it is removed from the tree and returned. Otherwise, nil is returned.
nil cannot be added to the tree (will panic).
type BinarySearchTree ¶
type BinarySearchTree struct {
Root *TreeNode
}
func (*BinarySearchTree) Delete ¶
func (t *BinarySearchTree) Delete(node *TreeNode)
func (*BinarySearchTree) InOrderTreeWalk ¶
func (t *BinarySearchTree) InOrderTreeWalk() []int
func (*BinarySearchTree) Insert ¶
func (t *BinarySearchTree) Insert(item int)
func (*BinarySearchTree) Join ¶
func (t *BinarySearchTree) Join(other *BinarySearchTree) *BinarySearchTree
func (*BinarySearchTree) Minimum ¶
func (t *BinarySearchTree) Minimum() *TreeNode
func (*BinarySearchTree) PostOrderTreeWalk ¶
func (t *BinarySearchTree) PostOrderTreeWalk() []int
func (*BinarySearchTree) PreOrderTreeWalk ¶
func (t *BinarySearchTree) PreOrderTreeWalk() []int
func (*BinarySearchTree) Replace ¶
func (t *BinarySearchTree) Replace(src, dest *TreeNode)
func (*BinarySearchTree) Search ¶
func (t *BinarySearchTree) Search(item int) *TreeNode
func (*BinarySearchTree) Size ¶
func (t *BinarySearchTree) Size() int
type FreeList ¶
type FreeList struct {
// contains filtered or unexported fields
}
FreeList represents a free list of btree nodes. By default each BTree has its own FreeList, but multiple BTrees can share the same FreeList. Two Btrees using the same freelist are safe for concurrent write access.
func NewFreeList ¶
NewFreeList creates a new free list. size is the maximum size of the returned free list.
type HeapPriorityQueue ¶
type HeapPriorityQueue []*PriorityQueueItem
func NewHeapPriorityQueue ¶
func NewHeapPriorityQueue() *HeapPriorityQueue
func (HeapPriorityQueue) IsEmpty ¶
func (pq HeapPriorityQueue) IsEmpty() bool
func (HeapPriorityQueue) Len ¶
func (pq HeapPriorityQueue) Len() int
func (HeapPriorityQueue) Less ¶
func (pq HeapPriorityQueue) Less(i, j int) bool
func (HeapPriorityQueue) Next ¶
func (pq HeapPriorityQueue) Next() interface{}
func (*HeapPriorityQueue) Pop ¶
func (pq *HeapPriorityQueue) Pop() interface{}
func (*HeapPriorityQueue) Push ¶
func (pq *HeapPriorityQueue) Push(i interface{})
func (HeapPriorityQueue) Swap ¶
func (pq HeapPriorityQueue) Swap(i, j int)
type ItemIterator ¶
ItemIterator allows callers of Ascend* to iterate in-order over portions of the tree. When this function returns false, iteration will stop and the associated Ascend* function will immediately return.
type LinkedList ¶
type LinkedList struct {
Previous *LinkedList
Val interface{}
Next *LinkedList
}
func (*LinkedList) Add ¶
func (l *LinkedList) Add(item interface{})
func (*LinkedList) Get ¶
func (l *LinkedList) Get(i int) *LinkedList
func (*LinkedList) Len ¶
func (l *LinkedList) Len() int
func (*LinkedList) Remove ¶
func (l *LinkedList) Remove(i int)
type Path ¶
type Path struct {
ID string
Vertices []*WeightedVertex
Weight int
}
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
func NewPriorityQueue ¶
func NewPriorityQueue() *PriorityQueue
func (*PriorityQueue) IsEmpty ¶
func (q *PriorityQueue) IsEmpty() bool
func (*PriorityQueue) Pop ¶
func (q *PriorityQueue) Pop() *Path
func (*PriorityQueue) Push ¶
func (q *PriorityQueue) Push(item *Path)
type PriorityQueueItem ¶
type TreeNode ¶
func (*TreeNode) InOrderTreeWalk ¶
func (*TreeNode) IsContinous ¶
A tree is Continuous tree if in each root to leaf path, absolute difference between keys of two adjacent is 1. We are given a binary tree, we need to check if tree is continuous or not.
func (*TreeNode) IsFoldable ¶
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
func (*TreeNode) PostOrderTreeWalk ¶
func (*TreeNode) PreOrderTreeWalk ¶
type WeightedEdge ¶
type WeightedEdge struct {
Vertex *WeightedVertex
Weight int
}
type WeightedGraph ¶
type WeightedGraph struct {
Vertices map[string]*WeightedVertex
// contains filtered or unexported fields
}
func (*WeightedGraph) AddEdge ¶
func (g *WeightedGraph) AddEdge(a, b string, weight int, bidirictional bool)
func (*WeightedGraph) AddVertex ¶
func (g *WeightedGraph) AddVertex(value string) *WeightedVertex
func (*WeightedGraph) String ¶
func (g *WeightedGraph) String()
String Prints String Presentation of the Graph
type WeightedVertex ¶
type WeightedVertex struct {
Val string
Edges map[string]*WeightedEdge
}
func (*WeightedVertex) String ¶
func (n *WeightedVertex) String() string
Source Files