Skip to content

Instantly share code, notes, and snippets.

@reverendpaco
Created July 26, 2010 22:42
Show Gist options
  • Save reverendpaco/491376 to your computer and use it in GitHub Desktop.
Save reverendpaco/491376 to your computer and use it in GitHub Desktop.
queryNode source node = bool
where (bool,_) = queryNodeWithPath source node []
queryNodeWithPath :: (Ord a) => [a] -> TrieNode a -> [[a]] -> (Bool,[[a]])
queryNodeWithPath source@(s:_) node@TrieNode{ nodeType = Top, children=ch} acc
| Map.member s ch = queryNodeWithPath source (ch ! s) acc
| otherwise = (False,acc)
queryNodeWithPath source node@TrieNode{ wordFragment = target, nodeType=nT, children=ch } acc = case matchData of
ExactMatchDatum {shared=source}
| nT == Word -> (True, (target:acc))
| otherwise -> (False,acc)
TargetIsSmallerDatum {suffixS= suffixStringOfSource@(s:_)}
| Map.member s ch -> queryNodeWithPath suffixStringOfSource (ch ! s) (target:acc )
| otherwise -> (False,acc)
otherwise -> (False,acc)
where matchData = source =><= target
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment