Class: AmplitudeExperiment::Evaluation::TopologicalSort

Inherits:
Object
  • Object
show all
Defined in:
lib/experiment/evaluation/topological_sort.rb

Class Method Summary collapse

Class Method Details

.parent_traversal(flag_key, available, path = []) ⇒ Object

Perform depth-first traversal of flag dependencies



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/experiment/evaluation/topological_sort.rb', line 24

def self.parent_traversal(flag_key, available, path = [])
  flag = available[flag_key]
  return nil unless flag

  # No dependencies - return flag and remove from available
  if !flag.dependencies || flag.dependencies.empty?
    available.delete(flag.key)
    return [flag]
  end

  # Check for cycles
  path.push(flag.key)
  result = []

  flag.dependencies.each do |parent_key|
    raise CycleError, path if path.any? { |p| p == parent_key }

    traversal = parent_traversal(parent_key, available, path)
    result.concat(traversal) if traversal
  end

  result.push(flag)
  path.pop
  available.delete(flag.key)

  result
end

.sort(flags, flag_keys = nil) ⇒ Object

Sort flags topologically based on their dependencies



10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/experiment/evaluation/topological_sort.rb', line 10

def self.sort(flags, flag_keys = nil)
  available = flags.clone
  result = []
  starting_keys = flag_keys.nil? || flag_keys.empty? ? flags.keys : flag_keys

  starting_keys.each do |flag_key|
    traversal = parent_traversal(flag_key, available)
    result.concat(traversal) if traversal
  end

  result
end