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 

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

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

insertNode contextNode ExactMatchDatum{} = switchToWord contextNode

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

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

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

reverendpaco

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

reverendpaco

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

reverendpaco

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: