List container strawman 1.2

List container strawman 1.2

[Ted Dennison]

I've attached a slightly updated version of the list container strawman. 
This contains a few changes which I think there was consensus for, and 
some oversight corrections. Specificly:

A version of Insert using a List rather than just a single element was 
added.

A "Modify" routine was added.

The Done_Iterating constant was transmogrified into a Has_Item boolean 
function.

Unary "+" changed to "Singleton". (I know the name is still 
contravesial, but there does appear to be general agreement to not use "+".)

Added Pop functions.

Changed the name of the "Iterator" type to "Index", and 
"Passive_Iterator" to "Iterator". I'm trying out this solution before 
taking the more drastic step of making a safe active iterator. We don't 
quite yet seem to have reached a consensus for making that drastic of a 
change. However, it seems to me that the terminology I was using may 
have been a bit of a stumbling block for some, so I'd like everyone to 
think about it with the new name a bit and re-formulate your opinions. 
As an "index" it makes sense that you would supply it along with its 
List to routines, and that it isn't particularly safe, as that is how 
array indexes work too.

--- code attached below ----

with Ada.Finalization;
with Ada.Streams;

-------------------------------------------------------------------------------
-- This file contains a proposal for a standard Ada list package.
--
-- version - Strawman 1.2
-------------------------------------------------------------------------------
generic
    type Element is private;
package Containers.Lists.Unbounded is

 
-----------------------------------------------------------------------------
    -- The list type. I know the name's a bit redundant, but it doesn't 
look too
    -- bad, and any fully-named use will have to have a different name 
for the
    -- package anyway.
 
-----------------------------------------------------------------------------
    type List is private;

 
-----------------------------------------------------------------------------
    -- List construction operations. The returned list will contain 
*copies* of
    -- all the elements in the source lists, so these routines could get
    -- time-consuming. However, they should be useful for Lisp-like 
processing.
    --
    -- Unary plus ("+") wasn't a big hit for the "Construct" routine, so 
now I'm
    -- floating "Singleton".
 
-----------------------------------------------------------------------------
    function "&" (Left, Right : Element) return List;
    function "&" (Left : Element; Right : List) return List;
    function "&" (Left : List; Right : Element) return List;
    function "&" (Left, Right : List) return List;
    function Singleton (Initial_Element : Element) return List;

 
-----------------------------------------------------------------------------
    -- "push" and "pop" operations. Pops on empty lists raise No_Item.
 
-----------------------------------------------------------------------------
    No_Item : exception;

    procedure Push_Front (Target : in out List; New_Element : in 
Element);
    procedure Pop_Front  (Target : in out List; Old_Element :    out 
Element);
    procedure Push_Back  (Target : in out List; New_Element : in 
Element);
    procedure Pop_Back   (Target : in out List; Old_Element :    out 
Element);
    function  Pop_Front  (Source : List) return List;
    function  Pop_Back   (Source : List) return List;

 
-----------------------------------------------------------------------------
    -- Non-modifying query operations.
 
-----------------------------------------------------------------------------
    function Is_Empty (Subject : List) return Boolean;
    function Size     (Subject : List) return Natural;
    function Front    (Subject : List) return Element;
    function Back     (Subject : List) return Element;

 
-----------------------------------------------------------------------------
    -- Passive iterator. Operation will be applied on each element on 
the list
    -- Opertion can terminate this process early by setting Quit to True.
 
-----------------------------------------------------------------------------
    generic
       with procedure Operation (Target : in out Element; Quit : out 
Boolean);
    procedure Iterator (Target : in out List);

 
-----------------------------------------------------------------------------
    -- List index routines. For an empty list, Has_Item(First) = False. 
Item and
    -- Remove raise No_Item if they are called when Has_Item(Location) = 
False.
    -- As written, a typical iteration idiom would look like:
    --
    --    i := My_Lists.First (My_List);
    --    while My_Lists.Has_Item (i) loop
    --       do stuff with My_Lists.Item(i);
    --       i := My_Lists.Next (i);
    --    end loop;
    --
    -- Another alternative using "Size" would be:
    --
    --  i := My_Lists.First (My_List);
    --  for iteration_count in 1..My_Lists.Size (My_List) loop
    --    do stuff with My_Lists.Item (i);
    --    i := My_Lists.Next (i);
    --  end loop;
    --
 
-----------------------------------------------------------------------------
    type Index is private;

    function Has_Item (Location : Index) return Boolean;

    function First    (Subject  : List)  return Index;
    function Last     (Subject  : List)  return Index;
    function Next     (Location : Index) return Index;
    function Previous (Location : Index) return Index;
    function Item     (Location : Index) return Element;

    -- Ideally these routines would verify that Location was issued for 
the Subject
    -- list and is still valid, but that would be tough to enforce. 
Better to call
    -- such misuse a "bounded error", or somesuch.
 
-----------------------------------------------------------------------------
    -- Remove the element at the given location, and advance Location to 
the next
    -- element.
    -- If Done_Iterating then No_Item will be raised.
    -- If Location=First, then Location will be set to the new First.
    -- If Location=Last, then Location will be set to Done_Iterating.
    -- otherwise, Location will be set to what Next was previously (the next
    -- element after the removal).
 
-----------------------------------------------------------------------------
    procedure Remove (Subject : in out List; Location : in out Index);

 
-----------------------------------------------------------------------------
    -- Insert a copy of the given element (or list) at the given 
location in the
    -- list (in front of the element that is already there). Location will
    -- continue to point to the same element.
    -- If Done_Iterating, then the element will be put at the end of the
    -- list. Otherwise, the element will be placed immediately before 
the element
    -- at Location. Location will continue to reference that element.
 
-----------------------------------------------------------------------------
    procedure Insert (Subject : in out List; Location : in Index;
                                             New_Item : in Element);
    procedure Insert (Subject : in out List; Location  : in Index;
                                             New_Items : in List);

 
-----------------------------------------------------------------------------
    -- Modify the element at the given location in the list. Location will
    -- continue to point to the same element, but the value at that 
location will
    -- be changed to New_Value.
    -- If Done_Iterating, then No_Item will be raised.
 
-----------------------------------------------------------------------------
    procedure Modify (Subject : in out List; Location  : in Index;
                                             New_Value : in Element);

 
-----------------------------------------------------------------------------
    -- Sorting routine.
    -- To sort in increasing order, use the ">" routine for the 
Reverse_Order
    -- parameter. To sort in decreasing order, substitute your "<" 
routine for
    -- the Reverse_Order parameter. :-)
 
-----------------------------------------------------------------------------
    generic
       with function Reverse_Order (Left, Right : in Element) return 
Boolean;
    procedure Sort (Subject : in out List);

 
-----------------------------------------------------------------------------
    -- Stream attributes.
 
-----------------------------------------------------------------------------
    procedure Stream_Read
      (Stream : access Ada.Streams.Root_Stream_Type'Class;
       Item   : out    List);

    procedure Stream_Write
      (Stream : access Ada.Streams.Root_Stream_Type'Class;
       Item   : in     List);

private
    -- Placebo entries to make the compiler happy (so I know the syntax 
above is correct)

    type List is new Ada.Finalization.Controlled with null record;

    for List'Read use Stream_Read;
    type Index is new Boolean;
    for List'Write use Stream_Write;

end Containers.Lists.Unbounded;

Re: List container strawman 1.2

[Jeffrey Carter]

This looks pretty good. Index is OK, though I think Position or Location
would be better. I still think the declarations are reversed, and the
operations using Index should come before the dequeue- and string-like
operations. You have left a reference to Done_Iterating in the comments.

Inserting one list into another seems like overkill. If we're going to
have that kind of operation, perhaps we should include something like

type Bunch_O_Elements is array (Positive range <>) of Element; -- :)

function Make (Elements : Bunch_O_Elements) return List;

Primes : Int_List.List := Int_List.Make ((2, 3, 5, 7, 11, 13));

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail

Re: List container strawman 1.2

[Ted Dennison]

In article <3BECAAE8.62110AFC@acm.org>, Jeffrey Carter says...
>Inserting one list into another seems like overkill. If we're going to

It seemed that way to me too when suggested, but no one else said anything of
the sort, and its easy enough to code up. I'm still unconvinced that this is
something that folks would have to do a lot.

>type Bunch_O_Elements is array (Positive range <>) of Element; -- :)
>
>function Make (Elements : Bunch_O_Elements) return List;
>
>Primes : Int_List.List := Int_List.Make ((2, 3, 5, 7, 11, 13));

:-)
I seriously considered adding routines to convert between unbounded arrays and
lists. I'd probably just name them "To" and "From" (which is what the same
routines in Ada.Strings.Unbounded *should* have been named).

---
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 container strawman 1.2

[Florian Weimer]

    -- Ideally these routines would verify that Location was issued
    -- for the Subject list and is still valid, but that would be
    -- tough to enforce. Better to call such misuse a "bounded error",
    -- or somesuch.

You should not call it a "bounded error" because that would be
confusing.  Such errors result in erroneous execution with typical
implementations.  For debugging, we might add an additional variable
parameter to the generic, which can be used to enable debugging.  It
should default to "no debugging", and in such cases, at least GNAT
generates no code for "if Debugging then ... end if;" conditional
statements.

Regarding the the name of "Index", I would like to reserve this word
for discrete types.  "Location" or "Position", as proposed by Jeffrey,
is probably better.

What about terminating Iterator prematurely using an exception?  It's
a bit ugly, granted, but with the "out" parameter approach, I've
managed to forget to set the parameter more than once.  If the Quit
parameter is going to stay, we shouldn't use a Boolean type for it,
but a new enumeration type.

Re: List container strawman 1.2

[Ehud Lamm]

Ted,

If I am seeing correctly we are still stuck with the library level
instantiation bussiness.
I must say that it seems to me that I'd rather ditch the Controlled type,
and remove this obstacle.

Don't others detest this as much as I do?

Ehud

Re: List container strawman 1.2

[Larry Kilgallen]

In article <9sjf4n$odm$1@news.huji.ac.il>, "Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:
> Ted,
> 
> If I am seeing correctly we are still stuck with the library level
> instantiation bussiness.
> I must say that it seems to me that I'd rather ditch the Controlled type,
> and remove this obstacle.
> 
> Don't others detest this as much as I do?

I prefer a Controlled type.

Re: List container strawman 1.2

[Ted Dennison]

In article <9sjf4n$odm$1@news.huji.ac.il>, Ehud Lamm says...
>
>If I am seeing correctly we are still stuck with the library level
>instantiation bussiness.
>I must say that it seems to me that I'd rather ditch the Controlled type,
>and remove this obstacle.
>
>Don't others detest this as much as I do?

Well, as I remember the discussion last time, to get rid of that you'd have to
get rid of the functional notation (by making List limited). The general
consensus seemed to be that this was undesirable.

Also note that if we go to a "safe active iterator", which seems to be the
direction the discussion is heading at the moment, then that would *also*
require List to be Controlled.

---
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.

List container: Insert and Delete

[Nick Roberts]

Sorry, but I want to draw attaention to a post I have made (which may have
got lost in another thread for some readers) in which I hopefully demolish
the idea that Insert or Delete is needed in a list container. You don't need
a 'Position' type (you have an implicit position in the list object itself).

All the horrible shinanigans related to insert and delete can and should be
completely avoided. I'll re-post my demo of why, if you like. Again, I
implore you not to make this terrible design mistake (and I'm sure it is).
To use one of my amusing analogies, it's a bit like watching people having
an earnest discussion of whether to have 10 or 12 wings on a jet fighter.

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Ted Dennison]

In article <87668ivpw8.fsf@deneb.enyo.de>, Florian Weimer says...
>You should not call it a "bounded error" because that would be
>confusing.  Such errors result in erroneous execution with typical
>implementations.  For debugging, we might add an additional variable

I thought the whole point of "bounded errors" was that they *don't* result in
erroneous executions. Instead, there's a certian defined set of nasty things
that may happen (vs. the infamous "nasal monkeys" you get when you say
"erronious").

>parameter to the generic, which can be used to enable debugging.  It
>should default to "no debugging", and in such cases, at least GNAT
>generates no code for "if Debugging then ... end if;" conditional
>statements.

That's a technique I have to say I've never used in final production code, and
is certianly not used anywhere in the rest of the current Ada library. Exactly
what benifit would we get from this? I don't think you can use it to switch
between safe active iterators and unsafe "Locations", as the declarations would
have to be different too.

>Regarding the the name of "Index", I would like to reserve this word
>for discrete types.  "Location" or "Position", as proposed by Jeffrey,
>is probably better.

Fair enough.

>What about terminating Iterator prematurely using an exception?  It's
>a bit ugly, granted, but with the "out" parameter approach, I've
>managed to forget to set the parameter more than once.  If the Quit
>parameter is going to stay, we shouldn't use a Boolean type for it,
>but a new enumeration type.

I suspect we would have some violent objections to that idea from some people
(Although its still an option for the user. Just handle it outside the Iterator
call). What would you say to the proposal we had to make it "in out" with a
default?


---
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 container strawman 1.2

[Ted Dennison]

In article <3BECA3B7.5020702@telepath.com>, Ted Dennison says...
>Changed the name of the "Iterator" type to "Index", and 
>"Passive_Iterator" to "Iterator". I'm trying out this solution before 
>taking the more drastic step of making a safe active iterator. We don't 

After sleeping on this issue, here are my current thoughts. A safe active
iterator would probably be *logicaly* more appropriate to this package, while a
faster unsafe "Index" would be more appropriate for Containers.Bounded.Lists.
However, as coded, that would completely destroy the ability to use this package
in real-time systems. Currently any use of an active iterator (eg: First, Next),
creates a new iterator, which would force dynamic allocation of a new iterator
node on the List's iterator list. 

In many (most?) real-time systems start-up heap allocations are OK, but runtime
heap operations are verboten. Again, for those unfamiliar with the issues, speed
isn't nessecarily the problem (although that may well be too). Its an issue of
time-determinism. There's just no way to tell up front how long a heap op is
going to take. It may be quite quick on average, but if we miss a deadline once,
the whole system is hosed.

This issue could be mostly fixed by changing the iterator-returning functions
into procedures. However there is another issue, which is that our theoretical
Containers.Lists.Bounded *cannot* use this method (well...I guess it could if we
limited the number of allowable iterators per List). Obviously the packages will
need to have some differences, but having different iterator/location methods
seems a smidge on the extreme side.

---
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 container: Insert and Delete

[Ted Dennison]

In article <9sjkc7$145mhb$1@ID-25716.news.dfncis.de>, Nick Roberts says...
>All the horrible shinanigans related to insert and delete can and should be
>completely avoided. I'll re-post my demo of why, if you like. Again, I

I'd prefer a good explanation in English. I honestly couldn't follow your code.
Perhaps I'm just being dense (more than a small possiblity, my wife would
probably say), but I couldn't see what you were getting at at all.

---
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 container strawman 1.2

[Florian Weimer]

Ted Dennison<dennison@telepath.com> writes:

> In article <87668ivpw8.fsf@deneb.enyo.de>, Florian Weimer says...
>>You should not call it a "bounded error" because that would be
>>confusing.  Such errors result in erroneous execution with typical
>>implementations.  For debugging, we might add an additional variable
>
> I thought the whole point of "bounded errors" was that they *don't*
> result in erroneous executions.

Oops, sorry.  "Such errors" referred to errors in using the list
container routines, IOW these usage errors can lead to erroneous
execution.

> That's a technique I have to say I've never used in final production
> code, and is certianly not used anywhere in the rest of the current
> Ada library.

What about pragma Assert? It's similar.

> Exactly what benifit would we get from this?

You would get a debugging version without the need to duplicate a lot
of code.

> I don't think you can use it to switch between safe active iterators
> and unsafe "Locations", as the declarations would have to be
> different too.

Hmm, I haven't completely followed the discussion, but there was a
proposal for including a list pointer in the Location/Position type,
and it made sense to me.  If this proposal is followed, all data would
be there to verify these operations (the only thing missing is
verification of the list access value itself).

But perhaps it isn't worth the trouble, I don't know.

>>What about terminating Iterator prematurely using an exception?  It's
>>a bit ugly, granted, but with the "out" parameter approach, I've
>>managed to forget to set the parameter more than once.  If the Quit
>>parameter is going to stay, we shouldn't use a Boolean type for it,
>>but a new enumeration type.
>
> I suspect we would have some violent objections to that idea from
> some people

Yes, of course, and I understand these objections.

> What would you say to the proposal we had to make it "in out" with a
> default?

That's probably better.  I think we can assume that most of the time,
the user wants to iterate over the entire structure, so we could
specify a default value of "Continue", and in many cases, the user
wouldn't have to deal with this parameter at all.

BTW, there's an unnecessary negative in the Sort routine:

    generic
       with function Reverse_Order (Left, Right : in Element) return Boolean;
    procedure Sort (Subject : in out List);

I think it would be better to test for "In_Order" ("<=") because this
seems to be more natural.  In addition, we should probably specify if
Sort is stable or not.

(And I wouldn't include the stream attributes in the main package, but
in a child.)

Re: List container strawman 1.2

[Florian Weimer]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> If I am seeing correctly we are still stuck with the library level
> instantiation bussiness.  I must say that it seems to me that I'd
> rather ditch the Controlled type, and remove this obstacle.

I agree completely.  The controlled type is not such a big win for
this kind of design, it seems.

Re: List container strawman 1.2

[Ted Dennison]

In article <87d72qfrtd.fsf@deneb.enyo.de>, Florian Weimer says...
>
>Oops, sorry.  "Such errors" referred to errors in using the list
>container routines, IOW these usage errors can lead to erroneous
>execution.

I used the term "bouded error", because it seems to me that the limits for what
nasty things can happen is definable. Its probably not worth wasting this much
breath over though. :-)


>What about pragma Assert? It's similar.

It's also Gnat-specific. Anyway, I think it would be easier for acceptance of
this facility if there were one implemtation (spec and body) that could (not
must but could) be used by any compliant compiler vendor.

>Hmm, I haven't completely followed the discussion, but there was a
>proposal for including a list pointer in the Location/Position type,
>and it made sense to me.  If this proposal is followed, all data would
>be there to verify these operations (the only thing missing is
>verification of the list access value itself).

Even if we did that, the declarations of List and Location in the private part
of the spec would have to be different depending on what approach is used.
That's why we don't want to move to a reference implementation for the body
until we get this issue resolved. 

>BTW, there's an unnecessary negative in the Sort routine:
>
>    generic
>       with function Reverse_Order (Left, Right : in Element) return Boolean;
>    procedure Sort (Subject : in out List);
>
>I think it would be better to test for "In_Order" ("<=") because this
>seems to be more natural.  In addition, we should probably specify if
>Sort is stable or not.

You have a point. My thinking was that since the routine is a boolean, and can
be substitued with any matching function whatsoever, its generic name should say
what action needs to be done when the condition is true, rather than stipulating
the conditions under which *nothing* will be done.

Perhaps some comparative code would help folks decide:

Assume:
  package Integer_List is new Containers.Lists.Unbounded (Integer);

Version 1:
  procedure Sort_Increasing is new Integer_List.Sort (Reverse_Order => ">");

Version 2:
  procedure Sort_Increasing is new Integer_List.Sort (In_Order => "<");

I'm not sure what you mean by "Stable". If you mean some flag will be set and
every insertion after that will also call "Reverse_Order" to keep things sorted
that way, I'd say no. Hmmm. I'd meant to add an "Insert_Sorted" routine for that
issue. Perhaps you were leading up to 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 container strawman 1.2

[Jean-Marc Bourguet]

Ted Dennison wrote:

> Assume:
>   package Integer_List is new Containers.Lists.Unbounded (Integer);
> 
> Version 1:
>   procedure Sort_Increasing is new Integer_List.Sort (Reverse_Order => ">");
> 
> Version 2:
>   procedure Sort_Increasing is new Integer_List.Sort (In_Order => "<");

You probably mean "<=" instead of "<".

I prefer the In_Order version.
 
> I'm not sure what you mean by "Stable". If you mean some flag will be set and
> every insertion after that will also call "Reverse_Order" to keep things sorted
> that way, I'd say no. Hmmm. I'd meant to add an "Insert_Sorted" routine for that
> issue. Perhaps you were leading up to that.

A sorting algorithm is stable if after applying it, the relative order
of elements comparing equal is conserved.  That's usefull when you want
to sort on several keys: you sort several times beginning with the less
significant key.

For a list, the natural sorting algorithm is merge sort which is stable.

-- 
Jean-Marc

Re: List container strawman 1.2

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> In article <9sjf4n$odm$1@news.huji.ac.il>, Ehud Lamm says...
> >
> >If I am seeing correctly we are still stuck with the library level
> >instantiation bussiness.
> >I must say that it seems to me that I'd rather ditch the Controlled type,
> >and remove this obstacle.
> >
> >Don't others detest this as much as I do?
> 
> Well, as I remember the discussion last time, to get rid of that you'd have to
> get rid of the functional notation (by making List limited). The general
> consensus seemed to be that this was undesirable.

Even if the list is limited (something I would not object to, I don't see
much use for a non limited list where the assignement does make a copy of
the list), it has to be controlled or you'll have a memory leak or impose
to call a cleanup procedure.

-- 
Jean-Marc

RE: List container strawman 1.2

[Steven Deller]

> After sleeping on this issue, here are my current thoughts. A 
> safe active iterator would probably be *logicaly* more 
> appropriate to this package, while a faster unsafe "Index" 
> would be more appropriate for Containers.Bounded.Lists. 
> However, as coded, that would completely destroy the ability 
> to use this package in real-time systems. Currently any use 
> of an active iterator (eg: First, Next), creates a new 
> iterator, which would force dynamic allocation of a new 
> iterator node on the List's iterator list. 
Ted,

I don't believe this conclusion follows.  I would think the Index type
could have suitable links to allow it to be "associated" with a list
(probably want it to be limited private).  There would also have to be
handling when the object goes out of scope, to prevent dangling
references, but that should be possible using controlled types.

>In many (most?) real-time systems start-up heap allocations 
> are OK, but runtime heap operations are verboten. Again, for 
> those unfamiliar with the issues, speed isn't necessarily the 
> problem (although that may well be too). Its an issue of 
> time-determinism. There's just no way to tell up front how 
> long a heap op is going to take. It may be quite quick on 
> average, but if we miss a deadline once, the whole system is hosed.
> 
> This issue could be mostly fixed by changing the 
> iterator-returning functions into procedures. However there 
> is another issue, which is that our theoretical 
> Containers.Lists.Bounded *cannot* use this method (well...I 
> guess it could if we limited the number of allowable 
> iterators per List). Obviously the packages will need to have 
> some differences, but having different iterator/location 
> methods seems a smidge on the extreme side.

Same method works for bounded as well.  The iterators are "bounded" only
by the number of objects created by the user.

Regards,
Steve
deller@smsail.com
Smooth Sailing LLC

Re: List container strawman 1.2

[Jacob Sparre Andersen]

Ted Dennison wrote:

[ ditching the Controlled type ]

> Well, as I remember the discussion last time, to get rid of that you'd have to
> get rid of the functional notation (by making List limited). The general
> consensus seemed to be that this was undesirable.

I may have missed some important points in the discussion,
but why is it undesirable to make List limited? I would
definitely prefer a limited list type, using Copy and Append
procedures instead of ":=" and "&".

> Also note that if we go to a "safe active iterator", which seems to be the
> direction the discussion is heading at the moment, then that would *also*
> require List to be Controlled.

<thinking hard>

Isn't that only if the "index" is external to the list type?

Jacob
-- 
The great LEGO building competition of the year:
              http://www.1000steine.de/themen/bauwettbewerb/

Re: List container strawman 1.2

[Ehud Lamm]

Jean-Marc Bourguet <jbourguet@free.fr> wrote in message
news:3BED76AA.3FFF82C8@free.fr...

> Even if the list is limited (something I would not object to, I don't see
> much use for a non limited list where the assignement does make a copy of
> the list), it has to be controlled or you'll have a memory leak or impose
> to call a cleanup procedure.
>

If we don't make the type controlled we must have a clean up routine, of
course.

Ehud

Re: List container: Insert and Delete

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:_edH7.20119$xS6.32495@www.newsranger.com...
> I'd prefer a good explanation in English. I honestly couldn't follow your
code.

I've posted what I hope is an explanation in another thread.

> Perhaps I'm just being dense (more than a small possiblity, my wife would
> probably say), but I couldn't see what you were getting at at all.

LOL

Really, I think it was my code that was dense. I hope my exposition will be
illuminating.

Furthermore, I'm being very clumsy in saying the list type should not have
insertion or deletion: on the contrary, it should, but not based on any
iterator position, rather on a notional positional index (of type Positive),
exactly like Ada's Unbounded_Strings.

I'm putting together an alternative proposal (two package specs to start off
with), which I'll e-mail to you, Ted, if you don't object, for posting on
your splendid site. Did I ever send you a copy of my 1999 proposal to the
ASCL group?

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Jeffrey Carter]

Ted Dennison wrote:
> 
> Assume:
>   package Integer_List is new Containers.Lists.Unbounded (Integer);
> 
> Version 1:
>   procedure Sort_Increasing is new Integer_List.Sort (Reverse_Order => ">");
> 
> Version 2:
>   procedure Sort_Increasing is new Integer_List.Sort (In_Order => "<");

Or possibly Out_Of_Order instead of Reverse_Order, though I think "<" is
clearer.

> 
> I'm not sure what you mean by "Stable". If you mean some flag will be set and
> every insertion after that will also call "Reverse_Order" to keep things sorted
> that way, I'd say no. Hmmm. I'd meant to add an "Insert_Sorted" routine for that
> issue. Perhaps you were leading up to that.

A stable sort keeps identical values in the same order after the sort.
An unstable sort may change the order of identical values.

Consider sorting something like

1(1), 1(2), 1(3), 1(4)

[where 1(n) indicates that this instance of 1 occurs nth in the unsorted
list]

into ascending order. If 1(I) always occurs before 1(I+1) in the sorted
list then the sort is stable.

In many cases this is irrelevant. For example, a well optimized quick
sort is faster than other sorts for large sets in almost all situations,
but is unstable. However, it is an easy matter to include a position
number with each value and define "<" so it sorts identical values into
the correct order, thus gaining the speed of quick sort without
sacrificing stability.

Merge sort seems to be the best sort for a list. Although it's O(N) in
space, that extra space already exists in a list as the pointers between
nodes, so it becomes O(N) in space. Merge sort is always O(N log N) in
time.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail

Re: List container: Insert and Delete

[Ehud Lamm]

