RedBlackTree

Implementation of a red-black tree container.

All inserts, removes, searches, and any function in general has complexity of O(lg(n)).

To use a different comparison than "a < b", pass a different operator string that can be used by std.functional.binaryFun, or pass in a function, delegate, functor, or any type where less(a, b) results in a bool value.

Note that less should produce a strict ordering. That is, for two unequal elements a and b, less(a, b) == !less(b, a). less(a, a) should always equal false.

If allowDuplicates is set to true, then inserting the same element more than once continues to add more elements. If it is false, duplicate elements are ignored on insertion. If duplicates are allowed, then new elements are inserted after all existing duplicate elements.

final

class RedBlackTree (

alias less = "a < b"

bool allowDuplicates = false

) if (

is(typeof(binaryFun!less(T.init, T.init)))

) {

template Take(R) via import std.range : Take;;

enum bool isInputRange(R, E); via import std.range.primitives : isInputRange, walkLength;;

auto walkLength(Range range, size_t upTo) via import std.range.primitives : isInputRange, walkLength;;

template isIntegral(T) via import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible;;

template isDynamicArray(T) via import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible;;

enum bool isImplicitlyConvertible(From, To); via import std.traits : isIntegral, isDynamicArray, isImplicitlyConvertible;;

version(StdUnittest)

static if(!(is(typeof(less) == string)))

enum doUnittest;

alias Elem = T;

alias Range = RBRange!(RBNode*);

bool empty [@property getter];

size_t length [@property getter];

RedBlackTree dup [@property getter];

Range opSlice();

ConstRange opSlice();

ImmutableRange opSlice();

inout(Elem) front();

inout(Elem) back();

bool opBinaryRight(Elem e);

bool opEquals(Object rhs);

size_t toHash();

void clear();

size_t stableInsert(Stuff stuff);

alias insert = stableInsert;

Elem removeAny();

void removeFront();

void removeBack();

Range remove(Range r);

Range remove(Take!Range r);

size_t removeKey(U elems);

size_t removeKey(U[] elems);

size_t removeKey(Stuff stuff);

Range upperBound(Elem e);

ConstRange upperBound(Elem e);

ImmutableRange upperBound(Elem e);

Range lowerBound(Elem e);

ConstRange lowerBound(Elem e);

ImmutableRange lowerBound(Elem e);

auto equalRange(Elem e);

static if(is(typeof( ())))

void toString(void delegate(const(char)[]) sink, FormatSpec!char fmt);

this(Elem[] elems);

this(Stuff stuff);

this();

}

Constructors

this this(Elem[] elems): Constructor. Pass in an array of elements, or individual elements to initialize the tree with.
this this(Stuff stuff): Constructor. Pass in a range of elements to initialize the tree with.
this this()

Members

Aliases

Elem alias Elem = T: Element type for the tree
Range alias Range = RBRange!(RBNode*): The range types for RedBlackTree
insert alias insert = stableInsert: Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.

Functions

back inout(Elem) back(): The last element in the container
clear void clear(): Removes all elements from the container.
equalRange auto equalRange(Elem e): Get a range from the container with all elements that are == e according to the less comparator
front inout(Elem) front(): The front element in the container
lowerBound Range lowerBound(Elem e)
ConstRange lowerBound(Elem e)
ImmutableRange lowerBound(Elem e): Get a range from the container with all elements that are < e according to the less comparator
opBinaryRight bool opBinaryRight(Elem e): in operator. Check to see if the given element exists in the container.
opEquals bool opEquals(Object rhs): Compares two trees for equality.
opSlice Range opSlice()
ConstRange opSlice()
ImmutableRange opSlice(): Fetch a range that spans all the elements in the container.
remove Range remove(Range r): Removes the given range from the container.
remove Range remove(Take!Range r): Removes the given Take!Range from the container
removeAny Elem removeAny(): Remove an element from the container and return its value.
removeBack void removeBack(): Remove the back element from the container.
removeFront void removeFront(): Remove the front element from the container.
removeKey size_t removeKey(U elems)
size_t removeKey(U[] elems)
size_t removeKey(Stuff stuff): Removes elements from the container that are equal to the given values according to the less comparator. One element is removed for each value given which is in the container. If allowDuplicates is true, duplicates are removed only if duplicate values are given.
stableInsert size_t stableInsert(Stuff stuff): Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.
stableInsert size_t stableInsert(Stuff stuff): Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.
toHash size_t toHash(): Generates a hash for the tree. Note that with a custom comparison function it may not hold that if two rbtrees are equal, the hashes of the trees will be equal.
toString void toString(void delegate(const(char)[]) sink, FormatSpec!char fmt): Formats the RedBlackTree into a sink function. For more info see std.format.formatValue. Note that this only is available when the element type can be formatted. Otherwise, the default toString from Object is used.
upperBound Range upperBound(Elem e)
ConstRange upperBound(Elem e)
ImmutableRange upperBound(Elem e): Get a range from the container with all elements that are > e according to the less comparator

Properties

dup RedBlackTree dup [@property getter]: Duplicate this container. The resulting container contains a shallow copy of the elements.
empty bool empty [@property getter]: Check if any elements exist in the container. Returns false if at least one element exists.
length size_t length [@property getter]: Returns the number of elements in the container.