module Numeric.Interpolation.NodeList (
   T(Interval, Node),
   fromList,
   toList,
   singleton,
   lookup,
   ) where

import Data.Tuple.HT (mapFst)

import Prelude hiding (lookup)


data T x y = Interval | Node (x, y) (T x y) (T x y)
   deriving (Eq, Ord, Show)

{- |
list must be sorted with respect to first element
-}
fromList :: [(x,y)] -> T x y
fromList =
   let merge n0 xys0 =
          case xys0 of
             (xy0,n1):(xy1,n2):xys ->
                (Node xy0 n0 n1,
                 uncurry (:) $ mapFst ((,) xy1) $ merge n2 xys)
             (xy0,n1):[] -> (Node xy0 n0 n1, [])
             [] -> (n0, [])
       rep (n,xyns) = if null xyns then n else rep $ merge n xyns
   in  rep . merge Interval . map (flip (,) Interval)

singleton :: x -> y -> T x y
singleton x y = Node (x,y) Interval Interval

toList :: T x y -> [(x,y)]
toList =
   let go Interval = []
       go (Node p l r) = go l ++ p : go r
   in  go

lookup :: Ord x => T x y -> x -> (Maybe (x,y), Maybe (x,y))
lookup nodes0 x0 =
   let go lb rb Interval = (lb, rb)
       go lb rb (Node n@(x,_y) ln rn) =
          if x0>=x
            then go (Just n) rb rn
            else go lb (Just n) ln
   in  go Nothing Nothing nodes0