Struct k2_tree::K2Tree

pub struct K2Tree {
    pub stem_k: usize,
    pub leaf_k: usize,
    pub max_slayers: usize,
    pub stems: BitVec,
    pub leaves: BitVec,
}

A collection designed to efficiently compress sparsely-populated bit-matrices.

The K2Tree represents a matrix of bits and behaves as if it is a bit-matrix. The k value of this structure is currently fixed at 2, but future updates may allow customisation. The matrix represented by the K2Tree must always be square, with a width/height equal to a power of k: 8, 16, 32 etc. This isn’t much of an issue because almost all empty cells in the matrix are compressed-away, so don’t stress about wasted columns/rows.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  //matrix_width = 8, k = 2
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.set(0, 4, true);
  tree.set(6, 5, true);
  tree.set(0, 4, false);
  assert_eq!(false, tree.get(0, 4)?);
  assert_eq!(true, tree.get(6, 5)?);
  assert_eq!(false, tree.get(0, 0)?);
  Ok(())
}

Fields

stem_k: usize

The k value of the K2Tree’s stems.

leaf_k: usize

The k value of the K2Tree’s leaves.

max_slayers: usize

The maximum number of stem-layers possible given the matrix_width.

stems: BitVec

The bits that comprise the stems of the tree.

leaves: BitVec

The bits that comprise the leaves of the tree.

Implementations

impl K2Tree

pub fn new() -> Self

Returns a K2Tree representing an 8x8 bit-matrix of all 0s. K = 2.

use k2_tree::K2Tree;
let tree = K2Tree::new();
assert!(tree.is_empty());
assert_eq!(8, tree.matrix_width());
assert_eq!(2, tree.stem_k);
assert_eq!(2, tree.leaf_k);

pub fn with_k(stem_k: usize, leaf_k: usize) -> Result<Self, Error>

Returns a K2Tree with a specified k-value, which represents an empty bit-matrix of width k.pow(3).

Returns a SmallKValue error if k < 2.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let tree = K2Tree::with_k(4, 4)?;
  assert!(tree.is_empty());
  assert_eq!(4usize.pow(3), tree.matrix_width());
  assert_eq!(64, tree.matrix_width());
  assert_eq!(4, tree.stem_k);
  assert_eq!(4, tree.leaf_k);
  Ok(())
}

pub fn set_stem_k(&mut self, stem_k: usize) -> Result<(), Error>

Changes the stem_k value of a K2Tree. This can be a time and space expensive operation for large, non-sparse datasets. Returns a SmallKValue error if stem_k < 2.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::new();
  tree.set_stem_k(4);
  assert!(tree.set_stem_k(1).is_err());
  Ok(())
}

pub fn set_leaf_k(&mut self, leaf_k: usize) -> Result<(), Error>

Changes the leaf_k value of a K2Tree. This can be a time and space expensive operation for large, non-sparse datasets. Returns a SmallKValue error if stem_k < 2.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::new();
  tree.set_leaf_k(4);
  assert!(tree.set_leaf_k(1).is_err());
  Ok(())
}

pub fn is_empty(&self) -> bool

Returns true if a K2Tree contains no 1s.

pub fn get(&self, x: usize, y: usize) -> Result<bool, Error>

Returns that state of a bit at a specified coordinate in the bit-matrix the K2Tree represents.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.set(0, 1, true)?;
  assert_eq!(true, tree.get(0, 1)?);
  assert_eq!(false, tree.get(0, 0)?);
  Ok(())
}

pub fn get_row(&self, y: usize) -> Result<Vec<bool>, Error>

Returns a BitVec containing the bits in a specified row, in order.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use bitvec::prelude::bitvec;
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.set(1, 0, true)?;
  tree.set(3, 0, true)?;
  tree.set(6, 0, true)?;
  assert_eq!(
    vec![false,true,false,true,false,false,true,false],
    tree.get_row(0)?
  );
  Ok(())
}

pub fn get_column(&self, x: usize) -> Result<Vec<bool>, Error>

Returns a BitVec containing the bits in a specified column, in order.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use bitvec::prelude::bitvec;
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.set(1, 1, true)?;
  tree.set(1, 3, true)?;
  tree.set(1, 6, true)?;
  assert_eq!(
    vec![false,true,false,true,false,false,true,false],
    tree.get_column(1)?
  );
  Ok(())
}

pub fn set(&mut self, x: usize, y: usize, state: bool) -> Result<(), Error>

Sets the state of a bit at the coordinates (x, y) in the bit-matrix the K2Tree represents.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  assert_eq!(false, tree.get(0, 0)?);
  tree.set(0, 0, true)?;
  assert_eq!(true, tree.get(0, 0)?);
  Ok(())
}

pub fn matrix_width(&self) -> usize

Returns the width of the bit-matrix that a K2Tree represents.

The matrix is always square, so this is also the height.

This can only have certain values, depending on the values of leaf_k and stem_k, so it is common for a K2Tree’s matrix_width to be greater than the matrix it was built from. Thankfully, trailing rows/columns have no affect on the size of the K2Tree.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::{K2Tree, matrix::BitMatrix};
  let matrix = BitMatrix::with_dimensions(8, 8);
  let tree = K2Tree::from_matrix(matrix, 2, 2)?;
  assert_eq!(8, tree.matrix_width());
  Ok(())
}

pub fn stems(&self) -> Stems<'_>

Returns an iterator over the K2Tree’s stems which produces instances of StemBit.

StemBit contains extra information on the layer, block and offset of the specific bit in the stems.

pub fn into_stems(self) -> IntoStems

Consumes the K2Tree to return an iterator over its stems, which produces instances of StemBit.

StemBit contains extra information on the layer, block and offset of the specific bit in the stems.

pub fn stems_raw(&self) -> StemsRaw<'_>

Returns an iterator over the K2Tree’s stems which produces only the raw boolean values.

pub fn leaves(&self) -> Leaves<'_>

Returns an iterator over the K2Tree’s leaves which produces instances of LeafBit.

LeafBit contains extra information on the exact coordinates of each bit in the leaves.

pub fn into_leaves(self) -> IntoLeaves

Consumes the K2Tree to return an iterator over its leaves, which produces instances of LeafBit.

LeafBit contains extra information on the exact coordinates of each bit in the leaves.

pub fn leaves_raw(&self) -> LeavesRaw<'_>

Returns an iterator over the K2Tree’s leaves which produces only the raw boolean values.

pub fn grow(&mut self)

Increases the height and width of the matrix the K2Tree represents by a factor of k.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  assert_eq!(2, tree.stem_k);
  assert_eq!(2, tree.leaf_k);
  assert_eq!(8, tree.matrix_width());
  tree.grow();
  assert_eq!(16, tree.matrix_width());
  tree.grow();
  assert_eq!(32, tree.matrix_width());
  Ok(())
}

pub fn shrink_if_possible(&mut self)

Only shrinks the height and width of the matrix the K2Tree represents by a factor of k if it is possible.

Does not Err if the matrix cannot be shrunk i.e. it is already at the minimum size.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.grow();
  assert_eq!(16, tree.matrix_width());
  tree.shrink_if_possible();
  assert_eq!(8, tree.matrix_width());
  tree.shrink_if_possible();
  assert_eq!(8, tree.matrix_width());
  Ok(())
}

pub fn shrink(&mut self) -> Result<(), Error>

Attempts to reduce the height and width of the matrix the K2Tree represents by a factor of k.

Returns an Err if the matrix cannot be shrunk i.e. it is already at the minimum size.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.grow();
  assert_eq!(16, tree.matrix_width());
  assert!(tree.shrink().is_ok());
  assert_eq!(8, tree.matrix_width());
  assert!(tree.shrink().is_err());
  Ok(())
}

pub unsafe fn shrink_unchecked(&mut self)

Reduces the height and width of the matrix the K2Tree represents by a factor of k without doing any bounds checking before or integrity checking afterwards.

Safety

Do not attempt to shrink matrix_width smaller than k^3.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.grow();
  assert_eq!(16, tree.matrix_width());
  unsafe { tree.shrink_unchecked(); }
  assert_eq!(8, tree.matrix_width());
  Ok(())
}

pub fn into_matrix(self) -> Result<BitMatrix, Error>

Comsumes the K2Tree to produce the bit-matrix it represented.

The matrix is presented as a list of columns of bits, Vec<Vec>.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.set(0, 0, true)?;
  tree.set(5, 6, true)?;
  tree.set(7, 7, true)?;
  let matrix = tree.into_matrix()?;
  assert_eq!(true, matrix.get(0, 0).unwrap());
  assert_eq!(true, matrix.get(5, 6).unwrap());
  assert_eq!(true, matrix.get(7, 7).unwrap());
  assert_eq!(false, matrix.get(4, 3).unwrap());
  Ok(())
}

pub fn to_matrix(&self) -> Result<BitMatrix, Error>

Produces the bit-matrix a K2Tree represents.

The matrix is presented as a list of columns of bits, Vec<Vec>.

fn main() -> Result<(), k2_tree::error::K2TreeError> {
  use k2_tree::K2Tree;
  let mut tree = K2Tree::with_k(2, 2)?;
  tree.set(0, 0, true)?;
  tree.set(5, 6, true)?;
  tree.set(7, 7, true)?;
  let matrix = tree.to_matrix()?;
  assert_eq!(true, matrix.get(0, 0).unwrap());
  assert_eq!(true, matrix.get(5, 6).unwrap());
  assert_eq!(true, matrix.get(7, 7).unwrap());
  assert_eq!(false, matrix.get(4, 3).unwrap());
  Ok(())
}

pub fn from_matrix(
    matrix: BitMatrix,
    stem_k: usize,
    leaf_k: usize
) -> Result<Self, Error>

Constructs a K2Tree which represents the state of the input matrix.

All types that can produce rows of bits are valid inputs.

use k2_tree::{K2Tree, matrix::BitMatrix};
let mut m = BitMatrix::with_dimensions(8, 8);
m.set(0, 5, true);
assert!(K2Tree::from_matrix(m, 2, 2).is_ok());

Trait Implementations

impl Clone for K2Tree

fn clone(&self) -> K2Tree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for K2Tree

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

Formats the value using the given formatter.

impl Default for K2Tree

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for K2Tree

fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>

Deserialize this value from the given Serde deserializer.

impl Display for K2Tree

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

Formats the value using the given formatter.

impl Hash for K2Tree

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl PartialEq<K2Tree> for K2Tree

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

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

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

This method tests for !=.

impl Serialize for K2Tree

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.

impl Eq for K2Tree