BTree

Vanilla B-Tree.

O(lg(n)) insertion, removal, and search time, much like the builtin associative arrays.

.init is valid, needs no initialization.

struct BTree (

K

V

alias less = "a < b"

bool allowDuplicates = false

bool duplicateKeyIsUB = false

) {

this(int dummy);

size_t length();

bool empty();

bool insert(K key, V value);

size_t remove(K key);

auto byValue();

auto byValue();

auto byKeyValue();

auto byKeyValue();

inout(V)* opBinaryRight(K key);

inout(V) opIndex(K key);

bool contains(K key);

void display();

enum RangeType;

struct BTreeRange(RangeType type);

}

Constructors

this this(int dummy): Constructor. A new B-tree has no allocation and zero items.

Destructor

~this ~this(): Destructor. All nodes cleared.

Postblit

this(this) this(this): Not copyable.

Members

Enums

RangeType enum RangeType: Undocumented in source.

Functions

byKey auto byKey(): Iterate over all keys in the tree.
byKeyValue auto byKeyValue(): Iterate over all keys and values simultaneously.
byValue auto byValue(): Iterate over all values in the tree.
contains bool contains(K key): Search the B-Tree for a key.
display void display(): Undocumented in source. Be warned that the author may not have intended to support it.
empty bool empty(): Is this B-Tree empty?
insert bool insert(K key, V value): Insert item in tree.
length size_t length(): Number of items in the B-Tree.
opBinaryRight inout(V)* opBinaryRight(K key): Search the B-Tree by key.
opIndex inout(V) opIndex(K key): Search the B-Tree by key.
remove size_t remove(K key): Erase an item from the tree.

Structs

BTreeRange struct BTreeRange(RangeType type): Btree Range

Parameters

K: Key type, must be comparable with less.
V: Value type.
less: Must be a strict inequality, orders all K.
allowDuplicates: Are duplicate keys allowed?
duplicateKeyIsUB: Are duplicate keys UB? When true, user MUST guarantee no duplicates and insert is faster.
Warning: keys don't need opEquals, but: !(a < b) && !(b > a) should imply that:

Meta

Source

See Implementation

dplug core btree structs

BTree