Module: ActiveRecord::Acts::HappyTree::BreadthFirst

Defined in:
lib/active_record/acts/breadth_first.rb

Instance Method Summary collapse

Instance Method Details

#descendant_ids_bfs(options = {}) ⇒ Object

Returns a flat list of the descendant ids of the current node using a breadth-first search en.wikipedia.org/wiki/Breadth-first_search DB calls = level of tree only id field returned in query



48
49
50
51
52
53
54
 
# File 'lib/active_record/acts/breadth_first.rb', line 48

def descendant_ids_bfs(options={})
  desc_ids = []
  each_level_ids(options) do |level_ids|
    desc_ids += level_ids
  end
  return desc_ids
end

#descendant_ids_bfs_rec(options = {}) ⇒ Object 



73
74
75
 
# File 'lib/active_record/acts/breadth_first.rb', line 73

def descendant_ids_bfs_rec(options={})
  descendants_bfs_rec(options.merge(:select=>'id')).map(&:id)
end

#descendants_bfs(options = {}) ⇒ Object

Returns a flat list of the descendants of the current node using a breadth-first search en.wikipedia.org/wiki/Breadth-first_search

root.descendants_bfs # => [child1, child2, subchild1, subchild2]

options can be passed such as:

select - only return specified attributes, must include id
conditions - only return matching objects, will not return children
             of any unmatched objects
order - will set the order of each set of children
limit - will limit max number of children for each parent

number of DB calls == number of levels for the example there will be 3 DB calls



36
37
38
39
40
41
42
 
# File 'lib/active_record/acts/breadth_first.rb', line 36

def descendants_bfs(options={})
  desc_nodes = []
  each_level_nodes(options) do |nodes|
    desc_nodes += nodes
  end
  return desc_nodes
end

#descendants_bfs_rec(options = {}) ⇒ Object 



77
78
79
80
81
82
 
# File 'lib/active_record/acts/breadth_first.rb', line 77

def descendants_bfs_rec(options={})
  c = children.all(options)
  c + c.map do |child|
    child.descendants_bfs_rec(options)
  end.flatten
end

#descendants_count_bfs(options = {}) ⇒ Object

Return the number of descendants DB calls = level of tree only id field selected in query



59
60
61
62
63
64
65
 
# File 'lib/active_record/acts/breadth_first.rb', line 59

def descendants_count_bfs(options={})
  count = 0
  each_level_ids(options) do |level_ids|
    count += level_ids.count
  end
  return count
end

#descendants_count_bfs_rec(options = {}) ⇒ Object 



84
85
86
87
88
 
# File 'lib/active_record/acts/breadth_first.rb', line 84

def descendants_count_bfs_rec(options={})
  children.count + children.all(options.merge(:select=>'id')).reduce(0) do |count, child|
    count += child.descendants_count_bfs_rec(options)
  end
end

#each_level_ids(options = {}) ⇒ Object 



6
7
8
9
10
11
12
 
# File 'lib/active_record/acts/breadth_first.rb', line 6

def each_level_ids(options={})
  level_ids = [id]
  until level_ids.empty?
    level_ids = self.class.child_ids_of(level_ids, options)
    yield level_ids
  end
end

#each_level_nodes(options = {}) ⇒ Object 



14
15
16
17
18
19
20
21
 
# File 'lib/active_record/acts/breadth_first.rb', line 14

def each_level_nodes(options={})
  level_nodes = [self]
  until level_nodes.empty?
    ids = level_nodes.map(&:id)
    level_nodes = self.class.children_of(ids, options)
    yield level_nodes
  end
end

#self_and_descendants_bfs(options = {}) ⇒ Object

Return all descendants and current node, this is present for completeness with other tree implementations



69
70
71
 
# File 'lib/active_record/acts/breadth_first.rb', line 69

def self_and_descendants_bfs(options={})
  [self] + descendants_bfs(options)
end