Crate thicket 

   

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 Cloneor 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

Type	Stores	Sorts By	Iterator
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

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.

Modules

util

Utility types to support self balancing binary splay trees

Structs

Map

A simple map between keys and values, implemented using a splay tree.

MapBy

A simple map between keys and values, implemented using a splay tree.

MapByIterator

Iterator over a MapBy

MapIterator

Iterator over a Map

Set

A simple of keys, implemented using a splay tree.

SetBy

A simple set of keys, implemented using a splay tree.

SetByIterator

Iterator over a SetBy

SetIterator

Iterator over a Set

StringMap

A simple map between strings and values, implemented using a splay tree.

StringMapBy

A simple map between strings and values, implemented using a splay tree.

StringMapByIterator

Iterator over a StringMap

StringMapIterator

Iterator over a StringMap

StringSet

A simple set of strings, implemented using a splay tree.

StringSetBy

A simple set of strings, implemented using a splay tree.

StringSetByIterator

Iterator over a StringSet

StringSetIterator

Iterator over a StringSet