Primus2\Falcraft: New Data Type (leaf)

Many times in while programming you want to have a hierarchy of objects.  A hierarchy can very easily be realized as a ‘tree’ of parent elements and child elements.  This is not the only way to imagine a hierarchy, but for this post it is a good example.

Parents and Children

The idea behind a ‘tree’ is the very basic relationship between a ‘parent’ and ‘children’.  In a standard tree there is one parent, and multiple children.  In the example below there is the element ‘parent1’ whose children are ‘child1’, ‘child2’, and ‘child3’.


Now, the greatest part of this abstraction is that you can set ‘parents’ to be ‘children’ of other ‘parents’.  So, setting ‘parent1’, as a child of ‘parent2’ gives us the following diagram:


With this, you can start to construct a whole ‘tree’.  The tree in this metaphor is actually depicted backwards here and in many literature on data structures.  It might be more apt to call it a ‘root’ structure, but that term is usually set aside for the single starting base parent at the ‘bottom’ of the tree.

One aspect that is encapsulated in this data structure, as we’ll see, is that a child can have multiple parents:


The idea behind a ‘leaf’ data structure, to me, is to provide a means in which a tree can be traversed quickly and without much overhead.  I eliminated a bit of functionality to achieve this, making it much more difficult to go ‘up’ the tree as opposed to going down, however that was on purpose.

Let’s take a look at the basic starting foundation for a leaf data type, the interface.

The Leaf Interface

A brief overview of Falcraft\Data\Types\Resource\LeafInterface (GitHub) shows us:

We can see in this construction that there are methods for adding, retrieving, and removing leaves, but not one for getting the parent or siblings of the leaf.  I left that functionality for another data structure that is much more capable in building mappable trees, the UnorderedNode (GitHub) [post].

It’s really a very basic set interface, with ‘isLeaf’ testing whether the given leaf exists.

Note that the leaves have to be identified in some form or fashion.  Each leaf is expected to be identifiable in one form or another.  This could be implemented by a Map, or another associative array, including the built in array (object).  As you will see in our further implementation we utilized a RestrictedList to form our tree.

So, let’s implement the leaf in Falcraft\Data\Types\Resource\AbstractLeaf (GitHub):

As you can see, one of the confusing parts about leaves here is that there are 2 identifiers for them: the identifier of the leaf itself, and the identifier that the leaf is going by in its parent leaf.  These can be different.  This is not a bug, but a ‘feature’, if you will.

The part missing above is the constructor function for the leaf.  It’s a bit complex, which is why all those files are required, but we’ll cover it here.

First we start out establishing default configuration and setting up the configuration object ( $->conf ), as done in the Configuration Trait:

The default is that we don’t supply an identifier and use the identity generated by the Identity Trait with the default prefix ‘Leaf’.  ‘Strict’ tells us whether we want to keep a close eye on the errors of things.

We move on to establishing the identity generated by the Identity Trait:

It’s important to note here in the constructor that the identity of the leaf is ‘lazily set’.  That is, it’s not set until a piece of programming requests it.  This means that when a leaf instantiates it doesn’t necessarily increment the identity counter, but rather when it is polled for its identity does it do so.

Finally we get to the meat of the constructor, the instantiation of our children leaves:

With an abstract leaf you can only attach objects that implement LeafInterface to a particular leaf.  These may be different objects, linked only by their interface, so beware that a tree may have a plurality of objects in it, not just one.  We construct the leaf restrictions, check the incoming array, and then construct the RestrictedList (that only accepts the interface).

The Leaf Data Type

Finally we have the final implementation of the leaf that we can use to encapsulate data (not interface, not abstract):

Simple enough.  Note here that not only can different disparate data be stored in the $->data property, but you can also define alternate objects that implement the LeafInterface and stick those as objects in the tree hierarchy.  And remember, a leaf’s identifier inside a leaf may be different than the identifier used to refer to it.  You cannot gaurantee three things when using this data structure: that the leaf will have a unique identifier, that a tree will have only homogenous objects, and that data pointed to a link will be of the same type across the board.  However, that’s by design, for maximum functionality.

photo credit: Leaves Carpet a Sidewalk via photopin (license)


I'm just a wunk, trying to enjoy life. I am a cofounder of http// and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: