toybox
Various data-structures and other toys implemented in Mojo🔥.
https://github.com/dimitrilw/toybox
Current toys:
- DisjointSet
- Heap (priority queue)
➡️ PRs are welcome, so long as you are patient with me. ⬅️
🐰 ❤️
GitHub
GitHub - dimitrilw/toybox: Various data-structures and other toys i...
Various data-structures and other toys implemented in Mojo🔥. - dimitrilw/toybox
7 Replies
Added basic binary heap.
Of note: the heap can take any
List[HeapableCollectionElement]. A HeapableCollectionElement is any CollectionElement with a __lt__ dunder-method, so if you make your lt be a gt under-the-hood, then you have a Max Heap. The file test/test_heap.mojo demonstrates a custom struct to create a Max Heap.
For that matter, using a custom struct with a custom __lt__, you can create complex heap-sorting logic, too. The same test/test_heap.mojo contains an example of a struct with three attributes: a (an Int), b (an Int), and s (a String). The sort logic is simple: sort by a first, then if a is tied, sort by b; s has no role in sorting. By creating a heap with a custom struct as your HeapableCollectionElement, you can engineer some complex Priority Queues.A friend asked me if this structure would allow a Heap of Heaps. I said yes. He said prove it. Challenge accepted.
I added a file
test/test_heap_of_heaps__LOL.mojo.
Don't judge me. 😂
One more post:
I plan to make a few more common-use data-structures, like a double-ended priority-queue (aka "depq") and a few trie/tree structures (probably a Prefix Tree, Patricia Tree, and maybe an Adaptive Radix Tree). Does anybody have requests for other structures? Like maybe somebody out there wants to make SomeCoolThing for Mojo, but is missing a specific data-structure that would help their project along. Anything you need that would enable you to build SomeCoolThing for Mojo?
The example of using a heap for Dijkstra's shortest path algo works now.
https://github.com/dimitrilw/toybox/blob/main/test/test_heap_example_dijkstra_shortest_path.mojo
A few months back I looked into Judy Array, but decided life is too short 😄. But it would be definitely an interesting experiment to compare it against different implementations of HashMap. And there is also HAMT (used in Clojure), main feature is, it’s a persistent Dictionary. There is an implementation in C as well https://github.com/mkirchner/hamt
GitHub
GitHub - mkirchner/hamt: A hash array-mapped trie implementation in C
A hash array-mapped trie implementation in C. Contribute to mkirchner/hamt development by creating an account on GitHub.
Interesting. I've never heard of HAMT, nor used it for any personal work. But, I'm going to give it a look, too. ...adding to my wishlist. Ty, Maxim. ❤️
Re "life is too short": I sorta feel that way about implementing an Adaptive Radix Tree. 😂 I've used them before, but in the context of
import ART (easy) and not actually implementing it (not as easy).
But, I'd sure like to have ART in Mojo. I don't know that I'll ever have a need for one, but if I've used it before, then I'm sure somebody else here will need it someday to implement something else cool in Mojo. 🤷♂️
@Clean Cock , pinging you in here so you are in this Forum Post, toosure
@bunny Ok the weekend has come and i got a few spare hours at evnings. I'll be happy to help somehow with toybox. Is there anything specific you want me to do?
also shold I spam this channel?
Already been DM'ing CC, but figured I'd post for all:
I'd like to apologize for my absence from Mojo (and Discord in general) over the last two weeks -- my daughter has medical issues (not sharing details; it's her story, not mine), and the last two weeks have been nothing but scrambling to get work done while also taking her to medical appointments hours away from our house. So all other stuff (including all Discord) sort of fell to the side.