rope-utf16-splay 0.1.0.0 → 0.2.0.0

raw patch · 9 files changed

+84/−42 lines, 9 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +8/−0
• README.md +5/−1
• rope-utf16-splay.cabal +10/−6
• src/Data/Rope/UTF16.hs +6/−3
• src/Data/Rope/UTF16/Internal.hs +36/−24
• src/Data/Rope/UTF16/Internal/Text.hs +1/−1
• src/Data/Rope/UTF16/Position.hs +2/−2
• src/Data/SplayTree.hs +7/−0
• tests/Main.hs +9/−5

@@ -0,0 +1,8 @@+# 0.2.0.0++- Rename rowColumnCodePoints to rowColumnCodeUnits+- Add `null` function++# 0.1.0.0++- Initial release

@@ -1,7 +1,11 @@ # rope-utf16-splay [![Build Status](https://travis-ci.org/ollef/rope-utf16-splay.svg?branch=master)](https://travis-ci.org/ollef/rope-utf16-splay) -Thick strings optimised for indexing and updating using UTF-16 code points and+Thick strings optimised for indexing and updating using UTF-16 code units and row/column pairs.  This implementation uses splay trees instead of the usual finger trees, which is faster according to [the benchmarks](bench.html).++## Contact++Olle Fredriksson - https://github.com/ollef

@@ -1,9 +1,11 @@ name:                rope-utf16-splay-version:             0.1.0.0-synopsis:            Ropes optimised for updating using UTF-16 code points and row/column pairs.-description:         This implementation uses splay trees instead of the usual-                     finger trees. According to my benchmarks, splay trees are-                     faster in most situations.+version:             0.2.0.0+synopsis:            Ropes optimised for updating using UTF-16 code units and+                     row/column pairs.+description:         Ropes optimised for updating using UTF-16 code units and+                     row/column pairs.  This implementation uses splay trees+                     instead of the usual finger trees. According to my+                     benchmarks, splay trees are faster in most situations. homepage:            https://github.com/ollef/rope-utf16-splay license:             BSD3 license-file:        LICENSE@@ -12,7 +14,9 @@ copyright:           (c) 2018 Olle Fredriksson category:            Data, Text, Language build-type:          Simple-extra-source-files:  README.md+extra-source-files:+                     README.md+                     CHANGELOG.md cabal-version:       >=1.10 tested-with:         GHC == 8.0.2, GHC == 8.2.2, GHC == 8.4.1 

