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.



221
222
223
224
225
226
227
 
# File 'lib/make_like_a_tree.rb', line 221

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

Raises:



238
239
240
241
242
243
244
245
246
247
248
249
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
 
# File 'lib/make_like_a_tree.rb', line 238

def add_child!(child)
  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



319
320
321
322
 
# File 'lib/make_like_a_tree.rb', line 319

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



188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/make_like_a_tree.rb', line 188

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

#assign_default_left_and_right(with_space_inside = 0) ⇒ Object

Place the item to the appropriate place as a root item



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

def assign_default_left_and_right(with_space_inside = 0)
  
  # Instead of creating nodes with 0,0 make this a root node BY DEFAULT even if no children are specified
  self[root_column] = self.id
  last_root_node = self.class.find(:first, :conditions => "#{scope_condition} AND #{parent_column} = 0 AND id != #{self.id}",
    :order => "#{right_col_name} DESC", :limit => 1)
  offset = last_root_node ? last_root_node[right_col_name] : 0
  
  self[left_col_name], self[right_col_name] = (offset+1), (offset + with_space_inside + 2)
end

#child? ⇒ Boolean

Returns true is this is a child node

Returns:

  • (Boolean) 


177
178
179
180
 
# File 'lib/make_like_a_tree.rb', line 177

def child?
  parent_id = self[parent_column]
  @is_child ||= (!(parent_id.to_i.zero?) && (self[left_col_name] > 1) && (self[right_col_name] > self[left_col_name]))
end

#child_can_be_added?(child) ⇒ Boolean

Tells you if a reparent might be invalid

Returns:

  • (Boolean) 


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

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



298
299
300
301
 
# File 'lib/make_like_a_tree.rb', line 298

def child_count
  return 0 unless might_have_children? # optimization shortcut
  self.class.count_by_sql("SELECT COUNT(id) FROM #{self.class.table_name} WHERE #{conditions_for_all_children}")
end

#conditions_for_all_children ⇒ Object

Get conditions for direct and indirect children of this record



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

def conditions_for_all_children
  "#{scope_condition} AND #{root_column} = #{self[root_column]} AND " +
  "#{depth_column} > #{self[depth_column]} AND " +
  "#{left_col_name} > #{self[left_col_name]} AND #{right_col_name} < #{self[right_col_name]}"
end

#conditions_for_self_and_siblings ⇒ Object

Get conditions to find myself and my siblings



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

def conditions_for_self_and_siblings
  "#{scope_condition} AND #{parent_column} = #{self[parent_column]}"
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



287
288
289
290
291
292
293
294
295
 
# File 'lib/make_like_a_tree.rb', line 287

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



357
358
359
360
 
# File 'lib/make_like_a_tree.rb', line 357

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



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

def full_set(extras = {})
  [self] + all_children
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



157
158
159
160
161
162
163
 
# File 'lib/make_like_a_tree.rb', line 157

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



213
214
215
 
# File 'lib/make_like_a_tree.rb', line 213

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) 


308
309
310
 
# File 'lib/make_like_a_tree.rb', line 308

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)



142
143
144
 
# File 'lib/make_like_a_tree.rb', line 142

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



71
72
73
74
75
76
77
78
79
80
81
82
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
 
# File 'lib/make_like_a_tree.rb', line 71

def move_to(idx)
  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 = [], []
  
    # Exhaust the range starting with the last element, determining a remap on the fly
    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
      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
      
      unless shift.zero? # Optimize - do not move nodes that stay in the same place
        condition_stmt = "#{left_col_name} >= #{e[left_col_name]} AND #{right_col_name} <= #{e[right_col_name]}"
        value_stmt_left = "#{left_col_name} + #{shift}"
        value_stmt_right = "#{right_col_name} + #{shift}"
    
        left_remaps.unshift(
          "WHEN (#{condition_stmt}) THEN (#{left_col_name} + #{shift})"
        )
        right_remaps.unshift(
          "WHEN (#{condition_stmt}) THEN (#{right_col_name} + #{shift})"
        )
      end
    end
  
    # If we are not a root node, scope the changes to our subtree only - this will win us some less writes
    update_condition = if root?
      scope_condition
    else
      "#{scope_condition} AND #{root_column} = #{self[root_column]}"
    end
    
    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)



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

def move_to_bottom
  move_to(-1)
end

#move_to_top ⇒ Object

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



147
148
149
 
# File 'lib/make_like_a_tree.rb', line 147

def move_to_top
  move_to(0)
end

#move_up ⇒ Object

Move the record down in the list (uses move_to)



137
138
139
 
# File 'lib/make_like_a_tree.rb', line 137

def move_up
  move_to(index_in_parent - 1)
end

#promote_to_root ⇒ Object

Make this item a root node



363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
 
# File 'lib/make_like_a_tree.rb', line 363

def promote_to_root
  transaction do
    my_width = child_count * 2
  
    # Stash the values because assign_default_left_and_right reassigns them
    old_left, old_right, old_root = self[left_col_name], self[right_col_name], self[root_column]
    self[parent_column] = 0 # Signal the root node
  
    assign_default_left_and_right(my_width)
    
    move_by = self[left_col_name] - old_left
    move_depth_by = self[depth_column]
  
    # 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}"
    )
    self.reload
  end
  true
end

#register_parent_id_before_update ⇒ Object 



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

def register_parent_id_before_update 
  @old_parent_id = self.class.connection.select_value("SELECT #{parent_column} FROM #{self.class.table_name} WHERE id = #{self.id}")
  true
end

#reload(*any_arguments) ⇒ Object

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



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

def reload(*any_arguments)
  @index_in_parent, @is_root, @is_child, @old_parent_id, @rerooted = nil, nil, nil, nil, nil
  super
end

#replant_after_update ⇒ Object 



395
396
397
398
399
400
401
402
403
404
405
406
 
# File 'lib/make_like_a_tree.rb', line 395

def replant_after_update
  if @old_parent_id.nil? || (@old_parent_id == self[parent_column])
    return true
  # If the new parent_id is nil, it means we are promoted to woot node
  elsif self[parent_column].nil? || self[parent_column].zero?
    promote_to_root
  else
    self.class.find(self[parent_column]).add_child(self)
  end

  true
end

#root? ⇒ Boolean

Returns true is this is a root thread.

Returns:

  • (Boolean) 


172
173
174
 
# File 'lib/make_like_a_tree.rb', line 172

def root?
  @is_root ||= (self[root_column].to_i.zero? ||  (self[root_column] == self.id))
end

#scope_hash_for_branch ⇒ Object

Returns scoping options suitable for fetching all children



325
326
327
 
# File 'lib/make_like_a_tree.rb', line 325

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



330
331
332
 
# File 'lib/make_like_a_tree.rb', line 330

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

#siblings ⇒ Object

Get immediate siblings, ordered



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

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

#siblings_and_self ⇒ Object

Get myself and siblings, ordered



352
353
354
 
# File 'lib/make_like_a_tree.rb', line 352

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

#unknown? ⇒ Boolean

Returns true if we have no idea what this is

Returns:

  • (Boolean) 


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

def unknown?
  !root? && !child?
end