dlist

List data structure based on AVL tree. It can store elements which have dimension and quickly search for elements by distance from 0. The list mutations and indexing are O(logN).

Use cases

Text Editors

DList can be used to split text data into lines and calculate line/column numbers based on absolute file offset: ```rust struct FileSliceMeasurer;

struct FileSlice { length: usize, }

impl Measurer for FileSliceMeasurer { type Measure = usize; fn nil(&self) -> usize { 0 }

fn measure(&self, value: &FileSlice) -> usize {
    value.length
}

}

let mut dlist = DList::new(FileSliceMeasurer);

let line_lengths: Vec = ... // let's say we have parsed some text file and now have a vector containing the length of each line (in bytes)

for i in 0..linelengths.len() { dlist.append(FileSlice { length: linelengths[i] }); }

let lineinfo = dl.getbyindex(100).unwrap(); asserteq!(lineinfo.index, 100); // a line index. Since we use getbyindex(n), it should always be equal to n. asserteq!(lineinfo.item.length, 50); // in this case an item is of type FileSlice and contains the length of the text line. asserteq!(lineinfo.outerdistance, 1000); // an absolute file offset of the first character in the line. asserteq!(lineinfo.innerdistance, 0); // always 0 for getby_index

let lineinfo = dl.getbydistance(10000).unwrap(); asserteq!(lineinfo.index, 100); // a zero-based line index for the distance (i.e. file offset). asserteq!(lineinfo.item.length, 50); // a FileSlice containing the length of the line which contains this distance. asserteq!(lineinfo.outerdistance, 1000); // an absolute file offset of the first character in the line. asserteq!(lineinfo.inner_distance, 34); // an offset inside the slice, i.e. zero-based column offset.

```