| Top | |
|
|
|
The GSequence data structure has the API of a list, but is implemented internally with a balanced binary tree. This means that most of the operations (access, search, insertion, deletion, ...) on GSequence are O(log(n)) in average and O(n) in worst case for time complexity. But, note that maintaining a balanced sorted list of n elements is done 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.
To sort the data, either use g_sequence_insert_sorted() or
g_sequence_insert_sorted_iter() to add data to the GSequence or, if
you want to add a large amount of data, it is more efficient to call
g_sequence_sort() or g_sequence_sort_iter() after doing unsorted
insertions.
gint (*GSequenceIterCompareFunc) (GSequenceIter *a,GSequenceIter *b,gpointer user_data);
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
.
GSequence *
g_sequence_new (GDestroyNotify data_destroy);
Creates a new GSequence. The data_destroy
function, if non-NULL will
be called on all items when the sequence is destroyed and on items that
are removed from the sequence.
Since: 2.14
void
g_sequence_free (GSequence *seq);
Frees the memory allocated for seq
. If seq
has a data destroy
function associated with it, that function is called on all items
in seq
.
Since: 2.14
gint
g_sequence_get_length (GSequence *seq);
Returns the positive length (>= 0) of seq
. Note that this method is
O(h) where `h' is the height of the tree. It is thus more efficient
to use g_sequence_is_empty() when comparing the length to zero.
Since: 2.14
gboolean
g_sequence_is_empty (GSequence *seq);
Returns TRUE if the sequence contains zero items.
This function is functionally identical to checking the result of
g_sequence_get_length() being equal to zero. However this function is
implemented in O(1) running time.
Since: 2.48
void g_sequence_foreach (GSequence *seq,GFunc func,gpointer user_data);
Calls func
for each item in the sequence passing user_data
to the function. func
must not modify the sequence itself.
Since: 2.14
void g_sequence_foreach_range (GSequenceIter *begin,GSequenceIter *end,GFunc func,gpointer user_data);
Calls func
for each item in the range (begin
, end
) passing
user_data
to the function. func
must not modify the sequence
itself.
Since: 2.14
void g_sequence_sort (GSequence *seq,GCompareDataFunc cmp_func,gpointer cmp_data);
Sorts seq
using cmp_func
.
cmp_func
is passed two items of seq
and should
return 0 if they are equal, a negative value if the
first comes before the second, and a positive value
if the second comes before the first.
seq |
||
cmp_func |
the function used to sort the sequence |
|
cmp_data |
user data passed to |
Since: 2.14
void g_sequence_sort_iter (GSequence *seq,GSequenceIterCompareFunc cmp_func,gpointer cmp_data);
Like g_sequence_sort(), but uses a GSequenceIterCompareFunc instead
of a GCompareDataFunc as the compare function
cmp_func
is called with two iterators pointing into seq
. It should
return 0 if the iterators are equal, a negative value if the first
iterator comes before the second, and a positive value if the second
iterator comes before the first.
seq |
||
cmp_func |
the function used to compare iterators in the sequence |
|
cmp_data |
user data passed to |
Since: 2.14
GSequenceIter *
g_sequence_get_begin_iter (GSequence *seq);
Returns the begin iterator for seq
.
Since: 2.14
GSequenceIter *
g_sequence_get_end_iter (GSequence *seq);
Returns the end iterator for seg
Since: 2.14
GSequenceIter * g_sequence_get_iter_at_pos (GSequence *seq,gint pos);
Returns the iterator at position pos
. If pos
is negative or larger
than the number of items in seq
, the end iterator is returned.
Since: 2.14
GSequenceIter * g_sequence_append (GSequence *seq,gpointer data);
Adds a new item to the end of seq
.
Since: 2.14
GSequenceIter * g_sequence_prepend (GSequence *seq,gpointer data);
Adds a new item to the front of seq
Since: 2.14
GSequenceIter * g_sequence_insert_before (GSequenceIter *iter,gpointer data);
Inserts a new item just before the item pointed to by iter
.
Since: 2.14
void g_sequence_move (GSequenceIter *src,GSequenceIter *dest);
Moves the item pointed to by src
to the position indicated by dest
.
After calling this function dest
will point to the position immediately
after src
. It is allowed for src
and dest
to point into different
sequences.
src |
a GSequenceIter pointing to the item to move |
|
dest |
a GSequenceIter pointing to the position to which the item is moved |
Since: 2.14
void g_sequence_swap (GSequenceIter *a,GSequenceIter *b);
Swaps the items pointed to by a
and b
. It is allowed for a
and b
to point into difference sequences.
Since: 2.14
GSequenceIter * g_sequence_insert_sorted (GSequence *seq,gpointer data,GCompareDataFunc cmp_func,gpointer cmp_data);
Inserts data
into seq
using cmp_func
to determine the new
position. The sequence must already be sorted according to cmp_func
;
otherwise the new position of data
is undefined.
cmp_func
is called with two items of the seq
, and cmp_data
.
It should return 0 if the items are equal, a negative value
if the first item comes before the second, and a positive value
if the second item comes before the first.
Note that when adding a large amount of data to a GSequence,
it is more efficient to do unsorted insertions and then call
g_sequence_sort() or g_sequence_sort_iter().
seq |
||
data |
the data to insert |
|
cmp_func |
the function used to compare items in the sequence |
|
cmp_data |
user data passed to |
Since: 2.14
GSequenceIter * g_sequence_insert_sorted_iter (GSequence *seq,gpointer data,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data);
Like g_sequence_insert_sorted(), but uses
a GSequenceIterCompareFunc instead of a GCompareDataFunc as
the compare function.
iter_cmp
is called with two iterators pointing into seq
.
It should return 0 if the iterators are equal, a negative
value if the first iterator comes before the second, and a
positive value if the second iterator comes before the first.
Note that when adding a large amount of data to a GSequence,
it is more efficient to do unsorted insertions and then call
g_sequence_sort() or g_sequence_sort_iter().
seq |
||
data |
data for the new item |
|
iter_cmp |
the function used to compare iterators in the sequence |
|
cmp_data |
user data passed to |
Since: 2.14
void g_sequence_sort_changed (GSequenceIter *iter,GCompareDataFunc cmp_func,gpointer cmp_data);
Moves the data pointed to by iter
to a new position as indicated by
cmp_func
. This
function should be called for items in a sequence already sorted according
to cmp_func
whenever some aspect of an item changes so that cmp_func
may return different values for that item.
cmp_func
is called with two items of the seq
, and cmp_data
.
It should return 0 if the items are equal, a negative value if
the first item comes before the second, and a positive value if
the second item comes before the first.
iter |
||
cmp_func |
the function used to compare items in the sequence |
|
cmp_data |
user data passed to |
Since: 2.14
void g_sequence_sort_changed_iter (GSequenceIter *iter,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data);
Like g_sequence_sort_changed(), but uses
a GSequenceIterCompareFunc instead of a GCompareDataFunc as
the compare function.
iter_cmp
is called with two iterators pointing into the GSequence that
iter
points into. It should
return 0 if the iterators are equal, a negative value if the first
iterator comes before the second, and a positive value if the second
iterator comes before the first.
iter |
||
iter_cmp |
the function used to compare iterators in the sequence |
|
cmp_data |
user data passed to |
Since: 2.14
void
g_sequence_remove (GSequenceIter *iter);
Removes the item pointed to by iter
. It is an error to pass the
end iterator to this function.
If the sequence has a data destroy function associated with it, this function is called on the data for the removed item.
Since: 2.14
void g_sequence_remove_range (GSequenceIter *begin,GSequenceIter *end);
Removes all items in the (begin
, end
) range.
If the sequence has a data destroy function associated with it, this function is called on the data for the removed items.
Since: 2.14
void g_sequence_move_range (GSequenceIter *dest,GSequenceIter *begin,GSequenceIter *end);
Inserts the (begin
, end
) range at the destination pointed to by dest
.
The begin
and end
iters must point into the same sequence. It is
allowed for dest
to point to a different sequence than the one pointed
into by begin
and end
.
If dest
is NULL, the range indicated by begin
and end
is
removed from the sequence. If dest
points to a place within
the (begin
, end
) range, the range does not move.
Since: 2.14
GSequenceIter * g_sequence_search (GSequence *seq,gpointer data,GCompareDataFunc cmp_func,gpointer cmp_data);
Returns an iterator pointing to the position where data
would
be inserted according to cmp_func
and cmp_data
.
cmp_func
is called with two items of the seq
, and cmp_data
.
It should return 0 if the items are equal, a negative value if
the first item comes before the second, and a positive value if
the second item comes before the first.
If you are simply searching for an existing element of the sequence,
consider using g_sequence_lookup().
This function will fail if the data contained in the sequence is unsorted.
seq |
||
data |
data for the new item |
|
cmp_func |
the function used to compare items in the sequence |
|
cmp_data |
user data passed to |
an GSequenceIter pointing to the position where data
would have been inserted according to cmp_func
and cmp_data
.
[transfer none]
Since: 2.14
GSequenceIter * g_sequence_search_iter (GSequence *seq,gpointer data,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data);
Like g_sequence_search(), but uses a GSequenceIterCompareFunc
instead of a GCompareDataFunc as the compare function.
iter_cmp
is called with two iterators pointing into seq
.
It should return 0 if the iterators are equal, a negative value
if the first iterator comes before the second, and a positive
value if the second iterator comes before the first.
If you are simply searching for an existing element of the sequence,
consider using g_sequence_lookup_iter().
This function will fail if the data contained in the sequence is unsorted.
seq |
||
data |
data for the new item |
|
iter_cmp |
the function used to compare iterators in the sequence |
|
cmp_data |
user data passed to |
a GSequenceIter pointing to the position in seq
where data
would have been inserted according to iter_cmp
and cmp_data
.
[transfer none]
Since: 2.14
GSequenceIter * g_sequence_lookup (GSequence *seq,gpointer data,GCompareDataFunc cmp_func,gpointer cmp_data);
Returns an iterator pointing to the position of the first item found
equal to data
according to cmp_func
and cmp_data
. If more than one
item is equal, it is not guaranteed that it is the first which is
returned. In that case, you can use g_sequence_iter_next() and
g_sequence_iter_prev() to get others.
cmp_func
is called with two items of the seq
, and cmp_data
.
It should return 0 if the items are equal, a negative value if
the first item comes before the second, and a positive value if
the second item comes before the first.
This function will fail if the data contained in the sequence is unsorted.
seq |
||
data |
data to look up |
|
cmp_func |
the function used to compare items in the sequence |
|
cmp_data |
user data passed to |
an GSequenceIter pointing to the position of the
first item found equal to data
according to cmp_func
and
cmp_data
, or NULL if no such item exists.
[transfer none][nullable]
Since: 2.28
GSequenceIter * g_sequence_lookup_iter (GSequence *seq,gpointer data,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data);
Like g_sequence_lookup(), but uses a GSequenceIterCompareFunc
instead of a GCompareDataFunc as the compare function.
iter_cmp
is called with two iterators pointing into seq
.
It should return 0 if the iterators are equal, a negative value
if the first iterator comes before the second, and a positive
value if the second iterator comes before the first.
This function will fail if the data contained in the sequence is unsorted.
seq |
||
data |
data to look up |
|
iter_cmp |
the function used to compare iterators in the sequence |
|
cmp_data |
user data passed to |
an GSequenceIter pointing to the position of
the first item found equal to data
according to iter_cmp
and cmp_data
, or NULL if no such item exists.
[transfer none][nullable]
Since: 2.28
gpointer
g_sequence_get (GSequenceIter *iter);
Returns the data that iter
points to.
Since: 2.14
void g_sequence_set (GSequenceIter *iter,gpointer data);
Changes the data for the item pointed to by iter
to be data
. If
the sequence has a data destroy function associated with it, that
function is called on the existing data that iter
pointed to.
Since: 2.14
gboolean
g_sequence_iter_is_begin (GSequenceIter *iter);
Returns whether iter
is the begin iterator
Since: 2.14
gboolean
g_sequence_iter_is_end (GSequenceIter *iter);
Returns whether iter
is the end iterator
Since: 2.14
GSequenceIter *
g_sequence_iter_next (GSequenceIter *iter);
Returns an iterator pointing to the next position after iter
.
If iter
is the end iterator, the end iterator is returned.
Since: 2.14
GSequenceIter *
g_sequence_iter_prev (GSequenceIter *iter);
Returns an iterator pointing to the previous position before iter
.
If iter
is the begin iterator, the begin iterator is returned.
Since: 2.14
gint
g_sequence_iter_get_position (GSequenceIter *iter);
Returns the position of iter
Since: 2.14
GSequenceIter * g_sequence_iter_move (GSequenceIter *iter,gint delta);
Returns the GSequenceIter which is delta
positions away from iter
.
If iter
is closer than -delta
positions to the beginning of the sequence,
the begin iterator is returned. If iter
is closer than delta
positions
to the end of the sequence, the end iterator is returned.
iter |
||
delta |
A positive or negative number indicating how many positions away
from |
Since: 2.14
GSequence *
g_sequence_iter_get_sequence (GSequenceIter *iter);
Returns the GSequence that iter
points into.
Since: 2.14
gint g_sequence_iter_compare (GSequenceIter *a,GSequenceIter *b);
Returns a negative number if a
comes before b
, 0 if they are equal,
and a positive number if a
comes after b
.
The a
and b
iterators must point into the same sequence.
a negative number if a
comes before b
, 0 if they are
equal, and a positive number if a
comes after b
Since: 2.14
GSequenceIter * g_sequence_range_get_midpoint (GSequenceIter *begin,GSequenceIter *end);
Finds an iterator somewhere in the range (begin
, end
). This
iterator will be close to the middle of the range, but is not
guaranteed to be exactly in the middle.
The begin
and end
iterators must both point to the same sequence
and begin
must come before or be equal to end
in the sequence.
Since: 2.14
typedef struct _GSequence GSequence;
The GSequence struct is an opaque data type representing a sequence data type.
typedef struct _GSequenceNode GSequenceIter;
The GSequenceIter struct is an opaque data type representing an iterator pointing into a GSequence.