SortedList.vala 11.3 KB
Newer Older
1
/* Copyright 2016 Software Freedom Conservancy Inc.
2 3
 *
 * This software is licensed under the GNU LGPL (version 2.1 or later).
4
 * See the COPYING file in this distribution.
5 6
 */

7
public delegate int64 Comparator(void *a, void *b);
8

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

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

        copy.list.add_all(list);

        return copy;
    }
294 295 296 297 298 299 300 301
    
#if VERIFY_SORTED_LIST
    private bool is_sorted() {
        if (cmp == null)
            return true;
        
        int length = list.size;
        for (int ctr = 1; ctr < length; ctr++) {
302
            if (cmp(list.get(ctr - 1), list.get(ctr)) >= 0) {
303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
                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) {
334
            int add_ctr = 0;
335
            while (offset < count) {
336
                array[offset] = add.get(add_ctr++);
337 338 339 340 341 342 343 344 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
                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);
        
371
        if (cmp(array[middle_index - 1], array[middle_index]) > 0)
372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
            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];
            
391
            if (cmp(left, right) <= 0) {
392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411
                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++];
    }
412
}
413