pub struct DynamicBitVector {
    pub root: usize,
    pub nodes: Vec<Node>,
    pub leafs: Vec<Leaf>,
}
Expand description

Implementation of Dynamic Bit Vector using self-balancing AVL tree.

Instance bit size: 56 bytes = 448 (not included: bit sizes of instances in Vector structures)

Fields

root: usize

index to root Node, 8 bytes

nodes: Vec<Node>

Vector containing Node, 24 bytes

leafs: Vec<Leaf>

Vector containing Leaf, 24 bytes

Implementations

Constructs new DynamicBitVector with empty root Node.

Descend tree to position index and apply function f with f(self, leaf, index) -> T.

Used to implement traversal for DynamicBitVector::access, DynamicBitVector::flip, DynamicBitVector::delete, DynamicBitVector::insert

Panics

If tree invariances are violated

Descend tree to position index and apply function f with f(self, leaf, index, bit) -> T. Function g with g(self, node, left_descent) -> T is used to modify the return value of f dependent on node. Its value is added to the result of recursion.

Used to implement traversal for DynamicBitVector::rank

Panics

If tree invariances are violated

Append bit to the rightmost position in the rightmost Leaf.

Retrace and update rank of parent until root (or until they cancel out, or until a rebalancing happens). node self is expected to be updated already.

Arguments
  • node: usize - begin retracing here, first to get updated is parent of node
  • depth_change: i8 - if depth change was positive or negative. Addition/Subtraction to rank depends on which child side it came from.

Left rotation of Nodes x and z.

Assumes that z is right child of x, x.rank == 2 and z.rank == 1|0 (0 can only happens after deletion, and correct ranks might not be zero in all situations after rotation).

        │parent                                          │parent
        │                                                │
      ┌─▼─┐                                            ┌─▼─┐
  left│ X │right                                   left│ Z │right
  ┌───┤   ├───┐                                    ┌───┤   ├───┐
  │   │r:2│   │                                    │   │r:0│   │
┌─▼─┐ └───┘ ┌─▼─┐                                ┌─▼─┐ └───┘ ┌─▼─┐
│   │   left│ Z │right    left rotation      left│ X │right  │   │
│T1 │   ┌───┤   ├───┐                        ┌───┤   ├───┐   │T4 │
│   │   │   │r:1│   │     ────────────►      │   │r:0│   │   │   │
└───┘ ┌─▼─┐ └───┘ ┌─▼─┐                    ┌─▼─┐ └───┘ ┌─▼─┐ └───┘
      │   │       │   │                    │   │       │   │
      │T23│       │T4 │                    │T1 │       │T23│
      │   │       │   │                    │   │       │   │
      └───┘       └───┘                    └───┘       └───┘

See also the wikipedia article on AVL-tree rebalancing.

Right rotation of Nodes z and x to reestablish rank-difference invariant.

Assumes that z is left child of x, x.rank == 2 and z.rank == 1|0 (0 can only happens after deletion, and correct ranks might not be zero in all situations after rotation). We won’t need to recursively update nums and ones, as they won't change from the perspective of parent`.

              │parent                               │parent
              │                                     │
            ┌─▼─┐                                 ┌─▼─┐
        left│ X │right                        left│ Z │right
        ┌───┤   ├───┐                         ┌───┤   ├───┐
        │   │r:2│   │                         │   │r:0│   │
      ┌─▼─┐ └───┘ ┌─▼─┐   right rotation    ┌─▼─┐ └───┘ ┌─▼─┐
  left│ Z │right  │   │                     │   │   left│ X │right
  ┌───┤   ├───┐   │T4 │    ───────────►     │T1 │   ┌───┤   ├───┐
  │   │r:1│   │   │   │                     │   │   │   │r:0│   │
┌─▼─┐ └───┘ ┌─▼─┐ └───┘                     └───┘ ┌─▼─┐ └───┘ ┌─▼─┐
│   │       │   │                                 │   │       │   │
│T1 │       │T23│                                 │T23│       │T4 │
│   │       │   │                                 │   │       │   │
└───┘       └───┘                                 └───┘       └───┘

