add internal copy of libgee and use Gee.ArrayList, Gee.HashMap, and

2007-07-27  Juerg Billeter  <j@bitron.ch>

	* Makefile.am, README, configure.ac, gee/Makefile.am,
	  gee/arraylist.vala, gee/collection.vala, gee/hashmap.vala,
	  gee/hashset.vala, gee/iterable.vala, gee/iterator.vala, gee/list.vala,
	  gee/map.vala, gee/readonlycollection.vala, gee/readonlylist.vala,
	  gee/readonlymap.vala, gee/readonlyset.vala, gee/set.vala,
	  vala/Makefile.am, vala/parser.y, vala/valaarray.vala,
	  vala/valaarraycreationexpression.vala, vala/valaattribute.vala,
	  vala/valablock.vala, vala/valacallback.vala, vala/valaclass.vala,
	  vala/valacodecontext.vala, vala/valacodenode.vala,
	  vala/valadatatype.vala, vala/valaelementaccess.vala,
	  vala/valaenum.vala, vala/valaexpression.vala, vala/valafield.vala,
	  vala/valaformalparameter.vala, vala/valaforstatement.vala,
	  vala/valainitializerlist.vala, vala/valainstancecast.vala,
	  vala/valainterface.vala, vala/valainterfacewriter.vala,
	  vala/valainvocationexpression.vala, vala/valainvokable.vala,
	  vala/valalambdaexpression.vala,
	  vala/valalocalvariabledeclaration.vala, vala/valamember.vala,
	  vala/valamemberaccess.vala, vala/valamemorymanager.vala,
	  vala/valamethod.vala, vala/valanamespace.vala,
	  vala/valaobjectcreationexpression.vala, vala/valapointer.vala,
	  vala/valascope.vala, vala/valasemanticanalyzer.vala,
	  vala/valasignal.vala, vala/valasourcefile.vala,
	  vala/valasourcefilecycle.vala, vala/valastruct.vala,
	  vala/valaswitchsection.vala, vala/valaswitchstatement.vala,
	  vala/valasymbol.vala, vala/valasymbolresolver.vala,
	  vala/valatrystatement.vala, vala/valatypeparameter.vala,
	  vala/valatypereference.vala, vala/valavariabledeclarator.vala,
	  ccode/Makefile.am, ccode/valaccodeblock.vala,
	  ccode/valaccodecasestatement.vala,
	  ccode/valaccodecommaexpression.vala, ccode/valaccodedeclaration.vala,
	  ccode/valaccodeenum.vala, ccode/valaccodeforstatement.vala,
	  ccode/valaccodefragment.vala, ccode/valaccodefunction.vala,
	  ccode/valaccodefunctioncall.vala,
	  ccode/valaccodefunctiondeclarator.vala,
	  ccode/valaccodeinitializerlist.vala, ccode/valaccodestruct.vala,
	  ccode/valaccodeswitchstatement.vala, gobject/Makefile.am,
	  gobject/valaclassregisterfunction.vala,
	  gobject/valacodegenerator.vala,
	  gobject/valacodegeneratorassignment.vala,
	  gobject/valacodegeneratorclass.vala,
	  gobject/valacodegeneratorinterface.vala,
	  gobject/valacodegeneratorinvocationexpression.vala,
	  gobject/valacodegeneratormemberaccess.vala,
	  gobject/valacodegeneratormethod.vala,
	  gobject/valacodegeneratorsignal.vala,
	  gobject/valacodegeneratorsourcefile.vala,
	  gobject/valainterfaceregisterfunction.vala, compiler/Makefile.am,
	  vapi/gio-standalone.vala, vapi/gstreamer-0.10.vala,
	  vapi/gtk+-2.0.vala, vapigen/Makefile.am, vapigen/valagidlparser.vala:
	  add internal copy of libgee and use Gee.ArrayList, Gee.HashMap, and
	  Gee.HashSet instead of GLib.List and GLib.HashTable

svn path=/trunk/; revision=406

14 files changed, 1493 insertions, 0 deletions

