jro_apps/redmine Commit - r10646:bb4c530ba29c

1

module CollectiveIdea #:nodoc:

1

module CollectiveIdea #:nodoc:

2

module Acts #:nodoc:

2

module Acts #:nodoc:

3

module NestedSet #:nodoc:

3

module NestedSet #:nodoc:

4

5

# This acts provides Nested Set functionality. Nested Set is a smart way to implement

5

# This acts provides Nested Set functionality. Nested Set is a smart way to implement

6

# an _ordered_ tree, with the added feature that you can select the children and all of their

6

# an _ordered_ tree, with the added feature that you can select the children and all of their

7

# descendants with a single query. The drawback is that insertion or move need some complex

7

# descendants with a single query. The drawback is that insertion or move need some complex

8

# sql queries. But everything is done here by this module!

8

# sql queries. But everything is done here by this module!

9

#

9

#

10

# Nested sets are appropriate each time you want either an orderd tree (menus,

10

# Nested sets are appropriate each time you want either an orderd tree (menus,

11

# commercial categories) or an efficient way of querying big trees (threaded posts).

11

# commercial categories) or an efficient way of querying big trees (threaded posts).

12

#

12

#

13

# == API

13

# == API

14

#

14

#

15

# Methods names are aligned with acts_as_tree as much as possible to make replacment from one

15

# Methods names are aligned with acts_as_tree as much as possible to make replacment from one

16

# by another easier.

16

# by another easier.

17

#

17

#

18

# item.children.create(:name => "child1")

18

# item.children.create(:name => "child1")

19

#

19

#

20

21

# Configuration options are:

21

# Configuration options are:

22

#

22

#

23

# * +:parent_column+ - specifies the column name to use for keeping the position integer (default: parent_id)

23

# * +:parent_column+ - specifies the column name to use for keeping the position integer (default: parent_id)

24

# * +:left_column+ - column name for left boundry data, default "lft"

24

# * +:left_column+ - column name for left boundry data, default "lft"

25

# * +:right_column+ - column name for right boundry data, default "rgt"

25

# * +:right_column+ - column name for right boundry data, default "rgt"

26

# * +:scope+ - restricts what is to be considered a list. Given a symbol, it'll attach "_id"

26

# * +:scope+ - restricts what is to be considered a list. Given a symbol, it'll attach "_id"

27

# (if it hasn't been already) and use that as the foreign key restriction. You

27

# (if it hasn't been already) and use that as the foreign key restriction. You

28

# can also pass an array to scope by multiple attributes.

28

# can also pass an array to scope by multiple attributes.

29

# Example: <tt>acts_as_nested_set :scope => [:notable_id, :notable_type]</tt>

29

# Example: <tt>acts_as_nested_set :scope => [:notable_id, :notable_type]</tt>

30

# * +:dependent+ - behavior for cascading destroy. If set to :destroy, all the

30

# * +:dependent+ - behavior for cascading destroy. If set to :destroy, all the

31

# child objects are destroyed alongside this object by calling their destroy

31

# child objects are destroyed alongside this object by calling their destroy

32

# method. If set to :delete_all (default), all the child objects are deleted

32

# method. If set to :delete_all (default), all the child objects are deleted

33

# without calling their destroy method.

33

# without calling their destroy method.

34

# * +:counter_cache+ adds a counter cache for the number of children.

34

# * +:counter_cache+ adds a counter cache for the number of children.

35

# defaults to false.

35

# defaults to false.

36

# Example: <tt>acts_as_nested_set :counter_cache => :children_count</tt>

36

# Example: <tt>acts_as_nested_set :counter_cache => :children_count</tt>

37

#

37

#

38

# See CollectiveIdea::Acts::NestedSet::Model::ClassMethods for a list of class methods and

38

# See CollectiveIdea::Acts::NestedSet::Model::ClassMethods for a list of class methods and

39

# CollectiveIdea::Acts::NestedSet::Model for a list of instance methods added

39

# CollectiveIdea::Acts::NestedSet::Model for a list of instance methods added

40

# to acts_as_nested_set models

40

# to acts_as_nested_set models

41

def acts_as_nested_set(options = {})

41

def acts_as_nested_set(options = {})

42

options = {

42

options = {

43

:parent_column => 'parent_id',

43

:parent_column => 'parent_id',

44

:left_column => 'lft',

44

:left_column => 'lft',

45

:right_column => 'rgt',

45

:right_column => 'rgt',

46

:dependent => :delete_all, # or :destroy

46

:dependent => :delete_all, # or :destroy

47

:counter_cache => false,

47

:counter_cache => false,

48

:order => 'id'

48

:order => 'id'

49

}.merge(options)

49

}.merge(options)

50

51

if options[:scope].is_a?(Symbol) && options[:scope].to_s !~ /_id$/

51

if options[:scope].is_a?(Symbol) && options[:scope].to_s !~ /_id$/

52

options[:scope] = "#{options[:scope]}_id".intern

52

options[:scope] = "#{options[:scope]}_id".intern

53

end

53

end

54

55

class_attribute :acts_as_nested_set_options

55

class_attribute :acts_as_nested_set_options

56

self.acts_as_nested_set_options = options

56

self.acts_as_nested_set_options = options

57

58

include CollectiveIdea::Acts::NestedSet::Model

58

include CollectiveIdea::Acts::NestedSet::Model

59

include Columns

59

include Columns

60

extend Columns

60

extend Columns

61

62

belongs_to :parent, :class_name => self.base_class.to_s,

62

belongs_to :parent, :class_name => self.base_class.to_s,

63

:foreign_key => parent_column_name,

63

:foreign_key => parent_column_name,

64

:counter_cache => options[:counter_cache],

64

:counter_cache => options[:counter_cache],

65

:inverse_of => :children

65

:inverse_of => :children

66

has_many :children, :class_name => self.base_class.to_s,

66

has_many :children, :class_name => self.base_class.to_s,

67

:foreign_key => parent_column_name, :order => left_column_name,

67

:foreign_key => parent_column_name, :order => left_column_name,

68

:inverse_of => :parent,

68

:inverse_of => :parent,

69

:before_add => options[:before_add],

69

:before_add => options[:before_add],

70

:after_add => options[:after_add],

70

:after_add => options[:after_add],

71

:before_remove => options[:before_remove],

71

:before_remove => options[:before_remove],

72

:after_remove => options[:after_remove]

72

:after_remove => options[:after_remove]

73

74

attr_accessor :skip_before_destroy

74

attr_accessor :skip_before_destroy

75

76

before_create :set_default_left_and_right

76

before_create :set_default_left_and_right

77

before_save :store_new_parent

77

before_save :store_new_parent

78

after_save :move_to_new_parent

78

after_save :move_to_new_parent

79

before_destroy :destroy_descendants

79

before_destroy :destroy_descendants

80

81

# no assignment to structure fields

81

# no assignment to structure fields

82

[left_column_name, right_column_name].each do |column|

82

[left_column_name, right_column_name].each do |column|

83

module_eval <<-"end_eval", __FILE__, __LINE__

83

module_eval <<-"end_eval", __FILE__, __LINE__

84

def #{column}=(x)

84

def #{column}=(x)

85

raise ActiveRecord::ActiveRecordError, "Unauthorized assignment to #{column}: it's an internal field handled by acts_as_nested_set code, use move_to_* methods instead."

85

raise ActiveRecord::ActiveRecordError, "Unauthorized assignment to #{column}: it's an internal field handled by acts_as_nested_set code, use move_to_* methods instead."

86

end

86

end

87

end_eval

87

end_eval

88

end

88

end

89

90

define_model_callbacks :move

90

define_model_callbacks :move

91

end

91

end

92

93

module Model

93

module Model

94

extend ActiveSupport::Concern

94

extend ActiveSupport::Concern

95

96

module ClassMethods

96

module ClassMethods

97

# Returns the first root

97

# Returns the first root

98

def root

98

def root

99

roots.first

99

roots.first

100

end

100

end

101

102

def roots

102

def roots

103

where(parent_column_name => nil).order(quoted_left_column_name)

103

where(parent_column_name => nil).order(quoted_left_column_name)

104

end

104

end

105

106

def leaves

106

def leaves

107

where("#{quoted_right_column_name} - #{quoted_left_column_name} = 1").order(quoted_left_column_name)

107

where("#{quoted_right_column_name} - #{quoted_left_column_name} = 1").order(quoted_left_column_name)

108

end

108

end

109

110

def valid?

110

def valid?

111

left_and_rights_valid? && no_duplicates_for_columns? && all_roots_valid?

111

left_and_rights_valid? && no_duplicates_for_columns? && all_roots_valid?

