Immutable TreeUtils

0.1.6

This CommonJS module is a collection of helpers to access and traverse ImmutableJS tree data structure with a DOM-inspired interface.

It is written in ES2015, the ES5/ES3 distribution is built with Babel.

It imposes some very basic conventions on your data structure, but I tried to make everything as low-level and configurable as possible. Still, a few conditions that need to be met remain:

• A tree can have only one root node.
• Every node has to provide a unique identifier value under a key that is the same for all nodes in the tree.
• Child nodes have to be stored in an List under a key that is the the same for all nodes containing children.

Getting started

You probably should feel comfortable working with ImmutableJS data structures, so if you don't I strongly recommend you to get familiar with the concepts of ImmutableJS first.

Understanding key paths

As you already know, with ImmutableJS we retrieve nested values like this:

let map = Immutable.Map({a: { b: 'c' }});
map.getIn(['a', 'b']);
// 'c'

We could say that the key path to the value 'c' is ['a', 'b']. Instead of an array you can also use Seq objects to describe key paths:

map.getIn(Immutable.Seq.of('a', 'b'));
// 'c'

This might feel a little over the top at first but comes with a few advantages that are pivotal to TreeUtils. As a matter of fact, all the functions in this lib, that give you a node or a collection of nodes don't return the actual ImmutableJS values but the key paths to the substate where the resulting node(s) are located. A lot of operations become very trivial with key paths. Let's look at the parent function. Determining the parent of a given node represented by a key path is as simple as this:

let nodePath = Immutable.Seq.of('data', 'childNodes', 0, 'childNodes', 1);
let parentPath = nodePath.skipLast(2);

The actual retrieval of the ImmutableJS values is left to you, but you will notice that working with key paths can be quite fun. Imagine you want to get value at key content of the next sibling of a given node. You could do this like so:

let keyPath = treeUtils.nextSibling(state, 'node-id');
let content = state.getIn(keyPath.concat('content'));

// or even shorter
let content = state.getIn(treeUtils.nextSibling(state, 'node-id').concat('name'));

Please note, that while ImmutableJS works well with Arrays as key paths, TreeUtils will only accept Seq objects as valid key paths.

Working with cursors

TreeUtils works just fine with cursor libraries like contrib/cursor or immutable-cursors, because cursors actually implement ImmutableJS interfaces.

Tree mutation

TreeUtils doesn't provide mutation helpers, because IMHO the varietiy of use cases and implementations ist just too huge to spec a sensible API for that kind of thing. However, simple mutation functions can easily be implemented. An insert function could look something like this:

function insert(state, newNode, parentId, index) {
	return state.updateIn(
		tree.getById(state, parentId).concat('childNodes'),
		childNodes => childNodes.splice(index, 0, newNode)
	);
}

Install and setup

Install the package from npm:

npm install immutable-treeutils

Note: This library relies on ES6 generators so you need either an environment that supports them or to include some polyfill like regenerator or babel's polyfill before importing immutable-treeutils;

Import the module and provide some state. Examples in the docs below refer to this data structure:

import Immutable from 'immutable';
import TreeUtils from 'immutable-treeutils';

let treeUtils = new TreeUtils();

let data = Immutable.fromJS({
	id: 'root',
	name: 'My Documents',
	type: 'folder'
	childNodes: [
		{
			id: 'node-1',
			name: 'Pictures',
			type: 'folder',
			childNodes: [
				{
					id: 'node-2',
					name: 'Me in Paris',
					type: 'image'
				},
				{
					id: 'node-3',
					name: 'Barbecue July 2015',
					type: 'image'
				}
			]
		},
		{
			id: 'node-4',
			name: 'Music',
			type: 'folder',
			childNodes: [
				{
					id: 'node-5',
					name: 'Pink Floyd - Wish You Were Here',
					type: 'audio'
				},
				{
					id: 'node-6',
					name: 'The Doors - People Are Strange',
					type: 'audio'
				}
			]
		}
	]
});

API Docs

---

_{See Source}

---

class TreeUtils

A collection of functional tree traversal helper functions for ImmutableJS data structures.

Example

const treeUtils = new TreeUtils(Immutable.Seq.of('path', 'to', 'tree'));

With custom key accessors

const treeUtils = new TreeUtils(Immutable.Seq.of('path', 'to', 'tree'), '__id', '__children');

Note The first argument of every method of a TreeUtils object is the state you want to analyse. I won't mention / explain it again in method descriptions bellow. The argument idOrKeyPath also appears in most signatures, its purpose is thoroughly explained in the docs of byArbitrary.

