Skip to content
This repository has been archived by the owner on Aug 14, 2024. It is now read-only.
/ tree_delta Public archive

Calculates the minimum set of operations that transform one tree into another.

Notifications You must be signed in to change notification settings

whichdigital/tree_delta

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

43 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Tree Delta

Build Status

Calculates the minimum set of operations that transform one tree into another.

Overview

Let's say we have the following ordered trees:

                             alpha               beta
                             /   \               /  \
                            a     b             a    e
                           / \     \           / \
                          c   d     e         d   c

You can transform the 'alpha' tree into the 'beta' tree through a combination of operations:

create - adds a node to the tree
update - changes the attributes of a node
delete - removes a node from the tree
detach - orphan a node from its parent
attach - give a node a new parent

Here are the operations for the above example:

detach 'e'
detach 'd'
detach 'a'
delete 'alpha'
create 'beta' as root
attach 'a' to 'beta' at position 0
attach 'd' to 'a' at position 0
attach 'e' to 'beta' at position 1

The order of these operations is somewhat important. For example, node 'a' can only be attached to 'beta' after 'beta' has been created.

Updates are not shown here. An 'update' operation is used to make changes to the value object for a node. This is where you'd store the node's attributes.

Usage

You must first define a node class with the following methods:

#identity
Returns an identifier that uniquely identifies the node across trees.

#parent
Returns the parent of the node.

#children
Returns an array of child nodes.

#value
Returns the value object associated with the node.

You can then use your node class to create separate trees:

alpha = Node.new("alpha", children: [
  Node.new("a", children: [
    Node.new("c"),
    Node.new("d")
  ]),
  Node.new("b", children: [
    Node.new("e")
  ])
])

beta = Node.new("beta", children: [
  Node.new("a", children: [
    Node.new("d"),
    Node.new("c")
  ]),
  Node.new("e")
])

Finally, you can instantiate a delta from the roots of the trees:

delta = TreeDelta.new(from: alpha, to: beta)

delta.each do |operation|
  # ...
end

Operation

An operation is a simple object that describes a transformation.

It can contain up to five pieces of information, as shown here:

type identity value parent position
create
update
delete
detach
attach

Here is an example:

operation.type
#=> :create

operation.identity
#=> "foo"

operation.value
#=> 123

operation.parent
#=> "bar"

operation.position
#=> 3

The 'value' is the value object for the node. This can be a literal value or an object, such as a hash of attributes.

The 'position' refers to the node's index position relative to its siblings, starting at zero.

The 'parent' will be nil if the node is the root of the tree.

Assumptions

  • The delta assumes that deletions cascade down to subtrees under a node. It will not yield operations to delete descendants of a node.

  • The delta assumes that positions for siblings are updated when a node is created or attached. Any sibling to the right of the node should have its position incremented by one.

  • The delta assumes that positions for siblings are updated when a node is deleted or detached. Any sibling to the right of the node should have its position decremented by one.

Contribution

If you'd like to contribute, please open an issue or submit a pull request.

About

Calculates the minimum set of operations that transform one tree into another.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages