@@ -1,744 +1,748 | |||
|
1 | 1 | module CollectiveIdea #:nodoc: |
|
2 | 2 | module Acts #:nodoc: |
|
3 | 3 | module NestedSet #:nodoc: |
|
4 | 4 | |
|
5 | 5 | # This acts provides Nested Set functionality. Nested Set is a smart way to implement |
|
6 | 6 | # an _ordered_ tree, with the added feature that you can select the children and all of their |
|
7 | 7 | # descendants with a single query. The drawback is that insertion or move need some complex |
|
8 | 8 | # sql queries. But everything is done here by this module! |
|
9 | 9 | # |
|
10 | 10 | # Nested sets are appropriate each time you want either an orderd tree (menus, |
|
11 | 11 | # commercial categories) or an efficient way of querying big trees (threaded posts). |
|
12 | 12 | # |
|
13 | 13 | # == API |
|
14 | 14 | # |
|
15 | 15 | # Methods names are aligned with acts_as_tree as much as possible to make replacment from one |
|
16 | 16 | # by another easier. |
|
17 | 17 | # |
|
18 | 18 | # item.children.create(:name => "child1") |
|
19 | 19 | # |
|
20 | 20 | |
|
21 | 21 | # Configuration options are: |
|
22 | 22 | # |
|
23 | 23 | # * +:parent_column+ - specifies the column name to use for keeping the position integer (default: parent_id) |
|
24 | 24 | # * +:left_column+ - column name for left boundry data, default "lft" |
|
25 | 25 | # * +:right_column+ - column name for right boundry data, default "rgt" |
|
26 | 26 | # * +:depth_column+ - column name for the depth data, default "depth" |
|
27 | 27 | # * +:scope+ - restricts what is to be considered a list. Given a symbol, it'll attach "_id" |
|
28 | 28 | # (if it hasn't been already) and use that as the foreign key restriction. You |
|
29 | 29 | # can also pass an array to scope by multiple attributes. |
|
30 | 30 | # Example: <tt>acts_as_nested_set :scope => [:notable_id, :notable_type]</tt> |
|
31 | 31 | # * +:dependent+ - behavior for cascading destroy. If set to :destroy, all the |
|
32 | 32 | # child objects are destroyed alongside this object by calling their destroy |
|
33 | 33 | # method. If set to :delete_all (default), all the child objects are deleted |
|
34 | 34 | # without calling their destroy method. |
|
35 | 35 | # * +:counter_cache+ adds a counter cache for the number of children. |
|
36 | 36 | # defaults to false. |
|
37 | 37 | # Example: <tt>acts_as_nested_set :counter_cache => :children_count</tt> |
|
38 | 38 | # * +:order_column+ on which column to do sorting, by default it is the left_column_name |
|
39 | 39 | # Example: <tt>acts_as_nested_set :order_column => :position</tt> |
|
40 | 40 | # |
|
41 | 41 | # See CollectiveIdea::Acts::NestedSet::Model::ClassMethods for a list of class methods and |
|
42 | 42 | # CollectiveIdea::Acts::NestedSet::Model for a list of instance methods added |
|
43 | 43 | # to acts_as_nested_set models |
|
44 | 44 | def acts_as_nested_set(options = {}) |
|
45 | 45 | options = { |
|
46 | 46 | :parent_column => 'parent_id', |
|
47 | 47 | :left_column => 'lft', |
|
48 | 48 | :right_column => 'rgt', |
|
49 | 49 | :depth_column => 'depth', |
|
50 | 50 | :dependent => :delete_all, # or :destroy |
|
51 | 51 | :polymorphic => false, |
|
52 | 52 | :counter_cache => false |
|
53 | 53 | }.merge(options) |
|
54 | 54 | |
|
55 | 55 | if options[:scope].is_a?(Symbol) && options[:scope].to_s !~ /_id$/ |
|
56 | 56 | options[:scope] = "#{options[:scope]}_id".intern |
|
57 | 57 | end |
|
58 | 58 | |
|
59 | 59 | class_attribute :acts_as_nested_set_options |
|
60 | 60 | self.acts_as_nested_set_options = options |
|
61 | 61 | |
|
62 | 62 | include CollectiveIdea::Acts::NestedSet::Model |
|
63 | 63 | include Columns |
|
64 | 64 | extend Columns |
|
65 | 65 | |
|
66 | 66 | belongs_to :parent, :class_name => self.base_class.to_s, |
|
67 | 67 | :foreign_key => parent_column_name, |
|
68 | 68 | :counter_cache => options[:counter_cache], |
|
69 | 69 | :inverse_of => (:children unless options[:polymorphic]), |
|
70 | 70 | :polymorphic => options[:polymorphic] |
|
71 | 71 | |
|
72 | 72 | has_many_children_options = { |
|
73 | 73 | :class_name => self.base_class.to_s, |
|
74 | 74 | :foreign_key => parent_column_name, |
|
75 | 75 | :order => order_column, |
|
76 | 76 | :inverse_of => (:parent unless options[:polymorphic]), |
|
77 | 77 | } |
|
78 | 78 | |
|
79 | 79 | # Add callbacks, if they were supplied.. otherwise, we don't want them. |
|
80 | 80 | [:before_add, :after_add, :before_remove, :after_remove].each do |ar_callback| |
|
81 | 81 | has_many_children_options.update(ar_callback => options[ar_callback]) if options[ar_callback] |
|
82 | 82 | end |
|
83 | 83 | |
|
84 | 84 | has_many :children, has_many_children_options |
|
85 | 85 | |
|
86 | 86 | attr_accessor :skip_before_destroy |
|
87 | 87 | |
|
88 | 88 | before_create :set_default_left_and_right |
|
89 | 89 | before_save :store_new_parent |
|
90 | 90 | after_save :move_to_new_parent, :set_depth! |
|
91 | 91 | before_destroy :destroy_descendants |
|
92 | 92 | |
|
93 | 93 | # no assignment to structure fields |
|
94 | 94 | [left_column_name, right_column_name, depth_column_name].each do |column| |
|
95 | 95 | module_eval <<-"end_eval", __FILE__, __LINE__ |
|
96 | 96 | def #{column}=(x) |
|
97 | 97 | raise ActiveRecord::ActiveRecordError, "Unauthorized assignment to #{column}: it's an internal field handled by acts_as_nested_set code, use move_to_* methods instead." |
|
98 | 98 | end |
|
99 | 99 | end_eval |
|
100 | 100 | end |
|
101 | 101 | |
|
102 | 102 | define_model_callbacks :move |
|
103 | 103 | end |
|
104 | 104 | |
|
105 | 105 | module Model |
|
106 | 106 | extend ActiveSupport::Concern |
|
107 | 107 | |
|
108 | 108 | included do |
|
109 | 109 | delegate :quoted_table_name, :to => self |
|
110 | 110 | end |
|
111 | 111 | |
|
112 | 112 | module ClassMethods |
|
113 | 113 | # Returns the first root |
|
114 | 114 | def root |
|
115 | 115 | roots.first |
|
116 | 116 | end |
|
117 | 117 | |
|
118 | 118 | def roots |
|
119 | 119 | where(parent_column_name => nil).order(quoted_left_column_full_name) |
|
120 | 120 | end |
|
121 | 121 | |
|
122 | 122 | def leaves |
|
123 | 123 | where("#{quoted_right_column_full_name} - #{quoted_left_column_full_name} = 1").order(quoted_left_column_full_name) |
|
124 | 124 | end |
|
125 | 125 | |
|
126 | 126 | def valid? |
|
127 | 127 | left_and_rights_valid? && no_duplicates_for_columns? && all_roots_valid? |
|
128 | 128 | end |
|
129 | 129 | |
|
130 | 130 | def left_and_rights_valid? |
|
131 | 131 | ## AS clause not supported in Oracle in FROM clause for aliasing table name |
|
132 | 132 | joins("LEFT OUTER JOIN #{quoted_table_name}" + |
|
133 | 133 | (connection.adapter_name.match(/Oracle/).nil? ? " AS " : " ") + |
|
134 | 134 | "parent ON " + |
|
135 | 135 | "#{quoted_parent_column_full_name} = parent.#{primary_key}"). |
|
136 | 136 | where( |
|
137 | 137 | "#{quoted_left_column_full_name} IS NULL OR " + |
|
138 | 138 | "#{quoted_right_column_full_name} IS NULL OR " + |
|
139 | 139 | "#{quoted_left_column_full_name} >= " + |
|
140 | 140 | "#{quoted_right_column_full_name} OR " + |
|
141 | 141 | "(#{quoted_parent_column_full_name} IS NOT NULL AND " + |
|
142 | 142 | "(#{quoted_left_column_full_name} <= parent.#{quoted_left_column_name} OR " + |
|
143 | 143 | "#{quoted_right_column_full_name} >= parent.#{quoted_right_column_name}))" |
|
144 | 144 | ).count == 0 |
|
145 | 145 | end |
|
146 | 146 | |
|
147 | 147 | def no_duplicates_for_columns? |
|
148 | 148 | scope_string = Array(acts_as_nested_set_options[:scope]).map do |c| |
|
149 | 149 | connection.quote_column_name(c) |
|
150 | 150 | end.push(nil).join(", ") |
|
151 | 151 | [quoted_left_column_full_name, quoted_right_column_full_name].all? do |column| |
|
152 | 152 | # No duplicates |
|
153 | 153 | select("#{scope_string}#{column}, COUNT(#{column})"). |
|
154 | 154 | group("#{scope_string}#{column}"). |
|
155 | 155 | having("COUNT(#{column}) > 1"). |
|
156 | 156 | first.nil? |
|
157 | 157 | end |
|
158 | 158 | end |
|
159 | 159 | |
|
160 | 160 | # Wrapper for each_root_valid? that can deal with scope. |
|
161 | 161 | def all_roots_valid? |
|
162 | 162 | if acts_as_nested_set_options[:scope] |
|
163 | 163 | roots.group_by {|record| scope_column_names.collect {|col| record.send(col.to_sym) } }.all? do |scope, grouped_roots| |
|
164 | 164 | each_root_valid?(grouped_roots) |
|
165 | 165 | end |
|
166 | 166 | else |
|
167 | 167 | each_root_valid?(roots) |
|
168 | 168 | end |
|
169 | 169 | end |
|
170 | 170 | |
|
171 | 171 | def each_root_valid?(roots_to_validate) |
|
172 | 172 | left = right = 0 |
|
173 | 173 | roots_to_validate.all? do |root| |
|
174 | 174 | (root.left > left && root.right > right).tap do |
|
175 | 175 | left = root.left |
|
176 | 176 | right = root.right |
|
177 | 177 | end |
|
178 | 178 | end |
|
179 | 179 | end |
|
180 | 180 | |
|
181 | 181 | # Rebuilds the left & rights if unset or invalid. |
|
182 | 182 | # Also very useful for converting from acts_as_tree. |
|
183 | 183 | def rebuild!(validate_nodes = true) |
|
184 | 184 | # Don't rebuild a valid tree. |
|
185 | 185 | return true if valid? |
|
186 | 186 | |
|
187 | 187 | scope = lambda{|node|} |
|
188 | 188 | if acts_as_nested_set_options[:scope] |
|
189 | 189 | scope = lambda{|node| |
|
190 | 190 | scope_column_names.inject(""){|str, column_name| |
|
191 | 191 | str << "AND #{connection.quote_column_name(column_name)} = #{connection.quote(node.send(column_name.to_sym))} " |
|
192 | 192 | } |
|
193 | 193 | } |
|
194 | 194 | end |
|
195 | 195 | indices = {} |
|
196 | 196 | |
|
197 | 197 | set_left_and_rights = lambda do |node| |
|
198 | 198 | # set left |
|
199 | 199 | node[left_column_name] = indices[scope.call(node)] += 1 |
|
200 | 200 | # find |
|
201 | where(["#{quoted_parent_column_full_name} = ? #{scope.call(node)}", node]).order("#{quoted_left_column_full_name}, #{quoted_right_column_full_name}, id").each{|n| set_left_and_rights.call(n) } | |
|
201 | where(["#{quoted_parent_column_name} = ? #{scope.call(node)}", node]). | |
|
202 | order(acts_as_nested_set_options[:order]). | |
|
203 | each{|n| set_left_and_rights.call(n) } | |
|
202 | 204 | # set right |
|
203 | 205 | node[right_column_name] = indices[scope.call(node)] += 1 |
|
204 | 206 | node.save!(:validate => validate_nodes) |
|
205 | 207 | end |
|
206 | 208 | |
|
207 | 209 | # Find root node(s) |
|
208 | root_nodes = where("#{quoted_parent_column_full_name} IS NULL").order("#{quoted_left_column_full_name}, #{quoted_right_column_full_name}, id").each do |root_node| | |
|
210 | root_nodes = where("#{quoted_parent_column_name} IS NULL"). | |
|
211 | order(acts_as_nested_set_options[:order]).each do |root_node| | |
|
209 | 212 | # setup index for this scope |
|
210 | 213 | indices[scope.call(root_node)] ||= 0 |
|
211 | 214 | set_left_and_rights.call(root_node) |
|
212 | 215 | end |
|
213 | 216 | end |
|
214 | 217 | |
|
215 | 218 | # Iterates over tree elements and determines the current level in the tree. |
|
216 | 219 | # Only accepts default ordering, odering by an other column than lft |
|
217 | 220 | # does not work. This method is much more efficent than calling level |
|
218 | 221 | # because it doesn't require any additional database queries. |
|
219 | 222 | # |
|
220 | 223 | # Example: |
|
221 | 224 | # Category.each_with_level(Category.root.self_and_descendants) do |o, level| |
|
222 | 225 | # |
|
223 | 226 | def each_with_level(objects) |
|
224 | 227 | path = [nil] |
|
225 | 228 | objects.each do |o| |
|
226 | 229 | if o.parent_id != path.last |
|
227 | 230 | # we are on a new level, did we descend or ascend? |
|
228 | 231 | if path.include?(o.parent_id) |
|
229 | 232 | # remove wrong wrong tailing paths elements |
|
230 | 233 | path.pop while path.last != o.parent_id |
|
231 | 234 | else |
|
232 | 235 | path << o.parent_id |
|
233 | 236 | end |
|
234 | 237 | end |
|
235 | 238 | yield(o, path.length - 1) |
|
236 | 239 | end |
|
237 | 240 | end |
|
238 | 241 | |
|
239 | 242 | # Same as each_with_level - Accepts a string as a second argument to sort the list |
|
240 | 243 | # Example: |
|
241 | 244 | # Category.each_with_level(Category.root.self_and_descendants, :sort_by_this_column) do |o, level| |
|
242 | 245 | def sorted_each_with_level(objects, order) |
|
243 | 246 | path = [nil] |
|
244 | 247 | children = [] |
|
245 | 248 | objects.each do |o| |
|
246 | 249 | children << o if o.leaf? |
|
247 | 250 | if o.parent_id != path.last |
|
248 | 251 | if !children.empty? && !o.leaf? |
|
249 | 252 | children.sort_by! &order |
|
250 | 253 | children.each { |c| yield(c, path.length-1) } |
|
251 | 254 | children = [] |
|
252 | 255 | end |
|
253 | 256 | # we are on a new level, did we decent or ascent? |
|
254 | 257 | if path.include?(o.parent_id) |
|
255 | 258 | # remove wrong wrong tailing paths elements |
|
256 | 259 | path.pop while path.last != o.parent_id |
|
257 | 260 | else |
|
258 | 261 | path << o.parent_id |
|
259 | 262 | end |
|
260 | 263 | end |
|
261 | 264 | yield(o,path.length-1) if !o.leaf? |
|
262 | 265 | end |
|
263 | 266 | if !children.empty? |
|
264 | 267 | children.sort_by! &order |
|
265 | 268 | children.each { |c| yield(c, path.length-1) } |
|
266 | 269 | end |
|
267 | 270 | end |
|
268 | 271 | |
|
269 | 272 | def associate_parents(objects) |
|
270 | 273 | if objects.all?{|o| o.respond_to?(:association)} |
|
271 | 274 | id_indexed = objects.index_by(&:id) |
|
272 | 275 | objects.each do |object| |
|
273 | 276 | if !(association = object.association(:parent)).loaded? && (parent = id_indexed[object.parent_id]) |
|
274 | 277 | association.target = parent |
|
275 | 278 | association.set_inverse_instance(parent) |
|
276 | 279 | end |
|
277 | 280 | end |
|
278 | 281 | else |
|
279 | 282 | objects |
|
280 | 283 | end |
|
281 | 284 | end |
|
282 | 285 | end |
|
283 | 286 | |
|
284 | 287 | # Any instance method that returns a collection makes use of Rails 2.1's named_scope (which is bundled for Rails 2.0), so it can be treated as a finder. |
|
285 | 288 | # |
|
286 | 289 | # category.self_and_descendants.count |
|
287 | 290 | # category.ancestors.find(:all, :conditions => "name like '%foo%'") |
|
288 | 291 | # Value of the parent column |
|
289 | 292 | def parent_id |
|
290 | 293 | self[parent_column_name] |
|
291 | 294 | end |
|
292 | 295 | |
|
293 | 296 | # Value of the left column |
|
294 | 297 | def left |
|
295 | 298 | self[left_column_name] |
|
296 | 299 | end |
|
297 | 300 | |
|
298 | 301 | # Value of the right column |
|
299 | 302 | def right |
|
300 | 303 | self[right_column_name] |
|
301 | 304 | end |
|
302 | 305 | |
|
303 | 306 | # Returns true if this is a root node. |
|
304 | 307 | def root? |
|
305 | 308 | parent_id.nil? |
|
306 | 309 | end |
|
307 | 310 | |
|
308 | 311 | # Returns true if this is the end of a branch. |
|
309 | 312 | def leaf? |
|
310 | persisted? && right.to_i - left.to_i == 1 | |
|
313 | new_record? || (persisted? && right.to_i - left.to_i == 1) | |
|
311 | 314 | end |
|
312 | 315 | |
|
313 | 316 | # Returns true is this is a child node |
|
314 | 317 | def child? |
|
315 | 318 | !root? |
|
316 | 319 | end |
|
317 | 320 | |
|
318 | 321 | # Returns root |
|
319 | 322 | def root |
|
320 | 323 | if persisted? |
|
321 | 324 | self_and_ancestors.where(parent_column_name => nil).first |
|
322 | 325 | else |
|
323 | 326 | if parent_id && current_parent = nested_set_scope.find(parent_id) |
|
324 | 327 | current_parent.root |
|
325 | 328 | else |
|
326 | 329 | self |
|
327 | 330 | end |
|
328 | 331 | end |
|
329 | 332 | end |
|
330 | 333 | |
|
331 | 334 | # Returns the array of all parents and self |
|
332 | 335 | def self_and_ancestors |
|
333 | 336 | nested_set_scope.where([ |
|
334 | 337 | "#{quoted_left_column_full_name} <= ? AND #{quoted_right_column_full_name} >= ?", left, right |
|
335 | 338 | ]) |
|
336 | 339 | end |
|
337 | 340 | |
|
338 | 341 | # Returns an array of all parents |
|
339 | 342 | def ancestors |
|
340 | 343 | without_self self_and_ancestors |
|
341 | 344 | end |
|
342 | 345 | |
|
343 | 346 | # Returns the array of all children of the parent, including self |
|
344 | 347 | def self_and_siblings |
|
345 | 348 | nested_set_scope.where(parent_column_name => parent_id) |
|
346 | 349 | end |
|
347 | 350 | |
|
348 | 351 | # Returns the array of all children of the parent, except self |
|
349 | 352 | def siblings |
|
350 | 353 | without_self self_and_siblings |
|
351 | 354 | end |
|
352 | 355 | |
|
353 | 356 | # Returns a set of all of its nested children which do not have children |
|
354 | 357 | def leaves |
|
355 | 358 | descendants.where("#{quoted_right_column_full_name} - #{quoted_left_column_full_name} = 1") |
|
356 | 359 | end |
|
357 | 360 | |
|
358 | 361 | # Returns the level of this object in the tree |
|
359 | 362 | # root level is 0 |
|
360 | 363 | def level |
|
361 | 364 | parent_id.nil? ? 0 : compute_level |
|
362 | 365 | end |
|
363 | 366 | |
|
364 | 367 | # Returns a set of itself and all of its nested children |
|
365 | 368 | def self_and_descendants |
|
366 | 369 | nested_set_scope.where([ |
|
367 | 370 | "#{quoted_left_column_full_name} >= ? AND #{quoted_left_column_full_name} < ?", left, right |
|
368 | 371 | # using _left_ for both sides here lets us benefit from an index on that column if one exists |
|
369 | 372 | ]) |
|
370 | 373 | end |
|
371 | 374 | |
|
372 | 375 | # Returns a set of all of its children and nested children |
|
373 | 376 | def descendants |
|
374 | 377 | without_self self_and_descendants |
|
375 | 378 | end |
|
376 | 379 | |
|
377 | 380 | def is_descendant_of?(other) |
|
378 | 381 | other.left < self.left && self.left < other.right && same_scope?(other) |
|
379 | 382 | end |
|
380 | 383 | |
|
381 | 384 | def is_or_is_descendant_of?(other) |
|
382 | 385 | other.left <= self.left && self.left < other.right && same_scope?(other) |
|
383 | 386 | end |
|
384 | 387 | |
|
385 | 388 | def is_ancestor_of?(other) |
|
386 | 389 | self.left < other.left && other.left < self.right && same_scope?(other) |
|
387 | 390 | end |
|
388 | 391 | |
|
389 | 392 | def is_or_is_ancestor_of?(other) |
|
390 | 393 | self.left <= other.left && other.left < self.right && same_scope?(other) |
|
391 | 394 | end |
|
392 | 395 | |
|
393 | 396 | # Check if other model is in the same scope |
|
394 | 397 | def same_scope?(other) |
|
395 | 398 | Array(acts_as_nested_set_options[:scope]).all? do |attr| |
|
396 | 399 | self.send(attr) == other.send(attr) |
|
397 | 400 | end |
|
398 | 401 | end |
|
399 | 402 | |
|
400 | 403 | # Find the first sibling to the left |
|
401 | 404 | def left_sibling |
|
402 | 405 | siblings.where(["#{quoted_left_column_full_name} < ?", left]). |
|
403 | 406 | order("#{quoted_left_column_full_name} DESC").last |
|
404 | 407 | end |
|
405 | 408 | |
|
406 | 409 | # Find the first sibling to the right |
|
407 | 410 | def right_sibling |
|
408 | 411 | siblings.where(["#{quoted_left_column_full_name} > ?", left]).first |
|
409 | 412 | end |
|
410 | 413 | |
|
411 | 414 | # Shorthand method for finding the left sibling and moving to the left of it. |
|
412 | 415 | def move_left |
|
413 | 416 | move_to_left_of left_sibling |
|
414 | 417 | end |
|
415 | 418 | |
|
416 | 419 | # Shorthand method for finding the right sibling and moving to the right of it. |
|
417 | 420 | def move_right |
|
418 | 421 | move_to_right_of right_sibling |
|
419 | 422 | end |
|
420 | 423 | |
|
421 | 424 | # Move the node to the left of another node (you can pass id only) |
|
422 | 425 | def move_to_left_of(node) |
|
423 | 426 | move_to node, :left |
|
424 | 427 | end |
|
425 | 428 | |
|
426 | 429 | # Move the node to the left of another node (you can pass id only) |
|
427 | 430 | def move_to_right_of(node) |
|
428 | 431 | move_to node, :right |
|
429 | 432 | end |
|
430 | 433 | |
|
431 | 434 | # Move the node to the child of another node (you can pass id only) |
|
432 | 435 | def move_to_child_of(node) |
|
433 | 436 | move_to node, :child |
|
434 | 437 | end |
|
435 | 438 | |
|
436 | 439 | # Move the node to the child of another node with specify index (you can pass id only) |
|
437 | 440 | def move_to_child_with_index(node, index) |
|
438 | 441 | if node.children.empty? |
|
439 | 442 | move_to_child_of(node) |
|
440 | 443 | elsif node.children.count == index |
|
441 | 444 | move_to_right_of(node.children.last) |
|
442 | 445 | else |
|
443 | 446 | move_to_left_of(node.children[index]) |
|
444 | 447 | end |
|
445 | 448 | end |
|
446 | 449 | |
|
447 | 450 | # Move the node to root nodes |
|
448 | 451 | def move_to_root |
|
449 | 452 | move_to nil, :root |
|
450 | 453 | end |
|
451 | 454 | |
|
452 | 455 | # Order children in a nested set by an attribute |
|
453 | 456 | # Can order by any attribute class that uses the Comparable mixin, for example a string or integer |
|
454 | 457 | # Usage example when sorting categories alphabetically: @new_category.move_to_ordered_child_of(@root, "name") |
|
455 | 458 | def move_to_ordered_child_of(parent, order_attribute, ascending = true) |
|
456 | 459 | self.move_to_root and return unless parent |
|
457 | 460 | left = nil # This is needed, at least for the tests. |
|
458 | 461 | parent.children.each do |n| # Find the node immediately to the left of this node. |
|
459 | 462 | if ascending |
|
460 | 463 | left = n if n.send(order_attribute) < self.send(order_attribute) |
|
461 | 464 | else |
|
462 | 465 | left = n if n.send(order_attribute) > self.send(order_attribute) |
|
463 | 466 | end |
|
464 | 467 | end |
|
465 | 468 | self.move_to_child_of(parent) |
|
466 | 469 | return unless parent.children.count > 1 # Only need to order if there are multiple children. |
|
467 | 470 | if left # Self has a left neighbor. |
|
468 | 471 | self.move_to_right_of(left) |
|
469 | 472 | else # Self is the left most node. |
|
470 | 473 | self.move_to_left_of(parent.children[0]) |
|
471 | 474 | end |
|
472 | 475 | end |
|
473 | 476 | |
|
474 | 477 | def move_possible?(target) |
|
475 | 478 | self != target && # Can't target self |
|
476 | 479 | same_scope?(target) && # can't be in different scopes |
|
477 | 480 | # !(left..right).include?(target.left..target.right) # this needs tested more |
|
478 | 481 | # detect impossible move |
|
479 | 482 | !((left <= target.left && right >= target.left) or (left <= target.right && right >= target.right)) |
|
480 | 483 | end |
|
481 | 484 | |
|
482 | 485 | def to_text |
|
483 | 486 | self_and_descendants.map do |node| |
|
484 | 487 | "#{'*'*(node.level+1)} #{node.id} #{node.to_s} (#{node.parent_id}, #{node.left}, #{node.right})" |
|
485 | 488 | end.join("\n") |
|
486 | 489 | end |
|
487 | 490 | |
|
488 | 491 | protected |
|
489 | 492 | def compute_level |
|
490 | 493 | node, nesting = self, 0 |
|
491 | 494 | while (association = node.association(:parent)).loaded? && association.target |
|
492 | 495 | nesting += 1 |
|
493 | 496 | node = node.parent |
|
494 | 497 | end if node.respond_to? :association |
|
495 | 498 | node == self ? ancestors.count : node.level + nesting |
|
496 | 499 | end |
|
497 | 500 | |
|
498 | 501 | def without_self(scope) |
|
499 | 502 | scope.where(["#{self.class.quoted_table_name}.#{self.class.primary_key} != ?", self]) |
|
500 | 503 | end |
|
501 | 504 | |
|
502 | 505 | # All nested set queries should use this nested_set_scope, which performs finds on |
|
503 | 506 | # the base ActiveRecord class, using the :scope declared in the acts_as_nested_set |
|
504 | 507 | # declaration. |
|
505 | 508 | def nested_set_scope(options = {}) |
|
506 | 509 | options = {:order => quoted_left_column_full_name}.merge(options) |
|
507 | 510 | scopes = Array(acts_as_nested_set_options[:scope]) |
|
508 | 511 | options[:conditions] = scopes.inject({}) do |conditions,attr| |
|
509 | 512 | conditions.merge attr => self[attr] |
|
510 | 513 | end unless scopes.empty? |
|
511 | 514 | self.class.base_class.unscoped.scoped options |
|
512 | 515 | end |
|
513 | 516 | |
|
514 | 517 | def store_new_parent |
|
515 | 518 | @move_to_new_parent_id = send("#{parent_column_name}_changed?") ? parent_id : false |
|
516 | 519 | true # force callback to return true |
|
517 | 520 | end |
|
518 | 521 | |
|
519 | 522 | def move_to_new_parent |
|
520 | 523 | if @move_to_new_parent_id.nil? |
|
521 | 524 | move_to_root |
|
522 | 525 | elsif @move_to_new_parent_id |
|
523 | 526 | move_to_child_of(@move_to_new_parent_id) |
|
524 | 527 | end |
|
525 | 528 | end |
|
526 | 529 | |
|
527 | 530 | def set_depth! |
|
528 | 531 | if nested_set_scope.column_names.map(&:to_s).include?(depth_column_name.to_s) |
|
529 | 532 | in_tenacious_transaction do |
|
530 | 533 | reload |
|
531 | 534 | |
|
532 | 535 | nested_set_scope.where(:id => id).update_all(["#{quoted_depth_column_name} = ?", level]) |
|
533 | 536 | end |
|
534 | 537 | self[depth_column_name.to_sym] = self.level |
|
535 | 538 | end |
|
536 | 539 | end |
|
537 | 540 | |
|
538 | 541 | # on creation, set automatically lft and rgt to the end of the tree |
|
539 | 542 | def set_default_left_and_right |
|
540 | 543 | highest_right_row = nested_set_scope(:order => "#{quoted_right_column_full_name} desc").limit(1).lock(true).first |
|
541 | 544 | maxright = highest_right_row ? (highest_right_row[right_column_name] || 0) : 0 |
|
542 | 545 | # adds the new node to the right of all existing nodes |
|
543 | 546 | self[left_column_name] = maxright + 1 |
|
544 | 547 | self[right_column_name] = maxright + 2 |
|
545 | 548 | end |
|
546 | 549 | |
|
547 | 550 | def in_tenacious_transaction(&block) |
|
548 | 551 | retry_count = 0 |
|
549 | 552 | begin |
|
550 | 553 | transaction(&block) |
|
551 | 554 | rescue ActiveRecord::StatementInvalid => error |
|
552 | 555 | raise unless connection.open_transactions.zero? |
|
553 | 556 | raise unless error.message =~ /Deadlock found when trying to get lock|Lock wait timeout exceeded/ |
|
554 | 557 | raise unless retry_count < 10 |
|
555 | 558 | retry_count += 1 |
|
556 | 559 | logger.info "Deadlock detected on retry #{retry_count}, restarting transaction" |
|
557 | 560 | sleep(rand(retry_count)*0.1) # Aloha protocol |
|
558 | 561 | retry |
|
559 | 562 | end |
|
560 | 563 | end |
|
561 | 564 | |
|
562 | 565 | # Prunes a branch off of the tree, shifting all of the elements on the right |
|
563 | 566 | # back to the left so the counts still work. |
|
564 | 567 | def destroy_descendants |
|
565 | 568 | return if right.nil? || left.nil? || skip_before_destroy |
|
566 | 569 | |
|
567 | 570 | in_tenacious_transaction do |
|
568 | 571 | reload_nested_set |
|
569 | 572 | # select the rows in the model that extend past the deletion point and apply a lock |
|
570 | 573 | nested_set_scope.where(["#{quoted_left_column_full_name} >= ?", left]). |
|
571 | 574 | select(id).lock(true) |
|
572 | 575 | |
|
573 | 576 | if acts_as_nested_set_options[:dependent] == :destroy |
|
574 | 577 | descendants.each do |model| |
|
575 | 578 | model.skip_before_destroy = true |
|
576 | 579 | model.destroy |
|
577 | 580 | end |
|
578 | 581 | else |
|
579 | 582 | nested_set_scope.where(["#{quoted_left_column_name} > ? AND #{quoted_right_column_name} < ?", left, right]). |
|
580 | 583 | delete_all |
|
581 | 584 | end |
|
582 | 585 | |
|
583 | 586 | # update lefts and rights for remaining nodes |
|
584 | 587 | diff = right - left + 1 |
|
585 | 588 | nested_set_scope.where(["#{quoted_left_column_full_name} > ?", right]).update_all( |
|
586 | 589 | ["#{quoted_left_column_name} = (#{quoted_left_column_name} - ?)", diff] |
|
587 | 590 | ) |
|
588 | 591 | |
|
589 | 592 | nested_set_scope.where(["#{quoted_right_column_full_name} > ?", right]).update_all( |
|
590 | 593 | ["#{quoted_right_column_name} = (#{quoted_right_column_name} - ?)", diff] |
|
591 | 594 | ) |
|
592 | 595 | |
|
596 | reload | |
|
593 | 597 | # Don't allow multiple calls to destroy to corrupt the set |
|
594 | 598 | self.skip_before_destroy = true |
|
595 | 599 | end |
|
596 | 600 | end |
|
597 | 601 | |
|
598 | 602 | # reload left, right, and parent |
|
599 | 603 | def reload_nested_set |
|
600 | 604 | reload( |
|
601 | 605 | :select => "#{quoted_left_column_full_name}, #{quoted_right_column_full_name}, #{quoted_parent_column_full_name}", |
|
602 | 606 | :lock => true |
|
603 | 607 | ) |
|
604 | 608 | end |
|
605 | 609 | |
|
606 | 610 | def move_to(target, position) |
|
607 | 611 | raise ActiveRecord::ActiveRecordError, "You cannot move a new node" if self.new_record? |
|
608 | 612 | run_callbacks :move do |
|
609 | 613 | in_tenacious_transaction do |
|
610 | 614 | if target.is_a? self.class.base_class |
|
611 | 615 | target.reload_nested_set |
|
612 | 616 | elsif position != :root |
|
613 | 617 | # load object if node is not an object |
|
614 | 618 | target = nested_set_scope.find(target) |
|
615 | 619 | end |
|
616 | 620 | self.reload_nested_set |
|
617 | 621 | |
|
618 | 622 | unless position == :root || move_possible?(target) |
|
619 | 623 | raise ActiveRecord::ActiveRecordError, "Impossible move, target node cannot be inside moved tree." |
|
620 | 624 | end |
|
621 | 625 | |
|
622 | 626 | bound = case position |
|
623 | 627 | when :child; target[right_column_name] |
|
624 | 628 | when :left; target[left_column_name] |
|
625 | 629 | when :right; target[right_column_name] + 1 |
|
626 | 630 | when :root; 1 |
|
627 | 631 | else raise ActiveRecord::ActiveRecordError, "Position should be :child, :left, :right or :root ('#{position}' received)." |
|
628 | 632 | end |
|
629 | 633 | |
|
630 | 634 | if bound > self[right_column_name] |
|
631 | 635 | bound = bound - 1 |
|
632 | 636 | other_bound = self[right_column_name] + 1 |
|
633 | 637 | else |
|
634 | 638 | other_bound = self[left_column_name] - 1 |
|
635 | 639 | end |
|
636 | 640 | |
|
637 | 641 | # there would be no change |
|
638 | 642 | return if bound == self[right_column_name] || bound == self[left_column_name] |
|
639 | 643 | |
|
640 | 644 | # we have defined the boundaries of two non-overlapping intervals, |
|
641 | 645 | # so sorting puts both the intervals and their boundaries in order |
|
642 | 646 | a, b, c, d = [self[left_column_name], self[right_column_name], bound, other_bound].sort |
|
643 | 647 | |
|
644 | 648 | # select the rows in the model between a and d, and apply a lock |
|
645 | 649 | self.class.base_class.select('id').lock(true).where( |
|
646 | 650 | ["#{quoted_left_column_full_name} >= :a and #{quoted_right_column_full_name} <= :d", {:a => a, :d => d}] |
|
647 | 651 | ) |
|
648 | 652 | |
|
649 | 653 | new_parent = case position |
|
650 | 654 | when :child; target.id |
|
651 | 655 | when :root; nil |
|
652 | 656 | else target[parent_column_name] |
|
653 | 657 | end |
|
654 | 658 | |
|
655 | 659 | self.nested_set_scope.update_all([ |
|
656 | 660 | "#{quoted_left_column_name} = CASE " + |
|
657 | 661 | "WHEN #{quoted_left_column_name} BETWEEN :a AND :b " + |
|
658 | 662 | "THEN #{quoted_left_column_name} + :d - :b " + |
|
659 | 663 | "WHEN #{quoted_left_column_name} BETWEEN :c AND :d " + |
|
660 | 664 | "THEN #{quoted_left_column_name} + :a - :c " + |
|
661 | 665 | "ELSE #{quoted_left_column_name} END, " + |
|
662 | 666 | "#{quoted_right_column_name} = CASE " + |
|
663 | 667 | "WHEN #{quoted_right_column_name} BETWEEN :a AND :b " + |
|
664 | 668 | "THEN #{quoted_right_column_name} + :d - :b " + |
|
665 | 669 | "WHEN #{quoted_right_column_name} BETWEEN :c AND :d " + |
|
666 | 670 | "THEN #{quoted_right_column_name} + :a - :c " + |
|
667 | 671 | "ELSE #{quoted_right_column_name} END, " + |
|
668 | 672 | "#{quoted_parent_column_name} = CASE " + |
|
669 | 673 | "WHEN #{self.class.base_class.primary_key} = :id THEN :new_parent " + |
|
670 | 674 | "ELSE #{quoted_parent_column_name} END", |
|
671 | 675 | {:a => a, :b => b, :c => c, :d => d, :id => self.id, :new_parent => new_parent} |
|
672 | 676 | ]) |
|
673 | 677 | end |
|
674 | 678 | target.reload_nested_set if target |
|
675 | 679 | self.set_depth! |
|
676 | 680 | self.descendants.each(&:save) |
|
677 | 681 | self.reload_nested_set |
|
678 | 682 | end |
|
679 | 683 | end |
|
680 | 684 | |
|
681 | 685 | end |
|
682 | 686 | |
|
683 | 687 | # Mixed into both classes and instances to provide easy access to the column names |
|
684 | 688 | module Columns |
|
685 | 689 | def left_column_name |
|
686 | 690 | acts_as_nested_set_options[:left_column] |
|
687 | 691 | end |
|
688 | 692 | |
|
689 | 693 | def right_column_name |
|
690 | 694 | acts_as_nested_set_options[:right_column] |
|
691 | 695 | end |
|
692 | 696 | |
|
693 | 697 | def depth_column_name |
|
694 | 698 | acts_as_nested_set_options[:depth_column] |
|
695 | 699 | end |
|
696 | 700 | |
|
697 | 701 | def parent_column_name |
|
698 | 702 | acts_as_nested_set_options[:parent_column] |
|
699 | 703 | end |
|
700 | 704 | |
|
701 | 705 | def order_column |
|
702 | 706 | acts_as_nested_set_options[:order_column] || left_column_name |
|
703 | 707 | end |
|
704 | 708 | |
|
705 | 709 | def scope_column_names |
|
706 | 710 | Array(acts_as_nested_set_options[:scope]) |
|
707 | 711 | end |
|
708 | 712 | |
|
709 | 713 | def quoted_left_column_name |
|
710 | 714 | connection.quote_column_name(left_column_name) |
|
711 | 715 | end |
|
712 | 716 | |
|
713 | 717 | def quoted_right_column_name |
|
714 | 718 | connection.quote_column_name(right_column_name) |
|
715 | 719 | end |
|
716 | 720 | |
|
717 | 721 | def quoted_depth_column_name |
|
718 | 722 | connection.quote_column_name(depth_column_name) |
|
719 | 723 | end |
|
720 | 724 | |
|
721 | 725 | def quoted_parent_column_name |
|
722 | 726 | connection.quote_column_name(parent_column_name) |
|
723 | 727 | end |
|
724 | 728 | |
|
725 | 729 | def quoted_scope_column_names |
|
726 | 730 | scope_column_names.collect {|column_name| connection.quote_column_name(column_name) } |
|
727 | 731 | end |
|
728 | 732 | |
|
729 | 733 | def quoted_left_column_full_name |
|
730 | 734 | "#{quoted_table_name}.#{quoted_left_column_name}" |
|
731 | 735 | end |
|
732 | 736 | |
|
733 | 737 | def quoted_right_column_full_name |
|
734 | 738 | "#{quoted_table_name}.#{quoted_right_column_name}" |
|
735 | 739 | end |
|
736 | 740 | |
|
737 | 741 | def quoted_parent_column_full_name |
|
738 | 742 | "#{quoted_table_name}.#{quoted_parent_column_name}" |
|
739 | 743 | end |
|
740 | 744 | end |
|
741 | 745 | |
|
742 | 746 | end |
|
743 | 747 | end |
|
744 | 748 | end |
General Comments 0
You need to be logged in to leave comments.
Login now