#!/usr/bin/ruby -w
# search.rb - Copyright 2004 by Karsten Meier
# Port of Search example, from
# Constructing Intelligent Agents with Java
# Chapter 2: Searching
require 'optparse'
require 'rexml/document'

##
# stores the node and some search related information
# 
class SearchNode
    attr_accessor :label      # symbolic name
    attr_accessor :state      # to store state space
    attr_accessor :depth      # depth of tree from start node
    #  attr_accessor :oper    # operator which generated this node
    attr_accessor :links      # array of other nodes
    attr_accessor :expanded   # true if node has been expaned
    attr_accessor :tested     # true if node was ever tested
    attr_accessor :cost       # cost to reach this node

    FRONT = 0                 # Constant Definition
    BACK = 1
    INSERT = 2

    def initialize(label, state)
        @label = label
        @state = state
        @depth = 0
        @links = []
    end
    
    ##
    # add nodes to our links array
    #
    def addLinks(*links)
        @links.push(*links)
    end
    
    ##
    # node is leaf if it has no links
    def leaf?
        links.size == 0
    end
    
    # to diplay a node during debugging
    def to_s
        "#{label}:#{cost}"
    end
    
    ##
    # reset node depth and boolean flags before start search
    def reset
        @depth = 0
        @expanded = false
        @tested = false
    end

    ##
    # expanding a node places its childs in the queue,
    # if they were not already tested.
    # @param queue our child notes will be put in this queue
    # @param position where put out child notes
    def expand( queue, position)
        @links.each {
            | nextnode |
            if !nextnode.tested
                puts "add node #{nextnode}"
                nextnode.tested = true
                nextnode.depth = depth + 1 
                case position
                when FRONT # front
                    queue.unshift(nextnode)
                when BACK # back
                    queue.push(nextnode)
                when INSERT # insert according to cost
                    inserted = false
                    if ! defined?(nextnode.cost)
                        puts "#{nextnode.label} has not defined the cost"
                    end
                    nextcost = nextnode.cost
                    for i in 0...queue.size
                        if nextcost < queue[i].cost
                            queue.insert(i, nextnode)
                            inserted = true
                            break
                        end
                    end
                    # if position not found, just add them at end
                    if !inserted
                        queue.push(nextnode)
                    end 
                else
                    puts "Bad Case"  
                end
            end
        }
    end

    # to show output
    def trace
        indent = "  " * depth
        puts "#{indent}Searching #{depth}:#{label} with state #{state}"
    end  

    # generates an xml fragment that has the basic information about this object
    def to_xml()
        xml = "<SearchNode><label>#{@label}</label><cost>#{@cost}</cost>"
        links.each{|node|
            xml.concat("<link>#{node.label}</link>")
        }
        xml.concat("</SearchNode>")
    end
end


##
# contains all nodes and provides the methods to perform 
# the serach with different search algorithms
#
class SearchGraph < Hash  
    attr_accessor :label      # symbolic name
    
    def reset
        self.each_value {
            | node |
            node.reset
        }
    end
    
    def put(node)
        self[node.label] = node
    end
    
    # do the breadth first search
    # @param initialNode searchNode to start from
    # @param goalState what we want to reach
    # @return 
    def breadthFirstSearch(initialNode, goalState)
        queue = Array.new
        queue.push(initialNode)
        initialNode.tested = true
        while queue.size > 0
            testNode = queue.shift   # return first element and remove it      
            testNode.trace
            if testNode.state == goalState
                return testNode
            end  
            if !testNode.expanded
                testNode.expand(queue, SearchNode::BACK)  
            end  
        end
        return nil
    end
   
    # Do the depth-first search.
    # It works exactly in the same way like breadthFirstSearch(),
    # but only gives a different parameter to expand()
    # @param initialNode searchNode to start from
    # @param goalState what we want to reach
    # @return searchNode which was found, or nil of nothing found
    def depthFirstSearch(initialNode, goalState)
        queue = Array.new
        queue.push(initialNode)
        initialNode.tested = true
        while queue.size > 0
            testNode = queue.shift   # return first element and remove it
            testNode.trace
            if testNode.state == goalState
                return testNode
            end  
            if !testNode.expanded
                testNode.expand(queue, SearchNode::FRONT)  
            end        
        end  
        return nil
    end
    
    # modified depth first search.
    # Stops at prefefined length
    # @param initialNode searchNode to start from
    # @param goalState what we want to reach
    # @param maximum length
    # @return searchNode which was found, or nil of nothing found
    def deepLimitSearch(initialNode, goalState, maxDepth)
        queue = Array.new
        queue.push(initialNode)
        initialNode.tested = true
        
        while queue.size > 0
            testNode = queue.shift   # return first element and remove it
            testNode.trace
            if testNode.state == goalState
                return testNode
            end  
            if testNode.depth < maxDepth
                if !testNode.expanded
                    testNode.expand(queue, SearchNode::FRONT)  
                end
            end        
        end  
        return nil
    end
    
    def iterDeepSearch(initialNode, goalState)
        maxDepth = 10
        (0..maxDepth).each{ |j|
            reset
            answer = deepLimitSearch(initialNode, goalState, j)
            if answer
                return answer
            end
        }
        return nil
    end
    
    # Do the best first search
    # @param initialNode searchNode to start from
    # @param goalState what we want to reach
    # @return goal node or nuil if not found
    def bestFirstSearch(initialNode, goalState)
        queue = Array.new
        queue.push(initialNode)
        initialNode.tested = true
    
        while queue.size > 0
            puts queue.join("/")
            testNode = queue.shift   # return first element and remove it
            #testNode.trace
            if testNode.state == goalState
                return testNode
            end  
            if !testNode.expanded
                testNode.expand(queue, SearchNode::INSERT)  
            end      
         end 
         return nil    
    end
   
    # generates an xml fragment that has the basic information about this object
    # and its containing nodes
    def to_xml()
        xml = "<SearchGraph><label>#{@label}</label><nodes>"
        self.each_value{|node| xml.concat(node.to_xml)}
        xml.concat("</nodes></SearchGraph>")
    end
  
end

class SearchController
    def buildTestGraph
        graph = SearchGraph.new
        roch = SearchNode.new("Rochester", "Rochester")
        graph.put(roch)  
        sfalls = SearchNode.new("Sioux Falls", "Sioux Falls")
        graph.put(sfalls)
        mpls = SearchNode.new("Minneapolis","Minneapolis") ;
        graph.put(mpls) 
        lacrosse = SearchNode.new("LaCrosse","LaCrosse") 
        graph.put(lacrosse) 
        fargo = SearchNode.new("Fargo","Fargo") 
        graph.put(fargo) 
        stcloud = SearchNode.new("St.Cloud","St.Cloud") 
        graph.put(stcloud)
        duluth = SearchNode.new("Duluth","Duluth") 
        graph.put(duluth) 
        wausau = SearchNode.new("Wausau","Wausau") 
        graph.put(wausau) 
        gforks = SearchNode.new("Grand Forks","Grand Forks") 
        graph.put(gforks) 
        bemidji = SearchNode.new("Bemidji","Bemidji") 
        graph.put(bemidji) 
        ifalls = SearchNode.new("International Falls","International Falls") 
        graph.put(ifalls) 
        gbay = SearchNode.new("Green Bay","Green Bay") 
        graph.put(gbay) 
        madison = SearchNode.new("Madison","Madison") 
        graph.put(madison) 
        dubuque = SearchNode.new("Dubuque","Dubuque") 
        graph.put(dubuque) 
        rockford = SearchNode.new("Rockford","Rockford") 
        graph.put(rockford) 
        chicago = SearchNode.new("Chicago","Chicago") 
        graph.put(chicago) 
        milwaukee = SearchNode.new("Milwaukee","Milwaukee") 
        graph.put(milwaukee) 
    
        roch.addLinks(mpls, lacrosse, sfalls, dubuque) 
        mpls.addLinks(duluth, stcloud, wausau)
        mpls.addLinks(lacrosse, roch ) 
        lacrosse.addLinks(madison, dubuque, roch)
        lacrosse.addLinks(mpls,gbay) 
        sfalls.addLinks(fargo, roch) 
        fargo.addLinks(sfalls, gforks, stcloud) 
        gforks.addLinks(bemidji, fargo, ifalls) 
        bemidji.addLinks(gforks, ifalls, stcloud, duluth) 
        ifalls.addLinks(bemidji, duluth, gforks) 
        duluth.addLinks(ifalls,mpls, bemidji) 
        stcloud.addLinks(bemidji, mpls, fargo) 
        dubuque.addLinks(lacrosse, rockford, roch) 
        rockford.addLinks(dubuque, madison, chicago) 
        chicago.addLinks(rockford, milwaukee) 
        milwaukee.addLinks(gbay, chicago) 
        gbay.addLinks(wausau, milwaukee, lacrosse) 
        wausau.addLinks(mpls, gbay) 
        
        # use as costs for best first search example
        # straight line distances from cities to Rochester
        roch.cost= 0        # goal
        sfalls.cost = 232 
        mpls.cost = 90 
        lacrosse.cost = 70 
        dubuque.cost = 140 
        madison.cost = 170 
        milwaukee.cost = 230 
        rockford.cost = 210 
        chicago.cost = 280
        stcloud.cost = 140
        duluth.cost = 180 
        ifalls.cost = 330  # estimated, because it was left in the sourcefile
        bemidji.cost = 260
        wausau.cost = 200 
        gbay.cost = 220
        fargo.cost = 280
        gforks.cost = 340    
        graph
    end
    
    # write the hole graph as xmlfile with specified filename
    def write_xml(graph, filename)
        File.open(filename, "w"){
          | file |
          file.puts('<?xml version="1.0" ?>')
          file.puts(graph.to_xml)
        }
    end
    # read a hole graph from an xml file  
    def read_xml(filename)
        graph = SearchGraph.new
        file = File.new(filename)
        doc = REXML::Document.new(file)
        name = doc.elements["SearchGraph/label"].text
        puts "Label is #{name}"
        doc.elements.each("SearchGraph/nodes/SearchNode"){
            | elem |
            label = elem.elements['label'].text
            puts "Elem label is #{label}"
            cost = elem.elements['cost'].text
            puts "Elem cost is #{cost}"
            # links
            # construct the node
            searchnode = SearchNode.new(label,label) 
            searchnode.cost = cost
            graph.put(searchnode)
        }
        doc.elements.each("SearchGraph/nodes/SearchNode/link"){
            | elem |
            label = elem.parent.elements['label'].text
            node = graph[label]
            linknode = graph[elem.text]
            puts "link for #{label}: #{elem.text}"
            if node && linknode
                node.addLinks(linknode)
            end  
        }   
        graph
    end
end

# ------------ Main Program -----------------
ARGV.options do 
    |opts|
    opts.banner  = "Usage: ruby search.rb [-b] [-d] -v -gGoal -sSTART -oOutputFile"
    opts.on("-h", "--help", "show this message"){
        puts opts; 
        exit
    }
    opts.on("-v", "--[no-]verbose=[FLAG]", TrueClass, "run verbosly") {
        |@verbose|
    }   # sets @verbose to true or false
    opts.on("-b", "--BreadthFirst", TrueClass, "start breadth-search " ){
        |@breadthFirst|
    }          # sets @debugmode
    opts.on("-d", "--DepthFirst", TrueClass, "start depth-first search " ){
        |@depthFirst|
    }          # sets @debugmode
    opts.on("-f", "--BestFirst", TrueClass, "start best-first search " ){
        |@bestFirst|
    }          # sets @debugmode
    opts.on("-g", "--Goal=string", String, "node we want to find"){
        |@goal|
    }          # sets @debugmode
    opts.on("-s", "--Start=string", String, "node we start with"){
        |@start|
    }          # sets @debugmode
    opts.on("-o", "--Output=string", String, "File were we store our graph"){
        |@outputfile|
    }          # sets @debugmode
    opts.on("-i", "--Input=string", String, "File were we read our graph from"){
        |@inputfile|
    }          # sets @debugmode
    opts.on("-t", "--Test", TrueClass, "Do selftest"){
        |@selftest|
    }          # sets @debugmode
    opts.parse!
end

controller = SearchController.new
if defined?(@inputfile)
    graph = controller.read_xml(@inputfile)
else 
    graph = controller.buildTestGraph
end
graph.label = "TestGraph"

if defined?(@outputfile)
    controller.write_xml(graph, @outputfile)
end

if defined?(@breadthFirst)
    puts "Searching Breadth-First from #{@start} to #{@goal}"
    found = graph.breadthFirstSearch(graph[@start], @goal)
    if found 
        puts "Found node #{found}"
    end
elsif defined?(@depthFirst)
    puts "Searching Depth-First from #{@start} to #{@goal}"
    found = graph.iterDeepSearch(graph[@start], @goal)
    if found 
        puts "Found node #{found}"
    end
elsif defined?(@bestFirst)
    @start = "Rochester"
    puts "Searching Best-First from #{@start} to #{@goal}"
    found = graph.bestFirstSearch(graph[@start], @goal)
    if found 
        puts "Found node #{found}"
    end
elsif defined?(@selftest)
    puts "Selftest not implemented yet"
end