Class: Hierarchy

Inherits:
Object
  • Object
show all
Defined in:
lib/hierarchy_tree.rb

Overview

Debug ################ gem uninstall hierarchy-tree -v 0.3.0 rm hierarchy-tree-0.3.0.gem gem build hierarchy_tree gem install hierarchy-tree-0.3.0.gem ruby -Itest test/test_hierarchy_tree.rb

Class Method Summary collapse

Class Method Details

.ancestors_bfs(from:, to:) ⇒ Object

Return the ancestors associations by navigating through :belongs_to Starting from the “from” class towards the “to” class Using BFS - Breadth First Search, thus finding the Shortest Path



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/hierarchy_tree.rb', line 48

def self.ancestors_bfs(from:, to:)
  return if from == to

  queue = [{ class: from, path: [] }]
  visited = [from]

  while queue.any?
    current = queue.shift
    current_class = current[:class]
    current_path = current[:path]

    current_class.reflect_on_all_associations(:belongs_to).each do |relation|
      next_class = relation.klass
      next_path = current_path + [relation.name]

      return hashify(next_path) if next_class.to_s == to.to_s

      if visited.exclude?(next_class)
        visited << next_class
        queue.push({ class: next_class, path: next_path })
      end
    end
  end
end

.ancestors_dfs(from:, to:, descendants: []) ⇒ Object

Return the ancestors associations by navigating through :belongs_to Starting from the “from” class towards the “to” class Using DFS - Depth First Search, thus finding the Deepest Path (more likely)



32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/hierarchy_tree.rb', line 32

def self.ancestors_dfs(from:, to:, descendants: [])
  return if from.to_s == to.to_s and descendants == [] # Base case
  return 'loop' if from.in? descendants # Avoids cycle

  descendants.push(from)

  from.reflect_on_all_associations(:belongs_to).map do |relation|
    return relation.name if relation.klass.to_s == to.to_s # Path is found
    path = ancestors_dfs(from: relation.klass, to: to, descendants: descendants)
    return { relation.name => path } if valid_path?(path, to.model_name.param_key.to_sym)
  end.compact.first
end

.associations(klass) ⇒ Object

Return the full hierarchy as associations starting from the provided class



13
14
15
 
# File 'lib/hierarchy_tree.rb', line 13

def self.associations(klass)
  build_hierarchy(class: klass)
end

.build_descendants(klass) ⇒ Object 



137
138
139
140
141
142
 
# File 'lib/hierarchy_tree.rb', line 137

def self.build_descendants(klass)
  dfs_descendants(class: klass, classes?: true)
rescue SystemStackError
  Rails.logger.ap "Infinite loop detected and handled for #{opts[:class]} classes_list", :warn
  []
end

.build_hierarchy(opts) ⇒ Object 



82
83
84
85
86
87
88
 
# File 'lib/hierarchy_tree.rb', line 82

def self.build_hierarchy(opts)
  @cache = {}
  dfs_hierarchy(opts)
rescue SystemStackError
  Rails.logger.ap "Infinite loop detected and handled for #{opts[:class]} hierarchy", :warn
  []
end

.children_classes(opts) ⇒ Object 



113
114
115
116
117
118
119
120
121
122
 
# File 'lib/hierarchy_tree.rb', line 113

def self.children_classes(opts)
  walkables(opts[:class]).map do |reflection|
    child_class = get_class(reflection)
    if opts[:classes?]
      [child_class, child_class.to_s]
    else
      [child_class, reflection.name]
    end
  end.uniq
end

.classes(klass) ⇒ Object

Return the full hierarchy as classes starting from the provided class



18
19
20
 
# File 'lib/hierarchy_tree.rb', line 18

def self.classes(klass)
  build_hierarchy(class: klass, classes?: true)
end

.classes_list(klass) ⇒ Object

Return the array of children classes



23
24
25
26
27
 
# File 'lib/hierarchy_tree.rb', line 23

def self.classes_list(klass)
  @classes_list = []
  build_descendants(klass)
  @classes_list
end

.dfs_descendants(opts, klass_name = nil) ⇒ Object 



144
145
146
147
148
149
150
151
152
 
# File 'lib/hierarchy_tree.rb', line 144

def self.dfs_descendants(opts, klass_name = nil)
  return if klass_name.in? @classes_list
  @classes_list.push(klass_name) if klass_name.present?
  children_classes(opts).each do |child_klass, child_name|
    child_opts = { class: child_klass, classes?: opts[:classes?] }
    dfs_descendants(child_opts, child_name)
  end
  true
end

.dfs_hierarchy(opts, klass_name = nil, ancestral_nodes = []) ⇒ Object 



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
# File 'lib/hierarchy_tree.rb', line 90

def self.dfs_hierarchy(opts, klass_name = nil, ancestral_nodes = [])
  return @cache[klass_name] if klass_name.in? @cache.keys
  return klass_name if opts[:class].in? ancestral_nodes # Early abort to not enter in a cycle
  if leaf?(opts[:class])
    @cache[klass_name] = klass_name
    return klass_name if klass_name.present? # Leaf
    [] # Leaf and Root
  else
    ancestral_nodes.push(opts[:class])
    children_hierarchies = children_classes(opts).map do |c_class, c_name|
      dfs_hierarchy({ class: c_class, classes?: opts[:classes?] }, c_name, ancestral_nodes.dup)
    end
    @cache[klass_name] = { klass_name => children_hierarchies }
    return @cache[klass_name] if klass_name.present? # Middle
    children_hierarchies # Root
  end
end

.get_class(reflection) ⇒ Object 



131
132
133
134
135
 
# File 'lib/hierarchy_tree.rb', line 131

def self.get_class(reflection)
  child = reflection.name.to_s.singularize.classify
  child = reflection.options[:class_name].to_s if reflection.options.key?(:class_name)
  child.constantize
end

.hashify(array) ⇒ Object 



167
168
169
170
171
172
173
 
# File 'lib/hierarchy_tree.rb', line 167

def self.hashify(array)
  if array.length == 1
    array.first
  else
    { array.first => hashify(array.drop(1)) }
  end
end

.leaf?(klass) ⇒ Boolean

Returns:

  • (Boolean) 


108
109
110
111
 
# File 'lib/hierarchy_tree.rb', line 108

def self.leaf?(klass)
  return true if walkables(klass).empty?
  false
end

.loop?(klass) ⇒ Boolean

Returns:

  • (Boolean) 


73
74
75
76
77
78
 
# File 'lib/hierarchy_tree.rb', line 73

def self.loop?(klass)
  @cache = {}
  false if dfs_hierarchy(class: klass, classes?: false)
rescue SystemStackError
  true
end

.valid_path?(path, target) ⇒ Boolean

Returns:

  • (Boolean) 


154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/hierarchy_tree.rb', line 154

def self.valid_path?(path, target)
  return true if path == target

  case path
  when Array
    path.any? { |sub_path| valid_path?(sub_path, target) }
  when Hash
    path.values.any? { |value| valid_path?(value, target) }
  else
    false
  end
end

.walkables(klass) ⇒ Object 



124
125
126
127
128
129
 
# File 'lib/hierarchy_tree.rb', line 124

def self.walkables(klass)
  # get all models associated with :has_many or :has_one that are walkable.
  klass.reflections.values.select do |r|
    r.macro.in? %i[has_one has_many] and not r.options.key?(:through)
  end
end