## Sequences

Sequences — scalable lists

## Functions

gint | (*GSequenceIterCompareFunc) ()
GSequence * | g_sequence_new ()
void | g_sequence_free ()
gint | g_sequence_get_length ()
gboolean | g_sequence_is_empty ()
void | g_sequence_foreach ()
void | g_sequence_foreach_range ()
void | g_sequence_sort ()
void | g_sequence_sort_iter ()
GSequenceIter * | g_sequence_get_begin_iter ()
GSequenceIter * | g_sequence_get_end_iter ()
GSequenceIter * | g_sequence_get_iter_at_pos ()
GSequenceIter * | g_sequence_append ()
GSequenceIter * | g_sequence_prepend ()
GSequenceIter * | g_sequence_insert_before ()
void | g_sequence_move ()
void | g_sequence_swap ()
GSequenceIter * | g_sequence_insert_sorted ()
GSequenceIter * | g_sequence_insert_sorted_iter ()
void | g_sequence_sort_changed ()
void | g_sequence_sort_changed_iter ()
void | g_sequence_remove ()
void | g_sequence_remove_range ()
void | g_sequence_move_range ()
GSequenceIter * | g_sequence_search ()
GSequenceIter * | g_sequence_search_iter ()
GSequenceIter * | g_sequence_lookup ()
GSequenceIter * | g_sequence_lookup_iter ()
gpointer | g_sequence_get ()
void | g_sequence_set ()
gboolean | g_sequence_iter_is_begin ()
gboolean | g_sequence_iter_is_end ()
GSequenceIter * | g_sequence_iter_next ()
GSequenceIter * | g_sequence_iter_prev ()
gint | g_sequence_iter_get_position ()
GSequenceIter * | g_sequence_iter_move ()
GSequence * | g_sequence_iter_get_sequence ()
gint | g_sequence_iter_compare ()
GSequenceIter * | g_sequence_range_get_midpoint ()

## Types and Values

| GSequence
typedef | GSequenceIter

## Includes

    #include <gmodule.h>

## Description

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.

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.

## Functions

