No commit activity in last 3 years
No release in over 3 years
A tree structure for Mongoid documents using the materialized path pattern and rational number sorting.
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
 Dependencies

Development

>= 0.9.2
~> 3.0
>= 0.7
~> 0.8

Runtime

>= 0.6
<= 5.0, >= 4.0
 Project Readme

mongoid-tree Build Status Dependency Status Coverage Status

A tree structure for Mongoid documents using rational numbers and materialized path pattern

Requirements

  • mongoid (~> 4.0)

Version 2.x.x supports mongoid 4.x Version 0.1.x supports Mongoid 3.x

Install

To install mongoid_tree_rational, simply add it to your Gemfile:

gem 'mongoid-tree-rational', :require => 'mongoid/tree'

In order to get the latest development version of mongoid-tree:

gem 'mongoid-tree-rational', :git => 'git://github.com/boxcms/mongoid-tree-rational', :require => 'mongoid/tree'

You might want to add :require => nil option and explicitly require 'mongoid/tree' where needed and finally run

bundle install

Usage

class Node
  include Mongoid::Document
  include Mongoid::Tree
  include Mongoid::Tree::RationalNumbering
end

Utility methods

There are several utility methods that help getting to other related documents in the tree:

Node.root
Node.roots
Node.leaves

node.root
node.parent
node.children
node.ancestors
node.ancestors_and_self
node.descendants
node.descendants_and_self
node.siblings
node.siblings_and_self
node.leaves

In addition it's possible to check certain aspects of the document's position in the tree:

node.root?
node.leaf?
node.depth
node.ancestor_of?(other)
node.descendant_of?(other)
node.sibling_of?(other)

See Mongoid::Tree for more information on these methods.

Ordering

Mongoid::Tree doesn't order children by default. To enable ordering of tree nodes include the Mongoid::Tree::RationalNumbering or the Mongoid::Tree::Ordering module.

By rational numbers

To use rational ordering, include the Mongoid::Tree::RationalNumbering module. This will add a position field to your document and provide additional utility methods:

While rational numbering requires more processing when saving, it does give the benefit of querying an entire tree in one query. This is really use

Mathematical details about rational numbers in nested trees can be found here: http://arxiv.org/pdf/0806.3115v1.pdf

node.set_rational_number(nv,dv) # set the nv/dv directly if you have the values
                                # returns true/false + errors if any.
node.lower_siblings
node.higher_siblings
node.first_sibling_in_list
node.last_sibling_in_list
node.siblings_between(other_node)

node.tree # get the entire tree under the node (Triggers 1 query only! Hurray)
node.tree_and_self # # get the entire tree under the node including node

node.move_up
node.move_down
node.move_to_top
node.move_to_bottom
node.move_above(other)
node.move_below(other)

node.at_top?
node.at_bottom?

Example:

class Node
  include Mongoid::Document
  include Mongoid::Tree
  include Mongoid::Tree::RationalNumbering
end

There are one additional class function

Node.rekey_all! # Will iterate over the entire tree and rekey every single node.
                # Please note that this might take a while for a large tree.
                # Do this in a background worker or rake task.
end

Examples on querying trees:

# - node_1
#    - node_1_1
#    - node_1_2
# - node_2
#   - node_2_1
#     - node_2_1_1
#     - node_2_1_2
#   - node_2_2
#     - node_2_2_1
#     - node_2_2_2

Node.all  # Get the entire tree
# -> [node_1, node_1_1, node_1_2, node_2, node_2_1, node_2_1_1, node_2_1_2, node_2_2, node_2_2_1, node_2_2_2]
node_1.tree # Get tree below node 1
# -> [node_1_1, node_1_2]
node_1.tree_and_self # Get tree below node 1 including node_1
# -> [node_1, node_1_1, node_1_2]
node_2.tree # Get tree below node 1 including node_1
# -> [node_2_1, node_2_1_1, node_2_1_2, node_2_2, node_2_2_1, node_2_2_2]
node_2.tree_and_self # Get tree below node 1 including node_1
# -> [node_2, node_2_1, node_2_1_1, node_2_1_2, node_2_2, node_2_2_1, node_2_2_2]
end

