RBTree implementation for the GC.

Code Map

//! RBTree implementation for the GC.
module vrt.gc.rbtree;


enum Black;
enum Red;

alias Colour = bool;

//! Embeddable Node for the RBTree.
struct Node
{
public:
	children: Link[2];


public:
	fn left() Link* { }
	fn left(l: Link) { }
	fn right(l: Link) { }
	fn right() Link* { }
	fn visit(func: scope (RBTree.VisitDg)) { }
}

//! Wrapping a pointer and red black bit, link from one Node to another.
struct Link
{
public:
	fn getAs(c: Colour) Link { }
	fn getAsBlack() Link { }
	fn getAsRed() Link { }
	fn node() Node* { }
	fn colour() Colour { }
	fn isRed() bool { }
	fn isBlack() bool { }
	fn isLeaf() bool { }
	fn left() Link* { }
	fn right() Link* { }
	fn left(l: Link) { }
	fn right(l: Link) { }
	fn getChild(cmp: bool) Link* { }
	fn rotate(cmp: bool) Link { }


public:
	static fn build(n: Node*, c: Colour) Link { }
}

struct Path
{
public:
	fn colour() Colour { }
	fn isRed() bool { }
	fn isBlack() bool { }
	fn cmp() bool { }
	fn node() Node* { }
	fn link() Link { }
	fn getWithLink(l: Link) Path { }
	fn getWithCmp(c: bool) Path { }
	fn getChild(c: bool) Link* { }


public:
	static fn build(l: Link, c: bool) Path { }
}

//! The tree's root object. This doesn't allocate any nodes, that is
//! handled by the client code. Test and compare delegates are user
//! defined.
struct RBTree
{
public:
	alias TestDg = scope (i32 delegate(Node*));
	alias CompDg = scope (i32 delegate(Node*, Node*));
	alias VisitDg = scope (void delegate(Node*));
	alias FindDg = scope (bool delegate(Node*));


public:
	root: Node*;


public:
	fn get(test: scope (TestDg)) Node* { }
	fn find(test: scope (FindDg)) Node* { }
	fn find(n: Node*, test: scope (FindDg)) Node* { }
	fn visit(func: scope (VisitDg)) { }
	fn insert(n: Node*, compare: scope (CompDg)) { }
	fn remove(n: Node*, compare: scope (CompDg)) { }
	fn extractAny(compare: scope (CompDg)) Node* { }
	fn extract(n: Node*, compare: scope (CompDg)) Node* { }
}