list strawman

list strawman

[Stephen Leake]

I've done a priliminary implementation of
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
using SAL lists as the base. It implements fully
safe iterators. The sorting nested package is not implemented, mostly
because I didn't have time, but also because there are some design
issues (I'll talk about that in a separate post).

See http://users.erols.com/leakstan/Stephe/Ada/strawman-sal.html to
Download my the source. It relies on a slightly modified version of
SAL (two added functions); if you want to actually compile it, either
add the functions yourself (should be obvious), or send me an email.

There is only a simple test; it demonstrates the operation of "&".
But it uses an iterator to print the lists, so it's actually a good
test. I'll try to use Ted's test harness when that is ready.

This was an interesting excersize. I got quite stuck on making the
iterators safe, while at the same time not requiring the user to use
'Unchecked_Access. A hint from http://homepage.ntlworld.com/ramatthews/
(Robert A. Matthews' GAPSE) set me straight; use a layer of indirection.

There are three source directories: Iterator_1, Iterator_2, and
Source. The Iterator directories show early attempts at implementing
safe iterators; the file "iterator_design.text" describes the attempts
and the final result.

The final implementation is quite complex (and I haven't done sort
yet). I don't think I will ever use this package in a real project.
Just writing all the tests to prove that iterators actually are safe
will take quite a while. But it is an interesting example of what can
be done.

-- 
-- Stephe

Re: list strawman

[Ted Dennison]

In article <ug05j42sp.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>I've done a priliminary implementation of
>http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
..
>This was an interesting excersize. I got quite stuck on making the

Yes it is, isn't it? :-)

>iterators safe, while at the same time not requiring the user to use
>'Unchecked_Access. A hint from http://homepage.ntlworld.com/ramatthews/
>(Robert A. Matthews' GAPSE) set me straight; use a layer of indirection.

I ended up doing almost exactly the same thing. 

>The final implementation is quite complex (and I haven't done sort
>yet). I don't think I will ever use this package in a real project.
>Just writing all the tests to prove that iterators actually are safe
>will take quite a while. But it is an interesting example of what can
>be done.

Things that I have stumbled over so far:

The Iterator Adjust routine needs to add the new iterator to its list's iterator
list(s). You do this.

The List Adjust routine should wipe out any iterator lists, as they belong to
the source List (and visa versa), not the target. You don't deal with this.

The List Finalize routine needs to invalidate any iterators on the list's
iterator list. You don't do this. (The comment says you do, but you just seem to
be calling Unchecked_Conversion on the list header, unless I am missing
something)

The Iterator Finalize routine needs to remove its entry from the list it belongs
to's iterator list. You do this.

The List and Iterator Initialize routines have to allocate new list and iterator
structures respectively before they do anything else. The list Initialize does
this, but the iterator one looks like it tries to dereference the (null) pointer
immediately. You say you've tested with iterators, so you must have gotten this
to work somehow, but I'm mystified as to how (unless it was the passive iterator
generic).

A subtle point: Iterators may have the "No_Item" condition, but still be validly
associated with a list (eg: An empty list that you want to add items to with
"Insert").

When elements are removed from a list, you have to invalidate any iterator
entires that may point to that element. It doesn't look like this is being done
in "Remove" (end or iterator versions).

Item doesn't seem to be checking for the No_Item condition. 

Perhaps something is going on in the Sal.Poly.Lists.Double package with
iterators to take care of these last two issues. I don't have it, so I can't
tell. But I'm guessing not, since the iterator is defined in the private part,
and those don't look like child packages.

Efficiency issues:

I discovered it is possible to get rid of all dynamic allocations in iterator
manipulations. This can be accomplished by using an aliased subrecord within the
iterator itself as the List's iterator list node. A greasy hack, but it appears
to work. I think its actually *less* error prone this way, as you don't have to
worry about keeping a 1-to-1 correspondence between iterators and allocated
iterator list nodes from the lists's side. The only safety issue is implementing
the Adjust and Finalize routines correctly, rather than implementing every List
and Iterator manipulation routine correctly.

It also looks like it is possible to get rid of all list searches in iterator
manipulations. This can be accomplished by putting a node for the iterator in
lists for both the list (for splice and merge) and the pointed-to element (for
everything else). I haven't finished implementing this yet, so I'm not entirely
sure, but it looks like this method can also be used to make all iterator ops
O(1). A nice side benifit to doing this is that iterators can be made to travel
with the element when it chages lists (via Splice). We will have to discuss if
this is a Bad Thing or a Good Thing from a user perspective.

Anyway, sorry for all the criticism. Good work. Believe me, I know how much
effort it is to try to get this right. :-)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Ted Dennison]

In article <myj_7.7141$cD4.10982@www.newsranger.com>, Ted Dennison says...
>
>iterator list. You don't do this. (The comment says you do, but you just seem >to be calling Unchecked_Conversion on the list header, unless I am missing
Uhhh...that "Unchecked_Deallocation". Sorry for the confusion.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <ug05j42sp.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >I've done a priliminary implementation of
> >http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> ..
> >This was an interesting excersize. I got quite stuck on making the
> 
> Yes it is, isn't it? :-)
> 
> >iterators safe, while at the same time not requiring the user to use
> >'Unchecked_Access. A hint from http://homepage.ntlworld.com/ramatthews/
> >(Robert A. Matthews' GAPSE) set me straight; use a layer of indirection.
> 
> I ended up doing almost exactly the same thing. 

Cool. Great minds think alike? or just common environments lead to
common evolution :).

One issue I did not point out is the changes I had to make to the
spec. In particular, I had to declare "List" as tagged, and use 'class
in a couple places. Do you have any objections to that?

> >The final implementation is quite complex (and I haven't done sort
> >yet). I don't think I will ever use this package in a real project.
> >Just writing all the tests to prove that iterators actually are
> >safe will take quite a while. But it is an interesting example of
> >what can be done.
> 
> Things that I have stumbled over so far:

Well, I have _not_ done thorough testing, so it is quite possible
you've uncovered real bugs.

> The List Adjust routine should wipe out any iterator lists, as they
> belong to the source List (and visa versa), not the target. You
> don't deal with this.

Hmm. Adjust (List) explicitly sets the new list's iterator list to
null. The source list iterators are preserved, and the new list has no
iterators. Are you saying I should "wipe out" the source iterators,
and not preserve them? That's not what I would expect.

> The List Finalize routine needs to invalidate any iterators on the
> list's iterator list. You don't do this. (The comment says you do,
> but you just seem to be calling Unchecked_Conversion on the list
> header, unless I am missing something)

Actually Unchecked_Deallocation. That eventually calls Finalize on the
iterator list, which should invalidate all of them. A test case
proving this is needed.

> The List and Iterator Initialize routines have to allocate new list
> and iterator structures respectively before they do anything else.
> The list Initialize does this, but the iterator one looks like it
> tries to dereference the (null) pointer immediately. You say you've
> tested with iterators, so you must have gotten this to work somehow,
> but I'm mystified as to how (unless it was the passive iterator
> generic).

Yes, I've only used the passive generic (to print the lists), so maybe
I am missing something. 

There is a tradeoff between putting stuff in Initialize, and doing
stuff with aggregates when an object is created. If you assign an
aggregate to a Controlled object, Initialize is _not_ called (LRM 7.6
(10)). So any place you assign an aggregate to a Controlled object,
you have to be sure you do everything Initialize would do. I'm pretty
sure I haven't got that right yet.

> A subtle point: Iterators may have the "No_Item" condition, but
> still be validly associated with a list (eg: An empty list that you
> want to add items to with "Insert").

Yes. SAL just raises Constraint_Error for the No_Item condition; I do
not map that to the No_Item exception everywhere yet.

I just noticed that the No_Item exception is declared within the
generic Lists.Unbounded package, which means we get a different one
for each instantiation. We probably want to move that up to Lists or
ACL.

> When elements are removed from a list, you have to invalidate any
> iterator entires that may point to that element. It doesn't look
> like this is being done in "Remove" (end or iterator versions).

Yes, I haven't put that in yet. I wanted to write a test that failed
first, so I would know the test was valid :).

> Efficiency issues:
> 
> I discovered it is possible to get rid of all dynamic allocations in iterator
> manipulations. <snip>

I'd definitely like to see this.

> It also looks like it is possible to get rid of all list searches in iterator
> manipulations. <snip>

Are you sure you are considering all the nasty things users can do?
Like declaring several iterators to a list, but not actually using
them for anything.

> A nice side benifit to doing this is that iterators can be
> made to travel with the element when it chages lists (via Splice).
> We will have to discuss if this is a Bad Thing or a Good Thing from
> a user perspective.

I think that's a Bad Thing. But if it were clearly documented, maybe
it would be ok.

> Anyway, sorry for all the criticism. Good work. Believe me, I know
> how much effort it is to try to get this right. :-)

Hey, it was actually fun! It made me appreciate having written SAL;
having a working low-level list abstraction makes it easier to
implement the safe iterators. And doing this clarified some of the
design issues in SAL.

You might consider using my Test_Storage_Pools package in your test
harness; it makes it possible to find memory leaks as part of testing.

-- 
-- Stephe

Re: list strawman

[Stephen Leake]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> > The List and Iterator Initialize routines have to allocate new list
> > and iterator structures respectively before they do anything else.
> > The list Initialize does this, but the iterator one looks like it
> > tries to dereference the (null) pointer immediately. You say you've
> > tested with iterators, so you must have gotten this to work somehow,
> > but I'm mystified as to how (unless it was the passive iterator
> > generic).
> 
> Yes, I've only used the passive generic (to print the lists), so maybe
> I am missing something. 

I lied. My test case calls "&" (list, list), which uses an explicit
iterator. So this does work, somehow.

I found chasing thru the various layers of Initialize, Adjust, and
Finalize very confusing, espically for functions like "&" that must
allocate a temporary object to return. I have not done a lot of work
with Controlled types, and now I remember one reason why!

-- 
-- Stephe

Re: list strawman

[Ted Dennison]

In article <u3d1i3yns.fsf@gsfc.nasa.gov>, Stephen Leake says...
>I found chasing thru the various layers of Initialize, Adjust, and
>Finalize very confusing, espically for functions like "&" that must
>allocate a temporary object to return. I have not done a lot of work
>with Controlled types, and now I remember one reason why!

Same here (although being restricted to the library level was another reason).

I had an early version that tried to initailize a temporary object of that same
type within Adjust. That of course causes Adjust to be called within Adjust,
with no way out of the implicit recursion. I started to get a clue when the
program ran for several minutes, with the disk going like mad, ending in a
virtual memory exhaustion warning. :-(

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Ted Dennison]

In article <u7kqu3yux.fsf@gsfc.nasa.gov>, Stephen Leake says...
>One issue I did not point out is the changes I had to make to the
>spec. In particular, I had to declare "List" as tagged, and use 'class
>in a couple places. Do you have any objections to that?

If you could move the tagged-ness to the private section, I'd prefer that done.
Since its done entirely for implmentation reasons (right?), that's where it
goes. There's no need to dictate taggedness onto someone who might not need it.

>> The List Adjust routine should wipe out any iterator lists, as they
>> belong to the source List (and visa versa), not the target. You
>> don't deal with this.
>
>Hmm. Adjust (List) explicitly sets the new list's iterator list to
>null. The source list iterators are preserved, and the new list has no
>iterators. 

Ahhh, that's right. I see it now.

>> The List Finalize routine needs to invalidate any iterators on the
>> list's iterator list. You don't do this. (The comment says you do,
>> but you just seem to be calling Unchecked_Conversion on the list
>> header, unless I am missing something)
>
>Actually Unchecked_Deallocation. That eventually calls Finalize on the
>iterator list, which should invalidate all of them. A test case
>proving this is needed.

I don't see how this makes the jump from your List object to the iterator
object. In order for an iterator to know that its list is gone, you'd have to
tell the iterator somehow. Something would have to set the Iterator's IA field
to null, or its IA.List or IA.I fields to null or something. Just dynamicly
deallocating the List's iterators from its iterator list isn't going to do that.
Instead you'd leave the iterator's IA field pointing off into space somewhere.
Are you setting that to null somewhere that I'm not seeing?

>There is a tradeoff between putting stuff in Initialize, and doing
>stuff with aggregates when an object is created. If you assign an
>aggregate to a Controlled object, Initialize is _not_ called (LRM 7.6
>(10)). So any place you assign an aggregate to a Controlled object,
>you have to be sure you do everything Initialize would do. I'm pretty
>sure I haven't got that right yet.

I wouldn't call it a trade-off exactly. I use initialize for allocating
nessecary substructures (with default clean values), and nothing else. Finalize
needs to undo that, along with undoing any bookeeping work that other routines
might do. Adjust needs to take the copied fields and make newly-allocated unique
copies of any pointed-to objects (or not in the case of iterators). Every
Initialize will eventually get a finalize, as will every Adjust.

I think it would have helped me to see a matrix something like this:

Operation
Example           Controlled Primitives called
------------------------------------------------------------
Declaration  
A : Mytype;       Initialize (A);
Initialization 
A : Mytype := B;  Adjust (A);
Assignment
A := B;           Finalize (A); {fields copied} Adjust (A);

{Note: Often a temporary B will be created during assinment too,
in which case we have:
                 Adjust (Temp_B); Finalize (A); Adjust (A); Finalize (Temp_B);
)

>I just noticed that the No_Item exception is declared within the
>generic Lists.Unbounded package, which means we get a different one
>for each instantiation. We probably want to move that up to Lists or
>ACL.

That's a good point. We may want to move that up when we get more than one. Then
again, we could leave a renaming of it down here too.

>> It also looks like it is possible to get rid of all list searches in iterator
>> manipulations. <snip>
>
>Are you sure you are considering all the nasty things users can do?
>Like declaring several iterators to a list, but not actually using
>them for anything.

Yup. It doesn't matter. This is related to my previous point about getting rid
of dynamic allocations. If the list's iterator list node is actually part of the
iterator itself, then the iterator can just go straight to its own node to move
itself from one iterator list to another. Unfortunately, this requires that the
List's iterator lists are doubly-linked. It gets to be a bit hairy.

>> A nice side benifit to doing this is that iterators can be
>> made to travel with the element when it chages lists (via Splice).
>> We will have to discuss if this is a Bad Thing or a Good Thing from
>> a user perspective.
>
>I think that's a Bad Thing. But if it were clearly documented, maybe
>it would be ok.

I think its mostly an issue of how it could be used. If its reasonable to do
splices inside of an iteration loop, then we may want to do it. I'm not feeling
creative enough to visualise a need for it though.

>> Anyway, sorry for all the criticism. Good work. Believe me, I know
>> how much effort it is to try to get this right. :-)
>
>Hey, it was actually fun! It made me appreciate having written SAL;
>having a working low-level list abstraction makes it easier to
>implement the safe iterators. And doing this clarified some of the
>design issues in SAL.

I think it will actually be quite useful for 3rd-party component libraries to do
this, as they will be able to provide their own functionality as sort of an
extension to the "training-wheels" standard version. :-)

>You might consider using my Test_Storage_Pools package in your test
>harness; it makes it possible to find memory leaks as part of testing.

I actually have been checking for leaks too, with some code internal to the
package. I essentially increment an alloction counter at every "new" call,
decrement it at every Unchecked_Deallocation, and make sure its 0 when the Empty
list (declared in the spec) gets finalized. Its not task-safe, but it works for
a test.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <u7kqu3yux.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >One issue I did not point out is the changes I had to make to the
> >spec. In particular, I had to declare "List" as tagged, and use 'class
> >in a couple places. Do you have any objections to that?
> 
> If you could move the tagged-ness to the private section, I'd prefer
> that done. Since its done entirely for implmentation reasons
> (right?), that's where it goes. There's no need to dictate
> taggedness onto someone who might not need it.

I agree, but I needed the 'Class in functions returning Iterator to
avoid dispatching on two types. If I use 'Class in the public part,
the type has to be _publicly_ tagged.

An alternate solution is to wrap the Controlled iterator type in a
record, so that the public Iterator type is not itself tagged.

My current solution allows users to derive new types from List; I
figured that was a Good Thing.

> >> The List Finalize routine needs to invalidate any iterators on the
> >> list's iterator list. You don't do this. (The comment says you do,
> >> but you just seem to be calling Unchecked_Conversion on the list
> >> header, unless I am missing something)
> >
> >Actually Unchecked_Deallocation. That eventually calls Finalize on the
> >iterator list, which should invalidate all of them. A test case
> >proving this is needed.
> 
> I don't see how this makes the jump from your List object to the
> iterator object. In order for an iterator to know that its list is
> gone, you'd have to tell the iterator somehow. Something would have
> to set the Iterator's IA field to null, or its IA.List or IA.I
> fields to null or something. Just dynamicly deallocating the List's
> iterators from its iterator list isn't going to do that. Instead
> you'd leave the iterator's IA field pointing off into space
> somewhere. Are you setting that to null somewhere that I'm not
> seeing?

You're right; I'm not doing this right. I think it is easy to fix; in
Finalize (List), loop thru the Iterator_list, and call
Invalidate_Iterator. Apparently I meant to do that, because I declared
the subprogram Invalidate_Iterator, but I never call it :).

> >There is a tradeoff between putting stuff in Initialize, and doing
> >stuff with aggregates when an object is created. If you assign an
> >aggregate to a Controlled object, Initialize is _not_ called (LRM
> >7.6 (10)). So any place you assign an aggregate to a Controlled
> >object, you have to be sure you do everything Initialize would do.
> >I'm pretty sure I haven't got that right yet.
> 
> I wouldn't call it a trade-off exactly. I use initialize for
> allocating nessecary substructures (with default clean values), and
> nothing else. Finalize needs to undo that, along with undoing any
> bookeeping work that other routines might do. Adjust needs to take
> the copied fields and make newly-allocated unique copies of any
> pointed-to objects (or not in the case of iterators). Every
> Initialize will eventually get a finalize, as will every Adjust.

Yes, that is a good design policy. But currently, in Initialize
(Iterator), I add the iterator to the List's Iterator_List. So that
doesn't get done in some cases. I need to change this.

> I think it would have helped me to see a matrix something like this:
> 
> Operation
> Example           Controlled Primitives called
> ------------------------------------------------------------
> Declaration  
> A : Mytype;       Initialize (A);
> Initialization 
> A : Mytype := B;  Adjust (A);
> Assignment
> A := B;           Finalize (A); {fields copied} Adjust (A);
> 
> {Note: Often a temporary B will be created during assinment too,
> in which case we have:
>                  Adjust (Temp_B); Finalize (A); Adjust (A); Finalize (Temp_B);
> )

Yes, this is helpful. I suspect there is something like this in
Cohen's "Ada as a second language"; that's where it really belongs :).
We're supposed to assume readers "know the language"!

> >You might consider using my Test_Storage_Pools package in your test
> >harness; it makes it possible to find memory leaks as part of testing.
> 
> I actually have been checking for leaks too, with some code internal
> to the package. I essentially increment an alloction counter at
> every "new" call, decrement it at every Unchecked_Deallocation, and
> make sure its 0 when the Empty list (declared in the spec) gets
> finalized. Its not task-safe, but it works for a test.

Yes, but my Test_Storage_Pools does the same thing, without modifying
the source; it's a generic parameter (the storage_pool). That makes it
easier to take out in a release. And you don't have to worry about
forgetting a "new".

-- 
-- Stephe

Re: list strawman

[Ted Dennison]

In article <upu4l3jg9.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>> If you could move the tagged-ness to the private section, I'd prefer

>I agree, but I needed the 'Class in functions returning Iterator to
>avoid dispatching on two types. If I use 'Class in the public part,
>the type has to be _publicly_ tagged.
>
>An alternate solution is to wrap the Controlled iterator type in a
>record, so that the public Iterator type is not itself tagged.

That's precisely what I did. The iterator is not tagged, but is a record with
one field whose type is derived from Controlled. 

>You're right; I'm not doing this right. I think it is easy to fix; in
>Finalize (List), loop thru the Iterator_list, and call
>Invalidate_Iterator. Apparently I meant to do that, because I declared
>the subprogram Invalidate_Iterator, but I never call it :).

Right. That's the way it looked to me too.

>Yes, that is a good design policy. But currently, in Initialize
>(Iterator), I add the iterator to the List's Iterator_List. So that
>doesn't get done in some cases. I need to change this.

Ahhh, so I see. Which list are you talking about though? The user has never
specified a list at this point, and Object.IA.List (which you dereference) is
probably going to be null (not to mention Object.IA itself).

>> I actually have been checking for leaks too, with some code internal
>> to the package. I essentially increment an alloction counter at
>
>Yes, but my Test_Storage_Pools does the same thing, without modifying
>the source; it's a generic parameter (the storage_pool). That makes it
>easier to take out in a release. And you don't have to worry about
>forgetting a "new".

I may look into that, if its something that can easily be fit into a dumb test
case. The way I have it in there now is good to prove that there are no leaks to
someone who is interested, but its a bit of a hack and clutters up the code
quite a bit.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

RE: list strawman

[Steven Deller]

Rather than implement the package, I have worked at taking the spec and
using it to in other code (I like to see how a package stands up to
usage before implementing it :-)).

I found I could NOT implement a simple quicksort with the package as
defined, at least not with any efficiency.  What was missing was a
simple way to split a list into two lists at the point of an iterator.

That seems to me to be a fundamental flaw in the interface.  Yes, I know
sorting is predefined in the interface, but as there is only ONE sort
predefined, I'd think users might want to implement their own sort.
(Not to mention I think including sorting in a fundamental list package
to be questionable -- though I can't see how to also include a "insert
sorted" function without the concept of sortedness, so maybe it makes
sense.)

Wouldn't it be useful to add a procedure that takes an iterator and
returns a new list, with the list where the iterator was pointing now
truncated to a shorter list?  (That is, it returns two lists, one of
which is implicitly referred to by the iterator.)

Regards,
Steve

Re: RE: list strawman

[Ted Dennison]

In article <mailman.1010451062.16465.comp.lang.ada@ada.eu.org>, Steven Deller
says...
>That seems to me to be a fundamental flaw in the interface.  Yes, I know
>sorting is predefined in the interface, but as there is only ONE sort
>predefined, I'd think users might want to implement their own sort.

The sort used will probably be Quicksort too (yes, I know that's not your
point). 

I should point out two things here:

1) Anyone implementing something so low-level could always us a child package.
2) This is not really the appropriate package to use if sorting is very
important to you. That would be the *.Maps package (unwritten).

>Wouldn't it be useful to add a procedure that takes an iterator and
>returns a new list, with the list where the iterator was pointing now
>truncated to a shorter list?  (That is, it returns two lists, one of
>which is implicitly referred to by the iterator.)

Since we have a "Splice", I can't really sit here and argue that its inverse
function has no business being there. But I'd like to hear a few concurrances
that it needs to be in there before changing things.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Jean-Marc Bourguet]

Ted Dennison<dennison@telepath.com> writes:

> In article <mailman.1010451062.16465.comp.lang.ada@ada.eu.org>, Steven Deller
> says...
> >That seems to me to be a fundamental flaw in the interface.  Yes, I know
> >sorting is predefined in the interface, but as there is only ONE sort
> >predefined, I'd think users might want to implement their own sort.
> 
> The sort used will probably be Quicksort too (yes, I know that's not your
> point). 

How do you do quicksort on a list?  quicksort assume random access so
you'll have O(n) space overhead. I'd use a merge sort on a list which
would have the same complexity as quicksort and do not need random
access.

Yours,

-- 
Jean-Marc

Re: list strawman

[Ted Dennison]

In article <3c3b13ba$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>How do you do quicksort on a list?  quicksort assume random access so
>you'll have O(n) space overhead. I'd use a merge sort on a list which
>would have the same complexity as quicksort and do not need random
>access.

I don't see that. The way it works, all you have to keep track of is the ends of
the list (or sublist you are working on), the pivot point, and a couple of
pointers that iterate through the list. There's nothing in there that can't be
done easily with a doubly-linked list.

For an example of how this can be done in place (and thus no extra space
overhead), see http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort1a.html .
The example uses an array, but again there's nothing in there that can't be
trivially adapted to doubly-linked lists. 

There are even ways to do it in place without recursion...

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Jean-Marc Bourguet]

Ted Dennison<dennison@telepath.com> writes:

> In article <3c3b13ba$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
> >
> >How do you do quicksort on a list?  quicksort assume random access so
> >you'll have O(n) space overhead. I'd use a merge sort on a list which
> >would have the same complexity as quicksort and do not need random
> >access.
> 
> I don't see that. 

I'm sorry, I was thinking about heap sort.

> The way it works, all you have to keep track of is the ends of the
> list (or sublist you are working on), the pivot point, and a couple
> of pointers that iterate through the list. There's nothing in there
> that can't be done easily with a doubly-linked list.

Yes.  There is still the problem of choosing the pivot.  With random
access, I'd use a random element.  Without random access, you'll have
to choose the first or the last element and then degenerate in N^2 for
a sorted input, not something I'd like in a general purpose library.
Well taking a random element is possible but at a cost of iterating
some more time on the whole list.  Perhaps there is a way to even
choose the next pivot while you construct the upper and lower list but
I don't see one.

Well, I think I'd still choose a merge sort.

Yours,

-- 
Jean-Marc

Re: list strawman

[Ted Dennison]

In article <3c3b2aa0$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...
>
>I'm sorry, I was thinking about heap sort.

Ahh. Yeah, heapsort would probably be a bad idea in this package. In a *.Maps
package it might make sense, if things are already kept in a heap anyway. 

>Yes.  There is still the problem of choosing the pivot.  With random
>access, I'd use a random element.  Without random access, you'll have
>to choose the first or the last element and then degenerate in N^2 for
>a sorted input, not something I'd like in a general purpose library.

That's a good point. It would probably be fairly easy to alternate which side
the pivot is taken from. Then again, I think the advice to use a different
package if sorting is *really* important to you should mitagate this issue.
Also, we provide tools to insert into a pre-sorted list, so the only reason
anyone should ever hit the worst case is ignorance or really bad luck.

>Well, I think I'd still choose a merge sort.

I believe the splitting part of mergesort would involve a linear search for a
linked-list. That would take us into O(n*2) territory, if not worse. In my
student days I could figure out the exact factor...hmmm...perhaps its just
another nlogn...

Despite taking Computer Science Algorithms courses no less than 3 times (or
perhaps *because* I had to :-) ), I'm not really a sorting expert. But all the
literature I read highly suggests one use Quicksort, despite its theoretical
O(n**2) behavior. http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html is
a good example. 

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Jean-Marc Bourguet]

Ted Dennison<dennison@telepath.com> writes:

> In article <3c3b2aa0$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says...

[...]

> >Yes.  There is still the problem of choosing the pivot.  With
> >random access, I'd use a random element.  Without random access,
> >you'll have to choose the first or the last element and then
> >degenerate in N^2 for a sorted input, not something I'd like in a
> >general purpose library.
> 
> That's a good point. It would probably be fairly easy to alternate
> which side the pivot is taken from.

This will not change the behaviour in N^2 for a (nearly) sorted input.

[...]

> I believe the splitting part of mergesort would involve a linear
> search for a linked-list. That would take us into O(n*2) territory,
> if not worse. In my student days I could figure out the exact
> factor...hmmm...perhaps its just another nlogn...

Merge sort can be implemented in O(N log N) worst case, with a O(N)
for an already sorted input.
 
> Despite taking Computer Science Algorithms courses no less than 3
> times (or perhaps *because* I had to :-) ), I'm not really a sorting
> expert. But all the literature I read highly suggests one use
> Quicksort, despite its theoretical O(n**2)
> behavior. http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
> is a good example.

Most litterature I've read is about sorting arrays.  AFAIK, it is not
possible to do merge sort in place for arrays (but it is for linked
list, even singly linked list) and that's probably why this algorithm
is often neglected.

Yours,

-- 
Jean-Marc

Re: list strawman

[Ted Dennison]

Jean-Marc Bourguet <jm@bourguet.org> wrote in message news:<3c3bfabc$0$3190$626a54ce@news.free.fr>...
> Ted Dennison<dennison@telepath.com> writes:
> 
> > That's a good point. It would probably be fairly easy to alternate
> > which side the pivot is taken from.
> 
> This will not change the behaviour in N^2 for a (nearly) sorted input.

After thinking about it harder, you are right. Everything will allways
go on one side of the pivot, no matter which side you take it from. So
no "dividing" will actually happen, which is where this
divide-and-conquer algorithm gets its speed from.

> > I believe the splitting part of mergesort would involve a linear
> > search for a linked-list. That would take us into O(n*2) territory,
> > if not worse. In my student days I could figure out the exact
> > factor...hmmm...perhaps its just another nlogn...
> 
> Merge sort can be implemented in O(N log N) worst case, with a O(N)
> for an already sorted input.

OK. By arguing through repeated assertion, you are forcing to either
ignore you, or do the work of proof myself. Since I made the first
claim, its only fair that I do the work I guess...

...OK it looks like the work involved in doing *all* the splits using
linear searches is (n/2 + 2(n/4) + 4(n/8) ....) where n>1. Since there
is one of these factors for each "level", and there are logn levels,
that should work out to roughly (n/2)logn, or O(n logn). So you are
right that it is O(N log N) worst case. However, you are wrong about
the best case. With a linked-list, that is *also* O(N log N).

However, this also shows one the reasons why Quicksort is going to be
faster in practice. We haven't even done any of the real sorting work
yet, and we *already* have a factor of n logn to deal with. Quicksort
in the best case will do exactly that same amount of linear searching,
and be done sorting at the end of it!

Also note that if you were to modify the Quicksort routine to take a
middle pivot, you would get the exact same linear search factor added
in, and it would no longer suck at unordered lists. So your issue
actually degenerates to whether it is worth the speed hit to modify
Quicksort to use a middle pivot. If it is, *then* we can talk about if
mergesort would be quicker.

So again, its a matter of priorities. Algorithm aside, I don't think
that large sorted lists are worth slowing down everyone else.

> Most litterature I've read is about sorting arrays.  AFAIK, it is not
I noticed that too.

> possible to do merge sort in place for arrays (but it is for linked
> list, even singly linked list) and that's probably why this algorithm
> is often neglected.

Perhaps, but then the linear searches required to do the splits kind
of make up for that, don't they?

The impression I got from my last two Algorithms courses was the the
basic problem with Mergesort wasn't its time behavior, but (in
algorithm terms) the huge constant factor that it is multiplied by.
The reason Qucksort generally beats Mergesort's butt is that its
average case O(n log n) is a heck of a lot smaller than mergesort's
average case O(n log n). Until the input gets large, its worst case is
often better than mergesort's best case.

Re: list strawman

[Jean-Marc Bourguet]

dennison@telepath.com (Ted Dennison) writes:

> Jean-Marc Bourguet <jm@bourguet.org> wrote in message news:<3c3bfabc$0$3190$626a54ce@news.free.fr>...
> > Ted Dennison<dennison@telepath.com> writes:
> > 
> > > That's a good point. It would probably be fairly easy to alternate
> > > which side the pivot is taken from.
> > 
> > This will not change the behaviour in N^2 for a (nearly) sorted input.
> 
> After thinking about it harder, you are right. Everything will allways
> go on one side of the pivot, no matter which side you take it from. So
> no "dividing" will actually happen, which is where this
> divide-and-conquer algorithm gets its speed from.
> 
> > > I believe the splitting part of mergesort would involve a linear
> > > search for a linked-list. That would take us into O(n*2) territory,
> > > if not worse. In my student days I could figure out the exact
> > > factor...hmmm...perhaps its just another nlogn...
> > 
> > Merge sort can be implemented in O(N log N) worst case, with a O(N)
> > for an already sorted input.
> 
> OK. By arguing through repeated assertion, you are forcing to either
> ignore you, or do the work of proof myself. Since I made the first
> claim, its only fair that I do the work I guess...

I think the proof is in The Art Of Computer Programming (Knuth, volume
three).

> ...OK it looks like the work involved in doing *all* the splits using
> linear searches is (n/2 + 2(n/4) + 4(n/8) ....) where n>1. Since there
> is one of these factors for each "level", and there are logn levels,
> that should work out to roughly (n/2)logn, or O(n logn). So you are
> right that it is O(N log N) worst case. However, you are wrong about
> the best case. With a linked-list, that is *also* O(N log N).

Not tested, not even compiled, but it should show the principles.  I
think it is in the section "external sorting" of Knuth.  I think the
sort is stable which is an added bonus (but this should be verified).

type Node;   
type Node_Ptr is access Node;
type Node is record
   Next: Node_Ptr;
   Value: Value_Type;
end record;

procedure Sort (Head : in out Node_Ptr) is

   procedure Append(N : Node_Ptr; 
                    Last, Other: in out Node_Ptr;
                    L1, L2: out Node_Ptr) is
   begin
      if Last = null then
         Last := N;
         L1   := N;
      else if Last.Value <= N.Value then
         Last.Next := N;
         Last := N;
      else if Other = null then
         Other := Last;
         Last  := N;
         L2    := N;
      else
         declare
           Tmp : Node_Ptr := Last;
         begin
           Last := Other;
           Other := Tmp;
           Last.Next := N;
           Last := N;
         end;
      end if;
   end Append;

   procedure Split(Head: Node_Ptr; L1, L2: out Node_Ptr) is
      Current : Node_Ptr := Head;
      Last    : Node_Ptr := Null;
      Other   : Node_Ptr := Null;
   begin -- Split
      L1 := null
      L2 := null;
      while Current /= null loop
         declare
            Next : Node_Ptr := Current.Next;
         begin
            Append(Current, Last, Other, L1, L2);
            Current := Next;
         end;
      end loop;
      Last.Next := null;
      if Other /= null then
         Other.Next := null
      end if;            
   end Split;

   procedure Merge(L1, L2: in out Node_Ptr) is
      Current1 : Node_Ptr := L1;
      Current2 : Node_Ptr := L2;
      Last    : Node_Ptr := null;
      Other   : Node_Ptr := Null;
      Tmp     : Node_Ptr := Null;
   begin -- Merge
      L1 := null;
      L2 := null;
      while Current1 /= null and Current2 /= null loop
         if Current1.Value <= Current2.Value then
            declare
               Next : Node_Ptr := Current1.Next;
            begin
               Append(Current1, Last, Other, L1, L2);
               Current1 := Next;
            end;
         else
            declare
               Next : Node_Ptr := Current2.Next;
            begin
               Append(Current2, Last, Other, L1, L2);
               Current2 := Next;
            end;
         end if;
      end loop;
      if Current1 /= null then
         Tmp := Current1;
      else
         Tmp := Current2;
      end if;
      while Tmp /= null loop
         declare
            Next : Node_Ptr := Tmp.Next;
         begin
            Append(Tmp, Last, Other, L1, L2);
            Tmp := Next;
         end;
      end loop;
      Last.Next := null;
      if Other /= null then
         Other.Next := null
      end if;                     
   end Merge;

begin -- Sort
   if Head = Null then
      return;
   end if;
   Split(Head, L1, L2);
   while L2 /= Null loop
      Merge(L1, L2);
   end loop;
   Head = L1;
end Sort;

Each split and Merge phase are O(n).  If the list is sorted, only
Split is done.  Merge reduce the number of chunks by a factor 2 and
there is at most N chunks (if the list is in the reverse order), so
worse case is O(N log N).

-- 
Jean-Marc

Re: list strawman

[Ted Dennison]

Jean-Marc Bourguet wrote:

> dennison@telepath.com (Ted Dennison) writes:
> 
> 
>>...OK it looks like the work involved in doing *all* the splits using
>>linear searches is (n/2 + 2(n/4) + 4(n/8) ....) where n>1. Since there
>>is one of these factors for each "level", and there are logn levels,
>>that should work out to roughly (n/2)logn, or O(n logn). So you are
>>right that it is O(N log N) worst case. However, you are wrong about
>>the best case. With a linked-list, that is *also* O(N log N).


>    procedure Split(Head: Node_Ptr; L1, L2: out Node_Ptr) is
>       Current : Node_Ptr := Head;
>       Last    : Node_Ptr := Null;
>       Other   : Node_Ptr := Null;
>    begin -- Split
>       L1 := null
>       L2 := null;
>       while Current /= null loop
>          declare
>             Next : Node_Ptr := Current.Next;
>          begin
>             Append(Current, Last, Other, L1, L2);
>             Current := Next;
>          end;
>       end loop;
>       Last.Next := null;
>       if Other /= null then
>          Other.Next := null
>       end if;            
>    end Split;
> Each split and Merge phase are O(n).  If the list is sorted, only


That's right, each call to those routines is O(n). However, for a 
mergesort you don't do just one split or merge. At the top level you do 
1, and the next level you do 2, at the next 4, and so on.

It doesn't look like the algorithm you presented does this, but then it 
doesn't look like a sort either. It only calls split once, and then 
merge. Its actually a O(n) algorithm. Too bad it doesn't actually sort, 
or you'd be up for some kind of prize. :-)

Now lets assume it *did* sort, by having split call itself recursively 
after the split if there are multiple elements, then perform a merge 
when its done. The way this modified Split algorithm works, you 
essentially do one full linear search through every list element at 
every recusion level that the list has. Since you divide the list in 
half at each level, there are log N division levels. Thus this algorithm 
you presented is O(n log n), best, worst and average case, just like I 
was saying. The algorithm I assumed for my previous mergesort split 
calculations was a bit quicker, in that I only searched through *half* 
the list at each level, but the time behavior is the same.

Re: list strawman

[Jeffrey Carter]

