reverendpaco

-- the following is for trie nodes where the source is smaller
insertNode contextNode@TrieNode{children=childNodes,nodeType=oldNodeType} 
           SourceIsSmallerDatum {pre=source,
                                 suffixT= suffixStringOfTarget}
    = contextNode{ wordFragment = source,
                   nodeType = Word,
                   children= slidNode *-> childNodes   }
      where slidNode = contextNode{wordFragment=suffixStringOfTarget,nodeType=oldNodeType}

reverendpaco

-- the following is guaranteed not to have something at the child node as we
-- checked it above 
insertNode contextNode@TrieNode{children=childNodes} 
           TargetIsSmallerDatum {pre=target,
                                 suffixS= suffixStringOfSource} 
    = contextNode{ children=(insertNewChildWordNode suffixStringOfSource childNodes) }

reverendpaco

insertNode contextNode ExactMatchDatum{} = switchToWord contextNode

reverendpaco

data PrefixSuffixTree a = ExactMatchDatum { shared :: a } |
                          SharedPrefixDatum { shared :: a, suffixT :: a, suffixS :: a } |
                          TargetIsSmallerDatum { pre :: a, suffixS :: a } |
                          SourceIsSmallerDatum { pre :: a, suffixT :: a } |
                          NoMatchDatum deriving (Show,Eq)
data MatchType = TargetIsPrefix | SourceIsPrefix | 
                 SharedPrefix | ExactMatch | NotEqual deriving (Show)

-- utility functions
switchToWord node = node{nodeType = Word} 

reverendpaco

data NodeType = Top|Word|NonWord 
                deriving (Show,Eq)
data TrieNode a = TrieNode { wordFragment :: [a], children :: (Map.Map a (TrieNode a)), 
                            nodeType:: NodeType }  deriving (Show,Eq)

reverendpaco

(defstruct trie-node :word-fragment :type :children)

(defn type-switch [node type-val]
  (assoc node :type type-val))
(defn switch-to-word [node]
  (type-switch node :word))
(defn switch-to-nonword [node]
  (type-switch node :nonword))

; constructors