Creating a IPersistentSet compatible Binary Tree in Clojure
Following on from my article on Binary Search Trees last week, I decided to see how I could use types and interfaces to implement the glue that is required to make the Binary Tree implementation compatible with the
In doing so, this would allow any library or function requiring an
IPersistentSet to use the Binary Tree data-structure.
At the end of the previous article we were left with a handful of useful functions which worked with the Binary Search Tree data-structure we had developed. For a recap, below are the definitions for each of the functions.
Implementing the IPersistentSet interface
In the code laid out below we are providing a wrapper around the functions that we have already developed - for the contract that is needed to become a
Creating a new type called
BinaryTree which holds a root tree node, allows us to easily handle the use-case of an empty set, along with logical proxying to the existing functions.
We are now able to supply a
BinaryTree in any place that desires a
IPersistentSet compatible type.
When the function is invoked Clojure polymorphically dispatches to the correct types function implementation.