#Tree #Interval #Range #AVL #DIET

lz_diet

An AVL balanced Discrete Interval Encoding Tree

5 releases

✓ Uses Rust 2018 edition

0.1.5 Jun 15, 2019
0.1.4 Mar 20, 2018
0.1.3 Aug 9, 2017

#279 in Data structures

28 downloads per month

MIT license

66KB
1.5K SLoC

Lz DIET (Discrete Interval Encoding Tree)

This crate provides a Discrete Interval Encoding Tree implementation.

Build Status

Documentation

Features

  • The tree is AVL balanced

Crate Features

  • bigint - Allows the tree to be used with BigInt and BigUInt
  • extprim - Allows the tree to be used with u128 and i128
  • chrono - Allows the tree to be used with chrono Dates

License

This project is licensed under the MIT License (LICENSE or http://opensource.org/licenses/MIT).


lib.rs:

This crate provides a Discrete Interval Encoding Tree (DIET) implementation.

At a small performance cost on mutation of the tree, large memory savings are made and performance gains may be made on lookup of elements.

An example of using the Diet<T>:

use lz_diet::{Diet, Interval};

let mut diet = Diet::new();
diet.insert(5);
diet.insert(7);

diet.insert(6);

let intervals: Vec<_> = diet.into_iter().collect();
assert_eq!(&intervals[..], &[Interval::from(5..8)]);

Interval endpoints are evaluated to determine whether the interval is discrete, this check implemented with the AdjacentBound trait and may be quickly implemented for types with a scalar interval using the adjacent_bound_impl macro provided.

Dependencies

~145–375KB