radix-tree 1.0.0.2 → 1.1.0.0

raw patch · 22 files changed

+676/−410 lines, 22 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +10/−1
• radix-tree.cabal +6/−2
• src/Data/Patricia/Word/Lazy/Internal.hs +6/−6
• src/Data/Patricia/Word/Strict/Internal.hs +6/−6
• src/Data/Radix1Tree/Word8/Lazy.hs +0/−27
• src/Data/Radix1Tree/Word8/Lazy/Unsafe.hs +17/−17
• src/Data/Radix1Tree/Word8/Lazy/Zipper.hs +118/−0
• src/Data/Radix1Tree/Word8/Strict.hs +0/−27
• src/Data/Radix1Tree/Word8/Strict/Pointer.hs +38/−0
• src/Data/Radix1Tree/Word8/Strict/Unsafe.hs +17/−17
• src/Data/Radix1Tree/Word8/Strict/Zipper.hs +118/−0
• src/Data/RadixNTree/Word8/Key.hs +9/−4
• src/Data/RadixNTree/Word8/Lazy.hs +0/−106
• src/Data/RadixNTree/Word8/Strict.hs +0/−106
• src/Data/RadixNTree/Word8/Strict/Pointer.hs +159/−0
• src/Data/RadixTree/Word8/Lazy.hs +0/−27
• src/Data/RadixTree/Word8/Strict.hs +1/−28
• src/Data/RadixTree/Word8/Strict/Pointer.hs +38/−0
• src/Data/RadixTree/Word8/Strict/Unsafe.hs +2/−2
• src/Radix/Word8/Common.hs +0/−10
• test/properties/Test/RadixTree/Word8/Lazy.hs +61/−12
• test/properties/Test/RadixTree/Word8/Strict.hs +70/−12

@@ -1,4 +1,13 @@-## 1.0.0.0 -- September 2024+## 1.1.0.0 -- October 2024++* Added `Zipper` modules for non-empty radix trees;++* Removed `Cursor`s from radix tree modules.+  Their functionality is subsumed by the appropriate `Zipper` modules.++* Added `Pointer` modules for strict radix trees;++## 1.0.0.2 -- September 2024  * Fixed `Data.Zebra.Word.fillRange`.   Previously it produced malformed trees in certain cases.

@@ -1,5 +1,5 @@ name:          radix-tree-version:       1.0.0.2+version:       1.1.0.0  category:      Data Structures synopsis:      Radix trees@@ -45,6 +45,7 @@                     Data.RadixTree.Word8.Lazy.Unsafe                     Data.RadixTree.Word8.Strict                     Data.RadixTree.Word8.Strict.Debug+                    Data.RadixTree.Word8.Strict.Pointer                     Data.RadixTree.Word8.Strict.TH                     Data.RadixTree.Word8.Strict.Unsafe @@ -54,10 +55,13 @@                     Data.Radix1Tree.Word8.Lazy.Debug                     Data.Radix1Tree.Word8.Lazy.TH                     Data.Radix1Tree.Word8.Lazy.Unsafe+                    Data.Radix1Tree.Word8.Lazy.Zipper                     Data.Radix1Tree.Word8.Strict                     Data.Radix1Tree.Word8.Strict.Debug+                    Data.Radix1Tree.Word8.Strict.Pointer                     Data.Radix1Tree.Word8.Strict.TH                     Data.Radix1Tree.Word8.Strict.Unsafe+                    Data.Radix1Tree.Word8.Strict.Zipper                      Data.Zebra.Word                     Data.Zebra.Word.Debug@@ -80,6 +84,7 @@                     Data.RadixNTree.Word8.Lazy.TH                     Data.RadixNTree.Word8.Strict                     Data.RadixNTree.Word8.Strict.Debug+                    Data.RadixNTree.Word8.Strict.Pointer                     Data.RadixNTree.Word8.Strict.TH                      Data.Zebra.Word.Internal@@ -88,7 +93,6 @@                      Radix.Common                     Radix.Exception-                    Radix.Word8.Common                     Radix.Word8.Debug                     Radix.Word8.Foundation                     Radix.Word.Common

