-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Ropes, an alternative to (Byte)Strings. -- -- Ropes : an alternative to Strings, a time and space-efficient -- representation of character strings. @package Data-Rope @version 0.2 module Data.Rope.Internals c_mmap :: Ptr a -> CSize -> CInt -> CInt -> CInt -> CInt -> IO (Ptr Word8) c_munmap :: Ptr a -> CSize -> IO () c_PROT_NONE :: CInt c_PROT_READ :: CInt c_PROT_WRITE :: CInt c_PROT_EXEC :: CInt c_MAP_SHARED :: CInt c_MAP_FILE :: CInt w2c :: Word8 -> Char c2w :: Char -> Word8 -- | Implementation of the ideas in -- http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf. -- Inspired also by Data.Map and the OCaml version of ropes. module Data.Rope data Rope -- | O(1) The empty Rope empty :: Rope -- | O(1) Convert a Word8 into a Rope singleton :: Word8 -> Rope -- | O(n) Convert a list of Word8 into a Rope pack :: [Word8] -> Rope -- | O(n) Inverse conversion unpack :: Rope -> [Word8] -- | O(n) Conversion from a strict ByteString fromByteString :: ByteString -> Rope -- | O(n) Conversion to a strict ByteString toByteString :: Rope -> ByteString -- | O(log n). Appends the specified byte at the beginning of the -- Rope. cons :: Word8 -> Rope -> Rope -- | O(log n). Appends the specified byte at the end of the Rope. snoc :: Rope -> Word8 -> Rope -- | O(log n) Concatenates two Ropes append :: Rope -> Rope -> Rope -- | O(log n) First element of the Rope. Raises an error if the -- argument is empty. head :: Rope -> Word8 -- | O(log n). Returns the first element of the Rope, and the -- Rope of the remaining elements. uncons :: Rope -> Maybe (Word8, Rope) -- | O(log n). Last element of a Rope. last :: Rope -> Word8 -- | O(log n) The elements after the head. An error is raised if the -- Rope is empty. tail :: Rope -> Rope -- | O(log n) The elements in the Rope except the last one. init :: Rope -> Rope -- | O(1) Tests whether a Rope is empty. null :: Rope -> Bool -- | O(1) Length of a Rope. length :: Rope -> Int -- | O(n). map f r applies f on each element of -- r and returns the concatenation of the result. map :: (Word8 -> Word8) -> Rope -> Rope -- | O(n) efficient way to reverse a Rope. reverse :: Rope -> Rope -- | O(n) intercalate an element between each element of the list of -- Ropes and concatenates the result. intercalate :: Rope -> [Rope] -> Rope -- | O(log n) insert a i b inserts Rope a -- in Rope b after the ith element of -- b. insert :: Rope -> Int -> Rope -> Rope -- | O(n). fold over a Rope. This implementation is not -- tail-recursive but never pushes more than O(log n) calls on the stack. foldl :: (a -> Word8 -> a) -> a -> Rope -> a -- | O(n). like foldl but strict. foldl' :: (a -> Word8 -> a) -> a -> Rope -> a -- | O(n). Right fold. Again not tail-recursive but never uses more than -- O(log n) on the stack. foldr :: (Word8 -> a -> a) -> a -> Rope -> a take :: Int -> Rope -> Rope drop :: Int -> Rope -> Rope splitAt# :: Int -> Rope -> (# Rope, Rope #) -- | O(log n). splitAt n xs is equivalent to (take n xs, -- drop n xs), but a little faster. splitAt :: Int -> Rope -> (Rope, Rope) -- | O(n). breakByte c r breaks Rope r -- before the first occurence of c. breakByte :: Word8 -> Rope -> (Rope, 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] -- | O(n). Satisfies lines r == breaks 0x0a r. lines :: Rope -> [Rope] -- | O(log n) returns the Word8 at given index in the Rope index :: Rope -> Int -> Char -- | O(n) returns the index of the first element equal to the query -- element. This implementation uses memchr at leaves, and explores the -- rope in parallel (with par). elemIndex :: Word8 -> Rope -> Maybe Int -- | O(n) Same as elemIndex, but explores the Rope -- sequentially. Useful for Ropes loaded lazily with -- readFile. elemIndex' :: Word8 -> Rope -> Maybe Int -- | O(n) returns the list of all positions where the queried elements -- occurs in the Rope. This implementation uses memchr. elemIndices :: Word8 -> Rope -> [Int] -- | Lazy file reading, using mmap. readFile :: FilePath -> IO Rope -- | Strict hGet. The whole rope is constructed. hGet :: Handle -> Int -> IO Rope -- | Returns the next line in the input Handle. If you need to -- iterate hGetLine, it may be more efficient to first -- mmap the file using readFile, or even load it with -- then iterate breakByte 0x0a : hGetLine -- allocates a buffer to read the file and may waste most of this space -- if the lines are shorter than the standard buffer size of this module. hGetLine :: Handle -> IO Rope -- | Reads the contents of a file handle strictly, then closes it. hGetContents :: Handle -> IO Rope -- | Writes the contents of the Rope on the specified Handle. hPut :: Handle -> Rope -> IO () -- | like hPut, but with a newline character at the end of the -- output hPutStrLn :: Handle -> Rope -> IO () -- | synonym for hPut. hPutStr :: Handle -> Rope -> IO () -- | like putStr but with a newline character at the end of the -- output putStrLn :: Rope -> IO () -- | Writes the contents of the Rope on the standard output. putStr :: Rope -> IO () instance Ord Rope instance Eq Rope instance Show Rope instance IsString Rope