FastTree

Fast and Intuitive tree structure using nested sets model.

Add this line to your application's Gemfile:

gem 'fast_tree'

And then execute:

$ bundle

Or install it yourself as:

$ gem install fast_tree

fast_tree provides a generator which adds left and right pointers used in nested sets model to your model class. Even if you have created a target class or not, execute following commands in your terminal:

$ bin/rails g fast_tree YOUR_MODEL_NAME

and, execute migration by bundle exec rake db:migrate.

After that, add the following line into your model:

include FastTree::Model

It seems like:

class YOUR_MODEL_NAME < ApplicationRecord
  include FastTree::Model

  ...
end

Finally, you can use several methods as class methods and instance methods.

If you are interested in how it works, see the section "How It Works" below.

To initialize tree structure, do the following:

attributes = { name: "root node" }
YOUR_MODEL_NAME.create_tree(attributes)

To create a new leaf under a node,

node = YOUR_MODEL_NAME.first

attributes = { name: "root node" }
node.create_child(attributes)

or, to add existed node to another,

node = YOUR_MODEL_NAME.first

new_node = YOUR_MODEL_NAME.second
node.add_child(new_node)

To create a new parent over a node,

node = YOUR_MODEL_NAME.first

attributes = { name: "root node" }
YOUR_MODEL_NAME.create_parent(attributes, [node])

or, to add existed node to another,

node = YOUR_MODEL_NAME.first

parent = YOUR_MODEL_NAME.second
YOUR_MODEL_NAME.add_parent(parent, [node])

You can add/create a parent over several nodes:

children = YOUR_MODEL_NAME.take(3)
parent = YOUR_MODEL_NAME.last
YOUR_MODEL_NAME.add_parent(parent, children)

NOTE: this method has a issue: #6

To remove a node reconstructing the tree,

node = YOUR_MODEL_NAME.take
node.remove

If you don't want to reconstruct the tree after deleting a node, do the following:

node = YOUR_MODEL_NAME.take
node.destroy

To copy a subtree under a node,

root_of_subtree = YOUR_MODEL_NAME.first
target = YOUR_MODEL_NAME.second

root_of_subtree.copy_to(targe)

To move a subtree under a node,

root_of_subtree = YOUR_MODEL_NAME.first
target = YOUR_MODEL_NAME.second

root_of_subtree.move_to(targe)

To get the root node from the tree,

root = YOUR_MODEL_NAME.find_root

To get subtree from a root node,

# root can be any node in the tree
root = YOUR_MODEL_NAME.take
root.subtree.each do |node|
  # do something
end

NOTE: subtree method returns ActiveRelation, so that you can use each, map or anything you want!

In fast_tree, several tree-traverse algorithms, such as DFS and BFS, are provided.

To get nodes by DFS,

root = YOUR_MODEL_NAME.take
root.subtree.dfs.each do |node|
  # do something
end

To get nodes by BFS,

root = YOUR_MODEL_NAME.take
root.subtree.bfs.each do |node|
  # do something
end

To get a parent node,

node = YOUR_MODEL_NAME.take
node.parent

or child nodes,

node = YOUR_MODEL_NAME.take
node.children

fast_tree provides several boolean methods, such as:

• root?
• leaf?
• has_children?

, as instance methods.

The migration file will create a migration file, such as:

class AddFastTreeToTestTrees < ActiveRecord::Migration[5.0]
  def self.up
    change_table :test_trees do |t|
      ## Pointers
      t.integer :l_ptr
      t.integer :r_ptr
      t.integer :depth

    end

    add_index :test_trees, :l_ptr
    add_index :test_trees, :r_ptr
    add_index :test_trees, :depth
  end

  def self.down
    # model already existed. Please edit below which fields you would like to remove in this migration.
  end
end

, but you don't have to care what l_ptr and r_ptr are: tree operations are executed in methods such as create_child or remove.

1. Fork it
2. Create your feature branch (git checkout -b my-new-feature)
3. Commit your changes (git commit -am 'Add some feature')
4. Push to the branch (git push origin my-new-feature)
5. Create new Pull Request

The gem is available as open source under the terms of the MIT License.