#!/usr/bin/ruby

require "actors.rb"

class MapPriorityQueue < Array
    $PARANOIA = __FILE__ == $0
    def initialize (xd, yd, item=nil)
        @xd = xd
        @yd = yd
        self.insert(0, item) if item.is_a? MapPath
    end
    def << (path)
        raise ArgumentError if !path.is_a?(MapPath)
        if self.length==0
            self.insert(self.length,path)
            return self
        end
        lastpr = 0
        pr = 0
        inserted = false
        p = path.fpriority(@xd,@yd)
        (0...self.length).each do |i|
            if (!inserted) && (pr = self[i].fpriority(@xd,@yd)) >= p
                self.insert(i, path)
                return self if !$PARANOIA
                pr = self[i].fpriority(@xd,@yd)
                inserted = true
            end
            if $PARANOIA
                raise "PriorityQueueMisordered" if lastpr > pr
                lastpr = pr
            end
        end
        self.insert(self.length, path) if !inserted
        return self
    end
    alias getnext shift
end

class MapPath < Array
    def initialize(map, orth=false)
        @map = map
        @orth = orth
        self
    end
    def fpriority(xd,yd)
        return 0 if self.length==0
        self[self.length-1].hpriority(xd,yd,@orth) + self.length - 1
    end
    def clone
        c = MapPath.new @map, @orth
        each do |node|
            c.push node
        end
        c
    end
    def successors(actor)
        last = self[length-1]
        succ = @map.neighbours(last.x, last.y, !@orth).collect do |n|
            self.clone << n if n.passable? actor
        end
        succ.compact
    end
end

class MapCell
    attr_reader :x, :y, :map
    attr_accessor :rock
    def hpriority(xd, yd, orth=false)
        dx = (xd-@x).abs
        dy = (yd-@y).abs
        if orth
            dx + dy
        else
            (dx>dy ? dx : dy)
        end
    end
    def initialize (map, x, y, rock=false)
        @map = map
        @x = x
        @y = y
        @rock = rock
    end
    def inspect
        "#<MapCell (%d, %d)>" % [@x, @y]
    end
    def passable? (actor)
        raise "NotAnActor" unless actor.is_a? Actor
        !@rock
    end

    # move_neighbours() returns a list of cells that are able to be moved to/from this square.
    def move_neighbours()
        # Make sure to check for doorways that can't be passed through diagonally!
        # Start with the current list from neighbours()
        # foreach cell in that list, remove that cell if either of the conditions are met:
        #   it is not passable
        #   it is diagonal, and either it or this square is a doorway
    end

    # neighbours() returns a list of cells that are adjacent to/from this square.
    def neighbours()
        @map.neighbours(@x, @y, true)
    end
end

class Map < Array
    $WIDTH  = 80
    $HEIGHT = 24
    def initialize
        (0...$WIDTH).each do |i|
            a = []
            (0...$HEIGHT).each do |j|
                a[j] = MapCell.new(self, i, j)
            end
            self.insert(i, a)
        end
    end
    def [] (x, y=nil)
        raise IndexError if !x.is_a?(Integer) || x<0 || x>=$WIDTH
        return self.at(x) if !y
        raise IndexError if !y.is_a?(Integer) || y<0 || y>=$HEIGHT
        return self.at(x)[y]
    end
    def neighbours (x,y, diagonals=true)
        n = []
        xa = (x>0)
        xb = (x<$WIDTH-1)
        ya = (y>0)
        yb = (y<$HEIGHT-1)
        n.push(self[x-1, y  ]) if xa
        n.push(self[x  , y-1]) if ya
        n.push(self[x+1, y  ]) if xb
        n.push(self[x  , y+1]) if yb
        if diagonals
            n.push(self[x-1, y-1]) if xa && ya
            n.push(self[x-1, y+1]) if xa && yb
            n.push(self[x+1, y-1]) if xb && ya
            n.push(self[x+1, y+1]) if xb && yb
        end
        n
    end

    def move_neighbours (x,y)
        n = []
        not_left_edge = (x>0)
        not_right_edge = (x<$WIDTH-1)
        not_top_edge = (y>0)
        not_bottom_edge = (y<$HEIGHT-1)
        n.push(self[x-1, y  ]) if not_left_edge
        n.push(self[x  , y-1]) if not_top_edge
        n.push(self[x+1, y  ]) if not_right_edge
        n.push(self[x  , y+1]) if not_bottom_edge
        if (!self[x,y].is_doorway?)
            (n.push(self[x-1, y-1]) if (!self[x-1, y-1].is_doorway?)) if not_left_edge  && not_top_edge
            (n.push(self[x-1, y+1]) if (!self[x-1, y+1].is_doorway?)) if not_left_edge  && not_bottom_edge
            (n.push(self[x+1, y-1]) if (!self[x+1, y-1].is_doorway?)) if not_right_edge && not_top_edge
            (n.push(self[x+1, y+1]) if (!self[x+1, y+1].is_doorway?)) if not_right_edge && not_bottom_edge
        end
        n
    end

    def plot (path, actor)
        (0...$HEIGHT).each do |j|
            (0...$WIDTH).each do |i|
                if i==X_S and j==Y_S; print("\e[1;35m<\e[0m"); next; end
                if i==X_G and j==Y_G; print("\e[1;35m>\e[0m"); next; end

                if path and path.include?(self[i,j])
                        print( self[i,j].passable?(actor) ? "@" : "\e[1;31mX\e[0m" )
                    else
                              print( self[i,j].passable?(actor) ? "." : "\e[32m#\e[0m" )
                    end
                end
            print "\n"
        end
    end
end

if __FILE__ == $0
  require "../utils/assert.rb"

  m = Map.new

  (0...$HEIGHT).each do |y|; (0...$WIDTH).each do |x|
      assert("equivalence of map[x,y] and map[x][y]"){ m[x,y] == m[x][y] }
  end; end

  assert("orthogonal neighbours") { m.neighbours(1, 1, false).length==4 }
  assert("all-around neighbours") { m.neighbours(1, 1, true ).length==8 }
  assert("orthogonal neighbours, at edge") { m.neighbours(0, 0, false).length==2 }
  assert("all-around neighbours, at edge") { m.neighbours($WIDTH-1, $HEIGHT-1, true).length==3 }

  seed = 732804 #rand(1_000_000)
  srand seed

  X_S, Y_S =  1,  1
  X_G, Y_G = 70, 20

  p = Player.new(X_S, Y_S)

  (0...$HEIGHT).each do |j|
      (0...$WIDTH).each do |i|
          m[i,j].rock = (rand(3)==0 ? true : false)
      end
  end
  m[X_S,Y_S].rock = false
  m[X_G,Y_G].rock = false

  t1 = Time.now
  path,tx = p.pathfind(m, X_G, Y_G)
  dt = Time.now - t1

  m.plot path, p

  raise "No path found" unless path
  puts "path traced in %fs, path length %d, iterations %d, random seed %d" % [dt, path.length, tx, seed]

  puts "unit test succeeded"
end