Module: DSort

Defined in:
lib/prick/dsort.rb

Defined Under Namespace

Modules: DSortPrivate Classes: Cyclic

Class Method Summary collapse

Class Method Details

.dsort(a, &block) ⇒ Object

dsort sorts its input in “dependency” order: The input can be thought of depends-on relations between objects and the output as sorted in the order needed to safisfy those dependencies so that no object comes before an object it depends on

dsort can take an array or a hash argument, or be supplied with a block

The Array argument should consist of pairs (two-element Arrays) with the first element being the depending object and the second an object or an array of objects it depends on: For example [:a, :b] means that :a depends on :b, and [:b, [:c, :d]] that :b depends on both :c and :d

The Hash argument should be a hash from depending object to an object or array of objects it depends on. If h is a Hash then dsort(h) is equivalent to dsort(h.to_a)

Note that if the elements are arrays themselves, then you should use the array form to list the dependencies even if there is only one dependency. Ie. use [:a, [:b]] or {:a => [:b] } instead of [:a, :b] or => :b

If dsort is given a block, the block is given an element as argument and should return an (possibly empty) array of the objects the argument depends on. The argument to dsort should be an element or an array of elements to be given to the block. Note that if the elements are arrays themselves, then the arguments to dsort should use the array form even if there is only one element. Ie. Use dsort() instead of dsort(:a)

dsort raise a DSort::Cyclic exception if a cycle detected

Example: If we have that dsort depends on ruby and rspec, ruby depends on C to compile, and rspec depends on ruby, then in what order should we build them ? Using dsort we could do

p dsort [[:dsort, [:ruby, :rspec]]], [:ruby, :C], [:rspec, :ruby]]
    => [:C, :ruby, :rspec, :dsort]

Using a hash

h = {
  :dsort => [:ruby, :rspec],
  :ruby => [:C],
  :rspec => [:ruby]
}
p dsort(h) # Same as dsort(h.to_a)
    => [:C, :ruby, :rspec, :dsort]

or using a block

p dsort(:dsort) { |e| h[e] }
    => [:C, :ruby, :rspec, :dsort]



74
75
76
77
78
79
80
81
 
# File 'lib/prick/dsort.rb', line 74

def dsort(a, &block) 
  sort_object = DSortPrivate::DSortObject.new(a, &block)
  begin
    sort_object.tsort 
  rescue TSort::Cyclic
    raise Cyclic.new(sort_object)
  end
end

.tsort(a, &block) ⇒ Object

tsort sort its input in topological order: The input can be thought of as comes-before relations between objects and the output will be in first-to-last order. This definition corresponds to the mathemacial defitionnn of topological sort. See en.wikipedia.org/wiki/Topological_sorting

Arguments are the same as for dsort. tsort is equivalent to dsort(…).reverse

tsort raise a DSort::Cyclic exception if a cycle is detected (DSort::Cyclic is an alias for TSort::Cyclic)



95
 
# File 'lib/prick/dsort.rb', line 95

def tsort(a, &block) dsort(a, &block).reverse end