Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 257 lines (190 sloc) 14.95 kB
79671c4 @stefankroes Started on rdoc readme
authored
1 = Ancestry
1282d2e @stefankroes Initial commit
authored
2
df705c3 @stefankroes Version 1.1.0 done!
authored
3 Ancestry allows the records of a ActiveRecord model to be organised as a tree structure, using a single, intuitively formatted database column, using a variation on the materialised path pattern. It exposes all the standard tree structure relations (ancestors, parent, root, children, siblings, descendants) and all of them can be fetched in a single sql query. Additional features are named_scopes, integrity checking, integrity restoration, arrangement of (sub)tree into hashes and different strategies for dealing with orphaned records.
1282d2e @stefankroes Initial commit
authored
4
79671c4 @stefankroes Started on rdoc readme
authored
5 = Installation
1282d2e @stefankroes Initial commit
authored
6
7 To apply Ancestry to any ActiveRecord model, follow these simple steps:
8
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
9 1. Install gem
10 - Install gemcutter gem: sudo gem install gemcutter (maybe you need: gem update --system)
11 - Add gemcutter.org as default gem source: gem tumble
d43ece5 @stefankroes Some last changes to the readme
authored
12 - Add to config/environment.rb: config.gem 'ancestry'
13 - Install required gems: sudo rake gems:install
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
14 - Alternatively: sudo gem install ancestry
15 - If you don't want gemcutter: config.gem 'ancestry', :source => 'gemcutter.org'
16 - Alternatively: sudo gem install ancestry --source gemcutter.org
1282d2e @stefankroes Initial commit
authored
17
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
18 2. Add ancestry column to your table
d43ece5 @stefankroes Some last changes to the readme
authored
19 - Create migration: ./script/generate migration add_ancestry_to_[table] ancestry:string
df705c3 @stefankroes Version 1.1.0 done!
authored
20 - Add index to migration: add_index [table], :ancestry (UP) / remove_index [table], :ancestry (DOWN)
d43ece5 @stefankroes Some last changes to the readme
authored
21 - Migrate your database: rake db:migrate
1282d2e @stefankroes Initial commit
authored
22
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
23 3. Add ancestry to your model
d43ece5 @stefankroes Some last changes to the readme
authored
24 - Add to app/models/[model].rb: acts_as_tree
1282d2e @stefankroes Initial commit
authored
25
26 Your model is now a tree!
27
79671c4 @stefankroes Started on rdoc readme
authored
28 = Organising Records Into A Tree
1282d2e @stefankroes Initial commit
authored
29
30 You can use the parent attribute to organise your records into a tree. If you have the id of the record you want to use as a parent and don't want to fetch it, you can also use parent_id. Like any virtual model attributes, parent and parent_id can be set using parent= and parent_id= on a record or by including them in the hash passed to new, create, create!, update_attributes and update_attributes!. For example:
31
95e6701 @stefankroes Updated README
authored
32 TreeNode.create! :name => 'Stinky', :parent => TreeNode.create!(:name => 'Squeeky')
1282d2e @stefankroes Initial commit
authored
33
48d00be @stefankroes Updated readme
authored
34 You can also create children through the children relation on a node:
35
95e6701 @stefankroes Updated README
authored
36 node.children.create :name => 'Stinky'
48d00be @stefankroes Updated readme
authored
37
79671c4 @stefankroes Started on rdoc readme
authored
38 = Navigating Your Tree
1282d2e @stefankroes Initial commit
authored
39
40 To navigate an Ancestry model, use the following methods on any instance / record:
41
df705c3 @stefankroes Version 1.1.0 done!
authored
42 parent Returns the parent of the record, nil for a root node
43 parent_id Returns the id of the parent of the record, nil for a root node
44 root Returns the root of the tree the record is in, self for a root node
45 root_id Returns the id of the root of the tree the record is in
46 is_root? Returns true if the record is a root node, false otherwise
47 ancestor_ids Returns a list of ancestor ids, starting with the root id and ending with the parent id
48 ancestors Scopes the model on ancestors of the record
49 path_ids Returns a list the path ids, starting with the root is and ending with the node's own id
50 path Scopes model on path records of the record
51 children Scopes the model on children of the record
52 child_ids Returns a list of child ids
53 has_children? Returns true if the record has any children, false otherwise
54 is_childless? Returns true is the record has no childen, false otherwise
55 siblings Scopes the model on siblings of the record, the record itself is included
56 sibling_ids Returns a list of sibling ids
57 has_siblings? Returns true if the record's parent has more than one child
58 is_only_child? Returns true if the record is the only child of its parent
59 descendants Scopes the model on direct and indirect children of the record
60 descendant_ids Returns a list of a descendant ids
61 subtree Scopes the model on descendants and itself
62 subtree_ids Returns a list of all ids in the record's subtree
63 depth Return the depth of the node, root nodes are at depth 0
64
65 = acts_as_tree Options
66
67 The acts_as_tree methods supports two options:
68
69 :ancestry_column Pass in a symbol to store ancestry in a different column
70 :orphan_strategy Instruct Ancestry what to do with children of a node that is destroyed:
71 :destroy All children are destroyed as well (default)
72 :rootify The children of the destroyed node become root nodes
73 :restrict An AncestryException is raised if any children exist
74 :cache_depth Cache the depth of each node in the 'ancestry_depth' column (default: false)
75 If you turn depth_caching on for an existing model, use: TreeNode.rebuild_depth_cache!
76 :depth_cache_column Pass in a symbol to store depth cache in a different column
1282d2e @stefankroes Initial commit
authored
77
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
78 = (Named) Scopes
1282d2e @stefankroes Initial commit
authored
79
80 Where possible, the navigation methods return scopes instead of records, this means additional ordering, conditions, limits, etc. can be applied and that the result can be either retrieved, counted or checked for existence. For example:
81
8d2cffb @stefankroes Fixed some problems in the README
authored
82 node.children.exists?(:name => 'Mary')
83 node.subtree.all(:order => :name, :limit => 10).each do; ...; end
84 node.descendants.count
1282d2e @stefankroes Initial commit
authored
85
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
86 For convenience, a couple of named scopes are included at the class level:
1282d2e @stefankroes Initial commit
authored
87
df705c3 @stefankroes Version 1.1.0 done!
authored
88 roots Root nodes
89 ancestors_of(node) Ancestors of node, node can be either a record or an id
90 children_of(node) Children of node, node can be either a record or an id
91 descendants_of(node) Descendants of node, node can be either a record or an id
92 siblings_of(node) Siblings of node, node can be either a record or an id
1282d2e @stefankroes Initial commit
authored
93
22a1984 - Added some tests for node creation through scopes
Stefan Kroes authored
94 Thanks to some convenient rails magic, it is even possible to create nodes through the children and siblings scopes:
95
48d00be @stefankroes Updated readme
authored
96 node.children.create
97 node.siblings.create!
98 TestNode.children_of(node_id).new
99 TestNode.siblings_of(node_id).create
1282d2e @stefankroes Initial commit
authored
100
df705c3 @stefankroes Version 1.1.0 done!
authored
101 = Selecting nodes by depth
1282d2e @stefankroes Initial commit
authored
102
df705c3 @stefankroes Version 1.1.0 done!
authored
103 When depth caching is enabled (see acts_as_tree options), five more named scopes can be used to select nodes on their depth:
1282d2e @stefankroes Initial commit
authored
104
df705c3 @stefankroes Version 1.1.0 done!
authored
105 before_depth(depth) Return nodes that are less deep than depth (node.depth < depth)
106 to_depth(depth) Return nodes up to a certain depth (node.depth <= depth)
107 at_depth(depth) Return nodes that are at depth (node.depth == depth)
108 from_depth(depth) Return nodes starting from a certain depth (node.depth >= depth)
109 after_depth(depth) Return nodes that are deeper than depth (node.depth > depth)
110
111 The depth scopes are also available through calls to descendants, descendant_ids, subtree, subtree_ids, path and ancestors. In this case, depth values are interpreted relatively. Some examples:
112
113 node.subtree(:to_depth => 2) Subtree of node, to a depth of node.depth + 2 (self, children and grandchildren)
114 node.subtree.to_depth(5) Subtree of node to an absolute depth of 5
115 node.descendants(:at_depth => 2) Descendant of node, at depth node.depth + 2 (grandchildren)
116 node.descendants.at_depth(10) Descendants of node at an absolute depth of 10
117 node.ancestors.to_depth(3) The oldest 4 ancestors of node (its root and 3 more)
118 node.path(:from_depth => -2) The node's grandparent, parent and the node itself
119
120 node.ancestors(:from_depth => -6, :to_depth => -4)
121 node.path.from_depth(3).to_depth(4)
122 node.descendants(:from_depth => 2, :to_depth => 4)
123 node.subtree.from_depth(10).to_depth(12)
124
125 Please note that depth constraints cannot be passed to ancestor_ids and path_ids. The reason for this is that both these relations can be fetched directly from the ancestry column without performing a database query. It would require an entirely different method of applying the depth constraints which isn't worth the effort of implementing. You can use ancestors(depth_options).map(&:id) or ancestor_ids.slice(min_depth..max_depth) instead.
1282d2e @stefankroes Initial commit
authored
126
79671c4 @stefankroes Started on rdoc readme
authored
127 = Arrangement
1282d2e @stefankroes Initial commit
authored
128
129 Ancestry can arrange an entire subtree into nested hashes for easy navigation after retrieval from the database. TreeNode.arrange could for example return:
130
8d2cffb @stefankroes Fixed some problems in the README
authored
131 { #<TreeNode id: 100018, name: "Stinky", ancestry: nil>
132 => { #<TreeNode id: 100019, name: "Crunchy", ancestry: "100018">
133 => { #<TreeNode id: 100020, name: "Squeeky", ancestry: "100018/100019">
134 => {}
135 }
1282d2e @stefankroes Initial commit
authored
136 }
137 }
138
139 The arrange method also works on a scoped class, for example:
140
8d2cffb @stefankroes Fixed some problems in the README
authored
141 TreeNode.find_by_name('Crunchy').subtree.arrange
1282d2e @stefankroes Initial commit
authored
142
df705c3 @stefankroes Version 1.1.0 done!
authored
143 = Migrating from plugin that uses parent_id column
144
145 Most current tree plugins use a parent_id column (acts_as_tree, awesome_nested_set, better_nested_set, acts_as_nested_set). With ancestry its easy to migrate from any of these plugins, to do so, follow these steps:
146
147 1. Add ancestry column to your table
148 - Create migration: ./script/generate migration add_ancestry_to_[table] ancestry:string
149 - Add index to migration: add_index [table], :ancestry (UP) / remove_index [table], :ancestry (DOWN)
150 - Migrate your database: rake db:migrate
151
152 2. Remove old tree plugin or gem and add in Ancestry
153 - Remove plugin: rm -Rf vendor/plugins/[old plugin]
154 - Remove gem config line from environment.rb: config.gem [old gem]
155 - Add Ancestry to environment.rb: config.gem :ancestry
156 - See 'Installation' for more info on installing and configuring gems
157
158 3. Change your model
159 - Remove any macros required by old plugin/gem from app/models/[model].rb
160 - Add to app/models/[model].rb: acts_as_tree
161
162 4. Migrate database
163 - In './script.console': [model].build_ancestry_from_parent_ids!
164 - Make sure it worked ok: [model].check_ancestry_integrity!
165
166 5. Change your code
167 - Most tree calls will probably work fine with ancestry
168 - Others must be changed or proxied
169 - Check if all your data is intact and all tests pass
170
171 6. Drop parent_id column:
172 - Create migration: ./script/generate migration remove_parent_id_from_[table]
173 - Add to migration: remove_column [table], :parent_id (UP) / add_column [table], :parent_id, :integer (DOWN)
174 - Migrate your database: rake db:migrate
175
79671c4 @stefankroes Started on rdoc readme
authored
176 = Integrity Checking and Restoration
1282d2e @stefankroes Initial commit
authored
177
df705c3 @stefankroes Version 1.1.0 done!
authored
178 I don't see any way Ancestry tree integrity could get compromised without explicitly setting cyclic parents or invalid ancestry and circumventing validation with update_attribute, if you do, please let me know.
179
180 Ancestry includes some methods for detecting integrity problems and restoring integrity just to be sure. To check integrity use: [Model].check_ancestry_integrity!. An AncestryIntegrityException will be raised if there are any problems. To restore integrity use: [Model].restore_ancestry_integrity!.
1282d2e @stefankroes Initial commit
authored
181
182 For example, from IRB:
183
8d2cffb @stefankroes Fixed some problems in the README
authored
184 >> stinky = TreeNode.create :name => 'Stinky'
d43ece5 @stefankroes Some last changes to the readme
authored
185 $ #<TreeNode id: 1, name: "Stinky", ancestry: nil>
8d2cffb @stefankroes Fixed some problems in the README
authored
186 >> squeeky = TreeNode.create :name => 'Squeeky', :parent => stinky
d43ece5 @stefankroes Some last changes to the readme
authored
187 $ #<TreeNode id: 2, name: "Squeeky", ancestry: "1">
8d2cffb @stefankroes Fixed some problems in the README
authored
188 >> stinky.update_attribute :parent, squeeky
d43ece5 @stefankroes Some last changes to the readme
authored
189 $ true
8d2cffb @stefankroes Fixed some problems in the README
authored
190 >> TreeNode.all
d43ece5 @stefankroes Some last changes to the readme
authored
191 $ [#<TreeNode id: 1, name: "Stinky", ancestry: "1/2">, #<TreeNode id: 2, name: "Squeeky", ancestry: "1/2/1">]
df705c3 @stefankroes Version 1.1.0 done!
authored
192 >> TreeNode.check_ancestry_integrity!
8d2cffb @stefankroes Fixed some problems in the README
authored
193 !! Ancestry::AncestryIntegrityException: Conflicting parent id in node 1: 2 for node 1, expecting nil
df705c3 @stefankroes Version 1.1.0 done!
authored
194 >> TreeNode.restore_ancestry_integrity!
d43ece5 @stefankroes Some last changes to the readme
authored
195 $ [#<TreeNode id: 1, name: "Stinky", ancestry: 2>, #<TreeNode id: 2, name: "Squeeky", ancestry: nil>]
1282d2e @stefankroes Initial commit
authored
196
df705c3 @stefankroes Version 1.1.0 done!
authored
197 Additionally, if you think something is wrong with your depth cache:
198
199 >> TreeNode.rebuild_depth_cache!
1282d2e @stefankroes Initial commit
authored
200
df705c3 @stefankroes Version 1.1.0 done!
authored
201 = Tests
202
203 The Ancestry gem comes with a unit test suite consisting of about 1800 assertions in about 30 tests. It takes about 10 seconds to run on sqlite. To run it yourself, install Ancestry as a plugin into a Rails application, go to the ancestry folder and type 'rake'. The test suite is located in 'test/acts_as_tree_test.rb'.
1282d2e @stefankroes Initial commit
authored
204
79671c4 @stefankroes Started on rdoc readme
authored
205 = Internals
1282d2e @stefankroes Initial commit
authored
206
207 As can be seen in the previous section, Ancestry stores a path from the root to the parent for every node. This is a variation on the materialised path database pattern. It allows Ancestry to fetch any relation (siblings, descendants, etc.) in a single sql query without the complicated algorithms and incomprehensibility associated with left and right values. Additionally, any inserts, deletes and updates only affect nodes within the affected node's own subtree.
208
df705c3 @stefankroes Version 1.1.0 done!
authored
209 In the example above, the ancestry column is created as a string. This puts a limitation on the depth of the tree of about 40 or 50 levels, which I think may be enough for most users. To increase the maximum depth of the tree, increase the size of the string that is being used or change it to a text to remove the limitation entirely. Changing it to a text will however decrease performance because an index cannot be put on the column in that case.
210
211 The materialised path pattern requires Ancestry to use a 'like' condition in order to fetch descendants. This should not be particularly slow however since the the condition never starts with a wildcard which allows the DBMS to use the column index. If you have any data on performance with a large number of records, please drop me line.
212
213 = Version history
214
215 The latest and recommended version of ancestry is 1.1.0. The three numbers of each version numbers are respectively the major, minor and patch versions. We started with major version 1 because it looks so much better and ancestry was already quite mature and complete when it was published. The major version is only bumped when backwards compatibility is broken. The minor version is bumped when new features are added. The patch version is bumped when bugs are fixed.
216
217 - Version 1.1.0 (2009-10-22)
218 - Depth caching (and cache rebuilding)
219 - Depth method for nodes
220 - Named scopes for selecting by depth
221 - Relative depth options for tree navigation methods:
222 - ancestors
223 - path
224 - descendants
225 - descendant_ids
226 - subtree
227 - subtree_ids
228 - Updated README
229 - Easy migration from existing plugins/gems
230 - acts_as_tree checks unknown options
231 - acts_as_tree checks that options are hash
232 - Added a bang (!) to the integrity functions
233 - Since these functions should only be used from ./script/console and not from your appliction, this change is not considered as breaking backwards compatibility and the major version wasn't bumped.
234 - Updated install script to point to documentation
235 - Removed rails specific init
236 - Removed uninstall script
237 - Version 1.0.0 (2009-10-16)
238 - Initial version
239 - Tree building
240 - Tree navigation
241 - Integrity checking / restoration
242 - Arrangement
243 - Orphan strategies
244 - Subtree movement
245 - Named scopes
246 - Validations
1282d2e @stefankroes Initial commit
authored
247
79671c4 @stefankroes Started on rdoc readme
authored
248 = Future Work
1282d2e @stefankroes Initial commit
authored
249
df705c3 @stefankroes Version 1.1.0 done!
authored
250 I will try to keep Ancestry up to date with changing versions of Rails and Ruby and also with any bug reports I might receive. I will implement new features on request as I see fit. One thing I definitely want to do soon is some proper performance testing.
1282d2e @stefankroes Initial commit
authored
251
df705c3 @stefankroes Version 1.1.0 done!
authored
252 = Contact and Copyright
1282d2e @stefankroes Initial commit
authored
253
df705c3 @stefankroes Version 1.1.0 done!
authored
254 Question? Bug report? Faulty/incomplete documentation? Feature request? Please post an issue on 'http://github.com/stefankroes/ancestry/issues'. Please also contact me at s.a.kroes[at]gmail.com if it's urgent.
1282d2e @stefankroes Initial commit
authored
255
256 Copyright (c) 2009 Stefan Kroes, released under the MIT license
Something went wrong with that request. Please try again.