112

end

112

end

113

114

def left_and_rights_valid?

114

def left_and_rights_valid?

115

joins("LEFT OUTER JOIN #{quoted_table_name} AS parent ON " +

115

joins("LEFT OUTER JOIN #{quoted_table_name} AS parent ON " +

116

"#{quoted_table_name}.#{quoted_parent_column_name} = parent.#{primary_key}").

116

"#{quoted_table_name}.#{quoted_parent_column_name} = parent.#{primary_key}").

117

where(

117

where(

118

"#{quoted_table_name}.#{quoted_left_column_name} IS NULL OR " +

118

"#{quoted_table_name}.#{quoted_left_column_name} IS NULL OR " +

119

"#{quoted_table_name}.#{quoted_right_column_name} IS NULL OR " +

119

"#{quoted_table_name}.#{quoted_right_column_name} IS NULL OR " +

120

"#{quoted_table_name}.#{quoted_left_column_name} >= " +

120

"#{quoted_table_name}.#{quoted_left_column_name} >= " +

121

"#{quoted_table_name}.#{quoted_right_column_name} OR " +

121

"#{quoted_table_name}.#{quoted_right_column_name} OR " +

122

"(#{quoted_table_name}.#{quoted_parent_column_name} IS NOT NULL AND " +

122

"(#{quoted_table_name}.#{quoted_parent_column_name} IS NOT NULL AND " +

123

"(#{quoted_table_name}.#{quoted_left_column_name} <= parent.#{quoted_left_column_name} OR " +

123

"(#{quoted_table_name}.#{quoted_left_column_name} <= parent.#{quoted_left_column_name} OR " +

124

"#{quoted_table_name}.#{quoted_right_column_name} >= parent.#{quoted_right_column_name}))"

124

"#{quoted_table_name}.#{quoted_right_column_name} >= parent.#{quoted_right_column_name}))"

125

).count == 0

125

).count == 0

126

end

126

end

127

128

def no_duplicates_for_columns?

128

def no_duplicates_for_columns?

129

scope_string = Array(acts_as_nested_set_options[:scope]).map do |c|

129

scope_string = Array(acts_as_nested_set_options[:scope]).map do |c|

130

connection.quote_column_name(c)

130

connection.quote_column_name(c)

131

end.push(nil).join(", ")

131

end.push(nil).join(", ")

132

[quoted_left_column_name, quoted_right_column_name].all? do |column|

132

[quoted_left_column_name, quoted_right_column_name].all? do |column|

133

# No duplicates

133

# No duplicates

134

select("#{scope_string}#{column}, COUNT(#{column})").

134

select("#{scope_string}#{column}, COUNT(#{column})").

135

group("#{scope_string}#{column}").

135

group("#{scope_string}#{column}").

136

having("COUNT(#{column}) > 1").

136

having("COUNT(#{column}) > 1").

137

first.nil?

137

first.nil?

138

end

138

end

139

end

139

end

140

141

# Wrapper for each_root_valid? that can deal with scope.

141

# Wrapper for each_root_valid? that can deal with scope.

142

def all_roots_valid?

142

def all_roots_valid?

143

if acts_as_nested_set_options[:scope]

143

if acts_as_nested_set_options[:scope]

144

roots.group(scope_column_names).group_by{|record| scope_column_names.collect{|col| record.send(col.to_sym)}}.all? do |scope, grouped_roots|

144

roots.group(scope_column_names).group_by{|record| scope_column_names.collect{|col| record.send(col.to_sym)}}.all? do |scope, grouped_roots|

145

each_root_valid?(grouped_roots)

145

each_root_valid?(grouped_roots)

146

end

146

end

147

else

147

else

148

each_root_valid?(roots)

148

each_root_valid?(roots)

149

end

149

end

150

end

150

end

151

152

def each_root_valid?(roots_to_validate)

152

def each_root_valid?(roots_to_validate)

153

left = right = 0

153

left = right = 0

154

roots_to_validate.all? do |root|

154

roots_to_validate.all? do |root|

155

(root.left > left && root.right > right).tap do

155

(root.left > left && root.right > right).tap do

156

left = root.left

156

left = root.left

157

right = root.right

157

right = root.right

158

end

158

end

159

end

159

end

160

end

160

end

161

162

# Rebuilds the left & rights if unset or invalid.

162

# Rebuilds the left & rights if unset or invalid.

163

# Also very useful for converting from acts_as_tree.

163

# Also very useful for converting from acts_as_tree.

164

def rebuild!(validate_nodes = true)

164

def rebuild!(validate_nodes = true)

165

# Don't rebuild a valid tree.

165

# Don't rebuild a valid tree.

166

return true if valid?

166

return true if valid?

167

168

scope = lambda{|node|}

168

scope = lambda{|node|}

169

if acts_as_nested_set_options[:scope]

169

if acts_as_nested_set_options[:scope]

170

scope = lambda{|node|

170

scope = lambda{|node|

171

scope_column_names.inject(""){|str, column_name|

171

scope_column_names.inject(""){|str, column_name|

172

str << "AND #{connection.quote_column_name(column_name)} = #{connection.quote(node.send(column_name.to_sym))} "

172

str << "AND #{connection.quote_column_name(column_name)} = #{connection.quote(node.send(column_name.to_sym))} "

173

}

173

}

174

}

174

}

175

end

175

end

176

indices = {}

176

indices = {}

177

178

set_left_and_rights = lambda do |node|

178

set_left_and_rights = lambda do |node|

179

# set left

179

# set left

180

node[left_column_name] = indices[scope.call(node)] += 1

180

node[left_column_name] = indices[scope.call(node)] += 1

181

# find

181

# find

182

where(["#{quoted_parent_column_name} = ? #{scope.call(node)}", node]).order(acts_as_nested_set_options[:order]).each{|n| set_left_and_rights.call(n) }

182

where(["#{quoted_parent_column_name} = ? #{scope.call(node)}", node]).order(acts_as_nested_set_options[:order]).each{|n| set_left_and_rights.call(n) }

183

# set right

183

# set right

184

node[right_column_name] = indices[scope.call(node)] += 1

184

node[right_column_name] = indices[scope.call(node)] += 1

185

node.save!(:validate => validate_nodes)

185

node.save!(:validate => validate_nodes)

186

end

186

end

187

188

# Find root node(s)

188

# Find root node(s)

189

root_nodes = where("#{quoted_parent_column_name} IS NULL").order("#{~~quoted_left_column_name~~}, #{~~quoted_right_column_name~~}~~, id"~~).each do |root_node|

189

root_nodes = where("#{quoted_parent_column_name} IS NULL").order(acts_as_nested_set_options[:order]).each do |root_node|

190

# setup index for this scope

190

# setup index for this scope

191

indices[scope.call(root_node)] ||= 0

191

indices[scope.call(root_node)] ||= 0

192

set_left_and_rights.call(root_node)

192

set_left_and_rights.call(root_node)

193

end

193

end

194

end

194

end

195

196

# Iterates over tree elements and determines the current level in the tree.

196

# Iterates over tree elements and determines the current level in the tree.

197

# Only accepts default ordering, odering by an other column than lft

197

# Only accepts default ordering, odering by an other column than lft

198

# does not work. This method is much more efficent than calling level

198

# does not work. This method is much more efficent than calling level

199

# because it doesn't require any additional database queries.

199

# because it doesn't require any additional database queries.

200

#

200

#

201

# Example:

201

# Example:

202

# Category.each_with_level(Category.root.self_and_descendants) do |o, level|

202

# Category.each_with_level(Category.root.self_and_descendants) do |o, level|

203

#

203

#

204

def each_with_level(objects)

204

def each_with_level(objects)

205

path = [nil]

205

path = [nil]

206

objects.each do |o|

206

objects.each do |o|

207

if o.parent_id != path.last

207

if o.parent_id != path.last

208

# we are on a new level, did we decent or ascent?

208

# we are on a new level, did we decent or ascent?

209

if path.include?(o.parent_id)

209

if path.include?(o.parent_id)

210

# remove wrong wrong tailing paths elements

210

# remove wrong wrong tailing paths elements

211

path.pop while path.last != o.parent_id

211

path.pop while path.last != o.parent_id

212

else

212

else

213

path << o.parent_id

213

path << o.parent_id

214

end

214

end

215

end

215

end

216

yield(o, path.length - 1)

216

yield(o, path.length - 1)

217

end

217

end

218

end

218

end

219

end

219

end

220

221

# 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.

221

# 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.

222

#

222

#

223

# category.self_and_descendants.count

223

# category.self_and_descendants.count

224

# category.ancestors.find(:all, :conditions => "name like '%foo%'")

224

# category.ancestors.find(:all, :conditions => "name like '%foo%'")

225

226

# Value of the parent column

226

# Value of the parent column

227

def parent_id

227

def parent_id

228

self[parent_column_name]

228

self[parent_column_name]

229

end

229

end

230

231

# Value of the left column

231

# Value of the left column

232

def left

232

def left

233

self[left_column_name]

233

self[left_column_name]

234

end

234

end

235

236

# Value of the right column

236

# Value of the right column

237

def right

237

def right

238

self[right_column_name]

238

self[right_column_name]

239

end

239

end

240

241

# Returns true if this is a root node.

241

# Returns true if this is a root node.

242

def root?

242

def root?

243

parent_id.nil?

243

parent_id.nil?

244

end

244

end

245

246

def leaf?

246

def leaf?

247

new_record? || (right - left == 1)

247

new_record? || (right - left == 1)

248

end

248

end

249

250

# Returns true is this is a child node

250

# Returns true is this is a child node

251

def child?

251

def child?

252

!parent_id.nil?

252

!parent_id.nil?

253

end

253

end

254

255

# Returns root

255

# Returns root

256

def root

256

def root

257

self_and_ancestors.where(parent_column_name => nil).first

257

self_and_ancestors.where(parent_column_name => nil).first

258

end

258

end

259

260

# Returns the array of all parents and self

260

# Returns the array of all parents and self

261

def self_and_ancestors

261

def self_and_ancestors

262

nested_set_scope.where([

262

nested_set_scope.where([

263

"#{self.class.quoted_table_name}.#{quoted_left_column_name} <= ? AND #{self.class.quoted_table_name}.#{quoted_right_column_name} >= ?", left, right

263

"#{self.class.quoted_table_name}.#{quoted_left_column_name} <= ? AND #{self.class.quoted_table_name}.#{quoted_right_column_name} >= ?", left, right

264

])

264

])

265

end

265

end

266

267

# Returns an array of all parents

267

# Returns an array of all parents

268

def ancestors

268

def ancestors

269

without_self self_and_ancestors

269

without_self self_and_ancestors

270

end

270

end

271

272

# Returns the array of all children of the parent, including self

272

# Returns the array of all children of the parent, including self

273

def self_and_siblings

273

def self_and_siblings

274

nested_set_scope.where(parent_column_name => parent_id)

274

nested_set_scope.where(parent_column_name => parent_id)

275

end

275

end

276

277

# Returns the array of all children of the parent, except self

277

# Returns the array of all children of the parent, except self

278

def siblings

278

def siblings

279

without_self self_and_siblings

279

without_self self_and_siblings

280

end

280

end

281

282

# Returns a set of all of its nested children which do not have children

282

# Returns a set of all of its nested children which do not have children

283

def leaves

283

def leaves

284

descendants.where("#{self.class.quoted_table_name}.#{quoted_right_column_name} - #{self.class.quoted_table_name}.#{quoted_left_column_name} = 1")

284

descendants.where("#{self.class.quoted_table_name}.#{quoted_right_column_name} - #{self.class.quoted_table_name}.#{quoted_left_column_name} = 1")

285

end

285

end

286

287

# Returns the level of this object in the tree

287

# Returns the level of this object in the tree

288

# root level is 0

288

# root level is 0

289

def level

289

def level

290

parent_id.nil? ? 0 : ancestors.count

290

parent_id.nil? ? 0 : ancestors.count

291

end

291

end

292

293

# Returns a set of itself and all of its nested children

293

# Returns a set of itself and all of its nested children

294

def self_and_descendants

294

def self_and_descendants

295

nested_set_scope.where([

295

nested_set_scope.where([

296

"#{self.class.quoted_table_name}.#{quoted_left_column_name} >= ? AND #{self.class.quoted_table_name}.#{quoted_right_column_name} <= ?", left, right

296

"#{self.class.quoted_table_name}.#{quoted_left_column_name} >= ? AND #{self.class.quoted_table_name}.#{quoted_right_column_name} <= ?", left, right

297

])

297

])

298

end

298

end

299

300

# Returns a set of all of its children and nested children

300

# Returns a set of all of its children and nested children

301

def descendants

301

def descendants

302

without_self self_and_descendants

302

without_self self_and_descendants

303

end

303

end

304

305

def is_descendant_of?(other)

305

def is_descendant_of?(other)

306

other.left < self.left && self.left < other.right && same_scope?(other)

306

other.left < self.left && self.left < other.right && same_scope?(other)

307

end

307

end

308

309

def is_or_is_descendant_of?(other)

309

def is_or_is_descendant_of?(other)

310

other.left <= self.left && self.left < other.right && same_scope?(other)

310

other.left <= self.left && self.left < other.right && same_scope?(other)

311

end

311

end

312

313

def is_ancestor_of?(other)

313

def is_ancestor_of?(other)

314

self.left < other.left && other.left < self.right && same_scope?(other)

314

self.left < other.left && other.left < self.right && same_scope?(other)

315

end

315

end

316

317

def is_or_is_ancestor_of?(other)

317

def is_or_is_ancestor_of?(other)

318

self.left <= other.left && other.left < self.right && same_scope?(other)

318

self.left <= other.left && other.left < self.right && same_scope?(other)

319

end

319

end

320

321

# Check if other model is in the same scope

321

# Check if other model is in the same scope

322

def same_scope?(other)

322

def same_scope?(other)

323

Array(acts_as_nested_set_options[:scope]).all? do |attr|

323

Array(acts_as_nested_set_options[:scope]).all? do |attr|

324

self.send(attr) == other.send(attr)

324

self.send(attr) == other.send(attr)

325

end

325

end

326

end

326

end

327

328

# Find the first sibling to the left

328

# Find the first sibling to the left

329

def left_sibling

329

def left_sibling

330

siblings.where(["#{self.class.quoted_table_name}.#{quoted_left_column_name} < ?", left]).

330

siblings.where(["#{self.class.quoted_table_name}.#{quoted_left_column_name} < ?", left]).

331

order("#{self.class.quoted_table_name}.#{quoted_left_column_name} DESC").last

331

order("#{self.class.quoted_table_name}.#{quoted_left_column_name} DESC").last

332

end

332

end

333

334

# Find the first sibling to the right

334

# Find the first sibling to the right

335

def right_sibling

335

def right_sibling

336

siblings.where(["#{self.class.quoted_table_name}.#{quoted_left_column_name} > ?", left]).first

336

siblings.where(["#{self.class.quoted_table_name}.#{quoted_left_column_name} > ?", left]).first

337

end

337

end

338

339

# Shorthand method for finding the left sibling and moving to the left of it.

339

# Shorthand method for finding the left sibling and moving to the left of it.

340

def move_left

340

def move_left

341

move_to_left_of left_sibling

341

move_to_left_of left_sibling

342

end

342

end

343

344

# Shorthand method for finding the right sibling and moving to the right of it.

344

# Shorthand method for finding the right sibling and moving to the right of it.

345

def move_right

345

def move_right

346

move_to_right_of right_sibling

346

move_to_right_of right_sibling

347

end

347

end

348

349

# Move the node to the left of another node (you can pass id only)

349

# Move the node to the left of another node (you can pass id only)

350

def move_to_left_of(node)

350

def move_to_left_of(node)

351

move_to node, :left

351

move_to node, :left

352

end

352

end

353

354

# Move the node to the left of another node (you can pass id only)

354

# Move the node to the left of another node (you can pass id only)

355

def move_to_right_of(node)

355

def move_to_right_of(node)

356

move_to node, :right

356

move_to node, :right

357

end

357

end

358

359

# Move the node to the child of another node (you can pass id only)

359

# Move the node to the child of another node (you can pass id only)

360

def move_to_child_of(node)

360

def move_to_child_of(node)

361

move_to node, :child

361

move_to node, :child

362

end

362

end

363

364

# Move the node to root nodes

364

# Move the node to root nodes

365

def move_to_root

365

def move_to_root

366

move_to nil, :root

366

move_to nil, :root

367

end

367

end

368

369

def move_possible?(target)

369

def move_possible?(target)

370

self != target && # Can't target self

370

self != target && # Can't target self

371

same_scope?(target) && # can't be in different scopes

371

same_scope?(target) && # can't be in different scopes

372

# !(left..right).include?(target.left..target.right) # this needs tested more

372

# !(left..right).include?(target.left..target.right) # this needs tested more

373

# detect impossible move

373

# detect impossible move

374

!((left <= target.left && right >= target.left) or (left <= target.right && right >= target.right))

374

!((left <= target.left && right >= target.left) or (left <= target.right && right >= target.right))

