diff options
Diffstat (limited to 'src/SortedList.vala')
| -rw-r--r-- | src/SortedList.vala | 429 |
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++]; + } +} + |