std.container.rbtree

This module implements a red-black tree container.

This module is a submodule of std.container.

Source: std/container/rbtree.d

Copyright

License

Distributed under the Boost Software License, Version 1.0.

(See accompanying file LICENSE_1_0.txt or copy at boost.org/LICENSE_1_0.txt).

Authors

Steven Schveighoffer, Andrei Alexandrescu

struct RBNode RBRange

class RedBlackTree

fn redBlackTree

Types 3

structRBNode(V)

Fields

private Node _left

private Node _right

private Node _parent

V valueThe value held by this node

Color colorThe color of the node.

Methods

inout(RBNode) * left() @property inout return scopeGet the left child

inout(RBNode) * right() @property inout return scopeGet the right child

inout(RBNode) * parent() @property inout return scopeGet the parent

Node left(return scope Node newNode) @property @trustedSet the left child. Also updates the new child's parent node. This does not update the previous child.

Node right(return scope Node newNode) @property @trustedSet the right child. Also updates the new child's parent node. This does not update the previous child.

Node rotateR()Rotate right. This performs the following operations: - The left child becomes the parent of this node. - This node becomes the new parent's right child. - The old right child of the new parent be...

Node rotateL()Rotate left. This performs the following operations: - The right child becomes the parent of this node. - This node becomes the new parent's left child. - The old left child of the new parent beco...

bool isLeftNode() @property constReturns true if this node is a left child.

void setColor(Node end)Set the color of the node after it is inserted. This performs an update to the whole tree, possibly rotating nodes to keep the Red-Black properties correct. This is an O(lg(n)) operation, where n...

Node remove(Node end) returnRemove this node from the tree. The 'end' node is used as the marker which is root's parent. Note that this cannot be null!

inout(RBNode) * leftmost() @property inout returnReturn the leftmost descendant of this node.

inout(RBNode) * rightmost() @property inout returnReturn the rightmost descendant of this node

inout(RBNode) * next() @property inout returnReturns the next valued node in the tree.

inout(RBNode) * prev() @property inout returnReturns the previous valued node in the tree.

Node dup(scope Node delegate(V v) alloc)

Node dup()

Constructors

this(Node left, Node right, Node parent, V value)

Nested Templates

ColorEnumeration determining what color the node is. Null nodes are assumed to be black.

private structRBRange(N)

Fields

private Node _begin

private Node _end

Methods

bool empty() @property constReturns `true` if the range is empty

Elem front() ref @propertyReturns the first element in the range

Elem back() ref @propertyReturns the last element in the range

void popFront()pop the front element from the range

void popBack()pop the back element from the range

RBRange save() @propertyTrivial save implementation, needed for `isForwardRange`.

Constructors

this(Node b, Node e)

classRedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if (is(typeof((ref const T a) => binaryFun!less(a, a))))

Implementation of a red-black tree container.

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

To use a different comparison than "a < b", pass a different operator string that can be used by 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.

Care should also be taken to not modify elements in the tree (e.g. via front / back, which return by ref) in a way which would affect the order defined by the less predicate.

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.

Fields

private Node _end

private Node _begin

private size_t _length

Methods

private void _setup()

private Node allocate()

private Node allocate(Elem v)

private inout(RBNode) * _find(Elem e) inout

private bool _add(return scope Elem n)

bool empty() @property constCheck if any elements exist in the container. Returns `false` if at least one element exists.

size_t length() @property constReturns the number of elements in the container.

RedBlackTree dup() @propertyDuplicate this container. The resulting container contains a shallow copy of the elements.

Range opSlice()Fetch a range that spans all the elements in the container.

ConstRange opSlice() constDitto

ImmutableRange opSlice() immutableDitto

inout(Elem) front() ref inoutThe front element in the container

inout(Elem) back() ref inoutThe last element in the container

bool opBinaryRight(string op)(Elem e) if (op == "in") const`in` operator. Check to see if the given element exists in the container.

bool opEquals(Object rhs)Compares two trees for equality.

size_t toHash() nothrow @safeGenerates 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.

void clear()Removes all elements from the container.

size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff, Elem))Insert a single element in the container. Note that this does not invalidate any ranges currently iterating the container.

size_t stableInsert(Stuff)(scope  Stuff stuff) if (isInputRange!Stuff &&
         isImplicitlyConvertible!(ElementType!Stuff,  Elem))

Insert a range of elements in the container. Note that this does not invalidate any ranges currently iterating the container.

Elem removeAny()Remove an element from the container and return its value.

void removeFront()Remove the front element from the container.

void removeBack()Remove the back element from the container.

Range remove(Range r)Removes the given range from the container.

Range remove(Take!Range r)Removes the given `Take!Range` from the container

size_t removeKey(U...)(U elems) if (allSatisfy!(isImplicitlyConvertibleToElem, U))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` ...

size_t removeKey(U)(scope U[] elems) if (isImplicitlyConvertible!(U, Elem))Ditto

size_t removeKey(Stuff)(Stuff stuff) if (isInputRange!Stuff &&
         isImplicitlyConvertible!(ElementType!Stuff,  Elem)  &&
        !isDynamicArray!Stuff)

Ditto

private inout(RBNode) * _firstGreater(Elem e) inout

private inout(RBNode) * _firstGreaterEqual(Elem e) inout

Range upperBound(Elem e)Get a range from the container with all elements that are > e according to the less comparator

ConstRange upperBound(Elem e) constDitto

ImmutableRange upperBound(Elem e) immutableDitto

Range lowerBound(Elem e)Get a range from the container with all elements that are < e according to the less comparator

ConstRange lowerBound(Elem e) constDitto

ImmutableRange lowerBound(Elem e) immutableDitto

auto equalRange(this This)(Elem e)Get a range from the container with all elements that are == e according to the less comparator

auto trisect(this This)(Elem e)Returns a static array of 3 ranges `r` such that `r[0]` is the same as the result of `lowerBound(value)`, `r[1]` is the same as the result of equalRange(value), and `r[2]` is the same as the result...

Constructors

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

this(Stuff stuff)Constructor. Pass in a range of elements to initialize the tree with.

this()

this(Node end, size_t length)

Nested Templates

isImplicitlyConvertibleToElem(U)

Functions 8

fnauto redBlackTree(E)(E[] elems...)Convenience function for creating a `RedBlackTree!E` from a list of values.

fnauto redBlackTree(bool allowDuplicates, E)(E[] elems...)Ditto

fnauto redBlackTree(alias less, E)(E[] elems...) if (is(typeof(binaryFun!less(E.init, E.init))))Ditto

auto redBlackTree(alias  less,  bool  allowDuplicates,  E)(E[]  elems...) if (is(typeof(binaryFun!less(E.init,  E.init))))

Ditto

fnauto redBlackTree(Stuff)(Stuff range) if (isInputRange!Stuff && !isArray!(Stuff))Ditto

fnauto redBlackTree(bool allowDuplicates, Stuff)(Stuff range) if (isInputRange!Stuff && !isArray!(Stuff))Ditto

auto redBlackTree(alias  less,  Stuff)(Stuff range) if (  is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
     &&  isInputRange!Stuff && !isArray!(Stuff))

Ditto

auto redBlackTree(alias  less,  bool  allowDuplicates,  Stuff)(Stuff range) if (  is(typeof(binaryFun!less((ElementType!Stuff).init, (ElementType!Stuff).init)))
     &&  isInputRange!Stuff && !isArray!(Stuff))

Ditto