A Zipper data structure for JavaScript DOM trees and other tree-like
structures.

Danny Yoo (dyoo@hashcollision.org)


This library provides a functional interface to traverse and
manipulate trees, using G\'erard Huet's Zipper data structure.  See:
http://en.wikipedia.org/wiki/Zipper_(data_structure)


Usage:



You can create a cursor into the DOM with this:

    var cursor = TreeCursor.domToCursor(document.body)

or a cursor into a tree whose structure uses nested arrays, with this:

    var cursor = TreeCursor.arrayToCursor([['this'], 'is', 'a', [['test']]])

TreeCursor provides a raw interface to adapt an arbitrary tree
structure to a cursor, described at the end of this document.



The node at the cursor can be found with:

    cursor.node: node
    The node that's currently being focused.



The cursor implements the following functions:

    cursor.down: -> cursor
    Move the cursor down to the first child.

    cursor.up: -> cursor
    Move the cursor up to the parent.

    cursor.left: -> cursor
    Move the cursor to the previous sibling.

    cursor.right: -> cursor
    Move the cursor to the next sibling.

    cursor.succ: -> cursor
    Move the cursor to the successor.

    cursor.pred: -> cursor
    Move the cursor to the predecessor. 

    cursor.top: -> cursor
    Jump to the topmost node in the tree.


succ() and pred() are defined in terms of preorder traversal.



The cursor also provides predicates to make sure the motion is legal:

    cursor.canDown: -> boolean
    Returns true if the node is non-atomic and has children.

    cursor.canUp: -> boolean
    Returns true if the node has a parent.

    cursor.canLeft: -> boolean
    Returns true if the node has a previous sibling.

    cursor.canRight: -> boolean
    Returns true if the node as a next sibling.

    cursor.canSucc: -> boolean
    Returns true if the node has a successor.

    cursor.canPred: -> boolean
    Returns true if the node has a predecessor.


and operations to make changes to the structure of the tree:

    cursor.replaceNode: node -> cursor
    Change the node at the cursor.

    cursor.insertDown: node -> cursor
    Insert an element as the first child at focus.  Focus
    moves to the inserted node.

    cursor.insertRight: node -> cursor
    Insert an element as the next sibling.  Focus moves to the inserted node.

    cursor.insertLeft: node -> cursor
    Insert an element as the previous sibling.  Focus moves to the inserted node.

    cursor.deleteNode: -> cursor
    Delete the element at the current cursor.  Focus moves to the right
    if possible.  If that's not possible, tries focusing to the left.
    Otherwise, moves up when neither are possible.


----------------------------------------------------------------------


Raw interface:

TreeCursor.adaptTreeCursor: [node Node] 
                            [openF (Node -> (arrayof Node))]
                            [closeF (Node (arrayof Node) -> Node)]
                            [atomicF (Node -> boolean)]
                            -> cursor

Creates a cursor that can traverse the structure of the given node.

openF and closeF are functions that teach the cursor how to sink and
rise through the structure of a node.

atomicF tell TreeCursor if the node should be considered one that can
be dived into.

As an example, the TreeCursor implementation has a function
TreeCursor.arrayToCursor to walk deeply nested JavaScript structures,
with arrays.  It only dives into arrays, and all other values are treated
atomically.


----------------------------------------------------------------------

Test cases are in tests.js, and are invoked by visiting index.html.