SortedList.vala 11.7 KB
Newer Older
Eric Gregory's avatar
Eric Gregory committed
1
/* Copyright 2009-2011 Yorba Foundation
2 3 4 5 6
 *
 * This software is licensed under the GNU LGPL (version 2.1 or later).
 * See the COPYING file in this distribution. 
 */

Jim Nelson's avatar
Jim Nelson committed
7
public delegate int64 Comparator(void *a, void *b);
8

9 10
extern string g_utf8_collate_key_for_filename(string str, ssize_t len = -1);

Jim Nelson's avatar
Jim Nelson committed
11
public int64 file_comparator(void *a, void *b) {
12 13 14 15 16 17 18 19 20 21 22
    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));
23
}
24

25
public class SortedList<G> : Object, Gee.Iterable<G>, Gee.Collection<G> {
26
    private Gee.ArrayList<G> list;
27
    private unowned Comparator? cmp;
28
    
Jim Nelson's avatar
Jim Nelson committed
29
    public SortedList(Comparator? cmp = null) {
30
        this.list = new Gee.ArrayList<G>();
31 32 33
        this.cmp = cmp;
    }
    
Jim Nelson's avatar
Jim Nelson committed
34 35
    public Type element_type {
        get { return typeof(G); } 
36 37 38 39 40 41 42
    }
    
    public Gee.Iterator<G?> iterator() {
        return list.iterator();
    }
    
    public bool add(G? item) {
43 44 45 46
        if (cmp == null)
            list.add(item);
        else
            list.insert(get_sorted_insert_pos(item), item);
47
        
48 49 50 51
#if VERIFY_SORTED_LIST
        assert(is_sorted());
#endif
        
52 53 54
        return true;
    }
    
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
    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) {
88 89 90 91 92 93 94
        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) {
Jim Nelson's avatar
Bug.  
Jim Nelson committed
95
                list.insert(get_sorted_insert_pos(items.get(0)), items.get(0));
96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
                added = true;
            } else {
                added = merge_sort(items);
            }
        } else {
            added = list.add_all(items);
        }
        
#if VERIFY_SORTED_LIST
        assert(is_sorted());
#endif
        
        return added;
    }
    
111 112 113 114 115 116 117 118
    public void clear() {
        list.clear();
    }
    
    public bool contains(G? item) {
        return list.contains(item);
    }
    
119 120 121 122 123 124 125 126 127 128
    public bool contains_all(Gee.Collection<G> collection) {
        return list.contains_all(collection);
    }
    
    public bool is_empty {
        get {
            return list.is_empty;
        }
    }
    
129 130 131 132
    public bool remove(G? item) {
        return list.remove(item);
    }
    
133 134 135 136 137 138
    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);
139 140
    }
    
141 142 143
    public int size {
        get { return list.size; }
    }
144 145 146 147 148
    
    public inline int get_count() {
        return list.size;
    }
    
149
    public G? get_at(int index) {
150 151 152
        return list.get(index);
    }
    
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
    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;
    }
    
180 181 182 183
    // 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.
184 185 186
    //
    // 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.
187
    public int index_of(G search) {
188
        return cmp != null ? binary_search(search, null) : locate(search, false);
189 190 191
    }
    
    // See notes at index_of for the difference between this method and it.
192 193
    public int locate(G search, bool altered, EqualFunc equal_func = direct_equal) {
        if (cmp == null || altered) {
194 195 196 197 198 199 200
            int count = list.size;
            for (int ctr = 0; ctr < count; ctr++) {
                if (equal_func(list.get(ctr), search))
                    return ctr;
            }
            
            return -1;
201 202
        }
        
203
        return binary_search(search, equal_func);
204 205
    }
    
206 207 208 209 210 211
    public Gee.Collection<G> read_only_view {
        owned get {
            return list.read_only_view;
        }
    }
    
212 213 214 215 216 217
    public Gee.List<G> read_only_view_as_list {
        owned get {
            return list.read_only_view;
        }
    }
    
218 219
    public G? remove_at(int index) {
        return list.remove_at(index);
220
    }
221
    
222 223 224 225
    public G[] to_array() {
        return list.to_array();
    }
    
Jim Nelson's avatar
Jim Nelson committed
226
    public void resort(Comparator new_cmp) {
227 228
        cmp = new_cmp;
        
229
        merge_sort();
230
        
231 232 233
#if VERIFY_SORTED_LIST
        assert(is_sorted());
#endif
234 235
    }
    
236 237
    // Returns true if item has moved.
    public bool resort_item(G item) {
238
        int index = locate(item, true);
Jim Nelson's avatar
Jim Nelson committed
239 240
        assert(index >= 0);
        
241 242 243 244 245
        int new_index = get_sorted_insert_pos(item);
        
        if (index == new_index)
            return false;
        
Jim Nelson's avatar
Jim Nelson committed
246 247 248 249 250 251 252 253 254 255 256
        // 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);
        }
257
        
258 259 260 261
#if VERIFY_SORTED_LIST
        assert(is_sorted());
#endif
        
262 263 264
        return true;
    }
    
265 266 267 268 269 270
    private int get_sorted_insert_pos(G? item) {
        int low = 0;
        int high = list.size;
        for (;;) {
            if (low == high)
                return low;
271
            
272
            int mid = low + ((high - low) / 2);
273 274 275 276
            
            // watch for the situation where the item is already in the list (can happen with
            // resort_item())
            G cmp_item = list.get(mid);
277 278 279 280 281
            if (item == cmp_item) {
                // if at the end of the list, add it there
                if (mid >= list.size - 1)
                    return list.size;
                
282
                cmp_item = list.get(mid + 1);
283
            }
284
            
Jim Nelson's avatar
Jim Nelson committed
285
            int64 result = cmp(item, cmp_item);
286 287 288 289 290 291 292 293
            if (result < 0)
                high = mid;
            else if (result > 0)
                low = mid + 1;
            else
                return mid;
        }
    }
294 295 296 297 298 299 300 301

    public SortedList<G> copy() {
        SortedList<G> copy = new SortedList<G>(cmp);

        copy.list.add_all(list);

        return copy;
    }
302 303 304 305 306 307 308 309
    
#if VERIFY_SORTED_LIST
    private bool is_sorted() {
        if (cmp == null)
            return true;
        
        int length = list.size;
        for (int ctr = 1; ctr < length; ctr++) {
Jim Nelson's avatar
Jim Nelson committed
310
            if (cmp(list.get(ctr - 1), list.get(ctr)) >= 0) {
311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341
                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) {
342
            int add_ctr = 0;
343
            while (offset < count) {
344
                array[offset] = add.get(add_ctr++);
345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
                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);
        
Jim Nelson's avatar
Jim Nelson committed
379
        if (cmp(array[middle_index - 1], array[middle_index]) > 0)
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398
            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];
            
Jim Nelson's avatar
Jim Nelson committed
399
            if (cmp(left, right) <= 0) {
400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
                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++];
    }
420
}
421