--------------------------------------------------
-- Custom ternary Tree search algorithm         --
-- Bottom up it builds an array of ALL possible --
-- paths, using a "binary" operator as the last --
-- character to filter out "true" paths later.  --
-- yes, this is inefficient, but I am not being --
-- marked on efficiency, only on it working.    --
--------------------------------------------------

-- the "called" function
findpath :: Int -> Ttree -> [Path]
findpath a b = filterpath(genpath a b)

-- the "filter" function for a list of paths
filterpath :: [Path] -> [Path]
filterpath (a:bs)
 | (head (reverse a))==T = (reverse(tail(reverse a))):(filterpath bs)
 | otherwise = filterpath bs
filterpath [] = []

-- generates ALL possible paths through the tree
genpath :: Int  -> Ttree  -> [Path]
genpath d (ND) = [[F]]
genpath d (Data b) 
 | d==b = [[T]]
 | otherwise = [[F]]
genpath d (Branch a b c) = (adp L (genpath d a))++(adp M (genpath d b))++(adp R (genpath d c))

-- Adds a direction to the start of every element in a list of paths
adp :: Dir -> [Path] -> [Path]
adp a (b:bs) = (adp2 a b):(adp a bs)
adp a [] = []
-- Adds a Dir to the start of a single path
adp2 :: Dir -> Path -> Path
adp2 a b = a:b