class SortedWalking
    class Vertex
        attr_accessor :weight, :label
        def initialize(label, weight = nil)
            @label = label

            @weight = weight || 5
        end

        def to_s
            label
        end
    end

    class ShadowMap
        Shadow = Struct.new(:failed, :noop, :events, :dependents)

        attr_reader :map
        def initialize
            @map = {}
            @failed = {}
        end

        def [](vertex)
            @map[vertex]
        end

        # Store a failure for later.
        def fail(vertex, reason)
            @failed[vertex] ||= []
            @failed[vertex] << resource
        end

        def shadow(edge)
            target_shadow = find_or_make_shadow(edge)

            add_failures(edge.target, target_shadow)

            target_shadow
        end

        private

        def add_failures(vertex, shadow)
            if failures = @failed[vertex]
                shadow.failures += failures
            end
        end

        def find_or_make_shadow(edge)
            unless target_shadow = map[edge.target]
                unless source_shadow = map[edge.source]
                    # This should be the top-level initialization
                    map[edge.source] = Shadow.new([], [], [], [])
                end

                target_shadow = map[edge.target] = make_target_shadow(target, source_shadow)
            end
        end

        def make_target_shadow(target, source_shadow)
            # We clone so that each shadow has its own array, rather than using
            # the same instance variables, as a 'dup' would do.
            shadow = source_shadow.clone
        end
    end


    def vertex(name)
        @graph.vertices.find { |v| v.label == name } || Vertex.new(name)
    end

    def add_edge(source, target, type = :container)
        edge = Puppet::Relationship.new(vertex(source), vertex(target))
        edge.type = type
        @graph.add_edge(edge)
    end

    def initialize
        Puppet[:graphdir] = "/Users/luke/Desktop/graph_testing"
        Puppet[:graph] = true
        @graph = Puppet::SimpleGraph.new

        add_edge("top", "a")
        add_edge("top", "A")

        add_edge("a", "b")
        add_edge("b", "c")
        add_edge("a", "d")
        add_edge("d", "e")
        add_edge("d", "f")
        add_edge("a", "g")

        add_edge("A", "B")
        add_edge("B", "C")
        add_edge("A", "D")
        add_edge("D", "E")
        add_edge("D", "F")
        add_edge("A", "G")

        # Now add our dependency edges
        #@dependencies = {"B" => "b", "C" => "d", "D" => "d"}
        #@dependencies = {"B" => "b", "C" => "d"}
        #@dependencies = {"B" => "b", "C" => "d", "D" => "g"}
        #@dependencies = {"A" => "a"}
        #@dependencies = {}

        #@weights = {}
        #@weights = { "A" => 4, "d" => 1 }

        @failures = %w{f}

        add_dependencies
        add_weights

        @shadow_map = ShadowMap.new
    end

    def add_dependencies
        return unless defined?(@dependencies)
        @dependencies.each do |source, target|
            add_edge(source, target, :dependency)
        end
    end

    def add_weights
        return unless defined?(@weights)
        @weights.each do |v, weight|
            vertex(v).weight = weight
        end
    end

    def apply_shadow(edge)
        return unless edge.container?

        shadow = @shadow_map.shadow(edge)

        # Track all of our dependents
        shadow.dependents += dependent_edges(edge.target)

        # Track failure state
        if @failures.include?(edge.target.label)
            shadow.failed << "%s failed" % edge.target.label

            # Mark all of our dependents as failed, too
            shadow.dependents.each do |edge|
                @shadow_map.fail(edge.source, shadow.failed[-1])
            end
        end

        shadow
    end

    def dependent_edges(vertex)
        adjacent(vertex, :direction => :in, :type => :edges).reject { |e| e.container? }
    end

    def run
        top = @graph.vertices.find { |v| v.label == "top" }
        result = []
        @graph.dfs_walk(top, :out) do |edge|
            begin
                #apply_shadow(edge)

            rescue => detail
                puts "Skipping %s: %s" % [edge.target, detail]
                next
            end

            result << edge.target.label unless result.include?(edge.target.label)
        end

        @graph.write_graph("test")

        p result
    end
end