Nick Roberts <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9sk5rq$140qdr$3@ID-25716.news.dfncis.de...
> I'm putting together an alternative proposal (two package specs to start
off
> with), which I'll e-mail to you, Ted, if you don't object, for posting on
> your splendid site. Did I ever send you a copy of my 1999 proposal to the
> ASCL group?


How about putting it on Adapower, which is the "standard" link for Ada
material? I am sure David will be happy to host this effort, while we
quibble about how to name it...

Ehud

Re: List container strawman 1.2

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <9sjf4n$odm$1@news.huji.ac.il>, Ehud Lamm says...
> >
> >If I am seeing correctly we are still stuck with the library level
> >instantiation bussiness.
> >I must say that it seems to me that I'd rather ditch the Controlled type,
> >and remove this obstacle.
> >
> >Don't others detest this as much as I do?
> 
> Well, as I remember the discussion last time, to get rid of that you'd have to
> get rid of the functional notation (by making List limited). The general
> consensus seemed to be that this was undesirable.

I'd prefer both a limited list type and a limited Element type, but even
then the list type must be controlled. In any case, a standard component
library must be suitable for industrial use, and structures that don't
initialize and finalize themselves don't measure up.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail

Re: List container: Insert and Delete

[Jeffrey Carter]

Nick Roberts wrote:
> 
> Sorry, but I want to draw attaention to a post I have made (which may have
> got lost in another thread for some readers) in which I hopefully demolish
> the idea that Insert or Delete is needed in a list container. You don't need
> a 'Position' type (you have an implicit position in the list object itself).

I recall that I couldn't understand your post. That may just be me, but
I recall that no one else seemed to be able to understand your post
(including you), and my request for an example that actually compiles
has resulted in nothing so far.

Mathematically, lists are defined in terms of positions and insertions
and deletions. I don't know what you're talking about, but it isn't a
list.

-- 
Jeff Carter
"Son of a window-dresser."
Monty Python & the Holy Grail

Re: List container strawman 1.2

[Ted Dennison]

In article <3BED75C8.D9D55263@free.fr>, Jean-Marc Bourguet says...
>A sorting algorithm is stable if after applying it, the relative order
>of elements comparing equal is conserved.  That's usefull when you want

Well, that would clearly be up to the person who supplies the comparison
routine, would it not? I mean (assuming the current definition), if "<" or ">"
is supplied, then equal values will not be changed. On the other hand, if "<="
or ">=" are supplied, then they will be.

If you are talking *assuming* the proper supplied routine, then I guess that's a
matter for discussion. It sounds like we probably have at least one vote for
requiring that, no?

---
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 container: Insert and Delete

[Ted Dennison]

In article <9sk9al$8j8$1@news.huji.ac.il>, Ehud Lamm says...
>
>How about putting it on Adapower, which is the "standard" link for Ada
>material? I am sure David will be happy to host this effort, while we
>quibble about how to name it...

I've just been using my website because its easy for me to access at a moment's
notice. I don't want to slow down discussion while we wait for someone else to
come in to work or wake up or get back from the movies or whatever. I don't have
any problem posting Nick's either, but if it gets to be a lot then perhaps there
should be some official place.

---
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 container strawman 1.2

[Ted Dennison]

In article <3BED7AFD.737C2AE9@nbi.dk>, Jacob Sparre Andersen says...
>
>Ted Dennison wrote:
>> Also note that if we go to a "safe active iterator", which seems to be the
>> direction the discussion is heading at the moment, then that would *also*
>> require List to be Controlled.
>
><thinking hard>
>
>Isn't that only if the "index" is external to the list type?

I'm not sure what you think the alternative would be. Perhaps each list gets one
and only one active iterator, whose current value is somehow a facet of the list
itself?

---
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 container strawman 1.2

[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: Saturday, November 10, 2001 5:44 PM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: List container strawman 1.2

> In article <3BED75C8.D9D55263@free.fr>, Jean-Marc Bourguet says...
> >A sorting algorithm is stable if after applying it, the 
> relative order 
> >of elements comparing equal is conserved.  That's useful 
> when you want
> 
> Well, that would clearly be up to the person who supplies the 
> comparison routine, would it not? I mean (assuming the 
> current definition), if "<" or ">" is supplied, then equal 
> values will not be changed. On the other hand, if "<=" or 
> ">=" are supplied, then they will be.

That is not true.  There is no comparison routine that can be supplied
in an instantiation that will convert a non-stable sort to a stable
sort.  It is necessary to "know" the original positions and include
those positions as part of the comparison (the original position becomes
the tie-breaker to keep equal values from switching places).

For any sort that is O(NlogN) in time, converting it to a stable sort
requires O(N) space (to keep the position values with the records).  One
of the better ways to do a stable sort on an array is to create an O(N)
list of pointers to the original elements, sort the pointers, and then
rearrange the original array to match the new positions of the pointers.
The position of the elements then becomes the "tie-breaker".

I'd prefer having a "stable sort" generic that "wraps" an arbitrary
generic sorting routine, but it is not possible to pass a generic as a
generic formal :-(.

Jean-Marc Bourguet has it pretty much right, though I would prefer a
heap sort instead of a merge sort.  A heap sort is also guaranteed
O(NlogN) time, and also can be done "in place" more easily.

Regards,
Steve Deller
Smooth Sailing LLC

Re: List container: Insert and Delete

[Nick Roberts]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3BEDACC0.9A314B54@acm.org...
> I recall that I couldn't understand your post. That may just be me, but
> I recall that no one else seemed to be able to understand your post
> (including you), and my request for an example that actually compiles
> has resulted in nothing so far.

Hold your horses! As quick as I can. Phew. :-(

> Mathematically, lists are defined in terms of positions and insertions
> and deletions. I don't know what you're talking about, but it isn't a
> list.

We're programmers, Jeff, not mathematicians. We don't have to worry about
what the mathematical definition of a list is. What we do have to worry
about is what is: (a) useful from a user's point of view; (b) practical from
an implementational point of view.

My suggestion that insertions and deletions be positioned by specifying an
integer (starting at 1 for the first item in the list) satisfies (a), I
think, but not necessarily (b), depending on the implementation.

However, I'm pretty sure that trying to do insertions and deletions while
iterating through a list fails both (a) and (b) miserably. That's what I was
trying to get across.

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Jean-Marc Bourguet]

Ehud Lamm wrote:
> If we don't make the type controlled we must have a clean up routine, of
> course.

I think that the need to call a cleanup procedure is more a burden than the
constraint to have instanciation at library level.

-- 
Jean-Marc

Re: List container strawman 1.2

[Jean-Marc Bourguet]

Steven Deller wrote:

> Jean-Marc Bourguet has it pretty much right, though I would prefer a
> heap sort instead of a merge sort.  A heap sort is also guaranteed
> O(NlogN) time, and also can be done "in place" more easily.

A merge sort is O (N log N) and is in place for linked lists. I don't 
see how you can do an heap sort with linked list without additionnal
data.

-- 
Jean-Marc

Re: List container strawman 1.2

[Jean-Marc Bourguet]

Ted Dennison wrote:
> 
> In article <3BED75C8.D9D55263@free.fr>, Jean-Marc Bourguet says...
> >A sorting algorithm is stable if after applying it, the relative order
> >of elements comparing equal is conserved.  That's usefull when you want

[...]

> If you are talking *assuming* the proper supplied routine, then I guess that's a
> matter for discussion. It sounds like we probably have at least one vote for
> requiring that, no?

Stabality is a property of the sorting algorithm, not of the comparison
function. You can simulate a stable sort with a non stable algorithm at
the cost of complexifying the comparison function see Knuth TAOCP
Volume 3 for more information.

-- 
Jean-Marc

Re: List container strawman 1.2

[Larry Kilgallen]

In article <3BEE56EB.B77E50B1@free.fr>, Jean-Marc Bourguet <jbourguet@free.fr> writes:
> Ehud Lamm wrote:
>> If we don't make the type controlled we must have a clean up routine, of
>> course.
> 
> I think that the need to call a cleanup procedure is more a burden than the
> constraint to have instanciation at library level.

In particular, failure to call a cleanup routine will not be automatically
detected.

Re: List container strawman 1.2

[Jeffrey Carter]

Jeffrey Carter wrote:
> 
> Merge sort seems to be the best sort for a list. Although it's O(N) in
> space, that extra space already exists in a list as the pointers between
> nodes, so it becomes O(N) in space. Merge sort is always O(N log N) in
> time.

Typo alert! That should read "it becomes O(1) in space."

My fingers apologize for any confusion.

-- 
Jeff Carter
"I blow my nose on you."
Monty Python & the Holy Grail

Re: List container: Insert and Delete

[Jeffrey Carter]

Nick Roberts wrote:
> 
> We're programmers, Jeff, not mathematicians. We don't have to worry about
> what the mathematical definition of a list is. What we do have to worry
> about is what is: (a) useful from a user's point of view; (b) practical from
> an implementational point of view.

I'm a software engineer, but I use lists when I need to insert and
delete at arbitrary points in a sequence, just as with the mathematical
definition.

> 
> My suggestion that insertions and deletions be positioned by specifying an
> integer (starting at 1 for the first item in the list) satisfies (a), I
> think, but not necessarily (b), depending on the implementation.

Positive integers are generally used to indicate positions in lists in
mathematical notation. For a software list implemented using pointers
(an unbounded list), using integers to indicate positions becomes an
O(N) time operation for every reference to the list. It is better to
abstract the concept of a position to something that provides the same
behavior but with O(1) time complexity.

> 
> However, I'm pretty sure that trying to do insertions and deletions while
> iterating through a list fails both (a) and (b) miserably. That's what I was
> trying to get across.

I agree that one should not be doing insertions and deletions while
iterating over a list. Iterators should not allow this, and positions
should generally not be used for iteration.

-- 
Jeff Carter
"I blow my nose on you."
Monty Python & the Holy Grail

RE: List container strawman 1.2

[Steven Deller]

> A merge sort is O (N log N) and is in place for linked lists. I don't 
> see how you can do an heap sort with linked list without 
> additional data.

This was in the context of a "stable" sort, in which case the necessary
"additional data" is the same data needed to provide a stable sort.

Merge sort is fine too :-).
Regards,
Steve

RE: List container: Insert and Delete

[Steven Deller]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> > However, I'm pretty sure that trying to do insertions and deletions 
> > while iterating through a list fails both (a) and (b) miserably. 
> > That's what I was trying to get across.
> 
> I agree that one should not be doing insertions and deletions 
> while iterating over a list. Iterators should not allow this, 
> and positions should generally not be used for iteration.
> 
> -- 
> Jeff Carter

I don't understand this comment.  It seems to me that iteration to find
some value and then insertion at that point is a normal list operation.

I see no difficulty with iteration doing inserts and deletes, even with
other simultaneous iterators.  It is a simple matter to define the
semantics to be unambiguous, particularly if you use positions that are
"in between" elements and semantics like:
   delete following item
   delete preceding item
   get value of following item
   get value of preceding item
   move to next position (skip over an element)
   move to previous position (skip backwards over an element)
   goto head of list (position before first item)
   goto tail of list (position after last item)
   is at end of list (boolean)
   is at beginning of list (boolean)

These are all well defined, even for empty lists.

Regards,
Steve Deller

Re: List container strawman 1.2

[Simon Wright]

Jeffrey Carter <jrcarter@acm.org> writes:

> I'd prefer both a limited list type and a limited Element type, but
> even then the list type must be controlled. In any case, a standard
> component library must be suitable for industrial use, and
> structures that don't initialize and finalize themselves don't
> measure up.

This would be untrue in a (safety-related) environment where
finalization was regarded as far too clever to be verifiable.

Re: List container: Insert and Delete

[Nick Roberts]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3BEEB766.B50C969@acm.org...
> Positive integers are generally used to indicate positions in lists in
> mathematical notation. For a software list implemented using pointers
> (an unbounded list), using integers to indicate positions becomes an
> O(N) time operation for every reference to the list. It is better to
> abstract the concept of a position to something that provides the same
> behavior but with O(1) time complexity.

I know it sounds like a good idea, but I don't think it is in reality. Just
look at all the messing around that has to be done, with pointers to check
you don't delete this, or to check you don't try to access something after
deleting it. It's just not worth it.

It's all very well saying access will be O(N), but that ignores the fact
that chasing down a linked list of pointers is a fast operation (because
each step is very simple). In practice, using integers to index positions
gains you: simplicty for the user; simplicity for the implementor. With
short lists, it's likely to be the most efficient possible implementation
anyway.

> > However, I'm pretty sure that trying to do insertions and deletions
while
> > iterating through a list fails both (a) and (b) miserably. That's what I
was
> > trying to get across.
>
> I agree that one should not be doing insertions and deletions while
> iterating over a list. Iterators should not allow this, and positions
> should generally not be used for iteration.

Your delicate distinction between an 'iterator' and a 'position' is a little
silly. The reasons why it should not be done with iterators are the same as
the reasons why it should not be done with positions.

I have prepared a proposal, which I am e-mailing to Ted Dennison today for
posting on his web site (which he has kindly agreed to). It defines an
abstract list with a big set of operations. In it is an inner package which
defines an 'unbounded' list type, for which I hope to produce a sample
implementation (based on the classic double linkage model). Then I will add
a (generic) child package with a 'bounded' list type, for which I will
produce an implementation (based on a fixed-size array).

The indexed operations will, of course, be of O(1) for the bounded list, yet
being both based on the abstract list type, they will be algorithmically
interchangeable. So there is a deeper reason for my insistence on indexed
operations: I am trying to make a bigger plan 'come together'.

Finally, my proposal includes all the usual head and tail dicing operations.
Chopping off, or adding on, one item to either end of a list will be the
most frequently used operations anyway, for which arguments about indexing
don't apply. The indexed operations are mainly there for convenience. As I
showed in an example in another thread, really serious manipulations of
lists are best done sequentially.

I hope you will look at my proposal, and perhaps be a little more convinced!

--
Best wishes,
Nick Roberts

Re: List container: Insert and Delete

[Nick Roberts]

"Steven Deller" <deller@smsail.com> wrote in message
news:mailman.1005507140.5856.comp.lang.ada@ada.eu.org...
> ...
> I see no difficulty with iteration doing inserts and deletes, even with
> other simultaneous iterators.  It is a simple matter to define the
> semantics to be unambiguous, particularly if you use positions that are
> "in between" elements and semantics like:
>    delete following item
>    delete preceding item
>    get value of following item
>    get value of preceding item
>    move to next position (skip over an element)
>    move to previous position (skip backwards over an element)
>    goto head of list (position before first item)
>    goto tail of list (position after last item)
>    is at end of list (boolean)
>    is at beginning of list (boolean)
>
> These are all well defined, even for empty lists.

(a) I don't think they are really that well defined. (b) Implementing these
operations is complicated.

In more detail:

(a) What if I do "delete preceding item" twice? Does it delete two items
(the preceding one and the one before that)? [In which case, at what
position do I end up?]  Does it raise an exception (Item_Already_Deleted)?
[In which case, how do I delete backwards twice?] Does it just delete one
item (the second delete being effectively ignored)? One of these semantics
can be chosen, but I don't think it's obvious which. Poor confused user. On
the other hand, I think an operation such as "delete the third item" is
pretty obvious and unambiguous.

(b) For a list based on an array, the operation: "delete the third item" is
easy to implement, and fairly efficient for short lists; "insert before the
third item" is ditto; and "replace the third item" is both easy and
efficient (for any length of list). For a list based on a linked-list, the
implementations of these operations are easy, and pretty efficient for short
lists and for operations near to either end of the list.

So I think the design based on indexed positioning wins 'on points', as it
were.

--
Best wishes,
Nick Roberts

RE: List container: Insert and Delete

[Steven Deller]

> (a) What if I do "delete preceding item" twice? Does it
> delete two items (the preceding one and the one before that)? 
> [In which case, at what position do I end up?]  Does it raise 
> an exception (Item_Already_Deleted)? [In which case, how do I 
> delete backwards twice?] Does it just delete one item (the 
> second delete being effectively ignored)? One of these 
> semantics can be chosen, but I don't think it's obvious 
> which. Poor confused user. On the other hand, I think an 
> operation such as "delete the third item" is pretty obvious 
> and unambiguous.

That's a pretty hard stretch to suggest the semantics are confusing.
  H - 1 - 2 - 3 - T
            ^       position after 2, before 3
  Delete Preceding
  H - 1 - 3 - T
        ^           position after 1, before 3
  Delete Preceding
  H - 3 - T
    ^               position after H, before 3

The semantics are "obvious" as long as positions are "between" elements
and not "on" elements. 

Delete 3rd item is just as "confusing" (No, I don't think it is
confusing, just "as confusing" as you make out for position semantics).
Once I delete the 3rd item, what if I delete the 3rd again.  Does it
raise an exception (Item_Already_Deleted) [In which case, how do I
delete the next item?] ...

As I said, if you speak in terms of pointing "between" elements, the
semantics for position operations are straightforward for all
operations.

Personally, numbering items in a list seems inappropriate to me.  I've
always thought of associating "positional names" with elements as
something other than lists -- arrays perhaps :-).

If I do "insert item before item names '1'", do I get an item named '0'?
Or do the names of ALL other items in the list change?  Yuk.  I
fundamentally object to something that changes the "name" of EVERY other
list item.  That just seems to be ripe for erroneous use.

> (b) For a list based on an array, the operation: "delete the
> third item" is easy to implement, and fairly efficient for 
> short lists; "insert before the third item" is ditto; and 
> "replace the third item" is both easy and efficient (for any 
> length of list). For a list based on a linked-list, the 
> implementations of these operations are easy, and pretty 
> efficient for short lists and for operations near to either 
> end of the list.

Delete preceding and delete succeeding for position operations are easy
too.  As is insert before or insert after position.  

Trying to keep number references straight in "user code" for a list as
inserts/deletes happen would lead (easily) to application errors by less
expert users. Off-by-one errors are quite frequent in such situations.
 
> So I think the design based on indexed positioning wins 'on
> points', as it were.

Only when you are adding up the points :-).  I have seen both semantics,
and there are times I'd prefer one or the other.  But when I want
"names" for elements, I use arrays, in which I can't *delete* an item or
a name, only make it have a different value.  Names (numbers) are
constant for arrays once they are created.

The numbering approach also has the problem of "dynamic constraints" for
index numbers.  What happens if I reference List(13) when there are only
12 items in the list?

The "position" approach is able to provide "split list" into two parts
-- head and tail -- with little effort and with clear semantics (with a
"between items" pointer).

With numbers, the semantics of split list become consufing :-) -- does
"split list at 3rd item" leave the 3rd item in the head or the tail?
The semantics are not obvious and I do agree that users need "models"
from which semantics are obvious, not an arbitrary list of operational
semantics that have to be remembered each on its own.

Either approach is simple to implement in terms of the other. The
"numbering" semantics require O(N) time in the general case.  That, in
my mind, is the strongest argument against providing "numbering" of
lists.  Naïve users typically program as if primitive operations are
O(1) in time. 

So I think a design based on indexed positioning can lead to impractical
(or erroneous) applications from naïve users -- primitive operations
ought to be more "user proof".

Regards,
Steve

Re: List container: Insert and Delete

[Ted Dennison]

In article <9sn4qm$13g29j$2@ID-25716.news.dfncis.de>, Nick Roberts says...
>(b) For a list based on an array, the operation: "delete the third item" is
>easy to implement, and fairly efficient for short lists; "insert before the

Right now we are working on a defintion for *unbounded* lists, on the theory
that this is the most basic need. Bounded is for special cases. If you know a
good way to make an unbounded list using an array, you are a better man than I,
Gungha Din.

---
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 container strawman 1.2

[Martin Dowie]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:3BECA3B7.5020702@telepath.com...
[snip]
> --------------------------------------------------------------------------
-----
> -- This file contains a proposal for a standard Ada list package.
> --
> -- version - Strawman 1.2
> --------------------------------------------------------------------------
-----
> generic
>     type Element is private;
> package Containers.Lists.Unbounded is

Hmm, how about adding two lines to this to allow a list to be specified
as having 'unique' items or not? e.g.

generic
    type Element is private;
    Elements_Must_Be_Unique : Boolean;
    function "=" (L, R : Element) return Boolean;
package Containers.Lists.Unbounded is

I have found this to be very useful in the past - but this may
have just been the specifics of the problem domain I was working
in.

Re: List container strawman 1.2

[Nick Roberts]

"Martin Dowie" <martin.dowie@nospam.baesystems.com> wrote in message
news:3bef920f@pull.gecm.com...
> "Ted Dennison" <dennison@telepath.com> wrote in message
> news:3BECA3B7.5020702@telepath.com...
> [snip]
>
> --------------------------------------------------------------------------
> -----
> > -- This file contains a proposal for a standard Ada list package.
> > --
> > -- version - Strawman 1.2
>
> --------------------------------------------------------------------------
> -----
> > generic
> >     type Element is private;
> > package Containers.Lists.Unbounded is
>
> Hmm, how about adding two lines to this to allow a list to be specified
> as having 'unique' items or not? e.g.
>
> generic
>     type Element is private;
>     Elements_Must_Be_Unique : Boolean;
>     function "=" (L, R : Element) return Boolean;
> package Containers.Lists.Unbounded is
>
> I have found this to be very useful in the past - but this may
> have just been the specifics of the problem domain I was working
> in.

This is definitely a feature for content-addressed arrays (contars) rather
than lists. Having dealt with lists, we should move on to contars.

--
Best wishes,
Nick Roberts

Re: List container: Insert and Delete

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:Z0JH7.21323$xS6.32782@www.newsranger.com...
> In article <9sn4qm$13g29j$2@ID-25716.news.dfncis.de>, Nick Roberts says...
> >(b) For a list based on an array, the operation: "delete the third item"
is
> >easy to implement, and fairly efficient for short lists; "insert before
the
>
> Right now we are working on a defintion for *unbounded* lists, on the
theory
> that this is the most basic need. Bounded is for special cases. If you
know a
> good way to make an unbounded list using an array, you are a better man
than I,
> Gungha Din.

I have walked on water, shortly before turning it into wine*. I have fed the
five thousand. I've even occasionally remembered to do a spell check before
posting, but even I can't do that.

However, it would be nice to have an identical, interoperable, interface to
both kinds of list, no?

--
Best wishes,
Nick Roberts




*a robust dry claret, actually

Re: List container: Insert and Delete

[Nick Roberts]

I'm not qoting your reply, I'll just say I find it pretty persuasive. (And
very well argued.)

I have actually e-mailed my proposal based on indexed positioning; hopefully
Ted will put it up on the web site soon. Do have a look at it.

My most solidified idea regarding an alternative way of indicating positions
was based on 'markers' which marked items in the list (rather than being
notionally inserted inbetween two adjacent items). Is it really better to
have starkly inter-item positioning, or would it actually be better to say
that if item X is marked, "delete forward" means delete the item X, whereas
"delete backward" means delete the item preceding X? This would be analogous
to the way the cursor in most word processors deletes characters. The
procedures could be named to reflect this model, e.g.:

   procedure Delete_from_Marker (
      Marker: in out Unbounded_Marker;
      Count:  in     Natural := 1);

   procedure Delete_Before_Marker (
      Marker: in out Unbounded_Marker;
      Count:  in     Natural := 1);

The idea was to be able to set a marker to any item in a list. The marker
could then be advanced up or retired down the list. The item it marks can be
retrieved for inspection. The item at the marker can be deleted or replaced,
but ONLY if there are no other markers set on it. This means having a
counter in each node (but that's okay), but it does provide a rudimentary
form of locking (handy for some algorithms); a basic implementation would
raise an exception on breach of this locking, but a multi-tasking
alternative could perform a wait. Insert and append operations would need to
have versions that return a marker. There would need to be a few extra
operations (e.g. "copy marker").

These operations would be efficient for a linked-list implementation, but
not for a array-based one (for long lists). Again, that's okay (just not
ideal).

Do you like this idea? Shall I work up a new proposal based on this? Would
it be worth having both approaches (both index-based and marker-based)? (I
quite favour having both. Students should be taught to use the markers.)

--
Best wishes,
Nick Roberts

Re: List container: Insert and Delete

[Larry Kilgallen]

In article <9sok8j$142am0$3@ID-25716.news.dfncis.de>, "Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:
> I'm not qoting your reply, I'll just say I find it pretty persuasive. (And
> very well argued.)

Nor are you indicating whose reply it is that you find persuasive
so the rest of us can go look at it :-)

Re: List container strawman 1.2

[Marin David Condic]

Lots of ways of handling that. I agree that there are cases where you want a
list to contain only one sample of a given element, but I'd prefer that the
instantiation doesn't force someone to make that decision and have to
provide parameters that may be unnecessary for the simple cases. It could
just as easily be done by providing a subprogram to set a flag in the List
object that disallows/allows duplicates. Or alternately, returning a flag on
insertion indicating there was a duplicate or providing a function to test
for a duplicate, or .... ? IOW, default behavior is "duplicates allowed"
unless you call "Disallow_Duplicates (My_List_Object) ;" or something
similar.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Martin Dowie" <martin.dowie@nospam.baesystems.com> wrote in message
news:3bef920f@pull.gecm.com...
> "Ted Dennison" <dennison@telepath.com> wrote in message
> news:3BECA3B7.5020702@telepath.com...
> [snip]
>
> --------------------------------------------------------------------------
> -----
> > -- This file contains a proposal for a standard Ada list package.
> > --
> > -- version - Strawman 1.2
>
> --------------------------------------------------------------------------
> -----
> > generic
> >     type Element is private;
> > package Containers.Lists.Unbounded is
>
> Hmm, how about adding two lines to this to allow a list to be specified
> as having 'unique' items or not? e.g.
>
> generic
>     type Element is private;
>     Elements_Must_Be_Unique : Boolean;
>     function "=" (L, R : Element) return Boolean;
> package Containers.Lists.Unbounded is
>
> I have found this to be very useful in the past - but this may
> have just been the specifics of the problem domain I was working
> in.
>
>
>

Re: List container: Insert and Delete

[Marin David Condic]

I think the semantics become "This is what this particular package *does* do
and it is consistent across all similar containers." It doesn't have to be
mathematically rigorous to be useful. It doesn't have to have any one
specific behavior to be useful - provided that whatever behavior it has
allows you to get the job done in *some* manner and is not too horribly
inconvenient to do. The important thing is that it be USEFUL - not that it
satisfies perfect behavior in every case. If the user does something
hopelessly impossible, raise an exception. If the user does something
stupid, but consistent with the defined behavior - let him do it and move
on. You can't always save people from themselves.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Steven Deller" <deller@smsail.com> wrote in message
news:mailman.1005537083.14431.comp.lang.ada@ada.eu.org...

