Roadmap

[Yomguithereal]

• MultiIndex
• CompositeIndex
• MultiSet
• MultiMap
• InvertedIndex
• SearchIndex
• Fuzzy?
• Deque
• BloomFilter
• DoublyLinkedList
• SuffixTree
• VPTree
• Buckhard-Keller Tree
• SymSpell
• QuadTree, MX-CIF QuadTree
• k d tree
• Interval tree
• Utils, set operators
• Static matrix + triangular
• Radix tree, Patricia tree
• Index
• M-tree
• BitSet
• LRUCache
• CoverTree
• MarisaTrie
• BiMap
• UnsafeBiMap
• Table
• Multi Vantage Point Tree
• Binary Tree
• RedBlack Tree
• ArrayTrie, DoubleArrayTrie StaticArrayTrie etc.
• Sparse Matrix, Sparse Vector
• Cuckoo filter
• HeapSet, HeapMap
• Static bit array
• Dynamic Typed arrays (1.5 factor by default)
• SparseSet
• Anagram Tree
• Palindrom Tree
• Wavelet Tree
• t-digest
• SparseArray
• CircularBuffer
• BipBuffer
• Nested Sets
• Perfect Hashmaps
• Static search set
• TrieMap
• BoundedHeap, Min-Max Heap
• Spatial Hashmap
• https://github.com/pabloem/advanced_arrays
• Elias Fano QuasiSuccint Indices
• Sparse Table
• Tupled Stack
• Disjoint Set
• dawgmap, dafsa
• GADDAG
• Count Min sketch
• PH-Tree
• BallTree
• HAMT
• Unrolled Linked list
• Fenwick Tree
• Inversion List
• TokenMap
• CallWheel / HashedWheelTimer
• HAT hashed array tree, HAT Trie
• GapBuffer
• x fast trie critbit trie y fast z fast
• Compressed bit vectors rrr etc.
• Default map
• Static stack
• Piece Table
• RoaringBitmap
• Vocab (alternative to incrementalmap)
• Hyperloglog
• SoftHeap
• Boundaries Trie like web entities
• Stern Brocot tree

[vmasto]

How about a Rope? I will try to find time to implement one if you're ok with it.

[Yomguithereal]

Sure @vmasto. Why not. I just have one concern: how do most JavaScript engines implement their strings. The problem is that the native string is probably optimized to do what a rope can do and will probably do it better. But this is just an intuition I have, this is not backed by any benchmark. However, if your rope is able to support sequences of arbitrary elements (not just a string of characters but, say, a list of words) then yes, it would probably be useful. What do you think?

[vmasto]

I am under the impression that native strings have O(n) complexities when it comes to insert, delete and concat whereas a Rope would give us O(m) (where m is the substring's length to be inserted/del/concat) with the caveat that we'll lose random access in constant time. Thus a Rope would be suitable for frequent text manipulation (e.g. a text editor?).

It's a good point though and I'll have to verify what I'm saying here since string implementation changes from engine to engine. I'll get back to you on this.

Another concern is that rope implementations most probably already exist around and maybe it'd be of more value to contribute with a more exotic data structure, although my experience is limited on those.