List of datastructures and algorithms to implement - Githubissues

jenspots / libwheel

Generic data structures for the C programming language with (near) zero overhead.

GNU Affero General Public License v3.0

8 stars 0 forks source link

List of datastructures and algorithms to implement #1

Open jenspots opened 1 year ago

jenspots commented 1 year ago

This list is a continuous work of progress.

Structures

Smart Pointers

[x] Reference Counter rc
- While useful, this data structure will require manual freeing. However, it allows to have multiple references to a single block of memory. For example, reading a value from an list which also contains rc values.

Associative Arrays

[ ] Extendible Hashing Table eht
[ ] Linear Hashing Table lht
[ ] ~~Ternary Trie ttrie~~
[ ] ~~Array Trie atrie~~
[x] Ternary trie with path compression trie

Priority Queues
[ ] Biniomial Heap bh

Lists

[ ] Dequeue dq
[ ] Stack stack
- This is currently implemented, but inefficiently relies on vec. Perhaps this can be implemented in a more focused manner.

Trees

[ ] B+ trees bplus
[ ] AVL trees avl
[ ] Semi-Splay trees sst

jenspots commented 1 year ago

The trie data structure has been implemented. For now, I think it's redundant to have multiple versions. There is a theoretical threshold at which it is more economical to switch from a Patricia trie to a binary-tree-based trie, but this also introduces a lot of complexity. The current implementation used binary trees with path compression, without rebalancing.