### GSequenceIterCompareFunc ()

    gint
    (*GSequenceIterCompareFunc) (GSequenceIter *a,
                                 GSequenceIter *b,
                                 gpointer 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` .

#### Parameters

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` .

### g_sequence_new ()

    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.

#### Parameters

data_destroy | a GDestroyNotify function, or `NULL`. | [nullable]

#### Returns

a new GSequence.

[transfer full]

Since: 2.14

### g_sequence_free ()

    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` .

#### Parameters

seq | a GSequence |

Since: 2.14

### g_sequence_get_length ()

    gint
    g_sequence_get_length (GSequence *seq);

Returns the length 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.

#### Parameters

seq | a GSequence |

#### Returns

the length of `seq`

Since: 2.14

### g_sequence_is_empty ()

    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.

#### Parameters

seq | a GSequence |

#### Returns

`TRUE` if the sequence is empty, otherwise `FALSE`.

Since: 2.48

### g_sequence_foreach ()

    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.

#### Parameters

seq | a GSequence |
func | the function to call for each item in `seq` |
user_data | user data passed to `func` |

Since: 2.14

### g_sequence_foreach_range ()

    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.

#### Parameters

begin | a GSequenceIter |
end | a GSequenceIter |
func | a GFunc |
user_data | user data passed to `func` |

Since: 2.14

### g_sequence_sort ()

    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.

#### Parameters

seq | a GSequence |
cmp_func | the function used to sort the sequence |
cmp_data | user data passed to `cmp_func` |

Since: 2.14

### g_sequence_sort_iter ()

    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.

#### Parameters

seq | a GSequence |
cmp_func | the function used to compare iterators in the sequence |
cmp_data | user data passed to `cmp_func` |

Since: 2.14

### g_sequence_get_begin_iter ()

    GSequenceIter *
    g_sequence_get_begin_iter (GSequence *seq);

Returns the begin iterator for `seq` .

#### Parameters

seq | a GSequence |

#### Returns

the begin iterator for `seq` .

[transfer none]

Since: 2.14

### g_sequence_get_end_iter ()

    GSequenceIter *
    g_sequence_get_end_iter (GSequence *seq);

Returns the end iterator for `seg`

#### Parameters

seq | a GSequence |

#### Returns

the end iterator for `seq` .

[transfer none]

Since: 2.14

### g_sequence_get_iter_at_pos ()

    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.

#### Parameters

seq | a GSequence |
pos | a position in `seq` , or -1 for the end |

#### Returns

The GSequenceIter at position `pos` .

[transfer none]

Since: 2.14

### g_sequence_append ()

    GSequenceIter *
    g_sequence_append (GSequence *seq,
                       gpointer data);

Adds a new item to the end of `seq` .

#### Parameters

seq | a GSequence |
data | the data for the new item |

#### Returns

an iterator pointing to the new item.

[transfer none]

Since: 2.14

### g_sequence_prepend ()

    GSequenceIter *
    g_sequence_prepend (GSequence *seq,
                        gpointer data);

Adds a new item to the front of `seq`

#### Parameters

seq | a GSequence |
data | the data for the new item |

#### Returns

an iterator pointing to the new item.

[transfer none]

Since: 2.14

### g_sequence_insert_before ()

    GSequenceIter *
    g_sequence_insert_before (GSequenceIter *iter,
                              gpointer data);

Inserts a new item just before the item pointed to by `iter` .

#### Parameters

iter | a GSequenceIter |
data | the data for the new item |

#### Returns

an iterator pointing to the new item.

[transfer none]

Since: 2.14

### g_sequence_move ()

    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.

#### Parameters

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

### g_sequence_swap ()

    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.

#### Parameters

a | a GSequenceIter |
b | a GSequenceIter |

Since: 2.14

### g_sequence_insert_sorted ()

    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()`.

#### Parameters

seq | a GSequence |
data | the data to insert |
cmp_func | the function used to compare items in the sequence |
cmp_data | user data passed to `cmp_func` . |

#### Returns

a GSequenceIter pointing to the new item.

[transfer none]

Since: 2.14

### g_sequence_insert_sorted_iter ()

    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()`.

#### Parameters

seq | a GSequence |
data | data for the new item |
iter_cmp | the function used to compare iterators in the sequence |
cmp_data | user data passed to `iter_cmp` |

#### Returns

a GSequenceIter pointing to the new item.

[transfer none]

Since: 2.14

### g_sequence_sort_changed ()

    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.

#### Parameters

iter | A GSequenceIter |
cmp_func | the function used to compare items in the sequence |
cmp_data | user data passed to `cmp_func` . |

Since: 2.14

### g_sequence_sort_changed_iter ()

    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.

#### Parameters

iter | a GSequenceIter |
iter_cmp | the function used to compare iterators in the sequence |
cmp_data | user data passed to `cmp_func` |

Since: 2.14

### g_sequence_remove ()

    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.

#### Parameters

iter | a GSequenceIter |

Since: 2.14

### g_sequence_remove_range ()

    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.

#### Parameters

begin | a GSequenceIter |
end | a GSequenceIter |

Since: 2.14

### g_sequence_move_range ()

    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.

#### Parameters

dest | a GSequenceIter |
begin | a GSequenceIter |
end | a GSequenceIter |

Since: 2.14

### g_sequence_search ()

    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.

#### Parameters

seq | a GSequence |
data | data for the new item |
cmp_func | the function used to compare items in the sequence |
cmp_data | user data passed to `cmp_func` |

#### Returns

an GSequenceIter pointing to the position where `data` would have been inserted according to `cmp_func` and `cmp_data` .

[transfer none]

Since: 2.14

### g_sequence_search_iter ()

    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.

#### Parameters

seq | a GSequence |
data | data for the new item |
iter_cmp | the function used to compare iterators in the sequence |
cmp_data | user data passed to `iter_cmp` |

#### Returns

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

### g_sequence_lookup ()

    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.

#### Parameters

seq | a GSequence |
data | data to look up |
cmp_func | the function used to compare items in the sequence |
cmp_data | user data passed to `cmp_func` |

#### Returns

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

### g_sequence_lookup_iter ()

    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.

#### Parameters

seq | a GSequence |
data | data to look up |
iter_cmp | the function used to compare iterators in the sequence |
cmp_data | user data passed to `iter_cmp` |

#### Returns

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

### g_sequence_get ()

    gpointer
    g_sequence_get (GSequenceIter *iter);

Returns the data that `iter` points to.

#### Parameters

iter | a GSequenceIter |

#### Returns

the data that `iter` points to.

[transfer none]

Since: 2.14

### g_sequence_set ()

    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.

#### Parameters

iter | a GSequenceIter |
data | new data for the item |

Since: 2.14

### g_sequence_iter_is_begin ()

    gboolean
    g_sequence_iter_is_begin (GSequenceIter *iter);

Returns whether `iter` is the begin iterator

#### Parameters

iter | a GSequenceIter |

#### Returns

whether `iter` is the begin iterator

Since: 2.14

### g_sequence_iter_is_end ()

    gboolean
    g_sequence_iter_is_end (GSequenceIter *iter);

Returns whether `iter` is the end iterator

#### Parameters

iter | a GSequenceIter |

#### Returns

Whether `iter` is the end iterator

Since: 2.14

### g_sequence_iter_next ()

    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.

#### Parameters

iter | a GSequenceIter |

#### Returns

a GSequenceIter pointing to the next position after `iter` .

[transfer none]

Since: 2.14

### g_sequence_iter_prev ()

    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.

#### Parameters

iter | a GSequenceIter |

#### Returns

a GSequenceIter pointing to the previous position before `iter` .

[transfer none]

Since: 2.14

### g_sequence_iter_get_position ()

    gint
    g_sequence_iter_get_position (GSequenceIter *iter);

Returns the position of `iter`

#### Parameters

iter | a GSequenceIter |

#### Returns

the position of `iter`

Since: 2.14

### g_sequence_iter_move ()

    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.

#### Parameters

iter | a GSequenceIter |
delta | A positive or negative number indicating how many positions away from `iter` the returned GSequenceIter will be |

#### Returns

a GSequenceIter which is `delta` positions away from `iter` .

[transfer none]

Since: 2.14

### g_sequence_iter_get_sequence ()

    GSequence *
    g_sequence_iter_get_sequence (GSequenceIter *iter);

Returns the GSequence that `iter` points into.

#### Parameters

iter | a GSequenceIter |

#### Returns

the GSequence that `iter` points into.

[transfer none]

Since: 2.14

### g_sequence_iter_compare ()

    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.

#### Parameters

a | a GSequenceIter |
b | a GSequenceIter |

#### Returns

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

### g_sequence_range_get_midpoint ()

    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.

#### Parameters

begin | a GSequenceIter |
end | a GSequenceIter |

#### Returns

a GSequenceIter pointing somewhere in the (`begin` , `end` ) range.

[transfer none]

Since: 2.14

## Types and Values

### GSequence

    typedef struct _GSequence GSequence;

The GSequence struct is an opaque data type representing a sequence data type.

### GSequenceIter

    typedef struct _GSequenceNode  GSequenceIter;

The GSequenceIter struct is an opaque data type representing an iterator pointing into a GSequence.