375

end

375

end

376

377

def to_text

377

def to_text

378

self_and_descendants.map do |node|

378

self_and_descendants.map do |node|

379

"#{'*'*(node.level+1)} #{node.id} #{node.to_s} (#{node.parent_id}, #{node.left}, #{node.right})"

379

"#{'*'*(node.level+1)} #{node.id} #{node.to_s} (#{node.parent_id}, #{node.left}, #{node.right})"

380

end.join("\n")

380

end.join("\n")

381

end

381

end

382

383

protected

383

protected

384

385

def without_self(scope)

385

def without_self(scope)

386

scope.where(["#{self.class.quoted_table_name}.#{self.class.primary_key} != ?", self])

386

scope.where(["#{self.class.quoted_table_name}.#{self.class.primary_key} != ?", self])

387

end

387

end

388

389

# All nested set queries should use this nested_set_scope, which performs finds on

389

# All nested set queries should use this nested_set_scope, which performs finds on

390

# the base ActiveRecord class, using the :scope declared in the acts_as_nested_set

390

# the base ActiveRecord class, using the :scope declared in the acts_as_nested_set

391

# declaration.

391

# declaration.

392

def nested_set_scope(options = {})

392

def nested_set_scope(options = {})

393

options = {:order => "#{self.class.quoted_table_name}.#{quoted_left_column_name}"}.merge(options)

393

options = {:order => "#{self.class.quoted_table_name}.#{quoted_left_column_name}"}.merge(options)

394

scopes = Array(acts_as_nested_set_options[:scope])

394

scopes = Array(acts_as_nested_set_options[:scope])

395

options[:conditions] = scopes.inject({}) do |conditions,attr|

395

options[:conditions] = scopes.inject({}) do |conditions,attr|

396

conditions.merge attr => self[attr]

396

conditions.merge attr => self[attr]

397

end unless scopes.empty?

397

end unless scopes.empty?

398

self.class.base_class.scoped options

398

self.class.base_class.scoped options

399

end

399

end

400

401

def store_new_parent

401

def store_new_parent

402

@move_to_new_parent_id = send("#{parent_column_name}_changed?") ? parent_id : false

402

@move_to_new_parent_id = send("#{parent_column_name}_changed?") ? parent_id : false

403

true # force callback to return true

403

true # force callback to return true

404

end

404

end

405

406

def move_to_new_parent

406

def move_to_new_parent

407

if @move_to_new_parent_id.nil?

407

if @move_to_new_parent_id.nil?

408

move_to_root

408

move_to_root

409

elsif @move_to_new_parent_id

409

elsif @move_to_new_parent_id

410

move_to_child_of(@move_to_new_parent_id)

410

move_to_child_of(@move_to_new_parent_id)

411

end

411

end

412

end

412

end

413

414

# on creation, set automatically lft and rgt to the end of the tree

414

# on creation, set automatically lft and rgt to the end of the tree

415

def set_default_left_and_right

415

def set_default_left_and_right

416

highest_right_row = nested_set_scope(:order => "#{quoted_right_column_name} desc").find(:first, :limit => 1,:lock => true )

416

highest_right_row = nested_set_scope(:order => "#{quoted_right_column_name} desc").find(:first, :limit => 1,:lock => true )

417

maxright = highest_right_row ? (highest_right_row[right_column_name] || 0) : 0

417

maxright = highest_right_row ? (highest_right_row[right_column_name] || 0) : 0

418

# adds the new node to the right of all existing nodes

418

# adds the new node to the right of all existing nodes

419

self[left_column_name] = maxright + 1

419

self[left_column_name] = maxright + 1

420

self[right_column_name] = maxright + 2

420

self[right_column_name] = maxright + 2

421

end

421

end

422

423

def in_tenacious_transaction(&block)

423

def in_tenacious_transaction(&block)

424

retry_count = 0

424

retry_count = 0

425

begin

425

begin

426

transaction(&block)

426

transaction(&block)

427

rescue ActiveRecord::StatementInvalid => error

427

rescue ActiveRecord::StatementInvalid => error

428

raise unless connection.open_transactions.zero?

428

raise unless connection.open_transactions.zero?

429

raise unless error.message =~ /Deadlock found when trying to get lock|Lock wait timeout exceeded/

429

raise unless error.message =~ /Deadlock found when trying to get lock|Lock wait timeout exceeded/

430

raise unless retry_count < 10

430

raise unless retry_count < 10

431

retry_count += 1

431

retry_count += 1

432

logger.info "Deadlock detected on retry #{retry_count}, restarting transaction"

432

logger.info "Deadlock detected on retry #{retry_count}, restarting transaction"

433

sleep(rand(retry_count)*0.1) # Aloha protocol

433

sleep(rand(retry_count)*0.1) # Aloha protocol

434

retry

434

retry

435

end

435

end

436

end

436

end

437

438

# Prunes a branch off of the tree, shifting all of the elements on the right

438

# Prunes a branch off of the tree, shifting all of the elements on the right

439

# back to the left so the counts still work.

439

# back to the left so the counts still work.

440

def destroy_descendants

440

def destroy_descendants

441

return if right.nil? || left.nil? || skip_before_destroy

441

return if right.nil? || left.nil? || skip_before_destroy

442

443

in_tenacious_transaction do

443

in_tenacious_transaction do

444

reload_nested_set

444

reload_nested_set

445

# select the rows in the model that extend past the deletion point and apply a lock

445

# select the rows in the model that extend past the deletion point and apply a lock

446

self.class.base_class.find(:all,

446

self.class.base_class.find(:all,

447

:select => "id",

447

:select => "id",

448

:conditions => ["#{quoted_left_column_name} >= ?", left],

448

:conditions => ["#{quoted_left_column_name} >= ?", left],

449

:lock => true

449

:lock => true

450

)

450

)

451

452

if acts_as_nested_set_options[:dependent] == :destroy

452

if acts_as_nested_set_options[:dependent] == :destroy

453

descendants.each do |model|

453

descendants.each do |model|

454

model.skip_before_destroy = true

454

model.skip_before_destroy = true

455

model.destroy

455

model.destroy

456

end

456

end

457

else

457

else

458

nested_set_scope.delete_all(

458

nested_set_scope.delete_all(

459

["#{quoted_left_column_name} > ? AND #{quoted_right_column_name} < ?",

459

["#{quoted_left_column_name} > ? AND #{quoted_right_column_name} < ?",

460

left, right]

460

left, right]

461

)

461

)

462

end

462

end

463

464

# update lefts and rights for remaining nodes

464

# update lefts and rights for remaining nodes

465

diff = right - left + 1

465

diff = right - left + 1

466

nested_set_scope.update_all(

466

nested_set_scope.update_all(

467

["#{quoted_left_column_name} = (#{quoted_left_column_name} - ?)", diff],

467

["#{quoted_left_column_name} = (#{quoted_left_column_name} - ?)", diff],

468

["#{quoted_left_column_name} > ?", right]

468

["#{quoted_left_column_name} > ?", right]

469

)

469

)

470

nested_set_scope.update_all(

470

nested_set_scope.update_all(

471

["#{quoted_right_column_name} = (#{quoted_right_column_name} - ?)", diff],

471

["#{quoted_right_column_name} = (#{quoted_right_column_name} - ?)", diff],

472

["#{quoted_right_column_name} > ?", right]

472

["#{quoted_right_column_name} > ?", right]

473

)

473

)

474

475

reload

475

reload

476

# Don't allow multiple calls to destroy to corrupt the set

476

# Don't allow multiple calls to destroy to corrupt the set

477

self.skip_before_destroy = true

477

self.skip_before_destroy = true

478

end

478

end

479

end

479

end

480

481

# reload left, right, and parent

481

# reload left, right, and parent

482

def reload_nested_set

482

def reload_nested_set

483

reload(

483

reload(

484

:select => "#{quoted_left_column_name}, #{quoted_right_column_name}, #{quoted_parent_column_name}",

484

:select => "#{quoted_left_column_name}, #{quoted_right_column_name}, #{quoted_parent_column_name}",

485

:lock => true

485

:lock => true

486

)

486

)

487

end

487

end

488

489

def move_to(target, position)

489

def move_to(target, position)

490

raise ActiveRecord::ActiveRecordError, "You cannot move a new node" if self.new_record?

490

raise ActiveRecord::ActiveRecordError, "You cannot move a new node" if self.new_record?

491

run_callbacks :move do

491

run_callbacks :move do

492

in_tenacious_transaction do

492

in_tenacious_transaction do

493

if target.is_a? self.class.base_class

493

if target.is_a? self.class.base_class

494

target.reload_nested_set

494

target.reload_nested_set

495

elsif position != :root

495

elsif position != :root

496

# load object if node is not an object

496

# load object if node is not an object

497

target = nested_set_scope.find(target)

497

target = nested_set_scope.find(target)

498

end

498

end

499

self.reload_nested_set

499

self.reload_nested_set

500

501

unless position == :root || move_possible?(target)

501

unless position == :root || move_possible?(target)

502

raise ActiveRecord::ActiveRecordError, "Impossible move, target node cannot be inside moved tree."

502

raise ActiveRecord::ActiveRecordError, "Impossible move, target node cannot be inside moved tree."

503

end

503

end

504

505

bound = case position

505

bound = case position

506

when :child; target[right_column_name]

506

when :child; target[right_column_name]

507

when :left; target[left_column_name]

507

when :left; target[left_column_name]

508

when :right; target[right_column_name] + 1

508

when :right; target[right_column_name] + 1

509

when :root; 1

509

when :root; 1

510

else raise ActiveRecord::ActiveRecordError, "Position should be :child, :left, :right or :root ('#{position}' received)."

510

else raise ActiveRecord::ActiveRecordError, "Position should be :child, :left, :right or :root ('#{position}' received)."

511

end

511

end

512

513

if bound > self[right_column_name]

513

if bound > self[right_column_name]

514

bound = bound - 1

514

bound = bound - 1

515

other_bound = self[right_column_name] + 1

515

other_bound = self[right_column_name] + 1

516

else

516

else

517

other_bound = self[left_column_name] - 1

517

other_bound = self[left_column_name] - 1

518

end

518

end

519

520

# there would be no change

520

# there would be no change

521

return if bound == self[right_column_name] || bound == self[left_column_name]

521

return if bound == self[right_column_name] || bound == self[left_column_name]

522

523

# we have defined the boundaries of two non-overlapping intervals,

523

# we have defined the boundaries of two non-overlapping intervals,

524

# so sorting puts both the intervals and their boundaries in order

524

# so sorting puts both the intervals and their boundaries in order

525

a, b, c, d = [self[left_column_name], self[right_column_name], bound, other_bound].sort

525

a, b, c, d = [self[left_column_name], self[right_column_name], bound, other_bound].sort

526

527

# select the rows in the model between a and d, and apply a lock

527

# select the rows in the model between a and d, and apply a lock

528

self.class.base_class.select('id').lock(true).where(

528

self.class.base_class.select('id').lock(true).where(

529

["#{quoted_left_column_name} >= :a and #{quoted_right_column_name} <= :d", {:a => a, :d => d}]

529

["#{quoted_left_column_name} >= :a and #{quoted_right_column_name} <= :d", {:a => a, :d => d}]

530

)

530

)

531

532

new_parent = case position

532

new_parent = case position

533

when :child; target.id

533

when :child; target.id

534

when :root; nil

534

when :root; nil

535

else target[parent_column_name]

535

else target[parent_column_name]

536

end

536

end

537

538

self.nested_set_scope.update_all([

538

self.nested_set_scope.update_all([

539

"#{quoted_left_column_name} = CASE " +

539

"#{quoted_left_column_name} = CASE " +

540

"WHEN #{quoted_left_column_name} BETWEEN :a AND :b " +

540

"WHEN #{quoted_left_column_name} BETWEEN :a AND :b " +

541

"THEN #{quoted_left_column_name} + :d - :b " +

541

"THEN #{quoted_left_column_name} + :d - :b " +

542

"WHEN #{quoted_left_column_name} BETWEEN :c AND :d " +

542

"WHEN #{quoted_left_column_name} BETWEEN :c AND :d " +

543

"THEN #{quoted_left_column_name} + :a - :c " +

543

"THEN #{quoted_left_column_name} + :a - :c " +

544

"ELSE #{quoted_left_column_name} END, " +

544

"ELSE #{quoted_left_column_name} END, " +

545

"#{quoted_right_column_name} = CASE " +

545

"#{quoted_right_column_name} = CASE " +

546

"WHEN #{quoted_right_column_name} BETWEEN :a AND :b " +

546

"WHEN #{quoted_right_column_name} BETWEEN :a AND :b " +

547

"THEN #{quoted_right_column_name} + :d - :b " +

547

"THEN #{quoted_right_column_name} + :d - :b " +

548

"WHEN #{quoted_right_column_name} BETWEEN :c AND :d " +

548

"WHEN #{quoted_right_column_name} BETWEEN :c AND :d " +

549

"THEN #{quoted_right_column_name} + :a - :c " +

549

"THEN #{quoted_right_column_name} + :a - :c " +

550

"ELSE #{quoted_right_column_name} END, " +

550

"ELSE #{quoted_right_column_name} END, " +

551

"#{quoted_parent_column_name} = CASE " +

551

"#{quoted_parent_column_name} = CASE " +

552

"WHEN #{self.class.base_class.primary_key} = :id THEN :new_parent " +

552

"WHEN #{self.class.base_class.primary_key} = :id THEN :new_parent " +

553

"ELSE #{quoted_parent_column_name} END",

553

"ELSE #{quoted_parent_column_name} END",

554

{:a => a, :b => b, :c => c, :d => d, :id => self.id, :new_parent => new_parent}

554

{:a => a, :b => b, :c => c, :d => d, :id => self.id, :new_parent => new_parent}

555

])

555

])

556

end

556

end

557

target.reload_nested_set if target

557

target.reload_nested_set if target

558

self.reload_nested_set

558

self.reload_nested_set

559

end

559

end

560

end

560

end

561

562

end

562

end

563

564

# Mixed into both classes and instances to provide easy access to the column names

564

# Mixed into both classes and instances to provide easy access to the column names

565

module Columns

565

module Columns

566

def left_column_name

566

def left_column_name

567

acts_as_nested_set_options[:left_column]

567

acts_as_nested_set_options[:left_column]

568

end

568

end

569

570

def right_column_name

570

def right_column_name

571

acts_as_nested_set_options[:right_column]

571

acts_as_nested_set_options[:right_column]

572

end

572

end

573

574

def parent_column_name

574

def parent_column_name

575

acts_as_nested_set_options[:parent_column]

575

acts_as_nested_set_options[:parent_column]

576

end

576

end

577

578

def scope_column_names

578

def scope_column_names

579

Array(acts_as_nested_set_options[:scope])

579

Array(acts_as_nested_set_options[:scope])

580

end

580

end

581

582

def quoted_left_column_name

582

def quoted_left_column_name

583

connection.quote_column_name(left_column_name)

583

connection.quote_column_name(left_column_name)

584

end

584

end

585

586

def quoted_right_column_name

586

def quoted_right_column_name

587

connection.quote_column_name(right_column_name)

587

connection.quote_column_name(right_column_name)

588

end

588

end

589

590

def quoted_parent_column_name

590

def quoted_parent_column_name

591

connection.quote_column_name(parent_column_name)

591

connection.quote_column_name(parent_column_name)

592

end

592

end

593

594

def quoted_scope_column_names

594

def quoted_scope_column_names

595

scope_column_names.collect {|column_name| connection.quote_column_name(column_name) }

595

scope_column_names.collect {|column_name| connection.quote_column_name(column_name) }

596

end

596

end

597

end

597

end

598

599

end

599

end

600

end

600

end

601

end

601

end

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

             module CollectiveIdea #:nodoc:
               module Acts #:nodoc:
                 module NestedSet #:nodoc:
                   # This acts provides Nested Set functionality. Nested Set is a smart way to implement
                   # an _ordered_ tree, with the added feature that you can select the children and all of their
                   # descendants with a single query. The drawback is that insertion or move need some complex
                   # sql queries. But everything is done here by this module!
                   #
                   # Nested sets are appropriate each time you want either an orderd tree (menus,
                   # commercial categories) or an efficient way of querying big trees (threaded posts).
                   #
                   # == API
                   #
                   # Methods names are aligned with acts_as_tree as much as possible to make replacment from one
                   # by another easier.
                   #
                   #   item.children.create(:name => "child1")
                   #
                   # 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 it hasn't been already) and use that as the foreign key restriction. You
                   #   can also pass an array to scope by multiple attributes.
                   #   Example: <tt>acts_as_nested_set :scope => [:notable_id, :notable_type]</tt>
                   # * +:dependent+ - behavior for cascading destroy. If set to :destroy, all the
                   #   child objects are destroyed alongside this object by calling their destroy
                   #   method. If set to :delete_all (default), all the child objects are deleted
                   #   without calling their destroy method.
                   # * +:counter_cache+ adds a counter cache for the number of children.
                   #   defaults to false.
                   #   Example: <tt>acts_as_nested_set :counter_cache => :children_count</tt>
                   #
                   # See CollectiveIdea::Acts::NestedSet::Model::ClassMethods for a list of class methods and
                   # CollectiveIdea::Acts::NestedSet::Model for a list of instance methods added
                   # to acts_as_nested_set models
                   def acts_as_nested_set(options = {})
                     options = {
                       :parent_column => 'parent_id',
                       :left_column => 'lft',
                       :right_column => 'rgt',
                       :dependent => :delete_all, # or :destroy
                       :counter_cache => false,
                       :order => 'id'
                     }.merge(options)
                     if options[:scope].is_a?(Symbol) && options[:scope].to_s !~ /_id$/
                       options[:scope] = "#{options[:scope]}_id".intern
                     end
                     class_attribute :acts_as_nested_set_options
                     self.acts_as_nested_set_options = options
                     include CollectiveIdea::Acts::NestedSet::Model
                     include Columns
                     extend Columns
                     belongs_to :parent, :class_name => self.base_class.to_s,
                       :foreign_key => parent_column_name,
                       :counter_cache => options[:counter_cache],
                       :inverse_of => :children
                     has_many :children, :class_name => self.base_class.to_s,
                       :foreign_key => parent_column_name, :order => left_column_name,
                       :inverse_of => :parent,
                       :before_add    => options[:before_add],
                       :after_add     => options[:after_add],
                       :before_remove => options[:before_remove],
                       :after_remove  => options[:after_remove]
                     attr_accessor :skip_before_destroy
                     before_create  :set_default_left_and_right
                     before_save    :store_new_parent
                     after_save     :move_to_new_parent
                     before_destroy :destroy_descendants
                     # no assignment to structure fields
                     [left_column_name, right_column_name].each do |column|
                       module_eval <<-"end_eval", __FILE__, __LINE__
                         def #{column}=(x)
                           raise ActiveRecord::ActiveRecordError, "Unauthorized assignment to #{column}: it's an internal field handled by acts_as_nested_set code, use move_to_* methods instead."
                         end
                       end_eval
                     end
                     define_model_callbacks :move
                   end
                   module Model
                     extend ActiveSupport::Concern
                     module ClassMethods
                       # Returns the first root
                       def root
                         roots.first
                       end
                       def roots
                         where(parent_column_name => nil).order(quoted_left_column_name)
                       end
                       def leaves
                         where("#{quoted_right_column_name} - #{quoted_left_column_name} = 1").order(quoted_left_column_name)
                       end
                       def valid?
                         left_and_rights_valid? && no_duplicates_for_columns? && all_roots_valid?
                       end
                       def left_and_rights_valid?
                         joins("LEFT OUTER JOIN #{quoted_table_name} AS parent ON " +
                             "#{quoted_table_name}.#{quoted_parent_column_name} = parent.#{primary_key}").
                         where(
                             "#{quoted_table_name}.#{quoted_left_column_name} IS NULL OR " +
                             "#{quoted_table_name}.#{quoted_right_column_name} IS NULL OR " +
                             "#{quoted_table_name}.#{quoted_left_column_name} >= " +
                               "#{quoted_table_name}.#{quoted_right_column_name} OR " +
                             "(#{quoted_table_name}.#{quoted_parent_column_name} IS NOT NULL AND " +
                               "(#{quoted_table_name}.#{quoted_left_column_name} <= parent.#{quoted_left_column_name} OR " +
                               "#{quoted_table_name}.#{quoted_right_column_name} >= parent.#{quoted_right_column_name}))"
                         ).count == 0
                       end
                       def no_duplicates_for_columns?
                         scope_string = Array(acts_as_nested_set_options[:scope]).map do |c|
                           connection.quote_column_name(c)
                         end.push(nil).join(", ")
                         [quoted_left_column_name, quoted_right_column_name].all? do |column|
                           # No duplicates
                           select("#{scope_string}#{column}, COUNT(#{column})").
                               group("#{scope_string}#{column}").
                               having("COUNT(#{column}) > 1").
                               first.nil?
                         end
                       end
                       # Wrapper for each_root_valid? that can deal with scope.
                       def all_roots_valid?
                         if acts_as_nested_set_options[:scope]
                           roots.group(scope_column_names).group_by{|record| scope_column_names.collect{|col| record.send(col.to_sym)}}.all? do |scope, grouped_roots|
                             each_root_valid?(grouped_roots)
                           end
                         else
                           each_root_valid?(roots)
                         end
                       end
                       def each_root_valid?(roots_to_validate)
                         left = right = 0
                         roots_to_validate.all? do |root|
                           (root.left > left && root.right > right).tap do
                             left = root.left
                             right = root.right
                           end
                         end
                       end
                       # Rebuilds the left & rights if unset or invalid.
                       # Also very useful for converting from acts_as_tree.
                       def rebuild!(validate_nodes = true)
                         # Don't rebuild a valid tree.
                         return true if valid?
                         scope = lambda{|node|}
                         if acts_as_nested_set_options[:scope]
                           scope = lambda{|node|
                             scope_column_names.inject(""){|str, column_name|
                               str << "AND #{connection.quote_column_name(column_name)} = #{connection.quote(node.send(column_name.to_sym))} "
                             }
                           }
                         end
                         indices = {}
                         set_left_and_rights = lambda do |node|
                           # set left
                           node[left_column_name] = indices[scope.call(node)] += 1
                           # find
                           where(["#{quoted_parent_column_name} = ? #{scope.call(node)}", node]).order(acts_as_nested_set_options[:order]).each{|n| set_left_and_rights.call(n) }
                           # set right
                           node[right_column_name] = indices[scope.call(node)] += 1
                           node.save!(:validate => validate_nodes)
                         end
                         # Find root node(s)
