gotemplate_orderTree.go

// Code generated by gotemplate. DO NOT EDIT.

// Copyright (c) 2015, Emir Pasic. All rights reserved.
// Copyright (c) 2021, E Sequeira. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package redblacktree implements a red-black tree.
//
// Used by TreeSet and TreeMap.
//
// Structure is not thread safe.
//
// References: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
package orderbook

import (
	"fmt"
)

type colorOrderTree bool

type comparatorOrderTree func(a, b uint64) int

const (
	blackOrderTree, redOrderTree colorOrderTree = true, false
)

// Tree holds elements of the red-black tree
type orderTree struct {
	Root       *nodeOrderTree
	size       int
	Comparator comparatorOrderTree
	Min        *nodeOrderTree
	Max        *nodeOrderTree
}

// template type Tree(KeyType, ValueType)

// Node is a single element within the tree
type nodeOrderTree struct {
	Key    uint64
	Value  *Order
	color  colorOrderTree
	Left   *nodeOrderTree
	Right  *nodeOrderTree
	Parent *nodeOrderTree
}

// NewWith instantiates a red-black tree with the custom comparator.
func newWithOrderTree(comparator comparatorOrderTree) *orderTree {
	return &orderTree{Comparator: comparator}
}

func newNodeOrderTree(key uint64, value *Order, color colorOrderTree) *nodeOrderTree {
	nt := notPool.Get()
	nt.Key = key
	nt.Value = value
	nt.color = color
	nt.Left = nil
	nt.Right = nil
	nt.Parent = nil

	return nt
}

func (n *nodeOrderTree) Release() {
	notPool.Put(n)
}

// Put inserts node into the tree.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) Put(key uint64, value *Order) {
	var insertedNode *nodeOrderTree
	if tree.Root == nil {
		// Assert key is of comparator's type for initial tree
		tree.Comparator(key, key)
		tree.Root = newNodeOrderTree(key, value, redOrderTree)
		insertedNode = tree.Root
		tree.Min = tree.Root
		tree.Max = tree.Root
	} else {
		node := tree.Root
		loop := true
		for loop {
			compare := tree.Comparator(key, node.Key)
			switch {
			case compare == 0:
				node.Key = key
				node.Value = value
				return
			case compare < 0:
				if node.Left == nil {
					node.Left = newNodeOrderTree(key, value, redOrderTree)
					insertedNode = node.Left
					loop = false
				} else {
					node = node.Left
				}
			case compare > 0:
				if node.Right == nil {
					node.Right = newNodeOrderTree(key, value, redOrderTree)
					insertedNode = node.Right
					loop = false
				} else {
					node = node.Right
				}
			}
		}
		insertedNode.Parent = node
	}
	tree.insertCase1(insertedNode)

	compare := tree.Comparator(insertedNode.Key, tree.Min.Key)
	if compare < 0 {
		tree.Min = insertedNode
	}
	compare = tree.Comparator(insertedNode.Key, tree.Max.Key)
	if compare > 0 {
		tree.Max = insertedNode
	}
	tree.size++
}

// Get searches the node in the tree by key and returns its value or nil if key is not found in tree.
// Second return parameter is true if key was found, otherwise false.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) Get(key uint64) (value *Order, found bool) {
	node := tree.lookup(key)
	if node != nil {
		return node.Value, true
	}
	return nil, false
}

// Remove remove the node from the tree by key.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) Remove(key uint64) {
	var child *nodeOrderTree
	node := tree.lookup(key)
	if node == nil {
		return
	}
	if node.Left != nil && node.Right != nil {
		pred := node.Left.maximumNode()
		node.Key = pred.Key
		node.Value = pred.Value
		node = pred
	}
	if node.Left == nil || node.Right == nil {
		if node.Right == nil {
			child = node.Left
		} else {
			child = node.Right
		}
		if node.color == blackOrderTree {
			node.color = nodeColorOrderTree(child)
			tree.deleteCase1(node)
		}
		tree.replaceNode(node, child)
		if node.Parent == nil && child != nil {
			child.color = blackOrderTree
		}
	}
	if node == tree.Max {
		if node.Parent != nil {
			tree.Max, _ = tree.getMaxFromNode(node.Parent)
		} else {
			tree.Max, _ = tree.getMaxFromNode(tree.Root)
		}
	}
	if node == tree.Min {
		if node.Parent != nil {
			tree.Min, _ = tree.getMinFromNode(node.Parent)
		} else {
			tree.Min, _ = tree.getMinFromNode(tree.Root)
		}
	}

	node.Release()
	tree.size--
}

// Empty returns true if tree does not contain any nodes
func (tree *orderTree) Empty() bool {
	return tree.size == 0
}

// Size returns number of nodes in the tree.
func (tree *orderTree) Size() int {
	return tree.size
}

// Keys returns all keys in-order
func (tree *orderTree) Keys() []uint64 {
	keys := make([]uint64, tree.size)
	it := tree.Iterator()
	for i := 0; it.Next(); i++ {
		keys[i] = it.Key()
	}
	return keys
}

// Values returns all values in-order based on the key.
func (tree *orderTree) Values() []*Order {
	values := make([]*Order, tree.size)
	it := tree.Iterator()
	for i := 0; it.Next(); i++ {
		values[i] = it.Value()
	}
	return values
}

// Left returns the left-most (min) node or nil if tree is empty.
func (tree *orderTree) Left() *nodeOrderTree {
	var parent *nodeOrderTree
	current := tree.Root
	for current != nil {
		parent = current
		current = current.Left
	}
	return parent
}

// Right returns the right-most (max) node or nil if tree is empty.
func (tree *orderTree) Right() *nodeOrderTree {
	var parent *nodeOrderTree
	current := tree.Root
	for current != nil {
		parent = current
		current = current.Right
	}
	return parent
}

// Floor Finds floor node of the input key, return the floor node or nil if no floor is found.
// Second return parameter is true if floor was found, otherwise false.
//
// Floor node is defined as the largest node that is smaller than or equal to the given node.
// A floor node may not be found, either because the tree is empty, or because
// all nodes in the tree are larger than the given node.
//
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) Floor(key uint64) (floor *nodeOrderTree, found bool) {
	found = false
	node := tree.Root
	for node != nil {
		compare := tree.Comparator(key, node.Key)
		switch {
		case compare == 0:
			return node, true
		case compare < 0:
			node = node.Left
		case compare > 0:
			floor, found = node, true
			node = node.Right
		}
	}
	if found {
		return floor, true
	}
	return nil, false
}

// Ceiling finds ceiling node of the input key, return the ceiling node or nil if no ceiling is found.
// Second return parameter is true if ceiling was found, otherwise false.
//
// Ceiling node is defined as the smallest node that is larger than or equal to the given node.
// A ceiling node may not be found, either because the tree is empty, or because
// all nodes in the tree are smaller than the given node.
//
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) Ceiling(key uint64) (ceiling *nodeOrderTree, found bool) {
	found = false
	node := tree.Root
	for node != nil {
		compare := tree.Comparator(key, node.Key)
		switch {
		case compare == 0:
			return node, true
		case compare < 0:
			ceiling, found = node, true
			node = node.Left
		case compare > 0:
			node = node.Right
		}
	}
	if found {
		return ceiling, true
	}
	return nil, false
}

// GreatestLessThan finds largest node that is smaller than the given node.
// A node may not be found, either because the tree is empty, or because
// all nodes in the tree are larger than or equal to the given node.
//
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) LargestLessThan(key uint64) (floor *nodeOrderTree, found bool) {
	found = false
	node := tree.Root
	for node != nil {
		if tree.Comparator(key, node.Key) > 0 {
			floor, found = node, true
			node = node.Right
		} else {
			node = node.Left
		}
	}
	if found {
		return floor, true
	}
	return nil, false
}

// Ceiling finds the smallest node that is larger than to the given node.
// A node may not be found, either because the tree is empty, or because
// all nodes in the tree are smaller than the given node.
//
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (tree *orderTree) SmallestGreaterThan(key uint64) (ceiling *nodeOrderTree, found bool) {
	found = false
	node := tree.Root
	for node != nil {
		if tree.Comparator(key, node.Key) < 0 {
			ceiling, found = node, true
			node = node.Left
		} else {
			node = node.Right
		}
	}

	if found {
		return ceiling, true
	}
	return nil, false
}

// GetMin gets the min value and flag if found
func (tree *orderTree) GetMin() (node *nodeOrderTree, found bool) {
	return tree.Min, tree.Min != nil
}

// GetMax gets the max value and flag if found
func (tree *orderTree) GetMax() (node *nodeOrderTree, found bool) {
	return tree.Max, tree.Max != nil
}

func (tree *orderTree) getMinFromNode(node *nodeOrderTree) (foundNode *nodeOrderTree, found bool) {
	if node == nil {
		return nil, false

	}
	if node.Left == nil {
		return node, true

	}
	return tree.getMinFromNode(node.Left)

}

func (tree *orderTree) getMaxFromNode(node *nodeOrderTree) (foundNode *nodeOrderTree, found bool) {
	if node == nil {
		return nil, false

	}
	if node.Right == nil {
		return node, true

	}
	return tree.getMaxFromNode(node.Right)

}

// Clear removes all nodes from the tree.
func (tree *orderTree) Clear() {
	tree.Root = nil
	tree.size = 0
	tree.Max = nil
	tree.Min = nil
}

// String returns a string representation of container
func (tree *orderTree) String() string {
	str := "RedBlackTree\n"
	if !tree.Empty() {
		outputOrderTree(tree.Root, "", true, &str)
	}
	return str
}

func (node *nodeOrderTree) String() string {
	return fmt.Sprintf("%v", node.Key)
}

func outputOrderTree(node *nodeOrderTree, prefix string, isTail bool, str *string) {
	if node.Right != nil {
		newPrefix := prefix
		if isTail {
			newPrefix += "│   "
		} else {
			newPrefix += "    "
		}
		outputOrderTree(node.Right, newPrefix, false, str)
	}
	*str += prefix
	if isTail {
		*str += "└── "
	} else {
		*str += "┌── "
	}
	*str += node.String() + "\n"
	if node.Left != nil {
		newPrefix := prefix
		if isTail {
			newPrefix += "    "
		} else {
			newPrefix += "│   "
		}
		outputOrderTree(node.Left, newPrefix, true, str)
	}
}

func (tree *orderTree) lookup(key uint64) *nodeOrderTree {
	node := tree.Root
	for node != nil {
		compare := tree.Comparator(key, node.Key)
		switch {
		case compare == 0:
			return node
		case compare < 0:
			node = node.Left
		case compare > 0:
			node = node.Right
		}
	}
	return nil
}

func (node *nodeOrderTree) grandparent() *nodeOrderTree {
	if node != nil && node.Parent != nil {
		return node.Parent.Parent
	}
	return nil
}

func (node *nodeOrderTree) uncle() *nodeOrderTree {
	if node == nil || node.Parent == nil || node.Parent.Parent == nil {
		return nil
	}
	return node.Parent.sibling()
}

func (node *nodeOrderTree) sibling() *nodeOrderTree {
	if node == nil || node.Parent == nil {
		return nil
	}
	if node == node.Parent.Left {
		return node.Parent.Right
	}
	return node.Parent.Left
}

func (tree *orderTree) rotateLeft(node *nodeOrderTree) {
	right := node.Right
	tree.replaceNode(node, right)
	node.Right = right.Left
	if right.Left != nil {
		right.Left.Parent = node
	}
	right.Left = node
	node.Parent = right
}

func (tree *orderTree) rotateRight(node *nodeOrderTree) {
	left := node.Left
	tree.replaceNode(node, left)
	node.Left = left.Right
	if left.Right != nil {
		left.Right.Parent = node
	}
	left.Right = node
	node.Parent = left
}

func (tree *orderTree) replaceNode(old *nodeOrderTree, new *nodeOrderTree) {
	if old.Parent == nil {
		tree.Root = new
	} else {
		if old == old.Parent.Left {
			old.Parent.Left = new
		} else {
			old.Parent.Right = new
		}
	}
	if new != nil {
		new.Parent = old.Parent
	}
}

func (tree *orderTree) insertCase1(node *nodeOrderTree) {
	if node.Parent == nil {
		node.color = blackOrderTree
	} else {
		tree.insertCase2(node)
	}
}

func (tree *orderTree) insertCase2(node *nodeOrderTree) {
	if nodeColorOrderTree(node.Parent) == blackOrderTree {
		return
	}
	tree.insertCase3(node)
}

func (tree *orderTree) insertCase3(node *nodeOrderTree) {
	uncle := node.uncle()
	if nodeColorOrderTree(uncle) == redOrderTree {
		node.Parent.color = blackOrderTree
		uncle.color = blackOrderTree
		node.grandparent().color = redOrderTree
		tree.insertCase1(node.grandparent())
	} else {
		tree.insertCase4(node)
	}
}

func (tree *orderTree) insertCase4(node *nodeOrderTree) {
	grandparent := node.grandparent()
	if node == node.Parent.Right && node.Parent == grandparent.Left {
		tree.rotateLeft(node.Parent)
		node = node.Left
	} else if node == node.Parent.Left && node.Parent == grandparent.Right {
		tree.rotateRight(node.Parent)
		node = node.Right
	}
	tree.insertCase5(node)
}

func (tree *orderTree) insertCase5(node *nodeOrderTree) {
	node.Parent.color = blackOrderTree
	grandparent := node.grandparent()
	grandparent.color = redOrderTree
	if node == node.Parent.Left && node.Parent == grandparent.Left {
		tree.rotateRight(grandparent)
	} else if node == node.Parent.Right && node.Parent == grandparent.Right {
		tree.rotateLeft(grandparent)
	}
}

func (node *nodeOrderTree) maximumNode() *nodeOrderTree {
	if node == nil {
		return nil
	}
	for node.Right != nil {
		node = node.Right
	}
	return node
}

func (tree *orderTree) deleteCase1(node *nodeOrderTree) {
	if node.Parent == nil {
		return
	}
	tree.deleteCase2(node)
}

func (tree *orderTree) deleteCase2(node *nodeOrderTree) {
	sibling := node.sibling()
	if nodeColorOrderTree(sibling) == redOrderTree {
		node.Parent.color = redOrderTree
		sibling.color = blackOrderTree
		if node == node.Parent.Left {
			tree.rotateLeft(node.Parent)
		} else {
			tree.rotateRight(node.Parent)
		}
	}
	tree.deleteCase3(node)
}

func (tree *orderTree) deleteCase3(node *nodeOrderTree) {
	sibling := node.sibling()
	if nodeColorOrderTree(node.Parent) == blackOrderTree &&
		nodeColorOrderTree(sibling) == blackOrderTree &&
		nodeColorOrderTree(sibling.Left) == blackOrderTree &&
		nodeColorOrderTree(sibling.Right) == blackOrderTree {
		sibling.color = redOrderTree
		tree.deleteCase1(node.Parent)
	} else {
		tree.deleteCase4(node)
	}
}

func (tree *orderTree) deleteCase4(node *nodeOrderTree) {
	sibling := node.sibling()
	if nodeColorOrderTree(node.Parent) == redOrderTree &&
		nodeColorOrderTree(sibling) == blackOrderTree &&
		nodeColorOrderTree(sibling.Left) == blackOrderTree &&
		nodeColorOrderTree(sibling.Right) == blackOrderTree {
		sibling.color = redOrderTree
		node.Parent.color = blackOrderTree
	} else {
		tree.deleteCase5(node)
	}
}

func (tree *orderTree) deleteCase5(node *nodeOrderTree) {
	sibling := node.sibling()
	if node == node.Parent.Left &&
		nodeColorOrderTree(sibling) == blackOrderTree &&
		nodeColorOrderTree(sibling.Left) == redOrderTree &&
		nodeColorOrderTree(sibling.Right) == blackOrderTree {
		sibling.color = redOrderTree
		sibling.Left.color = blackOrderTree
		tree.rotateRight(sibling)
	} else if node == node.Parent.Right &&
		nodeColorOrderTree(sibling) == blackOrderTree &&
		nodeColorOrderTree(sibling.Right) == redOrderTree &&
		nodeColorOrderTree(sibling.Left) == blackOrderTree {
		sibling.color = redOrderTree
		sibling.Right.color = blackOrderTree
		tree.rotateLeft(sibling)
	}
	tree.deleteCase6(node)
}

func (tree *orderTree) deleteCase6(node *nodeOrderTree) {
	sibling := node.sibling()
	sibling.color = nodeColorOrderTree(node.Parent)
	node.Parent.color = blackOrderTree
	if node == node.Parent.Left && nodeColorOrderTree(sibling.Right) == redOrderTree {
		sibling.Right.color = blackOrderTree
		tree.rotateLeft(node.Parent)
	} else if nodeColorOrderTree(sibling.Left) == redOrderTree {
		sibling.Left.color = blackOrderTree
		tree.rotateRight(node.Parent)
	}
}

func nodeColorOrderTree(node *nodeOrderTree) colorOrderTree {
	if node == nil {
		return blackOrderTree
	}
	return node.color
}

