containers.ttree

T-Tree.

Authors

Brian Schott

  • Declaration

    struct TTree(T, Allocator = Mallocator, bool allowDuplicates = false, alias less = "a < b", bool supportGC = shouldAddGCRange!T, size_t cacheLineSize = 64);

    Implements a binary search tree with multiple items per tree node.

    Discussion

    T-tree Nodes are (by default) sized to fit within a 64-byte cache line. The number of items stored per node can be read from the nodeCapacity field. Each node has 0, 1, or 2 children. Each node has between 1 and nodeCapacity items, or it has nodeCapacity items and 0 or more children.

    Parameters

    T

    the element type

    Allocator

    the allocator to use. Defaults to Mallocator.

    allowDuplicates

    if true, duplicate values will be allowed in the tree

    less

    the comparitor function to use

    supportGC

    true if the container should support holding references to GC-allocated memory.

    cacheLineSize

    Nodes will be sized to fit within this number of bytes.

    • Declaration

      this();

      No default construction if an allocator must be provided.

    • Declaration

      this(Allocator allocator);

      Use allocator to allocate and free nodes in the tree.

    • Declaration

      void clear();

      Removes all elements from the tree.

    • Declaration

      void opOpAssign(string op)(T value) if (op == "~");

      tree ~= item operator overload.

    • Declaration

      @safe size_t insert(T value, bool overwrite = false);
      size_t insert(R)(R r, bool overwrite = false) if (isInputRange!R && is(ElementType!R == T));
      size_t insert(T[] values, bool overwrite = false);
      alias insertAnywhere = insert;
      alias put = insert;

      Inserts the given value(s) into the tree.

      Discussion

      This is not a stable insert. You will get strange results if you insert into a tree while iterating over it.

      Parameters

      T value

      the value to insert

      bool overwrite

      if true the given value will replace the first item in the tree that is equivalent (That is greater-than and less-than are both false) to value. This is useful in cases where opCmp and opEquals for T type have different meanings. For example, if the element type is a circle that has a position and a color, the circle could implement opCmp to sort by color, and calling insert with overwrite set to true would allow you to update the position of the circle with a certain color in the tree.

      Return Value

      the number of values added.

    • Declaration

      bool remove(T value, void delegate(T) cleanup = null);

      Removes a single value from the tree, or does nothing.

      Discussion

      If allowDuplicates is true only a single element that is equivalent to the given value will be removed. Which of these elements is removed is not defined.

      Parameters

      T value

      a value equal to the one to be removed

      void delegate(T) cleanup

      a function that should be run on the removed item

      Retuns: true if any value was removed

    • Declaration

      const @nogc @safe bool contains(T value);

      Return Value

      true if the tree conains This page contains documentation for the EMSI containers library. Use the package index on the left to explore the documentation. the given value

    • Declaration

      const pure nothrow @nogc @property @safe size_t length();

      Return Value

      the number of elements in the tree.

    • Declaration

      const pure nothrow @nogc @property @safe bool empty();

      Return Value

      true if the tree is empty.

    • Declaration

      inout @nogc @trusted auto opSlice(this This)();

      Return Value

      a range over the tree. Do not insert into the tree while iterating because you may iterate over the same value multiple times or skip some values entirely.

    • Declaration

      inout @trusted auto lowerBound(this This)(inout T value);

      Return Value

      a range of elements which are less than value.

    • Declaration

      inout @trusted auto equalRange(this This)(inout T value);

      Return Value

      a range of elements which are equivalent (though not necessarily equal) to value.

    • Declaration

      inout @trusted auto upperBound(this This)(inout T value);

      Return Value

      a range of elements which are greater than value.

    • Declaration

      inout pure @property @trusted inout(T) front(this This)();

      Return Value

      the first element in the tree.

    • Declaration

      inout pure @property @trusted inout(T) back(this This)();

      Return Value

      the last element in the tree.

    • Declaration

      struct Range(ThisT);

      Tree range

      • Declaration

        const @nogc @property ET front();
        const pure nothrow @nogc @property @safe bool empty();
        void popFront();

        Standard range operations