Data-Rope 0 → 0.1

raw patch · 2 files changed

+163/−33 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data-Rope.cabal +1/−1
• Data/Rope.lhs +162/−32

@@ -1,5 +1,5 @@ Name:		Data-Rope-Version: 	0+Version: 	0.1 Synopsis:	Ropes, an alternative to (Byte)Strings. Description: 	Ropes : an alternative to Strings, 		a time and space-efficient representation of character

@@ -40,6 +40,9 @@   drop,   splitAt#,   splitAt,+  breakByte,+  breaks,+  lines,   -- * Indexing 'Rope's   index,   elemIndex,@@ -74,7 +77,7 @@ import GHC.IO (IO(IO),unsafePerformIO,unsafeInterleaveIO) import GHC.Base (realWorld#) import GHC.IO.Handle.Types-import GHC.IO.Handle.Internals+--import GHC.IO.Handle.Internals import GHC.IO.Device as IODevice #else import System.IO.Unsafe@@ -82,16 +85,16 @@ import Data.Maybe import GHC.Conc -import System.Posix (openFd,closeFd,defaultFileFlags,getFdStatus,getFileStatus,-                     fileSize,OpenMode(..),-                     OpenFileFlags(trunc))+import System.Posix (openFd,closeFd,defaultFileFlags,getFileStatus,+                     fileSize,OpenMode(..)) import System.IO hiding (hPutStrLn,hPutStr,putStrLn,putStr,readFile) import qualified Prelude(length,map,splitAt) import Prelude hiding (length,null,head,tail,last,init,map,reverse,                        foldl,foldr,-                       take,drop,splitAt,+                       take,drop,splitAt,lines,                        putStrLn,putStr,readFile) import Data.Bits hiding(rotateL,rotateR)+ \end{code}  Attention, on ne garantit pas necessairement que les deux sous-arbres sont non-vides.@@ -115,12 +118,69 @@            position:: !Int,            length_:: !Int,            rope::Rope  }-  deriving (Show)+--  deriving (Show)  instance IsString Rope where   fromString s=pack $ Prelude.map (fromIntegral.fromEnum) s  +instance Show Rope where+  show s="\""++(Prelude.map (toEnum.fromIntegral) $ unpack s)++"\""++{-+instance Show Rope where+  show (s@String{})=show ((Prelude.map (toEnum.fromIntegral) $ unpack s)::String)+  show (Concat{l,r})="Concat { l="++(show l)++"\nr="++(show r)+-}++instance Eq Rope where+  (==) String{contents=ca,offset=oa,length_=la}+    String{contents=cb, offset=ob, length_=lb} =+    +    la==lb &&+    (inlinePerformIO $ (withForeignPtr ca $ \pa->+                         withForeignPtr cb $ \pb->do+                           x<-strncmp (pa`plusPtr`oa) (pb`plusPtr`ob) (fromIntegral la)+                           return $ x == 0))+  +  (==) a b=+    (length a == length b) &&+    (case (a,b) of+        (Concat{l,r}, _) -> +          let (# x,y #)=splitAt# (length l) b in+          x==l && y==r+        (_,Concat{l,r})->+          let (# x,y #)=splitAt# (length l) a in+          x==l && y==r+        _->undefined) -- never happens+    +    +instance Ord Rope where+  compare (String{contents=ca,offset=oa,length_=la})+    (String{contents=cb, offset=ob, length_=lb}) =+    +    inlinePerformIO $ (withForeignPtr ca $ \pa->withForeignPtr cb $ \pb->do+                          x<-strncmp (pa`plusPtr`oa) (pb`plusPtr`ob) (fromIntegral $ min la lb)+                          if x==0 then return $ compare la lb else+                            return $ compare x 0)+  +  compare a_ b_=+    let (a,b)=if length a_<length b_ then (b_,a_) else (a_,b_) in+    case (a,b) of+      (_,Concat{l,r})->+        let (# x,y #)=splitAt# (length l) a in+        case compare x l of+          EQ->compare y r+          ord->ord+      (Concat{l,r},_)->+        let (# x,y #)=splitAt# (length l) b in+        case compare l x of+          EQ->compare r y+          ord->ord+      _->undefined --never happens+++   -- | leafLen est la taille standard des blocs de feuilles. leafSize::Int leafSize=0x10000@@ -262,13 +322,13 @@ map::(Word8->Word8)->Rope->Rope map f (String{contents,offset,length_})=   unsafePerformIO $ withForeignPtr contents $ \c->do-    contents<-mallocForeignPtrBytes leafSize-    withForeignPtr contents $ \p->copyMap p (c`plusPtr`offset) length_+    cont<-mallocForeignPtrBytes leafSize+    withForeignPtr cont $ \p->copyMap p (c`plusPtr`offset) length_          i0<-mallocForeignPtr     withForeignPtr i0 $ \i->poke i length_     -    return $ String { contents,offset=0,length_,i0 }+    return $ String { contents=cont,offset=0,length_,i0 }        where         copyMap _ _ 0=return ()@@ -283,14 +343,14 @@ reverse::Rope->Rope reverse (String{contents,offset,length_})=   unsafePerformIO $ withForeignPtr contents $ \c->do-    contents<-mallocForeignPtrBytes leafSize-    withForeignPtr contents $ \p->+    cont<-mallocForeignPtrBytes leafSize+    withForeignPtr cont $ \p->       copyRev (p`plusPtr`(length_-1)) (c`plusPtr`offset) length_          i0<-mallocForeignPtr     withForeignPtr i0 $ \i->poke i length_     -    return $ String { contents,offset=0,length_,i0 }+    return $ String { contents=cont,offset=0,length_,i0 }        where         copyRev::Ptr Word8->Ptr Word8->Int->IO()@@ -536,6 +596,7 @@ \begin{code}  foreign import ccall unsafe "string.h memchr" memchr::Ptr Word8->Word8->CSize->IO (Ptr Word8)+foreign import ccall unsafe "string.h strncmp" strncmp::Ptr Word8->Ptr Word8->CSize->IO CInt  {-# INLINE inlinePerformIO #-} inlinePerformIO::IO a->a@@ -565,11 +626,11 @@       index_ (Concat{r,l}) i_         |i_>=length l = index_ r (i_-length l)         |otherwise = index_ l i_-      index_ (File{handle,position,length_}) i_=-        unsafePerformIO $ alloca $ \c->do+      index_ (File{handle,position}) i_=+        unsafePerformIO $ alloca $ \cc->do           hSeek handle AbsoluteSeek $ fromIntegral $ position+i_-          hGetBuf handle c 1-          peek c+          hGetBuf handle cc 1+          peek cc   -- | O(n) returns the index of the first element equal to the query element. This implementation@@ -594,7 +655,8 @@       unsafePerformIO $ allocaBytes length_ $ \c->do         hSeek handle AbsoluteSeek $ fromIntegral position         l<-hGetBuf handle c length_-        loop c 0 l+        x<-loop c 0 l+        return $ x>>=(return.(+i))            loop ptr i l       | i>=l = return Nothing@@ -631,7 +693,7 @@       in        sl -    elemIndex_ i (File{handle,position,length_}) list=+    elemIndices_ i (File{handle,position,length_}) list=       unsafePerformIO $ allocaBytes length_ $ \c->do         hSeek handle AbsoluteSeek $ fromIntegral position         l<-hGetBuf handle c length_@@ -717,7 +779,7 @@ \begin{code}  take::Int->Rope->Rope-take i (s@String{offset,length_})=s { length_=min length_ i }+take i (s@String{length_})=s { length_=min length_ i } take i (c@Concat{l,r})   | i==length l = l   | i<length l = take i l@@ -731,17 +793,17 @@   | otherwise = drop (i-length l) r  splitAt# ::Int->Rope->(# Rope,Rope #)-splitAt# i (s@String{contents,offset,length_})+splitAt# i (s@String{offset,length_})   | i>=length_ = (# s,empty #)   | otherwise = (# s { length_=i }, s { offset=offset+i,length_=length_-i} #) splitAt# i (c@Concat{length_=l0,l,r})   | i>=l0 = (# c,empty #)   | i>=length_ l =     let (# u,v #)=splitAt# (i-length_ l) r in-    (# c { r=u }, v #)+    (# c { length_=i, r=u }, v #)   | otherwise =        let (# u,v #)=splitAt# i l in-      (# u, c { l=v } #)+      (# u, c { length_=i-length_ u, l=v } #)  -- | O(log n). @'splitAt' n xs@ is equivalent to (take n xs, drop n xs), but a little faster. splitAt::Int->Rope->(Rope,Rope)@@ -749,6 +811,79 @@   let (# u,v #)=splitAt# i r in   (u,v) +-- | O(n). @'breakByte' c r@ breaks 'Rope' @r@ before the first occurence of @c@.+breakByte::Word8->Rope->(Rope,Rope)+breakByte w rope_=+  let (_,b,c)=breakByte_ rope_ in+  (b,c)+  where+    breakByte_::Rope->(Bool,Rope,Rope)+    breakByte_ x@(String{contents,offset,length_})=+      inlinePerformIO $ withForeignPtr contents $ \con->do+        ptr<-memchr (con`plusPtr`offset) w (fromIntegral length_)+        return $ if ptr==nullPtr then (False, x, empty) else+                   (True,+                    x { length_=length_-(ptr`minusPtr`con)-1 }, +                    x { offset=offset+(ptr`minusPtr`con) })+                   +    breakByte_ (Concat{l,r})=+      case breakByte_ l of+        (True,x,y)->(True,x,append y r)+        (False,x,_)->+          case breakByte_ r of+            (True,x',y')->(True,append x x',y')+            u@(False,_,_)->u+    breakByte_ (File{rope})=breakByte_ rope++-- | O(n). @'breaks' w r@ breaks 'Rope' @r@ between each occurence of @w@ (non-inclusive).+-- This function is not tail-recursive, uses @memchr@ and constructs the list in parallel+-- using @'par'@.+    +breaks::Word8->Rope->[Rope]+breaks w rope_=+  let (a,_)=lines_ True rope_ in+  a+  where+    lines_::Bool->Rope->([Rope],Maybe Rope)+    lines_ isLast (str@String{contents,offset,length_})=+      if length_<=0 then ([],Nothing) else+        let off=inlinePerformIO $ withForeignPtr contents $ \con->do+              let pcon=con`plusPtr`offset+              ptr<-memchr pcon w (fromIntegral length_)+              if ptr==nullPtr then return Nothing else return $ Just (ptr`minusPtr`pcon)+        in+         case off of+           Nothing-> -- traceShow ("str",isLast, str) $ +                    if isLast then +                      if length str>0 then ([str],Nothing) else ([],Nothing)+                    else ([], Just str)+           Just diff->+             let line=str { length_=diff }+                 (a,b)=lines_ isLast (str{ offset=offset+diff+1,+                                           length_=length_-diff-1})+             in+              -- traceShow ("line",line:a,b) $+              (line:a,b)+             +    lines_ isLast (Concat{l,r})=+      let (ll,x)=lines_ False l+          (lr,y)=lines_ isLast r+      in+       (ll`par`lr)`seq`+       (case lr of+           []->case (x,y) of+             (Just xx, Just yy)->(ll,Just $ append xx yy)+             (Just _, Nothing)->(ll, x)+             (Nothing, _)->(ll, y)+             +           h:s->case x of { Nothing->(ll++lr,y); Just xx->(ll++((append xx h):s), y) }+       )+    +-- | O(n). Satisfies @lines r == breaks 0x0a r@.+lines::Rope->[Rope]+lines r=breaks 0x0a r++ \end{code}  Input and Output@@ -776,9 +911,7 @@ hPutStrLn::Handle->Rope->IO() hPutStrLn handle r=do   hPut handle r-  alloca $ \c->do-    poke (c::Ptr Word8) 0x0a-    hPutBuf handle c 1+  hPutChar handle '\n'    -- | Writes the contents of the 'Rope' on the standard output. putStr::Rope->IO()@@ -787,7 +920,7 @@ -- | like 'putStr' but with a newline character at the end of the output putStrLn::Rope->IO() putStrLn=hPutStrLn stdout-+     fromPtr::ForeignPtr Word8->Int->Int->IO Rope@@ -801,10 +934,10 @@          return $ String { contents,i0,offset=0,length_=s } -  | otherwise = withForeignPtr fp $ \p->do+  | otherwise = do     let sl=s`shiftR`1         sr=sl+s.&.1-        sz=ceiling $ (fromIntegral s)/(fromIntegral leafSize)+        sz=ceiling $ ((fromIntegral s)/(fromIntegral leafSize) :: Double)     l<-unsafeInterleaveIO $ fromPtr fp offset sl     r<-unsafeInterleaveIO $ fromPtr fp (offset+sl) sr     return $ Concat { l,r,length_=s, sizeC=2*sz-1 }@@ -827,7 +960,7 @@         fill p l         fill (p`plusPtr`(length_ l)) r       fill p (String{contents,offset,length_})=-        withForeignPtr contents $ \c->copyBytes p (c`plusPtr`offset) length_+        withForeignPtr contents $ \cc->copyBytes p (cc`plusPtr`offset) length_     -- | Lazy file reading, using @mmap@.@@ -856,9 +989,6 @@   position<-hTell handle   buildRope handle position length_   -  where-    realSize=leafSize*(ceiling $ (fromIntegral length_)/(fromIntegral leafSize))-     buildRope::Handle->Integer->Int->IO Rope buildRope handle position len       | len<=leafSize = do