Skip to content

API Reference

Summary

RedBlackDbTree is a utility module allowing sorting of objects based on their natural order or a given comparator.

RedBlackDbTree has a special function called RedBlackDbTree.new() which is used to instantiate a new RedBlackDbTree Instance. This function can take a comparator as a parameter to compare and sort objects by.

Methods

Add(object: any): nil

  Adds the given object to the tree, if it isn't already in the tree.

AddAll(...): nil

  Adds the given objects to the tree using Add.

Remove(object: any): nil

  Removes the given object from the tree, if it is present in the tree.

RemoveAll(...): nil

  Removes the given objects to the tree using Remove.

ContainsObject(object): nil

  Returns true if the tree contains the given object, false otherwise.

UpdateObject(object, dict{[property] = update}): nil

  Applies the updates given in the dictionary to the object.

Clear(): nil

  Removes all objects from the tree, making it empty.

IsEmpty(): nil

  Returns true if the tree is empty, false otherwise.

Height(): number

  Returns the height of the tree. A one-node tree has height 0.

__len(): number

  Returns the number of non-nil nodes in the tree accesed by the # size operator.

Min(): object

  Returns smallest object in the tree

Max(): object

  Returns largest object in the tree

RemoveMin(): nil

  Removes the smallest object from the tree.

RemoveMax(): nil

  Removes the largest object from the tree.

PreOrderArray(): {object}

  Returns a new array of the tree's objects in pre-order format.

InOrderArray(): {object}

  Returns a new array of the tree's objects in the in-order format.

PostOrderArray(): {object}

  Returns a new array of the tree's objects in post-order format.

PreOrderPrint(): nil

  Prints the tree's objects in pre-order format.

InOrderPrint(): nil

  Prints the tree's objects in the in-order format.

PostOrderPrint(): nil

  Prints the tree's objects in post-order format.

Constructors

RedBlackDbTree.new

RedBlackDbTree.new() -> RedBlackDBTree
Creates a new, empty RedBlackDbTree using the natural ordering of its objects.

Caution

The only objects who may be sorted by the default comparator are Strings, numbers or Metatables with comparison methods.

RedBlackDbTree.new(comparator: (object1, object2) -> number) -> RedBlackDbTree
Creates a new, empty RedBlackDbTree, ordered according to the given comparator.

The comparator should take two arguments representing the objects passed into it. The main 3 cases are listed below:

  • If object1 is "smaller" than object2, a negative number should be returned

  • If object1 is "greater" than object2, a positive number should be returned

  • If the two objects are considered equal, 0 should be returned

Methods

Info

self is an active RedBlackDbTree Instance.

Add

self:Add(object: any)
Adds object to the tree, given it is not in the array already.

Caution

If object is mutable, it must be updated using UpdateObject.

Alternatively, the object can be removed, updated then added back in.

AddAll

self:AddAll(...)
Adds all the given objects in the tuple ...

If one object is given, it is assumed to be a table in which all values will be added.

Remove

self:Remove(object: any)
Removes object from the tree.

RemoveAll

self:RemoveAll(...)
Removes all the given objects in the tuple ...

If one object is given, it is assumed to be a table in which all values will be removed.

ContainsObject

self:ContainsObject(object) -> boolean
Returns true if the tree contains object, false otherwise.

UpdateObject

self:UpdateObject(object, dict: {[property] = update})

  • Removes the object from the tree

  • Applies the update to the property of the object for all properties in dict

  • Adds the updated object back into the tree at its correct location

Caution

Only mutable objects may be updated this way. An error will be thrown otherwise.

Clear

self:Clear()
Remove all objects from the tree, making it empty.

IsEmpty

self:IsEmpty() -> boolean
Returns true if the tree is empty, false otherwise.

Height

self:Height()
Returns the height of the tree. A one-node tree has height 0.

__len

#self -> number
Returns the number of non-nil nodes in the tree. self should be a RedBlackDbTree instance.

Min

self:Min() -> object
Returns the smallest object in the tree.

Caution

An error will be produced if there are no objects in the tree.

Max

self:Max() -> object
Returns the largest object in the tree.

Caution

An error will be produced if there are no objects in the tree.

RemoveMin

self:RemoveMin()
Removes the smallest object from the tree.

Caution

An error will be produced if there are no objects in the tree.

RemoveMax

self:RemoveMax()
Removes the largest object from the tree

Caution

An error will be produced if there are no objects in the tree.

PreOrderArray

self:PreOrderArray() -> {object}
Returns a new array of the tree's objects in pre-order format.

InOrderArray

self:InOrderArray() -> {object}
Returns a new array of the tree's objects in the in-order format.

PostOrderArray

self:PostOrderArray() -> {object}
Returns a new array of the tree's objects in post-order format.

PreOrderPrint

self:PreOrderPrint()
Prints the tree's objects in pre-order format.

InOrderPrint

self:InOrderPrint()
Prints the tree's objects in the in-order format.

PostOrderPrint

self:PostOrderPrint()
Prints the tree's objects in post-order format.