Ops.I forgot to add
- SortedMap - the same as in SortedSet but should return keys/map respectivly.

I disagree, Collection does not guarantee order.

But I agree that we should have the SortedList, SortedMap and SortedSet interfaces (interfaces or abstract classes but not implementations).

Methods:
 - first/last: why not.
 - range (from, to): similar to slice (start, stop) but the bounds are on values instead of on index. It could be implemented in the abstract classes with the iterators.
 - lessThan/greaterThan: not sure if it's useful, but why not.

For range/lessThan/greaterThan, I would prefer to see them implemented as view, i.e. they return iterators and we should define a method/constructor for inserting items/creating collections from iterators.

For instance:
var l1 = instance of List<int>.
var sl = new SortedListWrapper<int> (l);
var l2 = new ArrayList<int>.from_iterator (sl.range (-2, 120));

That should be great.

(In reply to comment #2)
> I disagree, Collection does not guarantee order.
> 

SortedColletions may guarantee... But I guess SortedIterable is.

> But I agree that we should have the SortedList, SortedMap and SortedSet
> interfaces (interfaces or abstract classes but not implementations).
> 

To be honset - why SortedList? Doesn't List support set and insert breaking sorting?

> Methods:
>  - first/last: why not.
>  - range (from, to): similar to slice (start, stop) but the bounds are on
> values instead of on index. It could be implemented in the abstract classes
> with the iterators.

The difference is that slice is about indexies and range is about keys. May be list should support.

>  - lessThan/greaterThan: not sure if it's useful, but why not.
> 
> For range/lessThan/greaterThan, I would prefer to see them implemented as view,
> i.e. they return iterators and we should define a method/constructor for
> inserting items/creating collections from iterators.
> 
> For instance:
> var l1 = instance of List<int>.
> var sl = new SortedListWrapper<int> (l);
> var l2 = new ArrayList<int>.from_iterator (sl.range (-2, 120));
> 
> That should be great.
> 

I'm working on base interfaces for my Tree* ;)
I have others ideas for libgee (which is finally being cared) I'll post soon... with patches :)

PS.
Should SortedListWrapper<T> return SortedMap<int, T>?

> For range/lessThan/greaterThan, I would prefer to see them implemented as view,
> i.e. they return iterators and we should define a method/constructor for
> inserting items/creating collections from iterators.

I meant by view a rw view as oppose of ro view.

(In reply to comment #3)
> (In reply to comment #2)
> > I disagree, Collection does not guarantee order.
> 
> SortedColletions may guarantee... But I guess SortedIterable is.

I do not understand.

> > But I agree that we should have the SortedList, SortedMap and SortedSet
> > interfaces (interfaces or abstract classes but not implementations).
> 
> To be honset - why SortedList? Doesn't List support set and insert breaking
> sorting?

Yes, you are right, but, semantically only a list is in a well defined order. What could be right 

> > Methods:
> >  - first/last: why not.
> >  - range (from, to): similar to slice (start, stop) but the bounds are on
> > values instead of on index. It could be implemented in the abstract classes
> > with the iterators.
>
> The difference is that slice is about indexies and range is about keys. May be
> list should support.

That is exactly why I said (or at least, tried to say). About keys for maps but values for sets (no keys in a set).

> >  - lessThan/greaterThan: not sure if it's useful, but why not.
> > 
> > For range/lessThan/greaterThan, I would prefer to see them implemented as view,
> > i.e. they return iterators and we should define a method/constructor for
> > inserting items/creating collections from iterators.
> > 
> > For instance:
> > var l1 = instance of List<int>.
> > var sl = new SortedListWrapper<int> (l);
> > var l2 = new ArrayList<int>.from_iterator (sl.range (-2, 120));
> > 
> > That should be great.
> > 
> 
> I'm working on base interfaces for my Tree* ;)
> I have others ideas for libgee (which is finally being cared) I'll post soon...
> with patches :)

Ok (unfortunately I won't be able to see them soon, I will go tomorrow on holidays).

> PS.
> Should SortedListWrapper<T> return SortedMap<int, T>?

I don't understand.
In my example, SortedListWrapper implements the SortedList interface adn SortedListWrapper.range returns an iterator.

(In reply to comment #5)
> (In reply to comment #3)
> > (In reply to comment #2)
> > > But I agree that we should have the SortedList, SortedMap and SortedSet
> > > interfaces (interfaces or abstract classes but not implementations).
> > 
> > To be honset - why SortedList? Doesn't List support set and insert breaking
> > sorting?
> 
> Yes, you are right, but, semantically only a list is in a well defined order.
> What could be right 

Er... I did not finish my sentence, sorry :).

So, what could be right would be to have a interface "X" which guarantee an order (just like List does currently) and which would be implemented by List and all sorted interfaces.

For instance, SortedSet would implements both Set and X.

(In reply to comment #5)
> (In reply to comment #3)
> > (In reply to comment #2)
> > > But I agree that we should have the SortedList, SortedMap and SortedSet
> > > interfaces (interfaces or abstract classes but not implementations).
> > 
> > To be honset - why SortedList? Doesn't List support set and insert breaking
> > sorting?
> 
> Yes, you are right, but, semantically only a list is in a well defined order.
> What could be right 
> 

No. From mathematical standpoint sorted set is tuple (S, <=) where S in an unordered set and <= is ordering relation.

Ordering relation have following properties
- reflexivity (a <= a)
- antisimetry (a <= b and b <= a is equivalent to a == b)
- transitivity (a <= b and b <= c implies a <= c)
(For performace reason usually function A x A -> {<,=,>} is defined but the 'isomorphism' may be shown betwean {A x A -> {<,=,>}, <=})

Accoriding to my knoledge on any set such relationship can be defined - and for sure for finite[1] - which are perfectly sufficient for vala. And the choice of function is left to user of library - and hence the order is well defined.

Now. The iteration of the set makes quarantee that each element will be returned once. Now we can define operation of iteration over sorted set as returning sunsequent elements with relation to each other. I.e. the first element is in relation with second which is relation to third. It does not break.
Other operations are operating as usual. The sorted set is therefore a set (if it looks like duck and quack like duck I call it a duck).

[1] For sets which order is less then continum bijection to some subsets of real numbers can be performed on which we have a natural order. For finite sets we of order n we have bijection to {1...n} can be performed. Defining addition seems to be a bit trickier in such approach but I belive that injection to rational is sufficient.

Ok let start some design here.

We will not enforce any ordering of Lists and Iterators, unless by using views. Indeed nothing in their API contract says that they inherently provide ordering among their elements, but just follow the insertion order. Let's postpone this when we will have collection change events set up (planed for 0.7.0).

We can already start by extracting SortedSet and SortedMap interfaces from the TreeSet and TreeMap implementations. Let's use this ticket for that.

TreeSet and TreeMap inherently provide ordering while maintaining the storage for their elements. Thus we can define two interfaces providing services that use that natural ordering. Here is, in a glance, my proposal of the provided services:

- Subset/Submap methods: head_set, tail_set and sub_set would respectively return the subsets before a specified element, after that specified element,  and between two specified elements.

- First, last elements, keys and entries: first, last would provide the first and last element of a sorted set. first_key, last_key, first_entry, last_entry would provide the first and last key, first and last entries of a sorted map. We could also define poll_{first|last|first_entry|last_entry} that also removes instead of just returning from the set|map.

- Navigation methods: lower, higher, floor and ceil sets of methods to respectively get the greatest element that is strictly less than a specified element, the least element that is strictly greater than the specified element, the greatest element that is less than or equal to the specified element, and the least element that is greater than or equal to the specified element.

- Reversed set|map and iterator methods: descending_set, descending_map, and descending_iterator that would be the reversed order views of the original sets, maps and iterators.

(In reply to comment #8)
> Ok let start some design here.
> 
> We will not enforce any ordering of Lists and Iterators, unless by using views.

Iintroduced Ordered interface with just first/last. It simply inforsm that any order is preserved (i.e. inserting order, sorting order) so this operation make any sense.

> Indeed nothing in their API contract says that they inherently provide ordering
> among their elements, but just follow the insertion order. Let's postpone this
> when we will have collection change events set up (planed for 0.7.0).
> 

I'll concentrate on the current work. I introduced bi-directional iterators - helps me write several methods as wrappers around the others making implementation less complex. 

I guess I just post the series of patches and then I may start refactoring.

> We can already start by extracting SortedSet and SortedMap interfaces from the
> TreeSet and TreeMap implementations. Let's use this ticket for that.
> 
> TreeSet and TreeMap inherently provide ordering while maintaining the storage
> for their elements. Thus we can define two interfaces providing services that
> use that natural ordering. Here is, in a glance, my proposal of the provided
> services:
> 
> - Subset/Submap methods: head_set, tail_set and sub_set would respectively
> return the subsets before a specified element, after that specified element, 
> and between two specified elements.
> 

I started with sets.

I took such relationships:
head_set(G item);
tail_set(G item);
sub_set(G? first, G? last);

s.subset(a, b) = {x in s : a <= x < b}
head_set = s.subset(null,b) = {x in s : x < b}
tail_set = s.subset(a,null) = {x in s : a <= x }

But I can change it.

head_set/tail_set scafford implementation done.

> - First, last elements, keys and entries: first, last would provide the first
> and last element of a sorted set. first_key, last_key, first_entry, last_entry
> would provide the first and last key, first and last entries of a sorted map.
> We could also define poll_{first|last|first_entry|last_entry} that also removes
> instead of just returning from the set|map.
> 

See ordered ;). Implemented

- Iterator findings:
	/**
	 * Returns the iterator pointing at the given element. Returns null if not
	 * found.
	 */
	public abstract Gee.Biiterator<G>? find (G item);
	/**
	 * Returns the iterator pointing at the given element or the largest lower
	 * then the element.
	 */
	public abstract Gee.Biiterator<G> find_ceil (G item);
	/**
	 * Returns the iterator pointing at the given element or the smallest bigger
	 * then the element.
	 */
	public abstract Gee.Biiterator<G> find_floor (G item);

Written in SortedSet<G>

> - Navigation methods: lower, higher, floor and ceil sets of methods to
> respectively get the greatest element that is strictly less than a specified
> element, the least element that is strictly greater than the specified element,
> the greatest element that is less than or equal to the specified element, and
> the least element that is greater than or equal to the specified element.
> 

Scaffold implementation in terms of finding iterators done.

> - Reversed set|map and iterator methods: descending_set, descending_map, and
> descending_iterator that would be the reversed order views of the original
> sets, maps and iterators.

Scaffold implementation trivial in terms of bi-directional iterators.

Map not touched yet.

Created attachment 142767 [details] [review]
0001-Added-Ordered-interface.patch

Some random dump of work. It is not finished yet but it may help if the feedback on interface will be given.

Created attachment 142768 [details] [review]
0002-Add-Gee.AbstractOrdered-G.patch

Created attachment 142770 [details] [review]
0003-Add-bi-directional-iterators.patch

Created attachment 142771 [details] [review]
0004-Add-SortedSet-interface.patch

Hi Maciej,

This is a nice piece of work and I am glad you did split it :) All in all, I'm eager to integrate your work.

Some comments:
- Introducing Ordered is a good thing.

- I'm not sure of the interest to introduce the AbstractOrdered abstract classes. Both AbstractList and AbstractSortedSet will implement first, last and the bidirectionnal iterator differently.

- Are the find_floor, find_ceil, ... really usefull or do they do the same as find ?

- Could we rename Biiterator as BiIterator, or BidirIterator ? Also could we add first() and last() methods to BiIterator to move to start and end of the ordered ? The work about the bidirectionnal iterator joins the one in 589800. ListIterator could inherit from BiIterator, and just add the index, set, and add methods.

(In reply to comment #14)
> Hi Maciej,
> 
> This is a nice piece of work and I am glad you did split it :) All in all, I'm
> eager to integrate your work.
> 
> Some comments:
> - Introducing Ordered is a good thing.
> 
> - I'm not sure of the interest to introduce the AbstractOrdered abstract
> classes. Both AbstractList and AbstractSortedSet will implement first, last and
> the bidirectionnal iterator differently.
> 
> - Are the find_floor, find_ceil, ... really usefull or do they do the same as
> find ?
> 

IMHO - yes. First of all I can implement the 4 other methods (lower, higher, floor and ceil) in terms of them and they will probably used in Subset scaffold implementation. 

> - Could we rename Biiterator as BiIterator, or BidirIterator ?

That's the first name I came with - that's all. I just found BiDirectionalIterator a bit too long ;)
I'd prefere BidirIterator but I'm rather indifferent in this matter

> Also could we
> add first() and last() methods to BiIterator to move to start and end of the
> ordered ? The work about the bidirectionnal iterator joins the one in 589800.
> ListIterator could inherit from BiIterator, and just add the index, set, and
> add methods.

Well - in case of bidiriterator add could be used as 'hint' adding (I'm not sure if it is possible with current implementation) to set.

Patches are updated and few fixes are added. However I had little time today.

I've updated the interface Iterator and BidirIterator in such way:

	/**
	 * Advances to the next element in the iteration. If element does not
	 * exists it puts iterator in past-the-end state. Further calls will not
	 * affect such state.
	 *
	 * @return true if the iterator points to an element
	 */
	public abstract bool next ();

	/**
	 * Checks if the next element exists.
	 *
	 * @return true if the iterator has a next element
	 */
	public abstract bool has_next ();
	
	/**
	 * Resets the iterator making it pointing at first element. If such element
	 * does not exists iterator is before-the-beginning state.
	 *
	 * @return true if the iterator is pointing at the first element
	 */
	public abstract bool first ();

	/**
	 * Returns the current element in the iteration.
	 *
	 * @return the current element in the iteration
	 */
	public abstract G? get ();

----------------

	/**
	 * Go back to the previous element in the iteration. If element does not
	 * exists it moves the iterator to before the beginning state.
	 *
	 * @return true if the iterator points at an element
	 */
	public abstract bool prev ();

	/**
	 * Checks if the previous element exists.
	 *
	 * @return true if the iterator has a previous element
	 */
	public abstract bool has_next ();
	
	/**
	 * Resets the iterator making it pointing at last element. If such element
	 * does not exists iterator is past-the-end state.
	 *
	 * @return true if the iterator is pointing at the last element
	 */
	public abstract bool last ();

It is to make semantic of next/prev more precise. I haven't finished updating the other collections to new interface but comment will be welcome before that.

Created attachment 143555 [details] [review]
0001-Fix-of-Tree-iterators-to-confirm-the-specification.patch

First of the wanted patches

Created attachment 143556 [details] [review]
0002-Add-SortedSet-interface.patch

Second of the wanted patches.

TODO:
- Maps
- Find new name for find

Created attachment 143639 [details] [review]
0001-Add-SortedMap-interface.patch

Created attachment 143675 [details] [review]
0001-Fix-of-Tree-iterators-to-confirm-the-specification.patch

Rebased against master

Created attachment 143676 [details] [review]
0002-Add-SortedSet-interface.patch

Created attachment 143677 [details] [review]
0003-Add-SortedMap-interface.patch

Unfinished rebase against master. Not-compiling parts commented-out (I'm looking for source of problems).

Created attachment 143679 [details] [review]
0002-Add-SortedSet-interface.patch

Fix whitespaces

Created attachment 143681 [details] [review]
0003-Add-SortedMap-interface.patch

- Fix whitespace
- Add ascending entries (commented out)

Please note that it do not compile (C errors).

Created attachment 143773 [details] [review]
0002-Add-SortedSet-interface.patch

Created attachment 143774 [details] [review]
0003-Add-SortedMap-interface.patch

Let me change the ticket summary to better reflect current situation.

(In reply to comment #27)
> Let me change the ticket summary to better reflect current situation.

Ok. The patches seems to be a bit outdated now so I marked them obsolete. I'll attach new one when I finish testing.

Created attachment 144113 [details] [review]
0001-Add-missing-DEBUG-section.patch

Missing #if DEBUG/#endif statement (problems if someone is running with CONSISTENCY_CHECKS and w/out DEBUG).

Created attachment 144114 [details] [review]
0002-Add-SortedSet-interface.patch

100% covered (C0 and I belive C1) by tests.

(In reply to comment #30)
> Created an attachment (id=144114) [details]
> 0002-Add-SortedSet-interface.patch
> 
> 100% covered (C0 and I belive C1) by tests.

Ups. I haven't notice that tests were made (always has been?) non-virtual.

Created attachment 144149 [details] [review]
0002-Add-SortedSet-interface.patch

Simply remove unneeded == true.

Created attachment 144166 [details] [review]
0002-Add-SortedSet-interface.patch

commit d5e6a680d6ebb0ffc5a9985a09f70473001f5e9f
Author: Maciej Piechotka <uzytkownik2@gmail.com>
Date:   Mon Sep 14 20:09:43 2009 +0200

    Introduce the SortedSet interface and implement it in TreeSet

We now just miss SortedMap.

Created attachment 144400 [details] [review]
0001-Add-SortedMap-interface.patch

Patch. However 2 things are missing:
- Vala seems to compile get_value as the V==string was generic parameter and tries to call self->priv->v_destroy_func which does not compile. I belive it is Vala problem but I haven't check it deeply
- Vala seems to have problems with templates and for some reasons not allows to make EntrySet a SortedSet (bug 596549).

Created attachment 144414 [details] [review]
0001-Add-SortedMap-interface.patch

get_value problem is fixed upstream.

Instead of being commented out the not-compiling part is in #if SORTED_SET_IN_SORTED_MAP.

Created attachment 144415 [details] [review]
0001-Add-SortedMap-interface.patch

I blindly assumed that if it compiles with SET_TESTS_ASSERT_VALUE it compiles anyway. However even chaning it to #if true stops it from being compiled as VALAFLAGS are not passed to tests. Sorry for misinformation

Created attachment 145003 [details] [review]
0001-Add-read_only_view-to-SortedSet.patch

Read only instance of SortedSet.

Created attachment 145021 [details] [review]
0001-Add-read_only_view-to-SortedSet.patch

Created attachment 145022 [details] [review]
0002-Add-read_only_view-to-SortedMap.patch

Created attachment 164161 [details] [review]
0001-Preparation-for-new-Map.set-method.patch

Updated against libgee 0.5.1 & vala 0.8.1

Created attachment 164162 [details] [review]
0002-Fix-wrong-copyright-information.patch

Created attachment 164163 [details] [review]
0003-Add-SortedMap-interface.patch

Created attachment 164164 [details] [review]
0004-Add-read_only_view-to-SortedSet.patch

Created attachment 164165 [details] [review]
0005-Add-read_only_view-to-SortedMap.patch

The current patches are on https://gitorious.org/~uzytkownik/libgee/mpiechotkas-libgee/commits/sorted-collections

One may fetch by git://gitorious.org/~uzytkownik/libgee/mpiechotkas-libgee.git branch sorted-collections.

0.7.0 includes SortedMap. While it is not the whole interface I would like to include it is necessary to wait for bug #596549 to include the rest.

(In reply to comment #47)
> 0.7.0 includes SortedMap. While it is not the whole interface I would like to
> include it is necessary to wait for bug #596549 to include the rest.

It seems that I cannot find what's missing. Marking as resolved.