"""Common algorithms."""
import sys

__all__ = ["liangbarsky", "cohensutherland", "clipline", "point_on_line"]


def cohensutherland(left, top, right, bottom, x1, y1, x2, y2):
    """Clips a line to a rectangular area.

    This implements the Cohen-Sutherland line clipping algorithm. ``left``,
    ``top``, ``right`` and ``bottom`` define the bounds of the clipping area,
    by which the line from ``(x1, y1)`` to ``(x2, y2)`` will be clipped.

    Args:
        left (int): The left boundary of the clipping area.
        top (int): The top boundary of the clipping area.
        right (int): The right boundary of the clipping area.
        bottom (int): The bottom boundary of the clipping area.
        x1 (int): The x-coordinate of the starting point of the line.
        y1 (int): The y-coordinate of the starting point of the line.
        x2 (int): The x-coordinate of the end point of the line.
        y2 (int): The y-coordinate of the end point of the line.

    Returns:
        tuple: The start and end coordinates of the clipped line in the form
            ``(cx1, cy1, cx2, cy2)``. If the line does not intersect with the
            rectangular clipping area, all 4 values will be ``None``.

    """
    LEFT, RIGHT, LOWER, UPPER = 1, 2, 4, 8

    if bottom > top:
        bottom, top = (top, bottom)

    def _getclip(xa, ya):
        p = 0
        if xa < left:
            p = LEFT
        elif xa > right:
            p = RIGHT
        if ya < bottom:
            p |= LOWER
        elif ya > top:
            p |= UPPER
        return p

    k1 = _getclip(x1, y1)
    k2 = _getclip(x2, y2)
    while (k1 | k2) != 0:
        if (k1 & k2) != 0:
            return None, None, None, None
        opt = k2 if k2 > k1 else k1
        if opt & UPPER:
            x = x1 + (x2 - x1) * (1.0 * (top - y1)) / (y2 - y1)
            y = top
        elif opt & LOWER:
            x = x1 + (x2 - x1) * (1.0 * (bottom - y1)) / (y2 - y1)
            y = bottom
        elif opt & RIGHT:
            y = y1 + (y2 - y1) * (1.0 * (right - x1)) / (x2 - x1)
            x = right
        elif opt & LEFT:
            y = y1 + (y2 - y1) * (1.0 * (left - x1)) / (x2 - x1)
            x = left
        else:
            # this should not happen
            raise RuntimeError("invalid clipping state")

        if opt == k1:
            x1, y1 = x, y
            k1 = _getclip(x1, y1)
        else:
            x2, y2 = x, y
            k2 = _getclip(x2, y2)

    return x1, y1, x2, y2


def liangbarsky(left, top, right, bottom, x1, y1, x2, y2):
    """Clips a line to a rectangular area.

    This implements the Liang-Barsky line clipping algorithm. ``left``,
    ``top``, ``right`` and ``bottom`` define the bounds of the clipping area,
    by which the line from ``(x1, y1)`` to ``(x2, y2)`` will be clipped.

    Args:
        left (int): The left boundary of the clipping area.
        top (int): The top boundary of the clipping area.
        right (int): The right boundary of the clipping area.
        bottom (int): The bottom boundary of the clipping area.
        x1 (int): The x-coordinate of the starting point of the line.
        y1 (int): The y-coordinate of the starting point of the line.
        x2 (int): The x-coordinate of the end point of the line.
        y2 (int): The y-coordinate of the end point of the line.

    Returns:
        tuple: The start and end coordinates of the clipped line in the form
            ``(cx1, cy1, cx2, cy2)``. If the line does not intersect with the
            rectangular clipping area, all 4 values will be ``None``.

    """
    dx = x2 - x1 * 1.0
    dy = y2 - y1 * 1.0
    dt0, dt1 = 0.0, 1.0
    xx1 = x1
    yy1 = y1

    if bottom > top:
        bottom, top = (top, bottom)

    checks = ((-dx, x1 - left),
              (dx, right - x1),
              (-dy, y1 - bottom),
              (dy, top - y1))

    for p, q in checks:
        if p == 0 and q < 0:
            return None, None, None, None
        if p != 0:
            dt = q / (p * 1.0)
            if p < 0:
                if dt > dt1:
                    return None, None, None, None
                dt0 = max(dt0, dt)
            else:
                if dt < dt0:
                    return None, None, None, None
                dt1 = min(dt1, dt)

    if dt0 > 0:
        x1 += dt0 * dx
        y1 += dt0 * dy
    if dt1 < 1:
        x2 = xx1 + dt1 * dx
        y2 = yy1 + dt1 * dy

    return x1, y1, x2, y2


def clipline(l, t, r, b, x1, y1, x2, y2, method='liangbarsky'):
    """Clips a line to a rectangular area using a given method.

    Args:
        l (int): The left boundary of the clipping area.
        t (int): The top boundary of the clipping area.
        r (int): The right boundary of the clipping area.
        b (int): The bottom boundary of the clipping area.
        x1 (int): The x-coordinate of the starting point of the line.
        y1 (int): The y-coordinate of the starting point of the line.
        x2 (int): The x-coordinate of the end point of the line.
        y2 (int): The y-coordinate of the end point of the line.
        method (str, optional): The method to use for clipping lines, can be
            either 'cohensutherland' or 'liangbarsky'. Defaults to liangbarsky.

    Returns:
        tuple: The start and end coordinates of the clipped line in the form
            ``(cx1, cy1, cx2, cy2)``. If the line does not intersect with the
            rectangular clipping area, all 4 values will be ``None``.

    """
    if method == 'cohensutherland':
        return cohensutherland(l, t, r, b, x1, y1, x2, y2)
    elif method == 'liangbarsky':
        return liangbarsky(l, t, r, b, x1, y1, x2, y2)
    else:
        raise ValueError("Unknown clipping method '{0}'".format(method))


def point_on_line(p1, p2, point):
    """Checks if a point falls along a given line segment.

    Args:
        p1 (tuple): The (x, y) coordinates of the starting point of the line.
        p2 (tuple): The (x, y) coordinates of the end point of the line.
        point (tuple): The (x, y) coordinates to test against the line.
    
    Returns:
        bool: ``True`` if the point falls along the line segment, otherwise
            ``False``.

    """
    x1, y1 = p1
    x2, y2 = p2
    px, py = point
    det = (py - y1) * (x2 - x1) - (px - x1) * (y2 - y1)
    if abs(det) > sys.float_info.epsilon:
        return False
    return (min(x1, x2) <= px <= max(x1, x2) and
            min(y1, y2) <= py <= max(y1, y2))
