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).

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.

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.