A collection of persistent data structures written in Java
Any fool can write the Finger Tree data structure in Haskell, a purely functional language with expressive type system and lazy evaluation. But can you do this in Java, a vastly more verbose language with a weaker and clumsier type system? This repository contains the Enterprise Edition of Finger Tree, a pointless and stupid exercise, but very educational too. Because why not?
There are a few other persistent data structures too, such as:
- ArrayTrieHashMap
- PatriciaTrieHashMap
- Leaf-Leaning Red-Black Tree
- Queue, Stack, etc.
Probably none of this should be used in production, but might be used for the educational purposes.
The inspiring list of publications:
- Purely Functional Data Structures by Chris Okasaki
- Ideal Hash Trees by Phil Bagwell
- Finger trees: a simple general-purpose data structure by Ralf Hinze and Ross Paterson
- Left-LeaningRed-Black Trees by Robert Sedgewick