Skip to content

Instantly share code, notes, and snippets.

(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
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)
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}
insertNode contextNode ExactMatchDatum{} = switchToWord contextNode
-- 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) }
-- 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}
-- this will be the complicated case
insertNode contextNode@TrieNode{children=childNodes,nodeType=oldNodeType}
SharedPrefixDatum { shared = sharedPrefix ,
suffixS = sourceSuffix@(s:ss),
suffixT = targetSuffix@(t:ts)}
= newForkNode {children = ourTwoNewNodes }
where newForkNode = nonWordNode sharedPrefix
ourTwoNewNodes = Map.fromList [(s,newSourceSuffixNode),(t,newTargetSuffixNode) ]
newSourceSuffixNode = wordNode sourceSuffix
newTargetSuffixNode = contextNode{ wordFragment = targetSuffix}
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))
import math
def vpcnum(n):
Y,X = math.modf( (n-1)/float(16) )
x = "10.{0}.{1}.0".format(int(X),int(Y*256))
return x
def client(n):
clientNum = (n*2 + 16)
return (vpcnum(clientNum-1),vpcnum(clientNum))

Keybase proof

I hereby claim:

  • I am reverendpaco on github.
  • I am reverend_paco (https://keybase.io/reverend_paco) on keybase.
  • I have a public key ASB5p5DKzM53ePcNbBUtjDq-xieXECxljY75e_Dy_z6OTQo

To claim this, I am signing this object: