Ranked trees
Compatible with Clojurescript.
Feel free to clone this repo, the examples below located are in the dvlopt.rktree.example namespace. See the "Development" section at the end of this document.
Usage
A ranked tree
is a peculiar but interesting data structure. It is a form of
nested maps where leaves are located both in time and space. It comes in handy
for problems that needs some form of prioritization.
More specifically, it is a complex of nested maps where former levels are sorted and latter levels are unsorted.
Following this definition, the following qualifies as a ranked tree
:
(def my-tree
(sorted-map 0 (sorted-map 1 {:a {:b 'leaf-1}})
5 {:a {:d {:e 'leaf-2}}}))
Each leaf has two paths, one "horizontal" and one "vertical" (borrowing
vocabulary from the litterature). We shall rather talk (respectively) about
ranks
providing a notion of time and a path
providing a notion of space.
Thus, 'leaf-1
is said to be located at [:a :b]
and ranked at [0 1]
.
Similarly, 'leaf-2
is said to be located at [:c :d :e]
and ranked at [5]
.
We specify both the ranks
and the path
when we want to get
something out
of this tree:
(require '[dvlopt.rktree :as rktree])
(= 'leaf-1
(rktree/get my-tree
[0 1]
[:a :b]))
Ranks provid prioritization, a lower rank meaning a higher priority, 0 being the
highest priority. When we pop
the tree, we receive whatever resides at the
ranks with the highest priority. More precisely, we receive [popped-tree ranks unsorted-node]
:
(= (rktree/pop my-tree)
[(sorted-map 5 {:a {:d {:e 'leaf-2}}})
[0 1]
{:a {:b 'leaf-1}}])
Interestingly, as you might have noticed, different leaves can have ranks of
different length. This library handles that automagically. Remember we already
have 'leaf-1
located at [:a :b]
and ranked at [0 1]
. What if we assoc
something past those ranks?
(def my-tree-2
(rktree/assoc my-tree
[0 1 0 0 0 5]
[:possible?]
true))
;; Notice that 'leaf has been re-prioritized from [0 1] to [0 1 0 0 0 0].
;; Order is actually maintained as before, but we can account for the new
;; addition above.
(= 'leaf-1
(rktree/get my-tree-2
[0 1 0 0 0 0]
[:a :b]))
;; But notice that we can still use the original ranks!
(= 'leaf-1
(rktree/get my-tree-2
[0 1]
[:a :b]))
We have discovered a few recognizable functions such as assoc
and get
. The
API provide other ones (dissoc
,
update
, and friends), all acting on this idea of having ranks
and a path
.
Serialization
Some serializers make a distinction between sorted maps and unsorted ones. For instance, Nippy does.
But Transit does not.
The user can add the following dependency along side Transit-clj or Transit-cljs:
This package provides a read handler and a write handler for sorted maps:
(require '[dvlopt.rktree.transit :as rktree.transit])
rktree.transit/read-handler
rktree.transit/write-handler
Running tests
On the JVM, using Kaocha:
$ ./bin/test/jvm/run
$ ./bin/test/jvm/watch
On NodeJS, using Kaocha-CLJS:
$ ./bin/test/node/run
$ ./bin/test/node/watch
In the browser, using Chui:
$ ./bin/test/browser/compile
# Then open ./resources/chui/index.html
# For testing an advanced build
$ ./bin/test/browser/advanced
Development
Starting in Clojure JVM mode, mentioning an additional deps alias (here, a local setup of NREPL):
$ ./bin/dev/clojure :nrepl
Starting in CLJS mode using Shadow-CLJS:
$ ./bin/dev/cljs
# Then open ./resources/public/index.html
License
Copyright © 2020 Adam Helinski
Licensed under the term of the Mozilla Public License 2.0, see LICENSE.