Remove LinkedHashSet in favour of Gee.HashSet

Helps: bgo#640092

5 files changed, 1 insertions, 788 deletions

diff --git a/NEWS b/NEWS
index bdb419a..e9898f8 100644
--- a/NEWS
+++ b/NEWS
@@ -15,6 +15,7 @@ API changes:
 * ImDetails.im_addresses is now of type MultiMap<string, string>
 * WebServiceDetails.web_service_addresses is now of type
   MultiMap<string, string>
+* Removed LinkedHashSet in favour of Gee.HashSet
 
 Overview of changes from libfolks 0.4.0 to libfolks 0.5.0
 =========================================================
diff --git a/folks/Makefile.am b/folks/Makefile.am
index 51eefc4..4808264 100644
--- a/folks/Makefile.am
+++ b/folks/Makefile.am
@@ -34,7 +34,6 @@ libfolks_la_SOURCES = \
 	url-details.vala \
 	individual.vala \
 	individual-aggregator.vala \
-	linked-hash-set.vala \
 	persona.vala \
 	persona-store.vala \
 	types.vala \
diff --git a/folks/linked-hash-set.vala b/folks/linked-hash-set.vala
deleted file mode 100644
index 3098ec8..0000000
--- a/folks/linked-hash-set.vala
+++ /dev/null
@@ -1,377 +0,0 @@
-/*
- * Copyright (C) 2011 Collabora Ltd.
- *
- * 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, see <http://www.gnu.org/licenses/>.
- *
- * Authors:
- *       Eitan Isaacson <eitan.isaacson@collabora.co.uk>
- */
-
-using Gee;
-
-/**
- * Linked list implementation of the {@link Gee.Set} interface.
- * This implementation provides an ordered set with predictable iteration.
- *
- * @since 0.3.4
- */
-public class Folks.LinkedHashSet<G> : AbstractList<G>,
-    Set<G>
-{
-  /* A hash set that maintains a unique set. */
-  private HashSet<G> _hash_set;
-  /* A linked list that maintains the order of the items. */
-  private LinkedList<G> _linked_list;
-  /* A stamp which changes whenever either the hash set or the linked list are
-   * modified. */
-  private int _stamp = 0;
-
-  /**
-   * Constructs a new empty set.
-   *
-   * If no function parameters are provided, the default functions for the
-   * set's item type are used.
-   *
-   * @param hash_func an optional hash function
-   * @param equal_func an optional equality testing function
-   *
-   * @since 0.3.4
-   */
-  public LinkedHashSet (HashFunc? hash_func = null,
-      EqualFunc? equal_func = null)
-  {
-    this._hash_set = new HashSet<G> (hash_func, equal_func);
-    this._linked_list = new LinkedList<G> (equal_func);
-  }
-
-  /**
-   * The number of items in this collection.
-   *
-   * @see Gee.AbstractCollection.size
-   *
-   * @since 0.3.4
-   */
-  public override int size
-  {
-    get { return this._linked_list.size; }
-  }
-
-  /**
-   * Returns whether this structure contains the given item.
-   *
-   * @param item the element to find
-   *
-   * @return `true` if this collection contains the specified item.
-   * @see Gee.AbstractCollection.contains
-   *
-   * @since 0.3.4
-   */
-  public override bool contains (G item)
-  {
-    return this._hash_set.contains (item);
-  }
-
-  /**
-   * Add the given element.
-   *
-   * @param item element to add
-   *
-   * @return `true` if the element was added.
-   * @see Gee.AbstractCollection.add
-   *
-   * @since 0.3.4
-   */
-  public override bool add (G item)
-  {
-    if (this._hash_set.add (item))
-      {
-        this._stamp++;
-        this._linked_list.add (item);
-        return true;
-      }
-
-    return false;
-  }
-
-  /**
-   * Remove the instance of the given element.
-   *
-   * @param item element to remove
-   *
-   * @return `true` if the element was removed.
-   * @see Gee.AbstractCollection.remove
-   *
-   * @since 0.3.4
-   */
-  public override bool remove (G item)
-  {
-    if (this._hash_set.remove (item))
-      {
-        this._stamp++;
-        this._linked_list.remove (item);
-        return true;
-      }
-
-    return false;
-  }
-
-  /**
-   * Removes all items from this collection. Must not be called on read-only
-   * collections.
-   *
-   * @see Gee.AbstractCollection.clear
-   *
-   * @since 0.3.4
-   */
-  public override void clear ()
-  {
-    this._stamp++;
-    this._hash_set.clear ();
-    this._linked_list.clear ();
-  }
-
-  /**
-   * Returns the item at the given position.
-   *
-   * @param index the position of an element to retrieve.
-   *
-   * @return the item at the specified index in this list.
-   * @see Gee.AbstractList.get
-   *
-   * @since 0.3.4
-   */
-  public override G get (int index)
-  {
-    return this._linked_list.get (index);
-  }
-
-  /**
-   * Unimplemented method (incompatable with ordered set).
-   */
-  public override void set (int index, G item)
-  {
-    assert_not_reached ();
-  }
-
-  /**
-   * Unimplemented method (incompatable with ordered set).
-   */
-  public override void insert (int index, G item)
-  {
-    assert_not_reached ();
-  }
-
-  /**
-   * Returns the position of the given item.
-   *
-   * @param item an element to find within this structure.
-   *
-   * @return the index of the occurence of the specified item in this list.
-   * @see Gee.AbstractList.index_of
-   *
-   * @since 0.3.4
-   */
-  public override int index_of (G item)
-  {
-    if (!this._hash_set.contains (item))
-      return -1;
-    return this._linked_list.index_of (item);
-  }
-
-  /**
-   * Remove the element at the given index.
-   *
-   * @param index position of the element to remove.
-   *
-   * @return the removed element.
-   * @see Gee.AbstractList.remove_at
-   *
-   * @since 0.3.4
-   */
-  public override G remove_at (int index)
-  {
-    G item = this._linked_list.remove_at (index);
-    if (item != null)
-      {
-        this._stamp++;
-        this._hash_set.remove (item);
-      }
-    return item;
-  }
-
-  /**
-   * Returns a new sub-list of this structure. Caller does not own the new
-   * list's elements.
-   *
-   * @param start position of first element in sub-list
-   * @param stop position of last element in sub-list
-   *
-   * @return the sub-list specified by start and stop.
-   * @see Gee.AbstractList.slice
-   *
-   * @since 0.3.4
-   */
-  public override Gee.List<G>? slice (int start, int stop)
-  {
-    return this._linked_list.slice (start, stop);
-  }
-
-  /**
-   * Returns the first element in this structure.
-   *
-   * @return the first element in the structure. Fails if the structure is
-   * empty.
-   * @see Gee.AbstractList.first
-   *
-   * @since 0.3.4
-   */
-  public override G first ()
-  {
-    return this._linked_list.first ();
-  }
-
-  /**
-   * Returns the first element in this structure.
-   *
-   * @return the last element in the structure. Fails if the structure is empty.
-   * @see Gee.AbstractList.last
-   *
-   * @since 0.3.4
-   */
-  public override G last ()
-  {
-    return this._linked_list.last ();
-  }
-
-  /**
-   * Adds all the elements of the given collection to this one (as necessary).
-   *
-   * @param collection a {@link Gee.Collection} of elements to add.
-   *
-   * @return `true` if new elements were added to the collection.
-   * @see Gee.AbstractCollection.add_all
-   *
-   * @since 0.3.4
-   */
-  public override bool add_all (Collection<G> collection)
-  {
-    bool modified = false;
-
-    foreach (G item in collection)
-      modified |= add(item);
-
-    return modified;
-  }
-
-
-  /**
-   * Returns the Iterator for this structure. The iterator supports
-   * bi-directional iteration.
-   *
-   * @return a {@link Gee.Iterator} that can be used for iteration over this
-   * structure.
-   * @see Gee.Iterator
-   *
-   * @since 0.3.4
-   */
-  public override Gee.Iterator<G> iterator ()
-  {
-    return new Iterator<G> (this);
-  }
-
-  /**
-   * Unimplemented method (incompatible with ordered set).
-   *
-   * @return nothing
-   * @see Gee.ListIterator
-   *
-   * @since 0.3.4
-   */
-  public override ListIterator<G> list_iterator ()
-  {
-    assert_not_reached ();
-  }
-
-
-  private class Iterator<G> : Object, Gee.Iterator<G>, BidirIterator<G>
-  {
-    private LinkedHashSet<G> _linked_hash_set;
-    private BidirIterator<G> _list_iterator;
-    private int _stamp;
-
-    public Iterator (LinkedHashSet<G> linked_hash_set)
-      {
-        this._linked_hash_set = linked_hash_set;
-        this._stamp = linked_hash_set._stamp;
-        this._list_iterator = linked_hash_set._linked_list.list_iterator ();
-      }
-
-    public bool next ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.next ();
-      }
-
-    public bool has_next ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.has_next ();
-      }
-
-    public bool first ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.first ();
-      }
-
-    public bool previous ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.previous ();
-      }
-
-    public bool has_previous ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.has_previous ();
-      }
-
-    public bool last ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.last ();
-      }
-
-    public new G? get ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-        return this._list_iterator.get ();
-      }
-
-    public void remove ()
-      {
-        assert (this._stamp == this._linked_hash_set._stamp);
-
-        /* Remove the entry from the linked list *and* the hash set.
-         * Note that we can't do this by calling this._linked_hash_set.remove(),
-         * as that would change the LinkedHashSet's stamp. Removing the item
-         * from the hash set doesn't disrupt the iteration, as it's iterating
-         * over the linked list.*/
-        var item = this.get ();
-
-        this._list_iterator.remove ();
-        this._linked_hash_set._hash_set.remove (item);
-      }
-  }
-}
diff --git a/tests/folks/Makefile.am b/tests/folks/Makefile.am
index b3111ac..31fa1f7 100644
--- a/tests/folks/Makefile.am
+++ b/tests/folks/Makefile.am
@@ -40,7 +40,6 @@ AM_VALAFLAGS = \
 # in order from least to most complex
 noinst_PROGRAMS = \
 	field-details \