[in response to discussion of time complexity of merge sort]

A working, tested implementation of merge sort for a linked list is in
PragmARC.List_Unbounded_Unprotected. Like all merge sorts, it is O(N log
N) in time for all inputs.

The PragmAda Reusable Components are available from www.adapower.com.

-- 
Jeffrey Carter

Re: list strawman

[Jean-Marc Bourguet]

Ted Dennison <dennison@telepath.com> writes:

[...]

> That's right, each call to those routines is O(n). However, for a mergesort
> you don't do just one split or merge. At the top level you do 1, and the
> next level you do 2, at the next 4, and so on.
> 
> It doesn't look like the algorithm you presented does this, but then it
> doesn't look like a sort either. It only calls split once, and then
> merge. Its actually a O(n) algorithm. Too bad it doesn't actually sort, or
> you'd be up for some kind of prize. :-)

A merge sort can be splitting once into several sorted lists and then
merging them.  That's what I did.

What I presented is algorithm L in section 5.2.4 of The Art Of
Computer Programming (in the third volume) modified according exercise
12 of the same section.  All the ideas are also presented in the
section 5.4 of the same book. I don't think I'll get a prize for
reading Knuth and his solutions to his exercises :-)

There is a sligth difference with was is presented in Knuth. He use an
additionnal flag in the record to mark the end of the sublists.  I
didn't do that and used the fact that a sublist end when there is a
drop in value.  This has a consequence that sublists may be merged
inexpectedly and so some care must be taken not to go in O(N^2).

More precisely, what I wrote was supposed to be that. Reading Knuth
anew I see one bug which modify the number of operations needed to be
O(N^2) on average.

> Now lets assume it *did* sort, 

It do sort, try it.

Appended is a fixed version with a test harness.

Yours,

-- Jean-Marc

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Command_Line; use Ada.Command_Line;
with Ada.Numerics.Discrete_Random;
with Ada.Unchecked_Deallocation;

procedure Test_Sort is

   ---------------------------------------------------------------------------
   -- Data definition

   type Node;
   type Node_Ptr is access Node;
   type Node is record
      Next: Node_Ptr;
      Value: Positive;
   end record;

   function Ordered (A, B : Positive) return Boolean;

   ---------------------------------------------------------------------------
   -- Natural List Merge Sort
   -- See D.E. Knuth, The Art Of Computer Programming, Volume 3, Second Edition
   -- Algorithm L section 5.2.4 modified according exercise 12 in the same
   -- section, modified to mark the end of the sorted chunks by a drop in value
   -- instead of an additionnal flag.

   procedure Sort (Head : in out Node_Ptr);
   -- Sort the linked list Head.

   procedure Sort (Head : in out Node_Ptr) is

      procedure Split (Head : Node_Ptr; L1, L2 : out Node_Ptr);
      -- Split the sorted chunks of the list Head into L1 and L2

      procedure Merge(L1, L2 : in out Node_Ptr);
      -- Merge the sorted chunks of the list L1 and L2.  If the result has
      -- several chunks, they are splitted between L1 and L2; if the result
      -- has only one chunk, it is in L1

      procedure Split (Head : Node_Ptr; L1, L2 : out Node_Ptr) is
         Last    : Node_Ptr := Head;
         Current : Node_Ptr := Last.Next;
         Other   : Node_Ptr := null;
      begin -- Split
         L1 := Head;
         L2 := null;
         while Current /= null loop
            pragma Assert (Current = Last.Next);
            if not Ordered (Last.Value, Current.Value) then
               -- change the destination list
	       if Other = null then
		  L2 := Current;
	       else
		  Other.Next := Current;
	       end if;
	       Other := Last;
	    end if;
            Last    := Current;
            Current := Last.Next;
         end loop;
         pragma Assert (Last.Next = null);
         if Other /= null then
            Other.Next := null;
         end if;
      end Split;

      procedure Merge(L1, L2 : in out Node_Ptr) is

         procedure Append (C1, C2, Last, Other : in out Node_Ptr);
         -- Append the head of C1 to Last (removing it from C1).  If it is
         -- the last element of its chunks, the rest of the current chunk
         -- in C2 is also appended (removing it from C2) and Last and Other
         -- are swapped.

         procedure Append (C1, C2, Last, Other : in out Node_Ptr) is
         begin -- Append
            if Last = null then
               -- start the list
               if L1 = null then
                  L1 := C1;
               else
                  L2 := C1;
               end if;
            else
               -- Do the append
               Last.Next := C1;
            end if;
            -- Consume
            Last := C1;
            C1 := C1.Next;
            if C1 = null or else not Ordered (Last.Value, C1.Value) then
               -- end of chunk reached, append the rest of the peer chunk
               -- this is the missing part in my previous post, step L5/L7
               -- in Knuth
               loop
                  Last.Next := C2;
                  Last := C2;
                  C2 := C2.Next;
                  exit when C2 = null
                       or else not Ordered (Last.Value, C2.Value);
               end loop;
               -- end of missing part
               -- change the destination list
	       declare
		  Tmp : Node_Ptr := Last;
	       begin
		  Last  := Other;
		  Other := Tmp;
	       end;
            end if;
         end Append;

         Current1 : Node_Ptr := L1;
         Current2 : Node_Ptr := L2;
         Last     : Node_Ptr := null;
         Other    : Node_Ptr := null;
         Tmp      : Node_Ptr := null;

      begin -- Merge
         L1 := null;
         L2 := null;
         pragma Assert (Current1 /= null and Current2 /= null);
         while Current1 /= null and Current2 /= null loop
            if Ordered (Current1.Value, Current2.Value) then
               Append (Current1, Current2, Last, Other);
            else
               Append (Current2, Current1, Last, Other);
            end if;
         end loop;
         pragma Assert (L1 /= null and Other /= null);
         if Current1 /= null then
            Tmp := Current1;
         else
            Tmp := Current2;
         end if;
         if Tmp /= null then
            if Last = null then
               L2   := Tmp;
               Last := Tmp;
               Tmp  := Last.Next;
            else
               pragma Assert (L2 /= null);
               -- set up the loop invariant
               Last.Next := Tmp;
            end if;
	    -- Needed while it is not needed in Knuth because we detect end
	    -- of chunks by drop of value and so may merge some chunks
	    -- inexpectitly.  Ensure here that the number of chunks is more
	    -- or less balanced between L1 and L2.  Doing it more precisely
	    -- is not worthwhile in number of comparisons. This is very
	    -- similar to Split and in fact by changing precondition, Merge
	    -- and Split could be merged or Split called here.
            while Tmp /= null loop
               pragma Assert (Last.Next = Tmp);
               if not Ordered (Last.Value, Tmp.Value) then
                  -- change destination list
                  Other.Next := Tmp;
                  Other := Last;
               end if;
               Last := Tmp;
               Tmp  := Last.Next;
            end loop;
         else
            if Last /= null then
               Last.Next := null;
            end if;
         end if;
         if Other /= null then
            Other.Next := null;
         end if;
      end Merge;

      Aux : Node_Ptr := null;

   begin -- Sort
      if Head = null then
         return;
      end if;
      Split (Head, Head, Aux);
      while Aux /= null loop
         Merge (Head, Aux);
      end loop;
   end Sort;

   ---------------------------------------------------------------------------
   -- Test bench

   procedure Free is
      new Ada.Unchecked_Deallocation(Node, Node_Ptr);

   package Random_Positives is
      new Ada.Numerics.Discrete_Random(Positive);

   Comparison_Count : Long_Integer;

   function Ordered (A, B : Positive) return Boolean is
   begin
      Comparison_Count := Comparison_Count + 1;
      return A <= B;
   end Ordered;

   Generator : Random_Positives.Generator;

   Failed_Test_Count : Natural := 0;

   procedure Check (N : Positive; Sum : in out Long_Integer) is

      function Allocate_List (N : Positive) return Node_Ptr is
         Result : Node_Ptr;
         Last   : Node_Ptr;
         State  : Random_Positives.State;
      begin
         Random_Positives.Save (Generator, State);
         Put ("Sorting " & Positive'Image(N)
              &" numbers (seed="&Random_Positives.Image(State)&")... ");
         Flush;
         Result := new Node'(null, Random_Positives.Random(Generator));
         Last := Result;
         for I in 2 .. N loop
            Last.Next := new Node'(null, Random_Positives.Random(Generator));
            Last := Last.Next;
         end loop;
         return Result;
      end Allocate_List;

      procedure Check_And_Free_List (N : Positive; Head : Node_Ptr) is
         Current : Node_Ptr := Head;
         Next : Node_Ptr := Head;
         Count : Positive := 1;
      begin
         while Current.Next /= null loop
            Count := Count + 1;
            Next := Current.Next;
            if not (Current.Value <= Next.Value) or Count > N then
               Put_Line (" ERROR");
               Failed_Test_Count := Failed_Test_Count + 1;
               return;
            end if;
            Free (Current);
            Current := Next;
         end loop;
         Free (Current);
         if Count = N then
            Put_Line (" OK");
         else
            Put_Line (" ERROR");
            Failed_Test_Count := Failed_Test_Count + 1;
         end if;
      end Check_And_Free_List;

      Head : Node_Ptr := Allocate_List (N);

   begin
      Comparison_Count := 0;
      Sort (Head);
      Sum := Sum + Long_Integer(Comparison_Count);
      Put (Long_Integer'Image(Comparison_Count) & " cmp ");
      Flush;
      Check_And_Free_List (N, Head);
   end Check;

   Number_Of_Tests : Integer := 10;

   procedure Summary (N : Positive; Count : Long_Integer) is
   begin
      Put_Line ("Sorting " & Positive'Image(N) & " elements took "
                & Long_Integer'Image(Count) & " comparisons, "
                & Float'Image(Float(Count)/Float(Number_Of_Tests)/Float(N))
                & " per element per run");
   end Summary;

   Accu10,
   Accu100,
   Accu1000,
   Accu10000,
   Accu100000,
   Accu1000000 : Long_Integer := 0;

   Reset_Generator : Boolean := False;

begin -- Test_Sort
   if Argument_Count > 2 then
      Put_Line ("test_sort [number_of_run [reset_generator]]");
      return;
   end if;
   if Argument_Count > 0 then
      begin
         Number_Of_Tests := Integer'Value(Argument(1));
      exception
         when Constraint_Error =>
            Put_Line (Argument(1)&" is not a number");
            return;
      end;
   end if;
   if Argument_Count > 1 then
      begin
         Reset_Generator := Boolean'Value(Argument(2));
      exception
         when Constraint_Error =>
            Put_Line (Argument(1)&" is not a boolean");
            return;
      end;
   end if;
   if Reset_Generator then
      Random_Positives.Reset(Generator);
   end if;
   for I in 1 .. Number_Of_Tests loop
      Put_Line ("Run" & Integer'Image(I));
      Check (10, Accu10);
      Check (100, Accu100);
      Check (1000, Accu1000);
      Check (10000, Accu10000);
      Check (100000, Accu100000);
      Check (1000000, Accu1000000);
   end loop;
   Put_Line ("For " & Positive'Image(Number_Of_Tests) & " runs");
   Put_Line (Natural'Image(Failed_Test_Count)&" errors");
   Summary (10, Accu10);
   Summary (100, Accu100);
   Summary (1000, Accu1000);
   Summary (10000, Accu10000);
   Summary (100000, Accu100000);
   Summary (1000000, Accu1000000);
end Test_Sort;

Re: list strawman

[Jean-Marc Bourguet]

Jean-Marc Bourguet <jm@bourguet.org> writes:

> There is a sligth difference with was is presented in Knuth. He use an
> additionnal flag in the record to mark the end of the sublists.  I
> didn't do that and used the fact that a sublist end when there is a
> drop in value.  This has a consequence that sublists may be merged
> inexpectedly and so some care must be taken not to go in O(N^2).

Here is a variant.  Instead of detecting chunks by a drop in value, I
mark the end of chunk with Null and keep the already constructed chunks
in an array.  To keep their number low, I merge them as they are
constructed.

Pure algorithm L is having

procedure Extract_Next_Chunk (Head  : in out Node_Ptr;
			      Chunk :    out Node_Ptr;
		              Slot  :    out Table_Index) is
   Slot := 1;
   Chunk := Head;
   Head := Chunk.Next;
   Chunk.Next := null;
end Extract_Next_Chunk;

instead of what is below.

-- 
Jean-Marc

   ---------------------------------------------------------------------------
   -- Natural List Merge Sort
   -- See D.E. Knuth, The Art Of Computer Programming, Volume 3, Second Edition
   -- Algorithm L section 5.2.4 modified according exercise 12 in the same
   -- section, modified to merge chunks as they are constructed instead of keeping
   -- them.  Already constructed chunks are kept in an array.  They are at most
   -- log_2(N).  Big existing chunk are put at their place in the array, this help
   -- in the presence of nearly sorted input.

   procedure Sort (Head : in out Node_Ptr);
   -- Sort the linked list Head.

   procedure Sort (Head : in out Node_Ptr) is
      
      type Table_Index is range 1 .. 64;

      procedure Extract_Next_Chunk (Head  : in out Node_Ptr;
				    Chunk :    out Node_Ptr;
				    Slot  :    out Table_Index) is
         Last    : Node_Ptr := Head;
         Current : Node_Ptr := Last.Next;
	 Size    : Integer := 1;
	 Next    : Integer := 2;
      begin -- Extract_Next_Chunk
         Chunk := Head;
	 Slot  := 1;
         while Current /= null loop
            pragma Assert (Current = Last.Next);
            if not Ordered (Last.Value, Current.Value) then
	       Last.Next := null;
	       Head := Current;
	       return;
	    end if;
            Last    := Current;
            Current := Last.Next;
	    Size := Size + 1;
	    if Size = Next then
	       Next := 2*Next;
	       Slot := Slot + 1;
	    end if;
         end loop;
	 Head := null;
         pragma Assert (Last.Next = null);
      end Extract_Next_Chunk;
      
      function Merge (L1, L2 : Node_Ptr) return Node_Ptr is
	 Current1 : Node_Ptr := L1;
	 Current2 : Node_Ptr := L2;
	 Last : Node_Ptr := null;
	 Result : Node_Ptr := null;
      begin
	 while Current1 /= null and Current2 /= null loop
	    if Ordered (Current1.Value, Current2.Value) then
	       if Last /= null then
		  Last.Next := Current1;
	       else
		  Result := Current1;
	       end if;
	       Last := Current1;
	       Current1 := Current1.Next;
	    else
	       if Last /= null then
		  Last.Next := Current2;
	       else
		  Result := Current2;
	       end if;
	       Last := Current2;
	       Current2 := Current2.Next;
	    end if;
	 end loop;
	 if Current1 /= null then
	    if Last /= null then
	       Last.Next := Current1;
	    else
	       Result := Current1;
	    end if;
	 elsif Current2 /= null then
	    if Last /= null then
	       Last.Next := Current2;
	    else
	       Result := Current2;
	    end if;
	 end if;
	 return Result;
      end Merge;
      
      type Node_Ptr_Table is array(Table_Index) of Node_Ptr;

      Chunk_Table : Node_Ptr_Table := (others => null);
      -- list pointed by chunk_table(i) as at least 2^(i-1) elements
      
      procedure Merge_With_Other_Chunks (Chunk : Node_Ptr; Slot : Table_Index) is
	 Current : Node_Ptr := Chunk;
	 I : Table_Index := Slot;
      begin -- Merge_With_Other_Chunks
	 while Chunk_Table(I) /= null loop
	    Current := Merge (Current, Chunk_Table(I));
	    Chunk_Table(I) := null;
	    I := I+1;
	 end loop;
	 Chunk_Table(I) := Current;
      end Merge_With_Other_Chunks;
      
      Aux : Node_Ptr;
      Slot : Table_Index;
      
   begin -- Sort
      if Head = null then
         return;
      end if;
      while Head /= null loop
	 Extract_Next_Chunk (Head, Aux, Slot);
	 Merge_With_Other_Chunks (Aux, Slot);
      end loop;
      for I in Table_Index loop
	 Head := Merge (Head, Chunk_Table(I));
      end loop;
   end Sort;

Re: list strawman

[Ted Dennison]

Jean-Marc Bourguet <jm@bourguet.org> wrote in message news:<7uir1a.s11.ln@192.168.0.2>...
> What I presented is algorithm L in section 5.2.4 of The Art Of
> Computer Programming (in the third volume) modified according exercise
> 12 of the same section.  All the ideas are also presented in the
> section 5.4 of the same book. I don't think I'll get a prize for
> reading Knuth and his solutions to his exercises :-)

You probably should. Not enough people do that. :-)

I wish I had a copy myself. Its been on my Xmas book list for 3 years
running, but no-one seems to want to buy me a $50 book on algorithms
(much less a set of 3 of them). :-(

> More precisely, what I wrote was supposed to be that. Reading Knuth
> anew I see one bug which modify the number of operations needed to be
> O(N^2) on average.
...
> Appended is a fixed version with a test harness.

I'm still not convinced that you have a mergesort solution here that
is O(n) for sorted lists, as was advertised. I'll have to study it
pretty hard to be sure though (and I'm not sure I care to do that, as
I already have a working implementation of Quicksort going). It
doesn't really look like a mergesort implementation the way I'm used
to thinking of them, as there is no recursion, and only one call to
Split. Split also seems to be doing some sorting work.

Re: list strawman

[Jean-Marc Bourguet]

dennison@telepath.com (Ted Dennison) writes:

> Jean-Marc Bourguet <jm@bourguet.org> wrote in message
> news:<7uir1a.s11.ln@192.168.0.2>...
> > What I presented is algorithm L in section 5.2.4 of The Art Of
> > Computer Programming (in the third volume) modified according
> > exercise 12 of the same section.  All the ideas are also presented
> > in the section 5.4 of the same book. I don't think I'll get a
> > prize for reading Knuth and his solutions to his exercises :-)
> 
> You probably should. Not enough people do that. :-)
> 
> I wish I had a copy myself. Its been on my Xmas book list for 3
> years running, but no-one seems to want to buy me a $50 book on
> algorithms (much less a set of 3 of them). :-(

I did the same,... and ended by bying them myself :-)
 
> > More precisely, what I wrote was supposed to be that. Reading
> > Knuth anew I see one bug which modify the number of operations
> > needed to be O(N^2) on average.
> ...
> > Appended is a fixed version with a test harness.
> 
> I'm still not convinced that you have a mergesort solution here that
> is O(n) for sorted lists, as was advertised.

For sorted list, Merge is never run.  And Split is O(n).

-- 
Jean-Marc

RE: list strawman

[Steven Deller]

Jean-Marc,

Sorry I did not see your second post before sending my previous reply.

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of 
> Jean-Marc Bourguet
> Sent: Tuesday, January 08, 2002 12:22 PM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: list strawman
> Yes.  There is still the problem of choosing the pivot.  With 
> random access, I'd use a random element.  Without random 
> access, you'll have to choose the first or the last element 
> and then degenerate in N^2 for a sorted input, not something 
> I'd like in a general purpose library. Well taking a random 
> element is possible but at a cost of iterating some more time 
> on the whole list.  Perhaps there is a way to even choose the 
> next pivot while you construct the upper and lower list but I 
> don't see one.

Actually, the O(N**2) for a sorted list worried me too, but I think I
have a reasonable way to choose a "median" element after the first scan
with minimal additional computations.  I'll work it through before
suggesting it.

Regards,
Steve Deller

RE: list strawman

[Steven Deller]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of 
> Jean-Marc Bourguet
> Sent: Tuesday, January 08, 2002 10:44 AM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: list strawman
> How do you do quicksort on a list?  quicksort assume random 
> access so you'll have O(n) space overhead. I'd use a merge 
> sort on a list which would have the same complexity as 
> quicksort and do not need random access.

Quick sort does not assume (or require) random access. As long as I can
split, splice, extract elements and add elements I can do quicksort.
(The nice online description and animation of quicksort that Ted D
supplied makes this obvious:
    http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html 

Interestingly, using lists makes it possible to ensure that the
Quicksort is also stable -- the O(n) space required for making an
O(NlnN) sort into a stable sort is already inherent in the list
structure.

A Heapsort *does* require "indexed" access (which I presume is what you
mean by "random"), so it would not be a good candidate for list sorting.

Back in 1986 I wrote a sorting package for Rational (nee Verdix) that
provided several sorts and mentioned why others were not supplied.  Here
are some of the comments from that package, including a reference to a
nice "Taxomomy of Sorting" from 1985.  (I would note that the heapsort I
wrote is a slightly more efficient algorithm than described in Knuth,
uses Ada attributes to work with any array indices including enumeration
types, and encapsulates in Ada quite well -- there is a single routine
called "Almost_Heap_To_Heap" that is used both during the initialization
phase and the sorting phase, making the code quite succinct and easy to
understand.)

-- Provides several sorting algorithms and a permuting algorithm, which
are
-- generic with respect to
--   1. Element type in a List to be sorted, an arbitrary type.
--   2. Index type for indexing into the List, a discrete type.
--      A type List is defined from the Element type and the Index type.
--   3. A relation (Boolean result function) between Elements of the
List.
--      For an ascending sort, the relation should be True whenever the
--      first Element is strictly less than the second Element.  For a
--      descending sort, the relation should be True whenever the first
--      Element is strictly greater than the second Element.
-- Only "in-place" algorithms are provided, i.e. algorithms whose space
-- requirement is N or ( N + log_2(N)*e ), where e is some small value.
The
-- log_2(N)*e additional space is taken from the stack.
--
-- The following sorting algorithms are provided, and an indication is
given
-- about when the algorithm should be chosen:
-- 1. Quicksort (median-of-three): least average sort time of all, but
--    there are data organizations for which sorting time is O(N**2).
the
--    median-of-three approach is used for the split partition value, so
that
--    sorted data is NOT a worst case data organization (unlike the
basic
--    quicksort algorithm).
-- 2. Heapsort: guaranteed O(NlnN) time.  Note that the "heap" in this
--    algorithm applies to the type of data structure applied to the
--    list to be sorted; there is NO allocation of space from the heap.
-- 3. Insertion sort: one of the simplest sorts.  It is O(N**2) in time
--    complexity, but has the one advantage that it is stable, i.e.
elements
--    with equal values retain their order in the list.
--
-- The following sorting algorithms are NOT provided.  An indication of
-- why the algorithms are not provided is given.
-- 1. Shellsort (diminishing increments): This algorithm is consistently
--    bettered by Heapsort, and usually bettered by Quicksort.  Either
of
--    those should be used instead.
-- 2. Listmerge sort: This algorithm requires a special list that has a
--    link field in each element that can hold an index value.  Its
major
--    advantage is that it is a stable sort in O(NlnN) in time, i.e. it
--    makes a reasonable time-space tradeoff to achieve a stable sort.
--    However, its space requirements violate the "general element",
--    "in-place" sort requirements defined for this package.  A
reasonable
--    alternative to providing a stable sort in (NlnN) time is to add
--    a single field to each initial element, initialized to the value
--    of the element's position in the array, and make the "<" function
--    include a compare of this field if the original compared fields
--    are equal.  Thus equal elements are forced non-equal, and the
order
--    of equal elements in the array is maintained.
-- 3. Bubblesort.  This algorithm takes O(N**2) time, and has a higher
--    constant factor than insertion sort.
-- 4. Selectionsort.  This algorithm takes O(N**2), and is not stable
--    when done in-place with exchanges, unless considerable
complications
--    are added to the algorithm.
--
-- It is helpful to organize the sorting algorithms to aid
understanding.
-- The following taxonomy is based on the article:
--   An Inverted Taxonomy of Sorting Algorithms, Susan M. Merritt,
--   Communications of the ACM, Vol. 28, No. 1, January 1985, pp. 96-99.
--
-- All sorting algorithms are based on the abstraction "split into
parts,
-- sort the parts, join the sorted parts".  Specific sorting algorithms
are
-- conveniently classified as hard-split/easy-join or
easy-split/hard-join,
-- based on whether the "work" is done at the start or end of the
algorithm.
-- The abstract algorithm is clearly recursive.  Usual programming style
-- converts the recursions to iterations for speed.
--
-- If we independently specify the splitting criteria then we get the
-- following table:
--
--   Splitting criteria        hard-split/easy-join
easy-split/hard-join
--   ------------------        --------------------
--------------------
--   Equal-sized parts         Quicksort                 Merge Sort
--   One part is one element   Selection Sort            Insertion Sort
--   One element, in place     Bubble Sort               Sinking Sort
--
-- The Heapsort algorithm is viewed as a Selection Sort that minimizes
-- the comparisons to find the next element by using a data structure
-- (a heap).  The Shell Sort algorithm is viewed as a version of the
-- Insertion Sort that operates independently on various subsets of the
-- input data. An additional class of algorithms* may be viewed as
-- splitting criteria that are varying combinations of Quicksort with
-- Bubble Sort.  (Perhaps the combination of Merge Sort and Sinking Sort
-- would give rise to a similar set of algorithms.)
--
-- * A Class of Sorting Algorithms Based on Quicksort, Roger L.
Wainwright,
--   Communications of the ACM, Vol. 28, No. 4, April 1985, pp. 396-403.

Regards,
Steve 

RE: RE: list strawman

[Steven Deller]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Ted Dennison
> Sent: Tuesday, January 08, 2002 10:32 AM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: RE: list strawman
> 
> Since we have a "Splice", I can't really sit here and argue 
> that its inverse function has no business being there. But 
> I'd like to hear a few concurrances that it needs to be in 
> there before changing things.

Ted,
Actually, a "split" is not necessary if there is a way to compare two
iterators to see if they are pointing to the same item -- in that case,
the left and right partitions can simply be the list portions before,
and after a given iterator.

Of course that means the algorithm will need O(lnN) iterators, which is
another difficulty in the current interface.  I'm not sure why there
needs to be a limit on the number of iterators.  For any operation that
has to check consistency across all iterators, just traverse a "list" of
the iterators (such a list being a locally defined and used list).

>From my "usability" view, the interface now has 3 flaws:
  1. No "split" list into two lists
  2. No "compare iterators" (at least not that I recall)
  3. Limited number of iterators

Regards,
Steve

Re: RE: RE: list strawman

[Ted Dennison]

In article <mailman.1010519822.5637.comp.lang.ada@ada.eu.org>, Steven Deller
says...
>
>Actually, a "split" is not necessary if there is a way to compare two
>iterators to see if they are pointing to the same item -- in that case,
>the left and right partitions can simply be the list portions before,
>and after a given iterator.

This isn't explicit from the current strawman I'm afraid, so it bears publicly
stating:

The current implementation implies that "=" is available for both lists and
iterators (they are not limited types). Given this, we can either take steps to
make "=" no loger available (which was not done), or we can make it do sensible
things.

"Sensible things" to me would imply that for lists, it returns True if they have
the same number of elements, and each element in one list returns True for "="
with the element in the same position in the other list. For an iterator, it
implies that both iterators refer to the same element in the same position on
the same list.

Therefore, unless there is general disagreement with the above, "=" on iterators
should fit your requirement.


>Of course that means the algorithm will need O(lnN) iterators, which is
>another difficulty in the current interface.  I'm not sure why there
>needs to be a limit on the number of iterators.  For any operation that
>has to check consistency across all iterators, just traverse a "list" of
>the iterators (such a list being a locally defined and used list).

There is no limit on iterators in the current. You can make as many iterators as
you like. The implementation I'm working on doesn't even use dynamic allocation
for them or when working with them, so such an algorithm shouldn't be a big
efficiency problem either. But I'd have no big problem with adding a Split
either.

>From my "usability" view, the interface now has 3 flaws:
>  1. No "split" list into two lists
Again: this can be taken care of, if there is support for it.

>  2. No "compare iterators" (at least not that I recall)
Its there, it just hasn't been very well advertised.

>  3. Limited number of iterators
Nope. Never was such a limit in any of the strawmen. (This was a feature of some
of Nick's examples. Are you perhaps thinking of that?)

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <mailman.1010519822.5637.comp.lang.ada@ada.eu.org>, Steven Deller
> says...
> <snip> 
> >From my "usability" view, the interface now has 3 flaws:
> >  1. No "split" list into two lists
> Again: this can be taken care of, if there is support for it.

I vote for adding 'split'; it nicely compliments 'splice'.

> >  2. No "compare iterators" (at least not that I recall)
> Its there, it just hasn't been very well advertised.

We need to add a explicit visible "=" to make it do what you want; in
my implementation, the default "=" does not.

-- 
-- Stephe

Re: list strawman

[Ted Dennison]

In article <uwuys1qun.fsf@gsfc.nasa.gov>, Stephen Leake says...
>
>Ted Dennison<dennison@telepath.com> writes:
>> Its there, it just hasn't been very well advertised.
>
>We need to add a explicit visible "=" to make it do what you want; in
>my implementation, the default "=" does not.

You don't have to override "=" in the public part of a spec, so I usually don't.
With the strawmen I took the principle that only the public part of the spec was
presented, along with some extra stuff in the private part to get it to compile.
Perhaps in this case I took the principle too far...

I should shoulder the blame for any confusion this "implicit requirement" has
caused, since I left it implicit. But nits aside, it should be clear that "=" is
available, for Lists and Iterators, and thus implementors must make them both do
the sensible thing. Leaving them available but doing useless things is obviously
not good design. I might accept it for a package internal to a project, but
certianly not for something that is supposed to be standard.

Looking back at it now, what I should have done is what was done in the LRM for
the built-in operators in package Standard: put them in the public part
commented out.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Thomas Wolf]

dennison@telepath.com wrote:
> In article <uwuys1qun.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >Ted Dennison<dennison@telepath.com> writes:
> >> Its there, it just hasn't been very well advertised.
> >
> >We need to add a explicit visible "=" to make it do what you want; in
> >my implementation, the default "=" does not.
> 
> You don't have to override "=" in the public part of a spec, so I usually don't.
> With the strawmen I took the principle that only the public part of the spec was
> presented, along with some extra stuff in the private part to get it to compile.
> Perhaps in this case I took the principle too far...
> 
> I should shoulder the blame for any confusion this "implicit requirement" has
> caused, since I left it implicit. But nits aside, it should be clear that "=" is
> available, for Lists and Iterators, and thus implementors must make them both do
> the sensible thing. Leaving them available but doing useless things is obviously
> not good design. I might accept it for a package internal to a project, but
> certianly not for something that is supposed to be standard.

Some comments on that Strawman 1.4 interface:

1. Generic formals
------------------

   generic
      type Element is private;
   package Containers.Lists.Unbounded is

I'd prefer

   generic
      type Element is private;
      with function "=" (Left, Right : Element) return Boolean is <>;
   package Containers.Lists.Unbounded is

This allows users who have unconventional ideas of equality to provide
their own routine, without requiring "normal" users to specify the
equality function explicitly.

2. Element Arrays
-----------------

      type Element_Array is array (Natural range <>) of Element;
      
Why "Natural range <>"? I'd prefer "Positive range <>" similar to the
string packages. Note that you can still return an empty array for an
empty list by returning Element_Array (2 .. 1).

3. Naming issues
----------------

      function To   (Source : Element_Array) return List;
      function From (Source : List) return Element_Array;

I'd call these 'To_List' and 'To_Array', respectively. Maybe provide
these as renamings?

      function Singleton (Initial_Element : Element) return List;

I realize there's already been quite some discussion on that name. I
side with the "don't like" camp; I'd call this 'To_List', too.

4. Removing from a list end
---------------------------

      procedure Remove
        (Target      : in out List;
         Old_Element :    out Element;
         List_End    : in     Direction);

You don't always want to get the old element when you remove an item
from the list. Hence I'd add the following:

      procedure Remove
        (Target   : in out List;
         List_End : in     Direction);

5. Generic iterator
-------------------

      generic
         with procedure Operation (Target : in out Element; 
                                   Quit   :    out Boolean);
      procedure Passive_Iterator (Target : in out List);

Two things: first, 'Quit' must be an "in out"-parameter, and second,
in *my* terminology, this is an *active* iterator. After all, it
iterates on its own, so it's active, whereas the positions provided
by the type 'Iterator' do not move by themselves but have to be
advanced explicitly by the client code. Or did I get my nomenclature
mixed up?

Oh yes, and another thing: the list is an "in out" parameter, probably
to indicate that 'Operation' may change the elements (although the list
structure, i.e. the node chain, remains unchanged). A second variant

      generic
         with procedure Inspect (Target : in     Element; 
                                 Quit   : in out Boolean);
      procedure Read_Only_Iterator (Target : in List);

might be useful, too.

6. Inserting at a given location
--------------------------------

      procedure Insert (New_Item : in Element;
                        Location : in Iterator;
                        Side     : in Direction := Head);
      procedure Insert (New_Items : in List;
                        Location  : in Iterator;
                        Side      : in Direction := Head);

For completeness, the following is missing:

      procedure Insert (New_Items : in Element_Array;
                        Location  : in Iterator;
                        Side      : in Direction := Head);

In the two latter cases, nothing happens if 'New_Items' is empty.

7. Modifying an element at a given location
-------------------------------------------

      procedure Modify (Subject   : in out List; 
                        Location  : in     Iterator;
                        New_Value : in     Element);

Why is the subject list passed along? To be consistent with the
other operations on locations, it should be omitted.

8. Operations requiring a "<" on elements
-----------------------------------------

      generic
         with function Reverse_Order (First, Second : in Element)
                 return Boolean;
         From : in Direction;
      package Sorting is

Why this somewhat unusual (at least in my perception) interface?
Why not simply

      generic
         with function "<" (Left, Right : Element) return Boolean is <>;
      package Ordered is

and define e.g. Sort to sort the list into ascending order according to
the given "<" routine. (Or if you like, replace "<" by ">", it doesn't
matter.)

If you still want the ability to do both ascending and descending sorts
with the same instantiation, change 'Sort' to something like

         procedure Sort (Subject   : in out List;
                         Ascending : in     Boolean := True);

Furthermore, you could also provide lexicographical comparisons in this
nested package.

9. Equality
-----------

Both lists and iterators need meaningful equality operations. For lists,
return True if they both contain equal elements in the same order; for
iterators, return True if they both are null or else both point to the
same list node.

Is there any harm done by putting them explicitly in the public part?
This would make it absolutely clear for anybody that sensible 
implementations have to be provided for these operations. Furthermore,
it'd define a convenient place to put a comment explaining under what
conditions these operators return True.

10. Stream Attributes
---------------------

There's no need at all to make 'Stream_Read' and 'Stream_Write' public.
I'd put them into the private part.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: list strawman

[Ted Dennison]

Thomas Wolf <t_wolf@angelfire.com> wrote in message news:<MPG.16a629ebab6a7b63989682@news.ip-plus.net>...
> Some comments on that Strawman 1.4 interface:
> 2. Element Arrays
> -----------------
> 
>       type Element_Array is array (Natural range <>) of Element;
>       
> Why "Natural range <>"? I'd prefer "Positive range <>" similar to the

This has already been discussed, and it has in fact been changed to
positive. That's one of a couple of changes made since the last
strawman rev.

> 4. Removing from a list end
> ---------------------------
> You don't always want to get the old element when you remove an item
> from the list. Hence I'd add the following:
> 
>       procedure Remove
>         (Target   : in out List;
>          List_End : in     Direction);

We are past the point where we can add routines on a whim. People are
actually implementing it and writing code to work with it now. If a
routine is going to be added or changed at this point, it will be only
be for a very good reason (eg: A bug, or a very serious implementation
or usability problem).

> Two things: first, 'Quit' must be an "in out"-parameter, and second,

That's another thing that has already been discussed and changed.

> 7. Modifying an element at a given location
> -------------------------------------------
> 
>       procedure Modify (Subject   : in out List; 
>                         Location  : in     Iterator;
>                         New_Value : in     Element);
> 
> Why is the subject list passed along? To be consistent with the
> other operations on locations, it should be omitted.

Good catch there. I think I may have actually implemented this and not
noticed. Consider "Subject" removed.

> 9. Equality
> -----------
> Is there any harm done by putting them explicitly in the public part?

One does not put things in the public part of a package that do not
need to go there. So the proper question for putting things in the
public part of a package is not "Does it do any harm there?", but
rather, "Does it absolutely have to go there?" Again, I think the
proper model here is package Standard, which put a commented-out
version in the public part.

> 10. Stream Attributes
> ---------------------
> There's no need at all to make 'Stream_Read' and 'Stream_Write' public.
> I'd put them into the private part.

Again, this has already been discussed and done.

For the rest of your points, I have not addressed them because they
have already been debated and a decision has already been reached over
the last 3 months or so. Rather than have us rehash everything that
has been said before just for your benifit, I suggest you go review
the discussions and the rationale for the decisions at Google groups.

Re: list strawman

[Stephen Leake]

dennison@telepath.com (Ted Dennison) writes:

> Thomas Wolf <t_wolf@angelfire.com> wrote in message news:<MPG.16a629ebab6a7b63989682@news.ip-plus.net>...

> > 4. Removing from a list end
> > ---------------------------
> > You don't always want to get the old element when you remove an item
> > from the list. Hence I'd add the following:
> > 
> >       procedure Remove
> >         (Target   : in out List;
> >          List_End : in     Direction);
> 
> We are past the point where we can add routines on a whim. People are
> actually implementing it and writing code to work with it now. If a
> routine is going to be added or changed at this point, it will be only
> be for a very good reason (eg: A bug, or a very serious implementation
> or usability problem).

Well, as a (partial :) implementor, I don't mind this routine; filling
in little corners like this is fine. Adding major functionality is not.

> > 9. Equality
> > -----------
> > Is there any harm done by putting them explicitly in the public part?
> 
> One does not put things in the public part of a package that do not
> need to go there. So the proper question for putting things in the
> public part of a package is not "Does it do any harm there?", but
> rather, "Does it absolutely have to go there?" Again, I think the
> proper model here is package Standard, which put a commented-out
> version in the public part.

It needs to be explicit in either the public or private part of the
standard for this package, so that implementers are forced to provide
it.

If we adopt the rule that "the private part is _not_ specified by this
standard" (which makes sense), it _needs_ to be in the public part. 

Or we can draw a line in the private part and say "everything above
this line is defined by the standard". That would be simple.

-- 
-- Stephe

Re: list strawman

[Ted Dennison]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message news:<uelkz1pxk.fsf@gsfc.nasa.gov>...

> If we adopt the rule that "the private part is _not_ specified by this
> standard" (which makes sense), it _needs_ to be in the public part. 

Again, I'd point to the package Standard in the LRM
(http://www.ada-auth.org/~acats/arm-html/RM-A-1.html ), which adopted
that rule, but didn't seem to have any trouble with specifying that an
implementation for "=" exists as well using comments.

> Or we can draw a line in the private part and say "everything above
> this line is defined by the standard". That would be simple.

That would probably work too. We could get theoreticaly into a
situation where there is no single line, due to freezing issues. But
we don't have such a situation right now, and I can't think of any
good examples that would cause it.

Re: list strawman

[Mark Lundquist]

"Thomas Wolf" <t_wolf@angelfire.com> wrote in message
news:MPG.16a629ebab6a7b63989682@news.ip-plus.net...
> Some comments on that Strawman 1.4 interface:
>
> 1. Generic formals
> ------------------
>
>    generic
>       type Element is private;
>    package Containers.Lists.Unbounded is
>
> I'd prefer
>
>    generic
>       type Element is private;
>       with function "=" (Left, Right : Element) return Boolean is <>;
>    package Containers.Lists.Unbounded is
>
> This allows users who have unconventional ideas of equality to provide
> their own routine, without requiring "normal" users to specify the
> equality function explicitly.

Indeed it's a bug in Ada95 if the generic uses "=" without importing it
explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
predefined equality "reemerges".

Don't know if that's been fixedin Ted's latest, it may have...

-- mark

Re: list strawman

[Jeffrey Carter]

Mark Lundquist wrote:
> 
> "Thomas Wolf" <t_wolf@angelfire.com> wrote in message
> news:MPG.16a629ebab6a7b63989682@news.ip-plus.net...
> > Some comments on that Strawman 1.4 interface:
> >
> > 1. Generic formals
> > ------------------
> >
> >    generic
> >       type Element is private;
> >    package Containers.Lists.Unbounded is
> >
> > I'd prefer
> >
> >    generic
> >       type Element is private;
> >       with function "=" (Left, Right : Element) return Boolean is <>;
> >    package Containers.Lists.Unbounded is
> >
> > This allows users who have unconventional ideas of equality to provide
> > their own routine, without requiring "normal" users to specify the
> > equality function explicitly.
> 
> Indeed it's a bug in Ada95 if the generic uses "=" without importing it
> explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
> predefined equality "reemerges".
> 
> Don't know if that's been fixedin Ted's latest, it may have...

I realize I've been away for a while and may not have seen some minor
changes to the functionality, but "=" for Elements is not needed to
implement a list. "=" is not used, so there's no need to specify it in
the generic formal part.

What would be better would be some way to specify that the generic uses
assignment but not "=", but Ada does not provide that.

-- 
Jeff Carter
"Death awaits you all, with nasty, big, pointy teeth!"
Monty Python & the Holy Grail

Re: list strawman

[Thomas Wolf]

jrcarter@acm.org wrote:
> I realize I've been away for a while and may not have seen some minor
> changes to the functionality, but "=" for Elements is not needed to
> implement a list. "=" is not used, so there's no need to specify it in
> the generic formal part.

Yes, element equality is need to implement list equality.

And if it really were not used, it should be made explicitly unavailable
to avoid mistakenly using a re-emerging predefined equality all the same
by declaring it as abstract in the private part.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com

Re: list strawman

[Jeffrey Carter]

Thomas Wolf wrote:
> 
> jrcarter@acm.org wrote:
> > I realize I've been away for a while and may not have seen some minor
> > changes to the functionality, but "=" for Elements is not needed to
> > implement a list. "=" is not used, so there's no need to specify it in
> > the generic formal part.
> 
> Yes, element equality is need to implement list equality.

Ah, yes, I forgot that the list type is not limited. Sorry. While I can
live with this, it seems like a mistake to me, since list assignment and
equality comparison are not common operations in my experience, and can
be implemented easily and with no loss of efficiency by the client in
the few cases where they are needed.

-- 
Jeffrey Carter

Re: list strawman

[Chad Robert Meiners]

Has anyone considered using the Radix sort for the lists?  Radix is
O(n) and well suited and straight-forward for sorting lists.

-CRM

Re: list strawman

[Jeffrey Carter]

Chad Robert Meiners wrote:
> 
> Has anyone considered using the Radix sort for the lists?  Radix is
> O(n) and well suited and straight-forward for sorting lists.

Radix sort only applies to a limited class of values, and would not seem
suitable to sorting lists of arbitrary Elements.

-- 
Jeff Carter
"Now go away or I shall taunt you a second time."
Monty Python & the Holy Grail

Re: list strawman

[Chad R. Meiners]

True,  you do need provide a method and a type to key the data, but I
believe that if someone can provide a less than operator they surely can
provide these. (Well if all elements are of finite size)  This should handle
arbitrary Elements.  Of course as the key size grows so does the constant
time modifier, but this is a design time consideration so the designer can
expect stable performance in the field over all data combinations.

-CRM

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3C3FCD5C.25841A6C@acm.org...
> Chad Robert Meiners wrote:
> >
> > Has anyone considered using the Radix sort for the lists?  Radix is
> > O(n) and well suited and straight-forward for sorting lists.
>
> Radix sort only applies to a limited class of values, and would not seem
> suitable to sorting lists of arbitrary Elements.
>
> --
> Jeff Carter
> "Now go away or I shall taunt you a second time."
> Monty Python & the Holy Grail

Re: list strawman

[Jeffrey Carter]

"Chad R. Meiners" wrote:
> 

[concerning using radix sort to sort an arbitrary list]

> True,  you do need provide a method and a type to key the data, but I
> believe that if someone can provide a less than operator they surely can
> provide these. (Well if all elements are of finite size)  This should handle
> arbitrary Elements.  Of course as the key size grows so does the constant
> time modifier, but this is a design time consideration so the designer can
> expect stable performance in the field over all data combinations.

Perhaps I'm missing something, but how can you radix sort

type Element is range System.Min_Int .. System.Max_Int;

into ascending order? I guess I would need to see an actual
implementation of a generic radix sort and how a client would invoke it
for my limited brain to understand what you're getting at.

-- 
Jeff Carter
"Perfidious English mouse-dropping hoarders."
Monty Python & the Holy Grail

Re: list strawman

[Chad R. Meiners]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3C41BDF6.6E797663@acm.org...
>
> Perhaps I'm missing something, but how can you radix sort
>
> type Element is range System.Min_Int .. System.Max_Int;
>
> into ascending order? I guess I would need to see an actual
> implementation of a generic radix sort and how a client would invoke it
> for my limited brain to understand what you're getting at.

Well I don't currently have time to whip up an implementation right now, but
the general method would be to choose the base that you want to sort by
(like base 2 , base 256 or base 2**10 and so on)  then you map the type to
an unsigned integer and take ceiling(log_base (Element'Lenght)) passes to
sort the list.  For the buckets you simply create an array of lists and when
we finish each pass you simply append the array of lists together to prepare
for the next pass.   When I have time, I'll look into implementing the sort
if you would like to see it.

-CRM

Re: list strawman

[Ted Dennison]

Chad R. Meiners wrote:


> Well I don't currently have time to whip up an implementation right now, but
> the general method would be to choose the base that you want to sort by
> (like base 2 , base 256 or base 2**10 and so on)  then you map the type to
> an unsigned integer and take ceiling(log_base (Element'Lenght)) passes to


How's that going to work for long strings or complicated records?

Re: list strawman

[Jeffrey Carter]

"Chad R. Miners" wrote:
> 
> When I have time, I'll look into implementing the sort
> if you would like to see it.

Yes, that would be interesting.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail

Re: list strawman

[Jeffrey Carter]

"Chad R. Meiners" wrote:
> 
> When I have time, I'll look into implementing the sort
> if you would like to see it.

Yes, that would be interesting.

-- 
Jeff Carter
"You empty-headed animal-food-trough wiper."
Monty Python & the Holy Grail

Re: list strawman

[Ted Dennison]

"Mark Lundquist" <no.spam@getalife.com> wrote in message news:<6i%_7.8890$fG.50588@rwcrnsc51.ops.asp.att.net>...
> Indeed it's a bug in Ada95 if the generic uses "=" without importing it
> explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
> predefined equality "reemerges".

I implied in an earlier repsonse that this issue has already been
addressed. Thomas pointed out to me privately that it had not, and
he's quite correct. I was thinking of assignment, which we had already
talked about and decided upon.

The killer for assignement was the large amount of effort required for
no benifit to most people. We have the same issue of little benifit to
most people here, but the effort required isn't nearly the same, as
"=" should already be available as a function for users to supply.
There's also the issue Mark points out of built-in "=" re-emerging,
which seems to be to be a pretty darn good argument.

> Don't know if that's been fixedin Ted's latest, it may have...

Not at this moment.

I'd like to see if anyone has a good objection to it, but I personally
can't see one. The only issue I can see is that it takes your typical
instantiation from:

   package Integer_Lists is new Containers.Lists.Unbounded (Integer);

to 

   package Integer_List is new Containers.Lists.Unbounded (Integer,
"=");

Instructors will have to explain the purpose of the extra parameter,
but I don't think that's too big a deal. I'd like to hear from one of
them though.

Re: list strawman

[Mark Biggar]

Ted Dennison wrote:
 
> I'd like to see if anyone has a good objection to it, but I personally
> can't see one. The only issue I can see is that it takes your typical
> instantiation from:
> 
>    package Integer_Lists is new Containers.Lists.Unbounded (Integer);
> 
> to
> 
>    package Integer_List is new Containers.Lists.Unbounded (Integer,
> "=");
> 
> Instructors will have to explain the purpose of the extra parameter,
> but I don't think that's too big a deal. I'd like to hear from one of
> them though.

use "is <>" for "=" then the user only needs to explicitly specify
it if it isn't named "=".

--
Mark Biggar
mark.a.biggar@attbi.com

Re: list strawman

[Simon Wright]

Mark Biggar <mark.a.biggar@attbi.com> writes:

> use "is <>" for "=" then the user only needs to explicitly specify
> it if it isn't named "=".

I had a case (OA7.2, I can't get 7.2.1 to install properly) where I
had to have 'function Eq' rather than 'function "="' as a generic
formal subprogram, or it got confused.

Re: list strawman

[Matthew Heaney]

"Simon Wright" <simon@pushface.org> wrote in message
news:x7vy9j3oj5t.fsf@smaug.pushface.org...
> Mark Biggar <mark.a.biggar@attbi.com> writes:
>
> > use "is <>" for "=" then the user only needs to explicitly specify
> > it if it isn't named "=".
>
> I had a case (OA7.2, I can't get 7.2.1 to install properly) where I
> had to have 'function Eq' rather than 'function "="' as a generic
> formal subprogram, or it got confused.

Can't you just say:

generic
   type T is private;
   with function Eq (L, R : T) return Boolean is "=";
package GP is

Re: list strawman

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> "Simon Wright" <simon@pushface.org> wrote in message
> news:x7vy9j3oj5t.fsf@smaug.pushface.org...
> > Mark Biggar <mark.a.biggar@attbi.com> writes:
> >
> > > use "is <>" for "=" then the user only needs to explicitly specify
> > > it if it isn't named "=".
> >
> > I had a case (OA7.2, I can't get 7.2.1 to install properly) where I
> > had to have 'function Eq' rather than 'function "="' as a generic
> > formal subprogram, or it got confused.
> 
> Can't you just say:
> 
> generic
>    type T is private;
>    with function Eq (L, R : T) return Boolean is "=";
> package GP is

Neat! will try ..

An alternate workround might be to use a renaming in the package (or
subprogram) body. Usual scrabbling around to find some form that the
compiler concerned will be happy with ..

Overridability of _private_ predefined "=" [was Re: list strawman]

[Vincent Marciante]

Mark Lundquist wrote:
> 
> "Thomas Wolf" <t_wolf@angelfire.com> wrote in message
> news:MPG.16a629ebab6a7b63989682@news.ip-plus.net...
> > Some comments on that Strawman 1.4 interface:
> >
> > 1. Generic formals
> > ------------------
> >
> >    generic
> >       type Element is private;
> >    package Containers.Lists.Unbounded is
> >
> > I'd prefer
> >
> >    generic
> >       type Element is private;
> >       with function "=" (Left, Right : Element) return Boolean is <>;
> >    package Containers.Lists.Unbounded is
> >
> > This allows users who have unconventional ideas of equality to provide
> > their own routine, without requiring "normal" users to specify the
> > equality function explicitly.
> 
> Indeed it's a bug in Ada95 if the generic uses "=" without importing it
> explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
> predefined equality "reemerges".

Its even worse than just that.  Now a "block compare" of any composite
type
that has a nontagged private type as a componant is questional because
that
comparison will utilize the predefined "=" of the private type even
though
the creator of the private type may have seen it proper to overridden
it.

There was a thread, gosh, I guess less than two years ago where I was
trying to
argue that this was a disaster wrt generics and that reemergence of "="
seemed
to be a special case wrt the whole reemergence issue.   I now feel that
the
situation is very bad in general as opposed to being bad only wrt
generics.

Does anyone think that it would be good for there to be a change in the
language such that for private types, if a primative "=" returning
boolean exists then it
should be the "=" used as part of block compares and that the predefined
one
should not reemerge in generics?  This would not have been incompatible
with
Ada83, right?

I hope that the above is not perceved as rehashing old arguments - I do
not
remember the issues having been discussed exactly as above.

Vincent Marciante

Re: Overridability of _private_ predefined "=" [was Re: list strawman]

[Vincent Marciante]

> Christoph Grein wrote:
> Please, before going into further discussions about reemergence of predefined 
> operations and thinking about changing the language, read the corresponding 
> chapters in the AARM (the Annotated Ada Reference Manual), e.g. 
> AARM 4.5.2(24a-c).

I have read that.  
 
> With respect to "block compare",

I'm sorry, I think that I should have said 'usage of predefined "=" 
for composite types that have componants of a private type'.

> this is not possible for tagged types, floating 
> point types if there are signed zeros, and who knows for which other cases.

So, in addition to what Mark Lundquist wrote:

Mark Lundquist wrote:
> 
> >
> >    generic
> >       type Element is private;
> >       with function "=" (Left, Right : Element) return Boolean is <>;
> >    package Containers.Lists.Unbounded is
> >
> > This allows users who have unconventional ideas of equality to provide
> > their own routine, without requiring "normal" users to specify the
> > equality function explicitly.
> 
> Indeed it's a bug in Ada95 if the generic uses "=" without importing it
> explicitly.  Otherwise, an overridden "=" is not visible to the generic, and
> predefined equality "reemerges".

it seems to also be a bug in Ada95 if the generic uses predefined "=" of 
any composite types that have componants whose type is that of an
imported
private type. Right?
 
> Thus it is generally a bad idea to override predefined operators for non-tagged 
> types. If this is really necessary, then utmost care has to be applied 
> everywhere such a type is used (e.g. as components of an array).

This is why I find the situation to be so bad now.  A generic written
for Ada 83 that only imports a private type can not be made into a valid
Ada 95 one by simply transforming its spec by adding the importation of
"=" for that type;  Its body must also be analyzed and possibly changed
so as to use componant by componant comparison for any composite types
having the private type as a componant (or predefined "=" has to be
overridden for those composite types _and_ any other composite types the
have those composite types as componants.)

What was impossible (?) to do wrong in Ada 83 has now become a pitfall
in Ada 95. were by we have to dilligently follow the verbal guideline
that you just suggested. 

> Reemergence has been introduced in the first place to avoid incompatibilities 
> with Ada83.

I have read this but I have not seen the statement of the
incompatibilities that were avoided.  Can someone point me to that
information?

I must really be missing something (and I do want to understand what it
is if I am.)

>
>Christoph Grein
>
> Vincent Marciante wrote:
>> Its even worse than just that.  Now a "block compare" of any composite
>> type
>> that has a nontagged private type as a componant is questional because
>> that
>> comparison will utilize the predefined "=" of the private type even
>> though
>> the creator of the private type may have seen it proper to overridden
>> it.
>> 
>> There was a thread, gosh, I guess less than two years ago where I was
>> trying to
>> argue that this was a disaster wrt generics and that reemergence of "="
>> seemed
>> to be a special case wrt the whole reemergence issue.   I now feel that
>> the
>> situation is very bad in general as opposed to being bad only wrt
>> generics.
>> 
>> Does anyone think that it would be good for there to be a change in the
>> language such that for private types, if a primative "=" returning
>> boolean exists then it
>> should be the "=" used as part of block compares and that the predefined
>> one
>> should not reemerge in generics?  This would not have been incompatible
>> with
>> Ada83, right?
>> 
>> I hope that the above is not perceved as rehashing old arguments - I do
>> not
>> remember the issues having been discussed exactly as above.
>> 
>> Vincent Marciante

Re: Overridability of _private_ predefined "=" [was Re: list strawman]

[Nick Roberts]

"Vincent Marciante" <marciant_remove@li.net> wrote in message
news:3C49A5C4.51D6@li.net...

> ...
> This is why I find the situation to be so bad now.  A generic written
> for Ada 83 that only imports a private type can not be made into a valid
> Ada 95 one by simply transforming its spec by adding the importation of
> "=" for that type;  Its body must also be analyzed and possibly changed
> so as to use componant by componant comparison for any composite types
> having the private type as a componant (or predefined "=" has to be
> overridden for those composite types _and_ any other composite types the
> have those composite types as componants.)
>
> What was impossible (?) to do wrong in Ada 83 has now become a pitfall
> in Ada 95. were by we have to dilligently follow the verbal guideline
> that you just suggested.

AI-123 discusses this in some detail, and results (rev 12) in a corrigendum
which specifically compels language-defined types to be composable with
respect to equality (thus forcing them to be implemented either without
redefined equality or as tagged types). I smell a hint of hypocrisy here.

Personally, I completely agree with Vincent. Damn Ada 83 compatibility, and
damn implementation complexities: equality should always be composable; the
current state is plainly a potential source of 'nasty surprises'; the
language is purportedly supposed to avoid nasty surprises. But I am a small
voice.

--
Best wishes,
Nick Roberts

Re: list strawman

[Ted Dennison]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message news:<uwuys1qun.fsf@gsfc.nasa.gov>...
> I vote for adding 'split'; it nicely compliments 'splice'.

OK. Next question(s): Can "split" be implemented as the inverse to
"splice", where it spilts from the iterator to the end, or does it
need to go from one iterator to another to be useful?

If the latter, should "splice" be changed to work the same way?

Re: list strawman

[Ted Dennison]

dennison@telepath.com (Ted Dennison) wrote in message news:<4519e058.0201081910.51225bf@posting.google.com>...
> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message news:<uwuys1qun.fsf@gsfc.nasa.gov>...
> > I vote for adding 'split'; it nicely compliments 'splice'.
> 
> OK. Next question(s): Can "split" be implemented as the inverse to
> "splice", where it spilts from the iterator to the end, or does it
> need to go from one iterator to another to be useful?
> 
> If the latter, should "splice" be changed to work the same way?

OK. I have bad news on this score. After playing with the code a bit,
I came to realise that, while Splice as it stands can be implemented
in O(C), Split and any iterator-to-iterator splice would both end up
being no better than O(n). The problem is our safe iterators. Since
iterators are associated with their list somehow, you have to go
through every iterator that got moved and change its list (or
invalidate it). There's no way to tell if a iterator's element got
moved by our theoretical "Split" without iterating through the
affected elements, which is O(n).

The current Splice escapes this fate by virtue of the fact that *all*
iterators are affected, so the algorithm can be made O(n) in iterators
but not in elements.

The only other option for other routines would to take the position
that all operations that can move a subrange of elements from one list
to another invalidate *all* the source lists' iterators. This looks
like a good solution on paper, but I think its quite liable to destroy
anyone's custom sort algorithm, which was the whole point of this
exercise in the first place.

So I'm not real sure we have a good reason for "Split" now after all.

Re: list strawman

[Georg Bauhaus]

Ted Dennison <dennison@telepath.com> wrote:
: In article <mailman.1010451062.16465.comp.lang.ada@ada.eu.org>, Steven Deller
: says...
:>That seems to me to be a fundamental flaw in the interface.  Yes, I know
:>sorting is predefined in the interface, but as there is only ONE sort
:>predefined, I'd think users might want to implement their own sort.
: 
: The sort used will probably be Quicksort too (yes, I know that's not your
: point). 

Another suggestion: Saving the current length of the list will allow
a quick inspection to choose an algorithm, so Insertion Sort could be
used for short lists, which can be made stable and is faster for doubly
linked lists than for arrays. 
Also, it does not have the n**2 problem for pre-sorted lists.


Georg

Re: list strawman

[Ted Dennison]

In article <a1fo5f$o10$1@a1-hrz.uni-duisburg.de>, Georg Bauhaus says...
>
>Another suggestion: Saving the current length of the list will allow
>a quick inspection to choose an algorithm, so Insertion Sort could be
>used for short lists, which can be made stable and is faster for doubly
>linked lists than for arrays. 
>Also, it does not have the n**2 problem for pre-sorted lists.

We probably don't want to get into the business of specifying implementations.
It may be reasonable to say things like "sort should be O(nlogn) in the average
case.", or "sort shall be stable", or even "Size should be O(C) in the worst
case". But I think what sort algorithm to use should be almost entirely left up
to the discretion of the implementors.

Now you might have meant this as a suggestion to us implementors. For my
reference implementation, I'm planning on just using a relatively simple
Quicksort (hopefully in-place, non-recursive, and stable). I don't care that
much about efficiency for small lists because the Sort is going to be quick on
small lists anyway, so there isn't all that much time to gain. Its not really
worth undully complicating things for them. I also don't really think its worth
pouring mass quantities of effort into making this sort as fast as possible,
since "*.Maps.Unbounded.Map" will presumably be the place to turn when you want
to deal with a sorted structure. 

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: list strawman

[Jeffrey Carter]

Ted Dennison wrote:
> 
> The sort used will probably be Quicksort too (yes, I know that's not your
> point).

I would suggest merge sort. Merge sort is O(N log N) worst case in time,
and well suited to sorting a list. Because a list already has the "Next"
pointers in each node, merge sort, which is usually described as being
O(N) in space, is O(1) in space for a list.

O(N log N) worst case in time seems better than the O(N**2) worst case
in time you get from Quick Sort.

-- 
Jeff Carter
"Death awaits you all, with nasty, big, pointy teeth!"
Monty Python & the Holy Grail

Re: list strawman

[Florian Weimer]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> I've done a priliminary implementation of
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> using SAL lists as the base.

While working on test cases for a similar list implementation, I
discovered that it isn't clear what happens if one tries to insert the
same list into itself using the iterator-based Insert procedure.

Re: list strawman

[Florian Weimer]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> I've done a priliminary implementation of
> http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> using SAL lists as the base.

While working on test cases for a similar list implementation, I
discovered that it isn't clear what should happen if one tries to
insert the same list into itself using the iterator-based Insert
procedure.

The specification seems to allow it, but to me, it seems that this
feature is not useful in practice and just adds unnecessary overhead.

Re: list strawman

[Stephen Leake]

Florian Weimer <fw@deneb.enyo.de> writes:

> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> 
> > I've done a priliminary implementation of
> > http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> > using SAL lists as the base.
> 
> While working on test cases for a similar list implementation, I
> discovered that it isn't clear what should happen if one tries to
> insert the same list into itself using the iterator-based Insert
> procedure.

Yes, this could easily lead to an infinite loop. I suggest testing for
this case, and raising some exception.

> The specification seems to allow it, but to me, it seems that this
> feature is not useful in practice and just adds unnecessary
> overhead.

Which feature? The whole idea of inserting a list using an iterator?
or just inserting a list into itself?

What overhead? Testing for the special case? That's really small.

-- 
-- Stephe

Re: list strawman

[Florian Weimer]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

>> The specification seems to allow it, but to me, it seems that this
>> feature is not useful in practice and just adds unnecessary
>> overhead.
>
> Which feature? The whole idea of inserting a list using an iterator?
> or just inserting a list into itself?

Just inserting a list into itself.

> What overhead? Testing for the special case? That's really small.

Implementing the special case (as required by the specification) seems
to be a bit complicated.