[vala/wip/merge-valadoc: 3/5] gee: Add some useful symbols from gee-0.8



commit 3106d1b46a6b72ccff4e7115749ae84012263bf2
Author: Rico Tzschichholz <ricotz ubuntu com>
Date:   Thu Jun 1 11:22:27 2017 +0200

    gee: Add some useful symbols from gee-0.8

 ccode/valaccodefunction.vala     |    7 +-
 codegen/valaccodebasemodule.vala |   12 +-
 gee/Makefile.am                  |    1 +
 gee/arraylist.vala               |   33 ++-
 gee/collection.vala              |  165 +++++++++
 gee/hashmap.vala                 |   74 ++++-
 gee/hashset.vala                 |   60 +++-
 gee/iterator.vala                |   20 +
 gee/list.vala                    |   46 +++-
 gee/timsort.vala                 |  713 ++++++++++++++++++++++++++++++++++++++
 vala/valaflowanalyzer.vala       |    9 +-
 vala/valagirparser.vala          |    6 +-
 12 files changed, 1101 insertions(+), 45 deletions(-)
---
diff --git a/ccode/valaccodefunction.vala b/ccode/valaccodefunction.vala
index ef8dad6..91addcd 100644
--- a/ccode/valaccodefunction.vala
+++ b/ccode/valaccodefunction.vala
@@ -220,11 +220,9 @@ public class Vala.CCodeFunction : CCodeNode {
        }
 
        public void else_if (CCodeExpression condition) {
-               var parent_if = (CCodeIfStatement) statement_stack[statement_stack.size - 1];
+               var parent_if = (CCodeIfStatement) statement_stack.remove_at (statement_stack.size - 1);
                assert (parent_if.false_statement == null);
 
-               statement_stack.remove_at (statement_stack.size - 1);
-
                current_block = new CCodeBlock ();
 
                var cif = new CCodeIfStatement (condition, current_block);
@@ -318,8 +316,7 @@ public class Vala.CCodeFunction : CCodeNode {
 
        public void close () {
                do {
-                       var top = statement_stack[statement_stack.size - 1];
-                       statement_stack.remove_at (statement_stack.size - 1);
+                       var top = statement_stack.remove_at (statement_stack.size - 1);
                        current_block = top as CCodeBlock;
                } while (current_block == null);
        }
diff --git a/codegen/valaccodebasemodule.vala b/codegen/valaccodebasemodule.vala
index b6bb770..7e87b47 100644
--- a/codegen/valaccodebasemodule.vala
+++ b/codegen/valaccodebasemodule.vala
@@ -53,8 +53,7 @@ public abstract class Vala.CCodeBaseModule : CodeGenerator {
                }
 
                public void pop_symbol () {
-                       current_symbol = symbol_stack[symbol_stack.size - 1];
-                       symbol_stack.remove_at (symbol_stack.size - 1);
+                       current_symbol = symbol_stack.remove_at (symbol_stack.size - 1);
                }
        }
 
@@ -568,8 +567,7 @@ public abstract class Vala.CCodeBaseModule : CodeGenerator {
 
        public void pop_context () {
                if (emit_context_stack.size > 0) {
-                       this.emit_context = emit_context_stack[emit_context_stack.size - 1];
-                       emit_context_stack.remove_at (emit_context_stack.size - 1);
+                       this.emit_context = emit_context_stack.remove_at (emit_context_stack.size - 1);
                        if (ccode != null) {
                                ccode.current_line = current_line;
                        }
@@ -589,8 +587,7 @@ public abstract class Vala.CCodeBaseModule : CodeGenerator {
        }
 
        public void pop_line () {
-               current_line = line_directive_stack[line_directive_stack.size - 1];
-               line_directive_stack.remove_at (line_directive_stack.size - 1);
+               current_line = line_directive_stack.remove_at (line_directive_stack.size - 1);
                if (ccode != null) {
                        ccode.current_line = current_line;
                }
@@ -603,8 +600,7 @@ public abstract class Vala.CCodeBaseModule : CodeGenerator {
        }
 
        public void pop_function () {
-               emit_context.ccode = emit_context.ccode_stack[emit_context.ccode_stack.size - 1];
-               emit_context.ccode_stack.remove_at (emit_context.ccode_stack.size - 1);
+               emit_context.ccode = emit_context.ccode_stack.remove_at (emit_context.ccode_stack.size - 1);
                if (ccode != null) {
                        ccode.current_line = current_line;
                }
diff --git a/gee/Makefile.am b/gee/Makefile.am
index 04dcf37..fd8779c 100644
--- a/gee/Makefile.am
+++ b/gee/Makefile.am
@@ -24,6 +24,7 @@ libgee_la_VALASOURCES = \
        list.vala \
        map.vala \
        set.vala \
+       timsort.vala \
        $(NULL)
 
 libgee_la_SOURCES = \
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
index fe398e4..80b20e9 100644
--- a/gee/arraylist.vala
+++ b/gee/arraylist.vala
@@ -36,8 +36,8 @@ public class Vala.ArrayList<G> : List<G> {
                set { _equal_func = value; }
        }
 
-       private G[] _items = new G[4];
-       private int _size;
+       internal G[] _items = new G[4];
+       internal int _size;
        private EqualFunc<G> _equal_func;
 
        // concurrent modification protection
@@ -110,14 +110,16 @@ public class Vala.ArrayList<G> : List<G> {
                return false;
        }
 
-       public override void remove_at (int index) {
+       public override G remove_at (int index) {
                assert (index >= 0 && index < _size);
 
+               G item = _items[index];
                _items[index] = null;
 
                shift (index + 1, -1);
 
                _stamp++;
+               return item;
        }
 
        public override void clear () {
@@ -162,6 +164,7 @@ public class Vala.ArrayList<G> : List<G> {
 
                private ArrayList<G> _list;
                private int _index = -1;
+               protected bool _removed = false;
 
                // concurrent modification protection
                public int _stamp = 0;
@@ -174,12 +177,19 @@ public class Vala.ArrayList<G> : List<G> {
                        assert (_stamp == _list._stamp);
                        if (_index < _list._size) {
                                _index++;
+                               _removed = false;
                        }
                        return (_index < _list._size);
                }
 
+               public override bool has_next () {
+                       assert (_stamp == _list._stamp);
+                       return (_index + 1 < _list._size);
+               }
+
                public override G? get () {
                        assert (_stamp == _list._stamp);
+                       assert (! _removed);
 
                        if (_index < 0 || _index >= _list._size) {
                                return null;
@@ -187,6 +197,23 @@ public class Vala.ArrayList<G> : List<G> {
 
                        return _list.get (_index);
                }
+
+               public override void remove () {
+                       assert (_stamp == _list._stamp);
+                       assert (! _removed && _index >= 0);
+                       assert (_index < _list._size);
+
+                       _list.remove_at (_index);
+                       _index--;
+                       _removed = true;
+                       _stamp = _list._stamp;
+               }
+
+               public override bool valid {
+                       get {
+                               return _index >= 0 && _index < _list._size && ! _removed;
+                       }
+               }
        }
 }
 
diff --git a/gee/collection.vala b/gee/collection.vala
index 76f568a..8416223 100644
--- a/gee/collection.vala
+++ b/gee/collection.vala
@@ -31,6 +31,11 @@ public abstract class Vala.Collection<G> : Iterable<G> {
        public abstract int size { get; }
 
        /**
+        * Specifies whether this collection is empty.
+        */
+       public virtual bool is_empty { get { return size == 0; } }
+
+       /**
         * Determines whether this collection contains the specified item.
         *
         * @param item the item to locate in the collection
@@ -64,5 +69,165 @@ public abstract class Vala.Collection<G> : Iterable<G> {
         * read-only collections.
         */
        public abstract void clear ();
+
+       /**
+        * Adds all items in the input collection to this collection.
+        *
+        * @param collection the collection which items will be added to this
+        *                   collection.
+        *
+        * @return     ``true`` if the collection has been changed, ``false`` otherwise
+        */
+       public virtual bool add_all (Collection<G> collection) {
+               bool changed = false;
+               for (Iterator<G> iter = collection.iterator (); iter.next ();) {
+                       G item = iter.get ();
+                       if (!contains (item)) {
+                               add (item);
+                               changed = true;
+                       }
+               }
+               return changed;
+       }
+
+       /**
+        * Returns an array containing all of items from this collection.
+        *
+        * @return an array containing all of items from this collection
+        */
+       public virtual G[] to_array () {
+               var t = typeof (G);
+               if (t == typeof (bool)) {
+                       return (G[]) to_bool_array ((Collection<bool>) this);
+               } else if (t == typeof (char)) {
+                       return (G[]) to_char_array ((Collection<char>) this);
+               } else if (t == typeof (uchar)) {
+                       return (G[]) to_uchar_array ((Collection<uchar>) this);
+               } else if (t == typeof (int)) {
+                       return (G[]) to_int_array ((Collection<int>) this);
+               } else if (t == typeof (uint)) {
+                       return (G[]) to_uint_array ((Collection<uint>) this);
+               } else if (t == typeof (int64)) {
+                       return (G[]) to_int64_array ((Collection<int64>) this);
+               } else if (t == typeof (uint64)) {
+                       return (G[]) to_uint64_array ((Collection<uint64>) this);
+               } else if (t == typeof (long)) {
+                       return (G[]) to_long_array ((Collection<long>) this);
+               } else if (t == typeof (ulong)) {
+                       return (G[]) to_ulong_array ((Collection<ulong>) this);
+               } else if (t == typeof (float)) {
+                       return (G[]) to_float_array ((Collection<float>) this);
+               } else if (t == typeof (double)) {
+                       return (G[]) to_double_array ((Collection<double>) this);
+               } else if (t.is_enum () || t.is_flags ()) {
+                       return (G[]) to_int_array ((Collection<int>) this);
+               } else {
+                       G[] array = new G[size];
+                       int index = 0;
+                       foreach (G element in this) {
+                               array[index++] = (owned)element;
+                       }
+                       return array;
+               }
+       }
+
+       private static bool[] to_bool_array (Collection<bool> coll) {
+               bool[] array = new bool[coll.size];
+               int index = 0;
+               foreach (bool element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static char[] to_char_array (Collection<char> coll) {
+               char[] array = new char[coll.size];
+               int index = 0;
+               foreach (char element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static uchar[] to_uchar_array (Collection<uchar> coll) {
+               uchar[] array = new uchar[coll.size];
+               int index = 0;
+               foreach (uchar element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static int[] to_int_array (Collection<int> coll) {
+               int[] array = new int[coll.size];
+               int index = 0;
+               foreach (int element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static uint[] to_uint_array (Collection<uint> coll) {
+               uint[] array = new uint[coll.size];
+               int index = 0;
+               foreach (uint element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static int64?[] to_int64_array (Collection<int64?> coll) {
+               int64?[] array = new int64?[coll.size];
+               int index = 0;
+               foreach (int64? element in coll) {
+                       array[index++] = (owned)element;
+               }
+               return array;
+       }
+
+       private static uint64?[] to_uint64_array (Collection<uint64?> coll) {
+               uint64?[] array = new uint64?[coll.size];
+               int index = 0;
+               foreach (uint64? element in coll) {
+                       array[index++] = (owned)element;
+               }
+               return array;
+       }
+
+       private static long[] to_long_array (Collection<long> coll) {
+               long[] array = new long[coll.size];
+               int index = 0;
+               foreach (long element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static ulong[] to_ulong_array (Collection<ulong> coll) {
+               ulong[] array = new ulong[coll.size];
+               int index = 0;
+               foreach (ulong element in coll) {
+                       array[index++] = element;
+               }
+               return array;
+       }
+
+       private static float?[] to_float_array (Collection<float?> coll) {
+               float?[] array = new float?[coll.size];
+               int index = 0;
+               foreach (float? element in coll) {
+                       array[index++] = (owned)element;
+               }
+               return array;
+       }
+
+       private static double?[] to_double_array (Collection<double?> coll) {
+               double?[] array = new double?[coll.size];
+               int index = 0;
+               foreach (double? element in coll) {
+                       array[index++] = (owned)element;
+               }
+               return array;
+       }
 }
 
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
index 9085f10..8590c7d 100644
--- a/gee/hashmap.vala
+++ b/gee/hashmap.vala
@@ -282,6 +282,7 @@ public class Vala.HashMap<K,V> : Map<K,V> {
                private HashMap<K,V> _map;
                private int _index = -1;
                private weak Node<K,V> _node;
+               private weak Node<K,V> _next;
 
                // concurrent modification protection
                private int _stamp;
@@ -291,21 +292,45 @@ public class Vala.HashMap<K,V> : Map<K,V> {
                }
 
                public override bool next () {
-                       if (_node != null) {
-                               _node = _node.next;
-                       }
-                       while (_node == null && _index + 1 < _map._array_size) {
-                               _index++;
-                               _node = _map._nodes[_index];
+                       assert (_stamp == _map._stamp);
+                       if (!has_next ()) {
+                               return false;
                        }
+                       _node = _next;
+                       _next = null;
                        return (_node != null);
                }
 
+               public override bool has_next () {
+                       assert (_stamp == _map._stamp);
+                       if (_next == null) {
+                               _next = _node;
+                               if (_next != null) {
+                                       _next = _next.next;
+                               }
+                               while (_next == null && _index + 1 < _map._array_size) {
+                                       _index++;
+                                       _next = _map._nodes[_index];
+                               }
+                       }
+                       return (_next != null);
+               }
+
                public override K? get () {
                        assert (_stamp == _map._stamp);
                        assert (_node != null);
                        return _node.key;
                }
+
+               public override void remove () {
+                       assert_not_reached ();
+               }
+
+               public override bool valid {
+                       get {
+                               return _node != null;
+                       }
+               }
        }
 
        private class ValueCollection<K,V> : Collection<V> {
@@ -365,6 +390,7 @@ public class Vala.HashMap<K,V> : Map<K,V> {
                private HashMap<V,K> _map;
                private int _index = -1;
                private weak Node<K,V> _node;
+               private weak Node<K,V> _next;
 
                // concurrent modification protection
                private int _stamp;
@@ -374,21 +400,45 @@ public class Vala.HashMap<K,V> : Map<K,V> {
                }
 
                public override bool next () {
-                       if (_node != null) {
-                               _node = _node.next;
-                       }
-                       while (_node == null && _index + 1 < _map._array_size) {
-                               _index++;
-                               _node = _map._nodes[_index];
+                       assert (_stamp == _map._stamp);
+                       if (!has_next ()) {
+                               return false;
                        }
+                       _node = _next;
+                       _next = null;
                        return (_node != null);
                }
 
+               public override bool has_next () {
+                       assert (_stamp == _map._stamp);
+                       if (_next == null) {
+                               _next = _node;
+                               if (_next != null) {
+                                       _next = _next.next;
+                               }
+                               while (_next == null && _index + 1 < _map._array_size) {
+                                       _index++;
+                                       _next = _map._nodes[_index];
+                               }
+                       }
+                       return (_next != null);
+               }
+
                public override V? get () {
                        assert (_stamp == _map._stamp);
                        assert (_node != null);
                        return _node.value;
                }
+
+               public override void remove () {
+                       assert_not_reached ();
+               }
+
+               public override bool valid {
+                       get {
+                               return _node != null;
+                       }
+               }
        }
 }
 
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 6ca0dfa..ff20e81 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -127,6 +127,24 @@ public class Vala.HashSet<G> : Set<G> {
                resize ();
        }
 
+       private inline bool remove_helper (G key) {
+               Node<G>** node = lookup_node (key);
+               if (*node != null) {
+                       assert (*node != null);
+                       Node<G> next = (owned) (*node)->next;
+
+                       (*node)->key = null;
+                       delete *node;
+
+                       *node = (owned) next;
+
+                       _nnodes--;
+                       _stamp++;
+                       return true;
+               }
+               return false;
+       }
+
        private void resize () {
                if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
                    (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
@@ -177,6 +195,7 @@ public class Vala.HashSet<G> : Set<G> {
                private HashSet<G> _set;
                private int _index = -1;
                private weak Node<G> _node;
+               private weak Node<G> _next;
 
                // concurrent modification protection
                private int _stamp = 0;
@@ -186,21 +205,50 @@ public class Vala.HashSet<G> : Set<G> {
                }
 
                public override bool next () {
-                       if (_node != null) {
-                               _node = _node.next;
-                       }
-                       while (_node == null && _index + 1 < _set._array_size) {
-                               _index++;
-                               _node = _set._nodes[_index];
+                       assert (_stamp == _set._stamp);
+                       if (!has_next ()) {
+                               return false;
                        }
+                       _node = _next;
+                       _next = null;
                        return (_node != null);
                }
 
+               public override bool has_next () {
+                       assert (_stamp == _set._stamp);
+                       if (_next == null) {
+                               _next = _node;
+                               if (_next != null) {
+                                       _next = _next.next;
+                               }
+                               while (_next == null && _index + 1 < _set._array_size) {
+                                       _index++;
+                                       _next = _set._nodes[_index];
+                               }
+                       }
+                       return (_next != null);
+               }
+
                public override G? get () {
                        assert (_stamp == _set._stamp);
                        assert (_node != null);
                        return _node.key;
                }
+
+               public override void remove () {
+                       assert (_stamp == _set._stamp);
+                       assert (_node != null);
+                       has_next ();
+                       _set.remove_helper (_node.key);
+                       _node = null;
+                       _stamp = _set._stamp;
+               }
+
+               public override bool valid {
+                       get {
+                               return _node != null;
+                       }
+               }
        }
 }
 
diff --git a/gee/iterator.vala b/gee/iterator.vala
index 5190fb6..224fa62 100644
--- a/gee/iterator.vala
+++ b/gee/iterator.vala
@@ -33,10 +33,30 @@ public abstract class Vala.Iterator<G> {
        public abstract bool next ();
 
        /**
+        * Checks whether there is a next element in the iteration.
+        *
+        * @return ``true`` if the iterator has a next element
+        */
+       public abstract bool has_next ();
+
+       /**
         * Returns the current element in the iteration.
         *
         * @return the current element in the iteration
         */
        public abstract G? get ();
+
+       /**
+        * Removes the current element in the iteration. The cursor is set in an
+        * in-between state. Both {@link get} and {@link remove} will fail until
+        * the next move of the cursor (calling {@link next}).
+        */
+       public abstract void remove ();
+
+       /**
+        * Determines wheather the call to {@link get} is legal. It is false at the
+        * beginning and after {@link remove} call and true otherwise.
+        */
+       public abstract bool valid { get; }
 }
 
diff --git a/gee/list.vala b/gee/list.vala
index d730283..57ba35d 100644
--- a/gee/list.vala
+++ b/gee/list.vala
@@ -61,7 +61,51 @@ public abstract class Vala.List<G> : Collection<G> {
         * Removes the item at the specified index of this list.
         *
         * @param index zero-based index of the item to be removed
+        *
+        * @return      the removed element
+        */
+       public abstract G remove_at (int index);
+
+       /**
+        * Returns the first item of the list. Fails if the list is empty.
+        *
+        * @return      first item in the list
+        */
+       public virtual G first () {
+               return @get (0);
+       }
+
+       /**
+        * Returns the last item of the list. Fails if the list is empty.
+        *
+        * @return      last item in the list
+        */
+       public virtual G last () {
+               return @get (size - 1);
+       }
+
+       /**
+        * Inserts items into this list for the input collection at the
+        * specified position.
+        *
+        * @param index zero-based index of the items to be inserted
+        * @param collection collection of items to be inserted
+        */
+       public virtual void insert_all (int index, Collection<G> collection) {
+               for (Iterator<G> iter = collection.iterator (); iter.next ();) {
+                       G item = iter.get ();
+                       insert (index, item);
+                       index++;
+               }
+       }
+
+       /**
+        * Sorts items by comparing with the specified compare function.
+        *
+        * @param compare_func compare function to use to compare items
         */
-       public abstract void remove_at (int index);
+       public virtual void sort (owned CompareDataFunc<G> compare_func) {
+               TimSort.sort<G> (this, compare_func);
+       }
 }
 
diff --git a/gee/timsort.vala b/gee/timsort.vala
new file mode 100644
index 0000000..58c4d08
--- /dev/null
+++ b/gee/timsort.vala
@@ -0,0 +1,713 @@
+/* timsort.vala
+ *
+ * Copyright (C) 2009  Didier Villevalois
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
+ *
+ * Author:
+ *     Didier 'Ptitjes Villevalois <ptitjes free fr>
+ */
+
+/**
+ * A stable, adaptive, iterative mergesort that requires far fewer than n*lg(n)
+ * comparisons when running on partially sorted arrays, while offering
+ * performance comparable to a traditional mergesort when run on random arrays.
+ * Like all proper mergesorts, this sort is stable and runs O(n*log(n)) time
+ * (worst case). In the worst case, this sort requires temporary storage space
+ * for n/2 object references; in the best case, it requires only a small
+ * constant amount of space.
+ *
+ * This implementation was adapted from Tim Peters's list sort for Python,
+ * which is described in detail here:
+ *   [[http://svn.python.org/projects/python/trunk/Objects/listsort.txt]]
+ *
+ * Tim's C code may be found here:
+ *   [[http://svn.python.org/projects/python/trunk/Objects/listobject.c]]
+ *
+ * The underlying techniques are described in this paper (and may have even
+ * earlier origins):
+ *
+ *   "Optimistic Sorting and Information Theoretic Complexity"
+ *   Peter McIlroy
+ *   SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp
+ *   467-474, Austin, Texas, 25-27 January 1993.
+ */
+internal class Vala.TimSort<G> {
+
+       public static void sort<G> (List<G> list, CompareDataFunc<G> compare) {
+               if (list is ArrayList) {
+                       TimSort.sort_arraylist<G> ((ArrayList<G>) list, compare);
+               } else {
+                       TimSort.sort_list<G> (list, compare);
+               }
+       }
+
+       private static void sort_list<G> (List<G> list, CompareDataFunc<G> compare) {
+               TimSort<G> helper = new TimSort<G> ();
+
+               helper.list_collection = list;
+               helper.array = list.to_array ();
+               helper.list = helper.array;
+               helper.index = 0;
+               helper.size = list.size;
+               helper.compare = compare;
+
+               helper.do_sort ();
+
+               // TODO Use a list iterator and use iter.set (item)
+               list.clear ();
+               foreach (G item in helper.array) {
+                       list.add (item);
+               }
+       }
+
+       private static void sort_arraylist<G> (ArrayList<G> list, CompareDataFunc<G> compare) {
+               TimSort<G> helper = new TimSort<G> ();
+
+               helper.list_collection = list;
+               helper.list = list._items;
+               helper.index = 0;
+               helper.size = list._size;
+               helper.compare = compare;
+
+               helper.do_sort ();
+       }
+
+       private const int MINIMUM_GALLOP = 7;
+
+       private List<G> list_collection;
+       private G[] array;
+       private void** list;
+       private int index;
+       private int size;
+       private Slice<G>[] pending;
+       private int minimum_gallop;
+       private unowned CompareDataFunc<G> compare;
+
+       private void do_sort () {
+               if (size < 2) {
+                       return;
+               }
+
+               pending = new Slice<G>[0];
+               minimum_gallop = MINIMUM_GALLOP;
+
+               Slice<G> remaining = new Slice<G> (list, index, size);
+               int minimum_length = compute_minimum_run_length (remaining.length);
+
+               while (remaining.length > 0) {
+                       // Get the next run
+                       bool descending;
+                       Slice<G> run = compute_longest_run (remaining, out descending);
+                       #if DEBUG
+                               message ("New run (%d, %d) %s", run.index, run.length,
+                                        descending ? "descending" : "ascending");
+                       #endif
+                       if (descending) {
+                               run.reverse ();
+                       }
+
+                       // Extend it to minimum_length, if needed
+                       if (run.length < minimum_length) {
+                               int sorted_count = run.length;
+                               run.length = int.min (minimum_length, remaining.length);
+                               insertion_sort (run, sorted_count);
+                               #if DEBUG
+                                       message ("Extended to (%d, %d) and sorted from index %d",
+                                                run.index, run.length, sorted_count);
+                               #endif
+                       }
+
+                       // Move remaining after run
+                       remaining.shorten_start (run.length);
+
+                       // Add run to pending runs and try to merge
+                       pending += (owned) run;
+                       merge_collapse ();
+               }
+
+               assert (remaining.index == size);
+
+               merge_force_collapse ();
+
+               assert (pending.length == 1);
+               assert (pending[0].index == 0);
+               assert (pending[0].length == size);
+       }
+
+       private delegate bool LowerFunc (G left, G right);
+
+       private inline bool lower_than (G left, G right) {
+            return compare (left, right) < 0;
+       }
+
+       private inline bool lower_than_or_equal_to (G left, G right) {
+            return compare (left, right) <= 0;
+       }
+
+       private int compute_minimum_run_length (int length) {
+               int run_length = 0;
+               while (length >= 64) {
+                       run_length |= length & 1;
+                       length >>= 1;
+               }
+               return length + run_length;
+       }
+
+       private Slice<G> compute_longest_run (Slice<G> a, out bool descending) {
+               int run_length;
+               if (a.length <= 1) {
+                       run_length = a.length;
+                       descending = false;
+               } else {
+                       run_length = 2;
+                       if (lower_than (a.list[a.index + 1], a.list[a.index])) {
+                               descending = true;
+                               for (int i = a.index + 2; i < a.index + a.length; i++) {
+                                       if (lower_than (a.list[i], a.list[i-1])) {
+                                               run_length++;
+                                       } else {
+                                               break;
+                                       }
+                               }
+                       } else {
+                               descending = false;
+                               for (int i = a.index + 2; i < a.index + a.length; i++) {
+                                       if (lower_than (a.list[i], a.list[i-1])) {
+                                               break;
+                                       } else {
+                                               run_length++;
+                                       }
+                               }
+                       }
+               }
+               return new Slice<G> (a.list, a.index, run_length);
+       }
+
+       private void insertion_sort (Slice<G> a, int offset) {
+               #if DEBUG
+                       message ("Sorting (%d, %d) at %d", a.index, a.length, offset);
+               #endif
+               for (int start = a.index + offset; start < a.index + a.length; start++) {
+                       int left = a.index;
+                       int right = start;
+                       void* pivot = a.list[right];
+
+                       while (left < right) {
+                               int p = left + ((right - left) >> 1);
+                               if (lower_than (pivot, a.list[p])) {
+                                       right = p;
+                               } else {
+                                       left = p + 1;
+                               }
+                       }
+                       assert (left == right);
+
+                       Memory.move (&a.list[left + 1], &a.list[left], sizeof (G) * (start - left));
+                       a.list[left] = pivot;
+               }
+       }
+
+       private void merge_collapse () {
+               #if DEBUG
+                       message ("Merge Collapse");
+               #endif
+               int count = pending.length;
+               while (count > 1) {
+                       #if DEBUG
+                               message ("Pending count: %d", count);
+                               if (count >= 3) {
+                                       message ("pending[count-3]=%p; pending[count-2]=%p; 
pending[count-1]=%p",
+                                                pending[count-3], pending[count-2], pending[count-1]);
+                               }
+                       #endif
+                       if (count >= 3 && pending[count-3].length <= pending[count-2].length + 
pending[count-1].length) {
+                               if (pending[count-3].length < pending[count-1].length) {
+                                       merge_at (count-3);
+                               } else {
+                                       merge_at (count-2);
+                               }
+                       } else if (pending[count-2].length <= pending[count-1].length) {
+                               merge_at (count-2);
+                       } else {
+                               break;
+                       }
+                       count = pending.length;
+                       #if DEBUG
+                               message ("New pending count: %d", count);
+                       #endif
+               }
+       }
+
+       private void merge_force_collapse () {
+               #if DEBUG
+                       message ("Merge Force Collapse");
+               #endif
+               int count = pending.length;
+               #if DEBUG
+                       message ("Pending count: %d", count);
+               #endif
+               while (count > 1) {
+                       if (count >= 3 && pending[count-3].length < pending[count-1].length) {
+                               merge_at (count-3);
+                       } else {
+                               merge_at (count-2);
+                       }
+                       count = pending.length;
+                       #if DEBUG
+                               message ("New pending count: %d", count);
+                       #endif
+               }
+       }
+
+       private void merge_at (int index) {
+               #if DEBUG
+                       message ("Merge at %d", index);
+               #endif
+               Slice<G> a = (owned) pending[index];
+               Slice<G> b = (owned) pending[index + 1];
+               
+               assert (a.length > 0);
+               assert (b.length > 0);
+               assert (a.index + a.length == b.index);
+
+               pending[index] = new Slice<G> (list, a.index, a.length + b.length);
+               pending.move (index + 2, index + 1, pending.length - index - 2);
+               pending.length -= 1;
+
+               int sorted_count = gallop_rightmost (b.peek_first (), a, 0);
+               a.shorten_start (sorted_count);
+               if (a.length == 0) {
+                       return;
+               }
+
+               b.length = gallop_leftmost (a.peek_last (), b, b.length - 1);
+               if (b.length == 0) {
+                       return;
+               }
+
+               if (a.length <= b.length) {
+                       merge_low ((owned) a, (owned) b);
+               } else {
+                       merge_high ((owned) a, (owned) b);
+               }
+       }
+
+       private int gallop_leftmost (G key, Slice<G> a, int hint) {
+               #if DEBUG
+                       message ("Galop leftmost in (%d, %d), hint=%d", a.index, a.length, hint);
+               #endif
+               assert (0 <= hint);
+               assert (hint < a.length);
+
+               int p = a.index + hint;
+               int last_offset = 0;
+               int offset = 1;
+               if (lower_than (a.list[p], key)) {
+                       int max_offset = a.length - hint;
+                       while (offset < max_offset) {
+                               if (lower_than (a.list[p + offset], key)) {
+                                       last_offset = offset;
+                                       offset <<= 1;
+                                       offset++;
+                               } else {
+                                       break;
+                               }
+                       }
+
+                       if (offset > max_offset) {
+                               offset = max_offset;
+                       }
+
+                       last_offset = hint + last_offset;
+                       offset = hint + offset;
+               } else {
+                       int max_offset = hint + 1;
+                       while (offset < max_offset) {
+                               if (lower_than (a.list[p - offset], key)) {
+                                       break;
+                               } else {
+                                       last_offset = offset;
+                                       offset <<= 1;
+                                       offset++;
+                               }
+                       }
+
+                       if (offset > max_offset) {
+                               offset = max_offset;
+                       }
+
+                       int temp_last_offset = last_offset;
+                       int temp_offset = offset;
+                       last_offset = hint - temp_offset;
+                       offset = hint - temp_last_offset;
+               }
+
+               assert (-1 <= last_offset);
+               assert (last_offset < offset);
+               assert (offset <= a.length);
+
+               last_offset += 1;
+               while (last_offset < offset) {
+                       int m = last_offset + ((offset - last_offset) >> 1);
+                       if (lower_than (a.list[a.index + m], key)) {
+                               last_offset = m + 1;
+                       } else {
+                               offset = m;
+                       }
+               }
+
+               assert (last_offset == offset);
+               return offset;
+       }
+
+       private int gallop_rightmost (G key, Slice<G> a, int hint) {
+               #if DEBUG
+                       message ("Galop rightmost in (%d, %d), hint=%d", a.index, a.length, hint);
+               #endif
+               assert (0 <= hint);
+               assert (hint < a.length);
+
+               int p = a.index + hint;
+               int last_offset = 0;
+               int offset = 1;
+               if (lower_than_or_equal_to (a.list[p], key)) {
+                       int max_offset = a.length - hint;
+                       while (offset < max_offset) {
+                               if (lower_than_or_equal_to (a.list[p + offset], key)) {
+                                       last_offset = offset;
+                                       offset <<= 1;
+                                       offset++;
+                               } else {
+                                       break;
+                               }
+                       }
+
+                       if (offset > max_offset) {
+                               offset = max_offset;
+                       }
+
+                       last_offset = hint + last_offset;
+                       offset = hint + offset;
+               } else {
+                       int max_offset = hint + 1;
+                       while (offset < max_offset) {
+                               if (lower_than_or_equal_to (a.list[p - offset], key)) {
+                                       break;
+                               } else {
+                                       last_offset = offset;
+                                       offset <<= 1;
+                                       offset++;
+                               }
+                       }
+
+                       if (offset > max_offset) {
+                               offset = max_offset;
+                       }
+
+                       int temp_last_offset = last_offset;
+                       int temp_offset = offset;
+                       last_offset = hint - temp_offset;
+                       offset = hint - temp_last_offset;
+               }
+
+               assert (-1 <= last_offset);
+               assert (last_offset < offset);
+               assert (offset <= a.length);
+
+               last_offset += 1;
+               while (last_offset < offset) {
+                       int m = last_offset + ((offset - last_offset) >> 1);
+                       if (lower_than_or_equal_to (a.list[a.index + m], key)) {
+                               last_offset = m + 1;
+                       } else {
+                               offset = m;
+                       }
+               }
+
+               assert (last_offset == offset);
+               return offset;
+       }
+
+       private void merge_low (owned Slice<G> a, owned Slice<G> b) {
+               #if DEBUG
+                       message ("Merge low (%d, %d) (%d, %d)", a.index, a.length, b.index, b.length);
+               #endif
+               assert (a.length > 0);
+               assert (b.length > 0);
+               assert (a.index + a.length == b.index);
+
+               int minimum_gallop = this.minimum_gallop;
+               int dest = a.index;
+               a.copy ();
+
+               try {
+                       list[dest++] = b.pop_first ();
+                       if (a.length == 1 || b.length == 0) {
+                               return;
+                       }
+
+                       while (true) {
+                               int a_count = 0;
+                               int b_count = 0;
+
+                               while (true) {
+                                       if (lower_than (b.peek_first (), a.peek_first ())) {
+                                               list[dest++] = b.pop_first ();
+                                               if (b.length == 0) {
+                                                       return;
+                                               }
+
+                                               b_count++;
+                                               a_count = 0;
+                                               if (b_count >= minimum_gallop) {
+                                                       break;
+                                               }
+                                       } else {
+                                               list[dest++] = a.pop_first ();
+                                               if (a.length == 1) {
+                                                       return;
+                                               }
+
+                                               a_count++;
+                                               b_count = 0;
+                                               if (a_count >= minimum_gallop) {
+                                                       break;
+                                               }
+                                       }
+                               }
+
+                               minimum_gallop++;
+
+                               while (true) {
+                                       minimum_gallop -= (minimum_gallop > 1 ? 1 : 0);
+                                       this.minimum_gallop = minimum_gallop;
+
+                                       a_count = gallop_rightmost (b.peek_first (), a, 0);
+                                       a.merge_in (list, a.index, dest, a_count);
+                                       dest += a_count;
+                                       a.shorten_start (a_count);
+                                       if (a.length <= 1) {
+                                               return;
+                                       }
+
+                                       list[dest++] = b.pop_first ();
+                                       if (b.length == 0) {
+                                               return;
+                                       }
+
+                                       b_count = gallop_leftmost (a.peek_first (), b, 0);
+                                       b.merge_in (list, b.index, dest, b_count);
+                                       dest += b_count;
+                                       b.shorten_start (b_count);
+                                       if (b.length == 0) {
+                                               return;
+                                       }
+
+                                       list[dest++] = a.pop_first ();
+                                       if (a.length == 1) {
+                                               return;
+                                       }
+
+                                       if (a_count < MINIMUM_GALLOP && b_count < MINIMUM_GALLOP) {
+                                               break;
+                                       }
+                               }
+
+                               minimum_gallop++;
+                               this.minimum_gallop = minimum_gallop;
+                       }
+               } finally {
+                       assert (a.length >= 0);
+                       assert (b.length >= 0);
+                       b.merge_in (list, b.index, dest, b.length);
+                       a.merge_in (list, a.index, dest + b.length, a.length);
+               }
+       }
+
+       private void merge_high (owned Slice<G> a, owned Slice<G> b) {
+               #if DEBUG
+                       message ("Merge high (%d, %d) (%d, %d)", a.index, a.length, b.index, b.length);
+               #endif
+               assert (a.length > 0);
+               assert (b.length > 0);
+               assert (a.index + a.length == b.index);
+
+               int minimum_gallop = this.minimum_gallop;
+               int dest = b.index + b.length;
+               b.copy ();
+
+               try {
+                       list[--dest] = a.pop_last ();
+                       if (a.length == 0 || b.length == 1) {
+                               return;
+                       }
+
+                       while (true) {
+                               int a_count = 0;
+                               int b_count = 0;
+
+                               while (true) {
+                                       if (lower_than (b.peek_last (), a.peek_last ())) {
+                                               list[--dest] = a.pop_last ();
+                                               if (a.length == 0) {
+                                                       return;
+                                               }
+
+                                               a_count++;
+                                               b_count = 0;
+                                               if (a_count >= minimum_gallop) {
+                                                       break;
+                                               }
+                                       } else {
+                                               list[--dest] = b.pop_last ();
+                                               if (b.length == 1) {
+                                                       return;
+                                               }
+
+                                               b_count++;
+                                               a_count = 0;
+                                               if (b_count >= minimum_gallop) {
+                                                       break;
+                                               }
+                                       }
+                               }
+
+                               minimum_gallop++;
+
+                               while (true) {
+                                       minimum_gallop -= (minimum_gallop > 1 ? 1 : 0);
+                                       this.minimum_gallop = minimum_gallop;
+
+                                       int k = gallop_rightmost (b.peek_last (), a, a.length - 1);
+                                       a_count = a.length - k;
+                                       a.merge_in_reversed (list, a.index + k, dest - a_count, a_count);
+                                       dest -= a_count;
+                                       a.shorten_end (a_count);
+                                       if (a.length == 0) {
+                                               return;
+                                       }
+
+                                       list[--dest] = b.pop_last ();
+                                       if (b.length == 1) {
+                                               return;
+                                       }
+
+                                       k = gallop_leftmost (a.peek_last (), b, b.length - 1);
+                                       b_count = b.length - k;
+                                       b.merge_in_reversed (list, b.index + k, dest - b_count, b_count);
+                                       dest -= b_count;
+                                       b.shorten_end (b_count);
+                                       if (b.length <= 1) {
+                                               return;
+                                       }
+
+                                       list[--dest] = a.pop_last ();
+                                       if (a.length == 0) {
+                                               return;
+                                       }
+
+                                       if (a_count < MINIMUM_GALLOP && b_count < MINIMUM_GALLOP) {
+                                               break;
+                                       }
+                               }
+
+                               minimum_gallop++;
+                               this.minimum_gallop = minimum_gallop;
+                       }
+               } finally {
+                       assert (a.length >= 0);
+                       assert (b.length >= 0);
+                       a.merge_in_reversed (list, a.index, dest - a.length, a.length);
+                       b.merge_in_reversed (list, b.index, dest - a.length - b.length, b.length);
+               }
+       }
+
+       [Compact]
+       private class Slice<G> {
+
+               public void** list;
+               public void** new_list;
+               public int index;
+               public int length;
+
+               public Slice (void** list, int index, int length) {
+                       this.list = list;
+                       this.index = index;
+                       this.length = length;
+               }
+               
+               ~Slice () {
+                       if (new_list != null)
+                               free (new_list);
+               }
+
+               public void copy () {
+                       new_list = Memory.dup (&list[index], (uint) sizeof (G) * length);
+                       list = new_list;
+                       index = 0;
+               }
+
+               public inline void merge_in (void** dest_array, int index, int dest_index, int count) {
+                       Memory.move (&dest_array[dest_index], &list[index], sizeof (G) * count);
+               }
+
+               public inline void merge_in_reversed (void** dest_array, int index, int dest_index, int 
count) {
+                       Memory.move (&dest_array[dest_index], &list[index], sizeof (G) * count);
+               }
+
+               public inline void shorten_start (int n) {
+                       index += n;
+                       length -= n;
+               }
+
+               public inline void shorten_end (int n) {
+                       length -= n;
+               }
+
+               public inline void* pop_first () {
+                       length--;
+                       return list[index++];
+               }
+
+               public inline void* pop_last () {
+                       length--;
+                       return list[index + length];
+               }
+
+               public inline unowned void* peek_first () {
+                       return list[index];
+               }
+
+               public inline unowned void* peek_last () {
+                       return list[index + length - 1];
+               }
+
+               public void reverse () {
+                       int low = index;
+                       int high = index + length - 1;
+                       while (low < high) {
+                               swap (low++, high--);
+                       }
+               }
+
+               private inline void swap (int i, int j) {
+                       void* temp = list[i];
+                       list[i] = list[j];
+                       list[j] = temp;
+               }
+       }
+}
+
diff --git a/vala/valaflowanalyzer.vala b/vala/valaflowanalyzer.vala
index 9f94a42..3683b81 100644
--- a/vala/valaflowanalyzer.vala
+++ b/vala/valaflowanalyzer.vala
@@ -374,8 +374,7 @@ public class Vala.FlowAnalyzer : CodeVisitor {
                                added.set (block, counter);
                        }
                        while (work_list.size > 0) {
-                               BasicBlock block = work_list.get (0);
-                               work_list.remove_at (0);
+                               BasicBlock block = work_list.remove_at (0);
                                foreach (BasicBlock frontier in block.get_dominator_frontier ()) {
                                        int blockPhi = phi.get (frontier);
                                        if (blockPhi < counter) {
@@ -405,8 +404,7 @@ public class Vala.FlowAnalyzer : CodeVisitor {
                        used_vars_queue.add (variable);
                }
                while (used_vars_queue.size > 0) {
-                       Variable used_var = used_vars_queue[0];
-                       used_vars_queue.remove_at (0);
+                       Variable used_var = used_vars_queue.remove_at (0);
 
                        PhiFunction phi = phi_functions.get (used_var);
                        if (phi != null) {
@@ -965,9 +963,8 @@ public class Vala.FlowAnalyzer : CodeVisitor {
                // remove catch clauses from jump stack
                List<JumpTarget> catch_stack = new ArrayList<JumpTarget> ();
                for (int i = jump_stack.size - 1; i >= finally_jump_stack_size; i--) {
-                       var jump_target = jump_stack[i];
+                       var jump_target = jump_stack.remove_at (i);
                        catch_stack.add (jump_target);
-                       jump_stack.remove_at (i);
                }
 
                foreach (JumpTarget jump_target in catch_stack) {
diff --git a/vala/valagirparser.vala b/vala/valagirparser.vala
index 9b4c0e8..16da385 100644
--- a/vala/valagirparser.vala
+++ b/vala/valagirparser.vala
@@ -1612,8 +1612,7 @@ public class Vala.GirParser : CodeVisitor {
        }
 
        void pop_metadata () {
-               metadata = metadata_stack[metadata_stack.size - 1];
-               metadata_stack.remove_at (metadata_stack.size - 1);
+               metadata = metadata_stack.remove_at (metadata_stack.size - 1);
        }
 
        bool parse_type_arguments_from_string (DataType parent_type, string type_arguments, SourceReference? 
source_reference = null) {
@@ -2001,8 +2000,7 @@ public class Vala.GirParser : CodeVisitor {
 
        void pop_node () {
                old_current = current;
-               current = tree_stack[tree_stack.size - 1];
-               tree_stack.remove_at (tree_stack.size - 1);
+               current = tree_stack.remove_at (tree_stack.size - 1);
        }
 
        void parse_namespace () {



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]