The semantics are "obvious" as long as positions are "between" elements
and not "on" elements.

Re: List container: Insert and Delete

[Jeffrey Carter]

Nick Roberts wrote:
> 
> Your delicate distinction between an 'iterator' and a 'position' is a little
> silly. The reasons why it should not be done with iterators are the same as
> the reasons why it should not be done with positions.

No, the idea that they are the same is a little silly. An iterator, by
definition, is something that iterates. A position within a list does
not iterate. If you can provide an example of a position iterating I
will change my position.

> The indexed operations will, of course, be of O(1) for the bounded list, yet
> being both based on the abstract list type, they will be algorithmically
> interchangeable. So there is a deeper reason for my insistence on indexed
> operations: I am trying to make a bigger plan 'come together'.

They will be O(N) in both versions, unless you make the extremely poor
implementation decision for the bounded version to implement insertions
and deletions by moving entire slices of the underlying array. I suspect
such an implementation will be universally considered unacceptable.
Making insertions and deletions O(N) so that indexing can be O(1) is a
poor choice, especially considering that both can be O(1).

The abstraction of a position should be the same for both bounded and
unbounded lists. The underlying implementation of a position for a
bounded list will be an index into the underlying array, but it is quite
likely that the component at index N of the array will not be the Nth
element in the list.

> Finally, my proposal includes all the usual head and tail dicing operations.
> Chopping off, or adding on, one item to either end of a list will be the
> most frequently used operations anyway, for which arguments about indexing
> don't apply. The indexed operations are mainly there for convenience. As I
> showed in an example in another thread, really serious manipulations of
> lists are best done sequentially.

There are no "usual" head and tail operations for a list. In decades of
using and implementing data structure libraries, TED's specification is
the first I've encountered that emphasizes dequeue- and string-like
operations.

The whole point of a list is that insertions and deletions are needed at
arbitrary positions. If you're only operating at the ends of the
sequence, then you want a dequeue, not a list, and you should not be
using a list.

> 
> I hope you will look at my proposal, and perhaps be a little more convinced!

I'll take a look.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Ted Dennison]

In article <9sok8i$142am0$2@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>"Ted Dennison" <dennison@telepath.com> wrote in message
>news:Z0JH7.21323$xS6.32782@www.newsranger.com...
>> Right now we are working on a defintion for *unbounded* lists, on the
>> theory that this is the most basic need. Bounded is for special cases. If you
>>
>However, it would be nice to have an identical, interoperable, interface to
>both kinds of list, no?

I've been thinking over that question myself, and right now I'm not sure what
the answer is. I can see two basic approaches here.

Approach one is, as you say, try to create 2 List packages with identical
interfaces, as near as possible. One would be "Bounded" and the other would be
"Unbounded". I'll call this the Stringslib choice, as this approach is inspired
by the approach taken by Ada.Strings.*. The other choice is to have separate
interfaces for bounded and unbounded Lists (in this case, probably "Vectors" and
"Lists" respectively) that are each designed around providing facilites that are
available and efficient for the implementation in question. I'll call that the
STL choice, as that's the way the STL did things.

I see two main advantages to the Stringslib approach. First, it is consistent
with the approach taken for the current Ada.Strings.* packages. That would
hopefully make it a more natural fit into the existing Ada library. Secondly,
there is only one interface to learn, so all the user has to worry about is the
trade-off between flexibility and dynamic memory use, and the relative speed of
typical operations in an array vs. heap environment.

However, the STL approach is attractive to me for several reasons. One is that
the design approach deals with abstractions rather than implementations. To me
that is generally a more sound approach. Another issue is that if we make some
kind of "Least Common Denominator" interface between the two implementations,
one of them is going to get short-changed. For instance, an array-based "Vector"
list could allow direct elment access via discrete type indices, just like an
array does. Why take that away, just because heap Lists can't do it?

But for the most part, I think we can delay resolving this partiular issue until
we are ready to deal with Bounded lists.

---
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 container strawman 1.2

[Jeffrey Carter]

Martin Dowie wrote:
> 
> Hmm, how about adding two lines to this to allow a list to be specified
> as having 'unique' items or not? e.g.

This is not a property of lists. While it may be useful in some cases to
have something list-like with this property, it should be a unique
structure, not something that affects every use of the basic list
component.

-- 
Jeffrey Carter

Re: List container strawman 1.2

[Jacob Sparre Andersen]

Ted: Dennison wrote:

> In article <3BED7AFD.737C2AE9@nbi.dk>, Jacob Sparre Andersen says...

> >Isn't that only if the "index" is external to the list type?
> 
> I'm not sure what you think the alternative would be. Perhaps each list gets one
> and only one active iterator, whose current value is somehow a facet of the list
> itself?

Something like that. Not necessarily only one though. That
would also help making sure that the iterator used actually
matches the list.

Jacob (who is a physicist, not a software engineer)
-- 
The great LEGO building competition of the year:
              http://www.1000steine.de/themen/bauwettbewerb/

Re: List container: Insert and Delete

[Ted Dennison]

In article <9sn4qk$13g29j$1@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>It's all very well saying access will be O(N), but that ignores the fact
>that chasing down a linked list of pointers is a fast operation (because

Not if there are 60000 of them to go through. What's worse is that you make
iterating through the entire list an O(N**2) operation, instead of O(N). This
effect compounds the time behavior for other operations the client might want to
do to. For example, if I were to try to use it to make my own custom sort
routine, which would normally be O(NlogN) average and O(N**2) worst case, using
an O(N) indexer changes it to O(N**2) average and O(N**3) worst case!

I wouldn't be horribly pained if some kind of "get me the n'th item" routine
were in there. But it *cannot* be the sole method for iteration in a
linked-list.

---
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 container strawman 1.2

[Ted Dennison]

In article <x7vpu6pq817.fsf@smaug.pushface.org>, Simon Wright says...
>
>This would be untrue in a (safety-related) environment where
>finalization was regarded as far too clever to be verifiable.

If finalization is too uncertian to be verifiable, would any heap operation at
all also be in the same boat?

---
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 container strawman 1.2

[Martin Dowie]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9soq34$be6$1@nh.pace.co.uk...
> Lots of ways of handling that. I agree that there are cases where you want
a
> list to contain only one sample of a given element, but I'd prefer that
the
> instantiation doesn't force someone to make that decision and have to
> provide parameters that may be unnecessary for the simple cases. It could
> just as easily be done by providing a subprogram to set a flag in the List
> object that disallows/allows duplicates. Or alternately, returning a flag
on
> insertion indicating there was a duplicate or providing a function to test
> for a duplicate, or .... ? IOW, default behavior is "duplicates allowed"
> unless you call "Disallow_Duplicates (My_List_Object) ;" or something
> similar.

Well, the biggest benefit we found with this method was that it allowed
the compiler to optimise away various paths on instantiation depending on
the
parameter passed. You could always have:

    Elements_Must_Be_Unique : Boolean := False;

The actual code difference between the two variants is very small and would
save having two package sources to maintain, which would have (almost)
exactly
the same specification.

Re: List container: Insert and Delete

[Jeffrey Carter]

Steven Deller wrote:
> 
> I don't understand this comment.  It seems to me that iteration to find
> some value and then insertion at that point is a normal list operation.

It is a common operation; however, the insertion (or deletion) occurs
after the iteration terminates; it is not done as part of iterating.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Jeffrey Carter]

Nick Roberts wrote:
> 
> (b) For a list based on an array, the operation: "delete the third item" is
> easy to implement, and fairly efficient for short lists; "insert before the
> third item" is ditto; and "replace the third item" is both easy and
> efficient (for any length of list). For a list based on a linked-list, the
> implementations of these operations are easy, and pretty efficient for short
> lists and for operations near to either end of the list.

For a bounded list (based on an array), deleting the third item is no
easier to implement than for an unbounded list, just as finding the Ith
item is O(N) for both types of list, unless a very poor implementation
is chosen for the bounded list.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Jeffrey Carter]

Nick Roberts wrote:
> 
> However, it would be nice to have an identical, interoperable, interface to
> both kinds of list, no?

A proper implementation of a bounded list has an identical interface to
that of an unbounded list (except for the concept of a full list).
Neither involves the client using positive integers to indicate
positions within a list.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Jeffrey Carter]

Nick Roberts wrote:
> 
> This would be analogous
> to the way the cursor in most word processors deletes characters.

Note that most word processors show the cursor between characters.

> These operations would be efficient for a linked-list implementation, but
> not for a array-based one (for long lists). Again, that's okay (just not
> ideal).

The time complexity of operations is identical for bounded and unbounded
lists. I suspect you have never seen a decent implementation of a
bounded list.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Ted Dennison]

In article <3BEFF9D6.607480D@boeing.com>, Jeffrey Carter says...
>They will be O(N) in both versions, unless you make the extremely poor
>implementation decision for the bounded version to implement insertions
>and deletions by moving entire slices of the underlying array. I suspect
>such an implementation will be universally considered unacceptable.
>Making insertions and deletions O(N) so that indexing can be O(1) is a
>poor choice, especially considering that both can be O(1).

If you make deletions O(N) in a bounded structure, that means you have to deal
with the possiblity of "holes" in your bounded storage area. I believe that
means that you will have to go searching for a empty hole in which to place new
nodes, which means that insertions are actually *not* O(1), even when done to
the end of the list! 

So there *are* trade-offs that have to be taken into consideration here. Just
implementing a STL-style "Vector" would actually be a big win for someone who
only wants a stack or a queue, or for someone who doesn't mind managing the
stuff in the middle themselves. Or we could implement a true unbounded list, but
not bother with internal links on the theory that middle insertions and
deletions are rare, and prominently documented to be O(N) for this data
strucutre. 


---
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 container strawman 1.2

[Ted Dennison]

In article <9soq34$be6$1@nh.pace.co.uk>, Marin David Condic says...
>
>Lots of ways of handling that. I agree that there are cases where you want a
>list to contain only one sample of a given element, but I'd prefer that the
>instantiation doesn't force someone to make that decision and have to
>provide parameters that may be unnecessary for the simple cases. It could

Agreed.

After a sort it should be pretty easy to identify (and then remove) dups. I'm
not sure if its a common enough need to merit its own routine. I suppose a
dup-removing sort could be introduced (as well as an Insert_Sorted_Unique that
raises an exception for a Dup, or somesuch). Perhaps after enough of these, we'd
have good material for Ehud's child package. :-)

---
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 container strawman 1.2

[Martin Dowie]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:NLTH7.21885$xS6.33661@www.newsranger.com...
> In article <9soq34$be6$1@nh.pace.co.uk>, Marin David Condic says...
> >
> >Lots of ways of handling that. I agree that there are cases where you
want a
> >list to contain only one sample of a given element, but I'd prefer that
the
> >instantiation doesn't force someone to make that decision and have to
> >provide parameters that may be unnecessary for the simple cases. It could
>
> Agreed.
>
> After a sort it should be pretty easy to identify (and then remove) dups.
I'm
> not sure if its a common enough need to merit its own routine. I suppose a
> dup-removing sort could be introduced (as well as an Insert_Sorted_Unique
that
> raises an exception for a Dup, or somesuch). Perhaps after enough of
these, we'd
> have good material for Ehud's child package. :-)

Why 'after a sort'? The point would be to not let anyone insert duplicates
in the first place!

Hmmm, a child package though... I'll have a think and see if there is a nice
why to do it like that.

It could just be the applications I've used list in (and I do like a list
;-)
but almost all I can think of do require no duplicates...

RE: List container strawman 1.2

[Steven Deller]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Marin 
> David Condic ]
> Sent: Monday, November 12, 2001 10:33 AM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: List container strawman 1.2
> 
> 
> Lots of ways of handling that. I agree that there are cases 
> where you want a list to contain only one sample of a given 
> element, but I'd prefer that the instantiation doesn't force 
> someone to make that decision and have to provide parameters 
> that may be unnecessary for the simple cases. It could just 
> as easily be done by providing a subprogram to set a flag in 
> the List object that disallows/allows duplicates. Or 
> alternately, returning a flag on insertion indicating there 
> was a duplicate or providing a function to test for a 
> duplicate, or .... ? IOW, default behavior is "duplicates 
> allowed" unless you call "Disallow_Duplicates 
> (My_List_Object) ;" or something similar.

In many "interesting" cases, duplicates are only defined over a subset
of the information in an element.  The approach suggested does not have
sufficient power to handle anything except "simple" duplication.  If
could also provide a generic "=" for the elements then perhaps it is
useful.

Also, these lists are NOT sorted, so non-duplication would require
searching the entire list for each insertion. As I said in previous
email, it is not good to have O(N) performance for primitive operations
on primitive structures.

Non-duplication insertion is better left to implementations intended for
sorted lists.  In which case, I'd expect "insert based on key" to be one
of the primitive operations.  And the user would NOT have the ability to
specify where in a list an insertion was going to be done.

Regards,
Steve

Re: List container strawman 1.2

[Marin David Condic]

I guess if your compiler is that smart, it could be a good thing. The flag
is probably not too bad a deal since it has a default. Defining equality is
of questionable value/pain since the element type was private - do you want
to force someone to define equality in every instance?

I don't know that this would be the best answer anyway. If you have a need
for unique and non-unique lists, then you've just duplicated the code
anyway, so you don't save anything on the optimization - and probably lose
more space along the way. If at some times you want your list object to be
unique and at other times non-unique (Say, if what you are storing in the
list is something the user may express a preference about) then you've got
to get two lists to work with.

Granted, maintaining a flag allows for the possibility that someone might be
having a Blonde Moment and switch the flag back and forth causing a required
unique list to have non-unique items (do you check this on state change?).
There's always something getting in the way.

An alternative might be to make a child of the basic list package that adds
the capability. (type Unique_List is new List with private....) I would just
favor making sure we have a nice simple basic list package without too many
dingleberries hanging off of it so it satisfies some large percentage of the
uses as simply and painlessly as possible. If there are interesting
variants, it seems better to include them as children or different branches.

Just my $0.02.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Martin Dowie" <martin.dowie@nospam.baesystems.com> wrote in message
news:3beffc62@pull.gecm.com...
>
> Well, the biggest benefit we found with this method was that it allowed
> the compiler to optimise away various paths on instantiation depending on
> the
> parameter passed. You could always have:
>
>     Elements_Must_Be_Unique : Boolean := False;
>
> The actual code difference between the two variants is very small and
would
> save having two package sources to maintain, which would have (almost)
> exactly
> the same specification.
>
>

Re: List container strawman 1.2

[Marin David Condic]

Maybe we shouldn't get to technical about it. If a feature is useful, does
it really matter that it doesn't satisfy some theoretical nicety? It is
probably more important to avoid making the basic list any more complicated
than it has to be - so we might be in agreement as to the end result. But I
wouldn't avoid the capability of eliminating/prohibiting duplicates
altogether if it was something that didn't cause the end user any additional
work for the basic case and didn't have any significant penalties in its
realization.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BEFFACC.4801D70D@boeing.com...
>
> This is not a property of lists. While it may be useful in some cases to
> have something list-like with this property, it should be a unique
> structure, not something that affects every use of the basic list
> component.

Re: List container: Insert and Delete

[Marin David Condic]

Well, a "full list" would have meaning for an unbounded list if you could no
longer allocate memory for it - Storage_Error. So if both handled it by way
of raising an exception or some test for sufficient memory, then either
could have a function "Is_Full (List)" or require handling of "exception
Overflow;".

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF004F4.F74AE461@boeing.com...
>
> A proper implementation of a bounded list has an identical interface to
> that of an unbounded list (except for the concept of a full list).
> Neither involves the client using positive integers to indicate
> positions within a list.
>

Re: List container: Insert and Delete

[Larry Kilgallen]

In article <9sp5up$g5o$1@nh.pace.co.uk>, "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:
> Well, a "full list" would have meaning for an unbounded list if you could no
> longer allocate memory for it - Storage_Error. So if both handled it by way
> of raising an exception or some test for sufficient memory, then either
> could have a function "Is_Full (List)" or require handling of "exception
> Overflow;".

Is_Full (List) is appropriate for some applications, but others
require How_Full (List).  While that is particularly meaningful
for Bounded lists, it should be present for Unbounded lists to
provide compatibility.

But do people expect a Bounded list implementation will allocate
a full list to the maximum size in all cases ?  If so, then the
Unbounded list implementation might have a meaningful How_Full (List)
answer related to the total address space available.

If one is managing multiple lists in the same address space,
learning How_Full is important for balancing resource usage
between the lists (in cases where the application can control
its appetites).

Re: List container strawman 1.2

[Ted Dennison]

In article <3bf013e4$1@pull.gecm.com>, Martin Dowie says...
>
>Why 'after a sort'? The point would be to not let anyone insert duplicates
>in the first place!

That could be done too. Its just particularly easy to do after a sort, as you
don't have to look through the entire list.

---
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: RE: List container strawman 1.2

[Ted Dennison]

In article <mailman.1005590546.670.comp.lang.ada@ada.eu.org>, Steven Deller
says...
>
>Non-duplication insertion is better left to implementations intended for
>sorted lists.  In which case, I'd expect "insert based on key" to be one
>of the primitive operations.  And the user would NOT have the ability to
>specify where in a list an insertion was going to be done.

Since that stuff (sorts and Keys) is a fairly natural thing for "maps", perhaps
it would go better there.

---
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 container strawman 1.2

[Ehud Lamm]

I vote YES for detailed comments, as in the code you posted...

Ehud

Re: List container: Insert and Delete

[Marin David Condic]

Not all functions need to be provided by the package. A caller knows how big
a list it asked for in the event of a Bounded List. It should be able to
determine from the package how many elements are on the list (bounded or
unbounded). How_Full is determined by current size and what you requested,
so (as a mathematician friend of mine was always fond of saying) A Solution
Does Exist.

A basic list package need not be all things to all users. If there is some
value in making a Bounded and an Unbounded package as similar as possible, I
think you could get *real* close to identical. However, even Ada.Strings.*
each have significant differences in the operations they provide, so as long
as there is a good deal of "orthogonality" and similarity between them, I
think we end up with a marketable product.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message
news:Gg93G3qLfuKE@eisner.encompasserve.org...
>
> Is_Full (List) is appropriate for some applications, but others
> require How_Full (List).  While that is particularly meaningful
> for Bounded lists, it should be present for Unbounded lists to
> provide compatibility.
>

Re: List container: Insert and Delete

[Darren New]

Larry Kilgallen wrote:
> But do people expect a Bounded list implementation will allocate
> a full list to the maximum size in all cases ?  If so, then the
> Unbounded list implementation might have a meaningful How_Full (List)
> answer related to the total address space available.
> 
> If one is managing multiple lists in the same address space,
> learning How_Full is important for balancing resource usage
> between the lists (in cases where the application can control
> its appetites).

I think we're rapidly moving away from the "newbie" version of the
lists. Suddenly you're getting into storage pool issues again, and etc.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container strawman 1.2

[Ted Dennison]

In article <3BF0247D.4500975E@san.rr.com>, Darren New says...
>
>This is a multi-part message in MIME format.
>--------------AC397429692108B025B90E25
>Content-Type: text/plain; charset=us-ascii
>Content-Transfer-Encoding: 7bit

I can't always read all parts of a MIME message w/ my regular newsreader. In
this case, your spec came through as garbage.


>>     No_Item : exception;
>>     function  Pop_Front  (Source : List) return List;
>>     function  Pop_Back   (Source : List) return List;
>
>I think calling it "Front" and "Back" here and "First" and "Last" later
>is going to be confusing.

Perhaps. But then First and Last make perfect sense in terms of iterating, and
make it clearer which way "Next" and "Previous" go, so I think the terminology
there is better. "Font" and "Back" are pretty standard terminology for list
ends, so from that standpoint they should stay too. What would you prefer to see
here?


>> >Inserting one list into another seems like overkill. If we're going to
>> 
>> It seemed that way to me too when suggested, but no one else said anything of
>> the sort, and its easy enough to code up. I'm still unconvinced that this is
>> something that folks would have to do a lot.
>
>I do it all the time in list-oriented languages. When you have a bunch
>of lists you want to merge into one, it's very handy. It makes no sense
>to leave it out, really, since it's not something you can easily code up
>yourself.

If all you want is to tack them together, the "&" functions do that just fine.
Do you actually need to merge lists by sticking one into a specific place in the
middle of the other all the time?

"next" should move the current value of a pointer, rather than returning
>the next pointer after this one, or you'll have a hard time keeping
>track of what "positions" might be valid.

No, its actually *no* tougher to keep track of valid positions either way. Even
with a limited position you have to worry about the possibility that one
position may go invalid due to operation on another position. (Or alternatively,
you don't worry about it in either case, which is what the current strawman
does). The data structures and methods for keeping track of this are the same as
they would be for non-limited positions. Making them procedures and/or limited
really buys you nothing, and prevents some very useful constructions for those
of us who like to do all the work we can in our declaration sections.

---
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 container strawman 1.2

[Darren New]

Ted Dennison wrote:

> I can't always read all parts of a MIME message w/ my regular newsreader. In
> this case, your spec came through as garbage.

Sorry. MIME's been around for longer than Ada95, so I figured everyone
could handle it. The plaintext version is pasted at the bottom, then.


> Perhaps. But then First and Last make perfect sense in terms of iterating, and
> make it clearer which way "Next" and "Previous" go, so I think the terminology
> there is better. "Font" and "Back" are pretty standard terminology for list
> ends, so from that standpoint they should stay too. What would you prefer to see
> here?

OK, well, is the front of the list the first element? If so, why do they
need different names? Just because there's two common terminologies,
that doesn't mean both should be used in the same library. :-) Pick
either "first" for the start of the list or "front" for the start of the
list, but not both. Especially not both with different signatures.

> >I do it all the time in list-oriented languages. When you have a bunch
> >of lists you want to merge into one, it's very handy. It makes no sense
> >to leave it out, really, since it's not something you can easily code up
> >yourself.
> 
> If all you want is to tack them together, the "&" functions do that just fine.
> Do you actually need to merge lists by sticking one into a specific place in the
> middle of the other all the time?

It's not uncommon, usually when the sub-lists being inserted "mean"
different things, like you're inserting the children of the directory
after the directory entry during a breadth-first walk, say. And "&" has
the overhead of copying both lists, as well. 

> Making them procedures and/or limited
> really buys you nothing, and prevents some very useful constructions for those
> of us who like to do all the work we can in our declaration sections.

OK, that makes sense. I'll grant that I'm not familiar enough with Ada
programming to call that one. :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container strawman 1.2

[Darren New]

Darren New wrote:
> 
> Ted Dennison wrote:
> 
> > I can't always read all parts of a MIME message w/ my regular newsreader. In
> > this case, your spec came through as garbage.
> 
> Sorry. MIME's been around for longer than Ada95, so I figured everyone
> could handle it. The plaintext version is pasted at the bottom, then.

Oops.

generic 
    type Element is private;
package AdaLists is

    type List is private;
    type Location is private;

    -- List construction, as already specified
    function "&" (Left, Right : Element) return List;
        -- O(1)
    function "&" (Left : Element; Right : List) return List;
        -- O(Size(Right))
    function "&" (Left : List; Right : Element) return List;
        -- O(Size(Left))
    function "&" (Left, Right : List) return List;
        -- O(Size(Left)+Size(Right))
    function "+" (Initial_Element : Element) return List;
        -- O(1)

    -- List access
    --   These should all be obvious, except for error cases.
    --   All of these raise No_Item if the specified item doesn't exist.
    --   I.e., front and back raise No_Item if Has_Item(L) is empty.
    --         Item raises No_Item if Size(L)<I.
    No_Item : exception;
    function Front(L : List) return Element; -- O(1)
    function Back(L : List) return Element; -- O(1)
    function Front(L : List) return Location; -- O(1)
    function Back(L : List) return Location; -- O(1)
    function Item(L : List; I : Positive) return Element; -- O(I)
    function Item(L : List; I : Positive) return Location; -- O(I)
    function Size(L : List) return Natural; -- O(1)
    function Has_Item(L : List) return Boolean; -- O(1)
        -- Same as Size(L)/=0
    function Has_Item(L : List; I : Positive) return Boolean; -- O(1)
        -- Same as I<=Size(L)
    function List_Of(L : Location) return List; -- O(1)
    function Index_Of(L : Location) return Positive; --
O(Size(List_Of(L))
        -- Raises No_Item if Has_Item(L)=False
        -- Item(List_Of(L),Index_Of(L))=Item(L)
    procedure Wipe(L : in out List); -- O(Size(L))
        -- Unlinks all links in List without affecting any elements
        -- After this, Size(L)=0
    procedure Copy(In_L : in List; Out_L : out List);
        -- Creates new list, puts copy of In_L into Out_L.

    -- Location manipulation
    function Has_Next(L : Location) return Boolean;
        -- Current location is not the last on the list and
        -- list is not empty. O(1)
    function Has_Previous(L : Location) return Boolean;
        -- Current location is not the first on the list and
        -- list is not empty. O(1)
    function Has_Item(L : Location) return Boolean;
        -- Current item has not been removed and list is not empty. O(1)
    procedure Next(L : in out Location);
        -- Raises No_Item if Has_Next(L) is false
        -- Ensures Has_Previous(L) is true if no exception
        -- May change Has_Next(L) and Has_Item(L)
        -- O(1)
    procedure Previous(L : in out Location);
        -- Raises No_Item if Has_Previous(L) is false
        -- Ensures Has_Next(L) if no exception thrown
        -- O(1)
    function Item(L : Location) return Element;
        -- Raises No_Item if Has_Item(L) is false
        -- O(1)

    -- List modification
    procedure Remove(L : in out Location);
        -- Raises No_Item if Has_Item(L) is false
        -- After this, Has_Item(L) will be false
        -- O(1)
    procedure Replace(L : in out Location; 
                Item : in Element);
        -- Does the obvious. Raises No_Item if Has_Item(L)=False
        -- O(1)

    procedure Insert_Before(L : in out Location;
                Item : in Element);
        -- Inserts copy of Item into list at location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) increases by one. 
        -- Works even on empty lists and even if not Has_Item(L)
        -- O(1)
    procedure Insert_After(L : in out Location;
                Item : in Element);
        -- Inserts a copy of Item into list after location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) remains the same, 
        --    but Size(List_Of(L)) increases.
        -- Works even on empty lists and even if not Has_Item(L)
        -- O(1)

    procedure Insert_Before(L : in out Location;
                Other : in out List);
        -- Inserts contents of Other into list at location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) increases by Size(Other). 
        -- Works even on empty lists and even if not Has_Item(L).
        -- After this, Size(Other)=0 -- Contents *moved*.
        -- O(1)
    procedure Insert_After(L : in out Location;
                Other : in out List);
        -- Inserts a copy of Item into list after location L.
        -- Item(L) is not changed by this call.
        -- That is, Index_Of(L) remains the same, 
        --    but Size(List_Of(L)) increases by Size(Other).
        -- Works even on empty lists and even if not Has_Item(L)
        -- After this, Size(Other)=0 -- Contents *moved*.
        -- O(1)

    generic
        with function "<"(Left, Right : in Element) return Boolean;
    procedure Sort(L : in out List);
    -- Old Size(L)=new Size(L), but all elements are sorted
    -- such that Item(L) < Item(Next(L)) for all locations.
    -- OK, do we want a stable sort? Probably. I'm not sure if
    -- we need "<=" or "=" or what.

    generic
        with function "<"(Left, Right : in Element) return Boolean;
    procedure Insert_Sorted(L : in out List; I : in Element);
    -- Inserts I into list L such that 

    -- I can also see a number of operations if "=" is defined
    -- for elements, such as "count the number of elements equal
    -- to this" or "give a Location where Item(L)=I" and such.

    -- Iterating would look something like this:
    -- Li : List; Lo : Location;
    -- Lo := Front(Li);
    -- while Has_Item(Lo) loop
    --   if Item(Lo) = George then
    --     Replace(Lo, Sally);
    --   end if;
    --   Next(Lo);
    -- end while;