@@ -2,7 +2,10 @@   ( module Position   , Rope.Rope -  -- * Conversions to and from @Text@ and @String@+  -- * Queries+  , Rope.null++  -- * Conversions to and from 'Text' and 'String'   , Rope.toText   , Rope.toLazyText   , Rope.fromText@@ -13,12 +16,12 @@   , Rope.unconsChunk   , Rope.unsnocChunk -  -- * UTF-16 code point indexing+  -- * UTF-16 code unit indexing   , Rope.length   , Rope.splitAt   , Rope.take   , Rope.drop-  , Rope.rowColumnCodePoints+  , Rope.rowColumnCodeUnits    -- * Breaking by predicate   , Rope.span

@@ -38,24 +38,24 @@ instance SplayTree.Measured Position Chunk where   measure (Chunk _ m) = m --- | A @SplayTree@ of @Text@ values optimised for being indexed by and--- modified at UTF-16 code points and row/column (@RowColumn@) positions.--- Internal invariant: No empty @Chunk@s in the @SplayTree@+-- | A 'SplayTree' of 'Text' values optimised for being indexed by and+-- modified at UTF-16 code units and row/column ('RowColumn') positions.+-- Internal invariant: No empty 'Chunk's in the 'SplayTree' newtype Rope = Rope { unrope :: SplayTree Position Chunk }   deriving (SplayTree.Measured Position, Show) --- | The maximum length, in code points, of a chunk+-- | The maximum length, in code units, of a chunk chunkLength :: Int chunkLength = 1000  -- | Append joins adjacent chunks if that can be done while staying below--- @chunkLength@.+-- 'chunkLength'. instance Semigroup Rope where   Rope r1 <> Rope r2 = case (SplayTree.unsnoc r1, SplayTree.uncons r2) of     (Nothing, _) -> Rope r2     (_, Nothing) -> Rope r1     (Just (r1', a), Just (b, r2'))-      | codePoints (chunkMeasure a <> chunkMeasure b) <= chunkLength+      | codeUnits (SplayTree.measure a) + codeUnits (SplayTree.measure b) <= chunkLength         -> Rope $ r1' <> ((a <> b) SplayTree.<| r2')       | otherwise         -> Rope $ r1' <> (a SplayTree.<| b SplayTree.<| r2')@@ -74,8 +74,18 @@   fromString = fromText . Text.pack  ---------------------------------------------------------------------------------- * Conversions to and from @Text@ and @String@+-- * Queries +-- | Is the rope empty?+--+-- @since 0.2.0.0+{-# INLINE null #-}+null :: Rope -> Bool+null (Rope r) = SplayTree.null r++-------------------------------------------------------------------------------+-- * Conversions to and from 'Text' and 'String'+ toText :: Rope -> Text toText = Text.concat . toChunks @@ -106,63 +116,65 @@ ------------------------------------------------------------------------------- -- * Chunking --- | The raw @Text@ data that the @Rope@ is built from+-- | The raw 'Text' data that the 'Rope' is built from toChunks :: Rope -> [Text] toChunks = fmap chunkText . toList . unrope --- | Get the first chunk and the rest of the @Rope@ if non-empty+-- | Get the first chunk and the rest of the 'Rope' if non-empty unconsChunk :: Rope -> Maybe (Text, Rope) unconsChunk (Rope r) = case SplayTree.uncons r of   Nothing -> Nothing   Just (Chunk t _, r') -> Just (t, Rope r') --- | Get the last chunk and the rest of the @Rope@ if non-empty+-- | Get the last chunk and the rest of the 'Rope' if non-empty unsnocChunk :: Rope -> Maybe (Rope, Text) unsnocChunk (Rope r) = case SplayTree.unsnoc r of   Nothing -> Nothing   Just (r', Chunk t _) -> Just (Rope r', t)  ---------------------------------------------------------------------------------- * UTF-16 code point indexing+-- * UTF-16 code unit indexing --- | Length in code points (not characters)+-- | Length in code units (not characters) length :: Rope -> Int-length = codePoints . SplayTree.measure+length = codeUnits . SplayTree.measure --- | Split the rope at the nth code point (not character)+-- | Split the rope at the nth code unit (not character) splitAt :: Int -> Rope -> (Rope, Rope)-splitAt n (Rope r) = case SplayTree.split ((> n) . codePoints) r of+splitAt n (Rope r) = case SplayTree.split ((> n) . codeUnits) r of   SplayTree.Outside     | n < 0 -> (mempty, Rope r)     | otherwise -> (Rope r, mempty)   SplayTree.Inside pre (Chunk t _) post -> (Rope pre <> fromShortText pret, fromShortText postt <> Rope post)     where-      n' = n - codePoints (SplayTree.measure pre)+      n' = n - codeUnits (SplayTree.measure pre)       (pret, postt) = split16At n' t --- | Take the first n code points (not characters)+-- | Take the first n code units (not characters) take :: Int -> Rope -> Rope take n = fst . Data.Rope.UTF16.Internal.splitAt n --- | Drop the first n code points (not characters)+-- | Drop the first n code units (not characters) drop :: Int -> Rope -> Rope drop n = snd . Data.Rope.UTF16.Internal.splitAt n --- | Get the code point index in the rope that corresponds to a @RowColumn@ position-rowColumnCodePoints :: RowColumn -> Rope -> Int-rowColumnCodePoints v (Rope r) = case SplayTree.split ((> v) . rowColumn) r of+-- | Get the code unit index in the rope that corresponds to a 'RowColumn' position+--+-- @since 0.2.0.0+rowColumnCodeUnits :: RowColumn -> Rope -> Int+rowColumnCodeUnits v (Rope r) = case SplayTree.split ((> v) . rowColumn) r of   SplayTree.Outside     | v <= RowColumn 0 0 -> 0-    | otherwise -> codePoints $ SplayTree.measure r+    | otherwise -> codeUnits $ SplayTree.measure r   SplayTree.Inside pre (Chunk t _) _ -> go 0 $ rowColumn prePos     where       prePos = SplayTree.measure pre       len = Unsafe.lengthWord16 t       go i !v'-        | v <= v' || i >= len = codePoints prePos + i+        | v <= v' || i >= len = codeUnits prePos + i         | otherwise = case Unsafe.iter t i of           Unsafe.Iter '\n' delta -> go (i + delta) (v' <> RowColumn 1 0)-          Unsafe.Iter _ 2 | v == v' <> RowColumn 0 1 -> codePoints prePos + i+          Unsafe.Iter _ 2 | v == v' <> RowColumn 0 1 -> codeUnits prePos + i           Unsafe.Iter _ delta -> go (i + delta) (v' <> RowColumn 0 delta)  -------------------------------------------------------------------------------

@@ -1,4 +1,4 @@--- | Helpers for working with @Text@ in UTF-16 code points+-- | Helpers for working with 'Text' in UTF-16 code units module Data.Rope.UTF16.Internal.Text where  import Data.Text(Text)

@@ -4,7 +4,7 @@  data RowColumn = RowColumn   { row :: !Int -- ^ Number of newlines before this position-  , column :: !Int -- ^ Number of code points since last newline or start of string+  , column :: !Int -- ^ Number of code units since last newline or start of string   } deriving (Eq, Ord, Show)  instance Semigroup RowColumn where@@ -18,7 +18,7 @@   mappend = (<>)  data Position = Position-  { codePoints :: !Int+  { codeUnits :: !Int   , rowColumn :: !RowColumn   } deriving (Eq, Ord, Show) 

@@ -35,6 +35,13 @@   {-# INLINE mappend #-}   mappend = (Semigroup.<>) +-- | Is the splay tree empty?+--+-- @since 0.2.0.0+null :: SplayTree v a -> Bool+null Leaf = True+null Fork {} = False+ ------------------------------------------------------------------------------- -- * Construction 

@@ -21,7 +21,7 @@         t2 = Text.pack s2     Rope.toText (Rope.fromText t1 <> Rope.fromText t2) == t1 <> t2 -  , testProperty "length is UTF-16 code points" $ \s -> do+  , testProperty "length is UTF-16 code units" $ \s -> do     let t = Text.pack s     Rope.length (Rope.fromText t) == Unsafe.lengthWord16 t @@ -38,13 +38,13 @@     let t = Text.pack s     Rope.toText (Rope.drop i $ Rope.fromText t) == Rope.drop16 i t -  , testProperty "rowColumnCodePoints first line" $ \s i -> do+  , testProperty "rowColumnCodeUnits first line" $ \s i -> do     let t = Text.pack $ takeWhile (/= '\n') s-    Rope.clamp16 i t == Rope.rowColumnCodePoints (Rope.RowColumn 0 i) (Rope.fromText t)+    Rope.clamp16 i t == Rope.rowColumnCodeUnits (Rope.RowColumn 0 i) (Rope.fromText t) -  , testProperty "rowColumnCodePoints subsequent lines" $ \s (NonNegative newlines) (NonNegative i) -> do+  , testProperty "rowColumnCodeUnits subsequent lines" $ \s (NonNegative newlines) (NonNegative i) -> do     let t = Text.pack $ replicate newlines '\n' ++ takeWhile (/= '\n') s-    Rope.clamp16 (newlines + i) t == Rope.rowColumnCodePoints (Rope.RowColumn newlines i) (Rope.fromText t)+    Rope.clamp16 (newlines + i) t == Rope.rowColumnCodeUnits (Rope.RowColumn newlines i) (Rope.fromText t)    , testProperty "span matches Text" $ \s p -> do     let t = Text.pack s@@ -67,4 +67,8 @@     let t = Text.pack s         f = QC.applyFun p     Rope.toText (Rope.dropWhile f $ Rope.fromText t) == Text.dropWhile f t++  , testProperty "null matches Text" $ \s -> do+    let t = Text.pack s+    Rope.null (Rope.fromText t) == Text.null t   ]