SkipList Library: Reverse Arbitrary Access Iterator LOGN

Category: iterators
Component type: concept

Description

A Reverse Arbitrary Access Iterator is an iterator that provides logarithmic-time methods for moving backward in arbitrary-sized steps.

Nothing is determined for decrementing (incrementing is constant-time). However, a Reverse Arbitrary Access Iterator LOGN should also be derived from either a Bidirectional Iterator or a Bidirectional Iterator LOGN.

Refinement of

LessThan Comparable, Bidirectional Iterator OR Bidirectional Iterator LOGN

Associated types

The same as for Bidirectional Iterator or Bidirectional Iterator LOGN

Notation

`X`	A type that is a model of Reverse Arbitrary Access Iterator LOGN
`T`	The value type of `X`
`Distance`	The distance type of `X`
`i`, `j`	Object of type `X`
`t`	Object of type `T`
`n`	Object of type `Distance`

Definitions

Valid expressions

In addition to the expressions defined in Bidirectional Iterator or Bidirectional Iterator, the following expressions must be valid.

Name	Expression	Return type
Iterator subtraction	`i -= n`	`X&`
Iterator subtraction	`i - n`	`X`
Difference	`i - j`	`Distance`

Expression semantics

Semantics of an expression is defined only where it differs from, or is not defined in, Bidirectional Iterator, Bidirectional Iterator LOGN or LessThan Comparable.

Name	Expression	Precondition	Semantics	Postcondition
Iterator subtraction	`i -= n`	Including `i` itself, there must be `n` dereferenceable or past-the-end iterators preceding or following `i`, depending on whether `n` is positive or negative. (n <= 0).		`i` is dereferenceable or past-the-end.
Iterator subtraction	`i - n`	Same as for `i -= n`	Equivalent to `{ X tmp = i; return tmp -= n; }`.	Result is dereferenceable or past-the-end
Difference	`i - j`	Either `i` is reachable from `j` or `j` is reachable from `i`, or both.	Returns a number `n` such that `i == j + n`
Less	`i < j`	Either `i` is reachable from `j` or `j` is reachable from `i`, or both. [1]	As described in LessThan Comparable [2]

Complexity guarantees

Incrementing is done in amortized constant time.
Decrementing is done in at most amortized logarithmic time and is determined if the iterator is derived from Bidirectional Iterator (constant-time) or Bidirectional Iterator LOGN (logarithmmic-time).
Moving backward by arbitrary-sized steps is done in at most amortized logarithmic time. [3]

Invariants

Symmetry of addition and subtraction	If `i + n` is well-defined, then `i += n; i -= n;` and `(i + n) - n` are null operations. Similarly, if `i - n` is well-defined, then `i -= n; i += n;` and `(i - n) + n` are null operations.
Relation between distance and addition	If `i - j` is well-defined, then `i == j + (i - j)`.
Reachability and distance	If `i` is reachable from `j`, then `i - j >= 0`.
Ordering	`operator <` is a strict weak ordering, as defined in LessThan Comparable.

Models

Notes

[1] The precondition defined in LessThan Comparable is that i and j be in the domain of operator <. Essentially, then, this is a definition of that domain: it is the set of pairs of iterators such that one iterator is reachable from the other.

[2] All of the other comparison operators have the same domain and are defined in terms of operator <, so they have exactly the same semantics as described in LessThan Comparable.

[3] This complexity guarantee is in fact the only reason why Reverse Arbitrary Iterator LOGN exists as a distinct concept. Every operation in iterator arithmetic can be defined for Bidirectional Iterator or Bidirectional Iterator LOGN; in fact, that is exactly what the algorithms advance and distance do. The distinction is simply that the Bidirectional Iterator and Bidirectional Iterator LOGN implementations are linear time and nlogn time respectively, while Reverse Arbitrary Iterators LOGN are required to support random access to elements in amortized logarithmic time. This has major implications for the sorts of algorithms that can sensibly be written using the two types of iterators.

AutoSkipList, AutoSSkipList, AutoKeyedSkipList, AutoKeyedSSkipList, MultiAutoSkipList, MultiAutoSSkipList, MultiAutoKeyedSkipList, MultiAutoKeyedSSkipList, IndexedSkipList, IndexedSSkipList, IndexedTinySkipList, XIndexedSkipList, XMultiAutoSkipList, AutoAccessSkipList, AutoAccessSSkipList, MultiAutoAccessSkipList, MultiAutoAccessSSkipList, XMultiAutoAccessSkipList,

LessThan Comparable, Trivial Iterator, Bidirectional Iterator, Iterator Overview, Sequence, LessThan Comparable, Trivial Iterator, Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Bidirectional Iterator LOGN, Forward Arbitrary Access Container, Forward Arbitrary Access Iterator Forward Arbitrary Access Container LOGN, Forward Arbitrary Access Iterator LOGN, Reverse Arbitrary Access Container, Reverse Arbitrary Access Iterator, Reverse Arbitrary Access Container LOGN, Random Access Container, Random Access Iterator, Random Access Container LOGN, Random Access Iterator LOGN, Arbitrary Access Container LOGN, Arbitrary Access Iterator LOGN

Reverse Arbitrary Access Iterator LOGN