Module: Julik::MakeLikeTree::InstanceMethods

Defined in:
lib/make_like_a_tree.rb

Instance Method Summary collapse

Instance Method Details

#add_child(child) ⇒ Object

Adds a child to this object in the tree. If this object hasn’t been initialized, it gets set up as a root node. Otherwise, this method will update all of the other elements in the tree and shift them to the right, keeping everything balanced.



231
232
233
234
235
236
237
 
# File 'lib/make_like_a_tree.rb', line 231

def add_child(child)
  begin
    add_child!(child)
  rescue ImpossibleReparent
    false
  end
end

#add_child!(child) ⇒ Object

A noisy version of add_child, will raise an ImpossibleReparent if you try to reparent a node onto its indirect child. Will return false if either of the records is a new record. Will reload both the parent and the child record

Raises:



250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
 
# File 'lib/make_like_a_tree.rb', line 250

def add_child!(child)
  return false if (new_record? || child.new_record?)
  raise ImpossibleReparent, "Cannot reparent #{child} onto its child node #{self}" unless child_can_be_added?(child)

  k = self.class
  
  new_left, new_right = determine_range_for_child(child)
  
  move_by = new_left - child[left_col_name]
  move_depth_by = (self[depth_column] + 1) - child[depth_column]
  
  child_occupies = (new_right - new_left) + 1
  
  transaction do
    # bring the child and its grandchildren over
    self.class.update_all( 
      "#{depth_column} = #{depth_column} + #{move_depth_by}," +
      "#{root_column} = #{self[root_column]}," +
      "#{left_col_name} = #{left_col_name} + #{move_by}," +
      "#{right_col_name} = #{right_col_name} + #{move_by}",
      "#{scope_condition} AND #{left_col_name} >= #{child[left_col_name]} AND #{right_col_name} <= #{child[right_col_name]}" +
      " AND #{root_column} = #{child[root_column]} AND #{root_column} != 0"
    )
    
    # update parent_id on child ONLY
    self.class.update_all(
      "#{parent_column} = #{self.id}",
      "id = #{child.id}"
    )
    
    # update myself and upstream to notify we are wider
    self.class.update_all(
      "#{right_col_name} = #{right_col_name} + #{child_occupies}",
      "#{scope_condition} AND #{root_column} = #{self[root_column]} AND (#{depth_column} < #{self[depth_column]} OR id = #{self.id})"
    )
    
    # update items to my right AND downstream of them to notify them we are wider. Will shift root items to the right
    self.class.update_all(
      "#{left_col_name} = #{left_col_name} + #{child_occupies}, " +
      "#{right_col_name} = #{right_col_name} + #{child_occupies}",
      "#{depth_column} >= #{self[depth_column]} " + 
      "AND #{left_col_name} > #{self[right_col_name]}"
    )
  end
  [self, child].map{|e| e.reload }
  true
end

#all_children(extras = {}) ⇒ Object

Returns a set of all of its children and nested children. Any additional options scope the find call.



335
336
337
338
 
# File 'lib/make_like_a_tree.rb', line 335

def all_children(extras = {})
  return [] unless might_have_children? # optimization shortcut
  self.class.scoped(scope_hash_for_branch).find(:all, extras)
end

#apply_parenting_after_create ⇒ Object

Used as an after_create callback to apply the parent_id assignment or create a root node



198
199
200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/make_like_a_tree.rb', line 198

def apply_parenting_after_create
  reload # Reload to bring in the id
  assign_default_left_and_right
  
  transaction do
    self.save
    unless self[parent_column].to_i.zero? # will also capture nil
      # Load the parent
      parent = self.class.find(self[parent_column])
      parent.add_child self
    end
  end
  true
end

#assign_default_left_and_right(with_space_inside = 0) ⇒ Object

Place the item to the appropriate place as a root item



214
215
216
217
218
219
 
# File 'lib/make_like_a_tree.rb', line 214

def assign_default_left_and_right(with_space_inside = 0)
  # Make a self root and assign left and right respectively
  # even if no children are specified
  self[root_column] = self.id
  self[left_col_name], self[right_col_name] = get_left_and_right_for(self, with_space_inside)
