Class: Hierarchy

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

Overview

Debug ################ gem cleanup hierarchy-tree rm hierarchy-tree-0.3.5.gem gem build hierarchy_tree gem install hierarchy-tree-0.3.5.gem ruby -Itest test/test_hierarchy_tree.rb

Class Method Summary collapse

Class Method Details

.ancestors(from:, to:) ⇒ Object

Return all the possible ancestors associations by navigating through :belongs_to Starting from the “from” class towards the “to” class



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
 
# File 'lib/hierarchy_tree.rb', line 39

def self.ancestors(from:, to:)
  return [] if from.to_s == to.to_s

  queue = [{ class: from.to_s, path: [] }]
  visited = { from.to_s => [] }
  paths = []

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

    current_class.constantize.reflect_on_all_associations(:belongs_to).each do |relation|
      next if relation.options[:polymorphic]

      next_class = relation.klass.to_s
      next_path = current_path + [relation.name]

      paths << hashify(next_path) if next_class == to.to_s

      if non_looped_path?(from, to, relation, next_path)
        visited[next_class] = next_path
        queue.push({ class: next_class, path: next_path })
      end
    end
  end

  paths
end

.ancestors_bfs(from:, to:, classify: false) ⇒ 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



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
 
# File 'lib/hierarchy_tree.rb', line 72

def self.ancestors_bfs(from:, to:, classify: false)
  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 if relation.options[:polymorphic]

      next_class = relation.klass

      if classify # An array of classes
        next_path = current_path + [relation.klass.to_s]
        return next_path if next_class.to_s == to.to_s
      else # A hash of associations
        next_path = current_path + [relation.name]
        return hashify(next_path) if next_class.to_s == to.to_s
      end

      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)



107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/hierarchy_tree.rb', line 107

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

.bottom_up_classes(klass) ⇒ Object

Return the array of children classes in a bottom up manner From leaf classes to upper classes



31
32
33
34
35
 
# File 'lib/hierarchy_tree.rb', line 31

def self.bottom_up_classes(klass)
  @classes_list = []
  build_descendants(klass)
  topological_sort([klass.to_s] + @classes_list)
end

.build_descendants(klass) ⇒ Object 



184
185
186
187
188
189
 
# File 'lib/hierarchy_tree.rb', line 184

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 



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

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 



160
161
162
163
164
165
166
167
168
169
 
# File 'lib/hierarchy_tree.rb', line 160

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 



191
192
193
194
195
196
197
198
199
 
# File 'lib/hierarchy_tree.rb', line 191

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 



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/hierarchy_tree.rb', line 137

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 



178
179
180
181
182
 
# File 'lib/hierarchy_tree.rb', line 178

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 



222
223
224
225
226
227
228
 
# File 'lib/hierarchy_tree.rb', line 222

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

.leaf?(klass) ⇒ Boolean

Returns:

  • (Boolean) 


155
156
157
158
 
# File 'lib/hierarchy_tree.rb', line 155

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

.loop?(klass) ⇒ Boolean

Returns:

  • (Boolean) 


120
121
122
123
124
125
 
# File 'lib/hierarchy_tree.rb', line 120

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

.non_looped_path?(from, to, relation, next_path) ⇒ Boolean

Returns:

  • (Boolean) 


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

def self.non_looped_path?(from, to, relation, next_path)
  relation.class_name != from.name and
    relation.class_name != to.name and
    next_path == next_path.uniq
end

.topological_sort(classes) ⇒ Object 



201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
 
# File 'lib/hierarchy_tree.rb', line 201

def self.topological_sort(classes)
  dependencies = classes.to_h do |c|
    [c, Hierarchy.ancestors_bfs(from: c.constantize, to: classes[0].constantize, classify: true)]
  end

  sorted_items = []
  visited = {}

  visit = lambda do |item|
    unless visited[item]
      visited[item] = true
      dependencies[item]&.each { |dependency| visit.call(dependency) }
      sorted_items.unshift(item)
    end
  end

  classes.each { |item| visit.call(item) unless visited[item] }

  sorted_items
end

.valid_path?(path, target) ⇒ Boolean

Returns:

  • (Boolean) 


236
237
238
239
240
241
242
243
244
245
246
247
 
# File 'lib/hierarchy_tree.rb', line 236

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 



171
172
173
174
175
176
 
# File 'lib/hierarchy_tree.rb', line 171

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