vebTree

This struct represents the VEB tree itself. For the sake of convinience it saves the provided at the initialization step wished maximum element. However at the point of development it is only used for testing. Beyond this, it stores only the reference to the root element, as the theory tells. The tree implements not only the documented interface of a van VEB tree, but is also a bidirectional range. It supports two slice operations and a non-trivial opIndex operator.

Constructors

this this(): default constructor of a VEB tree is disabled.
this this(uint expectedSize): to construct a VEB tree one should provide the maximum element one wish to be able to store.
this this(uint[] range): another possibility is to construct a VEB tree by providing an array.

Members

Functions

capacity uint capacity(): this method returns the capacity of the tree. It is equal to the next power of two with regard to the maximum element
fill uint fill(uint m, Random rndGenInUse): Undocumented in source. Be warned that the author may not have intended to support it.
fill uint fill(uint[] arr, Random rndGenInUse, uint fillPercentage): Undocumented in source. Be warned that the author may not have intended to support it.
insert void insert(uint x): this method is used to add an element to the tree. duplicate values will be ignored.
insert void insert(uint[] arr): this method overrides the insert method to directly use arrays
member bool member(uint x): this method is used to determine, whether an element is currently present in the tree
opIndex auto opIndex(uint i): This is a nontrivial opIndex operator on indizies of the tree. Given an index a range (!) is returned, which is, either the range of elements in the tree build up by [predecessor(i) .. successor(i)] (i. e. excluding the successor(i)), when the given index is not set. Or, if the given index is set, [member(i), successor(i)]. If an index out of bounds is given, an empty array is returned. The tree must not be empty to use this function.
opSlice uint[] opSlice(): opSlice operator to get the underlying array. This is a draft version, as it uses the successor method of the class. So getting the underlying array is proportional to n. As this functionaly is not seen as crucial, it is enough for the first time.
opSlice uint[] opSlice(uint begin, uint end): opSlice operator to get the underlying array between given bounds. This is a draft version, as it uses the successor method of the class. So getting the underlying array is proportional to min(n, m), where n is the number of elements between bounds and m are the number of present elements in the tree.
popBack void popBack(): Undocumented in source. Be warned that the author may not have intended to support it.
popFront void popFront(): Undocumented in source. Be warned that the author may not have intended to support it.
predecessor Nullable!uint predecessor(uint x): this method retrieves the predecessor of the given input.
remove void remove(uint x): this method is used to remove elements from the tree. not existing values will be ignored.
successor Nullable!uint successor(uint x): this method retrieves the successor of the given input.

Properties

back Nullable!uint back [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
elementCount auto elementCount [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
empty bool empty [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
front Nullable!uint front [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
length uint length [@property getter]: This method returns the amount of elements currently present in the tree. This is a draft version, as it uses the slice operator of the class. So getting this number has a complexity proportional to n. As this functionaly is not seen as crucial, it is enough for the first time.
max Nullable!uint max [@property getter]: this method is used to determine the maximum of the tree
min Nullable!uint min [@property getter]: this method is used to determine the minimum of the tree
save vebTree save [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.

Variables

expectedSize uint expectedSize;: Undocumented in source.