private
    type Link;
    type Link_Access is access Link;
    type Link is record
        Next, Prev : Link_Access;
        Elem : Element;
    end record;

    type List is record
        Head, Tail : Link_Access;
        Size : Natural;
    end record;
    -- Size=0 -> head=null and tail=null
    -- Size=1 -> head=tail
    -- Size>1 -> head/=tail
    type List_Access is access List;

    type Location is record
        L : List_Access; -- What am I pointing into?
        Next, Prev : Link_Access; -- prev and next
        Curr : Link_Access; -- Do I have a current?
    end record;
    -- L.Size=0 -> next, prev, curr=nul
    -- Has_Item(this) -> Curr/=null
    -- Has_Next(this) -> Next/=null
    -- Has_Previous(this) -> Prev/=null

    -- It is possible by to add Invalid_Change to all Location
    -- operations that will catch using two locations into the 
    -- same list and modifying them in ways that they invalidate
    -- the other, but that's additional overhead we might not want.
    -- It consists of basically adding a "change counter" to each
    -- location and list, incrementing both with each change, and
    -- then revalidating each location that refers to a list whose
    -- change counter doesn't match, eliminating most of the 
    -- overhead for the normal case of only one location being
    -- manipulated at a time.
end AdaLists;


-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container: Insert and Delete

[Nick Roberts]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:D6TH7.21816$xS6.33411@www.newsranger.com...
> In article <9sn4qk$13g29j$1@ID-25716.news.dfncis.de>, Nick Roberts says...
> >
> >It's all very well saying access will be O(N), but that ignores the fact
> >that chasing down a linked list of pointers is a fast operation (because
>
> Not if there are 60000 of them to go through. What's worse is that you
make
> iterating through the entire list an O(N**2) operation, instead of O(N).
This
> effect compounds the time behavior for other operations the client might
want to
> do to. For example, if I were to try to use it to make my own custom sort
> routine, which would normally be O(NlogN) average and O(N**2) worst case,
using
> an O(N) indexer changes it to O(N**2) average and O(N**3) worst case!
>
> I wouldn't be horribly pained if some kind of "get me the n'th item"
routine
> were in there. But it *cannot* be the sole method for iteration in a
> linked-list.

Okay, I'm convinced. I'm in the process of rewriting my proposal with a
comprehensive set of 'cursor' operations (in addition to the index-based
ones, which are relegated to deprecated relative to the cursor operations).

I'll e-mail this to you (Ted) maybe Wednesday (probably very busy tomorrow).
I'll also produce an implementation as quick as I can (despite the large
number of operations).

Thanks in advance for your forebearance.

--
Best wishes,
Nick Roberts

Re: List container: Insert and Delete

[Nick Roberts]

"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BEFF9D6.607480D@boeing.com...
> Nick Roberts wrote:
> >
> > Your delicate distinction between an 'iterator' and a 'position' is a
little
> > silly. The reasons why it should not be done with iterators are the same
as
> > the reasons why it should not be done with positions.
>
> No, the idea that they are the same is a little silly. An iterator, by
> definition, is something that iterates. A position within a list does
> not iterate. If you can provide an example of a position iterating I
> will change my position.

I knew I'd get a rocketing for that one! You are, of course, quite right.

> > The indexed operations will, of course, be of O(1) for the bounded list,
yet
> > being both based on the abstract list type, they will be algorithmically
> > interchangeable. So there is a deeper reason for my insistence on
indexed
> > operations: I am trying to make a bigger plan 'come together'.
>
> They will be O(N) in both versions, unless you make the extremely poor
> implementation decision for the bounded version to implement insertions
> and deletions by moving entire slices of the underlying array. I suspect
> such an implementation will be universally considered unacceptable.
> Making insertions and deletions O(N) so that indexing can be O(1) is a
> poor choice, especially considering that both can be O(1).

I will investigate the possibilities for the implementation of the bounded
version. As Ted Dennison intimates somewhere (in answer to this post?), I
think an indexed implementation is an interesting idea, but it's performance
under various conditions is likely to be a complex matter.

> > Finally, my proposal includes all the usual head and tail dicing
operations.
> > Chopping off, or adding on, one item to either end of a list will be the
> > most frequently used operations anyway, for which arguments about
indexing
> > don't apply. The indexed operations are mainly there for convenience. As
I
> > showed in an example in another thread, really serious manipulations of
> > lists are best done sequentially.
>
> There are no "usual" head and tail operations for a list. In decades of
> using and implementing data structure libraries, TED's specification is
> the first I've encountered that emphasizes dequeue- and string-like
> operations.

There are in functional languages such as LISP. I think they'll be handy for
lists sometimes, and are not difficult to implement.

> The whole point of a list is that insertions and deletions are needed at
> arbitrary positions. If you're only operating at the ends of the
> sequence, then you want a dequeue, not a list, and you should not be
> using a list.

Okay, I agree, and I'm writing a new proposal that has a complete set of
'cursor' operations that do just what (I assume) your position-based
strategy intended. Hope to get this to Ted (for his web site) soon (maybe
2-3 days).

> > I hope you will look at my proposal, and perhaps be a little more
convinced!
>
> I'll take a look.

My thanks, Jeff, for your patience!

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Nick Roberts]

"Jacob Sparre Andersen" <sparre@nbi.dk> wrote in message
news:3BEFFCAE.DCB5D136@nbi.dk...
> Ted: Dennison wrote:
>
> > In article <3BED7AFD.737C2AE9@nbi.dk>, Jacob Sparre Andersen says...
>
> > >Isn't that only if the "index" is external to the list type?
> >
> > I'm not sure what you think the alternative would be. Perhaps each list
gets one
> > and only one active iterator, whose current value is somehow a facet of
the list
> > itself?
>
> Something like that. Not necessarily only one though. That
> would also help making sure that the iterator used actually
> matches the list.

This is what my new proposal is based on: a 'cursor' (only one) is built
into each list object. This approach solves all the problems of
implementational inefficiency, extra memory use, and safety issues.

I assume most algorithms would only need one cursor. Are there going to be
occasions when more than one cursor (at a time) might be needed?

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Nick Roberts]

I agree with not getting too purist about what properties lists do or don't
classically have. However, I think I agree with Jeffrey on this one.

After dealing with lists, I intend to propose one or two content-addressed
array (contar) packages. The essence of a contar is that it has a specific
index or key type as well as a specific data type. I suppose a contar is a
kind of mapping (in alternative nomenclature).

The 'key' point (sorry ;-) is that the index or key type is assumed to be
ordered. This immediately opens the door to such things as sorting and
duplicate denial.

So, I suggest that these things are left to contars, and not loaded onto
lists (and my proposed list is already gravid with concepts and operations).

--
Best wishes,
Nick Roberts





"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9sp5kr$fvm$1@nh.pace.co.uk...
> Maybe we shouldn't get to technical about it. If a feature is useful, does
> it really matter that it doesn't satisfy some theoretical nicety? It is
> probably more important to avoid making the basic list any more
complicated
> than it has to be - so we might be in agreement as to the end result. But
I
> wouldn't avoid the capability of eliminating/prohibiting duplicates
> altogether if it was something that didn't cause the end user any
additional
> work for the basic case and didn't have any significant penalties in its
> realization.

> "Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
> news:3BEFFACC.4801D70D@boeing.com...
> >
> > This is not a property of lists. While it may be useful in some cases to
> > have something list-like with this property, it should be a unique
> > structure, not something that affects every use of the basic list
> > component.

Re: List container: Insert and Delete

[Nick Roberts]

Sorry! I meant Steve Deller. But I also include Jeff Carter in convincing
me.

--
Best wishes,
Nick Roberts



"Larry Kilgallen" <Kilgallen@SpamCop.net> wrote in message
news:KDcdjrT740Z9@eisner.encompasserve.org...
> In article <9sok8j$142am0$3@ID-25716.news.dfncis.de>, "Nick Roberts"
<nickroberts@adaos.worldonline.co.uk> writes:
> > I'm not qoting your reply, I'll just say I find it pretty persuasive.
(And
> > very well argued.)
>
> Nor are you indicating whose reply it is that you find persuasive
> so the rest of us can go look at it :-)

Re: List container: Insert and Delete

[Nick Roberts]

Excellent. I'm calling a marker a 'cursor'. I've already decided I'm going
for the 'inbetween items' model (it's very neat). By having just one cursor
built in to each list object, I think I solve all the problems of
inefficiency, memory greed, and safety (in one fell stroke!). Getting my
proposal to you ASAP. Might multiple (simlutaneous) cursors be required
sometimes?

I'm a happy bunny now :-)

--
Best wishes,
Nick Roberts



"Jeffrey Carter" <jeffrey.carter@boeing.com> wrote in message
news:3BF00692.3CFED98C@boeing.com...
> Nick Roberts wrote:
> >
> > This would be analogous
> > to the way the cursor in most word processors deletes characters.
>
> Note that most word processors show the cursor between characters.
>
> > These operations would be efficient for a linked-list implementation,
but
> > not for a array-based one (for long lists). Again, that's okay (just not
> > ideal).
>
> The time complexity of operations is identical for bounded and unbounded
> lists. I suspect you have never seen a decent implementation of a
> bounded list.

Re: List container: Insert and Delete

[Darren New]

Nick Roberts wrote:
> proposal to you ASAP. Might multiple (simlutaneous) cursors be required
> sometimes?

Sure. Removing duplicates. Any place where you have
for I in 1..Last loop
  for J in I..Last loop
    .... A(I,J) ...

you're going to need multiple cursors.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container: Insert and Delete

[Jeffrey Carter]

Marin David Condic wrote:
> 
> Well, a "full list" would have meaning for an unbounded list if you could no
> longer allocate memory for it - Storage_Error. So if both handled it by way
> of raising an exception or some test for sufficient memory, then either
> could have a function "Is_Full (List)" or require handling of "exception
> Overflow;".

The difference, of course, is that you can provide an Is_Full function
for a bounded list, but not for an unbounded list. In both cases an
exception should be raised if an attempt is made to add an element when
that is not possible.

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail

Re: List container: Insert and Delete

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BEFF9D6.607480D@boeing.com>, Jeffrey Carter says...
> >They will be O(N) in both versions, unless you make the extremely poor
> >implementation decision for the bounded version to implement insertions
> >and deletions by moving entire slices of the underlying array. I suspect
> >such an implementation will be universally considered unacceptable.
> >Making insertions and deletions O(N) so that indexing can be O(1) is a
> >poor choice, especially considering that both can be O(1).
> 
> If you make deletions O(N) in a bounded structure, that means you have to deal
> with the possiblity of "holes" in your bounded storage area. I believe that
> means that you will have to go searching for a empty hole in which to place new
> nodes, which means that insertions are actually *not* O(1), even when done to
> the end of the list!

I'm not sure what you're saying here; perhaps that initial "O(N)" should
be O(1)? Actually, for a bounded list you have 2 lists in the same
array: the real list and a free list. Because of the free list, there is
no searching for a hole. Insertions and deletions are O(1) for all
positions.

I think I have a skeleton for a bounded list somewhere. If I can get 2
votes for posting the basics of the implementation I'll dig it out (or
make it up again) and post it.

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail

Re: List container strawman 1.2

[Simon Wright]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

>          Defining equality is of questionable value/pain since the
> element type was private - do you want to force someone to define
> equality in every instance?

I have a user who definitely did want this (for example, what if the
key were a case-insensitive string?)

  with function "=" (L, R : Key) return Boolean is <>;

It does mean that equality has to be visible at the point of
instantiation, of course.

Slightly concerned about having over-simplified components (training
wheels); if the purpose is purely for teaching that's OK but look at
Pascal.

Re: List container strawman 1.2

[Simon Wright]

Ted Dennison<dennison@telepath.com> writes:

> In article <x7vpu6pq817.fsf@smaug.pushface.org>, Simon Wright says...
> >
> >This would be untrue in a (safety-related) environment where
> >finalization was regarded as far too clever to be verifiable.
> 
> If finalization is too uncertian to be verifiable, would any heap
> operation at all also be in the same boat?

I believe so (SPARK 95 _may_ eventually allow heap operation, but I
don't think it does now. I'm not an expert).

The point isn't that it's uncertain, rather that in that sort of
environment you need to be able to _prove_ things and the state of the
art in proof technology limits what features of the language can be
permitted.

Re: List container: Insert and Delete

[Simon Wright]

Kilgallen@SpamCop.net (Larry Kilgallen) writes:

> Is_Full (List) is appropriate for some applications, but others
> require How_Full (List).  While that is particularly meaningful
> for Bounded lists, it should be present for Unbounded lists to
> provide compatibility.
> 
> But do people expect a Bounded list implementation will allocate
> a full list to the maximum size in all cases ?  If so, then the
> Unbounded list implementation might have a meaningful How_Full (List)
> answer related to the total address space available.
> 
> If one is managing multiple lists in the same address space,
> learning How_Full is important for balancing resource usage
> between the lists (in cases where the application can control
> its appetites).

The BCs return Natural'Last to the question "how many slots are
available in this unbounded container?".

I dunno, no one expects Ada.Text_IO to have special functionality to
help you with managing your disk space!

Re: List container: Insert and Delete

[Ted Dennison]

In article <9spt1i$14snic$2@ID-25716.news.dfncis.de>, Nick Roberts says...
>I'll e-mail this to you (Ted) maybe Wednesday (probably very busy tomorrow).
>I'll also produce an implementation as quick as I can (despite the large
>number of operations).

OK. I'll hold off posting what you sent me until then, if you don't mind.
Tonight's my volleyball night, so I probably wouldn't get to it until Wednesday
anyway. :-)

---
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 container: Insert and Delete

[Marin David Condic]

O.K., but just to be tricky - suppose you pre-allocate a node that is to be
used for the next insertion. When an insertion is done, you use that node
and attempt to allocate another one. If it fails, the list is full.

That probably wouldn't work for all cases such as discriminated or tagged
records, where you can't allocate until you know what you want to store, but
it is a trick that might be useful in some contexts.

Basically, I agree - an unbounded list wouldn't likely have or need an
Is_Full function. If you wanted one for consistency, it could always return
False. But I see no need that a Bounded package and an Unbounded package
have to be plug compatible. You very seldom would want to unplug the one and
plug in the other - you take the decision at the time of design and use the
package that makes most sense then. Swapping implementations after that
would mean some serious regression testing of the software, so you could
probably modify it for any incompatibilities along the way and not be that
bad off.

I think it was Mark Twain who said something about "A foolish consistency is
the product of little minds." :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3BF0827A.DCF2213C@acm.org...
>
> The difference, of course, is that you can provide an Is_Full function
> for a bounded list, but not for an unbounded list. In both cases an
> exception should be raised if an attempt is made to add an element when
> that is not possible.
>

RE: List container: Insert and Delete

[Steven Deller]

> The difference, of course, is that you can provide an Is_Full 
> function for a bounded list, but not for an unbounded list. 
> In both cases an exception should be raised if an attempt is 
> made to add an element when that is not possible.

Which is why I believe there should ONLY be a "how full" function.

The user can always compare "how full" to "how big I made it in the
first place" to find out if it is full.

I do agree about both raising an exception if an element cannot be
added.  That should be an "exceptional event".

Regards,
Steve Deller
Smooth Sailing LLC
deller@smsail.com

Re: List container: Insert and Delete

[Ted Dennison]

In article <3BF08501.50C83D22@acm.org>, Jeffrey Carter says...
>
>I'm not sure what you're saying here; perhaps that initial "O(N)" should
>be O(1)? Actually, for a bounded list you have 2 lists in the same
>array: the real list and a free list. Because of the free list, there is
>no searching for a hole. Insertions and deletions are O(1) for all
>positions.

Ahhh. I'd fogotten that you can make a list of the free stuff. That's right, it
is O(1).

---
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 container: Insert and Delete

[Ted Dennison]

In article <9sra40$b8p$1@nh.pace.co.uk>, Marin David Condic says...
>
>False. But I see no need that a Bounded package and an Unbounded package
>have to be plug compatible. You very seldom would want to unplug the one and

