1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
module ActiveRecord
module Acts #:nodoc:
module NestedSet #:nodoc:
def self.append_features(base)
super
base.extend(ClassMethods)
end
# This acts provides Nested Set functionality. Nested Set is similiar to Tree, but with
# the added feature that you can select the children and all of it's descendants with
# a single query. A good use case for this is a threaded post system, where you want
# to display every reply to a comment without multiple selects.
#
# A google search for "Nested Set" should point you in the direction to explain the
# data base theory. I figured a bunch of this from
# http://threebit.net/tutorials/nestedset/tutorial1.html
#
# Instead of picturing a leaf node structure with child pointing back to their parent,
# the best way to imagine how this works is to think of the parent entity surrounding all
# of it's children, and it's parent surrounding it, etc. Assuming that they are lined up
# horizontally, we store the left and right boundries in the database.
#
# Imagine:
# root
# |_ Child 1
# |_ Child 1.1
# |_ Child 1.2
# |_ Child 2
# |_ Child 2.1
# |_ Child 2.2
#
# If my cirlces in circles description didn't make sense, check out this sweet
# ASCII art:
#
# ___________________________________________________________________
# | Root |
# | ____________________________ ____________________________ |
# | | Child 1 | | Child 2 | |
# | | __________ _________ | | __________ _________ | |
# | | | C 1.1 | | C 1.2 | | | | C 2.1 | | C 2.2 | | |
# 1 2 3_________4 5________6 7 8 9_________10 11_______12 13 14
# | |___________________________| |___________________________| |
# |___________________________________________________________________|
#
# The numbers represent the left and right boundries. The table them might
# look like this:
# ID | PARENT | LEFT | RIGHT | DATA
# 1 | 0 | 1 | 14 | root
# 2 | 1 | 2 | 7 | Child 1
# 3 | 2 | 3 | 4 | Child 1.1
# 4 | 2 | 5 | 6 | Child 1.2
# 5 | 1 | 8 | 13 | Child 2
# 6 | 5 | 9 | 10 | Child 2.1
# 7 | 5 | 11 | 12 | Child 2.2
#
# So, to get all children of an entry, you
# SELECT * WHERE CHILD.LEFT IS BETWEEN PARENT.LEFT AND PARENT.RIGHT
#
# To get the count, it's (LEFT - RIGHT + 1)/2, etc.
#
# To get the direct parent, it falls back to using the PARENT_ID field.
#
# There are instance methods for all of these.
#
# The structure is good if you need to group things together; the downside is that
# keeping data integrity is a pain, and both adding and removing and entry
# require a full table write.
#
# This sets up a before_destroy trigger to prune the tree correctly if one of it's
# elements gets deleted.
#
module ClassMethods
# Configuration options are:
#
# * +parent_column+ - specifies the column name to use for keeping the position integer (default: parent_id)
# * +left_column+ - column name for left boundry data, default "lft"
# * +right_column+ - column name for right boundry data, default "rgt"
# * +scope+ - restricts what is to be considered a list. Given a symbol, it'll attach "_id"
# (if that hasn't been already) and use that as the foreign key restriction. It's also possible
# to give it an entire string that is interpolated if you need a tighter scope than just a foreign key.
# Example: <tt>acts_as_list :scope => 'todo_list_id = #{todo_list_id} AND completed = 0'</tt>
def acts_as_nested_set(options = {})
configuration = { :parent_column => "parent_id", :left_column => "lft", :right_column => "rgt", :scope => "1 = 1" }
configuration.update(options) if options.is_a?(Hash)
configuration[:scope] = "#{configuration[:scope]}_id".intern if configuration[:scope].is_a?(Symbol) && configuration[:scope].to_s !~ /_id$/
if configuration[:scope].is_a?(Symbol)
scope_condition_method = %(
def scope_condition
if #{configuration[:scope].to_s}.nil?
"#{configuration[:scope].to_s} IS NULL"
else
"#{configuration[:scope].to_s} = \#{#{configuration[:scope].to_s}}"
end
end
)
else
scope_condition_method = "def scope_condition() \"#{configuration[:scope]}\" end"
end
class_eval <<-EOV
include ActiveRecord::Acts::NestedSet::InstanceMethods
#{scope_condition_method}
def left_col_name() "#{configuration[:left_column]}" end
def right_col_name() "#{configuration[:right_column]}" end
def parent_column() "#{configuration[:parent_column]}" end
EOV
end
end
module InstanceMethods
# Returns true is this is a root node.
def root?
parent_id = self[parent_column]
(parent_id == 0 || parent_id.nil?) && (self[left_col_name] == 1) && (self[right_col_name] > self[left_col_name])
end
# Returns true is this is a child node
def child?
parent_id = self[parent_column]
!(parent_id == 0 || parent_id.nil?) && (self[left_col_name] > 1) && (self[right_col_name] > self[left_col_name])
end
# Returns true if we have no idea what this is
def unknown?
!root? && !child?
end
# Added 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
# balanaced.
def add_child( child )
self.reload
child.reload
if child.root?
raise "Adding sub-tree isn\'t currently supported"
else
if ( (self[left_col_name] == nil) || (self[right_col_name] == nil) )
# Looks like we're now the root node! Woo
self[left_col_name] = 1
self[right_col_name] = 4
# What do to do about validation?
return nil unless self.save
child[parent_column] = self.id
child[left_col_name] = 2
child[right_col_name]= 3
return child.save
else
# OK, we need to add and shift everything else to the right
child[parent_column] = self.id
right_bound = self[right_col_name]
child[left_col_name] = right_bound
child[right_col_name] = right_bound + 1
self[right_col_name] += 2
self.class.transaction {
self.class.update_all( "#{left_col_name} = (#{left_col_name} + 2)", "#{scope_condition} AND #{left_col_name} >= #{right_bound}" )
self.class.update_all( "#{right_col_name} = (#{right_col_name} + 2)", "#{scope_condition} AND #{right_col_name} >= #{right_bound}" )
self.save
child.save
}
end
end
end
# Returns the number of nested children of this object.
def children_count
return (self[right_col_name] - self[left_col_name] - 1)/2
end
# Returns a set of itself and all of it's nested children
def full_set
self.class.find(:all, :conditions => "#{scope_condition} AND (#{left_col_name} BETWEEN #{self[left_col_name]} and #{self[right_col_name]})" )
end
# Returns a set of all of it's children and nested children
def all_children
self.class.find(:all, :conditions => "#{scope_condition} AND (#{left_col_name} > #{self[left_col_name]}) and (#{right_col_name} < #{self[right_col_name]})" )
end
# Returns a set of only this entries immediate children
def direct_children
self.class.find(:all, :conditions => "#{scope_condition} and #{parent_column} = #{self.id}")
end
# Prunes a branch off of the tree, shifting all of the elements on the right
# back to the left so the counts still work.
def before_destroy
return if self[right_col_name].nil? || self[left_col_name].nil?
dif = self[right_col_name] - self[left_col_name] + 1
self.class.transaction {
self.class.delete_all( "#{scope_condition} and #{left_col_name} > #{self[left_col_name]} and #{right_col_name} < #{self[right_col_name]}" )
self.class.update_all( "#{left_col_name} = (#{left_col_name} - #{dif})", "#{scope_condition} AND #{left_col_name} >= #{self[right_col_name]}" )
self.class.update_all( "#{right_col_name} = (#{right_col_name} - #{dif} )", "#{scope_condition} AND #{right_col_name} >= #{self[right_col_name]}" )
}
end
end
end
end
end
|