See Mongoid::Tree::RationalNumbering for more information on these methods.

By 0-based integer (simple)

To use simple ordering, include the Mongoid::Tree::Ordering module. This will add a position field to your document and provide additional utility methods:

node.lower_siblings
node.higher_siblings
node.first_sibling_in_list
node.last_sibling_in_list

node.move_up
node.move_down
node.move_to_top
node.move_to_bottom
node.move_above(other)
node.move_below(other)

node.at_top?
node.at_bottom?

Example:

class Node
  include Mongoid::Document
  include Mongoid::Tree
  include Mongoid::Tree::Ordering
end

See Mongoid::Tree::Ordering for more information on these methods.

Traversal

It's possible to traverse the tree using different traversal methods using the Mongoid::Tree::Traversal module.

Example:

class Node
  include Mongoid::Document
  include Mongoid::Tree
  include Mongoid::Tree::Traversal
end

node.traverse(:breadth_first) do |n|
  # Do something with Node n
end

Destroying

Mongoid::Tree does not handle destroying of nodes by default. However it provides several strategies that help you to deal with children of deleted documents. You can simply add them as before_destroy callbacks.

Available strategies are:

  • :nullify_children -- Sets the children's parent_id to null
  • :move_children_to_parent -- Moves the children to the current document's parent
  • :destroy_children -- Destroys all children by calling their #destroy method (invokes callbacks)
  • :delete_descendants -- Deletes all descendants using a database query (doesn't invoke callbacks)

Example:

class Node
  include Mongoid::Document
  include Mongoid::Tree

  before_destroy :nullify_children
end

Callbacks

There are two callbacks that are called before and after the rearranging process. This enables you to do additional computations after the documents position in the tree is updated. See Mongoid::Tree for details.

Example:

class Page
  include Mongoid::Document
  include Mongoid::Tree

  after_rearrange :rebuild_path

  field :slug
  field :path

  private

  def rebuild_path
    self.path = self.ancestors_and_self.collect(&:slug).join('/')
  end
end

Validations

Mongoid::Tree currently does not validate the document's children or parent associations by default. To explicitly enable validation for children and parent documents it's required to add a validates_associated validation.

Example:

class Node
  include Mongoid::Document
  include Mongoid::Tree

  validates_associated :parent, :children
end

Timestamps

Per default timestamps are only updated on the a node that is changed, and not siblings that are moved/shifted due to changes on a given node. Usually the tree position of a document does not give information about changes to the content of the document. This behaviour can be changed through the option auto_tree_timestamping .

Disable auto timestamps:

class Node
  include Mongoid::Document
  include Mongoid::Tree
  include Mongoid::Tree::RationalNumbering

  self.auto_tree_timestamping = false

  validates_associated :parent, :children
end

Enable auto timestamps: (default behaviour)

class Node
  include Mongoid::Document
  include Mongoid::Tree
  include Mongoid::Tree::RationalNumbering

  self.auto_tree_timestamping = false

  validates_associated :parent, :children
end

Build Status

mongoid-tree is on tested on Travis CI running the specs against ruby 2.0.0, ruby 2.1.2 and rbx-2

Known issues

See github.com/boxcms/mongoid-tree-rational/issues

Repository

See github.com/boxcms/mongoid-tree-rational and feel free to fork it!

MongoMapper version

Have a look here: github.com/leifcr/mm-tree

Contributors

See a list of all contributors at github.com/boxcms/mongoid-tree-rational/contributors. Thanks!

A huge thanks to Benedikt Deicke for all the work on mongoid-tree. This rational number version is based on his work

Copyright

See LICENSE for details.