-                        root_nodes = where("#{quoted_parent_column_name} IS NULL").order("#{quoted_left_column_name}, #{quoted_right_column_name}, id").each do |root_node|
+                        root_nodes = where("#{quoted_parent_column_name} IS NULL").order(acts_as_nested_set_options[:order]).each do |root_node|
                           # setup index for this scope
                           indices[scope.call(root_node)] ||= 0
                           set_left_and_rights.call(root_node)
                         end
                       end
                       # Iterates over tree elements and determines the current level in the tree.
                       # Only accepts default ordering, odering by an other column than lft
                       # does not work. This method is much more efficent than calling level
                       # because it doesn't require any additional database queries.
                       #
                       # Example:
                       #    Category.each_with_level(Category.root.self_and_descendants) do |o, level|
                       #
                       def each_with_level(objects)
                         path = [nil]
                         objects.each do |o|
                           if o.parent_id != path.last
                             # we are on a new level, did we decent or ascent?
                             if path.include?(o.parent_id)
                               # remove wrong wrong tailing paths elements
                               path.pop while path.last != o.parent_id
                             else
                               path << o.parent_id
                             end
                           end
                           yield(o, path.length - 1)
                         end
                       end
                     end
                     # 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.
                     #
                     #   category.self_and_descendants.count
                     #   category.ancestors.find(:all, :conditions => "name like '%foo%'")
                     # Value of the parent column
                     def parent_id
                       self[parent_column_name]
                     end
                     # Value of the left column
                     def left
                       self[left_column_name]
                     end
                     # Value of the right column
                     def right
                       self[right_column_name]
                     end
                     # Returns true if this is a root node.
                     def root?
                       parent_id.nil?
                     end
                     def leaf?
                       new_record? || (right - left == 1)
                     end
                     # Returns true is this is a child node
                     def child?
                       !parent_id.nil?
                     end
                     # Returns root
                     def root
                       self_and_ancestors.where(parent_column_name => nil).first
                     end
                     # Returns the array of all parents and self
                     def self_and_ancestors
                       nested_set_scope.where([
                         "#{self.class.quoted_table_name}.#{quoted_left_column_name} <= ? AND #{self.class.quoted_table_name}.#{quoted_right_column_name} >= ?", left, right
                       ])
                     end
                     # Returns an array of all parents
                     def ancestors
                       without_self self_and_ancestors
                     end
                     # Returns the array of all children of the parent, including self
                     def self_and_siblings
                       nested_set_scope.where(parent_column_name => parent_id)
                     end
                     # Returns the array of all children of the parent, except self
                     def siblings
                       without_self self_and_siblings
                     end
                     # Returns a set of all of its nested children which do not have children
                     def leaves
                       descendants.where("#{self.class.quoted_table_name}.#{quoted_right_column_name} - #{self.class.quoted_table_name}.#{quoted_left_column_name} = 1")
                     end
                     # Returns the level of this object in the tree
                     # root level is 0
                     def level
                       parent_id.nil? ? 0 : ancestors.count
                     end
                     # Returns a set of itself and all of its nested children
                     def self_and_descendants
                       nested_set_scope.where([
                         "#{self.class.quoted_table_name}.#{quoted_left_column_name} >= ? AND #{self.class.quoted_table_name}.#{quoted_right_column_name} <= ?", left, right
                       ])
                     end
                     # Returns a set of all of its children and nested children
                     def descendants
                       without_self self_and_descendants
                     end
                     def is_descendant_of?(other)
                       other.left < self.left && self.left < other.right && same_scope?(other)
                     end
                     def is_or_is_descendant_of?(other)
                       other.left <= self.left && self.left < other.right && same_scope?(other)
                     end
                     def is_ancestor_of?(other)
                       self.left < other.left && other.left < self.right && same_scope?(other)
                     end
                     def is_or_is_ancestor_of?(other)
                       self.left <= other.left && other.left < self.right && same_scope?(other)
                     end
                     # Check if other model is in the same scope
                     def same_scope?(other)
                       Array(acts_as_nested_set_options[:scope]).all? do |attr|
                         self.send(attr) == other.send(attr)
                       end
                     end
                     # Find the first sibling to the left
                     def left_sibling
                       siblings.where(["#{self.class.quoted_table_name}.#{quoted_left_column_name} < ?", left]).
                               order("#{self.class.quoted_table_name}.#{quoted_left_column_name} DESC").last
                     end
                     # Find the first sibling to the right
                     def right_sibling
                       siblings.where(["#{self.class.quoted_table_name}.#{quoted_left_column_name} > ?", left]).first
                     end
                     # Shorthand method for finding the left sibling and moving to the left of it.
                     def move_left
                       move_to_left_of left_sibling
                     end
                     # Shorthand method for finding the right sibling and moving to the right of it.
                     def move_right
                       move_to_right_of right_sibling
                     end
                     # Move the node to the left of another node (you can pass id only)
                     def move_to_left_of(node)
                       move_to node, :left
                     end
                     # Move the node to the left of another node (you can pass id only)
                     def move_to_right_of(node)
                       move_to node, :right
                     end
                     # Move the node to the child of another node (you can pass id only)
                     def move_to_child_of(node)
                       move_to node, :child
                     end
                     # Move the node to root nodes
                     def move_to_root
                       move_to nil, :root
                     end
                     def move_possible?(target)
                       self != target && # Can't target self
                       same_scope?(target) && # can't be in different scopes
                       # !(left..right).include?(target.left..target.right) # this needs tested more
                       # detect impossible move
                       !((left <= target.left && right >= target.left) or (left <= target.right && right >= target.right))
                     end
                     def to_text
                       self_and_descendants.map do |node|
                         "#{'*'*(node.level+1)} #{node.id} #{node.to_s} (#{node.parent_id}, #{node.left}, #{node.right})"
                       end.join("\n")
                     end
                   protected
                     def without_self(scope)
                       scope.where(["#{self.class.quoted_table_name}.#{self.class.primary_key} != ?", self])
                     end
                     # All nested set queries should use this nested_set_scope, which performs finds on
                     # the base ActiveRecord class, using the :scope declared in the acts_as_nested_set
                     # declaration.
                     def nested_set_scope(options = {})
                       options = {:order => "#{self.class.quoted_table_name}.#{quoted_left_column_name}"}.merge(options)
                       scopes = Array(acts_as_nested_set_options[:scope])
                       options[:conditions] = scopes.inject({}) do |conditions,attr|
                         conditions.merge attr => self[attr]
                       end unless scopes.empty?
                       self.class.base_class.scoped options
                     end
                     def store_new_parent
                       @move_to_new_parent_id = send("#{parent_column_name}_changed?") ? parent_id : false
                       true # force callback to return true
                     end
                     def move_to_new_parent
                       if @move_to_new_parent_id.nil?
                         move_to_root
                       elsif @move_to_new_parent_id
                         move_to_child_of(@move_to_new_parent_id)
                       end
                     end
                     # on creation, set automatically lft and rgt to the end of the tree
                     def set_default_left_and_right
                       highest_right_row = nested_set_scope(:order => "#{quoted_right_column_name} desc").find(:first, :limit => 1,:lock => true )
                       maxright = highest_right_row ? (highest_right_row[right_column_name] || 0) : 0
                       # adds the new node to the right of all existing nodes
                       self[left_column_name] = maxright + 1
                       self[right_column_name] = maxright + 2
                     end
                     def in_tenacious_transaction(&block)
                       retry_count = 0
                       begin
                         transaction(&block)
                       rescue ActiveRecord::StatementInvalid => error
                         raise unless connection.open_transactions.zero?
                         raise unless error.message =~ /Deadlock found when trying to get lock|Lock wait timeout exceeded/
                         raise unless retry_count < 10
                         retry_count += 1
                         logger.info "Deadlock detected on retry #{retry_count}, restarting transaction"
                         sleep(rand(retry_count)*0.1) # Aloha protocol
                         retry
                       end
                     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 destroy_descendants
                       return if right.nil? || left.nil? || skip_before_destroy
                       in_tenacious_transaction do
                         reload_nested_set
                         # select the rows in the model that extend past the deletion point and apply a lock
                         self.class.base_class.find(:all,
                           :select => "id",
                           :conditions => ["#{quoted_left_column_name} >= ?", left],
                           :lock => true
                         )
                         if acts_as_nested_set_options[:dependent] == :destroy
                           descendants.each do |model|
                             model.skip_before_destroy = true
                             model.destroy
                           end
                         else
                           nested_set_scope.delete_all(
                             ["#{quoted_left_column_name} > ? AND #{quoted_right_column_name} < ?",
                               left, right]
                           )
                         end
                         # update lefts and rights for remaining nodes
                         diff = right - left + 1
                         nested_set_scope.update_all(
                           ["#{quoted_left_column_name} = (#{quoted_left_column_name} - ?)", diff],
                           ["#{quoted_left_column_name} > ?", right]
                         )
                         nested_set_scope.update_all(
                           ["#{quoted_right_column_name} = (#{quoted_right_column_name} - ?)", diff],
                           ["#{quoted_right_column_name} > ?", right]
                           )
             reload
                           # Don't allow multiple calls to destroy to corrupt the set
                         self.skip_before_destroy = true
                       end
                     end
                     # reload left, right, and parent
                     def reload_nested_set
                       reload(
                         :select => "#{quoted_left_column_name}, #{quoted_right_column_name}, #{quoted_parent_column_name}",
                         :lock => true
                       )
                     end
                     def move_to(target, position)
                       raise ActiveRecord::ActiveRecordError, "You cannot move a new node" if self.new_record?
                       run_callbacks :move do
                         in_tenacious_transaction do
                           if target.is_a? self.class.base_class
                             target.reload_nested_set
                           elsif position != :root
                             # load object if node is not an object
                             target = nested_set_scope.find(target)
                           end
                           self.reload_nested_set
                           unless position == :root || move_possible?(target)
                             raise ActiveRecord::ActiveRecordError, "Impossible move, target node cannot be inside moved tree."
                           end
                           bound = case position
                             when :child;  target[right_column_name]
                             when :left;   target[left_column_name]
                             when :right;  target[right_column_name] + 1
                             when :root;   1
                             else raise ActiveRecord::ActiveRecordError, "Position should be :child, :left, :right or :root ('#{position}' received)."
                           end
                           if bound > self[right_column_name]
                             bound = bound - 1
                             other_bound = self[right_column_name] + 1
                           else
                             other_bound = self[left_column_name] - 1
                           end
                           # there would be no change
                           return if bound == self[right_column_name] || bound == self[left_column_name]
                           # we have defined the boundaries of two non-overlapping intervals,
                           # so sorting puts both the intervals and their boundaries in order
                           a, b, c, d = [self[left_column_name], self[right_column_name], bound, other_bound].sort
                           # select the rows in the model between a and d, and apply a lock
                           self.class.base_class.select('id').lock(true).where(
                             ["#{quoted_left_column_name} >= :a and #{quoted_right_column_name} <= :d", {:a => a, :d => d}]
                           )
                           new_parent = case position
                             when :child;  target.id
                             when :root;   nil
                             else          target[parent_column_name]
                           end
                           self.nested_set_scope.update_all([
                             "#{quoted_left_column_name} = CASE " +
                               "WHEN #{quoted_left_column_name} BETWEEN :a AND :b " +
                                 "THEN #{quoted_left_column_name} + :d - :b " +
                               "WHEN #{quoted_left_column_name} BETWEEN :c AND :d " +
                                 "THEN #{quoted_left_column_name} + :a - :c " +
                               "ELSE #{quoted_left_column_name} END, " +
                             "#{quoted_right_column_name} = CASE " +
                               "WHEN #{quoted_right_column_name} BETWEEN :a AND :b " +
                                 "THEN #{quoted_right_column_name} + :d - :b " +
                               "WHEN #{quoted_right_column_name} BETWEEN :c AND :d " +
                                 "THEN #{quoted_right_column_name} + :a - :c " +
                               "ELSE #{quoted_right_column_name} END, " +
                             "#{quoted_parent_column_name} = CASE " +
                               "WHEN #{self.class.base_class.primary_key} = :id THEN :new_parent " +
                               "ELSE #{quoted_parent_column_name} END",
                             {:a => a, :b => b, :c => c, :d => d, :id => self.id, :new_parent => new_parent}
                           ])
                         end
                         target.reload_nested_set if target
                         self.reload_nested_set
                       end
                     end
                   end
                   # Mixed into both classes and instances to provide easy access to the column names
                   module Columns
                     def left_column_name
                       acts_as_nested_set_options[:left_column]
                     end
                     def right_column_name
                       acts_as_nested_set_options[:right_column]
                     end
                     def parent_column_name
                       acts_as_nested_set_options[:parent_column]
                     end
                     def scope_column_names
                       Array(acts_as_nested_set_options[:scope])
                     end
                     def quoted_left_column_name
                       connection.quote_column_name(left_column_name)
                     end
                     def quoted_right_column_name
                       connection.quote_column_name(right_column_name)
                     end
                     def quoted_parent_column_name
                       connection.quote_column_name(parent_column_name)
                     end
                     def quoted_scope_column_names
                       scope_column_names.collect {|column_name| connection.quote_column_name(column_name) }
                     end
                   end
                 end
               end
             end

             # Redmine - project management software
             # Copyright (C) 2006-2012  Jean-Philippe Lang
             #
             # This program is free software; you can redistribute it and/or
             # modify it under the terms of the GNU General Public License
             # as published by the Free Software Foundation; either version 2
             # of the License, or (at your option) any later version.
             #
             # This program is distributed in the hope that it will be useful,
             # but WITHOUT ANY WARRANTY; without even the implied warranty of
             # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
             # GNU General Public License for more details.
             #
             # You should have received a copy of the GNU General Public License
             # along with this program; if not, write to the Free Software
             # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
             require File.expand_path('../../test_helper', __FILE__)
             class ProjectNestedSetTest < ActiveSupport::TestCase
               def setup
                 Project.delete_all
                 @a = Project.create!(:name => 'A', :identifier => 'projecta')
                 @a1 = Project.create!(:name => 'A1', :identifier => 'projecta1')
                 @a1.set_parent!(@a)
                 @a2 = Project.create!(:name => 'A2', :identifier => 'projecta2')
                 @a2.set_parent!(@a)
+                @c = Project.create!(:name => 'C', :identifier => 'projectc')
+                @c1 = Project.create!(:name => 'C1', :identifier => 'projectc1')
+                @c1.set_parent!(@c)
                 @b = Project.create!(:name => 'B', :identifier => 'projectb')
+                @b2 = Project.create!(:name => 'B2', :identifier => 'projectb2')
+                @b2.set_parent!(@b)
                 @b1 = Project.create!(:name => 'B1', :identifier => 'projectb1')
                 @b1.set_parent!(@b)
                 @b11 = Project.create!(:name => 'B11', :identifier => 'projectb11')
                 @b11.set_parent!(@b1)
-                @b2 = Project.create!(:name => 'B2', :identifier => 'projectb2')
-                @b2.set_parent!(@b)
-                @c = Project.create!(:name => 'C', :identifier => 'projectc')
-                @c1 = Project.create!(:name => 'C1', :identifier => 'projectc1')
-                @c1.set_parent!(@c)
                 @a, @a1, @a2, @b, @b1, @b11, @b2, @c, @c1 = *(Project.all.sort_by(&:name))
               end
               def test_valid_tree
                 assert_valid_nested_set
               end
+              def test_rebuild_should_build_valid_tree
+                Project.update_all "lft = NULL, rgt = NULL"
+                Project.rebuild!
+                assert_valid_nested_set
+              end
               def test_moving_a_child_to_a_different_parent_should_keep_valid_tree
                 assert_no_difference 'Project.count' do
                   Project.find_by_name('B1').set_parent!(Project.find_by_name('A2'))
                 end
                 assert_valid_nested_set
               end
               def test_renaming_a_root_to_first_position_should_update_nested_set_order
                 @c.name = '1'
                 @c.save!
                 assert_valid_nested_set
               end
               def test_renaming_a_root_to_middle_position_should_update_nested_set_order
                 @a.name = 'BA'
                 @a.save!
                 assert_valid_nested_set
               end
               def test_renaming_a_root_to_last_position_should_update_nested_set_order
                 @a.name = 'D'
                 @a.save!
                 assert_valid_nested_set
               end
               def test_renaming_a_root_to_same_position_should_update_nested_set_order
                 @c.name = 'D'
                 @c.save!
                 assert_valid_nested_set
               end
               def test_renaming_a_child_should_update_nested_set_order
                 @a1.name = 'A3'
                 @a1.save!
                 assert_valid_nested_set
               end
               def test_renaming_a_child_with_child_should_update_nested_set_order
                 @b1.name = 'B3'
                 @b1.save!
                 assert_valid_nested_set
               end
               def test_adding_a_root_to_first_position_should_update_nested_set_order
                 project = Project.create!(:name => '1', :identifier => 'projectba')
                 assert_valid_nested_set
               end
               def test_adding_a_root_to_middle_position_should_update_nested_set_order
                 project = Project.create!(:name => 'BA', :identifier => 'projectba')
                 assert_valid_nested_set
               end
               def test_adding_a_root_to_last_position_should_update_nested_set_order
                 project = Project.create!(:name => 'Z', :identifier => 'projectba')
                 assert_valid_nested_set
               end
               def test_destroying_a_root_with_children_should_keep_valid_tree
                 assert_difference 'Project.count', -4 do
                   Project.find_by_name('B').destroy
                 end
                 assert_valid_nested_set
               end
               def test_destroying_a_child_with_children_should_keep_valid_tree
                 assert_difference 'Project.count', -2 do
                   Project.find_by_name('B1').destroy
                 end
                 assert_valid_nested_set
               end
               private
               def assert_nested_set_values(h)
                 assert Project.valid?
                 h.each do |project, expected|
                   project.reload
                   assert_equal expected, [project.parent_id, project.lft, project.rgt], "Unexpected nested set values for #{project.name}"
                 end
               end
               def assert_valid_nested_set
                 projects = Project.all
                 lft_rgt = projects.map {|p| [p.lft, p.rgt]}.flatten
                 assert_equal projects.size * 2, lft_rgt.uniq.size
                 assert_equal 1, lft_rgt.min
                 assert_equal projects.size * 2, lft_rgt.max
                 projects.each do |project|
                   # lft should always be < rgt
                   assert project.lft < project.rgt, "lft=#{project.lft} was not < rgt=#{project.rgt} for project #{project.name}"
                   if project.parent_id
                     # child lft/rgt values must be greater/lower
                     assert_not_nil project.parent, "parent was nil for project #{project.name}"
                     assert project.lft > project.parent.lft, "lft=#{project.lft} was not > parent.lft=#{project.parent.lft} for project #{project.name}"
                     assert project.rgt < project.parent.rgt, "rgt=#{project.rgt} was not < parent.rgt=#{project.parent.rgt} for project #{project.name}"
                   end
                   # no overlapping lft/rgt values
                   overlapping = projects.detect {|other|
                     other != project && (
                       (other.lft > project.lft && other.lft < project.rgt && other.rgt > project.rgt) ||
                       (other.rgt > project.lft && other.rgt < project.rgt && other.lft < project.lft)
                     )
                   }
                   assert_nil overlapping, (overlapping && "Project #{overlapping.name} (#{overlapping.lft}/#{overlapping.rgt}) overlapped #{project.name} (#{project.lft}/#{project.rgt})")
                 end
                 # root projects sorted alphabetically
                 assert_equal Project.roots.map(&:name).sort, Project.roots.sort_by(&:lft).map(&:name), "Root projects were not properly sorted"
                 projects.each do |project|
                   if project.children.any?
                     # sibling projects sorted alphabetically
                     assert_equal project.children.map(&:name).sort, project.children.order('lft').map(&:name), "Project #{project.name}'s children were not properly sorted"
                   end
                 end
               end
             end