Module Persistent.Iter
The submodule Iter
offers an implementation of iterators on persistent sequences.
Overview
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.