I'd agree with this. The only compelling reason I could see for it would be if
we were using some kind of root tagged type to implement both (which we aren't),
and wanted to allow for dynamic dispatching on classwide list pointers.

I'm curious what people think about the extent of the compatability they should
have though. Should the look mostly alike, except for routines that don't make
sense in that context? Should we remove all basic-looking routines from either
implementation with time behavior >=O(N). Should the interface for bounded be
completely redesigned around things that you can do with bounded implementations
that you can't easily do with unbounded ones?

Personally, I think I'm leaning towards the middle-of-the road option, but its
not a strong leaning.


>plug in the other - you take the decision at the time of design and use the
>package that makes most sense then. Swapping implementations after that
>would mean some serious regression testing of the software, so you could
>probably modify it for any incompatibilities along the way and not be that
>bad off.
>
>I think it was Mark Twain who said something about "A foolish consistency is
>the product of little minds." :-)
>
>MDC
>--
>Marin David Condic
>Senior Software Engineer
>Pace Micro Technology Americas    www.pacemicro.com
>Enabling the digital revolution
>e-Mail:    marin.condic@pacemicro.com
>Web:      http://www.mcondic.com/
>
>
>"Jeffrey Carter" <jrcarter@acm.org> wrote in message
>news:3BF0827A.DCF2213C@acm.org...
>>
>> The difference, of course, is that you can provide an Is_Full function
>> for a bounded list, but not for an unbounded list. In both cases an
>> exception should be raised if an attempt is made to add an element when
>> that is not possible.
>>
>
>
>

---
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 container strawman 1.2

[Ted Dennison]

In article <9spt1k$14snic$4@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>I assume most algorithms would only need one cursor. Are there going to be
>occasions when more than one cursor (at a time) might be needed?

How about our cannonical custom sort routine?

I often find dealing with lists that I'm going through the list *two* elements
at a time (usually one element, and the one immediately before or after it).
There may be ways for dealing with that though. I'll look at your proposal
before I make up my mind about it.

---
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 container strawman 1.2

[Ted Dennison]

In article <9spt1k$14snic$5@ID-25716.news.dfncis.de>, Nick Roberts says...
>After dealing with lists, I intend to propose one or two content-addressed
>array (contar) packages. The essence of a contar is that it has a specific
>index or key type as well as a specific data type. I suppose a contar is a
>kind of mapping (in alternative nomenclature).

Sounds like a "Map" to me, which certianly is the next subject on the agenda.

---
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 container: Insert and Delete

[Marin David Condic]

If you had an abstract tagged list type that defined behavior common to
*all* lists (unbounded, bounded, unsorted, sorted, etc,) you could just add
the operations that make sense for the particular type of list. I don't know
that it has to be a tagged type - just create different packages that have
somewhat different features where it makes sense.

I'd take a cue from Ada.Strings.* since this is the "flavor" of things in
Ada. The packages are similar, but not identical. Operations exist only if
they make sense for the particular type of string and are not always
identical since different types of strings need different parameters to
operations. If you think about it, Strings are not all that different from
Lists, so to whatever extent we can get orthogonality between the two
package sets, the more familiar they will appear to be to your average Ada
programmer.

(You can change the names so you won't have
ASCL.Lists.Unbounded.Unbounded_List if you like :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:5DaI7.23016$xS6.35866@www.newsranger.com...
>
> I'd agree with this. The only compelling reason I could see for it would
be if
> we were using some kind of root tagged type to implement both (which we
aren't),
> and wanted to allow for dynamic dispatching on classwide list pointers.
>
> I'm curious what people think about the extent of the compatability they
should
> have though. Should the look mostly alike, except for routines that don't
make
> sense in that context? Should we remove all basic-looking routines from
either
> implementation with time behavior >=O(N). Should the interface for bounded
be
> completely redesigned around things that you can do with bounded
implementations
> that you can't easily do with unbounded ones?
>
> Personally, I think I'm leaning towards the middle-of-the road option, but
its
> not a strong leaning.
>

Re: List container: Insert and Delete

[John English]

Ted Dennison wrote:
> 
> In article <9sn4qm$13g29j$2@ID-25716.news.dfncis.de>, Nick Roberts says...
> >(b) For a list based on an array, the operation: "delete the third item" is
> >easy to implement, and fairly efficient for short lists; "insert before the
> 
> Right now we are working on a defintion for *unbounded* lists, on the theory
> that this is the most basic need. Bounded is for special cases. If you know a
> good way to make an unbounded list using an array, you are a better man than I,
> Gungha Din.

Sigh. Perhaps a "list" of shortcomings of existing list packages would
be better than yet another reinvention of this particular wheel. For
example, what's wrong with Booch lists, or for that matter the ones in
my book (http://www.it.bton.ac.uk/staff/je/adacraft/ch12.htm#12.1 and
http://www.it.bton.ac.uk/staff/je/adacraft/appd.htm#d.8), or any of
the many other implementations floating around already?

Otherwise, it seems to me we'll end up with "just another list package"
which will be supported by some and decried by others...

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.2

[Ted Dennison]

In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> there is better. "Font" and "Back" are pretty standard terminology for list

Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't they?

>OK, well, is the front of the list the first element? If so, why do they

That's actually a very good question. It isn't an array, so you can't tell from
that. The way the list is designed, I can use it as a queue or as a stack from
either end and it will work just fine either way. 

The iterator, on the other hand, has a different job to perform. In its world,
all it has to do is pick a side, and then go the other way until the end. So
there it makes more sense to talk about "First" and "Last". 

However, you have to pick a side, and it would be useful to know how to relate
the two. So you are right that this *is* a bit confusing, because somewhere you
have to realise that "First"="Head". But renaming "Head" to "First" won't remove
the confusion, because that term has no real meaning in the universe of Push'es
and Pop's.

So how do we get out of this. The best ways that I can see are either:

o  Make sure the iterator routines are well commented as to which 
directions in the "Head/Tail" world they operate.
o  Rename the iterator routines to match the other routines. 
Unfortunately, this would reqire "Next" and "Previous" to become
something like "Next_Toward_Tail" and "Next_Toward_Head". The
passive iterator would still have to be commented as to which 
direction it goes. I suppose a From_Head/From_Tail flag could be 
used instead. That might be useful anyway...

I think the second option is quite doable, if that's what people really want.

>It's not uncommon, usually when the sub-lists being inserted "mean"
>different things, like you're inserting the children of the directory
>after the directory entry during a breadth-first walk, say. And "&" has

So what you are saying is that there is a hetrogenious structure to your list
that isn't reflected in the structure of the list itself, but in the contents of
the elements in the list (and thus has to be parsed back out)? You could
accomplish this goal without the extra parsing (and without the middle insertion
routine) by using lists of lists, could you not? 

You are right about the level-of-effort vs. the append routines, though.

---
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 container strawman 1.2

[Ted Dennison]

In article <3BF05337.75BE0A18@san.rr.com>, Darren New says...
>
>Darren New wrote:
>    function "&" (Left, Right : Element) return List;
>        -- O(1)

I much prefer pre-comments to post-comments. The reason is that you read them
before you get to the source, rather than after you have already tried to read
the source and are perhaps already confused and/or misled. Forewarned is
forearmed. :-)

However, the bit about specifying the time behavior for the routines is a good
point.


>    function "&" (Left : Element; Right : List) return List;
>        -- O(Size(Right))
>    function "&" (Left : List; Right : Element) return List;
>        -- O(Size(Left))
>    function "&" (Left, Right : List) return List;
>        -- O(Size(Left)+Size(Right))
>    function "+" (Initial_Element : Element) return List;
>        -- O(1)
>
>    -- List access
>    --   These should all be obvious, except for error cases.
>    --   All of these raise No_Item if the specified item doesn't exist.
>    --   I.e., front and back raise No_Item if Has_Item(L) is empty.
>    --         Item raises No_Item if Size(L)<I.
>    No_Item : exception;
>    function Front(L : List) return Element; -- O(1)
>    function Back(L : List) return Element; -- O(1)
>    function Front(L : List) return Location; -- O(1)
>    function Back(L : List) return Location; -- O(1)
>    function Item(L : List; I : Positive) return Element; -- O(I)
>    function Item(L : List; I : Positive) return Location; -- O(I)
>    function Size(L : List) return Natural; -- O(1)
>    function Has_Item(L : List) return Boolean; -- O(1)
>        -- Same as Size(L)/=0
>    function Has_Item(L : List; I : Positive) return Boolean; -- O(1)
>        -- Same as I<=Size(L)
>    function List_Of(L : Location) return List; -- O(1)
>    function Index_Of(L : Location) return Positive; --
>O(Size(List_Of(L))
>        -- Raises No_Item if Has_Item(L)=False
>        -- Item(List_Of(L),Index_Of(L))=Item(L)
>    procedure Wipe(L : in out List); -- O(Size(L))
>        -- Unlinks all links in List without affecting any elements
>        -- After this, Size(L)=0
>    procedure Copy(In_L : in List; Out_L : out List);
>        -- Creates new list, puts copy of In_L into Out_L.
>
>    -- Location manipulation
>    function Has_Next(L : Location) return Boolean;
>        -- Current location is not the last on the list and
>        -- list is not empty. O(1)
>    function Has_Previous(L : Location) return Boolean;
>        -- Current location is not the first on the list and
>        -- list is not empty. O(1)
>    function Has_Item(L : Location) return Boolean;
>        -- Current item has not been removed and list is not empty. O(1)
>    procedure Next(L : in out Location);
>        -- Raises No_Item if Has_Next(L) is false
>        -- Ensures Has_Previous(L) is true if no exception
>        -- May change Has_Next(L) and Has_Item(L)
>        -- O(1)
>    procedure Previous(L : in out Location);
>        -- Raises No_Item if Has_Previous(L) is false
>        -- Ensures Has_Next(L) if no exception thrown
>        -- O(1)
>    function Item(L : Location) return Element;
>        -- Raises No_Item if Has_Item(L) is false
>        -- O(1)
>
>    -- List modification
>    procedure Remove(L : in out Location);
>        -- Raises No_Item if Has_Item(L) is false
>        -- After this, Has_Item(L) will be false
>        -- O(1)
>    procedure Replace(L : in out Location; 
>                Item : in Element);
>        -- Does the obvious. Raises No_Item if Has_Item(L)=False
>        -- O(1)
>
>    procedure Insert_Before(L : in out Location;
>                Item : in Element);
>        -- Inserts copy of Item into list at location L.
>        -- Item(L) is not changed by this call.
>        -- That is, Index_Of(L) increases by one. 
>        -- Works even on empty lists and even if not Has_Item(L)
>        -- O(1)
>    procedure Insert_After(L : in out Location;
>                Item : in Element);
>        -- Inserts a copy of Item into list after location L.
>        -- Item(L) is not changed by this call.
>        -- That is, Index_Of(L) remains the same, 
>        --    but Size(List_Of(L)) increases.
>        -- Works even on empty lists and even if not Has_Item(L)
>        -- O(1)
>
>    procedure Insert_Before(L : in out Location;
>                Other : in out List);
>        -- Inserts contents of Other into list at location L.
>        -- Item(L) is not changed by this call.
>        -- That is, Index_Of(L) increases by Size(Other). 
>        -- Works even on empty lists and even if not Has_Item(L).
>        -- After this, Size(Other)=0 -- Contents *moved*.
>        -- O(1)
>    procedure Insert_After(L : in out Location;
>                Other : in out List);
>        -- Inserts a copy of Item into list after location L.
>        -- Item(L) is not changed by this call.
>        -- That is, Index_Of(L) remains the same, 
>        --    but Size(List_Of(L)) increases by Size(Other).
>        -- Works even on empty lists and even if not Has_Item(L)
>        -- After this, Size(Other)=0 -- Contents *moved*.
>        -- O(1)
>
>    generic
>        with function "<"(Left, Right : in Element) return Boolean;
>    procedure Sort(L : in out List);
>    -- Old Size(L)=new Size(L), but all elements are sorted
>    -- such that Item(L) < Item(Next(L)) for all locations.
>    -- OK, do we want a stable sort? Probably. I'm not sure if
>    -- we need "<=" or "=" or what.
>
>    generic
>        with function "<"(Left, Right : in Element) return Boolean;
>    procedure Insert_Sorted(L : in out List; I : in Element);
>    -- Inserts I into list L such that 
>
>    -- I can also see a number of operations if "=" is defined
>    -- for elements, such as "count the number of elements equal
>    -- to this" or "give a Location where Item(L)=I" and such.
>
>    -- Iterating would look something like this:
>    -- Li : List; Lo : Location;
>    -- Lo := Front(Li);
>    -- while Has_Item(Lo) loop
>    --   if Item(Lo) = George then
>    --     Replace(Lo, Sally);
>    --   end if;
>    --   Next(Lo);
>    -- end while;
>
>private
>    type Link;
>    type Link_Access is access Link;
>    type Link is record
>        Next, Prev : Link_Access;
>        Elem : Element;
>    end record;
>
>    type List is record
>        Head, Tail : Link_Access;
>        Size : Natural;
>    end record;
>    -- Size=0 -> head=null and tail=null
>    -- Size=1 -> head=tail
>    -- Size>1 -> head/=tail
>    type List_Access is access List;
>
>    type Location is record
>        L : List_Access; -- What am I pointing into?
>        Next, Prev : Link_Access; -- prev and next
>        Curr : Link_Access; -- Do I have a current?
>    end record;
>    -- L.Size=0 -> next, prev, curr=nul
>    -- Has_Item(this) -> Curr/=null
>    -- Has_Next(this) -> Next/=null
>    -- Has_Previous(this) -> Prev/=null
>
>    -- It is possible by to add Invalid_Change to all Location
>    -- operations that will catch using two locations into the 
>    -- same list and modifying them in ways that they invalidate
>    -- the other, but that's additional overhead we might not want.
>    -- It consists of basically adding a "change counter" to each
>    -- location and list, incrementing both with each change, and
>    -- then revalidating each location that refers to a list whose
>    -- change counter doesn't match, eliminating most of the 
>    -- overhead for the normal case of only one location being
>    -- manipulated at a time.
>end AdaLists;
>
>
>-- 
>Darren New 
>San Diego, CA, USA (PST). Cryptokeys on demand.
>   You will soon read a generic fortune cookie.

---
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 container: Insert and Delete

[John English]

Nick Roberts wrote:
> ... Might multiple (simlutaneous) cursors be required
> sometimes?

Yes. Consider checking for palindromic lists, for example.

> I'm a happy bunny now :-)

Sorry... :-)

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <9sra40$b8p$1@nh.pace.co.uk>, Marin David Condic says...
> >
> But I see no need that a Bounded package and an Unbounded package
> >have to be plug compatible. You very seldom would want to unplug the one and
> 
> I'd agree with this. The only compelling reason I could see for it would be if
> we were using some kind of root tagged type to implement both (which we aren't),
> and wanted to allow for dynamic dispatching on classwide list pointers.
> 
> I'm curious what people think about the extent of the compatability they should
> have though. Should the look mostly alike, except for routines that don't make
> sense in that context? Should we remove all basic-looking routines from either
> implementation with time behavior >=O(N). Should the interface for bounded be
> completely redesigned around things that you can do with bounded implementations
> that you can't easily do with unbounded ones?

I've never actually encountered a situation that needed a bounded list,
so I really can't comment (not that I'll let that stop me). I have
encountered situations that needed a bounded queue, however. I have
sometimes used an unbounded queue for a quick test of functionality, and
then converted to an unbounded queue, since the packages I use have
identical interfaces except for the Is_Full function and the
Full/Storage_Exhausted exceptions.

However, all data structures are abstractions with specific interfaces,
and a specific implementation still needs to provide that interface. For
a list, there are basic operations to obtain positions within the list
and to insert, delete, and update at a specific position; these are
independent of the implementation.

For a list, the only basic operation that is O(N) in time is usually
Length; it is of course possible to make Length O(1) by keeping a count,
but that doesn't seem to be necessary. I would want every operation to
have its time complexity and pre- and post-conditions (where applicable)
clearly documented.

-- 
Jeffrey Carter

Re: List container strawman 1.2

[Martin Dowie]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:dibI7.23087$xS6.35921@www.newsranger.com...
> In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
> >
> >Ted Dennison wrote:
> >> there is better. "Font" and "Back" are pretty standard terminology for
list
>
> Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't
they?

I don't know if it is a "ML" thing (Brian?) but a list of a tail
used to be the list that was left (possibly empty) after the head
was removed and not an element within a list.

Re: List container strawman 1.2

[Darren New]

Ted Dennison wrote:
> 
> In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
> >
> >Ted Dennison wrote:
> >> there is better. "Font" and "Back" are pretty standard terminology for list
> 
> Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't they?

I'm less worried about "usual" than "consistancy". For example, in the
Java libraries, they have things like "insert" for lists, "put" for
vectors, "add" for maps, and such. And it's virtually impossible to keep
straight which is which. If I want to get the first element and I have
to call "First", but a pointer to the first element is "Head", then it's
going to be check-the-docs time every time I use it. 

This is what I liked about the Eiffel libraries. (The ISE version, I
mean.) Adding an item is *always* Put. The element to be added is always
the first argument (well, modulo distinguished-selector syntax). The
current element is always "item". Clearing out the data structure is
always "prune". It doesn't matter what structure it is. It doesn't
matter if you've never even seen that structure before.

> That's actually a very good question. It isn't an array, so you can't tell from
> that. The way the list is designed, I can use it as a queue or as a stack from
> either end and it will work just fine either way.
> 
> The iterator, on the other hand, has a different job to perform. In its world,
> all it has to do is pick a side, and then go the other way until the end. So
> there it makes more sense to talk about "First" and "Last".
> 
> However, you have to pick a side, and it would be useful to know how to relate
> the two. So you are right that this *is* a bit confusing, because somewhere you
> have to realise that "First"="Head". But renaming "Head" to "First" won't remove
> the confusion, because that term has no real meaning in the universe of Push'es
> and Pop's.

type direction is (towards_first, towards_last);
procedure next(L : in out Location; dir : in direction := towards_last);
-- Or however you want to declare the procedure/function/whatever.

No problem. Same thing that the string routines do.

> So how do we get out of this. The best ways that I can see are either:
> 
> o  Make sure the iterator routines are well commented as to which
> directions in the "Head/Tail" world they operate.

Make it a choice on each operation. Symmetry and orthoganality is what
makes a library easy to learn and use.

> o  Rename the iterator routines to match the other routines.
> Unfortunately, this would reqire "Next" and "Previous" to become
> something like "Next_Toward_Tail" and "Next_Toward_Head". The
> passive iterator would still have to be commented as to which
> direction it goes. I suppose a From_Head/From_Tail flag could be
> used instead. That might be useful anyway...

Yes. Especially if you have a sorted list and you want to go in
different directions.
 
> I think the second option is quite doable, if that's what people really want.
> 
> >It's not uncommon, usually when the sub-lists being inserted "mean"
> >different things, like you're inserting the children of the directory
> >after the directory entry during a breadth-first walk, say. And "&" has
> 
> So what you are saying is that there is a hetrogenious structure to your list
> that isn't reflected in the structure of the list itself, but in the contents of
> the elements in the list (and thus has to be parsed back out)?

Basically.

> You could
> accomplish this goal without the extra parsing (and without the middle insertion
> routine) by using lists of lists, could you not?

Except that each element of the list would have to be *either* a file
name *or* a directory name, for example. Just as much work to deal with
either way.

The point is that any time you flatten a tree into a list inorder,
you're going to want to have an operation to insert an entire list into
the middle of another list. Heirarchical data bases, databases of chess
moves, generating HTML, parsing MIME, etc.

Anyway, the places I do such things tend to be very weakly typed
languages. I've not done anything large enough to need that in Ada yet.
 
> You are right about the level-of-effort vs. the append routines, though.

Yeah. :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container: Insert and Delete

[Darren New]

Ted Dennison wrote:
> Should we remove all basic-looking routines from either
> implementation with time behavior >=O(N).

Definitely not. All that will do is force people to recreate the
functionality they need anyway, except without the benefit of being able
to access the internal structures.

For example, I strongly suggest that there be a mechanism to translate
between positions and integer offsets and back. This is an O(N)
operation, obviously, compared to the O(1) of moving the position.
However, if someone has a list that they want to stuff out to a file,
along with an offset (say, the one currently on the screen), they need a
way to handle that. Denying the ability to translate between positions
and integers just means that someone's going to write code full of
things like
  offset := offset + 1;
  pos := Next(pos);

Indeed, Tcl for many many years had O(N) access to arrays (called
"lists" there, the maps being called arrays), and it wasn't really a
problem. If you had a 1000 element list, it was still quick enough. If
you had a really large list, you did it some other way if the
performance was too bad. So don't leave out functionality just because
it's hard to do *efficiently*. O(2**N) is still darn fast if N is 10 or
the multiplier is in microseconds.

Basically, the library has to be useful for small programs too, or
you've (a) missed the point and (b) done little to help promote Ada. The
languages that are great for million-line beasts and excrutiating for
100-line programs never really get very popular outside their niches.

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container: Insert and Delete

[Pascal Obry]

"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> writes:

> Excellent. I'm calling a marker a 'cursor'. I've already decided I'm going
> for the 'inbetween items' model (it's very neat). By having just one cursor
> built in to each list object, I think I solve all the problems of
> inefficiency, memory greed, and safety (in one fell stroke!). Getting my
> proposal to you ASAP. 

We often say in CLA that others are reinventing the wheel ! For sure others
have already designed something like that. Here is a cut-and-paste from EPFL
containers library (which I found very good BTW), and here others are Ada
guys...

<<
generic
  type Item_Type is private;
  with function Equals (Left,Right: Item_Type) return Boolean;

package List_Of_Static_Items_G is
---------------------------------
--+ OVERVIEW:
--+   This package provides lists of unlimited dynamic size with elements
--+ of type Item_TYPE, where Item_TYPE is specified by a generic parameter.
--+ The type List_TYPE is implemented in such a way that every object has
--+ the implied initial value of an empty list.
--+
--+ A list appears like this:
--+
--+              element          element          element
--+                ____             ____             ____      
--+               |    |           |    |           |    |      
--+        o------|    |-----o-----|    |-----o-----|    |------o
--+               |____|           |____|           |____|       
--+      front               ^                                 rear
--+                          |
--+                <----  cursor  ---->
--+            previous              next
--+
--+   Possible points of interest (indexes) are located at the start of the
--+ list (front), at its end (rear) or on two moving cursors. Indexes never
--+ directly reference elements. They only reference inter-element locations
--+ (insertion points). Elements are referenced by specifying an index and
--+ a related direction (next or previous).
--+ In an empty list, the front and the rear collapse into a single location
--+ which is simultaneously the only valid cursor position. Every list is
--+ initially empty, with its cursors located on this position.
--+ The front and the rear also collapse when considering the list as circular.
--+ This can be done by setting the Circular parameter in the appropriate
--+ operations.
--+
--+
--+ PRIMITIVES :
--+     CURSOR CONSTRUCTORS :
--+             Set_Cursor
--+             Set_Cursor_At_Front
--+             Set_Cursor_At_Rear
--+             Move_Cursor_TO_Next
--+             Move_Cursor_TO Previous
--+             Find_And_Set_Cursor (2)
--+             Find_And_Set_Cursor_G
--+             Find_And_Set_Cursor_With_Exception_G
--+     CURSOR QUERIES :
--+             Cursor_Position (2)
--+             IS_Cursor_At_Front
--+             IS_Cursor_At_Rear
--+     LIST CONSTRUCTORS :
--+             Assign
--+             Construct
--+             Copy
--+             Set
--+             Modify
--+             Insert
--+             Remove (2)
--+             Swap
--+             Move (2)
--+             Move_G
--+     LIST QUERIES :
--+             Size
--+             Is_Empty
--+             Number
--+             Is_Present
--+             Get
--+             =
--+             Are_Identical
--+     LIST ITERATORS :
--+             Traverse_G
--+             Traverse_Modify_G
--+     HEAP MANAGEMENT :
--+    		Destroy
--+     	Release_Free_List
--+     	Set_Max_Free_List_Size
--+     	Free_List_Size
--+
>>

They have also Queue, Stack, Table.

Pascal.

-- 

--|------------------------------------------------------
--| Pascal Obry                           Team-Ada Member
--| 45, rue Gabriel Peri - 78114 Magny Les Hameaux FRANCE
--|------------------------------------------------------
--|         http://perso.wanadoo.fr/pascal.obry
--|
--| "The best way to travel is by means of imagination"

Re: List container strawman 1.2

[Ted Dennison]

In article <3bf14919$1@pull.gecm.com>, Martin Dowie says...
>
>"Ted Dennison" <dennison@telepath.com> wrote in message
>news:dibI7.23087$xS6.35921@www.newsranger.com...
>> In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
>> >
>> >Ted Dennison wrote:
>> >> there is better. "Font" and "Back" are pretty standard terminology for
>list
>>
>> Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't
>they?
>
>I don't know if it is a "ML" thing (Brian?) but a list of a tail
>used to be the list that was left (possibly empty) after the head
>was removed and not an element within a list.

It occured to me over lunch that this list type is actually missing exactly
those routines (CDR and its tail-oriented equivalent) if we were to truly make
it usable in the Lisp style. So perhaps Front and Back should stay as is, First
and Last should also become Front and Back, and Head and Tail should be new
functions returning the *rest* of the list minus Back and Front respectively?

---
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 container strawman 1.2

[Stephen Leake]

"Martin Dowie" <martin.dowie@nospam.baesystems.com> writes:

> "Ted Dennison" <dennison@telepath.com> wrote in message
> news:3BECA3B7.5020702@telepath.com...
> [snip]
> > --------------------------------------------------------------------------
> -----
> > -- This file contains a proposal for a standard Ada list package.
> > --
> > -- version - Strawman 1.2
> > --------------------------------------------------------------------------
> -----
> > generic
> >     type Element is private;
> > package Containers.Lists.Unbounded is
> 
> Hmm, how about adding two lines to this to allow a list to be specified
> as having 'unique' items or not? e.g.
> 
> generic
>     type Element is private;
>     Elements_Must_Be_Unique : Boolean;
>     function "=" (L, R : Element) return Boolean;
> package Containers.Lists.Unbounded is
> 
> I have found this to be very useful in the past - but this may
> have just been the specifics of the problem domain I was working
> in.

Actually, I prefer three choices for "duplicates"; ignore, error, and
allow.

I use "ignore" when I'm accumulating lists of Ada packages to "with"
(in an ASIS application); each package is on the list only once.

I use "error" when the program logic forbids duplicates; lists of
people, for example.

I use "allow" in other situations, usually when "compare" actually
makes no sense (a list of GUI controls).

This feature is not yet in my on-line version of SAL; I have not been
keeping it up to date.

-- 
-- Stephe

Re: List container strawman 1.2

[Stephen Leake]

"Steven Deller" <deller@smsail.com> writes:

> Also, these lists are NOT sorted, so non-duplication would require
> searching the entire list for each insertion. As I said in previous
> email, it is not good to have O(N) performance for primitive operations
> on primitive structures.
> 
> Non-duplication insertion is better left to implementations intended for
> sorted lists.  In which case, I'd expect "insert based on key" to be one
> of the primitive operations.  And the user would NOT have the ability to
> specify where in a list an insertion was going to be done.

Agreed. I should have mentioned in my other post: SAL only supports
"ignore, error, allow" for duplicates in sorted binary trees, not in
lists. 

-- 
-- Stephe

Re: List container strawman 1.2

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <3BF05337.75BE0A18@san.rr.com>, Darren New says...
> >
> >Darren New wrote:
> >    function "&" (Left, Right : Element) return List;
> >        -- O(1)
> 
> I much prefer pre-comments to post-comments. The reason is that you read them
> before you get to the source, rather than after you have already tried to read
> the source and are perhaps already confused and/or misled. Forewarned is
> forearmed. :-)

Well, I prefer to read the Ada source first, to get as much
information as possible, then read the comments. If you put the
comments first, and they are at all long, you start having to repeat
parts of the Ada code (like the function and parameter names) at the
top of the comment; a very bad idea.

-- 
-- Stephe

RE: List container: Insert and Delete

[Steven Deller]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Darren New
> Sent: Tuesday, November 13, 2001 12:47 PM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: List container: Insert and Delete
> 
> 
> Ted Dennison wrote:
> > Should we remove all basic-looking routines from either 
> implementation 
> > with time behavior >=O(N).
> 
> Definitely not. All that will do is force people to recreate 
> the functionality they need anyway, except without the 
> benefit of being able to access the internal structures.
> 
> For example, I strongly suggest that there be a mechanism to 
> translate between positions and integer offsets and back. 
> This is an O(N) operation, obviously, compared to the O(1) of 
> moving the position. However, if someone has a list that they 
> want to stuff out to a file, along with an offset (say, the 
> one currently on the screen), they need a way to handle that. 
> Denying the ability to translate between positions and 
> integers just means that someone's going to write code full 
> of things like
>   offset := offset + 1;
>   pos := Next(pos);

I wouldn't object to a function
   subtype position_index is natural ;
   head_position : constant position_index := 0 ;
   function offset (pos) return position_index ;
that returns the current index.

Done right, this index can be maintained as part of "pos", even in the
face of insertions, and deletions.  All in O(1) time.

I do object to making a List into a Map (and a Map limited to a
particular index type at that).

Please don't add array indexing to lists.

Regards,
Steve Deller
Smooth Sailing LLC

Re: List container: Insert and Delete

[Darren New]

Steven Deller wrote:
> 
> > -----Original Message-----
> > From: comp.lang.ada-admin@ada.eu.org
> > [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of Darren New
> > Sent: Tuesday, November 13, 2001 12:47 PM
> > To: comp.lang.ada@ada.eu.org
> > Subject: Re: List container: Insert and Delete
> >
> >
> > Ted Dennison wrote:
> > > Should we remove all basic-looking routines from either
> > implementation
> > > with time behavior >=O(N).
> >
> > Definitely not. All that will do is force people to recreate
> > the functionality they need anyway, except without the
> > benefit of being able to access the internal structures.
> >
> > For example, I strongly suggest that there be a mechanism to
> > translate between positions and integer offsets and back.
> > This is an O(N) operation, obviously, compared to the O(1) of
> > moving the position. However, if someone has a list that they
> > want to stuff out to a file, along with an offset (say, the
> > one currently on the screen), they need a way to handle that.
> > Denying the ability to translate between positions and
> > integers just means that someone's going to write code full
> > of things like
> >   offset := offset + 1;
> >   pos := Next(pos);
> 
> I wouldn't object to a function
>    subtype position_index is natural ;
>    head_position : constant position_index := 0 ;
>    function offset (pos) return position_index ;
> that returns the current index.
> 
> Done right, this index can be maintained as part of "pos", even in the
> face of insertions, and deletions.  All in O(1) time.

Good point.
 
> I do object to making a List into a Map (and a Map limited to a
> particular index type at that).
> 
> Please don't add array indexing to lists.

Then you need some way to map a "pos" onto something you can save, and
something to map it back. For example, if you're implementing Streams,
you'll need something like this anyway, yes?

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container strawman 1.2

[Marin David Condic]

"Gag me with a sandwich!"
    --  Momma Cass

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:UaeI7.23281$xS6.36587@www.newsranger.com...
> it usable in the Lisp style. So perhaps Front and Back should stay as is,
First
> and Last should also become Front and Back, and Head and Tail should be
new
> functions returning the *rest* of the list minus Back and Front
respectively?
>

Re: List container: Insert and Delete

[Ted Dennison]

In article <3BF14752.B3F3FBC@boeing.com>, Jeffrey Carter says...
>
>I've never actually encountered a situation that needed a bounded list,
>so I really can't comment (not that I'll let that stop me). I have
>encountered situations that needed a bounded queue, however. I have

That's precisely my experience, which is what makes me wonder if it really needs
to be a full O(1)-insert list. Every time I've needed a bounded list, I've ended
up writing a circular queue.

>For a list, the only basic operation that is O(N) in time is usually
>Length; it is of course possible to make Length O(1) by keeping a count,
>but that doesn't seem to be necessary. I would want every operation to
>have its time complexity and pre- and post-conditions (where applicable)
>clearly documented.

I think a lot of us are suffering under a bit of a terminology disconnect here.
I'm used to thinking of "lists" as bascily any linearly linked structure. In a
way, that means it is the union of queues, stacks, and any other nifty concept
that you can come up with using a lineraly linked-list. Thus using our "List"
type, you ought to be able to simulate any of those other aforementioned
structures. But they are all types of lists, and saying a stack isn't a list is
as confusing to me as saying a penny isn't a coin.

Some people however appear to think of "List"s as a specific type of structure
with specific implementations and algorithms. I'm sure somewhere there's a
language or even perhaps a whole software engineering discipline that uses that
definition for lack of a better name (good terms for different types of lists
must be awfully hard to come by once you get a good half a dozen or more of
them).

On the off chance that I'm just way obsolete in my knowledge (My last algorithms
course was 5 whole years ago. It could happen.), I went on a web hunt to see if
I could find any general source of computing knowledge that uses List in the
latter way rather than the former. I came up blank. I did find a few supporting
the former though:

http://hissa.nist.gov/dads/HTML/list.html (Dictionary of Algorithms, Data
Structures, and Problems at NIST)

http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=list&action=Search (Foldoc,
which is always my authoratitive source, but it is user-submitted...)

There were also numerous online Data Structures texts that used "Lists" as a
heading, with stuff like "Singly Linked Lists" and "Doubly Linked Lists" as
subheadings.

Anyway, the strawman was presented with the impression that the goal was to
create a simple basic "List" type from which Queues, stacks, and the like can be
implemented by the user. Acutal implementations of course have to be hashed out,
but I don't believe it was anyone's intention to specify a particular
implementation by choosing the word "List". Just the opposite, in fact.

---
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 container: Insert and Delete

[Ted Dennison]

In article <3BF15C70.B7EF23E6@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> Should we remove all basic-looking routines from either
>> implementation with time behavior >=O(N).
>
>Definitely not. All that will do is force people to recreate the
>functionality they need anyway, except without the benefit of being able
>to access the internal structures.
>
>For example, I strongly suggest that there be a mechanism to translate
>between positions and integer offsets and back. This is an O(N)
>operation, obviously, compared to the O(1) of moving the position.

You had me, before you presented this 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 container: Insert and Delete

[Marin David Condic]

If its any consolation, I have always heard and used the term "Lists" pretty
much as you have. Stacks, Queues, Single/Double, etc, were always special
cases of a "List". I would consider Trees (binary and otherwise) and Maps
outside of this set, but inside some general set called "Linked Data
Structures" or "Containers".

I'd really hate to have us get hung up on terminology and formalism. I think
if we get something that is generally useful - out of which you can get the
functionality of a stack or queue or whatever - then for *practical* usage,
we've got what we want. If an operation doesn't fit some formal definition,
but is useful and easily implemented, then fine. If soneone isn't going to
be happy about using the term "List" unless it fits some definition, then
lets call them "Gazorenthorpes" and move on. The important thing is having a
data structure of some sort that will exhibit the most common and useful
behavior in real-world programming situations.

Out of all the linked data structures I've ever heard about, the only two
that I've ever used with any frequency are Lists and Maps. (The minute you
get into trees of any sort, they start becoming so specialized to the
application that they always seemed to me to be something that would be
difficult to generalize & still be useful. Better to build them as you need
them...)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:aYeI7.23350$xS6.36692@www.newsranger.com...
>
> That's precisely my experience, which is what makes me wonder if it really
needs
> to be a full O(1)-insert list. Every time I've needed a bounded list, I've
ended
> up writing a circular queue.
>
> >For a list, the only basic operation that is O(N) in time is usually
> >Length; it is of course possible to make Length O(1) by keeping a count,
> >but that doesn't seem to be necessary. I would want every operation to
> >have its time complexity and pre- and post-conditions (where applicable)
> >clearly documented.
>
> I think a lot of us are suffering under a bit of a terminology disconnect
here.
> I'm used to thinking of "lists" as bascily any linearly linked structure.
In a
> way, that means it is the union of queues, stacks, and any other nifty
concept
> that you can come up with using a lineraly linked-list. Thus using our
"List"
> type, you ought to be able to simulate any of those other aforementioned
> structures. But they are all types of lists, and saying a stack isn't a
list is
> as confusing to me as saying a penny isn't a coin.
>
> Some people however appear to think of "List"s as a specific type of
structure
> with specific implementations and algorithms. I'm sure somewhere there's a
> language or even perhaps a whole software engineering discipline that uses
that
> definition for lack of a better name (good terms for different types of
lists
> must be awfully hard to come by once you get a good half a dozen or more
of
> them).
>
> On the off chance that I'm just way obsolete in my knowledge (My last
algorithms
> course was 5 whole years ago. It could happen.), I went on a web hunt to
see if
> I could find any general source of computing knowledge that uses List in
the
> latter way rather than the former. I came up blank. I did find a few
supporting
> the former though:
>
> http://hissa.nist.gov/dads/HTML/list.html (Dictionary of Algorithms, Data
> Structures, and Problems at NIST)
>
> http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=list&action=Search
(Foldoc,
> which is always my authoratitive source, but it is user-submitted...)
>
> There were also numerous online Data Structures texts that used "Lists" as
a
> heading, with stuff like "Singly Linked Lists" and "Doubly Linked Lists"
as
> subheadings.
>
> Anyway, the strawman was presented with the impression that the goal was
to
> create a simple basic "List" type from which Queues, stacks, and the like
can be
> implemented by the user. Acutal implementations of course have to be
hashed out,
> but I don't believe it was anyone's intention to specify a particular
> implementation by choosing the word "List". Just the opposite, in fact.
>
> ---
> 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 container: Insert and Delete

[Ted Dennison]

In article <3BF140D9.611DE43@brighton.ac.uk>, John English says...
>example, what's wrong with Booch lists, or for that matter the ones in

I think the problem there was that they were considered (particularly by some of
your fellow educators) too tough to figure out how to use.

>Otherwise, it seems to me we'll end up with "just another list package"
>which will be supported by some and decried by others...

I have to say, that's my fear as well. I was hoping we might be able to come up
with some kind of compromise simple list package that everyone can (at least
grudgingly) sign onto. I'll keep plugging at it while I think there's still
hope. If the strawmen only succeed in showing that Booch and friends really
aren't all that bad, or that the task simply isn't possible, then it at least
has been worthwhile for 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 container: Insert and Delete

[Ehud Lamm]

John English <je@brighton.ac.uk> wrote in message
news:3BF140D9.611DE43@brighton.ac.uk...
> Sigh. Perhaps a "list" of shortcomings of existing list packages would
> be better than yet another reinvention of this particular wheel. For
> example, what's wrong with Booch lists, or for that matter the ones in
> my book (http://www.it.bton.ac.uk/staff/je/adacraft/ch12.htm#12.1 and
> http://www.it.bton.ac.uk/staff/je/adacraft/appd.htm#d.8), or any of
> the many other implementations floating around already?
>

I agree with this sentiment. So why not take the lead and tell us why you
didn't use the BC in your book...?

Ehud

Re: List container strawman 1.2

[Ted Dennison]

In article <9srt4e$j46$1@nh.pace.co.uk>, Marin David Condic says...
>
>"Gag me with a sandwich!"

:-)

I'll take that as a note of disagreement...

---
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 container: Insert and Delete

[Ted Dennison]

In article <3BF17705.637A8B6E@san.rr.com>, Darren New says...
>
>Then you need some way to map a "pos" onto something you can save, and
>something to map it back. For example, if you're implementing Streams,
>you'll need something like this anyway, yes?

If you are implementing them for positions, which we currently are not (check
the spec). That could just be an oversight, though.

---
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 container: Insert and Delete

[Ted Dennison]

In article <3BF140D9.611DE43@brighton.ac.uk>, John English says...
>
>Sigh. Perhaps a "list" of shortcomings of existing list packages would
>be better than yet another reinvention of this particular wheel. For
>example, what's wrong with Booch lists, or for that matter the ones in
>my book (http://www.it.bton.ac.uk/staff/je/adacraft/ch12.htm#12.1 and
>http://www.it.bton.ac.uk/staff/je/adacraft/appd.htm#d.8), or any of
>the many other implementations floating around already?

To answer the other half of your question, the list implementation in your book
appears to be a proper subset of the Strawman. So the answer to your question is
really in this thread, where I was asked to add (or justify adding) all that
extra stuff. :-)

My guess is that your implementation was designed for instructional use, while
Booch was degined for industrial use. The general idea of this process is that
somewhere in between is perhaps a "sweet spot" that can be mostly acceptable for
both uses.

---
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 container strawman 1.2

[Marin David Condic]

Fair enough. If we went down the path of doing essentially CAR/CDR to please
the Lisp folks, the Unix guys would come out of the woodwork and want you to
impliment Head and Tail operations that would give you the first/last N
elements. And then the Eiffel guys would be there wanting pre/post
conditions and before you know it, the moon is turning blood red, lions are
having sex with sheep, the Seventh Angel breaks the Seventh Seal, a toy
company makes a tank that folds out into a rain forest and pretty much the
world as we know it comes to a screeching halt. I really hate it when that
happens. :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:cIfI7.23431$xS6.37207@www.newsranger.com...
>
> I'll take that as a note of disagreement...
>

Re: List container: Insert and Delete

[Ted Dennison]

In article <9srv70$k0k$1@nh.pace.co.uk>, Marin David Condic says...
>Out of all the linked data structures I've ever heard about, the only two
>that I've ever used with any frequency are Lists and Maps. (The minute you

Same here, but mostly lists.

>get into trees of any sort, they start becoming so specialized to the
>application that they always seemed to me to be something that would be
>difficult to generalize & still be useful. Better to build them as you need
>them...)

I agree here. However, I should note that one would probably want to implement a
general map as some kind of tree.

---
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 container strawman 1.2

[Marin David Condic]

I think the original example omitted the "is <>" part. It makes a
difference.

Things should be made as simple as possible - but no simpler? :-)

My fear is that opening the door to more generic parameters to control
behavior and other options is going to get everyone lining up with their
favorite generic option. If at all possible, I'd prefer to keep the
instantiations simple and control options via some kind of initialization of
the list object.

But that's just my preference.....

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Simon Wright" <simon@pushface.org> wrote in message
news:x7vpu6nxhp1.fsf@smaug.pushface.org...
>
> I have a user who definitely did want this (for example, what if the
> key were a case-insensitive string?)
>
>   with function "=" (L, R : Key) return Boolean is <>;
>
> It does mean that equality has to be visible at the point of
> instantiation, of course.

Re: List container: Insert and Delete

[Darren New]

Ted Dennison wrote:
> >For example, I strongly suggest that there be a mechanism to translate
> >between positions and integer offsets and back. This is an O(N)
> >operation, obviously, compared to the O(1) of moving the position.
> 
> You had me, before you presented this example. :-)

I don't follow. What's unreasonable about the example? It seems like a
perfectly reasonable way of saying "does this come before that in the
list", or saving positions to a stream, or printing something out for
debugging, or whatever.

Saying "we're not going to implement this operation because it's
inefficient" doesn't sound like a good idea to me, is all.

> >Then you need some way to map a "pos" onto something you can save, and
> >something to map it back. For example, if you're implementing Streams,
> >you'll need something like this anyway, yes?

> If you are implementing them for positions, which we currently are not (check
> the spec). That could just be an oversight, though.

Someone will want to save positions. There's three choices: implement
positions for streams, provide ways to convert to something simpler
(like Integer), or force the person who wants that to keep track of the
integer as well as the position or to implement the run-through-the-list
somehow (assuming positions have equality defined to start with). I vote
for anything except the latter. It would be nice to be able to be able
to print out the indicies and values of a list for debugging, however.


-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container: Insert and Delete

[Marin David Condic]

As long as it raises the "Youre_Out_Of_Memory_You_Bonehead" exception for me
when it can't add more, I'm happy. Same goes for bounded lists. If you know
the current size and you know how much you asked for, why do you need an
"Is_Full" or anything similar? If you exceed your own constant MAX_ELEMENTS
you deserve to get an exception.

Its a pretty easy function for the end user to add as a child unit (or any
other means) anyway...

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Simon Wright" <simon@pushface.org> wrote in message
news:x7vk7wvxh3a.fsf@smaug.pushface.org...
>
> I dunno, no one expects Ada.Text_IO to have special functionality to
> help you with managing your disk space!

Re: List container: Insert and Delete

[Simon Wright]

"Ehud Lamm" <mslamm@mscc.huji.ac.il> writes:

> John English <je@brighton.ac.uk> wrote in message
> news:3BF140D9.611DE43@brighton.ac.uk...
> > Sigh. Perhaps a "list" of shortcomings of existing list packages would
> > be better than yet another reinvention of this particular wheel. For
> > example, what's wrong with Booch lists, or for that matter the ones in
> > my book (http://www.it.bton.ac.uk/staff/je/adacraft/ch12.htm#12.1 and
> > http://www.it.bton.ac.uk/staff/je/adacraft/appd.htm#d.8), or any of
> > the many other implementations floating around already?
> >
> 
> I agree with this sentiment. So why not take the lead and tell us
> why you didn't use the BC in your book...?

I expect that (a) John's intention was to teach people how to program,
and the development of a generic list package was useful, (b) the BCs
were not all that usable in 1997 (the book was _published_ in 97, too,
so the material must be older)

Re: List container: Insert and Delete

[Marin David Condic]

If we both see a Map as being some flavor of an ISAM file in memory, then
I'm happy with whatever kind of underlying structure you want to implement
it out of. I'm presuming you aren't thinking of providing operations like
"Step to the left branch from the current node..." as visible to the user?
If we're just talking about storing and looking up based on an index element
and scanning over the Map in sorted order, I could see it being some kind of
tree, or some kind of static table, or and actual ISAM disk file, or....

Put the sticker on the package body that reads: "Caution! No user servicable
parts inside."

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:9egI7.23469$xS6.37348@www.newsranger.com...
>
> I agree here. However, I should note that one would probably want to
implement a
> general map as some kind of tree.
>

Re: List container strawman 1.2

[Ted Dennison]

In article <x7vn11rxhdf.fsf@smaug.pushface.org>, Simon Wright says...
>
>Ted Dennison<dennison@telepath.com> writes:
>> If finalization is too uncertian to be verifiable, would any heap
>> operation at all also be in the same boat?
>
>I believe so (SPARK 95 _may_ eventually allow heap operation, but I
>don't think it does now. I'm not an expert).

Then any unbounded structure is going to be unusable in that environement
anyway, so its not really an issue (at least not until we start discussing the
bounded structure, for which a case could be made for not using safe pointers
anyway).

---
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.

Map container (was: List container: Insert and Delete)

[Ted Dennison]

In article <9ss3uv$m09$1@nh.pace.co.uk>, Marin David Condic says...
>
>If we both see a Map as being some flavor of an ISAM file in memory, then
>I'm happy with whatever kind of underlying structure you want to implement
>it out of. I'm presuming you aren't thinking of providing operations like
>"Step to the left branch from the current node..." as visible to the user?
>If we're just talking about storing and looking up based on an index element
>and scanning over the Map in sorted order, I could see it being some kind of
>tree, or some kind of static table, or and actual ISAM disk file, or....

To speed lookup on the map keys, it makes sense to me to use a binary search
tree. That also implies that the sorted ordering (forward or back) would always
be available, and would probably be gone through anyway when iterating.

For this reason, I think putting a lot of special sorting capability into the
List structure would be overkill. If you need it kept sorted on some key, just
use a map instead.

---
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 container: Insert and Delete

[Jeffrey Carter]

Ted Dennison wrote:
> 
> I think a lot of us are suffering under a bit of a terminology disconnect here.
> I'm used to thinking of "lists" as bascily any linearly linked structure. In a
> way, that means it is the union of queues, stacks, and any other nifty concept
> that you can come up with using a lineraly linked-list. Thus using our "List"
> type, you ought to be able to simulate any of those other aforementioned
> structures. But they are all types of lists, and saying a stack isn't a list is
> as confusing to me as saying a penny isn't a coin.

The terminology I use has a list as a general purpose sequential data
structure, with insertions and deletions anywhere. Dequeues, stacks, and
queues are "modification-limited lists", with insertions and deletions
limited to specific locations.

It tend to use protected blocking queues between tasks frequently, so I
like having a special component to implement that. The underlying
implementation is a list.

-- 
Jeffrey Carter

Re: List container strawman 1.2

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
> >
> >Ted Dennison wrote:
> >> there is better. "Font" and "Back" are pretty standard terminology for list
> 
> Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't they?

I'm accustomed to First and Last for a list, with iteration starting at
First and going to Last. Head and Tail are more usual for queues.

-- 
Jeffrey Carter

Re: List container strawman 1.2

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BF05337.75BE0A18@san.rr.com>, Darren New says...
> >
> >Darren New wrote:
> >    function "&" (Left, Right : Element) return List;
> >        -- O(1)
> 
> I much prefer pre-comments to post-comments. The reason is that you read them
> before you get to the source, rather than after you have already tried to read
> the source and are perhaps already confused and/or misled. Forewarned is
> forearmed. :-)

I prefer post-comments, because they can refer to things by name without
breaking the linear flow of reading Ada and without having to duplicate
information given by the code.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Ted Dennison]

In article <3BF19106.5FF19B59@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> You had me, before you presented this example. :-)
>
>I don't follow. What's unreasonable about the example? It seems like a
>perfectly reasonable way of saying "does this come before that in the
>list", or saving positions to a stream, or printing something out for
>debugging, or whatever.

I didn't say it was unreasonable. Its just that its a pretty esoteric function.
I'll be charitable and say that for whatever wild reason, I have never required
such a thing from a List. Because of that, I am not currently convinced that
lots of others are out there who really do need it, therefore it wasn't the best
example that could have been chosen. I read from some other responses that I'm
not the only one in that boat.

Not that I'm saying  that there's nothing wrong with you if you need this or
some other esoteric function from a list from time to time. But I think all the
tools are already there to build your "Offset" function, and it won't really be
any slower than if one were provided for you. With the passive iterator, you'd
only need a one-line function, with the active perhaps 4 lines of code. When
that is the case, the general rule ought to be to leave the function out, unless
it is something so common that just about any disinterested observer would be
suprised to not find it in there. 

>Saying "we're not going to implement this operation because it's
>inefficient" doesn't sound like a good idea to me, is all.

Stated that way, I'd agree too. What I was suggesting was that stuff that can be
built w/ the other tools easily and is not O(1) (but *is* O(1) with the other
List type) perhaps should not be presented as a primitive. That way people are
encouraged to use the right tool (package) for the job. Again, this was just one
out of three positions I'd like to see discussed, as a middle ground between
total conformity between Bounded and Unbounded and total redesign. I frankly
could see a good case for any of the three.

>Someone will want to save positions. 
I believe you are most certianly right there, but no one has spoken up about it
yet.

---
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 container: Insert and Delete

[Ted Dennison]

In article <QghI7.23595$xS6.37646@www.newsranger.com>, Ted Dennison says...
>
>In article <3BF19106.5FF19B59@san.rr.com>, Darren New says...
>>I don't follow. What's unreasonable about the example? It seems like a
..
>Not that I'm saying  that there's nothing wrong with you if you need this or
>some other esoteric function from a list from time to time. But I think all the

Whoops! I got a little carried away with my negatives here. Darren, please
remove one negative (of your choice) when reading this sentence before feeling
insulted. :-)

---
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 container: Insert and Delete

[Darren New]

Ted Dennison wrote:
> Not that I'm saying  that there's nothing wrong with you if you need this or
> some other esoteric function from a list from time to time. But I think all the
> tools are already there to build your "Offset" function, and it won't really be
> any slower than if one were provided for you. 

Agreed, as long as positions can be compared for equality.

Anyway, I think the general point I was trying to make was that one
*should* be able to do most anything with the list that the data in the
list supplies. If it's not even a private type, that pretty much solves
all problems. :-)

> that is the case, the general rule ought to be to leave the function out, unless
> it is something so common that just about any disinterested observer would be
> suprised to not find it in there.

Sure, as long as stuff like that *can* be done.
 
> >Saying "we're not going to implement this operation because it's
> >inefficient" doesn't sound like a good idea to me, is all.
> 
> Stated that way, I'd agree too. What I was suggesting was that stuff that can be
> built w/ the other tools easily and is not O(1) (but *is* O(1) with the other
> List type) perhaps should not be presented as a primitive. That way people are
> encouraged to use the right tool (package) for the job. Again, this was just one
> out of three positions I'd like to see discussed, as a middle ground between
> total conformity between Bounded and Unbounded and total redesign. I frankly
> could see a good case for any of the three.

Yes. My concern was that *if* the "position" type can't be compared for
equality by the user, you have to provide that in the library somehow.
*Then* it becomes a one-liner to translate to integers and back.

It's a shame it's not *really* an ADT in the mathematical sense, or we
could prove whether or not we have all the functions anyone would want,
and whether we have the most efficient implementation of them. :-)

-- 
Darren New 
San Diego, CA, USA (PST). Cryptokeys on demand.
   You will soon read a generic fortune cookie.

Re: List container: Insert and Delete

[Nick Roberts]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1413 bytes --]

However, it doesn't solve the question of memory usage. I know the 'classic'
implementation of a bounded list is to have (in effect) a linked list within
an array (or three arrays), but that was not what I actually intended.

I actually intended the 'horrible' choice of an array where the first list
item is stored in the first element of the array, the second in the second,
etc. You might called this the 'na�ve' implementation. The reason why is
because it is the most memory efficient, and I assume that some applications
will require memory efficiency about speed concerns; especially considering
that appends still can be done very fast.

Possibly we need a different nomenclature, e.g. Bounded_List for the classic
implementation, and maybe Bounded_Vector for the na�ve? Or Packed_List?

--
Best wishes,
Nick Roberts




"Ted Dennison" <dennison@telepath.com> wrote in message
news:l%9I7.22965$xS6.35437@www.newsranger.com...
> In article <3BF08501.50C83D22@acm.org>, Jeffrey Carter says...
> >
> >I'm not sure what you're saying here; perhaps that initial "O(N)" should
> >be O(1)? Actually, for a bounded list you have 2 lists in the same
> >array: the real list and a free list. Because of the free list, there is
> >no searching for a hole. Insertions and deletions are O(1) for all
> >positions.
>
> Ahhh. I'd fogotten that you can make a list of the free stuff. That's
right, it
> is O(1).

Re: List container: Insert and Delete

[Nick Roberts]

Great. Good luck!

--
Best wishes,
Nick Roberts



"Ted Dennison" <dennison@telepath.com> wrote in message
news:BY9I7.22959$xS6.35700@www.newsranger.com...
> In article <9spt1i$14snic$2@ID-25716.news.dfncis.de>, Nick Roberts says...
> >I'll e-mail this to you (Ted) maybe Wednesday (probably very busy
tomorrow).
> >I'll also produce an implementation as quick as I can (despite the large
> >number of operations).
>
> OK. I'll hold off posting what you sent me until then, if you don't mind.
> Tonight's my volleyball night, so I probably wouldn't get to it until
Wednesday
> anyway. :-)

Re: List container strawman 1.2

[Nick Roberts]

Well, my proposal uses 'Head' and 'Tail', and other subprogram names, in a
way which (I hope!) is as consistent as possible with the Ada.Strings.*
packages.

Oh, and you forgot about the break-up of Microsoft :-)

--
Best wishes,
Nick Roberts



"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9ss24b$l8v$1@nh.pace.co.uk...
> Fair enough. If we went down the path of doing essentially CAR/CDR to
please
> the Lisp folks, the Unix guys would come out of the woodwork and want you
to
> impliment Head and Tail operations that would give you the first/last N
> elements. And then the Eiffel guys would be there wanting pre/post
> conditions and before you know it, the moon is turning blood red, lions
are
> having sex with sheep, the Seventh Angel breaks the Seventh Seal, a toy
> company makes a tank that folds out into a rain forest and pretty much the
> world as we know it comes to a screeching halt. I really hate it when that
> happens. :-)

Re: List container strawman 1.2

[Nick Roberts]

"Darren New" <dnew@san.rr.com> wrote in message
news:3BF15A01.1E8A6EC7@san.rr.com...
> ...
> type direction is (towards_first, towards_last);
> procedure next(L : in out Location; dir : in direction := towards_last);
> -- Or however you want to declare the procedure/function/whatever.

I think I'm going to use this trick, but I use:

   subtype Direction is Ada.Stings.Direction; -- (Forward, Backward)

in the base package (currently SCL). I also define:

   function Opposite (Way: in Direction) return Direction;
   -- Opposite(Forward) = Backward
   -- Opposite(Backward) = Forward

for convenience.

--
Best wishes,
Nick Roberts

Re: List container: Insert and Delete

[Nick Roberts]

Howabout having:

   Youre_Out_Of_Memory_You_Bonehead: exception renames Storage_Error;

in package Standard in the next revision?

:-)

--
Best wishes,
Nick Roberts

Re: List container: Insert and Delete

[John English]

Ehud Lamm wrote:
> 
> John English <je@brighton.ac.uk> wrote in message
> news:3BF140D9.611DE43@brighton.ac.uk...
> > Sigh. Perhaps a "list" of shortcomings of existing list packages would
> > be better than yet another reinvention of this particular wheel. For
> > example, what's wrong with Booch lists, or for that matter the ones in
> > my book (http://www.it.bton.ac.uk/staff/je/adacraft/ch12.htm#12.1 and
> > http://www.it.bton.ac.uk/staff/je/adacraft/appd.htm#d.8), or any of
> > the many other implementations floating around already?
> >
> 
> I agree with this sentiment. So why not take the lead and tell us why you
> didn't use the BC in your book...?

Uh, because I wanted to explain the internal mechanics in the book.
It's not reinventing the wheel; it's just building a wheel with a bunch
of students watching, and you saying "look, this bit goes here..." :-)

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[John English]

Ted Dennison wrote:
> 
> In article <3BF140D9.611DE43@brighton.ac.uk>, John English says...
> >example, what's wrong with Booch lists, or for that matter the ones in
> 
> I think the problem there was that they were considered (particularly by some of
> your fellow educators) too tough to figure out how to use.

Uh huh. So "hard to use" is one no-no. Are there any others that spring
to mind? Does "hard to use" apply to all the other libraries out there,
or are there other reasons for not using those?

I feel that knowing why existing libraries don't cut the mustard might
help in designing something that does...

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.2

[John English]

Jeffrey Carter wrote:
> 
> Ted Dennison wrote:
> >
> > In article <3BF052D3.ECEF3FF2@san.rr.com>, Darren New says...
> > >
> > >Ted Dennison wrote:
> > >> there is better. "Font" and "Back" are pretty standard terminology for list
> >
> > Hmmm. Reading this over, "Head" and "Tail" are actually more usual, aren't they?
> 
> I'm accustomed to First and Last for a list, with iteration starting at
> First and going to Last. Head and Tail are more usual for queues.

My vote also goes to First and Last. Apart from anything else, the
names are then consistent with the corresponding array attributes,
and consistency is a Good Thing IMHO.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[Ted Dennison]

In article <3BF1A5FC.251D9F20@san.rr.com>, Darren New says...
>
>Ted Dennison wrote:
>> is the case, the general rule ought to be to leave the function out, unless
>> it is something so common that just about any disinterested observer would be
>> suprised to not find it in there.
>
>Sure, as long as stuff like that *can* be done.

Right. I can certianly see occasions where we might want to include an O(NlogN)
function because implementing it yourself with the other tools provided might be
O(N**2), or not even possible at all.

>Yes. My concern was that *if* the "position" type can't be compared for
>equality by the user, you have to provide that in the library somehow.
>*Then* it becomes a one-liner to translate to integers and back.

Right now its not limited, so "=" is available. That being the case, I'd think
"=" ought to do something sensible (or be taken away). An incarnation or two
ago, iterating even depended on it.

---
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 container: Insert and Delete

[Ted Dennison]

In article <3BF26AAC.C0830E5B@brighton.ac.uk>, John English says...
>
>Uh huh. So "hard to use" is one no-no. Are there any others that spring
>to mind? Does "hard to use" apply to all the other libraries out there,
>or are there other reasons for not using those?

What got Booch into the "hard to use" category was its reliance on hierarchies
of generics. Unfortunately, if you throw that out, it also throws out just about
every industrial-strength component library out there. 

I think the basic problem is that pretty much everyone has approached the
problem either from a purely industrial perspective or from a purely acedemic
perspective. Thus we end up with a bunch of libraries that might be great for
their designed enviroment, but suck for the other.

What we are shooting for I believe is something that can be shipped with Ada
compilers (as part of the language, or as a cannonical add-on), which will be
usable for *both* purposes. That obviously means it isn't going to be ideal for
either purpose, but it should be usable most of the time. People will still be
free to go get one of the other component libraries if they find that this one
just isn't quite up to their needs.

>I feel that knowing why existing libraries don't cut the mustard might
>help in designing something that does...

I think (I hope anyway) we've already been through that process. Perhaps listing
some of the decisions and goals we arrived at on a webpage would help newcommers
to the discussion (and those who haven't had the fortitude to follow every post
:-) )?

We could certianly use your input in this process. Right now I believe Ehud is
the only active participant from acedemia, and I'm afraid things might be
getting a bit too much of an industrial tilt as a result. For instance, I'm more
interested in your views on the subprogram and type names than I am with most
people's, because you and Ehud are the ones who are charged with teaching people
how to think about lists, which presumably includes proper terminology.

---
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 container strawman 1.2

[Marin David Condic]

I'm all in favor of making a list package share as much similarity as it can
to Ada.Strings.Unbounded - since they are very similar in nature. It helps
keep things Ada flavored and makes it easier for the programmer to learn one
package and transition to the next.