end

#child? ⇒ Boolean

Returns true is this is a child node. Inverse of root?

Returns:

  • (Boolean) 


193
194
195
 
# File 'lib/make_like_a_tree.rb', line 193

def child?
  !root?
end

#child_can_be_added?(child) ⇒ Boolean

Tells you if a reparent might be invalid

Returns:

  • (Boolean) 


240
241
242
243
244
245
246
 
# File 'lib/make_like_a_tree.rb', line 240

def child_can_be_added?(child)
  impossible = (child[root_column] == self[root_column] && 
    child[left_col_name] < self[left_col_name]) && 
    (child[right_col_name] > self[right_col_name])
  
  !impossible
end

#child_count ⇒ Object Also known as: children_count

Returns the number of children and grandchildren of this object



311
312
313
314
315
 
# File 'lib/make_like_a_tree.rb', line 311

def child_count
  return 0 unless (!new_record? && might_have_children?) # shortcut
  
  @child_count ||= self.class.scoped(scope_hash_for_branch).count
end

#conditions_for_all_children ⇒ Object

Get conditions for direct and indirect children of this record



351
352
353
354
355
356
357
358
359
360
361
362
 
# File 'lib/make_like_a_tree.rb', line 351

def conditions_for_all_children
  pk = "#{self.class.table_name} WHERE id = #{self.id}"
  inner_r  = "(SELECT #{root_column}    FROM #{pk})"
  inner_d  = "(SELECT #{depth_column}   FROM #{pk})"
  inner_l  = "(SELECT #{left_col_name}  FROM #{pk})"
  inner_r  = "(SELECT #{right_col_name} FROM #{pk})"
  inner_rt = "(SELECT #{root_column} FROM #{pk})"
  
  "#{scope_condition} AND #{inner_rt} AND " +
  "#{depth_column} > #{inner_d} AND " +
  "#{left_col_name} > #{inner_l} AND #{right_col_name} < #{inner_r}"
end

#conditions_for_self_and_siblings ⇒ Object

Get conditions to find myself and my siblings



365
366
367
368
 
# File 'lib/make_like_a_tree.rb', line 365

def conditions_for_self_and_siblings
  inner_select = "SELECT %s FROM %s WHERE id = %d" % [parent_column, self.class.table_name, id]
  "#{scope_condition} AND #{parent_column} = (#{inner_select})"
end

#determine_range_for_child(child) ⇒ Object

Determine lft and rgt for a child item, taking into account the number of child and grandchild nodes it has. Normally you would not use this directly



300
301
302
303
304
305
306
307
308
 
# File 'lib/make_like_a_tree.rb', line 300

def determine_range_for_child(child)
  new_left = begin
    right_bound_child = self.class.find(:first, 
      :conditions => "#{scope_condition} AND #{parent_column} = #{self.id} AND id != #{child.id}", :order => "#{right_col_name} DESC")
    right_bound_child ? (right_bound_child[right_col_name] + 1) : (self[left_col_name] + 1)
  end
  new_right = new_left + (child[right_col_name] - child[left_col_name])
  [new_left, new_right]
end

#direct_children(extras = {}) ⇒ Object

Returns a set of only this entry’s immediate children, also ordered by position. Any additional options scope the find call.



390
391
392
393
 
# File 'lib/make_like_a_tree.rb', line 390

def direct_children(extras = {})
  return [] unless might_have_children? # optimize!
  self.class.scoped(scope_hash_for_direct_children).find(:all, extras)
end

#full_set(extras = {}) ⇒ Object Also known as: all_children_and_self

Returns a set of itself and all of its nested children. Any additional options scope the find call.



328
329
330
 
# File 'lib/make_like_a_tree.rb', line 328

def full_set(extras = {})
  [self] + all_children(extras)
end

#index_in_parent ⇒ Object

Get the item index in parent. TODO: when the tree is balanced with no orphan counts, just use (rgt-lft)/2



172
173
174
175
176
177
178
 
# File 'lib/make_like_a_tree.rb', line 172

