Reference » Collections and iterators » MWidthList

Elgrint::MWidthList<T> class

Declared in MWidthList.h

Description

Linear ordered collection of abstract "widths" with O(lgn) insert/remove complexity.
Read more...

MWidthList

Base class: Collection

Template parameters:

Name Description
T

The type of any element (a "width" section) in MWidthList.

Details: Represents both the "width" value of a single section and the "sum of widths" coordinate value. Must support a public copy constructor (default constructor is optional), a public destructor, a self-consistent binary operator+, and binary operator< (for comparison of "widths"). Also, it must support a binary operator> whose right operand is the constant 0 (of type int). This is needed for safety, to ensure that "widths", whatever they are, are indeed "positive". A value is defined as "positive", if adding it to another value doesn't decrease that value. In other words, x is positive iff y <= x+y (recall that operator+ and operator< are already defined for T). Note that this doesn't correspond exactly to the mathematical definition of a positive value.

Classes:

Name Description
CIter Constant iterator of MWidthList.

Initializers:

Name Description
MWidthList(coll) Conversion constructor. Converts any compatible collection to MWidthList.

Mutators:

Name Description
insert(atWidth,widths,iFirst,iLast,IRE) Inserts all positive elements in the widths vector from iFirst to iLast to this list, starting at coordinate atWidth.
insert(atWidth,newWidth,IRE) Inserts a positive newWidth at coordinate atWidth in O(lgn) time complexity.
insert(atWidth,widths,IRE) Inserts all positive elements in the widths vector to this list, starting at coordinate atWidth.
remove(wFirst,wLast,IRE) Removes all sections, which contain at least one point within the [wFirst..wLast] coordinate range in O(nlgn) complexity.
remove(atWidth,IRE) Removes a section at coordinate atWidth in O(lgn) time).
set(atWidth,newWidth,IRE) Changes the width of a section at coordinate atWidth to newWidth in O(lgn) complexity.

Revealers:

Name Description
getTotalWidth() Returns the sum of all widths in this list in O(1) time complexity.
getWidth(atWidth,IRE) Returns the width of the section, which is located at coordinate atWidth in O(lgn) time complexity.
getWidthSum(atWidth,IRE) Returns the sum of widths of all sections until the one that contains the atWidth coordinate in O(lgn) time complexity.

Details

MWidthList is the most powerful and versatile collection in Elgrint, even if it is also the most complicated one and is somewhat tricky to use. It is an implementation of a skip-list data structure, which provides logarithmic complexity on insertion, removal, and search operations.

In more abstract terms, however, MWidthList is defined as a linear sequence (a line) of adjacent sections, and each section has a positive "width" value attached to it. These sections are the list's elements. The collection allows inserting, removing, and locating these sections anywhere in the collection at logarithmic complexity, doesn't seem to be as good as the O(1) complexity of MVector and MHash. However, unlike MVector, the width list bases these operations not on the section's index, but on its "coordinate", which is equal to the sum of widths of all preceding sections. The big advantage of the width list is that it can calculate the "sum" of any number of segment "widths" in logarithmic time. In other words, it can calculate the sum of n numbers in O(lgn) time (of course, these numbers have to be properly prepared first, and that would take O(nlgn) time, so no miracles here). Any other collection would require a linear complexity for such an operation. Thus, the width list can solve certain problems more efficiently (by far) than any other collection.

At first glance, the width list seems like a limited collection, designed for some specific purpose (adding section widths), but in fact it is highly versatile, because a "width" doesn't have to be a number, and the "sum of widths" doesn't have to follow the same logic as the numeric addition.

For example, T can be a generic value, whose "width" is always 1. In this case, section coordinate (sum of widths) is equal to its index in the list. With such a definition, the width list becomes similar to MVector, except that it can insert/remove items at any position with logarithmic complexity, whereas MVector requires linear complexity (except when inserting/removing at the end of the list). In fact, this principle is used to implement the MList collection.

A more interesting example is to redefine the addition as follows: a+b = Max(a,b). With such a definition, a section's coordinate is equal to its value, so inserting a value to its own coordinate results in a list, which is automatically sorted in ascending order. In fact, this principle is used to implement the MSortList collection.

Such versatility comes with a price, however. If operators of the T type are defined improperly, then the width list can produce unexpected and illogical results. Therefore, it is recommended to use MList and MSortList (which cover the most popular usages of a skip-list), instead of using the width list directly, unless you know exactly what you're doing.

'MWidthList' is used directly (and to its full potential) in MEditBox. It is the power of the width list that makes the edit box as efficient as it is.

One more interesting fact about the width list - any collection that supports the Elgrint-like constant iterator (see Collection::CIter) can be converted to MWidthList in a single statement using the MWidthList(C) constructor template. This can work even if the source collection's items have a different (but compatible) type.

Let us know

Please Contact us to report any errors on this page, or to suggest any improvements.

Miranor Home | About Miranor | About Elgrint | Create account | Login | Account settings | Contact Us | Privacy Policy | Site map

© Copyright 2014 by Miranor. All rights reserved. By using this site you agree to the Terms of Use.

Page last updated on August 10th, 2014.