diff --git a/gee/Makefile.am b/gee/Makefile.am
new file mode 100644
index 000000000..9570518aa
--- /dev/null
+++ b/gee/Makefile.am
@@ -0,0 +1,82 @@
+NULL =
+
+INCLUDES = \
+	$(GLIB_CFLAGS) \
+	$(NULL)
+
+BUILT_SOURCES = gee.vala.stamp
+
+noinst_LTLIBRARIES = \
+	libgee.la
+	$(NULL)
+
+libgee_la_SOURCES = \
+	gee.vala.stamp \
+	arraylist.c \
+	arraylist.h \
+	arraylist.vala \
+	collection.c \
+	collection.h \
+	collection.vala \
+	hashmap.c \
+	hashmap.h \
+	hashmap.vala \
+	hashset.c \
+	hashset.h \
+	hashset.vala \
+	iterable.c \
+	iterable.h \
+	iterable.vala \
+	iterator.c \
+	iterator.h \
+	iterator.vala \
+	list.c \
+	list.h \
+	list.vala \
+	map.c \
+	map.h \
+	map.vala \
+	readonlycollection.c \
+	readonlycollection.h \
+	readonlycollection.vala \
+	readonlylist.c \
+	readonlylist.h \
+	readonlylist.vala \
+	readonlymap.c \
+	readonlymap.h \
+	readonlymap.vala \
+	readonlyset.c \
+	readonlyset.h \
+	readonlyset.vala \
+	set.c \
+	set.h \
+	set.vala \
+	$(NULL)
+
+geeincludedir = $(includedir)/vala-1.0/gee
+
+geeinclude_HEADERS = \
+	arraylist.h \
+	collection.h \
+	hashmap.h \
+	hashset.h \
+	iterable.h \
+	iterator.h \
+	list.h \
+	map.h \
+	readonlycollection.h \
+	readonlylist.h \
+	readonlymap.h \
+	readonlyset.h \
+	set.h \
+	$(NULL)
+
+gee.vala gee.vala.stamp: $(filter %.vala,$(libgee_la_SOURCES))
+	$(VALAC) --vapidir $(srcdir)/../vapi --library gee $^
+	touch $@
+
+libgee_la_LIBADD = \
+	$(GLIB_LIBS) \
+	$(NULL)
+
+EXTRA_DIST = gee.vala gee.vala.stamp
diff --git a/gee/arraylist.vala b/gee/arraylist.vala
new file mode 100644
index 000000000..9853bfd6c
--- /dev/null
+++ b/gee/arraylist.vala
@@ -0,0 +1,186 @@
+/* arraylist.vala
+ *
+ * Copyright (C) 2004-2005  Novell, Inc
+ * Copyright (C) 2005  David Waite
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Arrays of arbitrary elements which grow automatically as elements are added.
+ */
+public class Gee.ArrayList<G> : Iterable<G>, Collection<G>, List<G> {
+	public int size {
+		get { return _size; }
+	}
+
+	public EqualFunc equal_func {
+		set { _equal_func = value; }
+	}
+
+	private G[] _items = new G[4];
+	private int _size;
+	private EqualFunc _equal_func;
+
+	// concurrent modification protection
+	private int _stamp = 0;
+
+	public ArrayList (construct EqualFunc equal_func = GLib.direct_equal) {
+	}
+
+	public Gee.Iterator<G> iterator () {
+		return new Iterator<G> (this);
+	}
+
+	public bool contains (G item) {
+		return (index_of (item) != -1);
+	}
+
+	public int index_of (G item) {
+		for (int index = 0; index < _size; index++) {
+			if (_equal_func (_items[index], item)) {
+				return index;
+			}
+		}
+		return -1;
+	}
+
+	public G get (int index) {
+		assert (index >= 0 && index < _size);
+
+		return _items[index];
+	}
+
+	public void set (int index, G item) {
+		assert (index >= 0 && index < _size);
+
+		_items[index] = item;
+	}
+
+	public bool add (G item) {
+		if (_size == _items.length) {
+			grow_if_needed (1);
+		}
+		_items[_size++] = item;
+		_stamp++;
+		return true;
+	}
+
+	public void insert (int index, G item) {
+		assert (index >= 0 && index <= _size);
+
+		if (_size == _items.length) {
+			grow_if_needed (1);
+		}
+		shift (index, 1);
+		_items[index] = item;
+		_stamp++;
+	}
+
+	public bool remove (G item) {
+		for (int index = 0; index < _size; index++) {
+			if (_equal_func (_items[index], item)) {
+				remove_at (index);
+				return true;
+			}
+		}
+		return false;
+	}
+
+	public void remove_at (int index) {
+		assert (index >= 0 && index < _size);
+
+		_items[index] = null;
+
+		shift (index + 1, -1);
+
+		_stamp++;
+	}
+
+	public void clear () {
+		for (int index = 0; index < _size; index++) {
+			_items[index] = null;
+		}
+		_size = 0;
+		_stamp++;
+	}
+
+	private void shift (int start, int delta) {
+		assert (start >= 0 && start <= _size && start >= -delta);
+
+		_items.move (start, start + delta, _size - start);
+
+		_size += delta;
+	}
+
+	private void grow_if_needed (int new_count) {
+		assert (new_count >= 0);
+
+		int minimum_size = _size + new_count;
+		if (minimum_size > _items.length) {
+			// double the capacity unless we add even more items at this time
+			set_capacity (new_count > _items.length ? minimum_size : 2 * _items.length);
+		}
+	}
+
+	private void set_capacity (int value) {
+		assert (value >= _size);
+
+		_items.resize (value);
+	}
+
+	private class Iterator<G> : Gee.Iterator<G> {
+		public ArrayList<G> list {
+			set {
+				_list = value;
+				_stamp = _list._stamp;
+			}
+		}
+
+		private ArrayList<G> _list;
+		private int _index = -1;
+
+		// concurrent modification protection
+		public int _stamp = 0;
+
+		public Iterator (construct ArrayList! list) {
+		}
+
+		public bool next () {
+			assert (_stamp == _list._stamp);
+			if (_index < _list._size) {
+				_index++;
+			}
+			return (_index < _list._size);
+		}
+
+		public G get () {
+			assert (_stamp == _list._stamp);
+
+			if (_index < 0 || _index >= _list._size) {
+				return null;
+			}
+
+			return _list.get (_index);
+		}
+	}
+}
+
diff --git a/gee/collection.vala b/gee/collection.vala
new file mode 100644
index 000000000..4b109084c
--- /dev/null
+++ b/gee/collection.vala
@@ -0,0 +1,68 @@
+/* collection.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+/**
+ * Serves as the base interface for implementing collection classes. Defines
+ * size, iteration, and modification methods.
+ */
+public interface Gee.Collection<G> : Iterable<G> {
+	/**
+	 * The number of items in this collection.
+	 */
+	public abstract int size { get; }
+
+	/**
+	 * Determines whether this collection contains the specified item.
+	 *
+	 * @param item the item to locate in the collection
+	 *
+	 * @return     true if item is found, false otherwise
+	 */
+	public abstract bool contains (G item);
+
+	/**
+	 * Adds an item to this collection. Must not be called on read-only
+	 * collections.
+	 *
+	 * @param item the item to add to the collection
+	 *
+	 * @return     true if the collection has been changed, false otherwise
+	 */
+	public abstract bool add (G item);
+
+	/**
+	 * Removes the first occurence of an item from this collection. Must not
+	 * be called on read-only collections.
+	 *
+	 * @param item the item to remove from the collection
+	 *
+	 * @return     true if the collection has been changed, false otherwise
+	 */
+	public abstract bool remove (G item);
+
+	/**
+	 * Removes all items from this collection. Must not be called on
+	 * read-only collections.
+	 */
+	public abstract void clear ();
+}
+
diff --git a/gee/hashmap.vala b/gee/hashmap.vala
new file mode 100644
index 000000000..890bc7ad9
--- /dev/null
+++ b/gee/hashmap.vala
@@ -0,0 +1,332 @@
+/* hashmap.vala
+ *
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ * Copyright (C) 1997-2000  GLib Team and others
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Hashtable implementation of the Map interface.
+ */
+public class Gee.HashMap<K,V> : Map<K,V> {
+	public int size {
+		get { return _nnodes; }
+	}
+
+	public HashFunc key_hash_func {
+		set { _key_hash_func = value; }
+	}
+
+	public EqualFunc key_equal_func {
+		set { _key_equal_func = value; }
+	}
+
+	public EqualFunc value_equal_func {
+		set { _value_equal_func = value; }
+	}
+
+	private int _array_size;
+	private int _nnodes;
+	private Node<K,V>[] _nodes;
+
+	// concurrent modification protection
+	private int _stamp = 0;
+
+	private HashFunc _key_hash_func;
+	private EqualFunc _key_equal_func;
+	private EqualFunc _value_equal_func;
+
+	private const int MIN_SIZE = 11;
+	private const int MAX_SIZE = 13845163;
+
+	public HashMap (construct HashFunc key_hash_func = GLib.direct_hash, construct EqualFunc key_equal_func = GLib.direct_equal, construct EqualFunc value_equal_func = GLib.direct_equal) {
+	}
+
+	construct {
+		_array_size = MIN_SIZE;
+		_nodes = new Node<K,V>[_array_size];
+	}
+
+	public Set<K> get_keys () {
+		return new KeySet<K,V> (this);
+	}
+
+	public Collection<V> get_values () {
+		return new ValueCollection<K,V> (this);
+	}
+
+	private Node<K,V>* lookup_node (K key) {
+		uint hash_value = _key_hash_func (key);
+		Node<K,V>* node = &_nodes[hash_value % _array_size];
+		while ((*node) != null && (hash_value != (*node).key_hash || !_key_equal_func ((*node).key, key))) {
+			node = &((*node).next);
+		}
+		return node;
+	}
+
+	public bool contains (K key) {
+		Node<K,V>* node = lookup_node (key);
+		return (*node != null);
+	}
+
+	public V get (K key) {
+		weak Node<K,V> node = *lookup_node (key);
+		if (node != null) {
+			return node.value;
+		} else {
+			return null;
+		}
+	}
+
+	public void set (K key, V value) {
+		Node<K,V>* node = lookup_node (key);
+		if (*node != null) {
+			(*node).value = value;
+		} else {
+			uint hash_value = _key_hash_func (key);
+			*node = new Node<K,V> (key, value, hash_value);
+			_nnodes++;
+			resize ();
+		}
+		_stamp++;
+	}
+
+	public bool remove (K key) {
+		Node<K,V>* node = lookup_node (key);
+		if (*node != null) {
+			(*node).key = null;
+			(*node).value = null;
+			*node = (*node).next;
+			_nnodes--;
+			resize ();
+			_stamp++;
+			return true;
+		}
+		return false;
+	}
+
+	public void clear () {
+		for (int i = 0; i < _array_size; i++) {
+			Node<K,V> node = #_nodes[i];
+			while (node != null) {
+				Node next = #node.next;
+				node.key = null;
+				node.value = null;
+				node = #next;
+			}
+		}
+		_nnodes = 0;
+		resize ();
+	}
+
+	private void resize () {
+		if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
+		    (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
+			int new_array_size = SpacedPrimes.closest (_nnodes);
+			new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
+
+			Node<K,V>[] new_nodes = new Node<K,V>[new_array_size];
+
+			for (int i = 0; i < _array_size; i++) {
+				Node<K,V> node;
+				Node<K,V> next;
+				for (node = #_nodes[i]; node != null; node = #next) {
+					next = #node.next;
+					uint hash_val = node.key_hash % new_array_size;
+					node.next = #new_nodes[hash_val];
+					new_nodes[hash_val] = #node;
+				}
+			}
+			_nodes = #new_nodes;
+			_array_size = new_array_size;
+		}
+	}
+
+	~HashSet () {
+		clear ();
+	}
+
+	[ReferenceType]
+	private struct Node<K,V> {
+		public K key;
+		public V value;
+		public Node<K,V> next;
+		public uint key_hash;
+
+		public Node (K# k, V# v, uint hash) {
+			key = #k;
+			value = #v;
+			key_hash = hash;
+		}
+	}
+
+	private class KeySet<K,V> : Iterable<K>, Collection<K>, Set<K> {
+		public HashMap<K,V> map {
+			set { _map = value; }
+		}
+
+		private HashMap<K,V> _map;
+
+		public KeySet (construct HashMap! map) {
+		}
+
+		public Iterator<K> iterator () {
+			return new KeyIterator<K,V> (_map);
+		}
+
+		public int size {
+			get { return _map.size; }
+		}
+
+		public bool add (K key) {
+			assert_not_reached ();
+			return false;
+		}
+
+		public void clear () {
+			assert_not_reached ();
+		}
+
+		public bool remove (K key) {
+			assert_not_reached ();
+			return false;
+		}
+
+		public bool contains (K key) {
+			return _map.contains (key);
+		}
+	}
+
+	private class KeyIterator<K,V> : Iterator<K> {
+		public HashMap<K,V> map {
+			set {
+				_map = value;
+				_stamp = _map._stamp;
+			}
+		}
+
+		private HashMap<K,V> _map;
+		private int _index = -1;
+		private weak Node<K,V> _node;
+
+		// concurrent modification protection
+		private int _stamp;
+
+		public KeyIterator (construct HashMap! map) {
+		}
+
+		public bool next () {
+			if (_node != null) {
+				_node = _node.next;
+			}
+			while (_node == null && _index + 1 < _map._array_size) {
+				_index++;
+				_node = _map._nodes[_index];
+			}
+			return (_node != null);
+		}
+
+		public K get () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			return _node.key;
+		}
+	}
+
+	private class ValueCollection<K,V> : Iterable<V>, Collection<V> {
+		public HashMap<K,V> map {
+			set { _map = value; }
+		}
+
+		private HashMap<K,V> _map;
+
+		public ValueCollection (construct HashMap! map) {
+		}
+
+		public Iterator<V> iterator () {
+			return new ValueIterator<K,V> (_map);
+		}
+
+		public int size {
+			get { return _map.size; }
+		}
+
+		public bool add (V value) {
+			assert_not_reached ();
+		}
+
+		public void clear () {
+			assert_not_reached ();
+		}
+
+		public bool remove (V value) {
+			assert_not_reached ();
+		}
+
+		public bool contains (V value) {
+			Iterator<V> it = iterator ();
+			while (it.next ()) {
+				if (_map._value_equal_func (it.get (), value)) {
+					return true;
+				}
+			}
+			return false;
+		}
+	}
+
+	private class ValueIterator<K,V> : Iterator<V> {
+		public HashMap<K,V> map {
+			set {
+				_map = value;
+				_stamp = _map._stamp;
+			}
+		}
+
+		private HashMap<V,K> _map;
+		private int _index = -1;
+		private weak Node<K,V> _node;
+
+		// concurrent modification protection
+		private int _stamp;
+
+		public ValueIterator (construct HashMap! map) {
+		}
+
+		public bool next () {
+			if (_node != null) {
+				_node = _node.next;
+			}
+			while (_node == null && _index + 1 < _map._array_size) {
+				_index++;
+				_node = _map._nodes[_index];
+			}
+			return (_node != null);
+		}
+
+		public V get () {
+			assert (_stamp == _map._stamp);
+			assert (_node != null);
+			return _node.value;
+		}
+	}
+}
+
diff --git a/gee/hashset.vala b/gee/hashset.vala
new file mode 100644
index 000000000..f0bb5f46a
--- /dev/null
+++ b/gee/hashset.vala
@@ -0,0 +1,202 @@
+/* hashset.vala
+ *
+ * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
+ * Copyright (C) 1997-2000  GLib Team and others
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Hashtable implementation of the Set interface.
+ */
+public class Gee.HashSet<G> : Iterable<G>, Collection<G>, Set<G> {
+	public int size {
+		get { return _nnodes; }
+	}
+
+	public HashFunc hash_func {
+		set { _hash_func = value; }
+	}
+
+	public EqualFunc equal_func {
+		set { _equal_func = value; }
+	}
+
+	private int _array_size;
+	private int _nnodes;
+	private Node<G>[] _nodes;
+
+	// concurrent modification protection
+	private int _stamp = 0;
+
+	private HashFunc _hash_func;
+	private EqualFunc _equal_func;
+
+	private const int MIN_SIZE = 11;
+	private const int MAX_SIZE = 13845163;
+
+	public HashSet (construct HashFunc hash_func = GLib.direct_hash, construct EqualFunc equal_func = GLib.direct_equal) {
+	}
+
+	construct {
+		_array_size = MIN_SIZE;
+		_nodes = new Node<G>[_array_size];
+	}
+
+	private Node<G>* lookup_node (G key) {
+		uint hash_value = _hash_func (key);
+		Node<G>* node = &_nodes[hash_value % _array_size];
+		while ((*node) != null && (hash_value != (*node).key_hash || !_equal_func ((*node).key, key))) {
+			node = &((*node).next);
+		}
+		return node;
+	}
+
+	public bool contains (G key) {
+		Node<G>* node = lookup_node (key);
+		return (*node != null);
+	}
+
+	public Gee.Iterator<G> iterator () {
+		return new Iterator<G> (this);
+	}
+
+	public bool add (G key) {
+		Node<G>* node = lookup_node (key);
+		if (*node != null) {
+			return false;
+		} else {
+			uint hash_value = _hash_func (key);
+			*node = new Node<G> (key, hash_value);
+			_nnodes++;
+			resize ();
+			_stamp++;
+			return true;
+		}
+	}
+
+	public bool remove (G key) {
+		Node<G>* node = lookup_node (key);
+		if (*node != null) {
+			(*node).key = null;
+			*node = (*node).next;
+			_nnodes--;
+			resize ();
+			_stamp++;
+			return true;
+		}
+		return false;
+	}
+
+	public void clear () {
+		for (int i = 0; i < _array_size; i++) {
+			Node<G> node = #_nodes[i];
+			while (node != null) {
+				Node next = #node.next;
+				node.key = null;
+				node = #next;
+			}
+		}
+		_nnodes = 0;
+		resize ();
+	}
+
+	private void resize () {
+		if ((_array_size >= 3 * _nnodes && _array_size >= MIN_SIZE) ||
+		    (3 * _array_size <= _nnodes && _array_size < MAX_SIZE)) {
+			int new_array_size = SpacedPrimes.closest (_nnodes);
+			new_array_size = new_array_size.clamp (MIN_SIZE, MAX_SIZE);
+
+			Node<G>[] new_nodes = new Node<G>[new_array_size];
+
+			for (int i = 0; i < _array_size; i++) {
+				Node<G> node;
+				Node<G> next;
+				for (node = #_nodes[i]; node != null; node = #next) {
+					next = #node.next;
+					uint hash_val = node.key_hash % new_array_size;
+					node.next = #new_nodes[hash_val];
+					new_nodes[hash_val] = #node;
+				}
+			}
+			_nodes = #new_nodes;
+			_array_size = new_array_size;
+		}
+	}
+
+	~HashSet () {
+		clear ();
+	}
+
+	[ReferenceType]
+	private struct Node<G> {
+		public G key;
+		public Node<G> next;
+		public uint key_hash;
+
+		public Node (G# k, uint hash) {
+			key = #k;
+			key_hash = hash;
+		}
+	}
+
+	private class Iterator<G> : Gee.Iterator<G> {
+		public HashSet<G> set {
+			set {
+				_set = value;
+				_stamp = _set._stamp;
+				// find first node
+				while (_node == null && _index + 1 < _set._array_size) {
+					_index++;
+					_node = _set._nodes[_index];
+				}
+			}
+		}
+
+		private HashSet<G> _set;
+		private int _index = -1;
+		private weak Node<G> _node;
+
+		// concurrent modification protection
+		private int _stamp = 0;
+
+		public Iterator (construct HashSet! set) {
+		}
+
+		public bool next () {
+			if (_node != null) {
+				_node = _node.next;
+			}
+			while (_node == null && _index + 1 < _set._array_size) {
+				_index++;
+				_node = _set._nodes[_index];
+			}
+			return (_node != null);
+		}
+
+		public G get () {
+			assert (_stamp == _set._stamp);
+			assert (_node != null);
+			return _node.key;
+		}
+	}
+}
+
diff --git a/gee/iterable.vala b/gee/iterable.vala
new file mode 100644
index 000000000..1b3e66dd7
--- /dev/null
+++ b/gee/iterable.vala
@@ -0,0 +1,37 @@
+/* iterable.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+/**
+ * Implemented by classes that support a simple iteration over instances of the
+ * collection.
+ */
+public interface Gee.Iterable<G> {
+	/**
+	 * Returns a Iterator that can be used for simple iteration over a
+	 * collection.
+	 *
+	 * @return a Iterator that can be used for simple iteration over a
+	 *         collection
+	 */
+	public abstract Iterator<G> iterator ();
+}
+
diff --git a/gee/iterator.vala b/gee/iterator.vala
new file mode 100644
index 000000000..a4019462c
--- /dev/null
+++ b/gee/iterator.vala
@@ -0,0 +1,42 @@
+/* iterator.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+/**
+ * Implemented by classes that support a simple iteration over instances of the
+ * collection.
+ */
+public interface Gee.Iterator<G> {
+	/**
+	 * Advances to the next element in the iteration.
+	 *
+	 * @return true if the iterator has a next element
+	 */
+	public abstract bool next ();
+
+	/**
+	 * Returns the current element in the iteration.
+	 *
+	 * @return the current element in the iteration
+	 */
+	public abstract G get ();
+}
+
diff --git a/gee/list.vala b/gee/list.vala
new file mode 100644
index 000000000..0ff967b47
--- /dev/null
+++ b/gee/list.vala
@@ -0,0 +1,67 @@
+/* list.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+/**
+ * Represents a collection of items in a well-defined order.
+ */
+public interface Gee.List<G> : GLib.Object, Collection<G> {
+	/**
+	 * Returns the item at the specified index in this list.
+	 *
+	 * @param index zero-based index of the item to be returned
+	 *
+	 * @return      the item at the specified index in the list
+	 */
+	public abstract G get (int index);
+
+	/**
+	 * Sets the item at the specified index in this list.
+	 *
+	 * @param index zero-based index of the item to be set
+	 */
+	public abstract void set (int index, G item);
+
+	/**
+	 * Returns the index of the first occurence of the specified item in
+	 * this list.
+	 *
+	 * @return the index of the first occurence of the specified item, or
+	 *         -1 if the item could not be found
+	 */
+	public abstract int index_of (G item);
+
+	/**
+	 * Inserts an item into this list at the specified position.
+	 *
+	 * @param index zero-based index at which item is inserted
+	 * @param item  item to insert into the list
+	 */
+	public abstract void insert (int index, G item);
+
+	/**
+	 * Removes the item at the specified index of this list.
+	 *
+	 * @param index zero-based index of the item to be removed
+	 */
+	public abstract void remove_at (int index);
+}
+
diff --git a/gee/map.vala b/gee/map.vala
new file mode 100644
index 000000000..6dcee69cf
--- /dev/null
+++ b/gee/map.vala
@@ -0,0 +1,88 @@
+/* map.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+/**
+ * A map is a generic collection of key/value pairs.
+ */
+public interface Gee.Map<K,V> {
+	/**
+	 * The number of items in this map.
+	 */
+	public abstract int size { get; }
+
+	/**
+	 * Returns the keys of this map as a read-only set.
+	 *
+	 * @return the keys of the map
+	 */
+	public abstract Set<K> get_keys ();
+
+	/**
+	 * Returns the values of this map as a read-only collection.
+	 *
+	 * @return the values of the map
+	 */
+	public abstract Collection<V> get_values ();
+
+	/**
+	 * Determines whether this map contains the specified key.
+	 *
+	 * @param key the key to locate in the map
+	 *
+	 * @return    true if key is found, false otherwise
+	 */
+	public abstract bool contains (K key);
+
+	/**
+	 * Returns the value of the specified key in this map.
+	 *
+	 * @param key the key whose value is to be retrieved
+	 *
+	 * @return    the value associated with the key, or null if the key
+	 *            couldn't be found
+	 */
+	public abstract V get (K key);
+
+	/**
+	 * Inserts a new key and value into this map.
+	 *
+	 * @param key   the key to insert
+	 * @param value the value to associate with the key
+	 */
+	public abstract void set (K key, V value);
+
+	/**
+	 * Removes the specified key from this map.
+	 *
+	 * @param key the key to remove from the map
+	 *
+	 * @return    true if the map has been changed, false otherwise
+	 */
+	public abstract bool remove (K key);
+
+	/**
+	 * Removes all items from this collection. Must not be called on
+	 * read-only collections.
+	 */
+	public abstract void clear ();
+}
+
diff --git a/gee/readonlycollection.vala b/gee/readonlycollection.vala
new file mode 100644
index 000000000..30a6ea60f
--- /dev/null
+++ b/gee/readonlycollection.vala
@@ -0,0 +1,82 @@
+/* readonlycollection.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Represents a read-only collection of items.
+ */
+public class Gee.ReadOnlyCollection<G> : Iterable<G>, Collection<G> {
+	public int size {
+		get { return _collection.size; }
+	}
+
+	public Collection<G> collection {
+		set { _collection = value; }
+	}
+
+	private Collection<G> _collection;
+
+	public ReadOnlyCollection (construct Collection<G> collection = null) {
+	}
+
+	public Gee.Iterator<G> iterator () {
+		if (_collection == null) {
+			return new Iterator<G> ();
+		}
+
+		return _collection.iterator ();
+	}
+
+	public bool contains (G item) {
+		if (_collection == null) {
+			return false;
+		}
+
+		return _collection.contains (item);
+	}
+
+	public bool add (G item) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public bool remove (G item) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public void clear () {
+		assert_not_reached ();
+	}
+
+	private class Iterator<G> : Gee.Iterator<G> {
+		public bool next () {
+			return false;
+		}
+
+		public G get () {
+			return null;
+		}
+	}
+}
+
diff --git a/gee/readonlylist.vala b/gee/readonlylist.vala
new file mode 100644
index 000000000..b07fa4aeb
--- /dev/null
+++ b/gee/readonlylist.vala
@@ -0,0 +1,110 @@
+/* readonlylist.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Represents a read-only collection of items in a well-defined order.
+ */
+public class Gee.ReadOnlyList<G> : Iterable<G>, Collection<G>, List<G> {
+	public int size {
+		get { return _list.size; }
+	}
+
+	public List<G> list {
+		set { _list = value; }
+	}
+
+	private List<G> _list;
+
+	public ReadOnlyList (construct List<G> list = null) {
+	}
+
+	public Gee.Iterator<G> iterator () {
+		if (_list == null) {
+			return new Iterator<G> ();
+		}
+
+		return _list.iterator ();
+	}
+
+	public bool contains (G item) {
+		if (_list == null) {
+			return false;
+		}
+
+		return _list.contains (item);
+	}
+
+	public int index_of (G item) {
+		if (_list == null) {
+			return -1;
+		}
+
+		return _list.index_of (item);
+	}
+
+	public bool add (G item) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public bool remove (G item) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public void insert (int index, G item) {
+		assert_not_reached ();
+	}
+
+	public void remove_at (int index) {
+		assert_not_reached ();
+	}
+
+	public G get (int index) {
+		if (_list == null) {
+			return null;
+		}
+
+		return _list.get (index);
+	}
+
+	public void set (int index, G o) {
+		assert_not_reached ();
+	}
+
+	public void clear () {
+		assert_not_reached ();
+	}
+
+	class Iterator<G> : Gee.Iterator<G> {
+		public bool next () {
+			return false;
+		}
+
+		public G get () {
+			return null;
+		}
+	}
+}
+
diff --git a/gee/readonlymap.vala b/gee/readonlymap.vala
new file mode 100644
index 000000000..f36c9aaed
--- /dev/null
+++ b/gee/readonlymap.vala
@@ -0,0 +1,87 @@
+/* readonlymap.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Represents a read-only collection of key/value pairs.
+ */
+public class Gee.ReadOnlyMap<K,V> : Map<K,V> {
+	public int size {
+		get { return _map.size; }
+	}
+
+	public Map<K,V> map {
+		set { _map = value; }
+	}
+
+	private Map<K,V> _map;
+
+	public ReadOnlyMap (construct Map<K,V> map = null) {
+	}
+
+	public Set<K> get_keys () {
+		if (_map == null) {
+			return new ReadOnlySet<K> ();
+		}
+
+		return _map.get_keys ();
+	}
+
+	public Collection<V> get_values () {
+		if (_map == null) {
+			return new ReadOnlyCollection<V> ();
+		}
+
+		return _map.get_values ();
+	}
+
+	public bool contains (K key) {
+		if (_map == null) {
+			return false;
+		}
+
+		return _map.contains (key);
+	}
+
+	public V get (K key) {
+		if (_map == null) {
+			return null;
+		}
+
+		return _map.get (key);
+	}
+
+	public void set (K key, V value) {
+		assert_not_reached ();
+	}
+
+	public bool remove (K key) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public void clear () {
+		assert_not_reached ();
+	}
+}
+
diff --git a/gee/readonlyset.vala b/gee/readonlyset.vala
new file mode 100644
index 000000000..81db5b3f8
--- /dev/null
+++ b/gee/readonlyset.vala
@@ -0,0 +1,82 @@
+/* readonlyset.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+using GLib;
+
+/**
+ * Represents a read-only collection of items without duplicates.
+ */
+public class Gee.ReadOnlySet<G> : Iterable<G>, Collection<G>, Set<G> {
+	public int size {
+		get { return _set.size; }
+	}
+
+	public Set<G> set {
+		set { _set = value; }
+	}
+
+	private Set<G> _set;
+
+	public ReadOnlySet (construct Set<G> set = null) {
+	}
+
+	public Gee.Iterator<G> iterator () {
+		if (_set == null) {
+			return new Iterator<G> ();
+		}
+
+		return _set.iterator ();
+	}
+
+	public bool contains (G item) {
+		if (_set == null) {
+			return false;
+		}
+
+		return _set.contains (item);
+	}
+
+	public bool add (G item) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public bool remove (G item) {
+		assert_not_reached ();
+		return false;
+	}
+
+	public void clear () {
+		assert_not_reached ();
+	}
+
+	private class Iterator<G> : Gee.Iterator<G> {
+		public bool next () {
+			return false;
+		}
+
+		public G get () {
+			return null;
+		}
+	}
+}
+
diff --git a/gee/set.vala b/gee/set.vala
new file mode 100644
index 000000000..efdf7ae8d
--- /dev/null
+++ b/gee/set.vala
@@ -0,0 +1,28 @@
+/* set.vala
+ *
+ * Copyright (C) 2007  Jürg Billeter
+ *
+ * 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 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:
+ * 	Jürg Billeter <j@bitron.ch>
+ */
+
+/**
+ * A set is a collection without duplicates.
+ */
+public interface Gee.Set<G> : Collection<G> {
+}
+