You're right - I forgot about the Microsoft part. But wasn't it something to
do with Microsoft adopting Ada for its next generation OS and open-sourcing
the whole project?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Nick Roberts" <nickroberts@adaos.worldonline.co.uk> wrote in message
news:9ssu2b$150jnq$5@ID-25716.news.dfncis.de...
> Well, my proposal uses 'Head' and 'Tail', and other subprogram names, in a
> way which (I hope!) is as consistent as possible with the Ada.Strings.*
> packages.
>
> Oh, and you forgot about the break-up of Microsoft :-)
>

Re: List container: Insert and Delete

[Ted Dennison]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1134 bytes --]

In article <9ssu29$150jnq$3@ID-25716.news.dfncis.de>, Nick Roberts says...
>I actually intended the 'horrible' choice of an array where the first list
>item is stored in the first element of the array, the second in the second,

That's what I was initially thinking too.

>Possibly we need a different nomenclature, e.g. Bounded_List for the classic
>implementation, and maybe Bounded_Vector for the na�ve? Or Packed_List?

Precisely. This gets back to the issue of how we want to approach the other
packages. Should there be a "Lists.Bounded" that has all the same attributes as
Unbounded, or should we instead redesign things a bit around what can be done
better with a bounded structure, which would be something like a circular queue
or a STL-style "vector"? If we were to do the latter, then we would probably not
want to stick with the bounded/unbounded nomenclature, because that implies a
certian consistency that isn't there.

---
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: Map container (was: List container: Insert and Delete)

[Marin David Condic]

Sure, but the "treeness" of the implementation is not something the caller
ever sees - or needs to see - or should see.

I like the notion of using a Map if you want sorted elements - but I'm not
sure you wouldn't want to provide some kind of "Insert_Aascending" (or other
technique) on a simple list. If you posit that there will be usages for a
list that will be rather primitive - a list of integers or floats, for
example - you might want them sorted and a Map would start looking like a
lot of overhead - as well as being awkward.

Right now, I'd settle for a basic, unsorted list of private data items and a
sorted map for key/record kinds of things. That would take care of probably
70% of the usage. Getting a sorted list as an extension/variant would
probably pick up another 10% to 20% of the usage.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:mZgI7.23571$xS6.37495@www.newsranger.com...
>
> To speed lookup on the map keys, it makes sense to me to use a binary
search
> tree. That also implies that the sorted ordering (forward or back) would
always
> be available, and would probably be gone through anyway when iterating.
>
> For this reason, I think putting a lot of special sorting capability into
the
> List structure would be overkill. If you need it kept sorted on some key,
just
> use a map instead.
>

Re: List container strawman 1.2

[Ted Dennison]

In article <3BF27410.C899A16B@brighton.ac.uk>, John English says...
>
>Jeffrey Carter wrote:
>> I'm accustomed to First and Last for a list, with iteration starting at
>> First and going to Last. Head and Tail are more usual for queues.
>
>My vote also goes to First and Last. Apart from anything else, the
>names are then consistent with the corresponding array attributes,
>and consistency is a Good Thing IMHO.

Are you saying First and List just for the "Position", or for that and for the
Push and Pop routines too?

---
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 container: Insert and Delete

[Marin David Condic]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:IBvI7.24324$xS6.37794@www.newsranger.com...
>
> What got Booch into the "hard to use" category was its reliance on
hierarchies
> of generics. Unfortunately, if you throw that out, it also throws out just
about
> every industrial-strength component library out there.
>
I still think that the BC's might be an acceptable alternative so long as
what goes along with them is a *simple*case* alternative. Learn the
heierarchies of instantiation as you need them,  but for a plain-vanilla
case, you've got this basic List/Map package that gets the job done with a
minimum of instantiation questions.


>
> What we are shooting for I believe is something that can be shipped with
Ada
> compilers (as part of the language, or as a cannonical add-on), which will
be
> usable for *both* purposes. That obviously means it isn't going to be
ideal for
> either purpose, but it should be usable most of the time. People will
still be
> free to go get one of the other component libraries if they find that this
one
> just isn't quite up to their needs.
>
Well we *could* improve the usability of something like the BC's for both
purposes and this may be A Good Thing for everyone. Provide a simple-case
alternative *and* some Streams capabilities for the BCs and you get a
collection of software that is better for everyone. The academics can start
talking about data structures from the simple case and work their way up to
the more industrial-strength examples as time permits. The industrialists
get something that now gives them a quick-and-dirty method of doing
Lists/Maps for their own simple-case usage *plus* they get the kind of
persistence provided by libraries like MFC.


>
> We could certianly use your input in this process. Right now I believe
Ehud is
> the only active participant from acedemia, and I'm afraid things might be
> getting a bit too much of an industrial tilt as a result. For instance,
I'm more
> interested in your views on the subprogram and type names than I am with
most
> people's, because you and Ehud are the ones who are charged with teaching
people
> how to think about lists, which presumably includes proper terminology.
>
The academics might be able to point us at what are the most popular books
on the subject and what is being taught - that might enable us to mirror
something and be able to say "Well, if you want to understand it better, go
get this book from Amazon..." Wait a minute..... Isn't there a book about
the BC's? :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/

Re: List container strawman 1.2

[Jeffrey Carter]

Ted Dennison wrote:
> 
> In article <3BF27410.C899A16B@brighton.ac.uk>, John English says...
> >My vote also goes to First and Last. Apart from anything else, the
> >names are then consistent with the corresponding array attributes,
> >and consistency is a Good Thing IMHO.
> 
> Are you saying First and List just for the "Position", or for that and for the
> Push and Pop routines too?

Lists don't have Push and Pop operations. Those are stack operations. If
something like

Insert (Item => Thing, Into => List, Before => First (List) );

is so common you think you need a special operation for it, then they
should probably be called Insert_As_First, Append_As_Last, and so on.

-- 
Jeffrey Carter

Re: List container strawman 1.2

[Ted Dennison]

In article <3BF29600.E83E0652@boeing.com>, Jeffrey Carter says...
>Lists don't have Push and Pop operations. Those are stack operations. If
>something like
>
>Insert (Item => Thing, Into => List, Before => First (List) );
>
>is so common you think you need a special operation for it, then they
>should probably be called Insert_As_First, Append_As_Last, and so on.

I see where you are comming from, and I'm not overly enamoured of using stack
terms for a general list either. But I don't think Insert_As_First and
Append_As_Last are better names.

---
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 container: Insert and Delete

[Jeffrey Carter]

John English wrote:
> 
> I feel that knowing why existing libraries don't cut the mustard might
> help in designing something that does...

Let's see

Booch Components and Stephe's Ada Library: need to do multiple
instantiations and to instantiate generic child packages

PragmAda Reusable Components: need to provide an Assign procedure for
the Element type, and to wrap subrange scalar subtypes in a record for
use as an Element

I don't recall any other specific libraries, but I'm sure others do and
will provide the details for them.

-- 
Jeffrey Carter

Re: List container: Insert and Delete

[Ehud Lamm]

John English <je@brighton.ac.uk> wrote in message
news:3BF2699A.731DC436@brighton.ac.uk...
> Ehud Lamm wrote:
> >
> >
> > I agree with this sentiment. So why not take the lead and tell us why
you
> > didn't use the BC in your book...?
>
> Uh, because I wanted to explain the internal mechanics in the book.
> It's not reinventing the wheel; it's just building a wheel with a bunch
> of students watching, and you saying "look, this bit goes here..." :-)
>

But I guess you made some design decisions which resulted in something
different from the BC (either the -83 or -95 version).

I tried to give a list of goals awhile back. I decided it is nicer to list
requirements/goal instead of problems with this library or other. But I
guess most goals can be traced back to problems with using existing
libraries.

However, for the record, I prefer having a standard library which I don't
particularly like to having no standard container library at all.

Ehud

Re: List container: Insert and Delete

[Marin David Condic]

I concur - Could you get behind the Booch Components with some modifications
as I suggested? Would you favor the PragmARC with some similar
modifications?

I think we have some agreement that there needs to be a relatively simple
List & Map package - which could be added to any existing library. I think
we might also agree that any library of containers should be able to work
with Streams - which could be a modification to an existing library. I think
we *might* be able to get to a conclusion here if we could agree on a
library, accept Ted's Lists (and eventually, Maps) as an extension, and get
an agreement as to what subprograms should be added to the library's
components so that it would support Streams.

I think we might be able to get volunteers to add the extensions under the
supervision of the library's "owner". If its BC's, would Simon be willing to
supervise/coordinate the changes? If its PragmARC, would Jeffery be willing
to volunteer for this duty?

Personally, I'd opt for the BC's for no other reason than they seem to
already have a fairly wide audience and name recognition. However, I could
live with PragmARC if there is some strong consensus that it is a better
choice technically.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ehud Lamm" <mslamm@mscc.huji.ac.il> wrote in message
news:9su77k$c83$1@news.huji.ac.il...
>
> However, for the record, I prefer having a standard library which I don't
> particularly like to having no standard container library at all.
>

Re: List container: Sawdust woman 43

[Jeffrey Carter]

Marin David Condic wrote:
> 
> I think we might be able to get volunteers to add the extensions under the
> supervision of the library's "owner". If its BC's, would Simon be willing to
> supervise/coordinate the changes? If its PragmARC, would Jeffery be willing
> to volunteer for this duty?

The important thing is to have a workable standard library. I'm not
completely in favor of some of the choices made in the current standard
library, but having a standard is better what we had with Ada 83.

If the PragmARCs can serve as a basis for any of the components in such
a library, PragmAda would be proud to assist in the process. If another
form of components is chosen for a standard library, PragmAda would
welcome that. However, we would not consider the adoption of a standard
component based on the PragmARCs as "extending" the library; rather, we
would eliminate the equivalent component from the PragmARCs, as we
eliminated the variable-string component that was in the Ada-83 version
from the Ada-95 version of the components with the introduction of the
standard string libraries. Ideally, we would like to eliminate all the
basic components from the PragmARCs.

Let me try an experiment. I'll append the entire specification of
PragmARC.List_Unbounded_Unprotected to this message (the exception
Storage_Exhausted is defined in the root package PragmARC). I would like
to know who would refuse to use a standard component derived from this
package through modest modifications. For those who would be willing to
use such a component, what would be the minimal set of changes you would
require before using the component?

I'll help shorten the process by listing some changes I think we've
already reached consensus on here:

The package name will be different (but we haven't decided what it will
be yet). I would not expect a standard list package to be named
PragmARC.Anything.

The imported type Element will be private; the imported procedure Assign
will be eliminated.

Handle (the list type) will be private, with Adjust and "=" defined to
produce a deep copy and meaningful equality.

Any objections that enough people agree on could then be incorporated to
produce an acceptable specification for a standard list package. No one
would be entirely satisfied with the resulting package (obviously I
wouldn't), but perhaps we could reach consensus that it could be the
standard list. If the list of common objections is long, then this is
not a suitable starting point for a standard list package.

-- 
Jeffrey R. Carter
PragmAda Software Engineering

Listing follows; please bear with unavoidable reformatting by
newsreaders:

-- PragmAda Reusable Component (PragmARC)
-- Copyright (C) 2001 by PragmAda Software Engineering.  All rights
reserved.
--
**************************************************************************
--
-- General purpose list for sequential use
-- A list has elements in sequence; each element has a position in that
sequence
-- Positions are used to manipulate a list
--
-- History:
-- 2001 May 01     J. Carter          V1.1--Added Is_Empty
-- 2000 May 01     J. Carter          V1.0--Initial release
--
with Ada.Finalization;

use Ada;
generic -- PragmARC.List_Unbounded_Unprotected
   type Element is limited private; -- Do not instantiate with a scalar

   with procedure Assign (To : in out Element; From : in Element) is <>;
package PragmARC.List_Unbounded_Unprotected is
   pragma Preelaborate;

   type Handle is limited private; -- Initial value: empty

   type Position is private;
   -- A position is initially invalid until assigned a value by First,
Last, or Off_List
   -- Other positions accessible via Next and Prev

   Invalid_Position : exception; -- Raised if a position is invalid or
if the Off_List position is used for Delete, Get, or Put

   procedure Clear (List : in out Handle); -- Makes List empty

   -- Operations to obtain valid positions for lists:
   function First    (List : Handle) return Position; -- The position of
the first item in List
   function Last     (List : Handle) return Position; -- The position of
the last  item in List
   function Off_List (List : Handle) return Position;
   -- Next (Last (List), List) and Prev (First (List), List) refer to
positions which are "off the list"
   -- This special position is used in those cases
   -- Each list has a unique Off_List position
   -- Next (Last (List), List)  = Off_List (List)
   -- Prev (First (List), List) = Off_List (List)
   --
   -- Next and Prev are supposed to reverse each other
   -- For a valid Position P of Handle L, Next (Prev (P, L), L) = P and
Prev (Next (P, L), L) = P
   -- This gives us:
   -- Next (Off_List (List), List) = First (List)
   -- Prev (Off_List (List), List) = Last (List)
   --
   -- A similar relation holds for Insert and Append:
   -- Insert (List, X, Off_List (List), P) <=> Append (List, X, Last
(List), P)
   -- Append (List, X, Off_List (List), P) <=> Insert (List, X, First
(List), P)
   --
   -- If List is empty, Off_List (List) = First (List) = Last (List)
   -- The Off_List position cannot be used for Delete, Get, or Put
   --
   -- Time: O(1)

   -- Operations to obtain valid positions from valid positions:
   function Next (Pos : Position; List : Handle) return Position; --
raise Invalid_Position
   function Prev (Pos : Position; List : Handle) return Position; --
raise Invalid_Position
   -- Next and Prev raise Invalid_Position if Pos is invalid
   --
   -- Time: O(1)

   -- Operations to manipulate lists
   procedure Insert (Into : in out Handle; Item : in Element; Before :
in Position; New_Pos : out Position);
   -- Inserts Item before Before
   -- Returns the position of Item in Into in New_pos
   -- Raises Storage_Exhausted if no more storage is available for Into
   -- Raises Invalid_Position if Pos is invalid
   -- Nothing is changed if Storage_Exhausted or Invalid_Position are
raised
   --
   -- Time: O(1)

   procedure Append (Into : in out Handle; Item : in Element; After : in
Position; New_Pos : out Position);
   -- Appends Item after After
   -- Returns the position of Item in Into in New_Pos
   -- Raises Storage_Exhausted if no more storage is available for Into
   -- Raises Invalid_Position if Pos is invalid
   -- Nothing is changed if Storage_Exhausted or Invalid_Position are
raised
   --
   -- Time: O(1)

   procedure Delete (From : in out Handle; Pos : in out Position); --
raise Invalid_Position
   -- Deletes the item at Pos
   -- Pos is made invalid
   -- Raises Invalid_Position if Pos is invalid or is the Off_List
position for From
   -- Nothing is changed if Invalid_Position is raised
   --
   -- Time: O(1)

   function Get (From : Handle; Pos : Position) return Element; -- raise
Invalid_Position
   -- Returns the item at Pos
   -- Raises Invalid_Position if Pos is invalid or the Off_List position
   --
   -- Time: O(1)

   procedure Put (Into : in out Handle; Pos : in Position; Item : in
Element); -- raise Invalid_Position
   -- Makes the Element stored at Pos be Item
   -- Raises Invalid_Position if Pos is invalid or is the Off_List
position for Into
   -- Nothing is changed if Invalid_Position is raised
   --
   -- Time: O(1)
   
   function Is_Empty (List : Handle) return Boolean;
   -- Returns True if List is empty [Length (List) = 0]; returns False
otherwise
   --
   -- Time: O(1)

   function Length (List : Handle) return Natural; -- Returns a count of
the number of items in List
   --
   -- Time: O(N)

   generic -- Iterate
      with procedure Action (Item : in out Element; Pos : in Position;
Continue : out Boolean);
   procedure Iterate (Over : in out Handle);
   -- Calls Action with each Element in Over, & its Position, in turn
   -- Returns immediately if Continue is set to False (remainder of Over
is not processed)

   generic -- Sort
      with function "<" (Left : Element; Right : Element) return Boolean
is <>;
   procedure Sort (List : in out Handle); -- raise Storage_Exhausted
   -- Sorts List into ascending order as defined by "<"
   -- Requires one additional list node
   -- Raises Storage_Exhausted if no more storage is available for this
extra node
   -- List is unchanged if Storage_Exhausted is raised
   --
   -- Time: O(N log N)
private -- PragmARC.List_Unbounded_Unprotected
   ...
end PragmARC.List_Unbounded_Unprotected;
--
-- This is free software; you can redistribute it and/or modify it under
-- terms of the GNU General Public License as published by the Free
Software
-- Foundation; either version 2, or (at your option) any later version.
-- This software is distributed in the hope that it will be useful, but
WITH
-- OUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY
-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
License
-- for more details. Free Software Foundation, 59 Temple Place - Suite
-- 330, Boston, MA 02111-1307, USA.
--
-- As a special exception, if other files instantiate generics from this
-- unit, or you link this unit with other files to produce an
executable,
-- this unit does not by itself cause the resulting executable to be
-- covered by the GNU General Public License. This exception does not
-- however invalidate any other reasons why the executable file might be
-- covered by the GNU Public License.

Re: List container: Sawdust woman 43

[Marin David Condic]

Maybe you misinterpreted what I was suggesting. Hypothetically, the decision
could be taken to make PragmARC the "Standard Component Library" (Not
necessarily part of the ARM...) - but given some of the requirements, there
would need to be some enhancements made. (It doesn't support getting lists,
etc into Streams?) If the community was willing to buy into that concept and
we could identify a desired set of extensions/enhancements to make PragmARC
more acceptable to the community, would that adaptation be something you'd
be willing to supervise/coordinate?

I could see something similar being done to the BC's & I don't think I've
heard of any other libraries out there being proposed as candidates, so it
seems the decision comes down to a) Home-Brew a library, b) Adapt the
PragmARC library, c) Adapt the BC's.

Choices B and C get us moved along considerably faster than A. Any
preferences to be expressed?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3BF344AD.42FCB303@acm.org...
>
> The important thing is to have a workable standard library. I'm not
> completely in favor of some of the choices made in the current standard
> library, but having a standard is better what we had with Ada 83.
>
> If the PragmARCs can serve as a basis for any of the components in such
> a library, PragmAda would be proud to assist in the process. If another
> form of components is chosen for a standard library, PragmAda would
> welcome that. However, we would not consider the adoption of a standard
> component based on the PragmARCs as "extending" the library; rather, we
> would eliminate the equivalent component from the PragmARCs, as we
> eliminated the variable-string component that was in the Ada-83 version
> from the Ada-95 version of the components with the introduction of the
> standard string libraries. Ideally, we would like to eliminate all the
> basic components from the PragmARCs.

Re: List container strawman 1.2

[John English]

Ted Dennison wrote:
> 
> In article <3BF27410.C899A16B@brighton.ac.uk>, John English says...
> >My vote also goes to First and Last. Apart from anything else, the
> >names are then consistent with the corresponding array attributes,
> >and consistency is a Good Thing IMHO.
> 
> Are you saying First and List just for the "Position", or for that and for the
> Push and Pop routines too?

Hmm, Push_First and Push_Last? How about Insert_First, Insert_Last
(which would be effectively a renaming of
Insert(List,First(List),Item)).

Gah. Which is more confusing: having Front(L) = Item(First(L))
or First(L) = Item(First(L))? Perhaps Front and Back are "a
convenience too far", and should be dropped since they are
easily constructed from simpler building blocks? I would have
thought that bloating the API with extra functionality would be
a bad idea unless there's a good reason to, such as the operations
would be difficult for the user to implement (for some value of
"difficult")... I don't think writing Item(First(I)) counts as
"difficult", though.

I'd personally prefer to stick to:
  &, Singleton (or To_List?), Size, First, Last, Next, Previous,
  Item, Insert, Remove, Modify, Sort, Stream_Read, Stream_Write.

Iterator is nice too but instantiating the generic (and wrapping the
operation in an approapriately-shaped procedure first) is probably
more hassle than a while I <> Last(L) loop, IMHO...

OTOH, Sort counts as "difficult" so should probably be kept. However,
another one I might one would be Shuffle, which is about the same
level of difficulty... maybe a generalisation such as Swap(Index,Index)
might be a useful building block for algorithms of this sort.

Also operations on sublists, specified by a range of Indexes to allow
you to remove a sublist, insert a sublist, replace a sublist by another,
and so on. You'd need Copy(List,From,To) and Cut(List,From,To) for
this.

e.g. Insert(List_1, Index_1, Copy(List_2,A,B));
or   Insert(List_1, Index_1, Cut(List_2,A,B));

I also think that an Index needs to know which list it refers to,
to avoid:
  I := First(L2); Insert(L1,I,X); -- L1 /= L2
The package in my book models an iterator as a pair of pointers (one
to the list header, one to the element or null). (L,null) refers to
the end of L (the position after the last element); (null,null) is a
null iterator. Since it's a private type, the two pointers are always
kept in synch by the iterator primitives.

So Insert would need two parameters (List and Value) and Remove would
need one: Insert(First(L),Item) instead of Insert(L,First(L),Item) or
(worse) Insert(L,First(L2),Item).

Phew. Sorry for the stream-of-consciousness ramble... hope it helps ;-)

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[John English]

Ted Dennison wrote:
> >I feel that knowing why existing libraries don't cut the mustard might
> >help in designing something that does...
> 
> I think (I hope anyway) we've already been through that process. Perhaps listing
> some of the decisions and goals we arrived at on a webpage would help newcommers
> to the discussion (and those who haven't had the fortitude to follow every post
> :-) )?

Good idea -- the traffic has gone up to the point where I just have
to do a catch-up every few days, so I think I'm missing some important
stuff simply because I don't have the time to read everything that's
being posted.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[John English]

Ehud Lamm wrote:
> But I guess you made some design decisions which resulted in something
> different from the BC (either the -83 or -95 version).

Yes, I was influenced by the STL. So I had this:
  type Item_Type is private;
      -- supplied as a generic parameter
  type List_Type is new Limited_Controlled with private;
      -- a pain; means library-level instantiations. No easy
      -- solution to this...

  type List_Iterator is private;
      -- an iterator is like an STL iterator; it's represented
      -- internally as a pointer to the list header and a pointer
      -- to a node within that same list. For a list L = (A,B,C),
      -- the possible values are (L,A) = the position before A,
      -- (L,B) and (L,C) similarly, and (L,null) is the position
      -- after C. The initial value is (null,null) meaning an
      -- uninitialised iterator value (raises List_Error if used).

  function Size (List : List_Type) return Natural;
      -- length of the list

  function First (List : List_Type) return List_Iterator;
  function Last (List : List_Type) return List_Iterator;
  function Succ (Iterator : List_Iterator) return List_Iterator;
  function Pred (Iterator : List_Iterator) return List_Iterator;
      -- names chosen to match attributes of an enumeration.
      -- Iterators are immutable; these functions all produce
      -- a brand new iterator value each time they're used.

  function Value (Iterator : List_Iterator) return Item_Type;
      -- get the value that an iterator refers to (or raise
      -- List_Error)
     
  procedure Insert (Iterator : in List_Iterator;
                    Item     : in Item_Type);
  procedure Delete (Iterator : in List_Iterator);
      -- modify the list. The iterator given to Delete will be
      -- invalid afterwards; maybe it should be "in out", and
      -- explicitly nulled by the procedure.

  List_Error : exception;
      -- raised if iterators are invalid

Now: "&" is missing, Singleton = Insert(First(L)) where L is an
empty list; Push_Front(L,X) = Insert(First(L),X), Push_Back(L,X)
= Insert(Last(L),X), Pop_Front(L,X) = X := Value(First(X));
Delete(First(X)); Pop_Back(L,X) = X := Value(Pred(Last(X)));
Delete(Pred(Last(X)); Is_Empty(L) = (Size(L) = 0), Has_Item
doesn't apply any more, and Ted's Iterator, Insert(List,Index,List),
Modify and Sort aren't there but probably should be (see stream-of-
consciousness ramble elsewhere in this thread).

Missing from Ted's Strawman: Clear(L) = delete everything in the list,
Cut(A,B) = remove everything between iterators A and B and return as
a list (or raise List_Error if A and B refer to separate lists), and
Copy(A,B) = copy a sublist. The use of Cut and Copy together with "&"
and Insert(Iterator,List) would deal with all the sublist operations
and operations on pairs of lists.

Problems encountered: students don't like Delete(Pred(Last(L))),
they always write Delete(Last(L)) and then get a List_Error.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[Simon Wright]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> writes:

> I think we might be able to get volunteers to add the extensions under the
> supervision of the library's "owner". If its BC's, would Simon be willing to
> supervise/coordinate the changes?

Yep

Re: List container strawman 1.2

[martin.m.dowie]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in
message news:9ss371$lk6$1@nh.pace.co.uk...
> I think the original example omitted the "is <>" part. It makes a
> difference.

ok, I admit it - I "copied" the code from (human) memory!

Re: List container strawman 1.2

[martin.m.dowie]

"Ted Dennison" <dennison@telepath.com> wrote in message
news:BMaI7.23036$xS6.35883@www.newsranger.com...
> In article <9spt1k$14snic$5@ID-25716.news.dfncis.de>, Nick Roberts says...
> >After dealing with lists, I intend to propose one or two
content-addressed
> >array (contar) packages. The essence of a contar is that it has a
specific
> >index or key type as well as a specific data type. I suppose a contar is
a
> >kind of mapping (in alternative nomenclature).
>
> Sounds like a "Map" to me, which certianly is the next subject on the
agenda.

Well, so long as this sort of behaviour is _easily_ spec-ed in a _standard_
way, I'd don't care if it is called "package generic_blue_cheese" :-)

Re: List container strawman 1.2

[martin.m.dowie]

"John English" <je@brighton.ac.uk> wrote in message
news:3BF27410.C899A16B@brighton.ac.uk...
> My vote also goes to First and Last. Apart from anything else, the
> names are then consistent with the corresponding array attributes,
> and consistency is a Good Thing IMHO.

Hi John!

First and Head are equivilant

But Last and Tail were not - which is what I was trying to convay...

In ML-ish speak (I know this involves 'grannies' and 'eggs') but
a list is defined as:

List = <nothing> | Head | Head + Tail;
Head = List_Element;
Tail = Head | List;

(again from memory!)

So Tail /= (always) Last;

Re: List container: Sawdust woman 43

[Jeffrey Carter]

Marin David Condic wrote:
> 
> Maybe you misinterpreted what I was suggesting. Hypothetically, the decision
> could be taken to make PragmARC the "Standard Component Library" (Not
> necessarily part of the ARM...) - but given some of the requirements, there
> would need to be some enhancements made. (It doesn't support getting lists,
> etc into Streams?) If the community was willing to buy into that concept and
> we could identify a desired set of extensions/enhancements to make PragmARC
> more acceptable to the community, would that adaptation be something you'd
> be willing to supervise/coordinate?

Maybe I did. I certainly would have no objection if the Ada community
chose to adopt the PragmARCs as a standard library, and would be willing
to help incorporate enhancements that had a consensus as needed. I was
under the impression that the PragmARC's list component, at least, was
widely considered unacceptable for such a library because of some of the
design decisions.

I would still not expect the PragmAda name to be connected to the
library after acceptance as a standard library, since it would be the
specifications that were accepted, and other implementations may be
provided, as with the Ada.XYZ packages.

In the meantime, I'll hold my breath while waiting for you to form a
consensus for adopting an existing library. While I'm turning blue, it
might still be nice to get people's comments on how the PragmARC list
specification would have to change to be acceptable.

-- 
Jeffrey R. Carter
PragmAda Software Engineering

Re: List container: Insert and Delete

[Ted Dennison]

In article <3BF3F4E9.7E32361B@brighton.ac.uk>, John English says...
>Missing from Ted's Strawman: Clear(L) = delete everything in the list,

I think that's far more important in your version than it is in the Strawman
because you use a limited type. With a limited type, the only way for someone to
reuse a list variable on a new list is to delete everything out of the old one.
With a non-limited list, you can just build your new list and assign it in.

It could still be added, of course. It just isn't vital like it was for yours.

>Cut(A,B) = remove everything between iterators A and B and return as
>a list (or raise List_Error if A and B refer to separate lists), and
>Copy(A,B) = copy a sublist. The use of Cut and Copy together with "&"
>and Insert(Iterator,List) would deal with all the sublist operations
>and operations on pairs of lists.

What do you have to do a lot that requires this? They can both be built with the
provided iterators without loosing much processing power.

>Problems encountered: students don't like Delete(Pred(Last(L))),
>they always write Delete(Last(L)) and then get a List_Error.

I'd think the "Pop" operations would be the more standard (and popular) way of
removing items off of one of the ends of the list than going though the effort
of using the active iterator routines.

---
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 container strawman 1.2

[Ted Dennison]

In article <3BF3EDE5.FE0ED701@brighton.ac.uk>, John English says...
(good stuff all)
>
>Iterator is nice too but instantiating the generic (and wrapping the
>operation in an approapriately-shaped procedure first) is probably
>more hassle than a while I <> Last(L) loop, IMHO...

That's my feelings on it too. Additionally, I've found you have to use globals
in the routine to get all of your real work done, which rubs the wrong way
against about 13 years of training on my part. But there are those here who
swear by passive iterators.

>another one I might one would be Shuffle, which is about the same
>level of difficulty... maybe a generalisation such as Swap(Index,Index)
>might be a useful building block for algorithms of this sort.

I suppose. That would let someone write themselves a Bogo-sort if they really
want to.

>I also think that an Index needs to know which list it refers to,
..

We've been down that road. The place it leads is that if you want safe
iterators, you have to make both the indices and the lists controlled and keep a
little mini-list of iterators in each list. The algorithms for doing this
properly aren't unachieveable, but they do make everything quite a bit more
complex. They also create a situation where real-time users will have to be a
lot more careful when they iterate through a list to aviod heap operations.

The current version takes the opposite stance. I'm wavering quite a bit in my
support for it though.

---
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 container strawman 1.2

[Stephen Leake]

Ted Dennison<dennison@telepath.com> writes:

> In article <3BF3EDE5.FE0ED701@brighton.ac.uk>, John English says...
> (good stuff all)
> >
> >Iterator is nice too but instantiating the generic (and wrapping the
> >operation in an approapriately-shaped procedure first) is probably
> >more hassle than a while I <> Last(L) loop, IMHO...
> 
> That's my feelings on it too. Additionally, I've found you have to use globals
> in the routine to get all of your real work done, which rubs the wrong way
> against about 13 years of training on my part. But there are those here who
> swear by passive iterators.

I handle this in a different way in SAL. See the file
sal-gen-alg-process_all_constant.ads for an example.

The key point is that iterating thru a container is an _algorithm_. It
is instantiated separately from the container (I know, that's too hard
:). In fact, the algorithm can be instantiated in a local scope, so
the "global variables" are local to that scope.


Yet another design is to declare a "State_Type" generic formal for the
iterator, like ASIS does for tree processing:

generic
   type State_Type is limited private;
   with procedure Operation 
      (Target : in out Element; 
       State  : in out State_Type;
       Quit   :    out Boolean);
procedure Iterator (Target : in out List);

This complicates things for users that don't need state, but they can
just pass Integer.
 
-- 
-- Stephe

Re: List container strawman 1.2

[John English]

Ted Dennison wrote:
> >I also think that an Index needs to know which list it refers to,
> ..
> 
> We've been down that road. The place it leads is that if you want safe
> iterators, you have to make both the indices and the lists controlled and keep a
> little mini-list of iterators in each list.

No, you misunderstand me. The iterators I developed in my book weren't
safe in this sense, but they were more like pointers than array indexes.
Your strawman proposal has you passing a list and an index as two separate
(and hence seperable) components, like passing "My_Array" and "I" as two
separate components to represent "My_Array(I)". This is perhaps sensible
for arrays, where I could be an index into several arrays, but for a list
I feel that pointer-style semantics (the iterator refers to point I in
list X) is more sensible. There is also a universal "null pointer" value.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container: Insert and Delete

[John English]

Ted Dennison wrote:
> 
> In article <3BF3F4E9.7E32361B@brighton.ac.uk>, John English says...
> >Missing from Ted's Strawman: Clear(L) = delete everything in the list,
> 
> I think that's far more important in your version than it is in the Strawman
> because you use a limited type. With a limited type, the only way for someone to
> reuse a list variable on a new list is to delete everything out of the old one.
> With a non-limited list, you can just build your new list and assign it in.

Uh huh. True, I made it limited because I didn't want to talk about controlled
types at that point in the book, but non-limited (shallow copy semantics)
is probably better.

> >Cut(A,B) = remove everything between iterators A and B and return as
> >a list (or raise List_Error if A and B refer to separate lists), and
> >Copy(A,B) = copy a sublist. The use of Cut and Copy together with "&"
> >and Insert(Iterator,List) would deal with all the sublist operations
> >and operations on pairs of lists.
> 
> What do you have to do a lot that requires this? They can both be built with the
> provided iterators without loosing much processing power.

I'm thinking of the equivalent of A(1..N) := A(I+1..N) & A(1..I);
 
> >Problems encountered: students don't like Delete(Pred(Last(L))),
> >they always write Delete(Last(L)) and then get a List_Error.
> 
> I'd think the "Pop" operations would be the more standard (and popular) way of
> removing items off of one of the ends of the list than going though the effort
> of using the active iterator routines.

I'd certainly agree in this case!

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.2

[ramatthews]

In article <SLbK7.30473$xS6.49203@www.newsranger.com>, Ted Dennison<dennison@telepath.com> wrote:
> snip...
> 
> We've been down that road. The place it leads is that if you want safe
> iterators, you have to make both the indices and the lists controlled and keep a
> little mini-list of iterators in each list. The algorithms for doing this
> properly aren't unachieveable, but they do make everything quite a bit more
> complex. They also create a situation where real-time users will have to be a
> lot more careful when they iterate through a list to aviod heap operations.
> 
> The current version takes the opposite stance. I'm wavering quite a bit in my
> support for it though.
> 

An implementation of a list that uses 'safe' iterators is now
available on:

http://homepage.ntlworld.com/ramatthews

I have also asked David Bottom to hold a copy on AdaPower.

Robert A. Matthews

Re: List container strawman 1.2

[Nick Roberts]

My approach to solving the problem of 'safe pointers' is to have the
'pointers' (I call them 'cursors') inside the list type. This way they can
be checked by any list operation for validity (and internally updated as
necessary), and they can be referenced by number (1, 2, 3, etc.) for maximum
simplicity.

I hope to get my new proposal (V5) on my web site ASAP.

As for iteration as such, it's usefulness goes far beyond "it's easier to
have a while loop" or the like. More on this later.

I've taken the liberty of adding Robert's web page to my links.

--
Best wishes,
Nick Roberts




<ramatthews@tinuviel.com> wrote in message news:700ht9.6k1.ln@127.0.0.1...
> In article <SLbK7.30473$xS6.49203@www.newsranger.com>, Ted
Dennison<dennison@telepath.com> wrote:
> > snip...
> >
> > We've been down that road. The place it leads is that if you want safe
> > iterators, you have to make both the indices and the lists controlled
and keep a
> > little mini-list of iterators in each list. The algorithms for doing
this
> > properly aren't unachieveable, but they do make everything quite a bit
more
> > complex. They also create a situation where real-time users will have to
be a
> > lot more careful when they iterate through a list to aviod heap
operations.
> >
> > The current version takes the opposite stance. I'm wavering quite a bit
in my
> > support for it though.
> >
>
> An implementation of a list that uses 'safe' iterators is now
> available on:
>
> http://homepage.ntlworld.com/ramatthews
>
> I have also asked David Bottom to hold a copy on AdaPower.
>
> Robert A. Matthews

Re: List container strawman 1.2

[John English]

Nick Roberts wrote:
> 
> My approach to solving the problem of 'safe pointers' is to have the
> 'pointers' (I call them 'cursors') inside the list type. This way they can
> be checked by any list operation for validity (and internally updated as
> necessary), and they can be referenced by number (1, 2, 3, etc.) for maximum
> simplicity.

Uh huh. That addresses my concern (you can't try to use an iterator
to list X to access list Y by mistake), but I'm less happy about the
rationale for having a limited number of them inside the list type.
IMHO, the iterators should be a separate type so that you can use
them like any other type (pass them as parameters, etc.); you don't
end up with the overhead of unused iterators clogging up every list
you create; and you never have problems if you need "just one more".

What's the problem with having an iterator as a separate type which
identifies the list it refers to, together with a position in that
list? I really don't see why it should be a big deal...

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.2

[Ted Dennison]

In article <9tht9a$2j1ni$1@ID-25716.news.dfncis.de>, Nick Roberts says...
>
>My approach to solving the problem of 'safe pointers' is to have the
>'pointers' (I call them 'cursors') inside the list type. This way they can
>be checked by any list operation for validity (and internally updated as
>necessary), and they can be referenced by number (1, 2, 3, etc.) for maximum
>simplicity.

I find that solution slightly inferior, as it only allows one iterator at a
time, whereas the other one allows as many as you want. 

---
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 container strawman 1.2

[John English]

Ted Dennison wrote:
> 
> In article <9tht9a$2j1ni$1@ID-25716.news.dfncis.de>, Nick Roberts says...
> >
> >My approach to solving the problem of 'safe pointers' is to have the
> >'pointers' (I call them 'cursors') inside the list type. This way they can
> >be checked by any list operation for validity (and internally updated as
> >necessary), and they can be referenced by number (1, 2, 3, etc.) for maximum
> >simplicity.
> 
> I find that solution slightly inferior, as it only allows one iterator at a
> time, whereas the other one allows as many as you want.

Well, N for some finite N since:
> they can be referenced by number (1, 2, 3, etc.)

...but then you still have the same disadvantages (for cursors) as using an array
for a variable size data structure (you preallocate cursors pessimistically, but
you are occasionally disappointed even so).

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.comp.it.bton.ac.uk/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: List container strawman 1.2

[Nick Roberts]

Hooray! My revised proposal (version 5) is on my web site at:

http://www.adaos.ukf.net

"John English" <je@brighton.ac.uk> wrote in message
news:3BFCC54E.8632A515@brighton.ac.uk...
> ...
> but I'm less happy about the
> rationale for having a limited number of them inside the list type.
> ...
> you don't end up with the overhead of unused iterators clogging up
> every list you create;

For unbounded lists, you can have up to 255 cursors. They are (able to be)
dynamically allocated (from 'heap').

> IMHO, the iterators should be a separate type so that you can use
> them like any other type (pass them as parameters, etc.);

Are you confusing iterators with 'pointers' (I call them 'cursors')? I'm
going to add a set of iteration packages to my proposal as soon as I can (in
which an iterator will be a separate type).

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Marin David Condic]

I was taking another look at:
http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html and
I had a question....

We've got here a Stream_Read and a Stream_Write procedure. Is there any
reason not to have a Stream_Input and Stream_Output as well? Would it make
more sense to have a Stream_Class_Read/Input/Write/Output? I'm thinking that
'Input and 'Output are likely to be more useful than 'Read and 'Write
(although requiring more space) and I'm not sure about the class-wide ops.

I'm guessing that there would eventually be some version of "for List'Read
use Stream_Read..." and so forth?

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:3piL7.34607$xS6.59455@www.newsranger.com...
<snip>

Re: List container strawman 1.2

[Thomas Wolf]

Marin David Condic wrote:

> We've got here a Stream_Read and a Stream_Write procedure. Is there any
> reason not to have a Stream_Input and Stream_Output as well? 

Why? 'Output and 'Input are defined in terms of 'Write and 'Read (see
RM 13.13.2), so it generally suffices to define the latter.

> Would it make more sense to have a Stream_Class_Read/Input/Write/Output? 

These, too, are defined in terms of dispatching to the correct
non-class-wide
attribute, which in turn again invoke 'Write and 'Read.

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

Re: List container strawman 1.2

[Marin David Condic]

I knew that their *behavior* is defined in terms of 'Read and 'Write, but I
did not know that you would get them to come along free for the cost of
defining your own overrides for 'Read and 'Write. I was under the impression
that you'd still have to make your own procedures and do a for-use. If this
is not the case, then great - nice to get something as a freebie.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Thomas Wolf" <t_wolf@angelfire.com> wrote in message
news:3C049C06.DF85EF80@angelfire.com...
>
> Why? 'Output and 'Input are defined in terms of 'Write and 'Read (see
> RM 13.13.2), so it generally suffices to define the latter.
>

Re: List container strawman 1.2

[Ted Dennison]

In article <9u2scm$lqg$1@nh.pace.co.uk>, Marin David Condic says...
>
>I knew that their *behavior* is defined in terms of 'Read and 'Write, but I
>did not know that you would get them to come along free for the cost of
>defining your own overrides for 'Read and 'Write. I was under the impression
>that you'd still have to make your own procedures and do a for-use. If this
>is not the case, then great - nice to get something as a freebie.

That's what I thought for a while too, but I belive Tucker corrected me on that
point a while back. My memory of it is pretty bad, so perhaps we need another
language-lawyer to step in here.

If you think about it though, it really *needs* to be that way. How could you
possibly implement your own version of 'Class'Input yourself?

---
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 container strawman 1.2

[Marin David Condic]

Ummmmm.... By calling the 'Class'Input for individual components of the
thing being read? I've played with streams and got them to do what I needed
them to do, but I wouldn't trust myself to be up on all the ins and outs of
what can be done or how to do it. The ARM says you can override it with your
own operation so I'm guessing there must be a use for it.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:we9N7.40988$xS6.68991@www.newsranger.com...
>
> If you think about it though, it really *needs* to be that way. How could
you
> possibly implement your own version of 'Class'Input yourself?
>

Re: List container strawman 1.2

[Ted Dennison]

In article <9u38pn$r7r$1@nh.pace.co.uk>, Marin David Condic says...
>
>Ummmmm.... By calling the 'Class'Input for individual components of the
>thing being read? I've played with streams and got them to do what I needed

If its a tagged type, how do you declare an object of the appropriate type on
which to dispatch, when all you have is the saved value of its tag to go by? I
don't think this routine can be implemented (sensibly) in standard Ada. Mind
you, I wouldn't be adverse to someone adding the capability of creating tagged
type objects from just a tag value. There are several other useful applications
for that. But I don't think its there now.

>what can be done or how to do it. The ARM says you can override it with your
>own operation so I'm guessing there must be a use for it.

:-)
That's what I thought too. I brought up this issue here a couple of years ago
(back when I also thought you had to override every IO attribute). I'm pretty
sure the answer I got from Tucker was that it is indeed not particularly useful
to be able to override 'Class'Input.

---
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.

Overriding 'Class'Input (was: List container strawman 1.1)

[Ted Dennison]

In article <9paN7.41146$xS6.69394@www.newsranger.com>, Ted Dennison says...
>That's what I thought too. I brought up this issue here a couple of years ago
>(back when I also thought you had to override every IO attribute). I'm pretty
>sure the answer I got from Tucker was that it is indeed not particularly useful
>to be able to override 'Class'Input.

In the interest of interjecting a rare bit of fact into one of my discussions, I
went back to Deja to look this up. The best I could find was a thread from '99
where Matthew Heaney (*not* Tucker) told me that 'Class'Input comes from 'Input,
and *implied* that it isn't really useful to override 'Class'Input. That's not
particularly helpful to your specific issue though.

You can read the post yourself at
http://groups.google.com/groups?q=%27Class%27Input+group:comp.lang.ada&hl=xx-bork&rnum=1&selm=3803cc6c_1%40news1.prserv.net

---
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: Overriding 'Class'Input (was: List container strawman 1.1)

[Ted Dennison]

In article <ACaN7.41163$xS6.69385@www.newsranger.com>, Ted Dennison says...
>
>You can read the post yourself at
>http://groups.google.com/groups?q=%27Class%27Input+group:comp.lang.ada&hl=xx-bork&rnum=1&selm=3803cc6c_1%40news1.prserv.net

Here's another take on the issue: 
http://groups.google.com/groups?q=%27Class%27Input+group:comp.lang.ada&hl=xx-bork&rnum=7&selm=dewar.892816254%40merv

and:

http://groups.google.com/groups?q=%27Class%27Input+group:comp.lang.ada&start=10&hl=xx-bork&rnum=16&selm=32EE6A33.30C0%40watson.ibm.com

---
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: Overriding 'Class'Input (was: List container strawman 1.1)

[Marin David Condic]

O.K. But this post kind of implies that there is a reason you would want to
implement S'Input instead of S'Read - saying that S'Class'Input is going to
find its way to the S'Input you implement for the specific type. This
degenerates to the S'Read because the compiler will be smart enough to
figure out it should write bounds/discriminants/tags, then call your
replacement for S'Read?

If that's the case, it makes it a lot simpler than I previously had thought.
It also seems to explain where the 'Read and 'Write are useful since after
initially looking at them, I didn't know why I'd want them if they didn't
write out the tags, etc. (The 'Input and 'Output seem to be what you
normally want to use - getting them automagically by defining 'Read and
'Write makes more sense.)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:ACaN7.41163$xS6.69385@www.newsranger.com...
> In article <9paN7.41146$xS6.69394@www.newsranger.com>, Ted Dennison
says...
>
> In the interest of interjecting a rare bit of fact into one of my
discussions, I
> went back to Deja to look this up. The best I could find was a thread from
'99
> where Matthew Heaney (*not* Tucker) told me that 'Class'Input comes from
'Input,
> and *implied* that it isn't really useful to override 'Class'Input. That's
not
> particularly helpful to your specific issue though.
>
> You can read the post yourself at
>
http://groups.google.com/groups?q=%27Class%27Input+group:comp.lang.ada&hl=xx
-bork&rnum=1&selm=3803cc6c_1%40news1.prserv.net
>

Re: Overriding 'Class'Input (was: List container strawman 1.1)

[Ted Dennison]

In article <9u3i3t$211$1@nh.pace.co.uk>, Marin David Condic says...
>It also seems to explain where the 'Read and 'Write are useful since after
>initially looking at them, I didn't know why I'd want them if they didn't
>write out the tags, etc. (The 'Input and 'Output seem to be what you
>normally want to use - getting them automagically by defining 'Read and
>'Write makes more sense.)

Well, if you want to read in a large structure, you'd probably be better off
using 'Read just because there won't be an extra assignment involved. Also, I
don't find 'Input all that useful because you have to have some idea of the size
of the object in order to safely call it anyway. I use it for strings sometimes,
but not for anything else. As for 'Class'whatever: since you have to know the
exact types of all your non-tagged types when you use streams, it isn't really
all that helpful to not have to know the exact type of your tagged types. It
could be useful if you want to dynamicly dispatch on the result, (or for
restoring a hetrogenious array from which you'd like to dynamicly dispacth
later) but I've yet to need that myself. So in practice, I find I mostly use the
simple procedural forms. But perhaps that's just me.

I'll give you this: if it turns out I'm wrong about 'Read being used by 'Input,
I'll add 'Input and 'Output into the strawman as well. It was certinaly my
intention for those to be available too.

---
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: Overriding 'Class'Input (was: List container strawman 1.1)

[Marin David Condic]

Well, you're probably correct about how it works - but now I'm wondering
about what happens inside a hypothetical 'Write or 'Read for a hypothetical
list. The list itself is probably some form of record, with access values to
build a chain of nodes. So internally, you do a 'Write on the record (or the
fields of the record you want to save) then you are going to do 'Writes for
the individual nodes? What if you want the 'Output for the nodes so that any
tags, discriminants, etc end up in the stream? Now you've got a reason for
wanting to have the 'Input and 'Output to be manually constructed? Or does
the magic extend to the compiler knowing that the 'Reads & 'Writes of the
nodes should be converted to 'Inputs and 'Outputs just because you got there
from a 'Input or 'Output? (Can't imagine how!)

IIRC, somewhere between keeping the bounds/discriminants/tags around in the
stream and dynamic allocation and knowing what you've got in the stream and
dispatching on 'Class'Read/'Class'Write, I think you've got a means of
storing and recreating a list of just about anything. I'm just not entirely
convinced that it can be done with overriding the 'Read and 'Write alone.
(Maybe I need to reread some of this stuff, look at code I did some time ago
& do a few experiments.... Hmmmm........)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Ted Dennison" <dennison@telepath.com> wrote in message
news:WzcN7.41321$xS6.69893@www.newsranger.com...
>
> I'll give you this: if it turns out I'm wrong about 'Read being used by
'Input,
> I'll add 'Input and 'Output into the strawman as well. It was certinaly my
> intention for those to be available too.
>

Re: Overriding 'Class'Input (was: List container strawman 1.1)

[Nick Roberts]

In my proposal (V5R1), the types Unbounded_List and Bounded_List are both
definite. I override 'Read and 'Write to: (1) read/write the length (number
of data values); (2) read/write the values in order.

Since the types are definite, 'Input and 'Output simply call 'Read and
'Write respectively (RM95 13.13.2 (18-27)), so they will work correctly
automatically. Since the types are not tagged, there is no question about
'Class'Input or 'Class'Output.

The length is specified as being written by Natural'Write, so it can be
explicitly read and used to dimension a structure (e.g. an array) if
required.

--
Best wishes,
Nick Roberts

Re: List container strawman 1.2

[Thomas Wolf]

Marin David Condic wrote:

> I knew that their *behavior* is defined in terms of 'Read and 'Write, but I
> did not know that you would get them to come along free for the cost of
> defining your own overrides for 'Read and 'Write. I was under the impression
> that you'd still have to make your own procedures and do a for-use. If this
> is not the case, then great - nice to get something as a freebie.
> 
> "Thomas Wolf" <t_wolf@angelfire.com> wrote in message
> news:3C049C06.DF85EF80@angelfire.com...
> >
> > Why? 'Output and 'Input are defined in terms of 'Write and 'Read (see
> > RM 13.13.2), so it generally suffices to define the latter.
> >

The RM defines *more* than just the behavior of, say, 'Output: it defines
the implementation!

The RM says (quoting from RM 13.13.2 (27))

(RM 13.13.2 (25): "Unless overridden by an attribute_definition_clause...")

"S'Output then calls S'Write to write the value of Item to the stream. ..."

It *doesn't* say "S'Output behaves as if it called S'Write..." or some
such!

In fact, all of 'Output, 'Input, 'Class'Output, 'Class'Input,
'Class'Write and 'Class'Read by definition in the RM ultimately call
'Write or 'Read. Hence, if you implement 'Write and 'Read, you *do* get
the others for free.

(Just as you do get "/=" for free if you define "=". I haven't quite
understood why something similar hasn't been defined for the relational
operators: once you've defined "<", the other three (">", "<=", and ">=")
follow automatically: L <= R is (not (R < L)); L >= R is (not (L < R)),
and of course L > R is R < L. Does it maybe have something to do with
floating point?)

The only minor nit I have with the definitions in the RM is that the
class-wide 'Input and 'Output operations are defined to write the tag
by calling String'Output(Ada.Tags.External_Tag (Item'Tag)), and one
thus ends up with both the lower and the upper bound of the string in
the stream, followed by the string content. This wastes space: in my
eyes, it'd suffice to write the *length* of the tag string.

Unfortunately, this cannot be "corrected" by redefining 'Class'Output
and 'Class'Input, because the latter needs, once it has read the tag
and converted it to an internal tag, to dispatch to the 'Input
operation of the type identified by this very internal tag -- and
Ada 95 doesn't provide any way to do this, it just happens
"automagically" in some compiler-specific fashion inside the
default 'Input.

And while I'm on it (I've noticed that this post somehow has turned 
into a list of minor missing features in Ada 95 :-), I also miss an
"is_a" operator. (I am aware of "in", but unless I'm missing something,
it doesn't solve the following problem.)

Consider

   type Something is tagged null record;

   procedure Do_Something (A, B : in out Something'Class);
     -- Whatever 'Do_Something' does, it shall only do it if the type
     -- of B is directly or indirectly derived from the type of A.

I have not found any easy way to do this (not even using Ada.Tags),
except requiring that any type in Something'Class have a primitive
operation

   function Is_A (Test : in Something'Class; Target : in Something)
     return Boolean;

and invoke that from inside 'Do_Something'.

So, if there is

   type Foo is new Something with null record;

   function Is_A (Test : in Something'Class; Target : in Foo)
     return Boolean
   is
   begin
     return Test in Foo'Class;
   end Is_A;

and 

   procedure Do_Something (A, B : in out Something'Class)
   is
   begin
      if Is_A (B, A) then
        ...

then it works. But it would be really nice if one could avoid all
this overhead. My proposal would be to allow 'Class to be applied
to *objects* of tagged or class-wide types. (It currently can be
applied to tagged *types* only.) In that case, I could have just
written

   procedure Do_Something (A, B : in out Something'Class)
   is
   begin
      if B in A'Class then
        ...

Alas, the current RM doesn't allow this...
   
--
---------------------------------------------------------------------
Dr. Thomas Wolf                          e-mail: t_wolf@angelfire.com