# Sequence Tree Collection
### a collection for fast read and right storage of sequential data
###### (as an alternative to hashtable)

#### Intro
Sequence trees are a new type of collection that allows to store data using a key that is a sequence (such as string) and
fetch then corresponding value to that key at a time that is relative to the length of the key and the amount of similar
keys that already exist in the tree

This collection is meant to provide an alternative to hashtables which relay on a hash functions to convert the sequence to
a place in an array.

#### Hashtables
The advantages of hashtables is the time in take to fetch or store a key is often dependent on the time is takes to hash
said key, which in most cases is rather quick, but they have a drawback because a hash function have collision, meaning two different
values passed to the hash function can generate the same hash. To solve this many work arounds have been developed and implemented
but they all require some computationally expensive operations. In addition to that, when as hashtable stores more and more values
resizing of the array in the backend of the hashtable is required which can be an expensive operation.

#### Sequence Trees
In come Sequence Trees! sequence trees break up a given key in to nodes with each node holding one element of the sequence (in case of strings a character),
and each node linked to it's next neighbor (like a linked list), Then the very last value holds the actual value assigned to the key.
Now to fetch the value of a key one simply need to follow each node in the tree in accordance the sequence of the key and easily reach
the value, no hash function needed!. One advantage of this is that the keys are naturally compressed simply due to the nature of this collection,
but the challange to making the tree fast is in the way one finds the correct next node since one node (character) can link to multiple
other characters (up to as much as in your character encoding). Because characters are backed by numbers I was able to simply store the
next nodes of each node in a Binary Search Tree, but one can also use hashtables (which can be expensive memory wise since they reserve space),
or even just a plain array (but that would be rather slow).

Sequence trees are slower than hashtables since they need to follow each element in the sequence by finding the correct
next node in the many next nodes each node can potentially hold. for this reason also similarity of the keys provides a
speed boost.

#### Current State
Tree is implemented generically, for this implementation though type used for the key must have
the following traits `PartialOrd + PartialEq + Copy + Default` since a binary tree is used to find the next
node. Deletion of keys is currently supported but not thoroughly tested so use at your own risk and please
inform me if you find any issues.

The plan for the future is mainly performance testing and documentation

#### How to use:
    
    let mut st: SequenceTree<char, u64> = SequenceTree::new(); // initialize tree
    
    let key: Vec<char> = String::from("hello").chars().collect(); // create key

    st.set(key.to_owned(), 55); // set key

    println!("{:?}", st.get(key) ); //get value of key
    
#### Todo:
- deletion of keys and values from tree
    - ~~implement~~
    - more thorough testing
- ~~make generic implementation~~
- expand README to include 
    - picture explantions, 
    - efficiency calculation 
    - preformance chart to compare with current solutions
- comments in code