module PathTree
  (
    PathTree(..),DynTree(..),
    -- PathTree should be abstract...
    emptyPathTree,updateNode,mapPathTree,node,subTree,listNodes,
    attrMapPathTree,
    pruneTree,
    pos,unpos,spineVals
  ) where
import Direction
--import Path
import HbcUtils(apSnd)
import Maptrace(ctrace)

data PathTree n
   = Node n (PathTree n) (PathTree n)
   | Dynamic (DynTree (PathTree n))
   | Tip
   deriving (PathTree n -> PathTree n -> Bool
(PathTree n -> PathTree n -> Bool)
-> (PathTree n -> PathTree n -> Bool) -> Eq (PathTree n)
forall n. Eq n => PathTree n -> PathTree n -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: PathTree n -> PathTree n -> Bool
$c/= :: forall n. Eq n => PathTree n -> PathTree n -> Bool
== :: PathTree n -> PathTree n -> Bool
$c== :: forall n. Eq n => PathTree n -> PathTree n -> Bool
Eq, Eq (PathTree n)
Eq (PathTree n)
-> (PathTree n -> PathTree n -> Ordering)
-> (PathTree n -> PathTree n -> Bool)
-> (PathTree n -> PathTree n -> Bool)
-> (PathTree n -> PathTree n -> Bool)
-> (PathTree n -> PathTree n -> Bool)
-> (PathTree n -> PathTree n -> PathTree n)
-> (PathTree n -> PathTree n -> PathTree n)
-> Ord (PathTree n)
PathTree n -> PathTree n -> Bool
PathTree n -> PathTree n -> Ordering
PathTree n -> PathTree n -> PathTree n
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall n. Ord n => Eq (PathTree n)
forall n. Ord n => PathTree n -> PathTree n -> Bool
forall n. Ord n => PathTree n -> PathTree n -> Ordering
forall n. Ord n => PathTree n -> PathTree n -> PathTree n
min :: PathTree n -> PathTree n -> PathTree n
$cmin :: forall n. Ord n => PathTree n -> PathTree n -> PathTree n
max :: PathTree n -> PathTree n -> PathTree n
$cmax :: forall n. Ord n => PathTree n -> PathTree n -> PathTree n
>= :: PathTree n -> PathTree n -> Bool
$c>= :: forall n. Ord n => PathTree n -> PathTree n -> Bool
> :: PathTree n -> PathTree n -> Bool
$c> :: forall n. Ord n => PathTree n -> PathTree n -> Bool
<= :: PathTree n -> PathTree n -> Bool
$c<= :: forall n. Ord n => PathTree n -> PathTree n -> Bool
< :: PathTree n -> PathTree n -> Bool
$c< :: forall n. Ord n => PathTree n -> PathTree n -> Bool
compare :: PathTree n -> PathTree n -> Ordering
$ccompare :: forall n. Ord n => PathTree n -> PathTree n -> Ordering
$cp1Ord :: forall n. Ord n => Eq (PathTree n)
Ord, Int -> PathTree n -> ShowS
[PathTree n] -> ShowS
PathTree n -> String
(Int -> PathTree n -> ShowS)
-> (PathTree n -> String)
-> ([PathTree n] -> ShowS)
-> Show (PathTree n)
forall n. Show n => Int -> PathTree n -> ShowS
forall n. Show n => [PathTree n] -> ShowS
forall n. Show n => PathTree n -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PathTree n] -> ShowS
$cshowList :: forall n. Show n => [PathTree n] -> ShowS
show :: PathTree n -> String
$cshow :: forall n. Show n => PathTree n -> String
showsPrec :: Int -> PathTree n -> ShowS
$cshowsPrec :: forall n. Show n => Int -> PathTree n -> ShowS
Show)

data DynTree n
  = DynNode n (DynTree n) (DynTree n)
  | DynTip 
  deriving (DynTree n -> DynTree n -> Bool
(DynTree n -> DynTree n -> Bool)
-> (DynTree n -> DynTree n -> Bool) -> Eq (DynTree n)
forall n. Eq n => DynTree n -> DynTree n -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: DynTree n -> DynTree n -> Bool
$c/= :: forall n. Eq n => DynTree n -> DynTree n -> Bool
== :: DynTree n -> DynTree n -> Bool
$c== :: forall n. Eq n => DynTree n -> DynTree n -> Bool
Eq, Eq (DynTree n)
Eq (DynTree n)
-> (DynTree n -> DynTree n -> Ordering)
-> (DynTree n -> DynTree n -> Bool)
-> (DynTree n -> DynTree n -> Bool)
-> (DynTree n -> DynTree n -> Bool)
-> (DynTree n -> DynTree n -> Bool)
-> (DynTree n -> DynTree n -> DynTree n)
-> (DynTree n -> DynTree n -> DynTree n)
-> Ord (DynTree n)
DynTree n -> DynTree n -> Bool
DynTree n -> DynTree n -> Ordering
DynTree n -> DynTree n -> DynTree n
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall n. Ord n => Eq (DynTree n)
forall n. Ord n => DynTree n -> DynTree n -> Bool
forall n. Ord n => DynTree n -> DynTree n -> Ordering
forall n. Ord n => DynTree n -> DynTree n -> DynTree n
min :: DynTree n -> DynTree n -> DynTree n
$cmin :: forall n. Ord n => DynTree n -> DynTree n -> DynTree n
max :: DynTree n -> DynTree n -> DynTree n
$cmax :: forall n. Ord n => DynTree n -> DynTree n -> DynTree n
>= :: DynTree n -> DynTree n -> Bool
$c>= :: forall n. Ord n => DynTree n -> DynTree n -> Bool
> :: DynTree n -> DynTree n -> Bool
$c> :: forall n. Ord n => DynTree n -> DynTree n -> Bool
<= :: DynTree n -> DynTree n -> Bool
$c<= :: forall n. Ord n => DynTree n -> DynTree n -> Bool
< :: DynTree n -> DynTree n -> Bool
$c< :: forall n. Ord n => DynTree n -> DynTree n -> Bool
compare :: DynTree n -> DynTree n -> Ordering
$ccompare :: forall n. Ord n => DynTree n -> DynTree n -> Ordering
$cp1Ord :: forall n. Ord n => Eq (DynTree n)
Ord, Int -> DynTree n -> ShowS
[DynTree n] -> ShowS
DynTree n -> String
(Int -> DynTree n -> ShowS)
-> (DynTree n -> String)
-> ([DynTree n] -> ShowS)
-> Show (DynTree n)
forall n. Show n => Int -> DynTree n -> ShowS
forall n. Show n => [DynTree n] -> ShowS
forall n. Show n => DynTree n -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [DynTree n] -> ShowS
$cshowList :: forall n. Show n => [DynTree n] -> ShowS
show :: DynTree n -> String
$cshow :: forall n. Show n => DynTree n -> String
showsPrec :: Int -> DynTree n -> ShowS
$cshowsPrec :: forall n. Show n => Int -> DynTree n -> ShowS
Show)

emptyPathTree :: PathTree n
emptyPathTree = PathTree n
forall n. PathTree n
Tip
lookupPath :: (t -> a2) -> a2 -> PathTree t -> [Direction] -> a2
lookupPath t -> a2
f a2
z = (PathTree t -> a2) -> a2 -> PathTree t -> [Direction] -> a2
forall n a2.
Show n =>
(PathTree n -> a2) -> a2 -> PathTree n -> [Direction] -> a2
subTree (\(Node t
w PathTree t
_ PathTree t
_) -> t -> a2
f t
w) a2
z
subNodes :: PathTree a -> [Direction] -> [a]
subNodes PathTree a
x = (PathTree a -> [a]) -> [a] -> PathTree a -> [Direction] -> [a]
forall n a2.
Show n =>
(PathTree n -> a2) -> a2 -> PathTree n -> [Direction] -> a2
subTree ([a] -> PathTree a -> [a]
forall a. [a] -> PathTree a -> [a]
listNodes []) [] PathTree a
x

listNodes :: [a] -> PathTree a -> [a]
listNodes [a]
ns PathTree a
t =
    case PathTree a
t of
      PathTree a
Tip -> [a]
ns
      Node a
n PathTree a
l PathTree a
r -> [a] -> PathTree a -> [a]
listNodes ([a] -> PathTree a -> [a]
listNodes (a
n a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
ns) PathTree a
l) PathTree a
r
      Dynamic DynTree (PathTree a)
dt -> [a] -> DynTree (PathTree a) -> [a]
listDynNodes [a]
ns DynTree (PathTree a)
dt

listDynNodes :: [a] -> DynTree (PathTree a) -> [a]
listDynNodes [a]
ns DynTree (PathTree a)
dt =
    case DynTree (PathTree a)
dt of
      DynTree (PathTree a)
DynTip -> [a]
ns
      DynNode PathTree a
t DynTree (PathTree a)
l DynTree (PathTree a)
r -> [a] -> PathTree a -> [a]
listNodes ([a] -> DynTree (PathTree a) -> [a]
listDynNodes ([a] -> DynTree (PathTree a) -> [a]
listDynNodes [a]
ns DynTree (PathTree a)
r) DynTree (PathTree a)
l) PathTree a
t

subTree :: (PathTree n -> a2) -> a2 -> PathTree n -> [Direction] -> a2
subTree PathTree n -> a2
f a2
z PathTree n
Tip [Direction]
_ = a2
z
subTree PathTree n -> a2
f a2
z (Dynamic DynTree (PathTree n)
dt) [Direction]
p = (PathTree n -> [Direction] -> a2)
-> a2 -> DynTree (PathTree n) -> [Direction] -> a2
forall t p.
(t -> [Direction] -> p) -> p -> DynTree t -> [Direction] -> p
dynSelect ((PathTree n -> a2) -> a2 -> PathTree n -> [Direction] -> a2
subTree PathTree n -> a2
f a2
z) a2
z DynTree (PathTree n)
dt [Direction]
p
subTree PathTree n -> a2
f a2
z PathTree n
n [] = PathTree n -> a2
f PathTree n
n
subTree PathTree n -> a2
f a2
z (Node n
_ PathTree n
l PathTree n
_) (Direction
L : [Direction]
path') = (PathTree n -> a2) -> a2 -> PathTree n -> [Direction] -> a2
subTree PathTree n -> a2
f a2
z PathTree n
l [Direction]
path'
subTree PathTree n -> a2
f a2
z (Node n
_ PathTree n
_ PathTree n
r) (Direction
R : [Direction]
path') = (PathTree n -> a2) -> a2 -> PathTree n -> [Direction] -> a2
subTree PathTree n -> a2
f a2
z PathTree n
r [Direction]
path'
--subTree _ _ t p = error ("subTree _ _ "++show t++" "++show p)
-- Other cases of ill matching trees/paths return z, so why shouldn't this one?
subTree PathTree n -> a2
_ a2
z PathTree n
t [Direction]
p = String -> String -> a2 -> a2
forall a1 a2. Show a1 => String -> a1 -> a2 -> a2
ctrace String
"subTree" (String
"subTree _ _ "String -> ShowS
forall a. [a] -> [a] -> [a]
++PathTree n -> String
forall a. Show a => a -> String
show PathTree n
tString -> ShowS
forall a. [a] -> [a] -> [a]
++String
" "String -> ShowS
forall a. [a] -> [a] -> [a]
++[Direction] -> String
forall a. Show a => a -> String
show [Direction]
p) a2
z

{-
dynSubTree f z DynTip _ _ = z
dynSubTree f z (DynNode t _ _) 0 path' = subTree f z t path'
dynSubTree f z (DynNode _ l r) n path' =
    dynSubTree f z (if n `rem` 2 == 0 then l else r) (n `quot` 2) path'
-}
dynSelect :: (t -> [Direction] -> p) -> p -> DynTree t -> [Direction] -> p
dynSelect t -> [Direction] -> p
f p
z DynTree t
dn (Dno Int
n:[Direction]
p) = DynTree t -> Int -> p
forall t. Integral t => DynTree t -> t -> p
dynSelect' DynTree t
dn (Int -> Int
pos Int
n) where
   dynSelect' :: DynTree t -> t -> p
dynSelect' DynTree t
DynTip t
_ = p
z
   dynSelect' (DynNode t
t DynTree t
l DynTree t
r) t
n = if t
n t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 then t -> [Direction] -> p
f t
t [Direction]
p else
	     DynTree t -> t -> p
dynSelect' (if t
n t -> t -> t
forall a. Integral a => a -> a -> a
`rem` t
2 t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
0 then DynTree t
l else DynTree t
r) (t
n t -> t -> t
forall a. Integral a => a -> a -> a
`quot` t
2)
dynSelect t -> [Direction] -> p
f p
z DynTree t
dn [Direction]
_ = p
z

pruneNode :: n -> PathTree n -> [Direction] -> PathTree n
pruneNode n
e = n -> PathTree n -> PathTree n -> [Direction] -> PathTree n
forall n.
n -> PathTree n -> PathTree n -> [Direction] -> PathTree n
insertTree n
e PathTree n
forall n. PathTree n
Tip
insertTree :: n -> PathTree n -> PathTree n -> [Direction] -> PathTree n
insertTree n
n = (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
forall n.
(n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
forall a. a -> a
id n
n ((PathTree n -> PathTree n)
 -> PathTree n -> [Direction] -> PathTree n)
-> (PathTree n -> PathTree n -> PathTree n)
-> PathTree n
-> PathTree n
-> [Direction]
-> PathTree n
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PathTree n -> PathTree n -> PathTree n
forall a b. a -> b -> a
const
pruneTree :: (n -> n) -> n -> PathTree n -> [Direction] -> PathTree n
pruneTree n -> n
i n
e PathTree n
t [Direction]
path = (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
forall n.
(n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e (PathTree n -> PathTree n -> PathTree n
forall a b. a -> b -> a
const PathTree n
forall n. PathTree n
Tip) PathTree n
t [Direction]
path

updateNode :: (n -> n)
-> n -> PathTree n -> [Direction] -> (n -> n) -> PathTree n
updateNode n -> n
i n
e PathTree n
t [Direction]
path n -> n
f = (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
forall n.
(n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
g PathTree n
t [Direction]
path
  where g :: PathTree n -> PathTree n
g PathTree n
Tip = n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node (n -> n
f n
e) PathTree n
forall n. PathTree n
Tip PathTree n
forall n. PathTree n
Tip
        g (Node n
n PathTree n
l PathTree n
r) = n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node (n -> n
f n
n) PathTree n
l PathTree n
r

updTree :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t [Direction]
path' =
    case [Direction]
path' of
      [] -> PathTree n -> PathTree n
f PathTree n
t
      Direction
L : [Direction]
path'' -> (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updLeft n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t [Direction]
path''
      Direction
R : [Direction]
path'' -> (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updRight n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t [Direction]
path''
      Dno Int
n : [Direction]
path'' -> (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> Int
-> [Direction]
-> PathTree n
updateDyn n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t (Int -> Int
pos Int
n) [Direction]
path''

updLeft :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updLeft n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t [Direction]
path' =
    case PathTree n
t of
      PathTree n
Tip -> n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node n
e ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
forall n. PathTree n
Tip [Direction]
path') PathTree n
forall n. PathTree n
Tip
      Node n
n PathTree n
l PathTree n
r -> n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node (n -> n
i n
n) ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
l [Direction]
path') PathTree n
r
                    -- !!! space leak danger if i n is never used
		    -- need stingy evaluation!!
      Dynamic DynTree (PathTree n)
_ -> String -> PathTree n
forall a. HasCallStack => String -> a
error String
"PathTree.hs: updLeft (Dynamic _)"

updRight :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updRight n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t [Direction]
path' =
    case PathTree n
t of
      PathTree n
Tip -> n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node n
e PathTree n
forall n. PathTree n
Tip ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
forall n. PathTree n
Tip [Direction]
path')
      Node n
n PathTree n
l PathTree n
r -> n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node (n -> n
i n
n) PathTree n
l ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
r [Direction]
path')
                    -- !!! space leak danger if i n is never used
		    -- need stingy evaluation!!
      Dynamic DynTree (PathTree n)
_ -> String -> PathTree n
forall a. HasCallStack => String -> a
error String
"PathTree.hs: updRight (Dynamic _)"

updateDyn :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> Int
-> [Direction]
-> PathTree n
updateDyn n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t Int
n [Direction]
path' =
    case PathTree n
t of
      PathTree n
Tip -> DynTree (PathTree n) -> PathTree n
forall n. DynTree (PathTree n) -> PathTree n
Dynamic ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
forall n. DynTree n
DynTip Int
n [Direction]
path')
      Node n
_ PathTree n
_ PathTree n
_ -> DynTree (PathTree n) -> PathTree n
forall n. DynTree (PathTree n) -> PathTree n
Dynamic ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
forall n. DynTree n
DynTip Int
n [Direction]
path') -- throwing away part of the tree !!!
      Dynamic DynTree (PathTree n)
t' -> DynTree (PathTree n) -> PathTree n
forall n. DynTree (PathTree n) -> PathTree n
Dynamic ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
t' Int
n [Direction]
path')

updateDyn' :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
DynTip Int
0 [Direction]
path' =
    PathTree n
-> DynTree (PathTree n)
-> DynTree (PathTree n)
-> DynTree (PathTree n)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
forall n. PathTree n
Tip [Direction]
path') DynTree (PathTree n)
forall n. DynTree n
DynTip DynTree (PathTree n)
forall n. DynTree n
DynTip
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f (DynNode PathTree n
t DynTree (PathTree n)
l DynTree (PathTree n)
r) Int
0 [Direction]
path' = PathTree n
-> DynTree (PathTree n)
-> DynTree (PathTree n)
-> DynTree (PathTree n)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> PathTree n
-> [Direction]
-> PathTree n
updTree n -> n
i n
e PathTree n -> PathTree n
f PathTree n
t [Direction]
path') DynTree (PathTree n)
l DynTree (PathTree n)
r
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
t Int
n [Direction]
path' =
    (if Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` Int
2 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 then (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updDynLeft else (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updDynRight) n -> n
i n
e PathTree n -> PathTree n
f
                                                         DynTree (PathTree n)
t
                                                         (Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2)
                                                         [Direction]
path'

updDynLeft :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updDynLeft n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
t Int
n [Direction]
path' =
    case DynTree (PathTree n)
t of
      DynTree (PathTree n)
DynTip -> PathTree n
-> DynTree (PathTree n)
-> DynTree (PathTree n)
-> DynTree (PathTree n)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode PathTree n
forall n. PathTree n
Tip ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
forall n. DynTree n
DynTip Int
n [Direction]
path') DynTree (PathTree n)
forall n. DynTree n
DynTip
      DynNode PathTree n
t' DynTree (PathTree n)
l DynTree (PathTree n)
r -> PathTree n
-> DynTree (PathTree n)
-> DynTree (PathTree n)
-> DynTree (PathTree n)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode PathTree n
t' ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
l Int
n [Direction]
path') DynTree (PathTree n)
r

updDynRight :: (n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updDynRight n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
t Int
n [Direction]
path' =
    case DynTree (PathTree n)
t of
      DynTree (PathTree n)
DynTip -> PathTree n
-> DynTree (PathTree n)
-> DynTree (PathTree n)
-> DynTree (PathTree n)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode PathTree n
forall n. PathTree n
Tip DynTree (PathTree n)
forall n. DynTree n
DynTip ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
forall n. DynTree n
DynTip Int
n [Direction]
path')
      DynNode PathTree n
t' DynTree (PathTree n)
l DynTree (PathTree n)
r -> PathTree n
-> DynTree (PathTree n)
-> DynTree (PathTree n)
-> DynTree (PathTree n)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode PathTree n
t' DynTree (PathTree n)
l ((n -> n)
-> n
-> (PathTree n -> PathTree n)
-> DynTree (PathTree n)
-> Int
-> [Direction]
-> DynTree (PathTree n)
updateDyn' n -> n
i n
e PathTree n -> PathTree n
f DynTree (PathTree n)
r Int
n [Direction]
path')

pos :: Int->Int
pos :: Int -> Int
pos Int
0 = Int
0
pos Int
n = if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 then (-Int
2) Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n else Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1

unpos :: Int->Int
unpos :: Int -> Int
unpos Int
n =
  if Int -> Bool
forall a. Integral a => a -> Bool
even Int
n
  then -(Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2)
  else Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
2

mapPathTree :: (t -> n) -> PathTree t -> PathTree n
mapPathTree t -> n
f PathTree t
t =
  case PathTree t
t of
    Node t
n PathTree t
lt PathTree t
rt -> n -> PathTree n -> PathTree n -> PathTree n
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node (t -> n
f t
n) ((t -> n) -> PathTree t -> PathTree n
mapPathTree t -> n
f PathTree t
lt) ((t -> n) -> PathTree t -> PathTree n
mapPathTree t -> n
f PathTree t
rt)
    Dynamic DynTree (PathTree t)
dt -> DynTree (PathTree n) -> PathTree n
forall n. DynTree (PathTree n) -> PathTree n
Dynamic ((PathTree t -> PathTree n)
-> DynTree (PathTree t) -> DynTree (PathTree n)
forall t n. (t -> n) -> DynTree t -> DynTree n
mapDyn ((t -> n) -> PathTree t -> PathTree n
mapPathTree t -> n
f) DynTree (PathTree t)
dt)
    PathTree t
Tip -> PathTree n
forall n. PathTree n
Tip

mapDyn :: (t -> n) -> DynTree t -> DynTree n
mapDyn t -> n
f DynTree t
dt =
  case DynTree t
dt of
    DynNode t
n DynTree t
lt DynTree t
rt -> n -> DynTree n -> DynTree n -> DynTree n
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode (t -> n
f t
n) ((t -> n) -> DynTree t -> DynTree n
mapDyn t -> n
f DynTree t
lt) ((t -> n) -> DynTree t -> DynTree n
mapDyn t -> n
f DynTree t
rt)
    DynTree t
DynTip -> DynTree n
forall n. DynTree n
DynTip

attrMapPathTree :: (i -> [s] -> a -> (i,s,b)) -> i -> PathTree a -> 
		   ([s],PathTree b)
attrMapPathTree :: (i -> [s] -> a -> (i, s, b))
-> i -> PathTree a -> ([s], PathTree b)
attrMapPathTree i -> [s] -> a -> (i, s, b)
f i
i PathTree a
t = case PathTree a
t of
   Node a
n PathTree a
lt PathTree a
rt -> ([s
s],b -> PathTree b -> PathTree b -> PathTree b
forall n. n -> PathTree n -> PathTree n -> PathTree n
Node b
n' PathTree b
lt' PathTree b
rt') where
      ([s]
sl,PathTree b
lt') = (i -> [s] -> a -> (i, s, b))
-> i -> PathTree a -> ([s], PathTree b)
forall i s a b.
(i -> [s] -> a -> (i, s, b))
-> i -> PathTree a -> ([s], PathTree b)
attrMapPathTree i -> [s] -> a -> (i, s, b)
f i
i' PathTree a
lt
      ([s]
sr,PathTree b
rt') = (i -> [s] -> a -> (i, s, b))
-> i -> PathTree a -> ([s], PathTree b)
forall i s a b.
(i -> [s] -> a -> (i, s, b))
-> i -> PathTree a -> ([s], PathTree b)
attrMapPathTree i -> [s] -> a -> (i, s, b)
f i
i' PathTree a
rt
      (i
i',s
s,b
n') = i -> [s] -> a -> (i, s, b)
f i
i ([s]
sl[s] -> [s] -> [s]
forall a. [a] -> [a] -> [a]
++[s]
sr) a
n
      -- should perhaps extract ++ and []
   PathTree a
Tip -> ([],PathTree b
forall n. PathTree n
Tip)
   Dynamic DynTree (PathTree a)
dt -> (DynTree (PathTree b) -> PathTree b)
-> ([s], DynTree (PathTree b)) -> ([s], PathTree b)
forall t b a. (t -> b) -> (a, t) -> (a, b)
apSnd DynTree (PathTree b) -> PathTree b
forall n. DynTree (PathTree n) -> PathTree n
Dynamic ((i -> [s] -> a -> (i, s, b))
-> i -> DynTree (PathTree a) -> ([s], DynTree (PathTree b))
forall i a a b.
(i -> [a] -> a -> (i, a, b))
-> i -> DynTree (PathTree a) -> ([a], DynTree (PathTree b))
attrMapDyn i -> [s] -> a -> (i, s, b)
f i
i DynTree (PathTree a)
dt)

attrMapDyn :: (i -> [a] -> a -> (i, a, b))
-> i -> DynTree (PathTree a) -> ([a], DynTree (PathTree b))
attrMapDyn i -> [a] -> a -> (i, a, b)
f i
i DynTree (PathTree a)
dt = case DynTree (PathTree a)
dt of
   DynTree (PathTree a)
DynTip -> ([],DynTree (PathTree b)
forall n. DynTree n
DynTip)
   DynNode PathTree a
t DynTree (PathTree a)
lt DynTree (PathTree a)
rt -> ([a]
s[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a]
sl[a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++[a]
sr,PathTree b
-> DynTree (PathTree b)
-> DynTree (PathTree b)
-> DynTree (PathTree b)
forall n. n -> DynTree n -> DynTree n -> DynTree n
DynNode PathTree b
t' DynTree (PathTree b)
lt' DynTree (PathTree b)
rt') where
	     --        order?
      ([a]
sl,DynTree (PathTree b)
lt') = (i -> [a] -> a -> (i, a, b))
-> i -> DynTree (PathTree a) -> ([a], DynTree (PathTree b))
attrMapDyn i -> [a] -> a -> (i, a, b)
f i
i DynTree (PathTree a)
lt
      ([a]
sr,DynTree (PathTree b)
rt') = (i -> [a] -> a -> (i, a, b))
-> i -> DynTree (PathTree a) -> ([a], DynTree (PathTree b))
attrMapDyn i -> [a] -> a -> (i, a, b)
f i
i DynTree (PathTree a)
rt
      ([a]
s,PathTree b
t') = (i -> [a] -> a -> (i, a, b))
-> i -> PathTree a -> ([a], PathTree b)
forall i s a b.
(i -> [s] -> a -> (i, s, b))
-> i -> PathTree a -> ([s], PathTree b)
attrMapPathTree i -> [a] -> a -> (i, a, b)
f i
i PathTree a
t

spineVals :: PathTree a -> [Direction] -> [a]
spineVals PathTree a
t [Direction]
p = case PathTree a
t of
	  PathTree a
Tip -> []
	  Node a
v PathTree a
l PathTree a
r -> a
v a -> [a] -> [a]
forall a. a -> [a] -> [a]
: case [Direction]
p of
	       Direction
L:[Direction]
p' -> PathTree a -> [Direction] -> [a]
spineVals PathTree a
l [Direction]
p'
	       Direction
R:[Direction]
p' -> PathTree a -> [Direction] -> [a]
spineVals PathTree a
r [Direction]
p'
	       [Direction]
_    -> []
          Dynamic DynTree (PathTree a)
dt -> (PathTree a -> [Direction] -> [a])
-> [a] -> DynTree (PathTree a) -> [Direction] -> [a]
forall t p.
(t -> [Direction] -> p) -> p -> DynTree t -> [Direction] -> p
dynSelect PathTree a -> [Direction] -> [a]
spineVals [] DynTree (PathTree a)
dt [Direction]
p

node :: PathTree n -> (Maybe n, [PathTree n])
node PathTree n
t =
  case PathTree n
t of
    Node n
i PathTree n
lt PathTree n
rt -> (n -> Maybe n
forall a. a -> Maybe a
Just n
i,PathTree n -> [PathTree n] -> [PathTree n]
forall n. PathTree n -> [PathTree n] -> [PathTree n]
children PathTree n
lt (PathTree n -> [PathTree n] -> [PathTree n]
forall n. PathTree n -> [PathTree n] -> [PathTree n]
children PathTree n
rt []))
    PathTree n
Tip -> (Maybe n
forall a. Maybe a
Nothing,[])
    Dynamic DynTree (PathTree n)
dt -> (Maybe n
forall a. Maybe a
Nothing,DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
forall n. DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
dynChildren DynTree (PathTree n)
dt [])

children :: PathTree n -> [PathTree n] -> [PathTree n]
children PathTree n
t [PathTree n]
ts =
  case PathTree n
t of
    PathTree n
Tip -> [PathTree n]
ts
    Node n
_ PathTree n
_ PathTree n
_ -> PathTree n
tPathTree n -> [PathTree n] -> [PathTree n]
forall a. a -> [a] -> [a]
:[PathTree n]
ts
    Dynamic DynTree (PathTree n)
dt -> DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
dynChildren DynTree (PathTree n)
dt [PathTree n]
ts

dynChildren :: DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
dynChildren DynTree (PathTree n)
dt [PathTree n]
ts =
  case DynTree (PathTree n)
dt of
    DynTree (PathTree n)
DynTip -> [PathTree n]
ts
    DynNode PathTree n
t DynTree (PathTree n)
lt DynTree (PathTree n)
rt -> (PathTree n -> [PathTree n] -> [PathTree n]
children PathTree n
t ([PathTree n] -> [PathTree n])
-> ([PathTree n] -> [PathTree n]) -> [PathTree n] -> [PathTree n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
dynChildren DynTree (PathTree n)
lt ([PathTree n] -> [PathTree n])
-> ([PathTree n] -> [PathTree n]) -> [PathTree n] -> [PathTree n]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
dynChildren DynTree (PathTree n)
rt) [PathTree n]
ts
      -- !! order??