-	linked-hash-set \
 	backend-loading \
 	aggregation \
 	$(NULL)
@@ -69,10 +68,6 @@ field_details_SOURCES = \
 	field-details.vala \
 	$(NULL)
 
-linked_hash_set_SOURCES = \
-	linked-hash-set.vala \
-	$(NULL)
-
 CLEANFILES = \
         *.pid \
         *.address \
@@ -84,7 +79,6 @@ MAINTAINERCLEANFILES = \
         backend_loading_vala.stamp \
         aggregation_vala.stamp \
         field_details_vala.stamp \
-        linked_hash_set_vala.stamp \
         $(NULL)
 
 EXTRA_DIST = \
diff --git a/tests/folks/linked-hash-set.vala b/tests/folks/linked-hash-set.vala
deleted file mode 100644
index b52f20a..0000000
--- a/tests/folks/linked-hash-set.vala
+++ /dev/null
@@ -1,404 +0,0 @@
-using Gee;
-using Folks;
-
-public class LinkedHashSetTests : Folks.TestCase
-{
-  public LinkedHashSetTests ()
-    {
-      base ("LinkedHashSet");
-      this.add_test ("set properties", this.test_set_properties);
-      this.add_test ("list properties", this.test_list_properties);
-      this.add_test ("object elements", this.test_object_elements);
-      this.add_test ("bgo640551", this.test_bgo640551);
-      this.add_test ("iterator", this.test_iterator);
-      this.add_test ("iterator removal", this.test_iterator_removal);
-      this.add_test ("iterator empty", this.test_iterator_empty);
-      this.add_test ("iterator navigation", this.test_iterator_navigation);
-    }
-
-  public override void set_up ()
-    {
-    }
-
-  public override void tear_down ()
-    {
-    }
-
-  public void test_set_properties ()
-    {
-      /* XXX: ensure that values = values_no_dupes with some duplicates added */
-      const int[] values = {5, 7, 7, 9};
-      const int[] values_no_dupes = {5, 7, 9};
-      LinkedHashSet<int> lhs;
-      int i;
-
-      /* some basic assumptions for our source data */
-      assert (values_no_dupes.length < values.length);
-
-      /*
-       * Without duplicates
-       */
-
-      lhs = new LinkedHashSet<int> (direct_hash, direct_equal);
-      assert (lhs.size == 0);
-
-      foreach (var v1 in values_no_dupes)
-        assert (lhs.add (v1));
-
-      assert (lhs.size == values_no_dupes.length);
-
-      for (i = 0; i < values_no_dupes.length; i++)
-        assert (lhs.contains (values_no_dupes[i]));
-
-      /*
-       * Again, with dupes
-       */
-
-      lhs = new LinkedHashSet<int> (direct_hash, direct_equal);
-      assert (lhs.size == 0);
-
-      /* we can't assert this add will always return true, since there are
-       * duplicates in the source array */
-      foreach (var v2 in values)
-        lhs.add (v2);
-
-      /* since the lhs should ignore duplicates, it should be the size of the
-       * unique array */
-      assert (lhs.size == values_no_dupes.length);
-
-      for (i = 0; i < values.length; i++)
-        assert (lhs.contains (values[i]));
-
-      for (i = 0; i < values_no_dupes.length; i++)
-        assert (lhs.contains (values_no_dupes[i]));
-
-      /* ensure we ignore duplicates */
-      assert (!lhs.add (values_no_dupes[0]));
-      assert (lhs.size == values_no_dupes.length);
-
-      /* ensure proper return value when removing (successfully and not) */
-      assert (lhs.remove (values_no_dupes[0]));
-      assert (lhs.size == (values_no_dupes.length - 1));
-      assert (!lhs.remove (values_no_dupes[0]));
-      assert (lhs.size == (values_no_dupes.length - 1));
-    }
-
-  public void test_list_properties ()
-    {
-      /* XXX: ensure that values = values_no_dupes with some duplicates appended
-       */
-      const int[] values = {1, 3, 2, 3, 1, 2, 2};
-      const int[] values_no_dupes = {1, 3, 2};
-      int i;
-      LinkedHashSet<int> lhs;
-
-      lhs = new LinkedHashSet<int> (direct_hash, direct_equal);
-      assert (lhs.size == 0);
-      /* this item shouldn't exist, so we should get a negative return value */
-      assert (lhs.index_of (1) < 0);
-
-      /*
-       * Without duplicates
-       */
-      foreach (var val in values_no_dupes)
-        lhs.add (val);
-
-      assert (lhs.first () == values_no_dupes[0]);
-      assert (lhs.last () == values_no_dupes[values_no_dupes.length - 1]);
-
-      i = 0;
-      foreach (var val in lhs)
-        {
-          assert (i < values_no_dupes.length);
-          assert (val == values_no_dupes[i]);
-          i++;
-        }
-
-      /*
-       * With duplicates
-       */
-      lhs = new LinkedHashSet<int> (direct_hash, direct_equal);
-      assert (lhs.size == 0);
-      /* this item shouldn't exist, so we should get a negative return value */
-      assert (lhs.index_of (1) < 0);
-
-      foreach (var val in values)
-        lhs.add (val);
-
-      /* check that lhs matches the content (and ordering of) values_no_dupes,
-       * not values, since lhs will have ignored additional duplicates */
-      assert (lhs.first () == values_no_dupes[0]);
-      assert (lhs.last () == values_no_dupes[values_no_dupes.length - 1]);
-
-      i = 0;
-      foreach (var val in lhs)
-        {
-          assert (i < values_no_dupes.length);
-          assert (val == values_no_dupes[i]);
-          i++;
-        }
-    }
-
-  private class Dummy : GLib.Object
-    {
-      public string name { get; construct; }
-
-      public Dummy (string name)
-        {
-          Object (name: name);
-        }
-
-      public static uint hash_func (Dummy d)
-        {
-          return str_hash (d.name);
-        }
-
-      public static bool equal_func (Dummy d1, Dummy d2)
-        {
-          return str_equal (d1.name, d2.name);
-        }
-    }
-
-  public void test_object_elements ()
-    {
-      /* XXX: ensure that values = values_no_dupes with some duplicates appended
-       */
-      string[] values = {"Mac", "Charlie", "Dennis", "Frank", "Charlie"};
-      string[] values_no_dupes = {"Mac", "Charlie", "Dennis", "Frank"};
-      int i;
-      LinkedList<Dummy> ll;
-      HashSet<Dummy> hs;
-      LinkedHashSet<Dummy> lhs;
-
-      /* FIXME: remove this cast once libgee catches up with Vala's delegate
-       * definitions */
-      ll = new LinkedList<Dummy> ((GLib.EqualFunc) Dummy.equal_func);
-      hs = new HashSet<Dummy> ((GLib.HashFunc) Dummy.hash_func,
-          (GLib.EqualFunc) Dummy.equal_func);
-      lhs = new LinkedHashSet<Dummy> ((GLib.HashFunc) Dummy.hash_func,
-          (GLib.EqualFunc) Dummy.equal_func);
-      assert (lhs.size == 0);
-
-      /*
-       * Without duplicates
-       */
-      foreach (var val in values_no_dupes)
-        {
-          var dummy = new Dummy (val);
-          ll.add (dummy);
-          hs.add (dummy);
-          lhs.add (dummy);
-        }
-
-      assert (lhs.first ().name == values_no_dupes[0]);
-      assert (lhs.last ().name == values_no_dupes[values_no_dupes.length - 1]);
-
-      foreach (var val in ll)
-        assert (lhs.contains (val));
-
-      foreach (var val in hs)
-        assert (lhs.contains (val));
-
-      i = 0;
-      foreach (var val in ll)
-        {
-          assert (lhs.get (i).name == val.name);
-          assert (lhs.index_of (val) == i);
-          i++;
-        }
-
-      /*
-       * With duplicates
-       */
-      /* FIXME: remove this cast once libgee catches up with Vala's delegate
-       * definitions */
-      ll = new LinkedList<Dummy> ((GLib.EqualFunc) Dummy.equal_func);
-      hs = new HashSet<Dummy> ((GLib.HashFunc) Dummy.hash_func,
-          (GLib.EqualFunc) Dummy.equal_func);
-      lhs = new LinkedHashSet<Dummy> ((GLib.HashFunc) Dummy.hash_func,
-          (GLib.EqualFunc) Dummy.equal_func);
-      assert (lhs.size == 0);
-
-      foreach (var val in values)
-        {
-          var dummy = new Dummy (val);
-          ll.add (dummy);
-          hs.add (dummy);
-          lhs.add (dummy);
-        }
-
-      assert (lhs.first ().name == values_no_dupes[0]);
-      assert (lhs.last ().name == values_no_dupes[values_no_dupes.length - 1]);
-
-      foreach (var val in ll)
-        assert (lhs.contains (val));
-
-      foreach (var val in hs)
-        assert (lhs.contains (val));
-
-      i = 0;
-      /* note that lhs and ll are swapped vs. the similar test without dupes */
-      foreach (var val in lhs)
-        {
-          assert (ll.get (i).name == val.name);
-          i++;
-        }
-    }
-
-  /* derive a new string from the given one (purely for checking for leaks) */
-  private string _normalise_key (string key)
-    {
-      return key.down ();
-    }
-
-  public void test_bgo640551 ()
-    {
-      /* This resembles the compound structure used by the Telepathy backend's
-       * ImDetails implementation in Tpf.Persona (which has caused memory leaks
-       * in the past - see bgo#640551) */
-      var global_im_addresses =
-          new HashTable<string, LinkedHashSet<string>> (str_hash, str_equal);
-      var im_address_set = new LinkedHashSet<string> ();
-      const string protocol = "foo protocol";
-      const string address = "bar@example.org";
-      const string address2 = "bar2@example.org";
-
-      im_address_set.add (this._normalise_key (address));
-      im_address_set.add (this._normalise_key (address2));
-
-      var im_addresses =
-          new HashTable<string, LinkedHashSet<string>> (str_hash, str_equal);
-      im_addresses.insert (protocol, im_address_set);
-
-      im_addresses.foreach ((k, v) =>
-        {
-          var cur_protocol = (string) k;
-          var cur_addresses = (LinkedHashSet<string>) v;
-          var im_set = global_im_addresses.lookup (cur_protocol);
-
-          if (im_set == null)
-            {
-              im_set = new LinkedHashSet<string> ();
-              global_im_addresses.insert (cur_protocol, im_set);
-            }
-
-          im_set.add_all (cur_addresses);
-        });
-    }
-
-  /* Test that LinkedHashSet.iterator() works at a basic level */
-  public void test_iterator ()
-    {
-      HashSet<int> values = new HashSet<int> ();
-      LinkedHashSet<int> lhs = new LinkedHashSet<int> ();
-
-      /* Set up the values and insert them into the HashSet */
-      for (var i = 0; i < 10; i++)
-        {
-          values.add (i);
-          lhs.add (i);
-        }
-
-      /* We don't make any assertions about the order; just that exactly the
-       * right set of values is returned by the iterator. */
-      var iter = lhs.iterator ();
-
-      while (iter.next ())
-        {
-          var i = iter.get ();
-          assert (values.remove (i));
-        }
-
-      assert (values.size == 0);
-    }
-
-  public void test_iterator_removal ()
-    {
-      LinkedHashSet<int> lhs = new LinkedHashSet<int> ();
-
-      /* Set up the values and insert them into the HashSet */
-      for (var i = 0; i < 10; i++)
-        lhs.add (i);
-
-      /* Remove all the entries from the LinkedHashSet via Iterator.remove().
-       * Then, check that they've been removed. */
-      var iter = lhs.iterator ();
-
-      while (iter.next ())
-        iter.remove ();
-
-      assert (lhs.size == 0);
-
-      for (var i = 0; i < 10; i++)
-        assert (!lhs.contains (i));
-    }
-
-  public void test_iterator_empty ()
-    {
-      LinkedHashSet<int> lhs = new LinkedHashSet<int> ();
-      var _iter = lhs.iterator ();
-      assert (_iter is BidirIterator);
-      var iter = (BidirIterator<int>) _iter;
-
-      /* Check the iterator behaves correctly for an empty LinkedHashSet */
-      assert (!iter.next ());
-      assert (!iter.has_next ());
-      assert (!iter.first ());
-      assert (!iter.previous ());
-      assert (!iter.has_previous ());
-      assert (!iter.last ());
-    }
-
-  public void test_iterator_navigation ()
-    {
-      LinkedHashSet<int> lhs = new LinkedHashSet<int> ();
-
-      lhs.add (0);
-      lhs.add (1);
-      lhs.add (2);
-
-      var _iter = lhs.iterator ();
-      assert (_iter is BidirIterator);
-      var iter = (BidirIterator<int>) _iter;
-
-      assert (iter.has_next ());
-      assert (!iter.has_previous ());
-      assert (iter.next ());
-      assert (iter.get () == 0);
-
-      assert (iter.first ());
-      assert (iter.get () == 0);
-
-      assert (iter.has_next ());
-      assert (iter.next ());
-      assert (iter.has_previous ());
-      assert (iter.get () == 1);
-
-      assert (iter.first ());
-      assert (iter.get () == 0);
-
-      assert (iter.next ());
-      assert (iter.next ());
-      assert (iter.get () == 2);
-      assert (!iter.has_next ());
-      assert (iter.has_previous ());
-
-      assert (iter.last ());
-      assert (iter.get () == 2);
-
-      assert (iter.previous ());
-      assert (iter.get () == 1);
-    }
-}
-
-public int main (string[] args)
-{
-  Test.init (ref args);
-
-  TestSuite root = TestSuite.get_root ();
-  root.add_suite (new LinkedHashSetTests ().get_suite ());
-
-  Test.run ();
-
-  return 0;
-}