An ecto based Nested set model implementation for database
Add as_nested_set to your list of dependencies in mix.exs:
# use the stable version
def deps do
[{:as_nested_set, "~> 3.1"}]
end
# use the latest version
def deps do
[{:as_nested_set, github: "https://github.com/secretworry/as_nested_set.git"}]
end
To make use of as_nested_set your model has to have at least 4 fields: id, lft, rgt and parent_id. The name of those fields are configurable.
defmodule AsNestedSet.TestRepo.Migrations.MigrateAll do
use Ecto.Migration
def change do
create table(:taxons) do
add :name, :string
add :taxonomy_id, :id
add :parent_id, :id
add :lft, :integer
add :rgt, :integer
timestamps
end
end
endEnable the nested set functionality by use AsNestedSet on your model
defmodule AsNestedSet.Taxon do
use AsNestedSet, scope: [:taxonomy_id]
# ...
endYou can config the name of required field through attributes:
defmodule AsNestedSet.Taxon do
@right_column :right
@left_column :left
@node_id_column :node_id
@parent_id_column :pid
# ...
end@right_column: column name for right boundary (default tolft, since left is a reserved keyword for Mysql)@left_column: column name for left boundary (default torgt, reserved too)@node_id_column: specifies the name for the node id column (default toid, i.e. the id of the model, change this if you want to have a different id, or you id field is different)@parent_id_column: specifies the name for the parent id column (default toparent_id)
You can also pass following to modify its behavior:
defmodule AsNestedSet.Taxon do
use AsNestedSet, scope: [:taxonomy_id]
# ...
endscope: (optional) a list of column names which restrict what is to be considered within the same tree(same scope). When ignored, all the nodes will be considered under the same tree.
Once you have set up you model, you can then
Add a new node
target = Repo.find!(Taxon, 1)
# add to left
%Taxon{name: "left", taxonomy_id: 1} |> AsNestedSet.create(target, :left) |> AsNestedSet.execute(TestRepo)
# add to right
%Taxon{name: "right", taxonomy_id: 1} |> AsNestedSet.create(target, :right) |> AsNestedSet.execute(TestRepo)
# add as first child
%Taxon{name: "child", taxonomy_id: 1} |> AsNestedSet.create(target, :child) |> AsNestedSet.execute(TestRepo)
# add as parent
%Taxon{name: "parent", taxonomy_id: 1} |> AsNestedSet.create(target, :parent) |> AsNestedSet.execute(TestRepo)
# add as root
%Taxon{name: "root", taxonomy_id: 1} |> AsNestedSet.create(:root) |> AsNestedSet.execute(TestRepo)
# move a node to a new position
node |> AsNestedSet.move(:root) |> AsNestedSet.execute(TestRepo) // move the node to be a new root
node |> AsNestedSet.move(target, :left) |> AsNestedSet.execute(TestRepo) // move the node to the left of the target
node |> AsNestedSet.move(target, :right) |> AsNestedSet.execute(TestRepo) // move the node to the right of the target
node |> AsNestedSet.move(target, :child) |> AsNestedSet.execute(TestRepo) // move the node to be the right-most child of targetRemove a specified node and all its descendants
target = Repo.find!(Taxon, 1)
AsNestedSet.remove(target) |> AsNestedSet.execute(TestRepo)Query different nodes
# find all roots
AsNestedSet.roots(Taxon, %{taxonomy_id: 1}) |> AsNestedSet.execute(TestRepo)
# find all children of target
AsNestedSet.children(target) |> AsNestedSet.execute(TestRepo)
# find all the leaves for given scope
AsNestedSet.leaves(Taxon, %{taxonomy_id: 1}) |> AsNestedSet.execute(TestRepo)
# find all descendants
AsNestedSet.descendants(target) |> AsNestedSet.execute(TestRepo)
# include self
AsNestedSet.self_and_descendants(target) |> AsNestedSet.execute(TestRepo)
# find all ancestors
AsNestedSet.ancestors(target) |> AsNestedSet.execute(TestRepo)
#find all siblings (self included)
AsNestedSet.self_and_siblings(target) |> AsNestedSet.execute(TestRepo)Traverse the tree
# traverse a tree with 3 args post callback
AsNestedSet.traverse(Taxon, %{taxonomy_id}, context, fn node, context -> {node, context}, end, fn node, children, context -> {node, context} end) |> AsNestedSet.execute(TestRepo)
# traverse a tree with 2 args post callback
AsNestedSet.traverse(Taxon, %{taxonomy_id}, context, fn node, context -> {node, context}, end, fn node, context -> {node, context} end) |> AsNestedSet.execute(TestRepo)
# traverse a subtree with 3 args post callback
AsNestedSet.traverse(target, context, fn node, context -> {node, context}, end, fn node, children, context -> {node, context} end) |> AsNestedSet.execute(TestRepo)
# traverse a tree with 2 args post callback
AsNestedSet.traverse(target, context, fn node, context -> {node, context}, end, fn node, context -> {node, context} end) |> AsNestedSet.execute(TestRepo)We recommend users to use a transaction to wrap all the operations in the production environment
We introduced the @type executable( a delayed execution ) as return value of each API, so using transaction or not and how granular the transaction should be are all up to users.
In general, almost all modifications of a nested set can be done in one SQL, but we can't express some of them using ecto's DSL( ecto doesn't support case-when in update query ), so users having concurrent modifications must wrap AsNestedSet.execute(call, repo) in a Transaction, for example
exec = node |> AsNestedSet.move(:root)
Repo.transaction fn -> AsNestedSet.execute(exec, Repo) endThe node passed in as an argument might has changed after loaded from db, we will reload it from DB before use it, so there is no need to wrap the load and the execute in the same transaction
# This is not necessary
Repo.transaction fn ->
node = loadNode()
node |> AsNestedSet.move(:root) |> AsNestedSet.execute(Repo) # We will reload the node passed in
endBut if you want to ensure consistency across multiple executes , to avoid the racing condition, you have to isolate them by wrap them in different transaction.
Be default, after using AsNestedSet.move(node, target, :child), you move the node to be the right-most child of the target, because we can know the left and right of the target right way, but to find out the proper right and left for n-th child requires more operations.
To achieve the goal, you should:
- Query the n-th child or (n-1)th child of the target by
AsNestedSet.children(target), - Use
move(node, n_th_child, :left)andmove(node, n_1_th_child, :right)respectively.
Ecto is upgrading to 3.x. If you are using Ecto 3.x, please use branch ecto-3.0 (Thanks for @nicholasjhenry)
- Thanks Travis CI for providing free and convenient integration test
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent