    module Bench.Vector.Algo.Quickhull (quickhull) where

    import Data.Vector.Unboxed as V

    quickhull :: (Vector Double, Vector Double) -> (Vector Double, Vector Double)
    {-# NOINLINE quickhull #-}
    quickhull :: (Vector Double, Vector Double) -> (Vector Double, Vector Double)
    quickhull (Vector Double
    xs, Vector Double
    ys) = Vector Double
    xs' Vector Double
    -> (Vector Double, Vector Double) -> (Vector Double, Vector Double)
    forall a b. a -> b -> b
    `seq` Vector Double
    ys' Vector Double
    -> (Vector Double, Vector Double) -> (Vector Double, Vector Double)
    forall a b. a -> b -> b
    `seq` (Vector Double
    xs',Vector Double
    ys')
        where
          (Vector Double
    xs',Vector Double
    ys') = Vector (Double, Double) -> (Vector Double, Vector Double)
    forall a b.
    (Unbox a, Unbox b) =>
    Vector (a, b) -> (Vector a, Vector b)
    V.unzip
                    (Vector (Double, Double) -> (Vector Double, Vector Double))
    -> Vector (Double, Double) -> (Vector Double, Vector Double)
    forall a b. (a -> b) -> a -> b
    $ Vector (Double, Double)
    -> (Double, Double) -> (Double, Double) -> Vector (Double, Double)
    forall {b}.
    (Num b, Unbox b, Ord b) =>
    Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
    hsplit Vector (Double, Double)
    points (Double, Double)
    pmin (Double, Double)
    pmax Vector (Double, Double)
    -> Vector (Double, Double) -> Vector (Double, Double)
    forall a. Unbox a => Vector a -> Vector a -> Vector a
    V.++ Vector (Double, Double)
    -> (Double, Double) -> (Double, Double) -> Vector (Double, Double)
    forall {b}.
    (Num b, Unbox b, Ord b) =>
    Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
    hsplit Vector (Double, Double)
    points (Double, Double)
    pmax (Double, Double)
    pmin

          imin :: Int
    imin = Vector Double -> Int
    forall a. (Unbox a, Ord a) => Vector a -> Int
    V.minIndex Vector Double
    xs
          imax :: Int
    imax = Vector Double -> Int
    forall a. (Unbox a, Ord a) => Vector a -> Int
    V.maxIndex Vector Double
    xs

          points :: Vector (Double, Double)
    points = Vector Double -> Vector Double -> Vector (Double, Double)
    forall a b.
    (Unbox a, Unbox b) =>
    Vector a -> Vector b -> Vector (a, b)
    V.zip Vector Double
    xs Vector Double
    ys
          pmin :: (Double, Double)
    pmin   = Vector (Double, Double)
    points Vector (Double, Double) -> Int -> (Double, Double)
    forall a. Unbox a => Vector a -> Int -> a
    V.! Int
    imin
          pmax :: (Double, Double)
    pmax   = Vector (Double, Double)
    points Vector (Double, Double) -> Int -> (Double, Double)
    forall a. Unbox a => Vector a -> Int -> a
    V.! Int
    imax

          hsplit :: Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
    hsplit Vector (b, b)
    points (b, b)
    p1 (b, b)
    p2
            | Vector (b, b) -> Int
    forall a. Unbox a => Vector a -> Int
    V.length Vector (b, b)
    packed Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    2 = (b, b)
    p1 (b, b) -> Vector (b, b) -> Vector (b, b)
    forall a. Unbox a => a -> Vector a -> Vector a
    `V.cons` Vector (b, b)
    packed
            | Bool
    otherwise = Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
    hsplit Vector (b, b)
    packed (b, b)
    p1 (b, b)
    pm Vector (b, b) -> Vector (b, b) -> Vector (b, b)
    forall a. Unbox a => Vector a -> Vector a -> Vector a
    V.++ Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
    hsplit Vector (b, b)
    packed (b, b)
    pm (b, b)
    p2
            where
              cs :: Vector b
    cs     = ((b, b) -> b) -> Vector (b, b) -> Vector b
    forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
    V.map (\(b, b)
    p -> (b, b) -> (b, b) -> (b, b) -> b
    forall {a}. Num a => (a, a) -> (a, a) -> (a, a) -> a
    cross (b, b)
    p (b, b)
    p1 (b, b)
    p2) Vector (b, b)
    points
              packed :: Vector (b, b)
    packed = (((b, b), b) -> (b, b)) -> Vector ((b, b), b) -> Vector (b, b)
    forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
    V.map ((b, b), b) -> (b, b)
    forall a b. (a, b) -> a
    fst
                     (Vector ((b, b), b) -> Vector (b, b))
    -> Vector ((b, b), b) -> Vector (b, b)
    forall a b. (a -> b) -> a -> b
    $ (((b, b), b) -> Bool) -> Vector ((b, b), b) -> Vector ((b, b), b)
    forall a. Unbox a => (a -> Bool) -> Vector a -> Vector a
    V.filter (\((b, b), b)
    t -> ((b, b), b) -> b
    forall a b. (a, b) -> b
    snd ((b, b), b)
    t b -> b -> Bool
    forall a. Ord a => a -> a -> Bool
    > b
    0)
                     (Vector ((b, b), b) -> Vector ((b, b), b))
    -> Vector ((b, b), b) -> Vector ((b, b), b)
    forall a b. (a -> b) -> a -> b
    $ Vector (b, b) -> Vector b -> Vector ((b, b), b)
    forall a b.
    (Unbox a, Unbox b) =>
    Vector a -> Vector b -> Vector (a, b)
    V.zip Vector (b, b)
    points Vector b
    cs

              pm :: (b, b)
    pm     = Vector (b, b)
    points Vector (b, b) -> Int -> (b, b)
    forall a. Unbox a => Vector a -> Int -> a
    V.! Vector b -> Int
    forall a. (Unbox a, Ord a) => Vector a -> Int
    V.maxIndex Vector b
    cs

          cross :: (a, a) -> (a, a) -> (a, a) -> a
    cross (a
    x,a
    y) (a
    x1,a
    y1) (a
    x2,a
    y2) = (a
    x1a -> a -> a
    forall a. Num a => a -> a -> a
    -a
    x)a -> a -> a
    forall a. Num a => a -> a -> a
    *(a
    y2a -> a -> a
    forall a. Num a => a -> a -> a
    -a
    y) a -> a -> a
    forall a. Num a => a -> a -> a
    - (a
    y1a -> a -> a
    forall a. Num a => a -> a -> a
    -a
    y)a -> a -> a
    forall a. Num a => a -> a -> a
    *(a
    x2a -> a -> a
    forall a. Num a => a -> a -> a
    -a
    x)