Module type Sek.ITER_EPHEMERAL
The signature ITER_EPHEMERAL
extends the iterator API with concepts and operations that exist only in the case of iterators over ephemeral sequences. Please follow the link for details.
include ITER
Types
type 'a iter
'a iter
is the type of an iterator. If the sequence has n elements, then an iterator can be thought of as an integer index that lies in the closed interval[-1, n]
. The special indices-1
andn
designate the two sentinel elements, while the ordinary indices in the semi-open interval[0, n)
designate the actual elements of the sequence.
Creation Operations
val create : direction -> 'a t -> 'a iter
create forward s
creates an iterator that points to index0
. This means that the iterator points to the first element of the sequence, if the sequence is nonempty, and points to the back sentinel if the sequence is empty. Symmetrically,create backward s
creates an iterator that points to indexn-1
, wheren
is the length of the sequence. This means that the iterator points to the last element of the sequence, if the sequence is nonempty, and points to the front sentinel if the sequence is empty.Time complexity: O(1).
val reset : direction -> 'a iter -> unit
reset dir it
resets the iteratorit
to the same initial state that is established when a new iterator is created bycreate dir (sequence it)
. Thus,reset forward it
is equivalent toreach it 0
, andreset backward it
is equivalent toreach it (length it - 1)
.Time complexity: O(1).
Accessors
val sequence : 'a iter -> 'a t
sequence it
is the sequence that the iteratorit
navigates. Throughout its lifetime, an iterator remains attached to the same sequence.Time complexity: O(1).
val length : 'a iter -> length
length it
is the length of the sequence that the iteratorit
navigates. It is a short-hand forlength (sequence it)
.Time complexity: O(1).
val index : 'a iter -> index
index it
is the index that the iteratorit
currently points to. It lies in the closed interval[-1, length it]
. The special indices-1
andn
designate the two sentinel elements, while the ordinary indices in the semi-open interval[0, n)
designate the actual elements of the sequence.Time complexity: O(1).
val finished : 'a iter -> bool
finished it
tests whether the iteratorit
currently points to the front or back sentinel. Thus,finished it
is equivalent toindex it = -1 || index it = length it
. Its use is recommended, as it is both more readable and more efficient than testing a condition based onindex it
. The conditionnot (finished it)
corresponds toit.hasNext()
in Java's iterator API.Time complexity: O(1).
Read Operations
val get : 'a iter -> 'a
If
finished it
isfalse
, thenget it
reads and returns the element that the iteratorit
currently points to, that is, the element at indexindex it
. In that case,get it
is equivalent to accessing the sequence viaget (sequence it) (index it)
, yet is much cheaper. Iffinished it
istrue
, which means that the iterator points to a sentinel, thenget it
raises the exceptionEnd
.Time complexity: O(1).
val get_opt : 'a iter -> 'a option
get_opt it
is analogous toget it
, but returns an option instead of possibly raising the exceptionEnd
. It is equivalent toif finished it then None else Some (get it)
.Time complexity: O(1).
val get_segment : direction -> 'a iter -> 'a segment
If
finished it
isfalse
, thenget_segment dir it
returns a nonempty array segment, which contains a range of sequence elements. An array segment is a triple(a, j, k)
, wherea
is an array,j
is the start index of the segment in the arraya
, andk
is the length of the segment.k
must be positive. The segment covers the array indices in the semi-open interval[j, j + k)
. You are allowed to read this array segment. You are not allowed to modify the arraya
in any way.- If
dir
isforward
, then the array elementa.(j)
is the current element, that is, the element that would be returned byget it
. It is the first element of the segment. The last element of the segment isa.(j + k - 1)
. A loop of the formfor j = j to j + k - 1
can be used to enumerate these elements in the forward direction.
- If
dir
isbackward
, then the array elementa.(j + k - 1)
is the current element, that is, the element that would be returned byget it
. It is the first element of the segment. The last element of the segment isa.(j)
. A loop of the formfor j = j + k - 1 downto j
can be used to enumerate these elements in the backward direction.
If
finished it
istrue
, which means that the iterator points to a sentinel, thenget_segment dir it
raises the exceptionEnd
.Time complexity: O(1).
- If
Move Operations
val move : direction -> 'a iter -> unit
move dir it
moves the iteratorit
by one element in the directiondir
. An attempt to move the iterator forward when it already points to the back sentinel, or to move it backward when it already points to the front sentinel, is forbidden: in such a situation,move
must not be called. In other words, the new indexindex it + sign dir
must lie in the closed interval[-1, length it]
.Time complexity: O(log n) in the worst case. However, the amortized time complexity of
move
is only O(1), in the following sense: the cost of iterating over a sequence using n successivemove
operations is O(n).
val jump : direction -> 'a iter -> length -> unit
jump dir it k
moves the iteratorit
byk
elements in the directiondir
. The value ofk
may be positive, null, or negative. The new indexindex it + sign dir * k
must lie in the closed interval[-1, length it]
. Whenk
is positive,jump dir it k
is equivalent to a series ofk
calls tomove dir it
. Whenk
is negative,jump dir it k
is equivalent to a series ofk
calls tomove (opposite dir) it
. The operationjump dir it 0
has no effect.Time complexity: O(log n). In the particular where
abs k = 1
,jump
is optimized usingmove
.
val reach : 'a iter -> index -> unit
reach it i
moves the iteratorit
so as to point to the element at indexi
. Thus, after this operation,index it
isi
. The indexi
must lie in the closed interval[-1, length it]
.Time complexity: O(log n). In the particular case where
i = -1
ori = length it
,reach
is optimized and its complexity is O(1). In the particular case where one moves to the next or previous item,reach
is optimized usingmove
.
Read-and-Move Operations
val get_and_move : direction -> 'a iter -> 'a
get_and_move
combinesget
andmove
.get_and_move dir it
is equivalent tolet x = get it in move dir it; x
. Therefore, it raises the exceptionEnd
if (before the move) the iterator points to a sentinel. It corresponds toit.next()
in Java's iterator API.Time complexity: same as
move
.
val get_and_move_opt : direction -> 'a iter -> 'a option
get_and_move_opt dir it
is analogous toget_and_move dir it
, but returns an option instead of possibly raising the exceptionEnd
. It is equivalent toif finished it then None else Some (get_and_move it)
.Time complexity: same as
move
.
val get_segment_and_jump : direction -> 'a iter -> 'a segment
get_segment_and_jump
combinesget_segment
and ajump
of the length of the segment.get_segment_and_jump dir it
is equivalent tolet (_, _, k) as seg = get_segment dir it in jump dir it k; seg
. Therefore, it raises the exceptionEnd
if (before the move) the iterator points to a sentinel.Time complexity: same as
jump
. Furthermore, the total cost of iterating over a sequence of n elements usingget_segment_and_jump
is O(n/K).
val get_segment_and_jump_opt : direction -> 'a iter -> 'a segment option
get_segment_and_jump_opt dir it
is analogous toget_segment_and_jump dir it
, but returns an option instead of possibly raising the exceptionEnd
. It is equivalent toif finished it then None else Some (get_segment_and_jump dir it)
.Time complexity: same as
get_segment_and_jump
.
Miscellaneous Operations
val check : 'a iter -> unit
In a release build,
check it
does nothing. In a development build, it checks that the iterator's internal invariant is satisfied.
val format : Stdlib.Format.formatter -> int iter -> unit
format
is a printer for iterators over sequences of integers. It can be installed in the OCaml toplevel loop by#install_printer format
. It is intended to be used only while debugging the library.
Iterator Invalidation
Operations that Invalidate Iterators
As a general rule, every operation that modifies an ephemeral sequence invalidates all iterators associated with this sequence.
We do not give an exhaustive list of these operations. Among the core operations, the following operations are in this category:
E.push
,E.pop
,E.clear
,E.assign
,snapshot_and_clear
,E.set
,E.concat
,E.append
,E.split
,E.carve
,E.take
,E.drop
.
As an exception, E.assign s s
has no effect, therefore does not invalidate any iterators.
As a more interesting exception, the operation E.Iter.set it
invalidates all iterators on the sequence E.Iter.sequence it
, except the iterator it
itself, which remains valid.
If finished it
is true
, then E.Iter.set it
raises End
and does not invalidate any iterators.
The operations E.Iter.get_writable_segment
, E.Iter.get_writable_segment_opt
, E.Iter.set_and_move
, E.Iter.get_writable_segment_and_jump
, E.Iter.get_writable_segment_and_jump_opt
, behave in the same way as E.Iter.set
.
Operations that Can Be Applied to an Invalid Iterator
As a general rule, no operations can be applied to an invalid iterator.
As an exception to this rule, the following operations can be applied to an invalid iterator:
E.Iter.sequence
;E.Iter.is_valid
;E.Iter.reset
, with the effect of making this iterator valid again.
Runtime Detection of Illegal Operations on Iterators
An attempt to apply an operation other than those listed above to an invalid iterator is illegal.
If the flag check_iterator_validity
is enabled (which it is, by default), then such an attempt is detected at runtime and gives rise to a runtime error.
For the same reason, if the flag check_iterator_validity
is enabled, then an attempt to modify an ephemeral sequence while a higher-order iteration function (such as E.iter
, E.fold_left
, etc.) is running is detected at runtime and gives rise to a runtime error.
val is_valid : 'a iter -> bool
When the flag
check_iterator_validity
is enabled (which it is, by default), it is possible to test, at runtime, whether an iterator is currently valid. When the flagcheck_iterator_validity
isfalse
, it is impossible to determine at runtime whether an iterator is valid; in that case,is_valid
always returnstrue
.Time complexity: O(1).
Write Operations
val set : 'a iter -> 'a -> unit
If
finished it
isfalse
, thenset it x
replaces the element currently pointed to by the iteratorit
with the elementx
. In this case,set it x
is equivalent to accessing the sequence viaset (sequence it) (index it) x
, yet is much cheaper. Iffinished it
istrue
, then the exceptionEnd
is raised.Time complexity: if the
set
operation hits a chunk that is marked as potentially shared with other sequences, then its complexity is O(K + log n), and this chunk is replaced in the process with one that is not shared with any other sequence. Otherwise, the complexity is O(1).
val get_writable_segment : direction -> 'a iter -> 'a segment
If
finished it
isfalse
, thenget_writable_segment dir it
returns a nonempty array segment(a, j, k)
, which contains a range of sequence elements. The iterator must not point to a sentinel; that is,finished it
must befalse
. Please see the documentation ofget_segment
for a detailed description of the array segment. In the case ofget_writable_segment
, you are allowed to read and write this array segment. You are not allowed to modify the arraya
outside of the semi-open interval[j, j + k)
.If
finished it
istrue
, which means that the iterator points to a sentinel, thenget_writable_segment dir it
raises the exceptionEnd
.Time complexity: same as
set
.
val get_writable_segment_opt : direction -> 'a iter -> 'a segment option
get_writable_segment_opt dir it
is analogous toget_writable_segment dir it
, but returns an option instead of possibly raising the exceptionEnd
. It is equivalent toif finished it then None else Some (get_writable_segment dir it)
.Time complexity: same as
set
.
Write-and-Move Operations
val set_and_move : direction -> 'a iter -> 'a -> unit
set_and_move direction it x
is equivalent toset it x; move direction it
.Time complexity: same as
set
followed withmove
.
val get_writable_segment_and_jump : direction -> 'a iter -> 'a segment
get_writable_segment_and_jump
combinesget_writable_segment
and ajump
of the length of the segment.get_writable_segment_and_jump dir it
is equivalent tolet (_, _, k) as seg = get_writable_segment dir it in jump dir it k; seg
. The iterator must not point to a sentinel; that is,finished it
must befalse
.Time complexity: same as
set
followed withjump
. The total cost of iterating over a sequence of n elements usingget_writable_segment_and_jump
is O(n) in the worst case, and O(n/K) if no shared chunk is encountered.
val get_writable_segment_and_jump_opt : direction -> 'a iter -> 'a segment option
get_writable_segment_and_jump_opt dir it
is analogous toget_writable_segment_and_jump dir it
, but returns an option instead of possibly raising the exceptionEnd
. It is equivalent toif finished it then None else Some (get_writable_segment_and_jump dir it)
.Time complexity: same as
get_writable_segment_and_jump
.