@@ -1,744 +1,746 | |||
|
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 | 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) } |
|
202 | 202 | # set right |
|
203 | 203 | node[right_column_name] = indices[scope.call(node)] += 1 |
|
204 | 204 | node.save!(:validate => validate_nodes) |
|
205 | 205 | end |
|
206 | 206 | |
|
207 | 207 | # Find root node(s) |
|
208 | 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| |
|
209 | 209 | # setup index for this scope |
|
210 | 210 | indices[scope.call(root_node)] ||= 0 |
|
211 | 211 | set_left_and_rights.call(root_node) |
|
212 | 212 | end |
|
213 | 213 | end |
|
214 | 214 | |
|
215 | 215 | # Iterates over tree elements and determines the current level in the tree. |
|
216 | 216 | # Only accepts default ordering, odering by an other column than lft |
|
217 | 217 | # does not work. This method is much more efficent than calling level |
|
218 | 218 | # because it doesn't require any additional database queries. |
|
219 | 219 | # |
|
220 | 220 | # Example: |
|
221 | 221 | # Category.each_with_level(Category.root.self_and_descendants) do |o, level| |
|
222 | 222 | # |
|
223 | 223 | def each_with_level(objects) |
|
224 | 224 | path = [nil] |
|
225 | 225 | objects.each do |o| |
|
226 | 226 | if o.parent_id != path.last |
|
227 | 227 | # we are on a new level, did we descend or ascend? |
|
228 | 228 | if path.include?(o.parent_id) |
|
229 | 229 | # remove wrong wrong tailing paths elements |
|
230 | 230 | path.pop while path.last != o.parent_id |
|
231 | 231 | else |
|
232 | 232 | path << o.parent_id |
|
233 | 233 | end |
|
234 | 234 | end |
|
235 | 235 | yield(o, path.length - 1) |
|
236 | 236 | end |
|
237 | 237 | end |
|
238 | 238 | |
|
239 | 239 | # Same as each_with_level - Accepts a string as a second argument to sort the list |
|
240 | 240 | # Example: |
|
241 | 241 | # Category.each_with_level(Category.root.self_and_descendants, :sort_by_this_column) do |o, level| |
|
242 | 242 | def sorted_each_with_level(objects, order) |
|
243 | 243 | path = [nil] |
|
244 | 244 | children = [] |
|
245 | 245 | objects.each do |o| |
|
246 | 246 | children << o if o.leaf? |
|
247 | 247 | if o.parent_id != path.last |
|
248 | 248 | if !children.empty? && !o.leaf? |
|
249 | 249 | children.sort_by! &order |
|
250 | 250 | children.each { |c| yield(c, path.length-1) } |
|
251 | 251 | children = [] |
|
252 | 252 | end |
|
253 | 253 | # we are on a new level, did we decent or ascent? |
|
254 | 254 | if path.include?(o.parent_id) |
|
255 | 255 | # remove wrong wrong tailing paths elements |
|
256 | 256 | path.pop while path.last != o.parent_id |
|
257 | 257 | else |
|
258 | 258 | path << o.parent_id |
|
259 | 259 | end |
|
260 | 260 | end |
|
261 | 261 | yield(o,path.length-1) if !o.leaf? |
|
262 | 262 | end |
|
263 | 263 | if !children.empty? |
|
264 | 264 | children.sort_by! &order |
|
265 | 265 | children.each { |c| yield(c, path.length-1) } |
|
266 | 266 | end |
|
267 | 267 | end |
|
268 | 268 | |
|
269 | 269 | def associate_parents(objects) |
|
270 | 270 | if objects.all?{|o| o.respond_to?(:association)} |
|
271 | 271 | id_indexed = objects.index_by(&:id) |
|
272 | 272 | objects.each do |object| |
|
273 | 273 | if !(association = object.association(:parent)).loaded? && (parent = id_indexed[object.parent_id]) |
|
274 | 274 | association.target = parent |
|
275 | 275 | association.set_inverse_instance(parent) |
|
276 | 276 | end |
|
277 | 277 | end |
|
278 | 278 | else |
|
279 | 279 | objects |
|
280 | 280 | end |
|
281 | 281 | end |
|
282 | 282 | end |
|
283 | 283 | |
|
284 | 284 | # 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 | 285 | # |
|
286 | 286 | # category.self_and_descendants.count |
|
287 | 287 | # category.ancestors.find(:all, :conditions => "name like '%foo%'") |
|
288 | 288 | # Value of the parent column |
|
289 | 289 | def parent_id |
|
290 | 290 | self[parent_column_name] |
|
291 | 291 | end |
|
292 | 292 | |
|
293 | 293 | # Value of the left column |
|
294 | 294 | def left |
|
295 | 295 | self[left_column_name] |
|
296 | 296 | end |
|
297 | 297 | |
|
298 | 298 | # Value of the right column |
|
299 | 299 | def right |
|
300 | 300 | self[right_column_name] |
|
301 | 301 | end |
|
302 | 302 | |
|
303 | 303 | # Returns true if this is a root node. |
|
304 | 304 | def root? |
|
305 | 305 | parent_id.nil? |
|
306 | 306 | end |
|
307 | 307 | |
|
308 | 308 | # Returns true if this is the end of a branch. |
|
309 | 309 | def leaf? |
|
310 | 310 | persisted? && right.to_i - left.to_i == 1 |
|
311 | 311 | end |
|
312 | 312 | |
|
313 | 313 | # Returns true is this is a child node |
|
314 | 314 | def child? |
|
315 | 315 | !root? |
|
316 | 316 | end |
|
317 | 317 | |
|
318 | 318 | # Returns root |
|
319 | 319 | def root |
|
320 | 320 | if persisted? |
|
321 | 321 | self_and_ancestors.where(parent_column_name => nil).first |
|
322 | 322 | else |
|
323 | 323 | if parent_id && current_parent = nested_set_scope.find(parent_id) |
|
324 | 324 | current_parent.root |
|
325 | 325 | else |
|
326 | 326 | self |
|
327 | 327 | end |
|
328 | 328 | end |
|
329 | 329 | end |
|
330 | 330 | |
|
331 | 331 | # Returns the array of all parents and self |
|
332 | 332 | def self_and_ancestors |
|
333 | 333 | nested_set_scope.where([ |
|
334 | 334 | "#{quoted_left_column_full_name} <= ? AND #{quoted_right_column_full_name} >= ?", left, right |
|
335 | 335 | ]) |
|
336 | 336 | end |
|
337 | 337 | |
|
338 | 338 | # Returns an array of all parents |
|
339 | 339 | def ancestors |
|
340 | 340 | without_self self_and_ancestors |
|
341 | 341 | end |
|
342 | 342 | |
|
343 | 343 | # Returns the array of all children of the parent, including self |
|
344 | 344 | def self_and_siblings |
|
345 | 345 | nested_set_scope.where(parent_column_name => parent_id) |
|
346 | 346 | end |
|
347 | 347 | |
|
348 | 348 | # Returns the array of all children of the parent, except self |
|
349 | 349 | def siblings |
|
350 | 350 | without_self self_and_siblings |
|
351 | 351 | end |
|
352 | 352 | |
|
353 | 353 | # Returns a set of all of its nested children which do not have children |
|
354 | 354 | def leaves |
|
355 | 355 | descendants.where("#{quoted_right_column_full_name} - #{quoted_left_column_full_name} = 1") |
|
356 | 356 | end |
|
357 | 357 | |
|
358 | 358 | # Returns the level of this object in the tree |
|
359 | 359 | # root level is 0 |
|
360 | 360 | def level |
|
361 | 361 | parent_id.nil? ? 0 : compute_level |
|
362 | 362 | end |
|
363 | 363 | |
|
364 | 364 | # Returns a set of itself and all of its nested children |
|
365 | 365 | def self_and_descendants |
|
366 | 366 | nested_set_scope.where([ |
|
367 | 367 | "#{quoted_left_column_full_name} >= ? AND #{quoted_left_column_full_name} < ?", left, right |
|
368 | 368 | # using _left_ for both sides here lets us benefit from an index on that column if one exists |
|
369 | 369 | ]) |
|
370 | 370 | end |
|
371 | 371 | |
|
372 | 372 | # Returns a set of all of its children and nested children |
|
373 | 373 | def descendants |
|
374 | 374 | without_self self_and_descendants |
|
375 | 375 | end |
|
376 | 376 | |
|
377 | 377 | def is_descendant_of?(other) |
|
378 | 378 | other.left < self.left && self.left < other.right && same_scope?(other) |
|
379 | 379 | end |
|
380 | 380 | |
|
381 | 381 | def is_or_is_descendant_of?(other) |
|
382 | 382 | other.left <= self.left && self.left < other.right && same_scope?(other) |
|
383 | 383 | end |
|
384 | 384 | |
|
385 | 385 | def is_ancestor_of?(other) |
|
386 | 386 | self.left < other.left && other.left < self.right && same_scope?(other) |
|
387 | 387 | end |
|
388 | 388 | |
|
389 | 389 | def is_or_is_ancestor_of?(other) |
|
390 | 390 | self.left <= other.left && other.left < self.right && same_scope?(other) |
|
391 | 391 | end |
|
392 | 392 | |
|
393 | 393 | # Check if other model is in the same scope |
|
394 | 394 | def same_scope?(other) |
|
395 | 395 | Array(acts_as_nested_set_options[:scope]).all? do |attr| |
|
396 | 396 | self.send(attr) == other.send(attr) |
|
397 | 397 | end |
|
398 | 398 | end |
|
399 | 399 | |
|
400 | 400 | # Find the first sibling to the left |
|
401 | 401 | def left_sibling |
|
402 | 402 | siblings.where(["#{quoted_left_column_full_name} < ?", left]). |
|
403 | 403 | order("#{quoted_left_column_full_name} DESC").last |
|
404 | 404 | end |
|
405 | 405 | |
|
406 | 406 | # Find the first sibling to the right |
|
407 | 407 | def right_sibling |
|
408 | 408 | siblings.where(["#{quoted_left_column_full_name} > ?", left]).first |
|
409 | 409 | end |
|
410 | 410 | |
|
411 | 411 | # Shorthand method for finding the left sibling and moving to the left of it. |
|
412 | 412 | def move_left |
|
413 | 413 | move_to_left_of left_sibling |
|
414 | 414 | end |
|
415 | 415 | |
|
416 | 416 | # Shorthand method for finding the right sibling and moving to the right of it. |
|
417 | 417 | def move_right |
|
418 | 418 | move_to_right_of right_sibling |
|
419 | 419 | end |
|
420 | 420 | |
|
421 | 421 | # Move the node to the left of another node (you can pass id only) |
|
422 | 422 | def move_to_left_of(node) |
|
423 | 423 | move_to node, :left |
|
424 | 424 | end |
|
425 | 425 | |
|
426 | 426 | # Move the node to the left of another node (you can pass id only) |
|
427 | 427 | def move_to_right_of(node) |
|
428 | 428 | move_to node, :right |
|
429 | 429 | end |
|
430 | 430 | |
|
431 | 431 | # Move the node to the child of another node (you can pass id only) |
|
432 | 432 | def move_to_child_of(node) |
|
433 | 433 | move_to node, :child |
|
434 | 434 | end |
|
435 | 435 | |
|
436 | 436 | # Move the node to the child of another node with specify index (you can pass id only) |
|
437 | 437 | def move_to_child_with_index(node, index) |
|
438 | 438 | if node.children.empty? |
|
439 | 439 | move_to_child_of(node) |
|
440 | 440 | elsif node.children.count == index |
|
441 | 441 | move_to_right_of(node.children.last) |
|
442 | 442 | else |
|
443 | 443 | move_to_left_of(node.children[index]) |
|
444 | 444 | end |
|
445 | 445 | end |
|
446 | 446 | |
|
447 | 447 | # Move the node to root nodes |
|
448 | 448 | def move_to_root |
|
449 | 449 | move_to nil, :root |
|
450 | 450 | end |
|
451 | 451 | |
|
452 | 452 | # Order children in a nested set by an attribute |
|
453 | 453 | # Can order by any attribute class that uses the Comparable mixin, for example a string or integer |
|
454 | 454 | # Usage example when sorting categories alphabetically: @new_category.move_to_ordered_child_of(@root, "name") |
|
455 | 455 | def move_to_ordered_child_of(parent, order_attribute, ascending = true) |
|
456 | 456 | self.move_to_root and return unless parent |
|
457 | 457 | left = nil # This is needed, at least for the tests. |
|
458 | 458 | parent.children.each do |n| # Find the node immediately to the left of this node. |
|
459 | 459 | if ascending |
|
460 | 460 | left = n if n.send(order_attribute) < self.send(order_attribute) |
|
461 | 461 | else |
|
462 | 462 | left = n if n.send(order_attribute) > self.send(order_attribute) |
|
463 | 463 | end |
|
464 | 464 | end |
|
465 | 465 | self.move_to_child_of(parent) |
|
466 | 466 | return unless parent.children.count > 1 # Only need to order if there are multiple children. |
|
467 | 467 | if left # Self has a left neighbor. |
|
468 | 468 | self.move_to_right_of(left) |
|
469 | 469 | else # Self is the left most node. |
|
470 | 470 | self.move_to_left_of(parent.children[0]) |
|
471 | 471 | end |
|
472 | 472 | end |
|
473 | 473 | |
|
474 | 474 | def move_possible?(target) |
|
475 | 475 | self != target && # Can't target self |
|
476 | 476 | same_scope?(target) && # can't be in different scopes |
|
477 | 477 | # !(left..right).include?(target.left..target.right) # this needs tested more |
|
478 | 478 | # detect impossible move |
|
479 | 479 | !((left <= target.left && right >= target.left) or (left <= target.right && right >= target.right)) |
|
480 | 480 | end |
|
481 | 481 | |
|
482 | 482 | def to_text |
|
483 | 483 | self_and_descendants.map do |node| |
|
484 | 484 | "#{'*'*(node.level+1)} #{node.id} #{node.to_s} (#{node.parent_id}, #{node.left}, #{node.right})" |
|
485 | 485 | end.join("\n") |
|
486 | 486 | end |
|
487 | 487 | |
|
488 | 488 | protected |
|
489 | 489 | def compute_level |
|
490 | 490 | node, nesting = self, 0 |
|
491 | 491 | while (association = node.association(:parent)).loaded? && association.target |
|
492 | 492 | nesting += 1 |
|
493 | 493 | node = node.parent |
|
494 | 494 | end if node.respond_to? :association |
|
495 | 495 | node == self ? ancestors.count : node.level + nesting |
|
496 | 496 | end |
|
497 | 497 | |
|
498 | 498 | def without_self(scope) |
|
499 | 499 | scope.where(["#{self.class.quoted_table_name}.#{self.class.primary_key} != ?", self]) |
|
500 | 500 | end |
|
501 | 501 | |
|
502 | 502 | # All nested set queries should use this nested_set_scope, which performs finds on |
|
503 | 503 | # the base ActiveRecord class, using the :scope declared in the acts_as_nested_set |
|
504 | 504 | # declaration. |
|
505 | 505 | def nested_set_scope(options = {}) |
|
506 | 506 | options = {:order => quoted_left_column_full_name}.merge(options) |
|
507 | 507 | scopes = Array(acts_as_nested_set_options[:scope]) |
|
508 | 508 | options[:conditions] = scopes.inject({}) do |conditions,attr| |
|
509 | 509 | conditions.merge attr => self[attr] |
|
510 | 510 | end unless scopes.empty? |
|
511 | 511 | self.class.base_class.unscoped.scoped options |
|
512 | 512 | end |
|
513 | 513 | |
|
514 | 514 | def store_new_parent |
|
515 | 515 | @move_to_new_parent_id = send("#{parent_column_name}_changed?") ? parent_id : false |
|
516 | 516 | true # force callback to return true |
|
517 | 517 | end |
|
518 | 518 | |
|
519 | 519 | def move_to_new_parent |
|
520 | 520 | if @move_to_new_parent_id.nil? |
|
521 | 521 | move_to_root |
|
522 | 522 | elsif @move_to_new_parent_id |
|
523 | 523 | move_to_child_of(@move_to_new_parent_id) |
|
524 | 524 | end |
|
525 | 525 | end |
|
526 | 526 | |
|
527 | 527 | def set_depth! |
|
528 | 528 | if nested_set_scope.column_names.map(&:to_s).include?(depth_column_name.to_s) |
|
529 | 529 | in_tenacious_transaction do |
|
530 | 530 | reload |
|
531 | 531 | |
|
532 | 532 | nested_set_scope.where(:id => id).update_all(["#{quoted_depth_column_name} = ?", level]) |
|
533 | 533 | end |
|
534 | 534 | self[depth_column_name.to_sym] = self.level |
|
535 | 535 | end |
|
536 | 536 | end |
|
537 | 537 | |
|
538 | 538 | # on creation, set automatically lft and rgt to the end of the tree |
|
539 | 539 | def set_default_left_and_right |
|
540 | 540 | highest_right_row = nested_set_scope(:order => "#{quoted_right_column_full_name} desc").limit(1).lock(true).first |
|
541 | 541 | maxright = highest_right_row ? (highest_right_row[right_column_name] || 0) : 0 |
|
542 | 542 | # adds the new node to the right of all existing nodes |
|
543 | 543 | self[left_column_name] = maxright + 1 |
|
544 | 544 | self[right_column_name] = maxright + 2 |
|
545 | 545 | end |
|
546 | 546 | |
|
547 | 547 | def in_tenacious_transaction(&block) |
|
548 | 548 | retry_count = 0 |
|
549 | 549 | begin |
|
550 | 550 | transaction(&block) |
|
551 | 551 | rescue ActiveRecord::StatementInvalid => error |
|
552 | 552 | raise unless connection.open_transactions.zero? |
|
553 | 553 | raise unless error.message =~ /Deadlock found when trying to get lock|Lock wait timeout exceeded/ |
|
554 | 554 | raise unless retry_count < 10 |
|
555 | 555 | retry_count += 1 |
|
556 | 556 | logger.info "Deadlock detected on retry #{retry_count}, restarting transaction" |
|
557 | 557 | sleep(rand(retry_count)*0.1) # Aloha protocol |
|
558 | 558 | retry |
|
559 | 559 | end |
|
560 | 560 | end |
|
561 | 561 | |
|
562 | 562 | # Prunes a branch off of the tree, shifting all of the elements on the right |
|
563 | 563 | # back to the left so the counts still work. |
|
564 | 564 | def destroy_descendants |
|
565 | 565 | return if right.nil? || left.nil? || skip_before_destroy |
|
566 | 566 | |
|
567 | 567 | in_tenacious_transaction do |
|
568 | 568 | reload_nested_set |
|
569 | 569 | # select the rows in the model that extend past the deletion point and apply a lock |
|
570 | 570 | nested_set_scope.where(["#{quoted_left_column_full_name} >= ?", left]). |
|
571 | 571 | select(id).lock(true) |
|
572 | 572 | |
|
573 | 573 | if acts_as_nested_set_options[:dependent] == :destroy |
|
574 | 574 | descendants.each do |model| |
|
575 | 575 | model.skip_before_destroy = true |
|
576 | 576 | model.destroy |
|
577 | 577 | end |
|
578 | 578 | else |
|
579 | 579 | nested_set_scope.where(["#{quoted_left_column_name} > ? AND #{quoted_right_column_name} < ?", left, right]). |
|
580 | 580 | delete_all |
|
581 | 581 | end |
|
582 | 582 | |
|
583 | 583 | # update lefts and rights for remaining nodes |
|
584 | 584 | diff = right - left + 1 |
|
585 | 585 | nested_set_scope.where(["#{quoted_left_column_full_name} > ?", right]).update_all( |
|
586 | 586 | ["#{quoted_left_column_name} = (#{quoted_left_column_name} - ?)", diff] |
|
587 | 587 | ) |
|
588 | 588 | |
|
589 | 589 | nested_set_scope.where(["#{quoted_right_column_full_name} > ?", right]).update_all( |
|
590 | 590 | ["#{quoted_right_column_name} = (#{quoted_right_column_name} - ?)", diff] |
|
591 | 591 | ) |
|
592 | 592 | |
|
593 | # Reload is needed because children may have updated their parent (self) during deletion. | |
|
594 | reload | |
|
593 | 595 | # Don't allow multiple calls to destroy to corrupt the set |
|
594 | 596 | self.skip_before_destroy = true |
|
595 | 597 | end |
|
596 | 598 | end |
|
597 | 599 | |
|
598 | 600 | # reload left, right, and parent |
|
599 | 601 | def reload_nested_set |
|
600 | 602 | reload( |
|
601 | 603 | :select => "#{quoted_left_column_full_name}, #{quoted_right_column_full_name}, #{quoted_parent_column_full_name}", |
|
602 | 604 | :lock => true |
|
603 | 605 | ) |
|
604 | 606 | end |
|
605 | 607 | |
|
606 | 608 | def move_to(target, position) |
|
607 | 609 | raise ActiveRecord::ActiveRecordError, "You cannot move a new node" if self.new_record? |
|
608 | 610 | run_callbacks :move do |
|
609 | 611 | in_tenacious_transaction do |
|
610 | 612 | if target.is_a? self.class.base_class |
|
611 | 613 | target.reload_nested_set |
|
612 | 614 | elsif position != :root |
|
613 | 615 | # load object if node is not an object |
|
614 | 616 | target = nested_set_scope.find(target) |
|
615 | 617 | end |
|
616 | 618 | self.reload_nested_set |
|
617 | 619 | |
|
618 | 620 | unless position == :root || move_possible?(target) |
|
619 | 621 | raise ActiveRecord::ActiveRecordError, "Impossible move, target node cannot be inside moved tree." |
|
620 | 622 | end |
|
621 | 623 | |
|
622 | 624 | bound = case position |
|
623 | 625 | when :child; target[right_column_name] |
|
624 | 626 | when :left; target[left_column_name] |
|
625 | 627 | when :right; target[right_column_name] + 1 |
|
626 | 628 | when :root; 1 |
|
627 | 629 | else raise ActiveRecord::ActiveRecordError, "Position should be :child, :left, :right or :root ('#{position}' received)." |
|
628 | 630 | end |
|
629 | 631 | |
|
630 | 632 | if bound > self[right_column_name] |
|
631 | 633 | bound = bound - 1 |
|
632 | 634 | other_bound = self[right_column_name] + 1 |
|
633 | 635 | else |
|
634 | 636 | other_bound = self[left_column_name] - 1 |
|
635 | 637 | end |
|
636 | 638 | |
|
637 | 639 | # there would be no change |
|
638 | 640 | return if bound == self[right_column_name] || bound == self[left_column_name] |
|
639 | 641 | |
|
640 | 642 | # we have defined the boundaries of two non-overlapping intervals, |
|
641 | 643 | # so sorting puts both the intervals and their boundaries in order |
|
642 | 644 | a, b, c, d = [self[left_column_name], self[right_column_name], bound, other_bound].sort |
|
643 | 645 | |
|
644 | 646 | # select the rows in the model between a and d, and apply a lock |
|
645 | 647 | self.class.base_class.select('id').lock(true).where( |
|
646 | 648 | ["#{quoted_left_column_full_name} >= :a and #{quoted_right_column_full_name} <= :d", {:a => a, :d => d}] |
|
647 | 649 | ) |
|
648 | 650 | |
|
649 | 651 | new_parent = case position |
|
650 | 652 | when :child; target.id |
|
651 | 653 | when :root; nil |
|
652 | 654 | else target[parent_column_name] |
|
653 | 655 | end |
|
654 | 656 | |
|
655 | 657 | self.nested_set_scope.update_all([ |
|
656 | 658 | "#{quoted_left_column_name} = CASE " + |
|
657 | 659 | "WHEN #{quoted_left_column_name} BETWEEN :a AND :b " + |
|
658 | 660 | "THEN #{quoted_left_column_name} + :d - :b " + |
|
659 | 661 | "WHEN #{quoted_left_column_name} BETWEEN :c AND :d " + |
|
660 | 662 | "THEN #{quoted_left_column_name} + :a - :c " + |
|
661 | 663 | "ELSE #{quoted_left_column_name} END, " + |
|
662 | 664 | "#{quoted_right_column_name} = CASE " + |
|
663 | 665 | "WHEN #{quoted_right_column_name} BETWEEN :a AND :b " + |
|
664 | 666 | "THEN #{quoted_right_column_name} + :d - :b " + |
|
665 | 667 | "WHEN #{quoted_right_column_name} BETWEEN :c AND :d " + |
|
666 | 668 | "THEN #{quoted_right_column_name} + :a - :c " + |
|
667 | 669 | "ELSE #{quoted_right_column_name} END, " + |
|
668 | 670 | "#{quoted_parent_column_name} = CASE " + |
|
669 | 671 | "WHEN #{self.class.base_class.primary_key} = :id THEN :new_parent " + |
|
670 | 672 | "ELSE #{quoted_parent_column_name} END", |
|
671 | 673 | {:a => a, :b => b, :c => c, :d => d, :id => self.id, :new_parent => new_parent} |
|
672 | 674 | ]) |
|
673 | 675 | end |
|
674 | 676 | target.reload_nested_set if target |
|
675 | 677 | self.set_depth! |
|
676 | 678 | self.descendants.each(&:save) |
|
677 | 679 | self.reload_nested_set |
|
678 | 680 | end |
|
679 | 681 | end |
|
680 | 682 | |
|
681 | 683 | end |
|
682 | 684 | |
|
683 | 685 | # Mixed into both classes and instances to provide easy access to the column names |
|
684 | 686 | module Columns |
|
685 | 687 | def left_column_name |
|
686 | 688 | acts_as_nested_set_options[:left_column] |
|
687 | 689 | end |
|
688 | 690 | |
|
689 | 691 | def right_column_name |
|
690 | 692 | acts_as_nested_set_options[:right_column] |
|
691 | 693 | end |
|
692 | 694 | |
|
693 | 695 | def depth_column_name |
|
694 | 696 | acts_as_nested_set_options[:depth_column] |
|
695 | 697 | end |
|
696 | 698 | |
|
697 | 699 | def parent_column_name |
|
698 | 700 | acts_as_nested_set_options[:parent_column] |
|
699 | 701 | end |
|
700 | 702 | |
|
701 | 703 | def order_column |
|
702 | 704 | acts_as_nested_set_options[:order_column] || left_column_name |
|
703 | 705 | end |
|
704 | 706 | |
|
705 | 707 | def scope_column_names |
|
706 | 708 | Array(acts_as_nested_set_options[:scope]) |
|
707 | 709 | end |
|
708 | 710 | |
|
709 | 711 | def quoted_left_column_name |
|
710 | 712 | connection.quote_column_name(left_column_name) |
|
711 | 713 | end |
|
712 | 714 | |
|
713 | 715 | def quoted_right_column_name |
|
714 | 716 | connection.quote_column_name(right_column_name) |
|
715 | 717 | end |
|
716 | 718 | |
|
717 | 719 | def quoted_depth_column_name |
|
718 | 720 | connection.quote_column_name(depth_column_name) |
|
719 | 721 | end |
|
720 | 722 | |
|
721 | 723 | def quoted_parent_column_name |
|
722 | 724 | connection.quote_column_name(parent_column_name) |
|
723 | 725 | end |
|
724 | 726 | |
|
725 | 727 | def quoted_scope_column_names |
|
726 | 728 | scope_column_names.collect {|column_name| connection.quote_column_name(column_name) } |
|
727 | 729 | end |
|
728 | 730 | |
|
729 | 731 | def quoted_left_column_full_name |
|
730 | 732 | "#{quoted_table_name}.#{quoted_left_column_name}" |
|
731 | 733 | end |
|
732 | 734 | |
|
733 | 735 | def quoted_right_column_full_name |
|
734 | 736 | "#{quoted_table_name}.#{quoted_right_column_name}" |
|
735 | 737 | end |
|
736 | 738 | |
|
737 | 739 | def quoted_parent_column_full_name |
|
738 | 740 | "#{quoted_table_name}.#{quoted_parent_column_name}" |
|
739 | 741 | end |
|
740 | 742 | end |
|
741 | 743 | |
|
742 | 744 | end |
|
743 | 745 | end |
|
744 | 746 | end |
General Comments 0
You need to be logged in to leave comments.
Login now