Signature:

new TreeUtils(
   rootPath?: immutable.Seq,
   idKey?: string,
   childNodesKey?: string
)

Arguments:

• rootPath - The path to the substate of your ImmutableJS state that represents the root node of your tree. Default: Immutable.Seq().
• idKey - The name of the key that points at unique identifiers of all nodes in your tree . Default: 'id'.
• childNodesKey - The name of the key at which child nodes can be found. Default: 'childNodes'.

Returns:

• A new TreeUtils object

---

method id()

Returns the id for the node at keyPath. Most useful when you want to get the id of the result of a previous tree query:

treeUtils.id(state, treeUtils.parent(state, 'node-3'));
// 'node-1'

Signature:

id(
   state: Immutable.Iterable,
   keyPath: Immutable.Seq<string|number>
): string

Arguments:

• keyPath - The absolute key path to the substate / node whose id you want to retrieve

Returns:

The unique identifier of the node at the given key path.

---

method nodes()

An iterator of all nodes in the tree.

for(var nodePath of treeUtils.nodes(state)) {
   console.log(treeUtils.id(state, nodePath));
}

Signature:

nodes(
    state: Immutable.Iterable,
    path?: Immutable.Seq<string|number>
): Iterator

Arguments:

• path - The key path that points at the root of the (sub)tree whose descendants you want to iterate. Default: The TreeUtils object's rootPath.

Returns:

An unordered Iterator of all nodes in the tree.

---

method find()

Returns the key path to the first node for which compatator returns true. Uses nodes internally and as nodes is an unordered Iterator, you should probably use this to find unique occurences of data.

treeUtils.find(state, node => node.get('name') === 'Me in Paris');
// Seq ["childNodes", 0, "childNodes", 0]

Signature:

find(
   state: Immutable.Iterable,
   comparator: (
        node: Immutable.Iterable, 
        keyPath: Immutable.Seq<string|number>
    ): boolean,
   path?: Immutable.Seq<string|number>
): Immutable.Seq<string|number>

Arguments:

• comparator - A function that gets passed a node and a keyPath and should return whether it fits the criteria or not.
• path? - An optional key path to the (sub)state you want to analyse: Default: The TreeUtils object's rootPath.

Returns:

The key path to the first node for which comparator returned true.

---

method filter()

Returns an List of key paths pointing at the nodes for which comparator returned true.

treeUtils.filter(state, node => node.get('type') === 'folder');
//List [ Seq[], Seq["childNodes", 0], Seq["childNodes", 1] ]

Signature:

filter(
    state: Immutable.Iterable,
    comparator: (
        node: Immutable.Iterable, 
        keyPath: Immutable.Seq<string|number>
    ): boolean,
    path?: Immutable.Seq<string|number>
): List<Immutable.Seq<string|number>>

Arguments:

• comparator - A function that gets passed a node and a keyPath and should return whether it fits the criteria or not.
• path? - An optional key path to the (sub)state you want to analyse: Default: The TreeUtils object's rootPath.

Returns:

A List of all the key paths that point at nodes for which comparator returned true.

---

method byId()

Returns the key path to the node with id === id.

Signature:

id(
   state: Immutable.Iterable,
   id: string
): Immutable.Seq<string|number>

Arguments:

• id - A unique identifier

Returns:

The key path to the node with id === id.

---

method byArbitrary()

Returns idOrKeyPath if it is a Seq, else returns the result of byId for idOrKeyPath. This is used in all other functions that work on a unique identifiers in order to reduce the number of lookup operations.

Signature:

byArbitrary(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.Seq<string|number>

Returns:

The key path pointing at the node found for id === idOrKeyPath or, if is a Seq, the idOrKeyPath itself.

---

method nextSibling()

Signature:

nextSibling(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.Seq<string|number>

Returns:

Returns the next sibling node of the node at idOrKeyPath

---

method previousSibling()

Signature:

previousSibling(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.Seq<string|number>

Returns:

Returns the previous sibling node of the node at idOrKeyPath

---

method firstChild()

Signature:

firstChild(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.Seq<string|number>

Returns:

Returns the first child node of the node at idOrKeyPath

---

method lastChild()

Signature:

lastChild(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.Seq<string|number>

Returns:

Returns the last child node of the node at idOrKeyPath

---

method siblings()

Signature:

siblings(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.List<Immutable.Seq<string|number>>

Returns:

Returns a List of key paths pointing at the sibling nodes of the node at idOrKeyPath

---

method childNodes()

Signature:

childNodes(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>
): Immutable.List<Immutable.Seq<string|number>>

Returns:

Returns a List of all child nodes of the node at idOrKeyPath

---

method childAt()

Signature:

childAt(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
   index: number
): Immutable.Seq<string|number>

Returns:

Returns the child node at position of index of the node at idOrKeyPath

---

method descendants()

Signature:

descendants(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): Immutable.List<Immutable.Seq<string|number>>

Returns:

Returns a list of key paths pointing at all descendants of the node at idOrKeyPath

---

method childIndex()

Signature:

childIndex(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): number

Returns:

Returns the index at which the node at idOrKeyPath is positioned in its parent child nodes list.

---

method hasChildNodes()

Signature:

hasChildNodes(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): boolean

Returns:

Returns whether the node at idOrKeyPath has children.

---

method numChildNodes()

Signature:

numChildNodes(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): number

Returns:

Returns the number of child nodes the node at idOrKeyPath has.

---

method parent()

Signature:

parent(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): Immutable.Seq<string|number>

Returns:

Returns the key path to the parent of the node at idOrKeyPath.

---

method ancestors()

Signature:

ancestors(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): Immutable.Seq<string|number>

Returns:

Returns an List of all key paths that point at direct ancestors of the node at idOrKeyPath.

---

method position()

This method is a very naive attempt to calculate a unqiue numeric position descriptor that can be used to compare two nodes for their absolute position in the tree.

treeUtils.position(state, 'node-4') > treeUtils.position(state, 'node-3');
// true

Please note that position should not get used to do any comparison with the root node.

Signature:

position(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): number

Returns:

Returns a unique numeric value that represents the absolute position of the node at idOrKeyPath.

---

method right()

Returns the key path to the next node to the right. The next right node is either:

• The first child node.
• The next sibling.
• The next sibling of the first ancestor that in fact has a next sibling.
• undefined

let nodePath = treeUtils.byId(state, 'root');
while (nodePath) {
   console.log(nodePath);
   nodePath = treeUtils.right(state, nodePath);
}
// 'root'
// 'node-1'
// 'node-2'
// 'node-3'
// 'node-4'
// 'node-5'
// 'node-6'

Signature:

right(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): Immutable.Seq<string|number>

Returns:

Returns the key path to the node to the right of the one at idOrKeyPath.

---

method left()

Returns the key path to the next node to the left. The next left node is either:

• The last descendant of the previous sibling node.
• The previous sibling node.
• The parent node.
• undefined

let nodePath = treeUtils.lastDescendant(state, 'root');
while (nodePath) {
   console.log(nodePath);
   nodePath = treeUtils.left(state, nodePath);
}
// 'node-6'
// 'node-5'
// 'node-4'
// 'node-3'
// 'node-2'
// 'node-1'
// 'root'

Signature:

left(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): Immutable.Seq<string|number>

Returns:

Returns the key path to the node to the right of the one at idOrKeyPath.

---

method firstDescendant()

Alias of firstChild.

---

method lastDescendant()

Returns the key path to the most right node in the given subtree (keypath). The last child of the most deep descendant, if that makes any sense. Look at the example:

treeUtils.lastDescendant(state, 'root');
// 'node-6'

Signature:

lastDescendant(
   state: Immutable.Iterable,
   idOrKeyPath: string|Immutable.Seq<string|number>,
): Immutable.Seq<string|number>

Returns:

Returns the key path to the last descendant of the node at idOrKeyPath.

Development

Get the source:

git clone https://github.com/lukasbuenger/immutable-cursors

Install dependencies:

npm install

Lint the code:

npm run lint

Run the tests:

npm test

Build ES5/ES3:

npm run build

Build the docs / README:

npm run docs

Update all local dependencies:

npm run update-dependencies

## Changelog

0.1.6

• Dependencies updated.
• Docs: Fix typos and source links.

0.1.5

• Dependencies updated.
• All methods that need to evaluate whether a value exists or not check not only for undefined but for null as well now. Some methods were broken if you e.g. were using null as default value on Record definitions, which by some people is considered best practise.

0.1.4

• Dependencies updated. Added tests for the transpiled source (trivial).

0.1.3

• Minor fixes in API docs. Updated dependencies.

0.1.2

• Migration to Babel 6 courtesy of Kei Takashima.
• README hint to use environment with generators enabled courtesy of Emanuele Ingrosso.
• Further updated dependencies, most notably ImmutableJS.
• Added estraverse-fb to devDependencies (eslint/eslint#5476).

License

See LICENSE file.