import numpy as np
from numba import jit, njit
from copy import copy
from enum import Enum, unique, auto
import 靴紐

@unique
class Order(Enum):
    CLOCKWISE = auto()
    COUNTERCLOCKWISE = auto()

@jit
def ensure(xys, order=Order.COUNTERCLOCKWISE):
    """
    args
        xys, ndarray
            of shape (n_pts, 2)
        order, CLOCKWISE/COUNTERCLOCKWISE


    return
        ordered_xys, ndarray

    Note. This function only works for convex polygones in 2D space.
    """
    if order not in set(Order):
        raise TypeError("order arg should be either Order.CLOCKWISE or Order.COUNTERCLOCKWISE")

    # We construct a list of indices that corresponds to clockwise order
    n = len(xys)
    clockwise_indices = [0]
    remaining_indices = list(range(1, n))
    while len(remaining_indices) > 1:
        best_index = remaining_indices[0]
        u = xys[best_index, :] - xys[clockwise_indices[-1], :]
        for index in range(1, len(remaining_indices)):
            v = xys[remaining_indices[index], :] - xys[clockwise_indices[-1], :]
            A = np.array([u, v])
            determinant = np.linalg.det(A)
            if determinant > 0:
                best_index = remaining_indices[index]
                u = v
            elif determinant == 0:
                raise ValueError("det(A) == 0 => two edges of the polygone colinear")
        clockwise_indices.append(best_index)
        remaining_indices.remove(best_index)
    clockwise_indices.append(remaining_indices[0])
    if order == Order.CLOCKWISE:
        ordered_xys = xys[clockwise_indices]
    else:
        ordered_xys = xys[[clockwise_indices[i%n] for i in range(0, -n, -1)]]
    return ordered_xys

@jit
def area(xys):
    xs = xys[:, 0]
    ys = xys[:, 1]
    n = len(xys)
    # the following line cannot be jit-ed, but the one following it can,
    # no jit here does not give good performance, if not worsen.
    #A = sum(ys[k]*(xs[(k-1)%n] - xs[(k+1)%n])for k in range(n)) * 0.5
    A = sum([ys[k]*(xs[(k-1)%n] - xs[(k+1)%n])for k in range(n)]) * 0.5
    return A

@jit
def area_vectorize(xys):
    xs = xys[:, 0]
    ys = xys[:, 1]
    n = len(xys)
    shifted_left = xs[[(i-1) % n for i in range(n)]]
    shifted_right = xs[[(i+1) % n for i in range(n)]]
    A = np.dot(ys, shifted_left - shifted_right).astype(np.float32) * 0.5
    return A

@njit
def area_stackoverflow(xys):
    xs = xys[:, 0]
    ys = xys[:, 1]
    S1 = np.sum(xs * np.roll(ys, -1))
    S2 = np.sum(ys * np.roll(xs, -1))
    A = .5 * np.abs(S1 - S2)
    return A