// Iterator holding the iterator's state
type iteratorOrderTree struct {
	tree     *orderTree
	node     *nodeOrderTree
	position positionOrderTree
}

type positionOrderTree byte

const (
	beginOrderTree, betweenOrderTree, endOrderTree positionOrderTree = 0, 1, 2
)

// Iterator returns a stateful iterator whose elements are key/value pairs.
func (tree *orderTree) Iterator() iteratorOrderTree {
	return iteratorOrderTree{tree: tree, node: nil, position: beginOrderTree}
}

// IteratorAt returns a stateful iterator whose elements are key/value pairs that is initialised at a particular node.
func (tree *orderTree) IteratorAt(node *nodeOrderTree) iteratorOrderTree {
	return iteratorOrderTree{tree: tree, node: node, position: betweenOrderTree}
}

// Next moves the iterator to the next element and returns true if there was a next element in the container.
// If Next() returns true, then next element's key and value can be retrieved by Key() and Value().
// If Next() was called for the first time, then it will point the iterator to the first element if it exists.
// Modifies the state of the iterator.
func (iterator *iteratorOrderTree) Next() bool {
	if iterator.position == endOrderTree {
		goto end
	}
	if iterator.position == beginOrderTree {
		left := iterator.tree.Left()
		if left == nil {
			goto end
		}
		iterator.node = left
		goto between
	}
	if iterator.node.Right != nil {
		iterator.node = iterator.node.Right
		for iterator.node.Left != nil {
			iterator.node = iterator.node.Left
		}
		goto between
	}
	if iterator.node.Parent != nil {
		node := iterator.node
		for iterator.node.Parent != nil {
			iterator.node = iterator.node.Parent
			if iterator.tree.Comparator(node.Key, iterator.node.Key) <= 0 {
				goto between
			}
		}
	}

end:
	iterator.node = nil
	iterator.position = endOrderTree
	return false

between:
	iterator.position = betweenOrderTree
	return true
}

// Prev moves the iterator to the previous element and returns true if there was a previous element in the container.
// If Prev() returns true, then previous element's key and value can be retrieved by Key() and Value().
// Modifies the state of the iterator.
func (iterator *iteratorOrderTree) Prev() bool {
	if iterator.position == beginOrderTree {
		goto begin
	}
	if iterator.position == endOrderTree {
		right := iterator.tree.Right()
		if right == nil {
			goto begin
		}
		iterator.node = right
		goto between
	}
	if iterator.node.Left != nil {
		iterator.node = iterator.node.Left
		for iterator.node.Right != nil {
			iterator.node = iterator.node.Right
		}
		goto between
	}
	if iterator.node.Parent != nil {
		node := iterator.node
		for iterator.node.Parent != nil {
			iterator.node = iterator.node.Parent
			if iterator.tree.Comparator(node.Key, iterator.node.Key) >= 0 {
				goto between
			}
		}
	}

begin:
	iterator.node = nil
	iterator.position = beginOrderTree
	return false

between:
	iterator.position = betweenOrderTree
	return true
}

// Value returns the current element's value.
// Does not modify the state of the iterator.
func (iterator *iteratorOrderTree) Value() *Order {
	return iterator.node.Value
}

// Key returns the current element's key.
// Does not modify the state of the iterator.
func (iterator *iteratorOrderTree) Key() uint64 {
	return iterator.node.Key
}

// Begin resets the iterator to its initial state (one-before-first)
// Call Next() to fetch the first element if any.
func (iterator *iteratorOrderTree) Begin() {
	iterator.node = nil
	iterator.position = beginOrderTree
}

// End moves the iterator past the last element (one-past-the-end).
// Call Prev() to fetch the last element if any.
func (iterator *iteratorOrderTree) End() {
	iterator.node = nil
	iterator.position = endOrderTree
}

// First moves the iterator to the first element and returns true if there was a first element in the container.
// If First() returns true, then first element's key and value can be retrieved by Key() and Value().
// Modifies the state of the iterator
func (iterator *iteratorOrderTree) First() bool {
	iterator.Begin()
	return iterator.Next()
}

// Last moves the iterator to the last element and returns true if there was a last element in the container.
// If Last() returns true, then last element's key and value can be retrieved by Key() and Value().
// Modifies the state of the iterator.
func (iterator *iteratorOrderTree) Last() bool {
	iterator.End()
	return iterator.Prev()
}