#!/usr/bin/env ruby

module BoxFinder
  VERSION = '0.1.0'

  Box = Struct.new(:x, :y, :w, :h)

  class Finder
    attr_accessor :boxes

    def initialize(boxes)
      @boxes = boxes
    end

    def nearest(box_i, dir)
      # get current box, and set closest box to nil
      src, c = @boxes[box_i], nil

      # must have at least two boxes to compare
      return nil unless @boxes.length > 2

      # iterate over all boxes
      @boxes.each_with_index do |box, i|
        # skip src box
        next if i == box_i

        case dir
        when 'left'
          # 
          # look for boxes that intersect this region:
          #
          #           |        |
          #           |        |
          #           |        |
          #   --------------------------
          #   xxxxxxxx|        |
          #   x here x|  src   |  
          #   xxxxxxxx|        |
          #   --------------------------
          #           |        |
          #           |        |
          #           |        |

          # skip boxes to the right of src
          next if box.x > src.x

          # skip boxes that do not intersect the region
          # bounded by the left edge of the screen and the 
          # left edge of the src rectangle
          next if box.y + box.h < src.y ||
                  box.y > src.y + src.h

          # check to see if this box is closer than the current result
          c = i if !c || box.x > @boxes[c].x
        when 'right'
          # 
          # look for boxes that intersect this region:
          #
          #           |        |
          #           |        |
          #           |        |
          #   --------------------------
          #           |        |xxxxxxxx
          #           |  src   |x here x 
          #           |        |xxxxxxxx
          #   --------------------------
          #           |        |
          #           |        |
          #           |        |

          # skip boxes to the left of src
          next if box.x < src.x

          # skip boxes that do not intersect the region
          # bounded by the right edge of the src rectangle
          # and the right edge of the screen
          next if box.y + box.h < src.y ||
                  box.y > src.y + src.h

          # check to see if this box is closer than the current result
          c = i if !c || box.x < @boxes[c].x
        when 'above'
          # look for boxes that intersect this region:
          #
          #           |xxxxxxxx|
          #           |x here x|
          #           |xxxxxxxx|
          #   --------------------------
          #           |        |
          #           |  src   |
          #           |        |
          #   --------------------------
          #           |        |
          #           |        |
          #           |        |

          # skip boxes below src
          next if box.y > src.y

          # skip boxes that do not intersect the region
          # bounded by the top edge of the screen and the
          # and the top edge of the src rectangle
          next if box.x + box.w < src.w ||
                  box.x > src.x + src.w

          # check to see if this box is closer than the current result
          c = i if !c || box.y > @boxes[c].y
        when 'below'
          # 
          # look for boxes that intersect this region:
          #
          #           |        |
          #           |        |
          #           |        |
          #   --------------------------
          #           |        |
          #           |  src   |
          #           |        |
          #   --------------------------
          #           |xxxxxxxx|
          #           |x here x|
          #           |xxxxxxxx|

          # skip boxes above src
          next if box.y < src.y

          # skip boxes that do not intersect the region
          # bounded by the bottom edge of the src rectangle
          # and the bottom edge of the screen
          next if box.x + box.w < src.w ||
                  box.x > src.x + src.w

          # check to see if this box is closer than the current result
          c = i if !c || box.y < @boxes[c].y
        else 
          raise Error, "unknown direction: #{dir}"
        end
      end

      # if we have found a box, then return now
      return @boxes[c] if c

      # at this point we loop through all the boxes again and do a
      # distance comparison (XXX: this could be optimized by building a
      # sorted list of boxes in the previous loop)

      # set current minimum displacement to nil
      cd = nil

      # iterate over all boxes
      @boxes.each_with_index do |box, i|
        case dir
        when 'left'
          #
          # look for boxes within this region:
          #
          #   xxxxxxxx|        |
          #   xxxxxxxx|        |
          #   xxxxxxxx|        |
          #   --------------------------
          #   xxxxxxxx|        |
          #   x here x|  src   |  
          #   xxxxxxxx|        |
          #   --------------------------
          #   xxxxxxxx|        |
          #   xxxxxxxx|        |
          #   xxxxxxxx|        |

          # skip boxes to the right of src
          next if box.x > src.x
        when 'right'
          #
          # look for boxes within this region:
          #
          #           |        |xxxxxxxx
          #           |        |xxxxxxxx
          #           |        |xxxxxxxx
          #   --------------------------
          #           |        |xxxxxxxx
          #           |  src   |x here x 
          #           |        |xxxxxxxx
          #   --------------------------
          #           |        |xxxxxxxx
          #           |        |xxxxxxxx
          #           |        |xxxxxxxx

          # skip boxes to the left of src
          next if box.x < src.x
        when 'above'
          #
          # look for boxes within this region:
          #
          #   xxxxxxxx|xxxxxxxx|xxxxxxxx 
          #   xxxxxxxx|x here x|xxxxxxxx 
          #   xxxxxxxx|xxxxxxxx|xxxxxxxx
          #   --------------------------
          #           |        |
          #           |  src   |
          #           |        |
          #   --------------------------
          #           |        |
          #           |        |
          #           |        |

          # skip boxes below src
          next if box.y > src.y
        when 'below'
          #
          # look for boxes within this region:
          #
          #           |        |
          #           |        |
          #           |        |
          #   --------------------------
          #           |        |
          #           |  src   |
          #           |        |
          #   --------------------------
          #   xxxxxxxx|xxxxxxxx|xxxxxxxx 
          #   xxxxxxxx|x here x|xxxxxxxx 
          #   xxxxxxxx|xxxxxxxx|xxxxxxxx

          # skip boxes above src
          next if box.y < src.y
        else
          # never reached
          raise Error, "unknown direction: #{dir}"
        end

        # calculate distance between box and src
        bd = distance(box, src)

        # see if it's closer than the current result
        if !c || bd < cd
          cd = bd
          c = i
        end
      end

      # return matching box, or nil
      c ? @boxes[c] : nil
    end

    private

    # calculate the distance between two boxes
    def distance(a, b)
      Math.sqrt(
        (a.x + a.w/2.0) - (b.x + b.w/2.0) ** 2 +
        (a.y + a.h/2.0) - (b.y + b.h/2.0) ** 2
      )
    end
  end
end