Data.Rope

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.

The Rope type

data Rope

Instances

Eq Rope

Ord Rope

Show Rope

IsString Rope

Introducing and eliminating Ropes

empty :: Rope

O(1) The empty Rope

singleton :: Word8 -> Rope

O(1) Convert a Word8 into a Rope

pack :: [Word8] -> Rope

O(n) Convert a list of Word8 into a Rope

unpack :: Rope -> [Word8]

O(n) Inverse conversion

fromByteString :: ByteString -> Rope

O(n) Conversion from a strict ByteString

toByteString :: Rope -> ByteString

O(n) Conversion to a strict ByteString

Basic interface

cons :: Word8 -> Rope -> Rope

O(log n). Appends the specified byte at the beginning of the Rope.

snoc :: Rope -> Word8 -> Rope

O(log n). Appends the specified byte at the end of the Rope.

append :: Rope -> Rope -> Rope

O(log n) Concatenates two Ropes

head :: Rope -> Word8

O(log n) First element of the Rope. Raises an error if the argument is empty.

uncons :: Rope -> Maybe (Word8, Rope)

O(log n). Returns the first element of the Rope, and the Rope of the remaining elements.

last :: Rope -> Word8

O(log n). Last element of a Rope.

tail :: Rope -> Rope

O(log n) The elements after the head. An error is raised if the Rope is empty.

init :: Rope -> Rope

O(log n) The elements in the Rope except the last one.

null :: Rope -> Bool

O(1) Tests whether a Rope is empty.

length :: Rope -> Int

O(1) Length of a Rope.

Transforming Ropes

map :: (Word8 -> Word8) -> Rope -> Rope

O(n). map f r applies f on each element of r and returns the concatenation of the result.

reverse :: Rope -> Rope

O(n) efficient way to reverse a Rope.

intercalate :: Rope -> [Rope] -> Rope

O(n) intercalate an element between each element of the list of Ropes and concatenates the result.

Concatenations

insert :: Rope -> Int -> Rope -> Rope

O(log n) insert a i b inserts Rope a in Rope b after the ith element of b.

Reducing Ropes

foldl :: (a -> Word8 -> a) -> a -> Rope -> a

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.

foldr :: (Word8 -> a -> a) -> a -> Rope -> a

O(n). Right fold. Again not tail-recursive but never uses more than O(log n) on the stack.

Breaking Ropes

take :: Int -> Rope -> Rope

drop :: Int -> Rope -> Rope

splitAt# :: Int -> Rope -> (#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.

breakByte :: Word8 -> Rope -> (Rope, Rope)

O(n). breakByte c r breaks Rope r before the first occurence of c.

breaks :: Word8 -> 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.

lines :: Rope -> [Rope]

O(n). Satisfies lines r == breaks 0x0a r.

Indexing Ropes

index :: Rope -> Int -> Char

O(log n) returns the Word8 at given index in the Rope

elemIndex :: Word8 -> Rope -> Maybe Int

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.

elemIndices :: Word8 -> Rope -> [Int]

O(n) returns the list of all positions where the queried elements occurs in the Rope. This implementation uses memchr.

Input and Output

readFile :: FilePath -> IO Rope

Lazy file reading, using mmap.

hGet :: Handle -> Int -> IO Rope

Strict hGet. The whole rope is constructed.

hGetLine :: Handle -> 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.

hGetContents :: Handle -> IO Rope

Reads the contents of a file handle strictly, then closes it.

hPut :: Handle -> Rope -> IO ()

Writes the contents of the Rope on the specified Handle.

hPutStrLn :: Handle -> Rope -> IO ()

like hPut, but with a newline character at the end of the output

hPutStr :: Handle -> Rope -> IO ()

synonym for hPut.

putStrLn :: Rope -> IO ()

like putStr but with a newline character at the end of the output

putStr :: Rope -> IO ()

Writes the contents of the Rope on the standard output.