GNOME Bugzilla – Bug 589800
Mutating iterators
Last modified: 2009-09-15 23:57:21 UTC
In many cases iterators can be used to improve efficiency of many operations. For example: - Inserting into linked list - Removing from linked list - Inserting into tree - Removing from tree I guess such changes can be made for iterators: - insert_after/insert_before for lists - remove for all structures - put_with_hint for sets. It should put in order but take a hint where to put value. Interfaces can get get_iterator reciving int/key/value to get an iterator pointing to specific element (or for key/value it can be named Operations like in bug 587134 could be avoided
I have thought about this in the past. I have a WIP implementation of a ListIterator interface and implementation for ArrayList which can be used only by List implementors. The interface currently is: public interface Gee.ListIterator<G> : GLib.Object, Gee.Iterator<G> { public abstract bool previous (); public abstract void go_to_end (); public abstract void go_to_begin (); public abstract int current_index (); public abstract void set (G item); } Adding inserting would be the next step.
I would propose the following additions: public interface Iterator<G> : Object { // ... public abstract void remove (); } public interface List<G> : Collection<G> { // ... public abstract ListIterator<G> list_iterator (); } public interface ListIterator<G> : Iterator<G> { public abstract int index (); public abstract bool previous (); public abstract bool has_next (); public abstract bool has_previous (); public abstract void set (G item); public abstract void add (G item); public abstract void move_to_first (); public abstract void move_to_last (); }
Partially implemented in (further) patches to bug 589521: Iterator next() - Moves to next element. true is returned on success has_next() - Checks if next() will succeed but without changing anything first() - Moves to first element and returns true. Otherwise is before-the-beginning state. get() - Returns element iterator is pointing at. If no such element exists null. remove() - Removes the current element. BidirIterator : Iterator prev()/has_prev()/last() - mirrow of next()/has_next()/first() OrderedIterator : BidirIterator add() - Adds with hint. Iterator may ignore the hint but it should not be worst then Collection.add. Iterator does not change position. ListIterator : OrderedIterator set() - Set the current elemet to something. add() - Adds after (overload of OrderedIterator method). Iterator does not change position. add_before() - Adds before. Iterator does not change element it's pointing at In case of empty list add and add_before are early synonimous - pointing past-the-end and before-the-beginning respectivly. Notes: Should Iterator and BidirIterator be merged? Random ideas: MultiIterator: skip_the_same () - Skips equal elements in MultiSet RandomAccessIterator: move_by(int i) - Moves by i positions with O(1) complexity move_to(int i) - Moves to i index with O(1) complexity. i < 0 indicates elements from end (-1 last element etc.)
Ops. One more: the_same_collection - checks if they iterating over the same collection. == - checks if they iterating over the same collection pointing at the same element.
commit 14e877f7f99a521db59174d77d4876f92c03e78d Author: Didier 'Ptitjes <ptitjes@free.fr> Date: Tue Sep 15 13:33:29 2009 +0200 Introduce the ListIterator interface and make lists implement it commit 968fca3ccf9151f573e5d559bf0dc79c011b7d8a Author: Maciej Piechotka <uzytkownik2@gmail.com> Date: Mon Sep 14 20:09:43 2009 +0200 Introduce the BidirIterator interface commit a372fb799e3a7ac8a6df639153ceee5e9feed375 Author: Didier 'Ptitjes <ptitjes@free.fr> Date: Tue Sep 15 17:07:36 2009 +0200 Introduce remove method to the Iterator interface commit 5b2e267494ee7e20a02ab9e04ea1d984f20660c9 Author: Didier 'Ptitjes <ptitjes@free.fr> Date: Mon Sep 14 20:51:06 2009 +0200 Add has_next and first methods to the Iterator interface