Indexed sequence ADT

[Jiri Svoboda]

A sequence (list) is an ordered collection of elements. The elements have no keys, just values. Sequences can be split at any element, concatenated, new element can be prepended/appended.

An indexed sequence also allows to find an element efficiently by its index (numerical position) in the sequence and, conversely, to obtain the index of an element.

A weighed indexed sequence also assigns (non-negative) weight (or width) to each element, in which case for indexing purposes an element counts as much as its weight/width is.

Implement a weighed indexed sequence ADT in HelenOS libc.

A weighed indexed sequence can be efficiently implemented as slightly modified self-balancing search tree. The handling of the keys is slightly different and the algorithm needs to keep track of weights of subtrees during the rotations.

Indexed sequences and weighed indexes sequences are useful for destructive sequence editors, such as:

• text/file editors
• audio editors
• accessing characters UTF-8 strings by character index

Intended use: The current sheet implementation in the text editor is inefficient for larger files. It could be easily re-implemented as an indexed sequence of lines. Then it would work well for files with large number of lines (although not for files with very few very long lines).

[Jakub Jermář]

Is this the odict.[ch]?

[Jiri Svoboda]

No, that's just an ordered dictionary. Indexed sequence could be implemented as an extension to odict. It's on my TODO list.