GNOME Bugzilla – Bug 645684
Implement Iterator on LinkedHashSet
Last modified: 2011-04-16 13:45:14 UTC
(This bug was originally filed as number 645679, but then Bugzilla went and lost data, so I'm refiling.) Currently, if Iterator.remove() is called on an Iterator returned from a LinkedHashSet, the item will be removed from the LinkedHashSet's linked list, but not from its hash set. To solve this, we need to implement an Iterator subclass for LinkedHashSet. Branch coming up to do this. This blocks my work on bug #640092.
Created attachment 184242 [details] Squashed diff of the 64567-linked-hash-set-iterators branch
Created attachment 184243 [details] [review] Squashed diff of the 645684-linked-hash-set-iterators branch Ignore the previous patch; I uploaded too early. http://git.collabora.co.uk/?p=user/pwith/folks;a=shortlog;h=refs/heads/645684-linked-hash-set-iterators This adds an Iterator subclass to LinkedHashSet and a load of tests for LinkedHashSets in general.
Review of attachment 184243 [details] [review]: public override ListIterator<G> list_iterator () { - return this._linked_list.list_iterator (); + assert_not_reached (); } Can we really claim that LinkedHashSet implements AbstractList if we effectively don't implement this function? I do suppose that's better than letting the client inject elements in a violation of the set properties, though. Other than that, this looks good.
(In reply to comment #3) > Review of attachment 184243 [details] [review]: > > public override ListIterator<G> list_iterator () > { > - return this._linked_list.list_iterator (); > + assert_not_reached (); > } > > Can we really claim that LinkedHashSet implements AbstractList if we > effectively don't implement this function? I do suppose that's better than > letting the client inject elements in a violation of the set properties, > though. I think this kind of conflict is inevitable when trying to conflate the concepts of set and list. Nothing was using LinkedHashSet.list_iterator().
Comment on attachment 184243 [details] [review] Squashed diff of the 645684-linked-hash-set-iterators branch Pushed to master with a spelling fix to a comment and s/LinkedHashMap/LinkedHashSet/ in NEWS: commit 858e80d7649ebe7af0553531a940098f6d3c8449 Author: Philip Withnall <philip.withnall@collabora.co.uk> Date: Thu Mar 24 13:19:12 2011 +0000 Add navigation tests for LinkedHashSet.Iterator Helps: bgo#645684 tests/folks/linked-hash-set.vala | 59 ++++++++++++++++++++++++++++++++++++++ 1 files changed, 59 insertions(+), 0 deletions(-) commit 61ed5af3594831015fd52cf4c548ff1840ec334f Author: Philip Withnall <philip.withnall@collabora.co.uk> Date: Thu Mar 24 12:31:42 2011 +0000 Implement an Iterator for LinkedHashSet In order to ensure that calling Iterator.remove() on an iterator returned by LinkedHashSet.iterator() actually removes the item from both the linked list and hash set in the LinkedHashSet, we have to subclass Iterator ourselves. This means that all the LinkedHashSet tests pass once more. Closes: bgo#645684 NEWS | 3 ++ folks/linked-hash-set.vala | 77 ++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 78 insertions(+), 2 deletions(-) commit 34e89c9fdeba10c52238831cd6303fa7a2e9e2c3 Author: Philip Withnall <philip.withnall@collabora.co.uk> Date: Thu Mar 24 12:19:32 2011 +0000 Add stamping to LinkedHashSet Since we don't have access to the stamps in the LinkedHashSet's linked list or hash set, we have to maintain our own. This is necessary for implementing our own Iterator. (See next commit.) Helps: bgo#645684 folks/linked-hash-set.vala | 11 ++++++++++- 1 files changed, 10 insertions(+), 1 deletions(-) commit f311735144325c44de2c542415fcf65913d9e286 Author: Philip Withnall <philip.withnall@collabora.co.uk> Date: Thu Mar 24 12:08:28 2011 +0000 Remove implementation of LinkedHashSet.list_iterator() The extra methods provided by ListIterator are all incompatible with the set qualities of LinkedHashSet, and would allow duplicate entries to be introduced into the set. LinkedHashSet.iterator() continues to return an iterator which uses the links in LinkedHashSet to provide fast iteration. Helps: bgo#645684 NEWS | 3 +++ folks/linked-hash-set.vala | 7 +++---- 2 files changed, 6 insertions(+), 4 deletions(-) commit c6f44b505999d259af5b262a69e57da31af611d0 Author: Philip Withnall <philip.withnall@collabora.co.uk> Date: Thu Mar 24 11:57:24 2011 +0000 Add tests for LinkedHashSet.iterator() Helps: bgo#645684 tests/folks/linked-hash-set.vala | 49 ++++++++++++++++++++++++++++++++++++++ 1 files changed, 49 insertions(+), 0 deletions(-)