Introduction

Thank you Nicolas for letting me borrow your blog to talk about my work.

I would like to present hierarchy, an Emacs library to create, query, navigate and display hierarchies. This library can be used to manipulate any kind of hierarchy. For example, a developer can use it with file hierarchies (see the file-system example)

img

JSON documents (see the json-navigator project),

img

or class hierarchies (see the klassified prototype project)

img

As you can see, there are multiple ways to display a given hierarchy: as a tree widget (as shown above for the file hierarchy and JSON document), as a tabulated list (as shown above for the class hierarchy) or as plain text as shown below:

animal
  bird
    dove
    pigeon
  cow
  dolphin

A hierarchy is a set of items with a parent-child relationship. A hierarchy has at least one root, an item with no parent, and can have more than one (contrary to a tree which has one and only one root). An item of a hierarchy can be anything distinguishable with the equal function. Siblings are items with the same parent.

In the following we explore some parts of the library’s API so you can start using it in your own project right away.

Creation

There are two main ways to create a new hierarchy: either through functions describing the parent-child relationship or through a nested list.

Creation from functions

To create a hierarchy from functions, you can write something like that:

(require 'hierarchy)
    
(setq animals (hierarchy-new))
    
(let ((parentfn
       ;; Given an item, return its parent
       (lambda (item)
         (cl-case item
           (dove 'bird)
           (pigeon 'bird)
           (bird 'animal)
           (dolphin 'animal)
           (cow 'animal)))))
  (hierarchy-add-tree animals 'dove parentfn)
  (hierarchy-add-tree animals 'pigeon parentfn)
  (hierarchy-add-tree animals 'dolphin parentfn)
  (hierarchy-add-tree animals 'cow parentfn))
    
(hierarchy-sort animals) ;; sort siblings with #'string<

This creates the animal hierarchy shown above. The hierarchy-add-tree function takes a hierarchy to add to as first parameter, then an item to add and then a function to get the parent of the item (and the parent of the parent, recursively). This creates a hierarchy bottom-up.

It is also possible to create a hierarchy top-down by passing a fourth argument to hierarchy-add-tree in this way:

(setq animals2 (hierarchy-new))
    
(let ((childrenfn
       ;; Given an item, return its children
       (lambda (item)
         (cl-case item
           (animal '(bird cow dolphin))
           (bird '(pigeon dove))))))
  (hierarchy-add-tree animals2 'animal nil childrenfn))
    
(hierarchy-sort animals2)

At this point, animals and animals2 represent the same hierarchy as can be verified with hierarchy-equal:

(if (hierarchy-equal animals animals2)
    "The two hierarchies are equal"
  "The two hierarchies are not equal")
  
The two hierarchies are equal

Creation from a nested list

The second way to build a hierarchy is to start from a nested list:

(setq animals3
      (hierarchy-from-list '(animal (bird (dove) (pigeon)) (cow) (dolphin))))

In this case, the nodes in the resulting hierarchy are not symbols as in hierarchy and hierarchy2 above, but sub-lists:

(with-temp-buffer
  (hierarchy-print animals3)
  (buffer-substring-no-properties (point-min) (point-max)))

(animal (bird (dove) (pigeon)) (cow) (dolphin))
  (dolphin)
  (cow)
  (bird (dove) (pigeon))
    (pigeon)
    (dove)

Each line of the text above shows an item indented depending on its depth in the hierarchy (i.e., the number of parents before reaching a root).

You can pass an optional argument to hierarchy-print if you want to only print the car of each sub-list:

(with-temp-buffer
  (hierarchy-print animals3 (lambda (list) (symbol-name (car list))))
  (buffer-substring-no-properties (point-min) (point-max)))
animal
  dolphin
  cow
  bird
    pigeon
    dove

It is also possible to create a new hierarchy from an existing one. For example, to create a hierarchy from animals3 that looks like animals and animals2 :

(let ((animals3-new
       (hierarchy-map-hierarchy
        (lambda (item _indent) (car item))
        animals3)))
  (if (hierarchy-equal animals animals3-new)
      "The two hierarchies are equal"
    "The two hierarchies are not equal"))

The two hierarchies are equal

The hierarchy-map-hierarchy function takes a transformation function as first argument and a source hierarchy as second one. The transformation function will receive an item and its indentation level in the source hierarchy and must produce an item for the resulting hierarchy.

Querying

The hierarchy API provides its fair share of functions to query a hierarchy.

The functions hierarchy-items, hierarchy-roots and hierarchy-leafs return lists of items in the hierarchy. The first function returns all items, the second one only returns items with no parent and the third one returns items with no children:

(list
 (hierarchy-items animals)
 (hierarchy-roots animals)
 (hierarchy-leafs animals))

((dove bird animal pigeon dolphin cow)
 (animal)
 (dove pigeon dolphin cow))

There are also some predicate functions (returning a boolean) such as hierarchy-has-item, hierarchy-empty-p, hierarchy-equal, hierarchy-child-p and hierarchy-descendant-p.

There are several ways to iterate over items of a hierarchy. The simplest function is hierarchy-map which returns a list of the result of applying a function to each item. For example, to get a list of items and their depths in the hierarchy, you can write:

(hierarchy-map #'list animals)

((animal 0)
 (bird 1)
 (dove 2)
 (pigeon 2)
 (cow 1)
 (dolphin 1))

This function walks the hierarchy from the roots to the leafs. It is also possible to walk the hierarchy from the leafs to a root using hierarchy-map-tree. As additional bonus, the result of applying the function to children of an item is passed as a parameter when the function is called on the item itself:

(hierarchy-map-tree #'list animals)

(animal 0
	((bird 1
	       ((dove 2 nil)
		(pigeon 2 nil)))
	 (cow 1 nil)
	 (dolphin 1 nil)))

We have already seen the function hierarchy-map-hierarchy that builds and returns a hierarchy from an existing one by applying a function on each item (just like mapcar does it for lists).

Display

Finally, hierarchies can be displayed in many different ways. We have already seen hierarchy-print which formats a hierarchy as text in the current buffer. The functions hierarchy-tabulated-display and hierarchy-tree-display are respectively responsible for displaying a hierarchy as a list of elements and as a tree (as can be seen in the beginning of this article). For example, to display our hierarchy of animals:

(switch-to-buffer (hierarchy-tabulated-display
                   animals
                   (lambda (item indent)
                     (insert (symbol-name item)))))

img

The functions responsible for displaying a hierarchy take a function as parameter whose name is labelfn. This name indicates that the function should take two parameters (an item of a hierarchy and an indentation level) and insert some text in the current buffer. The hierarchy API provides several functions to help you build a labelfn function. For example, if you want your animal hierarchy printed with indentation and clickable labels, you can write something like that:

(switch-to-buffer (hierarchy-tabulated-display
                   animals
                   (hierarchy-labelfn-indent
                    (hierarchy-labelfn-button
                     (lambda (item indent)
                       (insert (symbol-name item)))
                     (lambda (item indent)
                       (message "You clicked on: %s" item))))))

img

Conclusion

The hierarchy library features an easy to use API to create, query, navigate and display any kind of hierarchy. This library has already been used to display hierarchies of files and classes as well as to navigate JSON structures. All functions are well documented and tested.

Have fun playing with the library.