id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	field_blocks	field_dependson	field_seealso
438	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).
"	enhancement	new	minor		helenos/unspecified	mainline