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:
(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)) |
I hereby claim:
To claim this, I am signing this object: