[−][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
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
[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 matrix_width(&self) -> usize
[src]
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<'_>ⓘ
[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<'de> Deserialize<'de> for K2Tree
[src]
pub fn deserialize<D: Deserializer<'de>>(
deserializer: D
) -> Result<Self, D::Error>
[src]
deserializer: D
) -> Result<Self, D::Error>
impl Display for K2Tree
[src]
impl Eq for K2Tree
[src]
impl Hash for K2Tree
[src]
pub fn hash<H: Hasher>(&self, state: &mut H)
[src]
pub fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
impl PartialEq<K2Tree> for K2Tree
[src]
pub fn eq(&self, other: &Self) -> bool
[src]
#[must_use]pub fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
impl Serialize for K2Tree
[src]
Auto Trait Implementations
impl RefUnwindSafe for K2Tree
[src]
impl Send for K2Tree
[src]
impl Sync for K2Tree
[src]
impl Unpin for K2Tree
[src]
impl UnwindSafe for K2Tree
[src]
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,
pub fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> DeserializeOwned for T where
T: for<'de> Deserialize<'de>,
[src]
T: for<'de> Deserialize<'de>,
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.
pub fn to_owned(&self) -> T
[src]
pub 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.
pub 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>,