[−][src]Struct k2_tree::K2Tree
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
matrix_width: usize
The width of the matrix this K2Tree represents. The matrix is always square, so this is also the height.
stem_k: usize
The k value of the K2Tree's stems.
This determines the minimum width of the matrix it represents, the length of stems, the number
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.
slayer_starts: Vec<usize>
The index of the first bit in each stem-layer in stems.
stems: BitVec
The bits that comprise the stems of the tree.
stem_to_leaf: Vec<usize>
Layer that links the positive bits in the final stem-layer.
The value of each element is the offset of a positive stem-bit relative to the the start of the final stem-layer. The index of each element corresponds to the position of the leaf-block it links to.
leaves: BitVec
The bits that comprise the leaves of the tree.
Implementations
impl K2Tree
[src]
pub fn new() -> Self
[src]
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>
[src]
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>
[src]
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>
[src]
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
[src]
Returns true if a K2Tree
contains no 1s
pub fn get(&self, x: usize, y: usize) -> Result<bool, Error>
[src]
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>
[src]
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>
[src]
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>
[src]
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 stems(&self) -> Stems<'_>ⓘ
[src]
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
[src]
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<'_>ⓘ
[src]
Returns an iterator over the K2Tree's stems which produces only the raw boolean values.
pub fn leaves(&self) -> Leaves<'_>ⓘ
[src]
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ⓘNotable traits for IntoLeaves
impl Iterator for IntoLeaves type Item = LeafBit;
[src]
Notable traits for IntoLeaves
impl Iterator for IntoLeaves type Item = LeafBit;
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<'_>ⓘ
[src]
Returns an iterator over the K2Tree's leaves which produces only the raw boolean values.
pub fn grow(&mut self)
[src]
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)
[src]
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>
[src]
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)
[src]
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>
[src]
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>
[src]
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>
[src]
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
[src]
impl Debug for K2Tree
[src]
impl Default for K2Tree
[src]
impl Display for K2Tree
[src]
impl Eq for K2Tree
[src]
impl Hash for K2Tree
[src]
fn hash<H: Hasher>(&self, state: &mut H)
[src]
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl PartialEq<K2Tree> for K2Tree
[src]
Auto Trait Implementations
impl RefUnwindSafe for K2Tree
impl Send for K2Tree
impl Sync for K2Tree
impl Unpin for K2Tree
impl UnwindSafe for K2Tree
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T> ToString for T where
T: Display + ?Sized,
[src]
T: Display + ?Sized,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,