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).
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.
line() = term()
Typically a string, but could be anything really.
line_array() = tuple()
A 10-ary balanced tree.
append/2 | Appends Line to the end of Array. |
convert_from_list/1 | Converts a list of "lines" to an array. |
convert_to_list/1 | Converts an array to a list of lines. |
count/1 | Returns the number of lines stored in the array. |
delete/2 | Deletes the line in position LineNo. |
insert/3 | Inserts NewLine *before* the line in position LineNo. |
insert_after/3 | Inserts NewLine *after* the line in position LineNo
(LineNo > 0 ). |
new/0 | Creates a new line array. |
new/1 | Equivalent to new(N, []). |
new/2 | Make an array of N lines. |
nth/2 | Returns the line in position LineNo. |
replace/3 | Replaces the line in position LineNo with NewLine. |
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(L::list()) -> line_array()
Converts a list of "lines" to an array.
This is done in an efficient manner.
convert_to_list(X1::line_array()) -> list()
Converts an array to a list of lines.
count(Array::line_array()) -> integer()
Returns the number of lines stored in the array
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(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(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() -> line_array()
Creates a new line array.
Equivalent to new(N, []).
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(LineNo::integer(), Array::line_array()) -> line()
Returns the line in position LineNo
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.