@@ -2348,7 +2348,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMin :: Patricia a -> (# a #) unsafeLookupMin t =   case t of@@ -2366,7 +2366,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMinWithKey :: Patricia a -> Lookup a unsafeLookupMinWithKey t =   case t of@@ -2386,7 +2386,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMax :: Patricia a -> (# a #) unsafeLookupMax t =   case t of@@ -2404,7 +2404,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMaxWithKey :: Patricia a -> Lookup a unsafeLookupMaxWithKey t =   case t of@@ -2543,7 +2543,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up the leftmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMinView :: Patricia a -> ViewL a unsafeMinView t =   case t of@@ -2570,7 +2570,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up the rightmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMaxView :: Patricia a -> ViewR a unsafeMaxView t =   case t of

@@ -2755,7 +2755,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMin :: Patricia a -> (# a #) unsafeLookupMin t =   case t of@@ -2773,7 +2773,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMinWithKey :: Patricia a -> Lookup a unsafeLookupMinWithKey t =   case t of@@ -2793,7 +2793,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMax :: Patricia a -> (# a #) unsafeLookupMax t =   case t of@@ -2811,7 +2811,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMaxWithKey :: Patricia a -> Lookup a unsafeLookupMaxWithKey t =   case t of@@ -3011,7 +3011,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up the leftmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMinView :: Patricia a -> ViewL a unsafeMinView t =   case t of@@ -3038,7 +3038,7 @@ -- | \(\mathcal{O}(\min(n,W))\). --   Look up the rightmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMaxView :: Patricia a -> ViewR a unsafeMaxView t =   case t of

@@ -69,21 +69,6 @@   , Data.Radix1Tree.Word8.Lazy.member   , subtree -    -- *** Chunked-    ---    -- | Chunked lookup allows providing the key piece by piece while retaining-    --   the ability to check for early failure.-    ---    --   Note that while 'subtree' can be used to achieve the same result,-    --   it is more expensive allocation-wise, as it must ensure that-    --   the resulting tree is well-formed after each chunk application.-  , Cursor-  , cursor-  , move-  , stop-  , Location (..)-  , locate-     -- ** Insert   , insert   , insertWith@@ -455,18 +440,6 @@ --   Prefix the root of the tree with the given key. prefix :: Feed1 -> RadixTree a -> Radix1Tree a prefix = prefix1----- | \(\mathcal{O}(1)\).---   Make a cursor that points to the root of the tree.-cursor :: Radix1Tree a -> Cursor a-cursor = cursor1--{-# INLINE move #-}--- | \(\mathcal{O}(\min(x,k))\).---   Move the cursor down by the extent of the given key.-move :: Feed1 -> Cursor a -> Cursor a-move = move1   

@@ -79,63 +79,63 @@ import           Data.RadixNTree.Word8.Common import           Data.RadixNTree.Word8.Lazy import           Radix.Exception-import           Radix.Word.Foundation+import           Radix.Word8.Foundation    -- | \(\mathcal{O}(k)\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMin :: Radix1Tree a -> (# a #) unsafeLookupMin = unsafeLookupMin1  -- | \(\mathcal{O}(k)\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMinWithKey :: Radix1Tree a -> Lookup1 a unsafeLookupMinWithKey = unsafeLookupMinWithKey1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Delete a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeDeleteMin :: Radix1Tree a -> Radix1Tree a unsafeDeleteMin = unsafeDeleteMin1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMin :: (a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMin = unsafeAdjustMin1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMinWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMinWithKey = unsafeAdjustMinWithKey1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update or delete a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeUpdateMin :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a unsafeUpdateMin = unsafeUpdateMin1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update or delete a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeUpdateMinWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a unsafeUpdateMinWithKey = unsafeUpdateMinWithKey1  -- | \(\mathcal{O}(\min(x,k))\). --   Look up the leftmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMinView :: Radix1Tree a -> ViewL1 a unsafeMinView = unsafeMinView1 @@ -144,56 +144,56 @@ -- | \(\mathcal{O}(k)\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMax :: Radix1Tree a -> (# a #) unsafeLookupMax = unsafeLookupMax1  -- | \(\mathcal{O}(k)\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMaxWithKey :: Radix1Tree a -> Lookup1 a unsafeLookupMaxWithKey = unsafeLookupMaxWithKey1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Delete a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeDeleteMax :: Radix1Tree a -> Radix1Tree a unsafeDeleteMax = unsafeDeleteMax1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMax :: (a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMax = unsafeAdjustMax1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMaxWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMaxWithKey = unsafeAdjustMaxWithKey1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update or delete a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeUpdateMax :: (a -> Maybe a) -> Radix1Tree a -> Radix1Tree a unsafeUpdateMax = unsafeUpdateMax1  -- | \(\mathcal{O}(1)\texttt{+}, \mathcal{O}(k)\). --   Update or delete a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeUpdateMaxWithKey :: (Build1 -> a -> Maybe a) -> Radix1Tree a -> Radix1Tree a unsafeUpdateMaxWithKey = unsafeUpdateMaxWithKey1  -- | \(\mathcal{O}(\min(x,k))\). --   Look up the rightmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMaxView :: Radix1Tree a -> ViewR1 a unsafeMaxView = unsafeMaxView1 

@@ -0,0 +1,118 @@+{-# LANGUAGE BangPatterns #-}++{-| Spine-lazy radix tree location manipulation.++    Allows lookup and successive insertion without retaining the entirety+    of the key in memory.+ -}++module Data.Radix1Tree.Word8.Lazy.Zipper+  ( Context1+  , descend+  , focus+  ) where++import           Data.ByteArray.NonEmpty+import           Data.RadixNTree.Word8.Key+import           Data.RadixNTree.Word8.Lazy+import           Radix.Word8.Foundation++import           Data.Primitive.ByteArray++++data Past a = Leftward+                !(Past a)+                {-# UNPACK #-} !Prefix+                (Radix1Tree a)++            | Rightward+                !(Past a)+                {-# UNPACK #-} !Prefix+                (Radix1Tree a)++            | Downward+                !(Past a)+                {-# UNPACK #-} !ByteArray+                {-# UNPACK #-} !(Maybe a)++            | Top+++-- | A location inside the radix tree.+data Context1 a = -- | Corresponds to a 'Tip'.+                  Context1+                    !(Past a)+                    {-# UNPACK #-} !Int       -- ^ Next index in the byte array.+                    {-# UNPACK #-} !ByteArray+                    {-# UNPACK #-} !(Maybe a)+                    !(Radix1Tree a)++++{-# INLINE descend #-}+-- | \(\mathcal{O}(\min(x,k))\).+--   Move down the tree by the extent of the given key.+--   Returns 'Nothing' if the resulting position is outside of the tree.+--+--   @since 1.1+descend :: Feed1 -> Either (Radix1Tree a) (Context1 a) -> Maybe (Context1 a)+descend (Feed1 w0 feed) =+  feed $ \step ->++    let go !past !w !s t =+          case t of+            Bin p l r ->+              if w < p+                then go (Leftward  past p r) w s l+                else go (Rightward past p l) w s r++            Tip arr mx dx -> goarr past arr mx dx w s 0++            Nil -> Nothing++        goarr !past !arr !mx dx = goarr_+          where+            goarr_ v !z n+              | v == indexByteArray arr n =+                  let n' = n + 1+                  in case step z of+                       More u z' -> if n' >= sizeofByteArray arr+                                      then go (Downward past arr mx) u z' dx+                                      else goarr_ u z' n'++                       Done      -> Just $! Context1 past n' arr mx dx++              | otherwise = Nothing++    in \s0 ei ->+         case ei of+           Left r                           -> go Top w0 s0 r+           Right (Context1 past n arr mx dx) ->+             if n == sizeofByteArray arr+               then go (Downward past arr mx) w0 s0 dx+               else goarr past arr mx dx w0 s0 n++++-- | \(\mathcal{O}(1)\).+--   Retrieve the value at the current position, if any exists,+--   together with the insertion function for the current position.+--+--   @since 1.1+focus :: Context1 a -> Maybe (a, a -> Radix1Tree a)+focus (Context1 past n arr mx dx)+  | n == sizeofByteArray arr, Just x <- mx =+      Just $! (x, \y -> rebuild (Tip arr (Just y) dx) past)++  | otherwise = Nothing++++rebuild :: Radix1Tree a -> Past a -> Radix1Tree a+rebuild !x past =+  case past of+    Leftward  past' p r   -> rebuild (Bin p x r) past'+    Rightward past' p l   -> rebuild (Bin p l x) past'+    Downward past' brr my -> rebuild (Tip brr my x) past'+    Top                   -> x

@@ -68,21 +68,6 @@   , Data.Radix1Tree.Word8.Strict.member   , subtree -    -- *** Chunked-    ---    -- | Chunked lookup allows providing the key piece by piece while retaining-    --   the ability to check for early failure.-    ---    --   Note that while 'subtree' can be used to achieve the same result,-    --   it is more expensive allocation-wise, as it must ensure that-    --   the resulting tree is well-formed after each chunk application.-  , Cursor-  , cursor-  , move-  , stop-  , Location (..)-  , locate-     -- ** Insert   , insert   , insertWith@@ -488,18 +473,6 @@ --   Prefix the root of the tree with the given key. prefix :: Feed1 -> RadixTree a -> Radix1Tree a prefix = prefix1----- | \(\mathcal{O}(1)\).---   Make a cursor that points to the root of the tree.-cursor :: Radix1Tree a -> Cursor a-cursor = cursor1--{-# INLINE move #-}--- | \(\mathcal{O}(\min(x,k))\).---   Move the cursor down by the extent of the given key.-move :: Feed1 -> Cursor a -> Cursor a-move = move1   

@@ -0,0 +1,38 @@+{-| Compressed references for spine-strict radix trees.++    Pointers have a much smaller memory footprint and+    allow faster lookup in trees that are known to never change shape.+ -}++module Data.Radix1Tree.Word8.Strict.Pointer+  ( Pointer+  , pointer+  , follow+  ) where++import           Data.RadixNTree.Word8.Key (Feed1)+import           Data.RadixNTree.Word8.Strict (Radix1Tree)+import           Data.RadixNTree.Word8.Strict.Pointer++++{-# INLINE pointer #-}+-- | \(\mathcal{O}(\min(x,k))\).+--   Create a pointer that mirrors an existing key.+--+--   The pointer is only guaranteed to behave correctly for any tree that holds the+--   same set of keys as the provided one.+--+--   @since 1.1+pointer :: Feed1 -> Radix1Tree a -> Maybe Pointer+pointer = pointer1++++-- | \(\mathcal{O}(\log n)\).+--   Look up the value at a pointer in the tree, falling back to the given default value+--   if it does not exist.+--+--   @since 1.1+follow :: a -> Pointer -> Radix1Tree a -> a+follow = follow1

@@ -83,42 +83,42 @@ import           Data.RadixNTree.Word8.Common import           Data.RadixNTree.Word8.Strict import           Radix.Exception-import           Radix.Word.Foundation+import           Radix.Word8.Foundation    -- | \(\mathcal{O}(k)\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMin :: Radix1Tree a -> (# a #) unsafeLookupMin = unsafeLookupMin1  -- | \(\mathcal{O}(k)\). --   Look up a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMinWithKey :: Radix1Tree a -> Lookup1 a unsafeLookupMinWithKey = unsafeLookupMinWithKey1  -- | \(\mathcal{O}(k)\). --   Delete a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeDeleteMin :: Radix1Tree a -> Radix1Tree a unsafeDeleteMin = unsafeDeleteMin1  -- | \(\mathcal{O}(k)\). --   Update a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMin :: (a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMin = unsafeAdjustMin1  -- | \(\mathcal{O}(k)\). --   Update a value at the leftmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMinWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMinWithKey = unsafeAdjustMinWithKey1 @@ -127,7 +127,7 @@ -- --   New value is evaluated to WHNF. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMin' :: (a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMin' = unsafeAdjustMin1' @@ -136,7 +136,7 @@ -- --   New value is evaluated to WHNF. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMinWithKey' :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMinWithKey' = unsafeAdjustMinWithKey1' @@ -153,7 +153,7 @@ -- | \(\mathcal{O}(\min(x,k))\). --   Look up the leftmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMinView :: Radix1Tree a -> ViewL1 a unsafeMinView = unsafeMinView1 @@ -162,35 +162,35 @@ -- | \(\mathcal{O}(k)\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMax :: Radix1Tree a -> (# a #) unsafeLookupMax = unsafeLookupMax1  -- | \(\mathcal{O}(k)\). --   Look up a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeLookupMaxWithKey :: Radix1Tree a -> Lookup1 a unsafeLookupMaxWithKey = unsafeLookupMaxWithKey1  -- | \(\mathcal{O}(k)\). --   Delete a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeDeleteMax :: Radix1Tree a -> Radix1Tree a unsafeDeleteMax = unsafeDeleteMax1  -- | \(\mathcal{O}(k)\). --   Update a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMax :: (a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMax = unsafeAdjustMax1  -- | \(\mathcal{O}(k)\). --   Update a value at the rightmost key in the tree. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMaxWithKey :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMaxWithKey = unsafeAdjustMaxWithKey1 @@ -199,7 +199,7 @@ -- --   New value is evaluated to WHNF. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMax' :: (a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMax' = unsafeAdjustMax1' @@ -208,7 +208,7 @@ -- --   New value is evaluated to WHNF. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeAdjustMaxWithKey' :: (Build1 -> a -> a) -> Radix1Tree a -> Radix1Tree a unsafeAdjustMaxWithKey' = unsafeAdjustMaxWithKey1' @@ -225,7 +225,7 @@ -- | \(\mathcal{O}(\min(x,k))\). --   Look up the rightmost value and return it alongside the tree without it. -----   Throws 'MalformedTree' if the tree is empty.+--   Throws t'MalformedTree' if the tree is empty. unsafeMaxView :: Radix1Tree a -> ViewR1 a unsafeMaxView = unsafeMaxView1 

@@ -0,0 +1,118 @@+{-# LANGUAGE BangPatterns #-}++{-| Spine-strict radix tree location manipulation.++    Allows lookup and successive insertion without retaining the entirety+    of the key in memory.+ -}++module Data.Radix1Tree.Word8.Strict.Zipper+  ( Context1+  , descend+  , focus+  ) where++import           Data.ByteArray.NonEmpty+import           Data.RadixNTree.Word8.Key+import           Data.RadixNTree.Word8.Strict+import           Radix.Word8.Foundation++import           Data.Primitive.ByteArray++++data Past a = Leftward+                !(Past a)+                {-# UNPACK #-} !Prefix+                !(Radix1Tree a)++            | Rightward+                !(Past a)+                {-# UNPACK #-} !Prefix+                !(Radix1Tree a)++            | Downward+                !(Past a)+                {-# UNPACK #-} !ByteArray+                {-# UNPACK #-} !(Maybe a)++            | Top+++-- | A location inside the radix tree.+data Context1 a = -- | Corresponds to a 'Tip'.+                  Context1+                    !(Past a)+                    {-# UNPACK #-} !Int       -- ^ Next index in the byte array.+                    {-# UNPACK #-} !ByteArray+                    {-# UNPACK #-} !(Maybe a)+                    !(Radix1Tree a)++++{-# INLINE descend #-}+-- | \(\mathcal{O}(\min(x,k))\).+--   Move down the tree by the extent of the given key.+--   Returns 'Nothing' if the resulting position is outside of the tree.+--+--   @since 1.1+descend :: Feed1 -> Either (Radix1Tree a) (Context1 a) -> Maybe (Context1 a)+descend (Feed1 w0 feed) =+  feed $ \step ->++    let go !past !w !s t =+          case t of+            Bin p l r ->+              if w < p+                then go (Leftward  past p r) w s l+                else go (Rightward past p l) w s r++            Tip arr mx dx -> goarr past arr mx dx w s 0++            Nil -> Nothing++        goarr !past !arr !mx dx = goarr_+          where+            goarr_ v !z n+              | v == indexByteArray arr n =+                  let n' = n + 1+                  in case step z of+                       More u z' -> if n' >= sizeofByteArray arr+                                      then go (Downward past arr mx) u z' dx+                                      else goarr_ u z' n'++                       Done      -> Just $! Context1 past n' arr mx dx++              | otherwise = Nothing++    in \s0 ei ->+         case ei of+           Left r                           -> go Top w0 s0 r+           Right (Context1 past n arr mx dx) ->+             if n == sizeofByteArray arr+               then go (Downward past arr mx) w0 s0 dx+               else goarr past arr mx dx w0 s0 n++++-- | \(\mathcal{O}(1)\).+--   Retrieve the value at the current position, if any exists,+--   together with the insertion function for the current position.+--+--   @since 1.1+focus :: Context1 a -> Maybe (a, a -> Radix1Tree a)+focus (Context1 past n arr mx dx)+  | n == sizeofByteArray arr, Just x <- mx =+      Just $! (x, \y -> rebuild (Tip arr (Just y) dx) past)++  | otherwise = Nothing++++rebuild :: Radix1Tree a -> Past a -> Radix1Tree a+rebuild !x past =+  case past of+    Leftward  past' p r   -> rebuild (Bin p x r) past'+    Rightward past' p l   -> rebuild (Bin p l x) past'+    Downward past' brr my -> rebuild (Tip brr my x) past'+    Top                   -> x

@@ -320,9 +320,11 @@   -data CarryBS = CarryBS Int Strict.ByteString Lazy.ByteString+data CarryBS = CarryBS+                 {-# UNPACK #-} !Int+                 !Strict.ByteString+                 !Lazy.ByteString -{-# INLINE stepLazyByteString #-} stepLazyByteString :: CarryBS -> Step Word8 CarryBS stepLazyByteString (CarryBS n bs lbs) =   if n >= BS.length bs@@ -348,9 +350,12 @@   -data CarryTxt = CarryTxt Int Int ByteArray Lazy.Text+data CarryTxt = CarryTxt+                  {-# UNPACK #-} !Int+                  {-# UNPACK #-} !Int+                  !ByteArray+                  !Lazy.Text -{-# INLINE stepLazyText #-} stepLazyText :: CarryTxt -> Step Word8 CarryTxt stepLazyText (CarryTxt n len arr t) =   if n >= len

@@ -73,19 +73,6 @@   , subtree1   , prefix1 -  , Point (..)-  , Cursor (..)-  , stop--  , Location (..)-  , locate--  , cursor0-  , move0--  , cursor1-  , move1-   , lookupL0   , lookupL1 @@ -292,7 +279,6 @@ import           Data.RadixNTree.Word8.Key import           Radix.Common import           Radix.Exception-import           Radix.Word8.Common import           Radix.Word8.Foundation  import           Control.Applicative@@ -1133,98 +1119,6 @@         Nil           -> Nil      Just _  -> Tip (fromStep step w z) mx t------ | Current position in the tree.-data Point = -- | Above a node.-             Seam--             -- | In the middle of a 'Tip'.-           | Plane-               {-# UNPACK #-} !Int       -- ^ Always greater than @0@ and smaller than-                                         --   the length of the 'ByteArray'.-               {-# UNPACK #-} !ByteArray---- | A particular point in the tree.-data Cursor a = -- | This is effectively a 'Tip' where the 'ByteArray' is optional.-                Cursor-                  {-# UNPACK #-} !Point-                  {-# UNPACK #-} !(Maybe a)-                  (Radix1Tree a)--instance Show a => Show (Cursor a) where-  showsPrec d c =-    showParen (d > 10) $-      showString "Cursor " . showsPrec 11 (stop c)--cursor0 :: RadixTree a -> Cursor a-cursor0 (RadixTree mx t) = Cursor Seam mx t--cursor1 :: Radix1Tree a -> Cursor a-cursor1 = Cursor Seam Nothing--{-# INLINE move0 #-}-move0 :: Feed -> Cursor a -> Cursor a-move0 (Feed feed) = \c ->-  feed $ \step s ->-    case step s of-      More w z -> move_ step w z c-      Done     -> c--{-# INLINE move1 #-}-move1 :: Feed1 -> Cursor a -> Cursor a-move1 (Feed1 w feed) = feed $ \step -> move_ step w--{-# INLINE move_ #-}-move_ :: (x -> Step Word8 x) -> Word8 -> x -> Cursor a -> Cursor a-move_ step = \w s (Cursor point mx dx) ->-  case point of-    Seam        -> go w s dx-    Plane i arr -> goarr arr mx dx w s i-  where-    go !w !s t =-      case t of-        Bin p l r     -> go w s $ if w < p-                                    then l-                                    else r--        Tip brr my dy -> goarr brr my dy w s 0--        Nil           -> Cursor Seam Nothing Nil--    goarr arr mx dx = goarr_-      where-        goarr_ w !s n-          | w == indexByteArray arr n =-              let !n' = n + 1-              in case step s of-                   More v z-                     | n' >= sizeofByteArray arr -> go v z dx-                     | otherwise                 -> goarr_ v z n'--                   Done      ->-                     let !point'-                           | n' >= sizeofByteArray arr = Seam-                           | otherwise                 = Plane n' arr--                     in Cursor point' mx dx--          | otherwise = Cursor Seam Nothing Nil---- | \(\mathcal{O}(1)\).---   Retrieve the value at which the cursor points.-stop :: Cursor a -> Maybe a-stop (Cursor point mx _) =-  case point of-    Seam -> mx-    _    -> Nothing---- | \(\mathcal{O}(1)\).---   Determine whether the cursor points to a point within the tree.-locate :: Cursor a -> Location-locate (Cursor _ Nothing Nil) = Outside-locate _                      = Inside   

@@ -77,19 +77,6 @@   , subtree1   , prefix1 -  , Point (..)-  , Cursor (..)-  , stop--  , Location (..)-  , locate--  , cursor0-  , move0--  , cursor1-  , move1-   , lookupL0   , lookupL1 @@ -330,7 +317,6 @@ import           Data.RadixNTree.Word8.Key import           Radix.Common import           Radix.Exception-import           Radix.Word8.Common import           Radix.Word8.Foundation  import           Control.Applicative@@ -1206,98 +1192,6 @@         Nil           -> Nil      Just _  -> Tip (fromStep step w z) mx t------ | Current position in the tree.-data Point = -- | Above a node.-             Seam--             -- | In the middle of a 'Tip'.-           | Plane-               {-# UNPACK #-} !Int       -- ^ Always greater than @0@ and smaller than-                                         --   the length of the 'ByteArray'.-               {-# UNPACK #-} !ByteArray---- | A particular point in the tree.-data Cursor a = -- | This is effectively a 'Tip' where the 'ByteArray' is optional.-                Cursor-                  {-# UNPACK #-} !Point-                  {-# UNPACK #-} !(Maybe a)-                  !(Radix1Tree a)--instance Show a => Show (Cursor a) where-  showsPrec d c =-    showParen (d > 10) $-      showString "Cursor " . showsPrec 11 (stop c)--cursor0 :: RadixTree a -> Cursor a-cursor0 (RadixTree mx t) = Cursor Seam mx t--cursor1 :: Radix1Tree a -> Cursor a-cursor1 = Cursor Seam Nothing--{-# INLINE move0 #-}-move0 :: Feed -> Cursor a -> Cursor a-move0 (Feed feed) = \c ->-  feed $ \step s ->-    case step s of-      More w z -> move_ step w z c-      Done     -> c--{-# INLINE move1 #-}-move1 :: Feed1 -> Cursor a -> Cursor a-move1 (Feed1 w feed) = feed $ \step -> move_ step w--{-# INLINE move_ #-}-move_ :: (x -> Step Word8 x) -> Word8 -> x -> Cursor a -> Cursor a-move_ step = \w s (Cursor point mx dx) ->-  case point of-    Seam        -> go w s dx-    Plane i arr -> goarr arr mx dx w s i-  where-    go !w !s t =-      case t of-        Bin p l r     -> go w s $ if w < p-                                    then l-                                    else r--        Tip brr my dy -> goarr brr my dy w s 0--        Nil           -> Cursor Seam Nothing Nil--    goarr arr mx dx = goarr_-      where-        goarr_ w !s n-          | w == indexByteArray arr n =-              let !n' = n + 1-              in case step s of-                   More v z-                     | n' >= sizeofByteArray arr -> go v z dx-                     | otherwise                 -> goarr_ v z n'--                   Done      ->-                     let !point'-                           | n' >= sizeofByteArray arr = Seam-                           | otherwise                 = Plane n' arr--                     in Cursor point' mx dx--          | otherwise = Cursor Seam Nothing Nil---- | \(\mathcal{O}(1)\).---   Retrieve the value at which the cursor points.-stop :: Cursor a -> Maybe a-stop (Cursor point mx _) =-  case point of-    Seam -> mx-    _    -> Nothing---- | \(\mathcal{O}(1)\).---   Determine whether the cursor points to a point within the tree.-locate :: Cursor a -> Location-locate (Cursor _ Nothing Nil) = Outside-locate _                      = Inside   

@@ -0,0 +1,159 @@+{-# LANGUAGE BangPatterns+           , DeriveLift+           , RankNTypes+           , ScopedTypeVariables #-}++module Data.RadixNTree.Word8.Strict.Pointer+  ( Pointer (..)+  , pointer0+  , pointer1++  , follow0+  , follow1+  ) where++import           Data.ByteArray.NonEmpty+import           Data.RadixNTree.Word8.Key+import           Data.RadixNTree.Word8.Strict++import           Control.Monad.ST+import           Data.Bits+import           Data.Primitive.ByteArray+import           Data.Word+import           Language.Haskell.TH.Syntax++++-- | Pure compressed tree reference.+--+--   @since 1.1+data Pointer = Pointer+                 {-# UNPACK #-} !Word -- ^ Node depth (0 is root).+                 !ByteArray           -- ^ Little-endian bitmask of size @depth@.+                                      --   'Bin' choices are represented as 0 and 1 for+                                      --   left and right respectively;+                                      --   'Tip's can hold any data.+               deriving (Show, Lift)++++-- | Mark a bit at the given depth as @1@.+mark :: MutableByteArray s -> Word -> ST s ()+mark marr n = do+  let x = fromIntegral $ n `unsafeShiftR` 3++      y = fromIntegral $ n .&. 0x07++  i <- readByteArray marr x++  let i' = i .|. unsafeShiftL 1 y++  writeByteArray marr x (i' :: Word8)++-- | Check if the bit at the given depth is @0@.+left :: ByteArray -> Word -> Bool+left arr n =+  let x = fromIntegral $ n `unsafeShiftR` 3++      y = fromIntegral $ n .&. 0x07++  in (unsafeShiftR (indexByteArray arr x :: Word8) y) .&. 0x1 == 0++-- | Create a bitmask that can hold @depth@ bits and populate it.+form :: (forall s. MutableByteArray s -> ST s ()) -> Word -> ByteArray+form go n = do+  runST $ do+    let m = fromIntegral (n `unsafeShiftR` 3) + 1+    marr <- newByteArray m+    fillByteArray marr 0 m 0x00+    go marr+    unsafeFreezeByteArray marr++++{-# INLINE pointer0 #-}+pointer0 :: Feed -> RadixTree a -> Maybe Pointer+pointer0 (Feed feed) = \(RadixTree mx t) ->+  feed $ \step s ->+    case step s of+      More w z -> pointer_ step w z t+      Done     ->+        case mx of+          Just _  -> Just $ Pointer 0 emptyByteArray+          Nothing -> Nothing++{-# INLINE pointer1 #-}+pointer1 :: Feed1 -> Radix1Tree a -> Maybe Pointer+pointer1 (Feed1 w feed) = feed $ \step -> pointer_ step w++{-# INLINE pointer_ #-}+pointer_+  :: (x -> Step Word8 x)+  -> Word8 -> x -> Radix1Tree a -> Maybe Pointer+pointer_ (step :: x -> Step Word8 x) = go 0 (\_ -> pure ())+  where+    go :: Word -> (forall s. MutableByteArray s -> ST s ())+       -> Word8 -> x -> Radix1Tree a -> Maybe Pointer+    go !i acc !w !s t =+      case t of+        Bin p l r ->+          if w < p+            then go (i + 1)                          acc       w s l+            else go (i + 1) (\marr -> mark marr i >> acc marr) w s r++        Tip arr mx dx -> goarr w s 0+          where+            goarr v !z n+              | v == indexByteArray arr n =+                  let n' = n + 1+                  in if n' >= sizeofByteArray arr+                       then case step z of+                              More u z' -> go (i + 1) acc u z' dx+                              Done      ->+                                case mx of+                                  Just _  -> Just $ Pointer (i + 1) (form acc i)+                                  Nothing -> Nothing++                       else case step z of+                              More u z' -> goarr u z' n'+                              Done      -> Nothing++              | otherwise = Nothing++        Nil -> Nothing++++follow0 :: a -> Pointer -> RadixTree a -> a+follow0 d (Pointer len arr) (RadixTree mx dx)+  | len == 0  = case mx of+                  Just x  -> x+                  Nothing -> d++  | otherwise = follow_ d len arr dx++follow1 :: a -> Pointer -> Radix1Tree a -> a+follow1 d (Pointer len arr) = follow_ d len arr++follow_ :: a -> Word -> ByteArray -> Radix1Tree a -> a+follow_ d len arr = go 0+  where+    go !i t =+      case t of+        Bin _ l r ->+          go (i + 1) $ if left arr i+                         then l+                         else r++        Tip _ mx dx ->+          let i' = i + 1+          in if i' > len+               then d+               else if i' == len+                      then case mx of+                             Just x  -> x+                             Nothing -> d++                      else go i' dx++        Nil -> d

@@ -67,21 +67,6 @@   , Data.RadixTree.Word8.Lazy.member   , subtree -    -- *** Chunked-    ---    -- | Chunked lookup allows providing the key piece by piece while retaining-    --   the ability to check for early failure.-    ---    --   Note that while 'subtree' can be used to achieve the same result,-    --   it is more expensive allocation-wise, as it must ensure that-    --   the resulting tree is well-formed after each chunk application.-  , Cursor-  , cursor-  , move-  , stop-  , Location (..)-  , locate-     -- ** Insert   , insert   , insertWith@@ -453,18 +438,6 @@ --   Prefix the root of the tree with the given key. prefix :: Feed -> RadixTree a -> RadixTree a prefix = prefix0----- | \(\mathcal{O}(1)\).---   Make a cursor that points to the root of the tree.-cursor :: RadixTree a -> Cursor a-cursor = cursor0--{-# INLINE move #-}--- | \(\mathcal{O}(\min(x,k))\).---   Move the cursor down by the extent of the given key.-move :: Feed -> Cursor a -> Cursor a-move = move0   

@@ -66,21 +66,6 @@   , Data.RadixTree.Word8.Strict.member   , subtree -    -- *** Chunked-    ---    -- | Chunked lookup allows providing the key piece by piece while retaining-    --   the ability to check for early failure.-    ---    --   Note that while 'subtree' can be used to achieve the same result,-    --   it is more expensive allocation-wise, as it must ensure that-    --   the resulting tree is well-formed after each chunk application.-  , Cursor-  , cursor-  , move-  , stop-  , Location (..)-  , locate-     -- ** Insert   , insert   , insertWith@@ -488,19 +473,7 @@ prefix = prefix0  --- | \(\mathcal{O}(1)\).---   Make a cursor that points to the root of the tree.-cursor :: RadixTree a -> Cursor a-cursor = cursor0 -{-# INLINE move #-}--- | \(\mathcal{O}(\min(x,k))\).---   Move the cursor down by the extent of the given key.-move :: Feed -> Cursor a -> Cursor a-move = move0--- {-# INLINE insert #-} -- | \(\mathcal{O}(\min(x,k))\). --   Insert a new value in the tree at the given key.@@ -575,7 +548,7 @@ -- | \(\mathcal{O}(\min(x,k))\). --   Update the part of the tree at the given prefix. -----   The resulting 'RadixTree' is evaluated to WHNF.+--   The resulting t'RadixTree' is evaluated to WHNF. shape :: (RadixTree a -> RadixTree a) -> Feed -> RadixTree a -> RadixTree a shape = shape0 

@@ -0,0 +1,38 @@+{-| Compressed references for spine-strict radix trees.++    Pointers have a much smaller memory footprint and+    allow faster lookup in trees that are known to never change shape.+ -}++module Data.RadixTree.Word8.Strict.Pointer+  ( Pointer+  , pointer+  , follow+  ) where++import           Data.RadixNTree.Word8.Key (Feed)+import           Data.RadixNTree.Word8.Strict (RadixTree)+import           Data.RadixNTree.Word8.Strict.Pointer++++{-# INLINE pointer #-}+-- | \(\mathcal{O}(\min(x,k))\).+--   Create a pointer that mirrors an existing key.+--+--   The pointer is only guaranteed to behave correctly for any tree that holds the+--   same set of keys as the provided one.+--+--   @since 1.1+pointer :: Feed -> RadixTree a -> Maybe Pointer+pointer = pointer0++++-- | \(\mathcal{O}(\log n)\).+--   Look up the value at a pointer in the tree, falling back to the given default value+--   if it does not exist.+--+--   @since 1.1+follow :: a -> Pointer -> RadixTree a -> a+follow = follow0

@@ -13,9 +13,9 @@     'Data.Patricia.Word.Strict.Unsafe.Patricia' tree, hence the definitions of     'Bin' and 'Nil' remain unchanged. -    The only state the resulting 'Radix1Tree' is unable to represent is the+    The only state the resulting t'Radix1Tree' is unable to represent is the     value at the root of the tree (for which the key is an empty byte sequence),-    as such that value is prepended with a special 2-tuple named 'RadixTree'.+    as such that value is prepended with a special 2-tuple named t'RadixTree'.  -}  module Data.RadixTree.Word8.Strict.Unsafe

@@ -1,10 +0,0 @@-module Radix.Word8.Common-  ( Location (..)-  ) where------ | Whether the cursor point to a point within the tree.-data Location = Inside-              | Outside-                deriving Show

@@ -5,6 +5,7 @@   ) where  import qualified Data.Radix1Tree.Word8.Lazy as Radix1+import qualified Data.Radix1Tree.Word8.Lazy.Zipper as Radix1 import           Data.RadixTree.Word8.Lazy (RadixTree) import qualified Data.RadixTree.Word8.Lazy as Radix import           Data.RadixTree.Word8.Lazy.Debug@@ -16,6 +17,7 @@  import           Data.Functor.Identity import qualified Data.List as List+import           Data.List.NonEmpty (NonEmpty (..)) import           Data.Word import           Test.Hspec @@ -136,25 +138,71 @@ subtreeT :: Eq a => TreeT [Word8] a subtreeT = Test treeEq (Radix.subtree . Radix.feedBytes) No.subtree -moveSingleT :: Eq a => IdT [Word8] a (Maybe a)-moveSingleT =-  Test (==) (\k -> Radix.stop . Radix.move (Radix.feedBytes k) . Radix.cursor)+descendLookup1T :: Eq a => IdT [Word8] a (Maybe a)+descendLookup1T =+  Test (==) (\k r -> let Radix.RadixTree mx t = r+                     in case k of+                          []   -> mx+                          l:ls -> do+                            ctx <- Radix1.descend (Radix1.feedBytes (l :| ls)) (Left t)+                            (v, _) <- Radix1.focus ctx+                            Just v+            )             No.lookup -moveThirdsT :: Eq a => IdT [Word8] a (Maybe a)-moveThirdsT =-  let thirds xs = let len = length xs+descendLookup3T :: Eq a => IdT [Word8] a (Maybe a)+descendLookup3T =+  let downward    []  mayEi = mayEi+      downward (k:ks) mayEi = do+        ei <- mayEi+        Right <$> Radix1.descend (Radix1.feedBytes (k :| ks)) ei++  in Test (==) (\xs r ->+                  let Radix.RadixTree mx t = r++                      len = length xs                       ~(as, ys) = List.splitAt (len `quot` 3) xs                       ~(bs, cs) = List.splitAt (len `quot` 3) ys -                  in Radix.move (Radix.feedBytes cs)-                   . Radix.move (Radix.feedBytes bs)-                   . Radix.move (Radix.feedBytes as)+                  in case downward cs . downward bs $ downward as (Just $ Left t) of+                       Just (Right ctx) -> fst <$> Radix1.focus ctx+                       Just (Left _)    -> mx+                       _                -> Nothing+               )+               No.lookup -  in Test (==) (\k -> Radix.stop . thirds k . Radix.cursor) No.lookup+descendAdjust3T :: (Eq a, Integral a) => TreeT ([Word8], a) a+descendAdjust3T =+  let downward    []  mayEi = mayEi+      downward (k:ks) mayEi = do+        ei <- mayEi+        Right <$> Radix1.descend (Radix1.feedBytes (k :| ks)) ei +  in Test treeEq (\(xs, a) r ->+                     let Radix.RadixTree mx t = r +                         len = length xs+                         ~(as, ys) = List.splitAt (len `quot` 3) xs+                         ~(bs, cs) = List.splitAt (len `quot` 3) ys +                     in case downward cs . downward bs $ downward as (Just $ Left t) of+                          Just (Right ctx) -> do+                            case Radix1.focus ctx of+                              Nothing            -> r+                              Just (x, reinsert) ->+                                Radix.RadixTree mx $ reinsert (x + fromIntegral a)++                          Just (Left _)    ->+                            case mx of+                              Nothing -> r+                              Just x  -> Radix.RadixTree (Just $ x + fromIntegral a) t++                          _                -> r+                 )+                 (\(k, a) -> No.adjust (+ fromIntegral a) k)+++ prefixT :: Eq a => TreeT [Word8] a prefixT = Test treeEq (Radix.prefix . Radix.feedBytes) No.prefix @@ -704,8 +752,9 @@     it "find"             $ run unary1  findT     it "member"           $ run unary1_ memberT     it "subtree"          $ run unary1_ subtreeT-    it "move/single"      $ run unary1_ moveSingleT-    it "move/thirds"      $ run unary1_ moveThirdsT+    it "descend/lookup1"  $ run unary1_ descendLookup1T+    it "descend/lookup3"  $ run unary1_ descendLookup3T+    it "descend/adjust3"  $ run unary1  descendAdjust3T     it "insert"           $ run unary1  insertT     it "insertWith"       $ run unary1  insertWithT     it "adjust"           $ run unary1  adjustT

@@ -5,10 +5,12 @@   ) where  import qualified Data.Radix1Tree.Word8.Strict as Radix1+import qualified Data.Radix1Tree.Word8.Strict.Zipper as Radix1 import           Data.RadixTree.Word8.Strict (RadixTree) import qualified Data.RadixTree.Word8.Strict as Radix import           Data.RadixTree.Word8.Strict.Debug import qualified Data.RadixTree.Word8.Strict.Unsafe as Radix+import qualified Data.RadixTree.Word8.Strict.Pointer as Radix import           No.Tree (NoTree) import qualified No.Tree as No import           Test.Kit@@ -16,6 +18,7 @@  import           Data.Functor.Identity import qualified Data.List as List+import           Data.List.NonEmpty (NonEmpty (..)) import           Data.Word import           Test.Hspec @@ -134,25 +137,78 @@ subtreeT :: Eq a => TreeT [Word8] a subtreeT = Test treeEq (Radix.subtree . Radix.feedBytes) No.subtree -moveSingleT :: Eq a => IdT [Word8] a (Maybe a)-moveSingleT =-  Test (==) (\k -> Radix.stop . Radix.move (Radix.feedBytes k) . Radix.cursor)+pointerT :: Eq a => IdT ([Word8], a) a (Maybe a)+pointerT = Test (==) (\(k, i) r -> do ptr <- Radix.pointer (Radix.feedBytes k) r+                                      Just $ Radix.follow i ptr r+                     )+                     (\(k, _) r -> No.lookup k r)++descendLookup1T :: Eq a => IdT [Word8] a (Maybe a)+descendLookup1T =+  Test (==) (\k r -> let Radix.RadixTree mx t = r+                     in case k of+                          []   -> mx+                          l:ls -> do+                            ctx <- Radix1.descend (Radix1.feedBytes (l :| ls)) (Left t)+                            (v, _) <- Radix1.focus ctx+                            Just v+            )             No.lookup -moveThirdsT :: Eq a => IdT [Word8] a (Maybe a)-moveThirdsT =-  let thirds xs = let len = length xs+descendLookup3T :: Eq a => IdT [Word8] a (Maybe a)+descendLookup3T =+  let downward    []  mayEi = mayEi+      downward (k:ks) mayEi = do+        ei <- mayEi+        Right <$> Radix1.descend (Radix1.feedBytes (k :| ks)) ei++  in Test (==) (\xs r ->+                  let Radix.RadixTree mx t = r++                      len = length xs                       ~(as, ys) = List.splitAt (len `quot` 3) xs                       ~(bs, cs) = List.splitAt (len `quot` 3) ys -                  in Radix.move (Radix.feedBytes cs)-                   . Radix.move (Radix.feedBytes bs)-                   . Radix.move (Radix.feedBytes as)+                  in case downward cs . downward bs $ downward as (Just $ Left t) of+                       Just (Right ctx) -> fst <$> Radix1.focus ctx+                       Just (Left _)    -> mx+                       _                -> Nothing+               )+               No.lookup -  in Test (==) (\k -> Radix.stop . thirds k . Radix.cursor) No.lookup+descendAdjust3T :: (Eq a, Integral a) => TreeT ([Word8], a) a+descendAdjust3T =+  let downward    []  mayEi = mayEi+      downward (k:ks) mayEi = do+        ei <- mayEi+        Right <$> Radix1.descend (Radix1.feedBytes (k :| ks)) ei +  in Test treeEq (\(xs, a) r ->+                     let Radix.RadixTree mx t = r +                         len = length xs+                         ~(as, ys) = List.splitAt (len `quot` 3) xs+                         ~(bs, cs) = List.splitAt (len `quot` 3) ys +                     in case downward cs . downward bs $ downward as (Just $ Left t) of+                          Just (Right ctx) -> do+                            case Radix1.focus ctx of+                              Nothing            -> r+                              Just (x, reinsert) ->+                                Radix.RadixTree mx $ reinsert (x + fromIntegral a)++                          Just (Left _)    ->+                            case mx of+                              Nothing -> r+                              Just x  -> Radix.RadixTree (Just $ x + fromIntegral a) t++                          _                -> r+                 )+                 (\(k, a) -> No.adjust (+ fromIntegral a) k)++++ prefixT :: Eq a => TreeT [Word8] a prefixT = Test treeEq (Radix.prefix . Radix.feedBytes) No.prefix @@ -720,8 +776,10 @@     it "find"             $ run unary1  findT     it "member"           $ run unary1_ memberT     it "subtree"          $ run unary1_ subtreeT-    it "move/single"      $ run unary1_ moveSingleT-    it "move/thirds"      $ run unary1_ moveThirdsT+    it "pointer1       "  $ run unary1  pointerT+    it "descend/lookup1"  $ run unary1_ descendLookup1T+    it "descend/lookup3"  $ run unary1_ descendLookup3T+    it "descend/adjust3"  $ run unary1  descendAdjust3T     it "insert"           $ run unary1  insertT     it "insertWith"       $ run unary1  insertWithT     it "insertWith'"      $ run unary1  insertWithT'