6 releases
0.3.0  Oct 10, 2020 

0.2.0  Dec 22, 2019 
0.1.3  Dec 30, 2018 
0.1.2  Sep 30, 2018 
0.1.1  Apr 17, 2018 
#695 in Data structures
420KB
9K
SLoC
outils
outils is a graph and tree data structure library. It provides utilities which at the time of writing were not available through other crates.
Please read the API Documentation here.
Utilities
Fully dynamic connectivity for general graphs:
A dynamic graph data structure is able to answer queries as to whether two vertices are connected in a graph through a path of edges. In this context, fully dynamic means that the graph can be updated by insertions or deletions of edges between queries (see also Dynamic Connectivity).
DynamicGraph
: Deterministic dynamic connectivity with query cost O(log(n)) and update costs of O(log^2 (n)). The structure also supports vertex weights, dynamically maintaining the total weight of connected components.
Balanced binary search trees:
A balanced binary search tree organizes search keys and their associated payload in a way such that the resulting binary tree has a minimal height, given the number of items stored, resulting in query and update costs of O(log(n)). This library uses AA trees, an abstraction of redblack trees, for balancing the trees after updates.

AaTree
: An iterative AA tree implementation using arena allocation. For most use cases, it is recommended to simply use theBTreeMap
provided by the standard library, as it is considerably faster (appr. 50%). However, if information on parent and child relations between tree nodes, or custom traversal of the tree as such, are needed,AaTree
has an advantage overBTreeMap
. 
WeightedAaTree
: This is similar toAaTree
. However, in addition to the actual payload, node weights can be stored and tree subweights are maintained.
Balanced binary forests:
A balanced binary forest is a forest of balanced binary trees. In contrast to the tree data structures above, the order of the payload is not determined by associated search keys but by the relations of the nodes to each other: the inorder traversal of a forest tree alone represents the order of its nodes. Forest trees can be concatenated or split in order to manage those sequences. Parent and child relations are available, facilitating analysis of the represented sequences.

AaForest
: A forest of trees balanced by the AA tree algorithm. Concatenation and separation do not require a reorganisation of the tree according to search keys  only rebalancing will take place, the order of the sequence being the responsibility of the user. The implementation is based on arena allocation, and tree queries and updates are conducted iteratively, as in the corresponding AA tree structures above. 
WeightedAaForest
: This is similar toAaForest
. However, in addition to the actual payload, a node weight can be stored and tree subweights are maintained.
General purpose tree data structures:
Forest
: A generic forest of trees. The implementation is based on arena allocation and a first child/next sibling representation, thus storing the children of a node as a linked list headed by the first child of the parent node.
Recent changes
 0.3.0
 BREAKING: Changed signatures of
AaTree
andWeightedAaTree
to pass the search key by value asKeyType
required keys to beCopy
.  Added function input_pos() to
AaTree
andWeightedAaTree
to expose the position in a tree where a new key would be inserted.
 BREAKING: Changed signatures of
 0.2.0
 Upgrade to Rust Edition 2018
 0.1.3
 Removed required implementation for Hash for types except
KeyType
 Removed required implementation for Hash for types except
 0.1.2
 Added general purpose forest data structure
 Fixed minor typos in documentation
 0.1.1
 TravisCI support
 Fixed minor typos in documentation
 0.1.0
 Initial version
Coming soon
FixedMemoryForest
: An extension ofForest
that will not exceed its assigned capacity. Rather, the data structur will use leaf recycling when the tree is filled to capacity. The basic idea is to keep track of accesses to leaf nodes and discard those leaves that haven't been accessed for the longest time, should it become necessary to free memory.
Dependencies
~415KB