1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 Soeren Sandmann (sandmann@daimi.au.dk)
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
22 #include "eggsequence.h"
24 typedef struct _EggSequenceNode EggSequenceNode;
28 EggSequenceNode * end_node;
29 GDestroyNotify data_destroy_notify;
30 gboolean access_prohibited;
33 struct _EggSequenceNode
36 EggSequenceNode *parent;
37 EggSequenceNode *left;
38 EggSequenceNode *right;
39 gpointer data; /* For the end node, this field points
44 static EggSequenceNode *node_new (gpointer data);
45 static EggSequenceNode *node_get_first (EggSequenceNode *node);
46 static EggSequenceNode *node_get_last (EggSequenceNode *node);
47 static EggSequenceNode *node_get_prev (EggSequenceNode *node);
48 static EggSequenceNode *node_get_next (EggSequenceNode *node);
49 static gint node_get_pos (EggSequenceNode *node);
50 static EggSequenceNode *node_get_by_pos (EggSequenceNode *node,
52 static EggSequenceNode *node_find_closest (EggSequenceNode *haystack,
53 EggSequenceNode *needle,
55 EggSequenceIterCompareFunc cmp,
57 static gint node_get_length (EggSequenceNode *node);
58 static void node_free (EggSequenceNode *node,
60 static void node_cut (EggSequenceNode *split);
61 static void node_insert_after (EggSequenceNode *node,
62 EggSequenceNode *second);
63 static void node_insert_before (EggSequenceNode *node,
64 EggSequenceNode *new);
65 static void node_unlink (EggSequenceNode *node);
66 static void node_insert_sorted (EggSequenceNode *node,
69 EggSequenceIterCompareFunc cmp_func,
73 get_sequence (EggSequenceNode *node)
75 return (EggSequence *)node_get_last (node)->data;
79 check_seq_access (EggSequence *seq)
81 if (G_UNLIKELY (seq->access_prohibited))
83 g_warning ("Accessing a sequence while it is "
84 "being sorted or searched is not allowed");
89 check_iter_access (EggSequenceIter *iter)
91 check_seq_access (get_sequence (iter));
95 is_end (EggSequenceIter *iter)
97 EggSequence *seq = get_sequence (iter);
99 return seq->end_node == iter;
108 * @data_destroy: A #GDestroyNotify function, or %NULL
110 * Creates a new EggSequence. The @data_destroy function will be called
111 * on all items when the sequence is destroyed and on items that are
112 * removed from the sequence.
114 * Return value: A new #EggSequence
119 egg_sequence_new (GDestroyNotify data_destroy)
121 EggSequence *seq = g_new (EggSequence, 1);
122 seq->data_destroy_notify = data_destroy;
124 seq->end_node = node_new (seq);
126 seq->access_prohibited = FALSE;
133 * @seq: a #EggSequence
135 * Frees the memory allocated for @seq. If @seq has a destroy notify
136 * function associated with it, that function is called on all items in
142 egg_sequence_free (EggSequence *seq)
144 g_return_if_fail (seq != NULL);
146 check_seq_access (seq);
148 node_free (seq->end_node, seq);
154 * egg_sequence_foreach_range:
155 * @begin: a #EggSequenceIter
156 * @end: a #EggSequenceIter
158 * @user_data: user data passed to @func
160 * Calls @func for each item in the range (@begin, @end) passing
161 * @user_data to the function.
166 egg_sequence_foreach_range (EggSequenceIter *begin,
167 EggSequenceIter *end,
172 EggSequenceIter *iter;
174 g_return_if_fail (func != NULL);
175 g_return_if_fail (begin != NULL);
176 g_return_if_fail (end != NULL);
178 seq = get_sequence (begin);
180 seq->access_prohibited = TRUE;
185 EggSequenceIter *next = node_get_next (iter);
187 func (iter->data, user_data);
192 seq->access_prohibited = FALSE;
196 * egg_sequence_foreach:
197 * @seq: a #EggSequence
198 * @func: the function to call for each item in @seq
199 * @data: user data passed to @func
201 * Calls @func for each item in the sequence passing @user_data
207 egg_sequence_foreach (EggSequence *seq,
211 EggSequenceIter *begin, *end;
213 check_seq_access (seq);
215 begin = egg_sequence_get_begin_iter (seq);
216 end = egg_sequence_get_end_iter (seq);
218 egg_sequence_foreach_range (begin, end, func, data);
222 * egg_sequence_range_get_midpoint:
223 * @begin: a #EggSequenceIter
224 * @end: a #EggSequenceIter
226 * Finds an iterator somewhere in the range (@begin, @end). This
227 * iterator will be close to the middle of the range, but is not
228 * guaranteed to be <emphasize>exactly</emphasize> in the middle.
230 * The @begin and @end iterators must both point to the same sequence and
231 * @begin must come before or be equal to @end in the sequence.
233 * Return value: A #EggSequenceIter which is close to the middle of
234 * the (@begin, @end) range.
239 egg_sequence_range_get_midpoint (EggSequenceIter *begin,
240 EggSequenceIter *end)
242 int begin_pos, end_pos, mid_pos;
244 g_return_val_if_fail (begin != NULL, NULL);
245 g_return_val_if_fail (end != NULL, NULL);
246 g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
248 begin_pos = node_get_pos (begin);
249 end_pos = node_get_pos (end);
251 g_return_val_if_fail (end_pos >= begin_pos, NULL);
253 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
255 return node_get_by_pos (begin, mid_pos);
259 * egg_sequence_iter_compare:
260 * @a: a #EggSequenceIter
261 * @b: a #EggSequenceIter
263 * Returns a negative number if @a comes before @b, 0 if they are equal,
264 * and a positive number if @a comes after @b.
266 * The @a and @b iterators must point into the same sequence.
268 * Return value: A negative number if @a comes before @b, 0 if they are
269 * equal, and a positive number if @a comes after @b.
274 egg_sequence_iter_compare (EggSequenceIter *a,
279 g_return_val_if_fail (a != NULL, 0);
280 g_return_val_if_fail (b != NULL, 0);
281 g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
283 check_iter_access (a);
284 check_iter_access (b);
286 a_pos = node_get_pos (a);
287 b_pos = node_get_pos (b);
291 else if (a_pos > b_pos)
298 * egg_sequence_append:
299 * @seq: a #EggSequencePointer
300 * @data: the data for the new item
302 * Adds a new item to the end of @seq.
304 * Return value: An iterator pointing to the new item
309 egg_sequence_append (EggSequence *seq,
312 EggSequenceNode *node;
314 g_return_val_if_fail (seq != NULL, NULL);
316 check_seq_access (seq);
318 node = node_new (data);
319 node_insert_before (seq->end_node, node);
325 * egg_sequence_prepend:
326 * @seq: a #EggSequence
327 * @data: the data for the new item
329 * Adds a new item to the front of @seq
331 * Return value: An iterator pointing to the new item
336 egg_sequence_prepend (EggSequence *seq,
339 EggSequenceNode *node, *first;
341 g_return_val_if_fail (seq != NULL, NULL);
343 check_seq_access (seq);
345 node = node_new (data);
346 first = node_get_first (seq->end_node);
348 node_insert_before (first, node);
354 * egg_sequence_insert_before:
355 * @iter: a #EggSequenceIter
356 * @data: the data for the new item
358 * Inserts a new item just before the item pointed to by @iter.
360 * Return value: An iterator pointing to the new item
365 egg_sequence_insert_before (EggSequenceIter *iter,
368 EggSequenceNode *node;
370 g_return_val_if_fail (iter != NULL, NULL);
372 check_iter_access (iter);
374 node = node_new (data);
376 node_insert_before (iter, node);
382 * egg_sequence_remove:
383 * @iter: a #EggSequenceIter
385 * Removes the item pointed to by @iter. It is an error to pass the
386 * end iterator to this function.
388 * If the sequnce has a data destroy function associated with it, this
389 * function is called on the data for the removed item.
394 egg_sequence_remove (EggSequenceIter *iter)
398 g_return_if_fail (iter != NULL);
399 g_return_if_fail (!is_end (iter));
401 check_iter_access (iter);
403 seq = get_sequence (iter);
406 node_free (iter, seq);
410 * egg_sequence_remove_range:
411 * @begin: a #EggSequenceIter
412 * @end: a #EggSequenceIter
414 * Removes all items in the (@begin, @end) range.
416 * If the sequence has a data destroy function associated with it, this
417 * function is called on the data for the removed items.
422 egg_sequence_remove_range (EggSequenceIter *begin,
423 EggSequenceIter *end)
425 g_return_if_fail (get_sequence (begin) == get_sequence (end));
427 check_iter_access (begin);
428 check_iter_access (end);
430 egg_sequence_move_range (NULL, begin, end);
434 * egg_sequence_move_range:
435 * @dest: a #EggSequenceIter
436 * @begin: a #EggSequenceIter
437 * @end: a #EggSequenceIter
439 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
440 * The @begin and @end iters must point into the same sequence. It is
441 * allowed for @dest to point to a different sequence than the one pointed
442 * into by @begin and @end.
444 * If @dest is NULL, the range indicated by @begin and @end is
445 * removed from the sequence. If @dest iter points to a place within
446 * the (@begin, @end) range, the range does not move.
451 egg_sequence_move_range (EggSequenceIter *dest,
452 EggSequenceIter *begin,
453 EggSequenceIter *end)
455 EggSequence *src_seq;
456 EggSequenceNode *first;
458 g_return_if_fail (begin != NULL);
459 g_return_if_fail (end != NULL);
461 check_iter_access (begin);
462 check_iter_access (end);
464 check_iter_access (dest);
466 src_seq = get_sequence (begin);
468 g_return_if_fail (src_seq == get_sequence (end));
470 /* Dest points to begin or end? */
471 if (dest == begin || dest == end)
474 /* begin comes after end? */
475 if (egg_sequence_iter_compare (begin, end) >= 0)
478 /* dest points somewhere in the (begin, end) range? */
479 if (dest && get_sequence (dest) == src_seq &&
480 egg_sequence_iter_compare (dest, begin) > 0 &&
481 egg_sequence_iter_compare (dest, end) < 0)
486 src_seq = get_sequence (begin);
488 first = node_get_first (begin);
495 node_insert_after (node_get_last (first), end);
498 node_insert_before (dest, begin);
500 node_free (begin, src_seq);
505 GCompareDataFunc cmp_func;
507 EggSequenceNode *end_node;
510 /* This function compares two iters using a normal compare
511 * function and user_data passed in in a SortInfo struct
514 iter_compare (EggSequenceIter *node1,
515 EggSequenceIter *node2,
518 const SortInfo *info = data;
521 if (node1 == info->end_node)
524 if (node2 == info->end_node)
527 retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
534 * @seq: a #EggSequence
535 * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
536 * passed two items of @seq and should return 0 if they are equal,
537 * a negative value fi the first comes before the second, and a
538 * positive value if the second comes before the first.
539 * @cmp_data: user data passed to @cmp_func
541 * Sorts @seq using @cmp_func.
546 egg_sequence_sort (EggSequence *seq,
547 GCompareDataFunc cmp_func,
550 SortInfo info = { cmp_func, cmp_data, seq->end_node };
552 check_seq_access (seq);
554 egg_sequence_sort_iter (seq, iter_compare, &info);
558 * egg_sequence_insert_sorted:
559 * @seq: a #EggSequence
560 * @data: the data to insert
561 * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
562 * is called with two items of the @seq and @user_data. It should
563 * return 0 if the items are equal, a negative value if the first
564 * item comes before the second, and a positive value if the second
565 * item comes before the first.
566 * @cmp_data: user data passed to @cmp_func.
568 * Inserts @data into @queue using @func to determine the new position.
569 * @seq must already be sorted according to @cmp_func; otherwise the
570 * new position of is undefined.
572 * Return value: A #EggSequenceIter pointing to the new item.
577 egg_sequence_insert_sorted (EggSequence *seq,
579 GCompareDataFunc cmp_func,
582 SortInfo info = { cmp_func, cmp_data, NULL };
584 g_return_val_if_fail (seq != NULL, NULL);
585 g_return_val_if_fail (cmp_func != NULL, NULL);
587 info.end_node = seq->end_node;
588 check_seq_access (seq);
590 return egg_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
594 * egg_sequence_sort_changed:
595 * @iter: A #EggSequenceIter
596 * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
597 * is called with two items of the @seq and @user_data. It should
598 * return 0 if the items are equal, a negative value if the first
599 * item comes before the second, and a positive value if the second
600 * item comes before the first.
601 * @cmp_data: user data passed to @cmp_func.
603 * Moves the data pointed to a new position as indicated by @cmp_func. This
604 * function should be called for items in a sequence already sorted according
605 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
606 * may return different values for that item.
611 egg_sequence_sort_changed (EggSequenceIter *iter,
612 GCompareDataFunc cmp_func,
615 SortInfo info = { cmp_func, cmp_data, NULL };
617 g_return_if_fail (!is_end (iter));
619 info.end_node = get_sequence (iter)->end_node;
620 check_iter_access (iter);
622 egg_sequence_sort_changed_iter (iter, iter_compare, &info);
626 * egg_sequence_search:
627 * @seq: a #EggSequence
628 * @data: data for the new item
629 * @cmp_func: the #GCompareDataFunc used to compare items in the queue. It
630 * is called with two items of the @seq and @user_data. It should
631 * return 0 if the items are equal, a negative value if the first
632 * item comes before the second, and a positive value if the second
633 * item comes before the first.
634 * @cmp_data: user data passed to @cmp_func.
636 * Returns an iterator pointing to the position where @data would
637 * be inserted according to @cmp_func and @cmp_data.
639 * Return value: An #EggSequenceIter pointing to the position where @data
640 * would have been inserted according to @cmp_func and @cmp_data.
645 egg_sequence_search (EggSequence *seq,
647 GCompareDataFunc cmp_func,
650 SortInfo info = { cmp_func, cmp_data, NULL };
652 g_return_val_if_fail (seq != NULL, NULL);
654 info.end_node = seq->end_node;
655 check_seq_access (seq);
657 return egg_sequence_search_iter (seq, data, iter_compare, &info);
661 * egg_sequence_sort_iter:
662 * @seq: a #EggSequence
663 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
664 * sequence. It is called with two iterators pointing into @seq. It should
665 * return 0 if the iterators are equal, a negative value if the first
666 * iterator comes before the second, and a positive value if the second
667 * iterator comes before the first.
668 * @cmp_data: user data passed to @cmp_func
670 * Like egg_sequence_sort(), but uses a #EggSequenceIterCompareFunc instead
671 * of a GCompareDataFunc as the compare function
676 egg_sequence_sort_iter (EggSequence *seq,
677 EggSequenceIterCompareFunc cmp_func,
681 EggSequenceNode *begin, *end;
683 g_return_if_fail (seq != NULL);
684 g_return_if_fail (cmp_func != NULL);
686 check_seq_access (seq);
688 begin = egg_sequence_get_begin_iter (seq);
689 end = egg_sequence_get_end_iter (seq);
691 tmp = egg_sequence_new (NULL);
693 egg_sequence_move_range (egg_sequence_get_begin_iter (tmp), begin, end);
695 tmp->access_prohibited = TRUE;
696 seq->access_prohibited = TRUE;
698 while (egg_sequence_get_length (tmp) > 0)
700 EggSequenceNode *node = egg_sequence_get_begin_iter (tmp);
704 node_insert_sorted (seq->end_node, node, seq->end_node, cmp_func, cmp_data);
707 tmp->access_prohibited = FALSE;
708 seq->access_prohibited = FALSE;
710 egg_sequence_free (tmp);
714 * egg_sequence_sort_changed_iter:
715 * @iter: a #EggSequenceIter
716 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
717 * sequence. It is called with two iterators pointing into @seq. It should
718 * return 0 if the iterators are equal, a negative value if the first
719 * iterator comes before the second, and a positive value if the second
720 * iterator comes before the first.
721 * @cmp_data: user data passed to @cmp_func
723 * Like egg_sequence_sort_changed(), but uses
724 * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
725 * the compare function.
730 egg_sequence_sort_changed_iter (EggSequenceIter *iter,
731 EggSequenceIterCompareFunc iter_cmp,
735 EggSequenceIter *next, *prev;
737 g_return_if_fail (!is_end (iter));
739 check_iter_access (iter);
741 /* If one of the neighbours is equal to iter, then
742 * don't move it. This ensures that sort_changed() is
743 * a stable operation.
746 next = node_get_next (iter);
747 prev = node_get_prev (iter);
749 if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
752 if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
755 seq = get_sequence (iter);
757 seq->access_prohibited = TRUE;
760 node_insert_sorted (seq->end_node, iter, seq->end_node, iter_cmp, cmp_data);
762 seq->access_prohibited = FALSE;
766 * egg_sequence_insert_sorted_iter:
767 * @seq: a #EggSequence
768 * @data: data for the new item
769 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
770 * sequence. It is called with two iterators pointing into @seq. It should
771 * return 0 if the iterators are equal, a negative value if the first
772 * iterator comes before the second, and a positive value if the second
773 * iterator comes before the first.
774 * @cmp_data: user data passed to @cmp_func
776 * Like egg_sequence_insert_sorted(), but uses
777 * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
778 * the compare function.
780 * Return value: A #EggSequenceIter pointing to the new item
785 egg_sequence_insert_sorted_iter (EggSequence *seq,
787 EggSequenceIterCompareFunc iter_cmp,
790 EggSequenceNode *new_node;
791 EggSequence *tmp_seq;
793 check_seq_access (seq);
795 /* Create a new temporary sequence and put the new node into
796 * that. The reason for this is that the user compare function
797 * will be called with the new node, and if it dereferences,
798 * "is_end" will be called on it. But that will crash if the
799 * node is not actually in a sequence.
801 * node_insert_sorted() makes sure the node is unlinked before
804 * The reason we need the "iter" versions at all is that that
805 * is the only kind of compare functions GtkTreeView can use.
807 tmp_seq = egg_sequence_new (NULL);
808 new_node = egg_sequence_append (tmp_seq, data);
810 node_insert_sorted (seq->end_node, new_node,
811 seq->end_node, iter_cmp, cmp_data);
813 egg_sequence_free (tmp_seq);
819 * egg_sequence_search_iter:
820 * @seq: a #EggSequence
821 * @data: data for the new item
822 * @cmp_func: the #EggSequenceItercompare used to compare iterators in the
823 * sequence. It is called with two iterators pointing into @seq. It should
824 * return 0 if the iterators are equal, a negative value if the first
825 * iterator comes before the second, and a positive value if the second
826 * iterator comes before the first.
827 * @cmp_data: user data passed to @cmp_func
829 * Like egg_sequence_search(), but uses
830 * a #EggSequenceIterCompareFunc instead of a #GCompareDataFunc as
831 * the compare function.
833 * Return value: A #EggSequenceIter pointing to the position in @seq
834 * where @data would have been inserted according to @cmp_func and @cmp_data.
839 egg_sequence_search_iter (EggSequence *seq,
841 EggSequenceIterCompareFunc cmp_func,
844 EggSequenceNode *node;
845 EggSequenceNode *dummy;
847 g_return_val_if_fail (seq != NULL, NULL);
849 check_seq_access (seq);
851 seq->access_prohibited = TRUE;
853 dummy = node_new (data);
855 node = node_find_closest (seq->end_node, dummy,
856 seq->end_node, cmp_func, cmp_data);
858 node_free (dummy, NULL);
860 seq->access_prohibited = FALSE;
866 * egg_sequence_iter_get_sequence:
867 * @iter: a #EggSequenceIter
869 * Returns the #EggSequence that @iter points into.
871 * Return value: The #EggSequence that @iter points into.
876 egg_sequence_iter_get_sequence (EggSequenceIter *iter)
878 g_return_val_if_fail (iter != NULL, NULL);
880 return get_sequence (iter);
885 * @iter: a #EggSequenceIter
887 * Returns the data that @iter points to.
889 * Return value: The data that @iter points to
894 egg_sequence_get (EggSequenceIter *iter)
896 g_return_val_if_fail (iter != NULL, NULL);
897 g_return_val_if_fail (!is_end (iter), NULL);
904 * @iter: a #EggSequenceIter
905 * @data: new data for the item
907 * Changes the data for the item pointed to by @iter to be @data. If
908 * the sequence has a data destroy function associated with it, that
909 * function is called on the existing data that @iter pointed to.
914 egg_sequence_set (EggSequenceIter *iter,
919 g_return_if_fail (iter != NULL);
920 g_return_if_fail (!is_end (iter));
922 seq = get_sequence (iter);
924 /* If @data is identical to iter->data, it is destroyed
925 * here. This will work right in case of ref-counted objects. Also
926 * it is similar to what ghashtables do.
928 * For non-refcounted data it's a little less convenient, but
929 * code relying on self-setting not destroying would be
930 * pretty dubious anyway ...
933 if (seq->data_destroy_notify)
934 seq->data_destroy_notify (iter->data);
940 * egg_sequence_get_length:
941 * @seq: a #EggSequence
943 * Returns the length of @seq
945 * Return value: The length of @seq
950 egg_sequence_get_length (EggSequence *seq)
952 return node_get_length (seq->end_node) - 1;
956 * egg_sequence_get_end_iter:
957 * @seq: a #EggSequence
959 * Returns the end iterator for @seg
961 * Return value: The end iterator for @seq
966 egg_sequence_get_end_iter (EggSequence *seq)
968 g_return_val_if_fail (seq != NULL, NULL);
970 g_assert (is_end (seq->end_node));
972 return seq->end_node;
976 * egg_sequence_get_begin_iter:
977 * @seq: a #EggSequence
979 * Returns the begin iterator for @seq.
981 * Return value: The begin iterator for @seq.
986 egg_sequence_get_begin_iter (EggSequence *seq)
988 g_return_val_if_fail (seq != NULL, NULL);
989 return node_get_first (seq->end_node);
993 clamp_position (EggSequence *seq,
996 gint len = egg_sequence_get_length (seq);
998 if (pos > len || pos < 0)
1005 * if pos > number of items or -1, will return end pointer
1008 * egg_sequence_get_iter_at_pos:
1009 * @seq: a #EggSequence
1010 * @pos: a position in @seq, or -1 for the end.
1012 * Returns the iterator as position @pos. If @pos is negative or larger
1013 * than the number of items in @seq, the end iterator is returned.
1015 * Return value: The #EggSequenceIter at position @pos
1020 egg_sequence_get_iter_at_pos (EggSequence *seq,
1023 g_return_val_if_fail (seq != NULL, NULL);
1025 pos = clamp_position (seq, pos);
1027 return node_get_by_pos (seq->end_node, pos);
1031 * egg_sequence_move:
1032 * @src: a #EggSequenceIter pointing to the item to move
1033 * @dest: a #EggSequenceIter pointing to the position to which
1034 * the item is moved.
1036 * Move the item pointed to by @src to the position indicated by @dest.
1037 * After calling this function @dest will point to the position immediately
1043 egg_sequence_move (EggSequenceIter *src,
1044 EggSequenceIter *dest)
1046 g_return_if_fail (src != NULL);
1047 g_return_if_fail (dest != NULL);
1048 g_return_if_fail (!is_end (src));
1054 node_insert_before (dest, src);
1057 /* EggSequenceIter */
1060 * egg_sequence_iter_is_end:
1061 * @iter: a #EggSequenceIter
1063 * Returns whether @iter is the end iterator
1065 * Return value: Whether @iter is the end iterator.
1070 egg_sequence_iter_is_end (EggSequenceIter *iter)
1072 g_return_val_if_fail (iter != NULL, FALSE);
1074 return is_end (iter);
1078 * egg_sequence_iter_is_begin:
1079 * @iter: a #EggSequenceIter
1081 * Returns whether @iter is the begin iterator
1083 * Return value: Whether @iter is the begin iterator
1088 egg_sequence_iter_is_begin (EggSequenceIter *iter)
1090 g_return_val_if_fail (iter != NULL, FALSE);
1092 return (node_get_prev (iter) == iter);
1096 * egg_sequence_iter_get_position:
1097 * @iter: a #EggSequenceIter
1099 * Returns the position of @iter
1101 * Return value: The position of @iter
1106 egg_sequence_iter_get_position (EggSequenceIter *iter)
1108 g_return_val_if_fail (iter != NULL, -1);
1110 return node_get_pos (iter);
1114 * egg_sequence_iter_next:
1115 * @iter: a #EggSequenceIter
1117 * Returns an iterator pointing to the next position after @iter. If
1118 * @iter is the end iterator, the end iterator is returned.
1120 * Return value: A #EggSequenceIter pointing to the next position after @iter.
1125 egg_sequence_iter_next (EggSequenceIter *iter)
1127 g_return_val_if_fail (iter != NULL, NULL);
1129 return node_get_next (iter);
1133 * egg_sequence_iter_prev:
1134 * @iter: a #EggSequenceIter
1136 * Returns an iterator pointing to the previous position before @iter. If
1137 * @iter is the begin iterator, the begin iterator is returned.
1139 * Return value: A #EggSequenceIter pointing to the previous position before
1145 egg_sequence_iter_prev (EggSequenceIter *iter)
1147 g_return_val_if_fail (iter != NULL, NULL);
1149 return node_get_prev (iter);
1153 * egg_sequence_iter_move:
1154 * @iter: a #EggSequenceIter
1155 * @delta: A positive or negative number indicating how many positions away
1156 * from @iter the returned #EggSequenceIter will be.
1158 * Returns the #EggSequenceIter which is @delta positions away from @iter.
1159 * If @iter is closer than -@delta positions to the beginning of the sequence,
1160 * the begin iterator is returned. If @iter is closer than @delta positions
1161 * to the end of the queue, the end iterator is returned.
1163 * Return value: a #EggSequenceIter which is @delta positions away from @iter.
1168 egg_sequence_iter_move (EggSequenceIter *iter,
1173 g_return_val_if_fail (iter != NULL, NULL);
1175 new_pos = node_get_pos (iter) + delta;
1177 new_pos = clamp_position (get_sequence (iter), new_pos);
1179 return node_get_by_pos (iter, new_pos);
1183 * egg_sequence_swap:
1184 * @a: a #EggSequenceIter
1185 * @b: a #EggSequenceIter
1187 * Swaps the items pointed to by @a and @b
1192 egg_sequence_swap (EggSequenceIter *a,
1195 EggSequenceNode *leftmost, *rightmost, *rightmost_next;
1198 g_return_if_fail (!egg_sequence_iter_is_end (a));
1199 g_return_if_fail (!egg_sequence_iter_is_end (b));
1204 a_pos = egg_sequence_iter_get_position (a);
1205 b_pos = egg_sequence_iter_get_position (b);
1218 rightmost_next = node_get_next (rightmost);
1220 /* Situation is now like this:
1222 * ..., leftmost, ......., rightmost, rightmost_next, ...
1225 egg_sequence_move (rightmost, leftmost);
1226 egg_sequence_move (leftmost, rightmost_next);
1230 * Implementation of the node_* methods
1233 node_update_fields (EggSequenceNode *node)
1235 g_assert (node != NULL);
1240 node->n_nodes += node->left->n_nodes;
1243 node->n_nodes += node->right->n_nodes;
1246 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1247 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1250 node_rotate (EggSequenceNode *node)
1252 EggSequenceNode *tmp, *old;
1254 g_assert (node->parent);
1255 g_assert (node->parent != node);
1257 if (NODE_LEFT_CHILD (node))
1262 node->right = node->parent;
1263 node->parent = node->parent->parent;
1266 if (node->parent->left == node->right)
1267 node->parent->left = node;
1269 node->parent->right = node;
1272 g_assert (node->right);
1274 node->right->parent = node;
1275 node->right->left = tmp;
1277 if (node->right->left)
1278 node->right->left->parent = node->right;
1287 node->left = node->parent;
1288 node->parent = node->parent->parent;
1291 if (node->parent->right == node->left)
1292 node->parent->right = node;
1294 node->parent->left = node;
1297 g_assert (node->left);
1299 node->left->parent = node;
1300 node->left->right = tmp;
1302 if (node->left->right)
1303 node->left->right->parent = node->left;
1308 node_update_fields (old);
1309 node_update_fields (node);
1312 static EggSequenceNode *
1313 splay (EggSequenceNode *node)
1315 while (node->parent)
1317 if (!node->parent->parent)
1322 else if ((NODE_LEFT_CHILD (node) && NODE_LEFT_CHILD (node->parent)) ||
1323 (NODE_RIGHT_CHILD (node) && NODE_RIGHT_CHILD (node->parent)))
1326 node_rotate (node->parent);
1340 static EggSequenceNode *
1341 node_new (gpointer data)
1343 EggSequenceNode *node = g_slice_new0 (EggSequenceNode);
1345 node->parent = NULL;
1346 node->parent = NULL;
1356 static EggSequenceNode *
1357 find_min (EggSequenceNode *node)
1367 static EggSequenceNode *
1368 find_max (EggSequenceNode *node)
1378 static EggSequenceNode *
1379 node_get_first (EggSequenceNode *node)
1381 return splay (find_min (node));
1384 static EggSequenceNode *
1385 node_get_last (EggSequenceNode *node)
1387 return splay (find_max (node));
1391 get_n_nodes (EggSequenceNode *node)
1394 return node->n_nodes;
1399 static EggSequenceNode *
1400 node_get_by_pos (EggSequenceNode *node,
1405 g_assert (node != NULL);
1409 while ((i = get_n_nodes (node->left)) != pos)
1419 g_assert (node->parent != NULL);
1423 return splay (node);
1426 static EggSequenceNode *
1427 node_get_prev (EggSequenceNode *node)
1438 return splay (node);
1441 static EggSequenceNode *
1442 node_get_next (EggSequenceNode *node)
1453 return splay (node);
1457 node_get_pos (EggSequenceNode *node)
1461 return get_n_nodes (node->left);
1464 /* Return closest node _strictly_ bigger than @needle (does always exist because
1465 * there is an end_node)
1467 static EggSequenceNode *
1468 node_find_closest (EggSequenceNode *haystack,
1469 EggSequenceNode *needle,
1470 EggSequenceNode *end,
1471 EggSequenceIterCompareFunc cmp_func,
1474 EggSequenceNode *best;
1477 g_assert (haystack);
1479 haystack = splay (haystack);
1485 /* cmp_func can't be called with the end node (it may be user-supplied) */
1486 if (haystack == end)
1489 c = cmp_func (haystack, needle, cmp_data);
1491 /* In the following we don't break even if c == 0. Instaed we go on searching
1492 * along the 'bigger' nodes, so that we find the last one that is equal
1496 haystack = haystack->left;
1498 haystack = haystack->right;
1500 while (haystack != NULL);
1502 /* If the best node is smaller or equal to the data, then move one step
1503 * to the right to make sure the best one is strictly bigger than the data
1505 if (best != end && c <= 0)
1506 best = node_get_next (best);
1512 node_free (EggSequenceNode *node,
1515 GQueue *stack = g_queue_new ();
1519 g_queue_push_head (stack, node);
1521 while (!g_queue_is_empty (stack))
1523 node = g_queue_pop_head (stack);
1527 g_queue_push_head (stack, node->right);
1528 g_queue_push_head (stack, node->left);
1530 if (seq && seq->data_destroy_notify && node != seq->end_node)
1531 seq->data_destroy_notify (node->data);
1533 g_slice_free (EggSequenceNode, node);
1537 g_queue_free (stack);
1540 /* Splits into two trees, left and right.
1541 * @node will be part of the right tree
1545 node_cut (EggSequenceNode *node)
1549 g_assert (node->parent == NULL);
1552 node->left->parent = NULL;
1555 node_update_fields (node);
1559 node_insert_before (EggSequenceNode *node,
1560 EggSequenceNode *new)
1562 g_assert (node != NULL);
1563 g_assert (new != NULL);
1567 new = splay (find_min (new));
1568 g_assert (new->left == NULL);
1571 node->left->parent = new;
1573 new->left = node->left;
1578 node_update_fields (new);
1579 node_update_fields (node);
1583 node_insert_after (EggSequenceNode *node,
1584 EggSequenceNode *new)
1586 g_assert (node != NULL);
1587 g_assert (new != NULL);
1591 new = splay (find_max (new));
1592 g_assert (new->right == NULL);
1593 g_assert (node->parent == NULL);
1596 node->right->parent = new;
1598 new->right = node->right;
1603 node_update_fields (new);
1604 node_update_fields (node);
1608 node_get_length (EggSequenceNode *node)
1610 g_assert (node != NULL);
1613 return node->n_nodes;
1617 node_unlink (EggSequenceNode *node)
1619 EggSequenceNode *right, *left;
1624 right = node->right;
1626 node->parent = node->left = node->right = NULL;
1627 node_update_fields (node);
1631 right->parent = NULL;
1633 right = node_get_first (right);
1634 g_assert (right->left == NULL);
1639 left->parent = right;
1640 node_update_fields (right);
1645 left->parent = NULL;
1650 node_insert_sorted (EggSequenceNode *node,
1651 EggSequenceNode *new,
1652 EggSequenceNode *end,
1653 EggSequenceIterCompareFunc cmp_func,
1656 EggSequenceNode *closest;
1658 closest = node_find_closest (node, new, end, cmp_func, cmp_data);
1662 node_insert_before (closest, new);
1666 node_calc_height (EggSequenceNode *node)
1677 left_height = node_calc_height (node->left);
1680 right_height = node_calc_height (node->right);
1682 return MAX (left_height, right_height) + 1;
1688 /* Self test functions */
1691 check_node (EggSequenceNode *node)
1695 g_assert (node->parent != node);
1696 g_assert (node->n_nodes ==
1697 1 + get_n_nodes (node->left) + get_n_nodes (node->right));
1698 check_node (node->left);
1699 check_node (node->right);
1704 egg_sequence_self_test (EggSequence *seq)
1706 EggSequenceNode *node = splay (seq->end_node);