"""
distances.py -- V.0.10, Feb 27 2006, by leonardo maffi

Functions (mostly for 2D) to computer various distance metrics.
Most functiosn take the two coordinates of the two points like this:
  (x1, y1), (x2, y2)

TODO: some doctests can be added.
"""

from math import hypot, sqrt
from itertools import izip #for euclidean_distance_nd and sqr_euclidean_distance_nd

def euclidean_distance_2d((x1, y1), (x2, y2)):
    """euclidean_distance_2d((x1, y1), (x2, y2)): computes the usual euclidean
    distance between two given 2D points."""
    return hypot(x1 - x2, y1 - y2)


def sqr_euclidean_distance_2d((x1, y1), (x2, y2)):
    """sqr_euclidean_distance_2d((x1, y1), (x2, y2)): computes the square of the
    euclidean distance between two given 2D points.
    Faster than euclidean_distance."""
    dx = x1 - x2
    dy = y1 - y2
    return dx * dx  +  dy * dy


def euclidean_distance_nd(p1, p2):
    """euclidean_distance_nd(p1, p2): the usual euclidean distance between
    two given points in n dimensions."""
    return sqrt( sum((c1-c2)*(c1-c2) for c1,c2 in izip(p1, p2)) )


def sqr_euclidean_distance_nd(p1, p2):
    """sqr_euclidean_distance_nd(p1, p2): computes the square of the euclidean
    distance between two given points in n dimensions.
    Faster than euclidean_distance_nd."""
    return sum((c1-c2)*(c1-c2) for c1,c2 in izip(p1, p2))


def manhattan_distance_2d((x1, y1), (x2, y2)):
    """manhattan_distance_2d((x1, y1), (x2, y2))  (or cityblock_distance):
    the sum of the difference of the two coordintes.
    Shape of this distance function:
          ,
         ,^,
        ,^*^,
       ,^*x*^,
      ,^*xfx*^,
     ,^*xfHfx*^,
    ,^*xfH#Hfx*^,
     ,^*xfHfx*^,
      ,^*xfx*^,
       ,^*x*^,
        ,^*^,
         ,^,
          ,
    """
    # A similar function can be created for n dimensions
    return abs(x1 - x2) + abs(y1 - y2)


cityblock_distance_2d = manhattan_distance_2d


def chessboard_distance_2d((x1, y1), (x2, y2)):
    """chessboard_distance_2d((x1, y1), (x2, y2)): the maximum between the two
    coordinate differences. Shape of this distance function:
    ,,,,,,,,,,,,,
    ,^^^^^^^^^^^,
    ,^*********^,
    ,^*xxxxxxx*^,
    ,^*xfffffx*^,
    ,^*xfHHHfx*^,
    ,^*xfH#Hfx*^,
    ,^*xfHHHfx*^,
    ,^*xfffffx*^,
    ,^*xxxxxxx*^,
    ,^*********^,
    ,^^^^^^^^^^^,
    ,,,,,,,,,,,,,
    """
    # A similar function can be created for n dimensions
    adx = abs(x1 - x2)
    ady = abs(y1 - y2)
    return (adx if adx > ady else ady) # max(adx, ady)


def hexagonal_distance_2d((x1, y1), (x2, y2)):
    """hexagonal_distance_2d((x1, y1), (x2, y2)): a hexagonal-shaped distance
    function. Shape of this distance function:
       ,,,,,,,
      .-^^^^^-.
      ,^*****^,
     .-=oxxxo=-.
     ,^*xfffx*^,
    .-=o8kHk8o=-.
    ,^*xfH#Hfx*^,
    .-=o8kHk8o=-.
     ,^*xfffx*^,
     .-=oxxxo=-.
      ,^*****^,
      .-^^^^^-.
       ,,,,,,,
    """
    part1 = abs(x1 - x2)
    part2 = 0.5*(abs(x1 - x2) + (x1 - x2)) - (x1/2.0 - x2/2.0) + y1 - y2
    part3 = 0.5*(abs(x1 - x2) - (x1 - x2)) + (x1/2.0 - x2/2.0) + y2 - y1
    return max(part1, part2, part3)


def octagonal_distance_2d((x1, y1), (x2, y2)):
    """octagonal_distance_2d((x1, y1), (x2, y2)): a octagonal-shaped distance
    function. Shape of this distance function:
       .,,,,,.
      .,~^^^~,.
     .,~=***=~,.
    .,~=*OxO*=~,.
    ,~=*O8f8O*=~,
    ,^*O8fBf8O*^,
    ,^*xfBWBfx*^,
    ,^*O8fBf8O*^,
    ,~=*O8f8O*=~,
    .,~=*OxO*=~,.
     .,~=***=~,.
      .,~^^^~,.
       .,,,,,.
    """
    adx = abs(x1 - x2)
    ady = abs(y1 - y2)
    g = 2.0/3.0 * (adx + ady + 1)
    return max(adx, ady, g)


# def triangular_distance_2d((x1, y1), (x2, y2)):
#     tx1,ty1,tz1 = projection of (x1,y1) on the 3 axis rotated by 120 degrees from each other.
#     tx2,ty2,tz2 = likewise for (x2,y2)
#     return max(abs(tx1-tx2), abs(ty1-ty2), abs(tz1-tz2))


def minkowski_distance_2d((x1, y1), (x2, y2), p):
    """minkowski_distance_2d((x1, y1), (x2, y2), p): Minkowski metric function.
    With p=1 it equals to the Manhattan metric, with p=2 it equals to the Euclidean
    metric."""
    adx = abs(x1 - x2)
    ady = abs(y1 - y2)
    return (adx**p  +  ady**p) ** (1.0/p)


if __name__ == "__main__": # Some demos -----------------------------------------------
#     import doctest
#     doctest.testmod()
#     print "Doctests finished.\n"

    print "A test of some distances:\n"

    from functools import partial # Python 2.5
    from array import array


    class Charmat(object): # from matrix module, reduced
        """Charmat(nrows, ncols): class that manages a 2D matrix of chars,
        implemented with an array.array("c")."""
        def __init__(self, nrows, ncols):
            self.nr = nrows
            self.nc = ncols
            self.mat = array("c", " " * (nrows * ncols))
        def __setitem__(self, (r, c), char):
            self.mat[self.nc * r + c] = char
        def __str__(self):
            nr = self.nr
            nc = self.nc
            return "\n".join(self.mat[i:i+nc].tostring() for i in xrange(0, len(self.mat), nc))


    def dist_ascii_density_plot(dist):
        m = Charmat(13, 13)
        #s = ".;=*%@$#"[::-1] + " " * 100
        s = "#@WHBkf$8xOo*+=^~-,:."  + " " * 1000
        center = m.nc // 2,  m.nr // 2
        for r in xrange(m.nr):
            for c in xrange(m.nc):
                d = dist(center, (r, c)) * 3.0
                m[r,c] = s[int(round(d))]
        print m


    distances = [chessboard_distance_2d, cityblock_distance_2d, euclidean_distance_2d,
                 hexagonal_distance_2d, manhattan_distance_2d, octagonal_distance_2d,
                 sqr_euclidean_distance_2d]

    for dist in distances:
        print dist.__name__ + ":"
        dist_ascii_density_plot(dist)
        print

    # computed with cfrange() from utils module
    ps = [ 0.3,0.4, 0.6, 0.8, 1.0,
          1.2, 1.4, 1.6, 1.8, 2.0,
          2.2, 2.4, 2.6, 2.8, 3.0,
          3.2, 3.4, 3.6, 3.8, 4.0,
          4.2, 4.4, 4.6, 4.8]
    for p in ps:
        print 'minkowski_distance, p =', p
        dist_ascii_density_plot(partial(minkowski_distance_2d, p=p))
        print