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
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, PathTree n -> PathTree n -> Bool
PathTree n -> PathTree n -> Ordering
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
Ord, Int -> PathTree n -> ShowS
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
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, DynTree n -> DynTree n -> Bool
DynTree n -> DynTree n -> Ordering
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
Ord, Int -> DynTree n -> ShowS
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 = forall n. PathTree n
Tip
lookupPath :: (t -> t) -> t -> PathTree t -> [Direction] -> t
lookupPath t -> t
f t
z = forall {n} {t}.
Show n =>
(PathTree n -> t) -> t -> PathTree n -> [Direction] -> t
subTree (\(Node t
w PathTree t
_ PathTree t
_) -> t -> t
f t
w) t
z
subNodes :: PathTree n -> [Direction] -> [n]
subNodes PathTree n
x = forall {n} {t}.
Show n =>
(PathTree n -> t) -> t -> PathTree n -> [Direction] -> t
subTree (forall {a}. [a] -> PathTree a -> [a]
listNodes []) [] PathTree n
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 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 -> t) -> t -> PathTree n -> [Direction] -> t
subTree PathTree n -> t
f t
z PathTree n
Tip [Direction]
_ = t
z
subTree PathTree n -> t
f t
z (Dynamic DynTree (PathTree n)
dt) [Direction]
p = forall {t} {p}.
(t -> [Direction] -> p) -> p -> DynTree t -> [Direction] -> p
dynSelect ((PathTree n -> t) -> t -> PathTree n -> [Direction] -> t
subTree PathTree n -> t
f t
z) t
z DynTree (PathTree n)
dt [Direction]
p
subTree PathTree n -> t
f t
z PathTree n
n [] = PathTree n -> t
f PathTree n
n
subTree PathTree n -> t
f t
z (Node n
_ PathTree n
l PathTree n
_) (Direction
L : [Direction]
path') = (PathTree n -> t) -> t -> PathTree n -> [Direction] -> t
subTree PathTree n -> t
f t
z PathTree n
l [Direction]
path'
subTree PathTree n -> t
f t
z (Node n
_ PathTree n
_ PathTree n
r) (Direction
R : [Direction]
path') = (PathTree n -> t) -> t -> PathTree n -> [Direction] -> t
subTree PathTree n -> t
f t
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 -> t
_ t
z PathTree n
t [Direction]
p = forall {a1} {a2}. Show a1 => String -> a1 -> a2 -> a2
ctrace String
"subTree" (String
"subTree _ _ "forall a. [a] -> [a] -> [a]
++forall a. Show a => a -> String
show PathTree n
tforall a. [a] -> [a] -> [a]
++String
" "forall a. [a] -> [a] -> [a]
++forall a. Show a => a -> String
show [Direction]
p) t
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) = 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 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 forall a. Integral a => a -> a -> a
`rem` t
2 forall a. Eq a => a -> a -> Bool
== t
0 then DynTree t
l else DynTree t
r) (t
n forall a. Integral a => a -> a -> a
`quot` t
2)
dynSelect t -> [Direction] -> p
f p
z DynTree t
dn [Direction]
_ = p
z

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

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

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

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

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

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

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

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

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

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

unpos :: Int->Int
unpos :: Int -> Int
unpos Int
n =
  if forall a. Integral a => a -> Bool
even Int
n
  then -(Int
n forall a. Integral a => a -> a -> a
`quot` Int
2)
  else Int
n 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 -> 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 -> forall n. DynTree (PathTree n) -> PathTree n
Dynamic (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 -> 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 -> 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 -> forall n. DynTree n
DynTip

attrMapPathTree :: (i -> [s] -> a -> (i,s,b)) -> i -> PathTree a -> 
		   ([s],PathTree b)
attrMapPathTree :: 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
t = case PathTree a
t of
   Node a
n PathTree a
lt PathTree a
rt -> ([s
s],forall n. n -> PathTree n -> PathTree n -> PathTree n
Node b
n' PathTree b
lt' PathTree b
rt') where
      ([s]
sl,PathTree b
lt') = 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') = 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]
slforall a. [a] -> [a] -> [a]
++[s]
sr) a
n
      -- should perhaps extract ++ and []
   PathTree a
Tip -> ([],forall n. PathTree n
Tip)
   Dynamic DynTree (PathTree a)
dt -> forall {t} {b} {a}. (t -> b) -> (a, t) -> (a, b)
apSnd forall n. DynTree (PathTree n) -> PathTree n
Dynamic (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 -> ([],forall n. DynTree n
DynTip)
   DynNode PathTree a
t DynTree (PathTree a)
lt DynTree (PathTree a)
rt -> ([a]
sforall a. [a] -> [a] -> [a]
++[a]
slforall a. [a] -> [a] -> [a]
++[a]
sr,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') = 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 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 -> 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 -> (forall a. a -> Maybe a
Just n
i,forall {n}. PathTree n -> [PathTree n] -> [PathTree n]
children PathTree n
lt (forall {n}. PathTree n -> [PathTree n] -> [PathTree n]
children PathTree n
rt []))
    PathTree n
Tip -> (forall a. Maybe a
Nothing,[])
    Dynamic DynTree (PathTree n)
dt -> (forall a. Maybe a
Nothing,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
tforall 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. DynTree (PathTree n) -> [PathTree n] -> [PathTree n]
dynChildren DynTree (PathTree n)
lt 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??