EggSequence

[Soeren Sandmann <sandmann daimi au dk>]

Hi,

A long time ago I wrote GSequence for the purpose of speeding up
Nautilus, which at the time was spending large amounts of maintaining
sorted lists of file. GSequence is a data structure that implements
the API of a list, but represents it internally as a balanced binary
tree. This allows things like g_sequence_insert_sorted() to run in
time O(log n) instead of O(n).

Compared to GTree, GSequence is a lot simpler to use when all you want
is to maintain a sorted list. Another big benefit is that you can
switch comparison function on the fly by just doing:

        g_sequence_sort (sequence, new_comparison_function, data);

and it is perfectly possible to maintain a non-sorted list if desired.

The datastructure is accessed through iterators. These are stable
across all manipulations of the sequence, Ie., you can have an
iterator point to an item, then sort the sequence, and the iterator
will still point to the same item whereever it ends up.

GSequence has already been cutted and pasted into a number of
projects, including nautilus, rhythmbox, jamboree and GtkListModel, so
I think it makes sense to add it to GLib.

If accepted, I'll write API documentation and port GtkListModel to use
it. There is already a through testsuite SVN.

Header file:

http://svn.gnome.org/viewcvs/libegg/trunk/libegg/sequence/eggsequence.h?view=markup

Other files:

http://svn.gnome.org/viewcvs/libegg/trunk/libegg/sequence/


Soren