RBTree

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.

struct RBTree (

alias less = "a < b"

bool allowDuplicates = true

ALLOC = ThreadMem

bool NOGC_ = false

) if (

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

) {

this(this);

import std.range : Take;;

import std.typetuple : allSatisfy;;

import std.traits;;

alias _less = binaryFun!less;

alias Elem = T;

void _defaultInitialize();

bool empty [@property getter];

size_t length [@property getter];

RBRange!(Elem, ALLOC, NOGC_) opSlice();

Elem front();

Elem back();

bool opBinaryRight(Elem e);

void clear();

size_t insert(Stuff stuff);

Elem removeAny();

void removeFront();

void removeBack();

size_t remove(U elems);

size_t remove(U[] elems);

size_t remove(Stuff stuff);

bool opEquals(RBTree rhs);

auto upperBoundRange(Elem e);

auto lowerBoundRange(Elem e);

auto getValuesAt(Elem e);

}

Constructors

this this(size_t elems): Undocumented in source.
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.

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): Undocumented in source.

Members

Aliases

Elem alias Elem = T: Element type for the tree
_less alias _less = binaryFun!less: Undocumented in source.

Functions

_defaultInitialize void _defaultInitialize(): Undocumented in source. Be warned that the author may not have intended to support it.
back Elem back(): The last element in the container
clear void clear(): Removes all elements from the container.
front Elem front(): The front element in the container
getValuesAt auto getValuesAt(Elem e): Get a range from the container with all elements that are == e according to the less comparator
insert size_t insert(Stuff stuff): Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.
insert size_t insert(Stuff stuff): Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.
lowerBoundRange auto lowerBoundRange(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(RBTree rhs): Compares two trees for equality.
opSlice RBRange!(Elem, ALLOC, NOGC_) opSlice(): Fetch a range that spans all the elements in the container.
remove size_t remove(U elems)
size_t remove(U[] elems)
size_t remove(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.
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.
upperBoundRange auto upperBoundRange(Elem e): Get a range from the container with all elements that are > e according to the less comparator

Properties

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.