module Bench.Vector.TestData.ParenTree where

import qualified Data.Vector.Unboxed as V

parenTree :: Int -> (V.Vector Int, V.Vector Int)
parenTree :: Int -> (Vector Int, Vector Int)
parenTree Int
n = case ([Int], [Int]) -> Int -> Int -> ([Int], [Int])
forall {t}. Integral t => ([t], [t]) -> t -> t -> ([t], [t])
go ([],[]) Int
0 (if Int -> Bool
forall a. Integral a => a -> Bool
even Int
n then Int
n else Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) of
               ([Int]
ls,[Int]
rs) -> (Int -> [Int] -> Vector Int
forall a. Unbox a => Int -> [a] -> Vector a
V.fromListN ([Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
ls) ([Int] -> [Int]
forall a. [a] -> [a]
reverse [Int]
ls),
                           Int -> [Int] -> Vector Int
forall a. Unbox a => Int -> [a] -> Vector a
V.fromListN ([Int] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [Int]
rs) ([Int] -> [Int]
forall a. [a] -> [a]
reverse [Int]
rs))
  where
    go :: ([t], [t]) -> t -> t -> ([t], [t])
go ([t]
ls,[t]
rs) t
i t
j = case t
jt -> t -> t
forall a. Num a => a -> a -> a
-t
i of
                       t
0 -> ([t]
ls,[t]
rs)
                       t
2 -> ([t]
ls',[t]
rs')
                       t
d -> let k :: t
k = ((t
dt -> t -> t
forall a. Num a => a -> a -> a
-t
2) t -> t -> t
forall a. Integral a => a -> a -> a
`div` t
4) t -> t -> t
forall a. Num a => a -> a -> a
* t
2
                            in
                            ([t], [t]) -> t -> t -> ([t], [t])
go (([t], [t]) -> t -> t -> ([t], [t])
go ([t]
ls',[t]
rs') (t
it -> t -> t
forall a. Num a => a -> a -> a
+t
1) (t
it -> t -> t
forall a. Num a => a -> a -> a
+t
1t -> t -> t
forall a. Num a => a -> a -> a
+t
k)) (t
it -> t -> t
forall a. Num a => a -> a -> a
+t
1t -> t -> t
forall a. Num a => a -> a -> a
+t
k) (t
jt -> t -> t
forall a. Num a => a -> a -> a
-t
1)
      where
        ls' :: [t]
ls' = t
it -> [t] -> [t]
forall a. a -> [a] -> [a]
:[t]
ls
        rs' :: [t]
rs' = t
jt -> t -> t
forall a. Num a => a -> a -> a
-t
1t -> [t] -> [t]
forall a. a -> [a] -> [a]
:[t]
rs