See also the wikipedia article on AVL-tree rebalancing.

Rebalance tree to reestablish the rank difference invariance (valid values -1, 0, 1). This is done via combinations of left and right rotations. For insertions, at most two rotations are necessary, deletions might require up until log(depth) rotations to reestablish balance. (rebalancing after deletion requires additional retracing which is not yet implemented)

  • parent is Node with temporary rank / balance factor violation
  • node is higher child of parent

Rebalance tree on parent, where highest node might not be known. One child has to be of |rank| == 1 while the other is rank == 0. Safe to assume, given that parent has |rank| == 2 (would be zero otherwise).

Create Leaf as right child of node, returns id of newly created Leaf.

Return closest immediately sequential neighbor to given Leaf leaf, should it exist. Either additionally tells if it was a right or left child.

Try to return a Leaf that is the closest neighbor (left or right) to the given Node child by ascending, and descending the respectively ‘other’ side of child. Fails if no such neighbor exists.

Try to find neighboring Leaf and merge into, or steal values if neighbor is too full.

Assumption: leaf has a used size of <= 3/4 LeafValue::BITS.

Merge, when found neighbor has at least 1/4 LeafValue::BITS to spare. Otherwise, steal.

Remove Leaf with given index leaf. Swaps with currently last in self.leafs and updates the child index of the parent of the swapped Leaf.

Remove Node with given index node. Swaps with currently last Node and updates its parent index for the swapped child.

Given some Child child, return side on parent and parent index

Given Leaf child, return side on parent and parent index

Given Node child, return side on parent and parent index

Non-recursive updating of parent nums and ones values.

Returns if child is left side child of node or not.

Recursively update parent values in case of left-child modification of nums or ones, coming from child.

Split content of leaf in two, and replace location with new Node. Afterward, apply DynamicBitVector::retrace. Returns id of newly created Node. Potentially rebalances when tracing ranks.

Return nums and ones of child (N2) from both its left and right subtrees.

Graphically, return fully redundant indexing support values nums and ones for N1 by adding left-values from N2 and N3, as well as right-values from N3 (recursively until leaf).

                          ┌───┐
                          │   │
                       ┌──┤N1 │
                       │  │num│
                     ┌─▼─┐└───┘
                     │   │
                     │N2 ├───┐
                     │num│   │
                     └───┘ ┌─▼─┐
                           │   │
                           │N3 │
                           │num│
                           └───┘

Trait Implementations

Return total number of bits allocated by objects managed by structures. Includes all elements on different areas of heap. Read more

Return total number of bits used by Type

Return total number of used bits (fewer than allocated) by objects managed by structures. Includes all elements on different areas of heap. Read more

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Returns the “default value” for a type. Read more

Really just the Debug output

Formats the value using the given formatter. Read more

Return dot representation for graph visualization. Read more

Insert bit at position index in underlying container Read more

Remove bit value at position index Read more

Flip bit at position index, updates ones and num values accordingly Read more

Return used capacity of underlying container

Return used capacity of underlying container

If the Leaf has active values

Return Leaf for isize indexing

When creating a new container with DynamicBitVector::new, a Leaf on position 0 (which cannot be accessed) is created, as all attempted (later) indexing to values >= 0 are converted to usize first and return a Node instead.

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

Return Node for usize indexing

The returned type after indexing.

Performs the indexing (container[index]) operation. Read more

Performs the mutable indexing (container[index]) operation. Read more

Performs the mutable indexing (container[index]) operation. Read more

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

Return value at position index of DynamicBitVector.

Panics

If index is out of bounds.

Return full internal container

Return number of on-bits in container or on left half for tree-based elements

Returns number of bit-values up to index in container Read more

Return index of n-th bit-value in container Read more

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into)

Uses borrowed data to replace owned data, usually by cloning. Read more

Converts the given value to a String. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.