Struct confertus::dynamic_vector::DynamicBitVector

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

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

impl DynamicBitVector

pub fn new() -> Self

Constructs new DynamicBitVector with empty root Node.

pub fn apply<T>(
    &mut self,
    f: impl FnMut(&mut DynamicBitVector, isize, usize) -> T,
    index: usize
) -> T

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

pub fn apply_bitop<T>(
    &self,
    f: impl FnMut(&DynamicBitVector, isize, usize, bool) -> T,
    g: impl Fn(&DynamicBitVector, usize, bool) -> T,
    index: usize,
    bit: bool
) -> T where
    T: Add<Output = T>, 

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

pub fn push(&mut self, bit: bool)

Append bit to the rightmost position in the rightmost Leaf.

pub fn retrace(&mut self, node: usize, depth_change: i8)

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.

pub fn rotate_left(&mut self, z: usize, x: usize)

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.

pub fn rotate_right(&mut self, z: usize, x: usize)

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.

pub fn rebalance(&mut self, node: usize, parent: usize)

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

pub fn rebalance_no_child(&mut self, parent: usize)

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).

pub fn create_right_leaf(&mut self, node: usize) -> isize

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

pub fn closest_neighbor_leaf(&self, leaf: isize) -> Option<Either<isize, isize>>

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

pub fn closest_neighbor_child(
    &self,
    child: usize
) -> Option<Either<isize, isize>>

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.

pub fn merge_away(&mut self, leaf: isize)

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.

pub fn swap_remove_leaf(&mut self, leaf: isize)

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.

pub fn swap_remove_node(&mut self, node: usize)

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

pub fn get_side(&self, child: isize) -> Option<Either<usize, usize>>

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

pub fn get_leaf_side(&self, child: isize) -> Either<usize, usize>

Given Leaf child, return side on parent and parent index

pub fn get_node_side(&self, child: usize) -> Option<Either<usize, usize>>

Given Node child, return side on parent and parent index

pub fn update_left_values_only(&mut self, node: usize, child: isize) -> bool

Non-recursive updating of parent nums and ones values.

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

pub fn update_left_values(&mut self, node: usize, child: isize)

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

pub fn split_leaf(&mut self, leaf: isize) -> usize

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.

pub fn full_nums_ones(&self, child: isize) -> (usize, usize)

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

impl BitSize for DynamicBitVector

fn bitsize_full(&self) -> usize

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

fn bitsize(&self) -> usize

Return total number of bits used by Type

fn bitsize_used(&self) -> usize

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

impl Clone for DynamicBitVector

fn clone(&self) -> DynamicBitVector

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DynamicBitVector

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for DynamicBitVector

fn default() -> DynamicBitVector

Returns the “default value” for a type.

impl Display for DynamicBitVector

Really just the Debug output

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Dot for DynamicBitVector

fn dotviz(&self, self_id: isize) -> String

Return dot representation for graph visualization.

impl DynBitVec for DynamicBitVector

fn insert(&mut self, index: usize, bit: bool) -> Result<(), &'static str>

Insert bit at position index in underlying container

fn delete(&mut self, index: usize) -> Result<(), &'static str>

Remove bit value at position index

fn flip(&mut self, index: usize)

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

fn nums(&self) -> usize

Return used capacity of underlying container

fn len(&self) -> usize

Return used capacity of underlying container

fn is_empty(&self) -> bool

If the Leaf has active values

impl Index<isize> for DynamicBitVector

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.

type Output = Leaf

The returned type after indexing.

fn index(&self, index: isize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl Index<usize> for DynamicBitVector

Return Node for usize indexing

type Output = Node

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl IndexMut<isize> for DynamicBitVector

fn index_mut(&mut self, index: isize) -> &mut Self::Output

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

impl IndexMut<usize> for DynamicBitVector

fn index_mut(&mut self, index: usize) -> &mut Self::Output

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

impl PartialEq<DynamicBitVector> for DynamicBitVector

fn eq(&self, other: &DynamicBitVector) -> bool

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

fn ne(&self, other: &DynamicBitVector) -> bool

This method tests for !=.

impl StaticBitVec for DynamicBitVector

fn access(&self, index: usize) -> bool

Return value at position index of DynamicBitVector.

Panics

If index is out of bounds.

fn values(&self) -> Self::Intern

Return full internal container

type Intern = Vec<u128, Global>

fn ones(&self) -> usize

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

fn rank(&self, bit: bool, index: usize) -> usize

Returns number of bit-values up to index in container

fn select(&self, bit: bool, n: usize) -> usize

Return index of n-th bit-value in container

impl StructuralPartialEq for DynamicBitVector