--------------------------------------------------
-- 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