#################################
### COPYRIGHT: Anders Lyhagen ###
#################################

#Space Hashing on vertex positions. Uses sketchup's inbuilt tolerance for equality.
module CAUL_FAQS
class VertexHash
  
  @divX = 20.0 ; @divY = 20.0 ; @divZ = 20.0
  @dxInv; @dyInv; @dzInv
  @epsilon; @epsilonX; @epsilonY; @epsilonZ
  @bbMin = nil
  @bbMax = nil
  @hash
  @elements
  @bCount; @boxCalls
  @boxN
  
  def set_divisions(divX, divY, divZ)
    @divX = divX.floor.to_f
    @divY = divY.floor.to_f
    @divZ = divZ.floor.to_f
  end

  def set_bounds(bbMin, bbMax)
    @bbMin = bbMin.clone
    @bbMax = bbMax.clone
  end
  
  def set_box_epsilon(boxEpsilon)
  
  end
  
  def set_equal_epsilon(eEpsilon)
  
  end

  def init
    @elements = 0
    @bCount = @boxCalls = 0
    @epsilon = 0.002
    @dxInv = 1.0 / ((@bbMax.x - @bbMin.x) / @divX)
    @dyInv = 1.0 / ((@bbMax.y - @bbMin.y) / @divY)
    @dzInv = 1.0 / ((@bbMax.z - @bbMin.z) / @divZ)
    
    @epsilonX = @epsilon * @dxInv
    @epsilonY = @epsilon * @dyInv
    @epsilonZ = @epsilon * @dzInv
    
    @hash = []
    (0..@divX - 1).each { |i| @hash << []
      (0..@divY - 1).each { |j| @hash[i] << []
        (0..@divZ - 1).each { |k| @hash[i][j] << []
    }}}
    @boxN = []
    @boxN[18] = [[0, 0, 0], [0, 0, -1], [1, 0, -1], [1, 0, 0]]
    @boxN[26] = [[0, 0, 0], [0, 0, -1], [0, 1, -1], [0, 1, 0], [1, 0, -1], [1, 0, 0], [1, 1, -1], [1, 1, 0]]
    @boxN[24] = [[0, 0, 0], [0, 0, -1], [0, 1, -1], [0, 1, 0]]
    @boxN[25] = [[0, 0, 0], [-1, 0, -1], [-1, 0, 0], [-1, 1, -1], [-1, 1, 0], [0, 0, -1], [0, 1, -1], [0, 1, 0]]
    @boxN[17] = [[0, 0, 0], [-1, 0, -1], [-1, 0, 0], [0, 0, -1]]
    @boxN[21] = [[0, 0, 0], [-1, -1, -1], [-1, -1, 0], [-1, 0, -1], [-1, 0, 0], [0, -1, -1], [0, -1, 0], [0, 0, -1]]
    @boxN[20] = [[0, 0, 0], [0, -1, -1], [0, -1, 0], [0, 0, -1]]
    @boxN[22] = [[0, 0, 0], [0, -1, -1], [0, -1, 0], [0, 0, -1], [1, -1, -1], [1, -1, 0], [1, 0, -1], [1, 0, 0]]
    @boxN[2] = [[0, 0, 0], [1, 0, 0]]
    @boxN[10] = [[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0]]
    @boxN[8] = [[0, 0, 0], [0, 1, 0]]
    @boxN[9] = [[0, 0, 0], [-1, 0, 0], [-1, 1, 0], [0, 1, 0]]
    @boxN[1] = [[0, 0, 0], [-1, 0, 0]]
    @boxN[5] = [[0, 0, 0], [-1, -1, 0], [-1, 0, 0], [0, -1, 0]]
    @boxN[4] = [[0, 0, 0], [0, -1, 0]]
    @boxN[6] = [[0, 0, 0], [0, -1, 0], [1, -1, 0], [1, 0, 0]]
    @boxN[34] = [[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1]]
    @boxN[42] = [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
    @boxN[40] = [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]]
    @boxN[41] = [[0, 0, 0], [-1, 0, 0], [-1, 0, 1], [-1, 1, 0], [-1, 1, 1], [0, 0, 1], [0, 1, 0], [0, 1, 1]]
    @boxN[33] = [[0, 0, 0], [-1, 0, 0], [-1, 0, 1], [0, 0, 1]]
    @boxN[37] = [[0, 0, 0], [-1, -1, 0], [-1, -1, 1], [-1, 0, 0], [-1, 0, 1], [0, -1, 0], [0, -1, 1], [0, 0, 1]]
    @boxN[36] = [[0, 0, 0], [0, -1, 0], [0, -1, 1], [0, 0, 1]]
    @boxN[38] = [[0, 0, 0], [0, -1, 0], [0, -1, 1], [0, 0, 1], [1, -1, 0], [1, -1, 1], [1, 0, 0], [1, 0, 1]]
    @boxN[32] = [[0, 0, 0], [0, 0, 1]]
    @boxN[16] = [[0, 0, 0], [0, 0, -1]]
    @boxN[0] = [[0, 0, 0]]
  end
  
  
  #NOTE: we need an add_vertex_tol method!!
  def add_vertex(v)
    ind = get_box(v.position)  
    return false unless ind
    
    hc = @hash[ind[0]][ind[1]][ind[2]]
    vp = nil
    hc.each { |he| 
      if he[0] == v.position
        vp = he; break
      end
    }
    if vp == nil
      hc << [v.position.clone, v]
    else
      vp << v
    end
    @elements += 1
    return true
  end
  
  def get_position_elem_tol(p)
    #puts 'get_position_elem_tol(p)  '+p.to_s
    ind, code = get_boxes_tol(p)
    #puts ind.to_s
    return nil unless ind
    @boxN[code].each { |b| 
      if valid_ind?(ind[0] + b[0], ind[1] + b[1], ind[2] + b[2])
        @hash[ind[0] + b[0]][ind[1] + b[1]][ind[2] + b[2]].each { |he| return he if he[0] == p }
      end
    }
    return nil
  end
  
  def valid_ind?(x, y, z)
    return false if x < 0 || y < 0 || z < 0 || x >= @divX || y >= @divY || z >= @divZ
    return true
  end
  
  def get_position_elem(p)
    ind = get_box(p)
    return false unless ind    
    @hash[ind[0]][ind[1]][ind[2]].each { |he| return he if he[0] == p }
    return nil
  end
  
  def has_position?(p)
    return get_position_elem_tol(p) != nil
  end
  
  def has_vertex?(v)
    he = get_position_tol(p) 
    return false if he == nil
    for i in 1..he.length - 1
      return true if he[i] == v 
    end
    return false
  end
  
  def get_edge(p0, p1)
    he = get_position_elem_tol(p0) 
    return nil if he == nil
    for i in 1..he.length - 1
      he[i].edges.each { |e| return e if get_other_vertex(e, p0).position == p1}
    end
    return nil
  end
  
  def get_other_vertex(e, p)
    return e.start.position == p ? e.end : e.start
  end
  
 
  def get_face(ps)
    e = get_edge(ps[0], ps[1])    
    return nil if e == nil
    cf = []
    e.faces.each { |f| cf << f }
    for i in 1..ps.length - 1
      e = get_edge(ps[i], ps[(i + 1) % ps.length])
      return nil if e == nil
      cf = cf & e.faces
      break if cf.length == 1
      break if cf.length == 0
    end
    
    #if we have more than one face, make sure that the edge e
    #is in the outer_loop of the faces and not in the inner loop
    if cf.length > 1
      res = []
      cf.each { |f| res << f if f.outer_loop.vertices.length == ps.length }
      return res if res.length < 2
      #more conclusive test...
      res2 = []
      res.each { |f|
        include = false
        f.outer_loop.edges.each { |e2|
          if e2 == e
            include = true
            break
          end
        }
        res2 << f if include
      }
      
      return res2
    end
    
    return cf
  
  end
  
  def get_max_load()
    ml = 0
    (0..@divX - 1).each { |i|
      (0..@divY - 1).each { |j|
        (0..@divZ - 1).each { |k| 
          ml = [ml, @hash[i][j][k].length].max
    }}}
    return ml
  end
  

  ######################
  ##### GET BOX(ES) ####
  ######################
  def get_boxes_tol(p)
    x = ((p.x - @bbMin.x) * @dxInv); xf = x.floor; bx = x - xf;
    y = ((p.y - @bbMin.y) * @dyInv); yf = y.floor; by = y - yf;
    z = ((p.z - @bbMin.z) * @dzInv); zf = z.floor; bz = z - zf;

    bbx = bx < @epsilonX ? 1 : ((1 - bx) < @epsilonX) ? 2 : 0 
    bby = by < @epsilonY ? 4 : ((1 - by) < @epsilonY) ? 8 : 0
    bbz = bz < @epsilonZ ? 16 : ((1 - bz) < @epsilonZ) ? 32 : 0
    
    code = bbx + bby + bbz
    @bCount += 1 unless code == 0
    @boxCalls += 1
    return nil if xf < 0 || yf < 0 || zf < 0 || xf >= @divX || yf >= @divY || zf >= @divZ
    return [xf, yf, zf], code
  end
  
  def get_box(p)
    x = ((p.x - @bbMin.x) * @dxInv).floor
    y = ((p.y - @bbMin.y) * @dyInv).floor
    z = ((p.z - @bbMin.z) * @dzInv).floor 
    return nil if x < 0 || y < 0 || z < 0 || x >= @divX || y >= @divY || z >= @divZ
    return [x, y, z]
  end
  
  #######################
  
  def print_info()
    s = '## Vertex Hash ##' + "\n"
    s += 'divX = '+@divX.to_s+"\n"+'divY = '+@divY.to_s+"\n"+ 'divZ = '+@divZ.to_s+"\n"
    s += 'MIN = '+@bbMin.to_s+"\n"
    s += 'MAX = '+@bbMax.to_s+"\n"
    s += "\n"
    s += 'Elements: '+@elements.to_s+ "\n"
    s += 'Max Load: '+get_max_load.to_s+"\n"
    s += 'B ratio : '+((@bCount / @boxCalls.to_f) * 100).to_s+' %' "\n"
  end

end
end
