Module lines

Efficient array of lines

This module implements an efficient array of lines (e.g. for text editor.) It allows for append, as well as insert, replace, delete in any position with reasonable access times.

Rough benchmarking indicates (on a 440MHz Ultra):

NoOfLines Append (uSec) Read (uSec) Delete (uSec)
100 9 7 7
1,000 14 10 11
10,000 22 13 15
100,000 30 16 18

Comment on the benchmark: The times for Append and Delete are mean times for "growing file" and "shrinking file", that is, starting from an empty array and inserting 100,000 lines took ca 3 seconds; deleting them took ca 1.8 seconds. The Read test involved accessing all lines in the full array and calculating the mean time.

There is also a function, new/[1,2] to create an array of a given size with default content. This function is much more efficient than growing the array from scratch. For example, creating an array of 100,000 elements using new(100000, []) took ca 12 ms on the same Ultra. One may compare this to the built-in function erlang:make_tuple/2, with which the corresponding operation (erlang:make_tuple(100000,[]) took ca 5 ms. Of course, appending an element to a tuple of size 100,000 then takes ca 6 ms, whereas append on the lines array takes 30 usec.

The array doesn't care what goes into each position. In other words, it can be used for any datatype -- not just lines of text.

.

Authors: Ulf Wiger, (ulf.wiger@ericsson.com).

Description

Efficient array of lines

This module implements an efficient array of lines (e.g. for text editor.) It allows for append, as well as insert, replace, delete in any position with reasonable access times.

Rough benchmarking indicates (on a 440MHz Ultra):

NoOfLines Append (uSec) Read (uSec) Delete (uSec)
100 9 7 7
1,000 14 10 11
10,000 22 13 15
100,000 30 16 18

Comment on the benchmark: The times for Append and Delete are mean times for "growing file" and "shrinking file", that is, starting from an empty array and inserting 100,000 lines took ca 3 seconds; deleting them took ca 1.8 seconds. The Read test involved accessing all lines in the full array and calculating the mean time.

There is also a function, new/[1,2] to create an array of a given size with default content. This function is much more efficient than growing the array from scratch. For example, creating an array of 100,000 elements using new(100000, []) took ca 12 ms on the same Ultra. One may compare this to the built-in function erlang:make_tuple/2, with which the corresponding operation (erlang:make_tuple(100000,[]) took ca 5 ms. Of course, appending an element to a tuple of size 100,000 then takes ca 6 ms, whereas append on the lines array takes 30 usec.

The array doesn't care what goes into each position. In other words, it can be used for any datatype -- not just lines of text.

Data Types

line()

line() = term()

Typically a string, but could be anything really.

line_array()

line_array() = tuple()

A 10-ary balanced tree.

Function Index

append/2Appends Line to the end of Array.
convert_from_list/1Converts a list of "lines" to an array.
convert_to_list/1Converts an array to a list of lines.
count/1Returns the number of lines stored in the array.
delete/2Deletes the line in position LineNo.
insert/3Inserts NewLine *before* the line in position LineNo.
insert_after/3Inserts NewLine *after* the line in position LineNo (LineNo > 0).
new/0Creates a new line array.
new/1

Equivalent to new(N, []).

new/2Make an array of N lines.
nth/2Returns the line in position LineNo.
replace/3Replaces the line in position LineNo with NewLine.

Function Details

append/2

append(Line::line(), Array::line_array()) -> line_array()

Appends Line to the end of Array.

e.g. append(x, [1,2,3,4]) => [1,2,3,4,x].

Returns the modified array.

convert_from_list/1

convert_from_list(L::list()) -> line_array()

Converts a list of "lines" to an array.

This is done in an efficient manner.

convert_to_list/1

convert_to_list(X1::line_array()) -> list()

Converts an array to a list of lines.

count/1

count(Array::line_array()) -> integer()

Returns the number of lines stored in the array

delete/2

delete(LineNo::integer(), Array::line_array()) -> line_array()

Deletes the line in position LineNo.

e.g. delete(3, [1,2,3,4]) => [1,2,4].

Returns the modified array.

insert/3

insert(LineNo::integer(), Array::line_array(), NewLine::line()) -> line_array()

Inserts NewLine *before* the line in position LineNo.

e.g. insert(3, [1,2,3,4], x) => [1,2,x,3,4].

Returns the modified array.

insert_after/3

insert_after(LineNo::integer(), Array::line_array(), NewLine::line()) -> line_array()

Inserts NewLine *after* the line in position LineNo (LineNo > 0).

e.g. insert(3, [1,2,3,4], x) => [1,2,3,x,4].

Returns the modified array.

new/0

new() -> line_array()

Creates a new line array.

new/1

new(N) -> term()

Equivalent to new(N, []).

new/2

new(N::integer(), DefaultLine::term()) -> line_array()

Make an array of N lines. Each line will be initialized to DefaultLine.

This is _much_ faster and more space efficient than growing an array line by line.

nth/2

nth(LineNo::integer(), Array::line_array()) -> line()

Returns the line in position LineNo

replace/3

replace(LineNo::integer(), Array::line_array(), NewLine::line()) -> line_array()

Replaces the line in position LineNo with NewLine.

e.g. replace(3, [1,2,3,4], x) => [1,2,x,4].

Returns the modified array.