summaryrefslogtreecommitdiff
path: root/src/SortedList.vala
diff options
context:
space:
mode:
authorJörg Frings-Fürst <debian@jff-webhosting.net>2014-07-23 09:06:59 +0200
committerJörg Frings-Fürst <debian@jff-webhosting.net>2014-07-23 09:06:59 +0200
commit4ea2cc3bd4a7d9b1c54a9d33e6a1cf82e7c8c21d (patch)
treed2e54377d14d604356c86862a326f64ae64dadd6 /src/SortedList.vala
Imported Upstream version 0.18.1upstream/0.18.1
Diffstat (limited to 'src/SortedList.vala')
-rw-r--r--src/SortedList.vala429
1 files changed, 429 insertions, 0 deletions
diff --git a/src/SortedList.vala b/src/SortedList.vala
new file mode 100644
index 0000000..791f9e0
--- /dev/null
+++ b/src/SortedList.vala
@@ -0,0 +1,429 @@
+/* Copyright 2009-2014 Yorba Foundation
+ *
+ * This software is licensed under the GNU LGPL (version 2.1 or later).
+ * See the COPYING file in this distribution.
+ */
+
+public delegate int64 Comparator(void *a, void *b);
+
+extern string g_utf8_collate_key_for_filename(string str, ssize_t len = -1);
+
+public int64 file_comparator(void *a, void *b) {
+ string? path_a = ((File *) a)->get_path();
+ string? path_b = ((File *) b)->get_path();
+
+ // if both are null, treat as equal; if one but not the other, prioritize the non-null
+ if (path_a == null)
+ return (path_b == null) ? 0 : 1;
+
+ if (path_b == null)
+ return -1;
+
+ return strcmp(g_utf8_collate_key_for_filename(path_a), g_utf8_collate_key_for_filename(path_b));
+}
+
+public class SortedList<G> : Object, Gee.Traversable<G>, Gee.Iterable<G>, Gee.Collection<G> {
+ private Gee.ArrayList<G> list;
+ private unowned Comparator? cmp;
+
+ public SortedList(Comparator? cmp = null) {
+ this.list = new Gee.ArrayList<G>();
+ this.cmp = cmp;
+ }
+
+ public Type element_type {
+ get { return typeof(G); }
+ }
+
+ public bool read_only {
+ get { return list.read_only; }
+ }
+
+ public Gee.Iterator<G?> iterator() {
+ return list.iterator();
+ }
+
+ public bool foreach(Gee.ForallFunc<G> f) {
+ return list.foreach(f);
+ }
+
+ public bool add(G? item) {
+ if (cmp == null)
+ list.add(item);
+ else
+ list.insert(get_sorted_insert_pos(item), item);
+
+#if VERIFY_SORTED_LIST
+ assert(is_sorted());
+#endif
+
+ return true;
+ }
+
+ public bool add_all(Gee.Collection<G> collection) {
+ if (collection.size == 0)
+ return false;
+
+ Gee.List<G> as_list = collection as Gee.List<G>;
+ if (as_list != null)
+ return add_list(as_list);
+
+ if (cmp == null)
+ return list.add_all(collection);
+
+ bool changed = false;
+ if (collection.size == 1) {
+ Gee.Iterator<G> iter = collection.iterator();
+ iter.next();
+ G item = iter.get();
+
+ list.insert(get_sorted_insert_pos(item), item);
+ changed = true;
+ } else {
+ Gee.List<G> items = new Gee.ArrayList<G>();
+ items.add_all(collection);
+
+ changed = merge_sort(items);
+ }
+
+#if VERIFY_SORTED_LIST
+ assert(is_sorted());
+#endif
+ return changed;
+ }
+
+ public bool add_list(Gee.List<G> items) {
+ bool added = false;
+ if (items.size == 0) {
+ // do nothing, return false
+ } else if (cmp != null) {
+ // don't use a full merge sort if the number of items is one ... a binary
+ // insertion sort with the insert is quicker
+ if (items.size == 1) {
+ list.insert(get_sorted_insert_pos(items.get(0)), items.get(0));
+ added = true;
+ } else {
+ added = merge_sort(items);
+ }
+ } else {
+ added = list.add_all(items);
+ }
+
+#if VERIFY_SORTED_LIST
+ assert(is_sorted());
+#endif
+
+ return added;
+ }
+
+ public void clear() {
+ list.clear();
+ }
+
+ public bool contains(G? item) {
+ return list.contains(item);
+ }
+
+ public bool contains_all(Gee.Collection<G> collection) {
+ return list.contains_all(collection);
+ }
+
+ public bool is_empty {
+ get {
+ return list.is_empty;
+ }
+ }
+
+ public bool remove(G? item) {
+ return list.remove(item);
+ }
+
+ public bool remove_all(Gee.Collection<G> collection) {
+ return list.remove_all(collection);
+ }
+
+ public bool retain_all(Gee.Collection<G> collection) {
+ return list.retain_all(collection);
+ }
+
+ public int size {
+ get { return list.size; }
+ }
+
+ public inline int get_count() {
+ return list.size;
+ }
+
+ public G? get_at(int index) {
+ return list.get(index);
+ }
+
+ private int binary_search(G search, EqualFunc? equal_func) {
+ assert(cmp != null);
+
+ int min = 0;
+ int max = list.size;
+ for (;;) {
+ int mid = min + ((max - min) / 2);
+ G item = list.get(mid);
+
+ if (equal_func != null && equal_func(item, search))
+ return mid;
+
+ int64 compare = cmp(item, search);
+ if (compare == 0)
+ return mid;
+ else if (compare > 0)
+ max = mid - 1;
+ else
+ min = mid + 1;
+
+ if (min > max)
+ break;
+ }
+
+ return -1;
+ }
+
+ // index_of uses the Comparator to find the item being searched for. Because SortedList allows
+ // for items identified as equal by the Comparator to co-exist in the list, this method will
+ // return the first item found where its compare() method returns zero. Use locate() if a
+ // specific EqualFunc is required for searching.
+ //
+ // Also, index_of() cannot be reliably used to find an item if it has been altered in such a
+ // way that it is no longer sorted properly. Use locate() for that.
+ public int index_of(G search) {
+ return cmp != null ? binary_search(search, null) : locate(search, false);
+ }
+
+ // See notes at index_of for the difference between this method and it.
+ public int locate(G search, bool altered, EqualFunc equal_func = direct_equal) {
+ if (cmp == null || altered) {
+ int count = list.size;
+ for (int ctr = 0; ctr < count; ctr++) {
+ if (equal_func(list.get(ctr), search))
+ return ctr;
+ }
+
+ return -1;
+ }
+
+ return binary_search(search, equal_func);
+ }
+
+ public Gee.Collection<G> read_only_view {
+ owned get {
+ return list.read_only_view;
+ }
+ }
+
+ public Gee.List<G> read_only_view_as_list {
+ owned get {
+ return list.read_only_view;
+ }
+ }
+
+ public G? remove_at(int index) {
+ return list.remove_at(index);
+ }
+
+ public G[] to_array() {
+ return list.to_array();
+ }
+
+ public void resort(Comparator new_cmp) {
+ cmp = new_cmp;
+
+ merge_sort();
+
+#if VERIFY_SORTED_LIST
+ assert(is_sorted());
+#endif
+ }
+
+ // Returns true if item has moved.
+ public bool resort_item(G item) {
+ int index = locate(item, true);
+ assert(index >= 0);
+
+ int new_index = get_sorted_insert_pos(item);
+
+ if (index == new_index)
+ return false;
+
+ // insert in such a way to avoid index shift (performing the rightmost
+ // operation before the leftmost)
+ if (new_index > index) {
+ list.insert(new_index, item);
+ G removed_item = list.remove_at(index);
+ assert(item == removed_item);
+ } else {
+ G removed_item = list.remove_at(index);
+ assert(item == removed_item);
+ list.insert(new_index, item);
+ }
+
+#if VERIFY_SORTED_LIST
+ assert(is_sorted());
+#endif
+
+ return true;
+ }
+
+ private int get_sorted_insert_pos(G? item) {
+ int low = 0;
+ int high = list.size;
+ for (;;) {
+ if (low == high)
+ return low;
+
+ int mid = low + ((high - low) / 2);
+
+ // watch for the situation where the item is already in the list (can happen with
+ // resort_item())
+ G cmp_item = list.get(mid);
+ if (item == cmp_item) {
+ // if at the end of the list, add it there
+ if (mid >= list.size - 1)
+ return list.size;
+
+ cmp_item = list.get(mid + 1);
+ }
+
+ int64 result = cmp(item, cmp_item);
+ if (result < 0)
+ high = mid;
+ else if (result > 0)
+ low = mid + 1;
+ else
+ return mid;
+ }
+ }
+
+ public SortedList<G> copy() {
+ SortedList<G> copy = new SortedList<G>(cmp);
+
+ copy.list.add_all(list);
+
+ return copy;
+ }
+
+#if VERIFY_SORTED_LIST
+ private bool is_sorted() {
+ if (cmp == null)
+ return true;
+
+ int length = list.size;
+ for (int ctr = 1; ctr < length; ctr++) {
+ if (cmp(list.get(ctr - 1), list.get(ctr)) >= 0) {
+ critical("Out of order: %d and %d", ctr - 1, ctr);
+
+ return false;
+ }
+ }
+
+ return true;
+ }
+#endif
+
+ private bool merge_sort(Gee.List<G>? add = null) {
+ assert(cmp != null);
+
+ int list_count = list.size;
+ int add_count = (add != null) ? add.size : 0;
+
+ int count = list_count + add_count;
+ if (count == 0)
+ return false;
+
+ // because list access is slow in large-scale sorts, flatten list (with additions) to
+ // an array, merge sort that, and then place them back in the internal ArrayList.
+ G[] array = new G[count];
+ int offset = 0;
+
+ while (offset < list_count) {
+ array[offset] = list.get(offset);
+ offset++;
+ }
+
+ if (add != null) {
+ int add_ctr = 0;
+ while (offset < count) {
+ array[offset] = add.get(add_ctr++);
+ offset++;
+ }
+ }
+
+ assert(offset == count);
+
+ _merge_sort(array, new G[count], 0, count - 1);
+
+ offset = 0;
+ while (offset < list_count) {
+ list.set(offset, array[offset]);
+ offset++;
+ }
+
+ while (offset < count) {
+ list.insert(offset, array[offset]);
+ offset++;
+ }
+
+ return true;
+ }
+
+ private void _merge_sort(G[] array, G[] scratch, int start_index, int end_index) {
+ assert(start_index <= end_index);
+
+ int count = end_index - start_index + 1;
+ if (count <= 1)
+ return;
+
+ int middle_index = start_index + (count / 2);
+
+ _merge_sort(array, scratch, start_index, middle_index - 1);
+ _merge_sort(array, scratch, middle_index, end_index);
+
+ if (cmp(array[middle_index - 1], array[middle_index]) > 0)
+ merge(array, scratch, start_index, middle_index, end_index);
+ }
+
+ private void merge(G[] array, G[] scratch, int start_index, int middle_index, int end_index) {
+ assert(start_index < end_index);
+
+ int count = end_index - start_index + 1;
+ int left_start = start_index;
+ int left_end = middle_index - 1;
+ int right_start = middle_index;
+ int right_end = end_index;
+
+ assert(scratch.length >= count);
+ int scratch_index = 0;
+
+ while (left_start <= left_end && right_start <= right_end) {
+ G left = array[left_start];
+ G right = array[right_start];
+
+ if (cmp(left, right) <= 0) {
+ scratch[scratch_index++] = left;
+ left_start++;
+ } else {
+ scratch[scratch_index++] = right;
+ right_start++;
+ }
+ }
+
+ while (left_start <= left_end)
+ scratch[scratch_index++] = array[left_start++];
+
+ while (right_start <= right_end)
+ scratch[scratch_index++] = array[right_start++];
+
+ assert(scratch_index == count);
+
+ scratch_index = 0;
+ for (int list_index = start_index; list_index <= end_index; list_index++)
+ array[list_index] = scratch[scratch_index++];
+ }
+}
+