thicket/
lib.rs

1//! [![github]](https://github.com/duncanlivingston/thicket)&ensp;
2//! [![crates-io]](https://crates.io/duncanlivingston/thicket)&ensp;
3//!
4//! [github]: https://img.shields.io/badge/github-8da0cb?style=for-the-badge&labelColor=555555&logo=github
5//! [crates-io]: https://img.shields.io/badge/crates.io-fc8d62?style=for-the-badge&labelColor=555555&logo=rust
6//!
7//! ## Introduction
8//!
9//! This crate implements a variety of collections based on binary trees, in particular splay trees.
10//! Splay trees are a type of data structure that offers logarithmic time lookup for random access
11//! of data. They are self-organising, in the sense that commonly accessed items with the tree send
12//! to 'bubble' to the top so that future lookups of these items will be faster in the future.
13//!
14//! ## Benefits
15//!
16//!  The crate complements the standard `std::collection` routines, but provide the following
17//! benefits:
18//!
19//! - Keys stored in the collections do not need to be hashable.
20//! - Keys are sorted into an 'ascending' order within the collection by comparing keys pairwise.
21//! - Keys in the collection do not need to implement `Clone`or `Copy`. Keys the support `Ord` can
22//!   use `Map` or `Set`, etc, but if not a custom function can be supplied to compare keys using
23//!   `MapBy` or `StringMapBy`, etc.
24//! - The crate is small and `#![no_std]`.
25//! - Copying and moving of keys are values is minimised. They are stored as (key, Value) pairs in a
26//!   single array. They are moved when inserted and moved when the array is expanded, but otherwise
27//!   do not move as the tree reconfigures around them. Once the array is large enough the memory is
28//!   managed internally and when keys are removed that memory is recycled for future use.
29//! - The storage of the (key, value) pair is separate to the storage of the structure of the tree.
30//!   This has subtle benefits such as removing a (key, value) pair does not immediately remove them
31//!   from strage. That means, for example that the `pop_first()` returns a reference `&(K, V)` not
32//!   a value `(K, V)`.
33//!
34//! ## Contents
35//!
36//! The initial release of the `thicket` crate includes the following types
37//!
38//! <center>
39//!
40//! | Type          | Stores       | Sorts By  | Iterator              |
41//! |:--------------|:-------------|:----------|-----------------------|
42//! | `Map`         | Key/Value    | Ord       | `MapIterator`         |
43//! | `Set`         | Key          | Ord       | `SetIterator`         |
44//! | `StringMap`   | String/Value | Ord       | `StringMapIterator`   |
45//! | `StringSet`   | String       | Ord       | `StringSetIterator`   |
46//! | `MapBy`       | Key/Value    | Function  | `MapByIterator`       |
47//! | `SetBy`       | Key          | Function  | `SetByIterator`       |
48//! | `StringMapBy` | String/Value | Function  | `StringMapByIterator` |
49//! | `StringSetBy` | String       | Function  | `StringSetByIterator` |
50//!
51//! </center>
52//!
53//! The crate exposes an additional type `util::Tree` that provides the foundation of the other
54//! types. This can be thought of as a utility that manages a set of `usize` indices into an
55//! external vector of data, without storing the vector itself. It is provided to support
56//! development of additional collection types.
57
58#![no_std]
59#![warn(missing_docs)]
60
61mod map;
62mod set;
63pub mod util;
64
65pub use map::*;
66pub use set::*;
thicket/lib.rs

thicket/
lib.rs
