Sequences
scalable lists
The #GSequence data structure has the API of a list, but is
implemented internally with a balanced binary tree. This means that it
is possible to maintain a sorted list of n elements in time O(n log
n). The data contained in each element can be either integer values, by
using of the
Type Conversion Macros,
or simply pointers to any type of data.
A #GSequence is accessed through iterators,
represented by a #GSequenceIter. An iterator represents a position
between two elements of the sequence. For example, the
begin iterator represents the gap immediately
before the first element of the sequence, and the
end iterator represents the gap immediately
after the last element. In an empty sequence, the begin and end
iterators are the same.
Some methods on #GSequence operate on ranges of items. For example
g_sequence_foreach_range() will call a user-specified function on each
element with the given range. The range is delimited by the gaps
represented by the passed-in iterators, so if you pass in the begin
and end iterators, the range in question is the entire sequence.
The function g_sequence_get() is used with an iterator to access the
element immediately following the gap that the iterator
represents. The iterator is said to point to
that element.
Iterators are stable across most operations on a #GSequence. For
example an iterator pointing to some element of a sequence will
continue to point to that element even after the sequence is
sorted. Even moving an element to another sequence using for example
g_sequence_move_range() will not invalidate the iterators pointing to
it. The only operation that will invalidate an iterator is when the
element it points to is removed from any sequence.
The GSequence struct is an opaque data type
representing a Sequence data type.
The GSequenceIter struct is an opaque data
type representing an iterator pointing into a #GSequence.
A #GSequenceIterCompareFunc is a function used to compare
iterators. It must return zero if the iterators compare equal, a
negative value if @a comes before @b, and a positive value if @b comes
before @a.
@a: a #GSequenceIter
@b: a #GSequenceIter
@data: user data
@Returns: zero if the iterators are equal, a negative value if @a
comes before @b, and a positive value if @b comes before @a.
@data_destroy:
@Returns:
@seq:
@seq:
@Returns:
@seq:
@func:
@user_data:
@begin:
@end:
@func:
@user_data:
@seq:
@cmp_func:
@cmp_data:
@seq:
@cmp_func:
@cmp_data:
@seq:
@Returns:
@seq:
@Returns:
@seq:
@pos:
@Returns:
@seq:
@data:
@Returns:
@seq:
@data:
@Returns:
@iter:
@data:
@Returns:
@src:
@dest:
@a:
@b:
@seq:
@data:
@cmp_func:
@cmp_data:
@Returns:
@seq:
@data:
@iter_cmp:
@cmp_data:
@Returns:
@iter:
@cmp_func:
@cmp_data:
@iter:
@iter_cmp:
@cmp_data:
@iter:
@begin:
@end:
@dest:
@begin:
@end:
@seq:
@data:
@cmp_func:
@cmp_data:
@Returns:
@seq:
@data:
@iter_cmp:
@cmp_data:
@Returns:
@iter:
@Returns:
@iter:
@data:
@iter:
@Returns:
@iter:
@Returns:
@iter:
@Returns:
@iter:
@Returns:
@iter:
@Returns:
@iter:
@delta:
@Returns:
@iter:
@Returns:
@a:
@b:
@Returns:
@begin:
@end:
@Returns: