# Collections using splay trees
## Introduction
This crate implements a variety of collections based on binary trees, in particular splay trees.
Splay trees are a type of data structure that offers logarithmic time lookup for random access
of data. They are self-organising, in the sense that commonly accessed items with the tree send
to 'bubble' to the top so that future lookups of these items will be faster in the future.
## Benefits
The crate complements the standard `std::collection` routines, but provide the following
benefits:
- Keys stored in the collections do not need to be hashable.
- Keys are sorted into an 'ascending' order within the collection by comparing keys pairwise.
- Keys in the collection do not need to implement `Clone`or `Copy`. Keys the support `Ord` can
use `Map` or `Set`, etc, but if not a custom function can be supplied to compare keys using
`MapBy` or `StringMapBy`, etc.
- The crate is small and `#![no_std]`.
- Copying and moving of keys are values is minimised. They are stored as (key, Value) pairs in a
single array. They are moved when inserted and moved when the array is expanded, but otherwise
do not move as the tree reconfigures around them. Once the array is large enough the memory is
managed internally and when keys are removed that memory is recycled for future use.
- The storage of the (key, value) pair is separate to the storage of the structure of the tree.
This has subtle benefits such as removing a (key, value) pair does not immediately remove them
from strage. That means, for example that the `pop_first()` returns a reference `&(K, V)` not
a value `(K, V)`.
## Contents
The initial release of the `thicket` crate includes the following types
<center>
| `Map` | Key/Value | Ord | `MapIterator` |
| `Set` | Key | Ord | `SetIterator` |
| `StringMap` | String/Value | Ord | `StringMapIterator` |
| `StringSet` | String | Ord | `StringSetIterator` |
| `MapBy` | Key/Value | Function | `MapByIterator` |
| `SetBy` | Key | Function | `SetByIterator` |
| `StringMapBy` | String/Value | Function | `StringMapByIterator` |
| `StringSetBy` | String | Function | `StringSetByIterator` |
</center>
The crate exposes an additional type `util::Tree` that provides the foundation of the other
types. This can be thought of as a utility that manages a set of `usize` indices into an
external vector of data, without storing the vector itself. It is provided to support
development of additional collection types.