pred-trie 0.1 → 0.2.0

raw patch · 5 files changed

+43/−6 lines, 5 files

Files

• pred-trie.cabal +3/−2
• src/Data/Trie/Pred/Disjoint.hs +6/−2
• src/Data/Trie/Pred/Disjoint/Tail.hs +14/−0
• src/Data/Trie/Pred/Unified.hs +6/−1
• src/Data/Trie/Pred/Unified/Tail.hs +14/−1

@@ -1,11 +1,12 @@ Name:                   pred-trie-Version:                0.1+Version:                0.2.0 Author:                 Athan Clark <athan.clark@gmail.com> Maintainer:             Athan Clark <athan.clark@gmail.com> License:                BSD3 License-File:           LICENSE+Category:               Data Synopsis:               Predicative tries--- Description:            +-- Description: Cabal-Version:          >= 1.10 Build-Type:             Simple 

@@ -2,6 +2,7 @@   ( RDPTrie (..)   , merge   , lookup+  , lookupWithL   , lookupNearestParent   , litSingleton   , litExtrude@@ -9,7 +10,7 @@   ) where  import Prelude hiding (lookup)-import Data.Trie.Pred.Disjoint.Tail hiding (lookup, lookupNearestParent, merge)+import Data.Trie.Pred.Disjoint.Tail hiding (lookup, lookupWithL, lookupNearestParent, merge) import qualified Data.Trie.Pred.Disjoint.Tail as ND import Data.Monoid import qualified Data.List.NonEmpty as NE@@ -35,6 +36,10 @@ lookup [] (Rooted mx _) = mx lookup ts (Rooted _ xs) = firstJust $ map (ND.lookup $ NE.fromList ts) xs +lookupWithL :: (Eq t) => (t -> t) -> [t] -> RDPTrie p t x -> Maybe x+lookupWithL _ [] (Rooted mx _) = mx+lookupWithL f ts (Rooted _ xs) = firstJust $ map (ND.lookupWithL f $ NE.fromList ts) xs+ lookupNearestParent :: (Eq t) => [t] -> RDPTrie p t x -> Maybe x lookupNearestParent [] (Rooted mx _) = mx lookupNearestParent ts (Rooted mx xs) =@@ -57,4 +62,3 @@ litExtrude ts (Rooted mx xs) = Rooted Nothing [ND.litExtrudeTail (init ts) $                                                  DMore (last ts) mx xs                                               ]-

@@ -5,6 +5,7 @@ module Data.Trie.Pred.Disjoint.Tail   ( DPTrie (..)   , lookup+  , lookupWithL   , lookupNearestParent   , merge   , areDisjoint@@ -66,6 +67,19 @@       [] -> ($ r) <$> mrx       _  -> ($ r) <$> firstJust (map (lookup $ NE.fromList ts) xrs) +lookupWithL :: Eq t => (t -> t) -> NonEmpty t -> DPTrie p t x -> Maybe x+lookupWithL f (t:|ts) (DMore t' mx xs)+  | null ts = if f t == t'+              then mx+              else Nothing+  | otherwise = if t == t'+                then firstJust $ map (lookupWithL f $ NE.fromList ts) xs+                else Nothing+lookupWithL f (t:|ts) (DPred _ p mrx xrs) =+  p t >>=+    \r -> case ts of+      [] -> ($ r) <$> mrx+      _  -> ($ r) <$> firstJust (map (lookupWithL f $ NE.fromList ts) xrs)  lookupNearestParent :: Eq t => NonEmpty t -> DPTrie p t x -> Maybe x lookupNearestParent tss@(t:|ts) trie@(DMore t' mx xs) = case lookup tss trie of

@@ -4,6 +4,7 @@   , showTrie   , merge   , lookup+  , lookupWithL   , lookupNearestParent   , litSingleton   , litExtrude@@ -11,7 +12,7 @@   ) where  import Prelude hiding (lookup)-import Data.Trie.Pred.Unified.Tail hiding (lookup, lookupNearestParent, merge, assignLit)+import Data.Trie.Pred.Unified.Tail hiding (lookup, lookupWithL, lookupNearestParent, merge, assignLit) import qualified Data.Trie.Pred.Unified.Tail as NU import Data.Monoid import Data.Maybe (fromMaybe)@@ -50,6 +51,10 @@ lookup :: (Eq t) => [t] -> RUPTrie t x -> Maybe x lookup [] (Rooted mx _) = mx lookup ts (Rooted _ xs) = firstJust $ map (NU.lookup $ NE.fromList ts) xs++lookupWithL :: (Eq t) => (t -> t) -> [t] -> RUPTrie t x -> Maybe x+lookupWithL _ [] (Rooted mx _) = mx+lookupWithL f ts (Rooted _ xs) = firstJust $ map (NU.lookupWithL f $ NE.fromList ts) xs  lookupNearestParent :: (Eq t) => [t] -> RUPTrie t x -> Maybe x lookupNearestParent [] (Rooted mx _) = mx

@@ -7,6 +7,7 @@   , showTail   , assignLit   , lookup+  , lookupWithL   , lookupNearestParent   , merge   , areDisjoint@@ -84,6 +85,19 @@       [] -> ($ r) <$> mrx       _  -> ($ r) <$> firstJust (map (lookup $ NE.fromList ts) xrs) +lookupWithL :: Eq t => (t -> t) -> NonEmpty t -> UPTrie t x -> Maybe x+lookupWithL f (t:|ts) (UMore t' mx xs)+  | null ts = if f t == t'+              then mx+              else Nothing+  | otherwise = if t == t'+                then firstJust $ map (lookupWithL f $ NE.fromList ts) xs+                else Nothing+lookupWithL f (t:|ts) (UPred _ p mrx xrs) =+  p t >>=+    \r -> case ts of+      [] -> ($ r) <$> mrx+      _  -> ($ r) <$> firstJust (map (lookupWithL f $ NE.fromList ts) xrs)  lookupNearestParent :: Eq t => NonEmpty t -> UPTrie t x -> Maybe x lookupNearestParent tss@(t:|ts) trie@(UMore t' mx xs) = case lookup tss trie of@@ -140,4 +154,3 @@     insert x@(UPred t _ _ _) (y@(UMore p _ _):rs)       | t == p = insert x rs       | otherwise = y : insert x rs-