def index_in_parent
  # Fetch the item count of items that have the same root_id and the same parent_id and are lower than me on the indices
  @index_in_parent ||= self.class.count_by_sql(
    "SELECT COUNT(id) FROM #{self.class.table_name} WHERE " + 
    "#{right_col_name} < #{self[left_col_name]} AND  #{parent_column} = #{self[parent_column]}"
  )
end

#level ⇒ Object

Shortcut for self



223
224
225
 
# File 'lib/make_like_a_tree.rb', line 223

def level
  self[depth_column]
end

#might_have_children? ⇒ Boolean

Shortcut to determine if our left and right values allow for possible children. Note the difference in wording between might_have and has - if this method returns false, it means you should look no further. If it returns true, you should really examine the children to be sure

Returns:

  • (Boolean) 


322
323
324
 
# File 'lib/make_like_a_tree.rb', line 322

def might_have_children?
  (self[right_col_name] - self[left_col_name]) > 1
end

#move_down ⇒ Object

Move the record up in the list (uses move_to)



157
158
159
 
# File 'lib/make_like_a_tree.rb', line 157

def move_down
  move_to(index_in_parent + 1)
end

#move_to(idx) ⇒ Object

Move the item to a specific index within the range of it’s siblings. Used to reorder lists. Will cause a cascading update on the neighbouring items and their children, but the update will be scoped



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/make_like_a_tree.rb', line 83

def move_to(idx)
  return false if new_record?
  
  transaction do 
    # Take a few shortcuts to avoid extra work
    cur_idx = index_in_parent
    return true if (cur_idx == idx)
  
    range = siblings_and_self
    return true if range.length == 1
  
    cur_idx = range.index(self)
    return true if cur_idx == idx
  
    # Register starting and ending elements
    start_left, end_right = range[0][left_col_name], range[-1][right_col_name]
  
    old_range = range.dup
  
    range.delete_at(cur_idx)
    range.insert(idx, self)
    range.compact! # If we inserted something outside of range and created empty slots
  
    # Now remap segements
    left_remaps, right_remaps, mini_scopes = [], [], ["(1=0)"]
  
    # Exhaust the range starting with the last element, determining the remapped offset
    # based on the width of remaining sets
    while range.any?
      e = range.pop
      
      w = (e[right_col_name] - e[left_col_name])

      # Determine by how many we need to shift the adjacent keys to put this item into place.
      # On every iteration add 1 (the formal increment in a leaf node)
      offset_in_range = range.inject(0) do | sum, item_before |
        sum + item_before[right_col_name] - item_before[left_col_name] + 1
      end
      shift = offset_in_range - e[left_col_name] + 1
      
       # Optimize - do not move nodes that stay in the same place
      next if shift.zero?

      case_stmt = "#{left_col_name} >= #{e[left_col_name]} AND #{right_col_name} <= #{e[right_col_name]}"
      
      # Scoping our query by the mini-scope will help us avoid a table scan in some situations
      mini_scopes << case_stmt
      
      left_remaps.unshift(
        "WHEN (#{case_stmt}) THEN (#{left_col_name} + #{shift})"
      )
      right_remaps.unshift(
        "WHEN (#{case_stmt}) THEN (#{right_col_name} + #{shift})"
      )
    end
  
    # If we are not a root node, scope the changes to our subtree only - this will win us some less writes
    update_condition = root? ? scope_condition : "#{scope_condition} AND #{root_column} = #{self[root_column]}"
    update_condition << " AND (#{mini_scopes.join(" OR ")})"
    
    self.class.update_all(
      "#{left_col_name} = CASE #{left_remaps.join(' ')} ELSE #{left_col_name} END, " + 
      "#{right_col_name} = CASE #{right_remaps.join(' ')} ELSE #{right_col_name} END ",
      update_condition
    )
  end
end

#move_to_bottom ⇒ Object

Move the record to the bottom of the list (uses move_to)



167
168
169
 
# File 'lib/make_like_a_tree.rb', line 167

def move_to_bottom
  move_to(-1)
end

#move_to_top ⇒ Object

Move the record to top of the list (uses move_to)



162
163
164
 
# File 'lib/make_like_a_tree.rb', line 162

def move_to_top
  move_to(0)
end

#move_up ⇒ Object

Move the record down in the list (uses move_to)



152
153
154
 
# File 'lib/make_like_a_tree.rb', line 152

def move_up
  move_to(index_in_parent - 1)
end

#promote_to_root ⇒ Object

Make this item a root node (moves it to the end of the root node list in the same scope)



396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
 
# File 'lib/make_like_a_tree.rb', line 396

def promote_to_root
  return false if new_record?

  transaction do
    my_width = child_count * 2
  
    # Use the copy in the DB to infer keys
    stale = self.class.find(self.id, :select => [left_col_name, right_col_name, root_column, depth_column].join(', '))
    
    old_left, old_right, old_root, old_depth = stale[left_col_name], stale[right_col_name], stale[root_column], stale[depth_column]
    
    
    self[parent_column] = 0 # Signal the root node
    new_left, new_right = get_left_and_right_for(self, my_width)
    
    move_by = new_left - old_left
    move_depth_by = old_depth
    
    # bring the child and its grandchildren over
    self.class.update_all( 
      "#{depth_column} = #{depth_column} - #{move_depth_by}," +
      "#{root_column} = #{self.id}," +
      "#{left_col_name} = #{left_col_name} + #{move_by}," +
      "#{right_col_name} = #{right_col_name} + #{move_by}",
      "#{scope_condition} AND #{left_col_name} >= #{old_left} AND #{right_col_name} <= #{old_right}" +
      " AND #{root_column} = #{old_root}"
    )
    
    # update self, assume valid object for speed
    self.class.update_all(
      "#{root_column} = #{self.id}, #{depth_column} = 0, #{parent_column} = 0, #{left_col_name} = #{new_left}, #{right_col_name} = #{new_right}",
      "id = #{self.id}"
    )
    
    # Blow away the memoized counts
    self.reload
  end
  true
end

#reload(options = nil) ⇒ Object

Override ActiveRecord::Base#reload to blow over all the memoized values



181
182
183
184
185
 
# File 'lib/make_like_a_tree.rb', line 181

def reload(options = nil)
  @index_in_parent, @is_root, @is_child, 
    @old_parent_id, @rerooted, @child_count = nil, nil, nil, nil, nil, nil
  super(options)
end

#root? ⇒ Boolean

Returns true is this is a root thread.

Returns:

  • (Boolean) 


188
189
190
 
# File 'lib/make_like_a_tree.rb', line 188

def root?
  self[parent_column].to_i.zero?
end

#scope_hash_for_branch ⇒ Object

Returns scoping options suitable for fetching all children



341
342
343
 
# File 'lib/make_like_a_tree.rb', line 341

def scope_hash_for_branch
  {:conditions => conditions_for_all_children, :order => "#{left_col_name} ASC" }
end

#scope_hash_for_direct_children ⇒ Object

Returns scopint options suitable for fetching direct children



346
347
348
 
# File 'lib/make_like_a_tree.rb', line 346

def scope_hash_for_direct_children
  {:conditions => "#{scope_condition} AND #{parent_column} = #{self.id}", :order => "#{left_col_name} ASC"}
end

#siblings(extras = {}) ⇒ Object

Get immediate siblings, ordered



371
372
373
374
375
376
377
 
# File 'lib/make_like_a_tree.rb', line 371

def siblings(extras = {})
  scope = {
    :conditions => "#{conditions_for_self_and_siblings} AND id != #{self.id}", 
    :order => "#{left_col_name} ASC"
  }
  self.class.scoped(scope).find(:all, extras)
end

#siblings_and_self(extras = {}) ⇒ Object

Get myself and siblings, ordered



380
381
382
383
384
385
386
 
# File 'lib/make_like_a_tree.rb', line 380

def siblings_and_self(extras = {})
  scope = {
    :conditions => "#{conditions_for_self_and_siblings}", 
    :order => "#{left_col_name} ASC"
  }
  self.class.scoped(scope).find(:all, extras)
end