Re: Doubly Linked List

Re: Doubly Linked List

[Robert Kitzberger]

lorenzen@osiris.cso.uiuc.edu (John Lorenzen) writes:

>I am not a student looking for code for an assignment. I work for USACERL am
>am new to the ADA world. I have a background in C/C++ and I've been told
>that the ONE good thing about ADA is the code reusablity [...]

The Net Police catch the wrong person; it's a sad story oft told. 

In any event, here's an extraction from my most recent copy of the
FAQ (old timers: remember the comp.lang.ada FAQ? ;-)

      Mirror of Ada Software Repository: wuarchive.wustl.edu
        Internet address: 128.252.135.4
      AJPO and AdaIC repository: ajpo.sei.cmu.edu
        Internet address: 128.237.2.253
      Source for aflex and ayacc: liege.ics.uci.edu (~ftp/pub/irus)
        Internet address: 128.195.1.5, 128.195.13.1
      European Repository: cnam.cnam.fr
        Internet address: 192.33.159.6
      STARS (Software Technology for Adaptable, Reliable Systems):
      source.asset.com
        Internet Address: 192.131.125.10
      Unisys/STARS source: stars.rosslyn.unisys.com
        Internet Address: 128.126.164.2


The Public Ada Library is out on wunet.wustl.edu.


Also from the FAQ:

      Booch, G.
      Software Components with Ada.
      Benjamin Cummings, 1987.
      This work is an encyclopedic presentation of data structure
      packages from Booch's OOD point of view.  It is great for those
      who love taxonomies.  It's not for the faint-hearted, because
      the volume of material can be overwhelming.  It could serve as a
      text for an advanced data structures course, but it's thin in
      "big O" analysis and other algorithm-theory matters.  The book
      is keyed to the (purchasable) Booch Components.



	.Bob.
--
Bob Kitzberger                          Internet:   rlk@rational.com
Rational, Grass Valley, CA              CompuServe: 70743,1550

Doubly linked list.

[Matt Tyler]

I'm having trouble implementing a Doubly linked list in ada.

My procedure to add a new singly linked record to the list is (body only)

List:=new Box'(V,List);

where V is an integer and List is an access type to box.

I don't understand how to set another access type in the record to the
previous record on the list. Can anyone help??

P.S is there a comp.lang.ada faq ???????????

Cheers,

Matt Tyler

Re: Doubly linked list.

[Tucker Taft]

Matt Tyler (matt_tyler@hotmail.com) wrote:

: I'm having trouble implementing a Doubly linked list in ada.

: My procedure to add a new singly linked record to the list is (body only)

: List:=new Box'(V,List);

: where V is an integer and List is an access type to box.

: I don't understand how to set another access type in the record to the
: previous record on the list. Can anyone help??

With a doubly linked list, each list element has both a "next" and
a "prev" component, in general.   You need to initialize both.  In
general, one will be null in the new element.

The following will accomplish the job:

    -- Insert on front of list
    List := new Box'(V, Next => List, Prev => null);  

    if List.Next /= null then
        -- Make old "first" element point back to new "first"
        List.Next.Prev := List;  
    end if;

: P.S is there a comp.lang.ada faq ???????????

Try www.adahome.com.

: Cheers,

: Matt Tyler

--
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Intermetrics, Inc.  Burlington, MA  USA
An AverStar Company (www.averstar.com)

Re: Doubly linked list.

[news.oxy.com]

Matt Tyler wrote in message <7560vn$21e@romeo.logica.co.uk>...
>I'm having trouble implementing a Doubly linked list in ada.
>
>My procedure to add a new singly linked record to the list is (body only)
>
>List:=new Box'(V,List);
>
>where V is an integer and List is an access type to box.
>
>I don't understand how to set another access type in the record to the
>previous record on the list. Can anyone help??
>
>P.S is there a comp.lang.ada faq ???????????
>
>Cheers,
>
>Matt Tyler
>
>

There is no need to reinvent the wheel ( of course if you do not need to
have smth very specific).
Have a look at the ADA95 implementation of the Booch components
 http://www.pogner.demon.co.uk/components/bc/ ).
Everything is already at hand (including all types of  linked lists). Just
use it. Also this is very good example of ADA95 programming.

Regards,
Vladimir Olensky (Vladimir_Olensky@oxy.com)
Telecommunication specialist,
Occidental C.I.S. Service, Inc. ( www.oxy.com )
Moscow,
Russia.

Re: Doubly linked list.

[Simon Wright]

"news.oxy.com" <Vladimir_Olensky@oxy.com> writes:

> Have a look at the ADA95 implementation of the Booch components
>  http://www.pogner.demon.co.uk/components/bc/ ).
> Everything is already at hand (including all types of  linked lists). Just
> use it. Also this is very good example of ADA95 programming.

Thanks for that, Vladimir! (from me and the team)

One small point, which I'm not sure how to address; the BCs have a
perhaps surprising take on manipulating lists.

The following comment is a direct transliteration of the C++ words
(and it shows in places!  "member function" indeed ..):

  -- Unreachable items are those that belong to a list or a sublist whose
  -- head is not designated by any alias. For example, consider the list (A
  -- B C), with the head of the list designated by L1. L1 initially points
  -- to the head of the list, at item A. Invoking the member function Tail
  -- on L1 now causes L1 to point to item B. Because A is now considered
  -- unreachable, the storage associated with item A is reclaimed; the
  -- predecessor of B is now null. Similarly, consider the list (D E F),
  -- with the head of the list designated by both L1 and L2. Both L1 and L2
  -- are aliases that initially point to the head of the list at item
  -- D. Invoking the member function Tail on L1 now causes L1 to point to
  -- item E; L2 is unaffected. Suppose we now invoke the member function
  -- clear on L2. The semantics of this operation are such that only
  -- unreachable items are reclaimed. Thus, the storage associated with
  -- item D is reclaimed, because it is no longer reachable; L2 is now
  -- null, and the predecessor of E is now null. Items E and F are not
  -- reclaimed, because they are reachable through L1.

I think this is not in fact that far from a Lisp approach, but at
least one user has been bitten by it (not helped by there being an
effor which meant that parts of the list were sometimes reachable when
they shouldn't have been).

STk> (define foo '(a b c))
STk> (define bar foo)
STk> (set! foo (cdr foo))
STk> foo
(b c)
STk> bar
(a b c)

Of course, there's no easy equivalent of the doubly-linked list ..

Re: Doubly linked list.

[news.oxy.com]

Simon,

It is a great pleasure for me to hear that I was able to help.

What is regarding quote from Bc.Containars.Lists it sounds quite natural for
me.
Bc implementation of doubly linked lists is a chain of nodes each containing
pointers to prev. and next nodes as well as reference to the object denoted
by that node (this object may be any kind of object including list, tree
,buffer, queue e.t.c.). Such object may belong to more than one list.
Moreover it may belong to any other kind of structure (e.g. tree, list
etc.).
When applying Clear function to the list it deletes nodes in the chain
denoted  only by the list to which this function was applied. Any object
that is referenced by any node in this particular chain is deleted only if
it is not referenced form any other structure to which it may belong. It is
also possible that the same object may referenced by the different elements
of the same list. This is extremely flexible. Such flexibility is achieved
through the use of controlled types.
To me this is absolutely right approach.
As BC is free software in ADA it is possible to build something  more
complicated based on it or use it as software patterns which may be easily
modified for particular needs.

As a matter of fact I am not software engineer. I am radio-electronic system
engineer (all kind of systems) so I am doing some programming when I need to
do it for some particular purpose and also for my pleasure.
If there are some specific question regarding BC you can ask Simon Wright
 simon@pogner.demon.co.uk ) who is maintaining it.


Regards,
Vladimir Olensky (Vladimir_Olensky@oxy.com)
Telecommunication specialist,
Occidental C.I.S. Service, Inc. ( www.oxy.com )
Moscow,
Russia.



Simon Wright wrote in message ...
>"news.oxy.com" <Vladimir_Olensky@oxy.com> writes:
>
>> Have a look at the ADA95 implementation of the Booch components
>>  http://www.pogner.demon.co.uk/components/bc/ ).
>> Everything is already at hand (including all types of  linked lists).
Just
>> use it. Also this is very good example of ADA95 programming.
>
>Thanks for that, Vladimir! (from me and the team)
>
>One small point, which I'm not sure how to address; the BCs have a
>perhaps surprising take on manipulating lists.
>
>The following comment is a direct transliteration of the C++ words
>(and it shows in places!  "member function" indeed ..):
>
>  -- Unreachable items are those that belong to a list or a sublist whose
>  -- head is not designated by any alias. For example, consider the list (A
>  -- B C), with the head of the list designated by L1. L1 initially points
>  -- to the head of the list, at item A. Invoking the member function Tail
>  -- on L1 now causes L1 to point to item B. Because A is now considered
>  -- unreachable, the storage associated with item A is reclaimed; the
>  -- predecessor of B is now null. Similarly, consider the list (D E F),
>  -- with the head of the list designated by both L1 and L2. Both L1 and L2
>  -- are aliases that initially point to the head of the list at item
>  -- D. Invoking the member function Tail on L1 now causes L1 to point to
>  -- item E; L2 is unaffected. Suppose we now invoke the member function
>  -- clear on L2. The semantics of this operation are such that only
>  -- unreachable items are reclaimed. Thus, the storage associated with
>  -- item D is reclaimed, because it is no longer reachable; L2 is now
>  -- null, and the predecessor of E is now null. Items E and F are not
>  -- reclaimed, because they are reachable through L1.
>
>I think this is not in fact that far from a Lisp approach, but at
>least one user has been bitten by it (not helped by there being an
>effor which meant that parts of the list were sometimes reachable when
>they shouldn't have been).
>
>STk> (define foo '(a b c))
>STk> (define bar foo)
>STk> (set! foo (cdr foo))
>STk> foo
>(b c)
>STk> bar
>(a b c)
>
>Of course, there's no easy equivalent of the doubly-linked list ..

Re: Doubly linked list.

[Simon Wright]

"news.oxy.com" <Vladimir_Olensky@oxy.com> writes:

> What is regarding quote from Bc.Containars.Lists it sounds quite
> natural for me.

In the BCs, you can traverse a doubly linked list both ways, but only
if you've kept a handle on the head of the list. This has been found
surprising by at least one person!

> Bc implementation of doubly linked lists is a chain of nodes each
> containing pointers to prev. and next nodes as well as reference to
> the object denoted by that node (this object may be any kind of
> object including list, tree ,buffer, queue e.t.c.). Such object may
> belong to more than one list.  Moreover it may belong to any other
> kind of structure (e.g. tree, list etc.).

The BCs work by taking copies of things (the generic parameter Item is
private), so to get the semantics you're talking about you need to use
(smart) pointers.

>                            If there are some specific question
> regarding BC you can ask Simon Wright simon@pogner.demon.co.uk ) who
> is maintaining it.

I'll ask him then ... :-)

Re: Doubly linked list.

[news.oxy.com]

Simon Wright wrote in message ...
>"news.oxy.com" <Vladimir_Olensky@oxy.com> writes:
>
>
>> Bc implementation of doubly linked lists is a chain of nodes each
>> containing pointers to prev. and next nodes as well as reference to
>> the object denoted by that node (this object may be any kind of
>> object including list, tree ,buffer, queue e.t.c.). Such object may
>> belong to more than one list.  Moreover it may belong to any other
>> kind of structure (e.g. tree, list etc.).
>
>The BCs work by taking copies of things (the generic parameter Item is
>private), so to get the semantics you're talking about you need to use
>(smart) pointers.
>



Yes, I agree.

Function Create in BC.Suppor.Nodes makes a copy of the Item passed to it so
the node after creation contains a copy of the Item, which is aliased. This
means that the Node.Element, which is the copy of the Item, may be
referenced from somewhere else and in this case it should not be deleted by
Clear function. Proper behavior of the Clear function in this case should be
to delete the node belonging to the list do not touching it's Element. After
that Node.Elememt should continue to live as separate entity that does not
belong any more to the deleted list. Anyway I did not investigate this issue
so deep. May be someone who will be working with this more closely will
analyze the BC code and test this kind of things.

I was recently experimenting a little bit with controlled types and such
(smart)pointers which in turn are also controlled types so I was thinking
regarding above mentioned issues using such categories. As a matter of fact
it gives extreme level of flexibility to the BC structures.

Sorry for mixing together this two things and I am glad that you noted this
inconsistency.



Regards,
Vladimir Olensky (Vladimir_Olensky@oxy.com)
Telecommunication specialist,
Occidental C.I.S. Service, Inc. ( www.oxy.com )
Moscow,
Russia.

Re: Doubly Linked List

[John Lorenzen]

I am not a student looking for code for an assignment. I work for USACERL am
am new to the ADA world. I have a background in C/C++ and I've been told
that the ONE good thing about ADA is the code reusablity, now I am working
on the first project in ADA transferring a system we wrote in C++ and do not
have the time to write all of the little data structures in ada while also
getting a hold on the language, so I thought that I would post a message and
see if I could get some help from the ADA community, now I don't know if is
was such a good idea. I probably should have stated my hold story in the
first message.

Re: Doubly Linked List

[cis.ohio-state.edu!math.ohio-state.edu!caen!usenet.cis.ufl.edu!eng.ufl.ed]

In article <4315.2c9f6315@vger.nsu.edu>, g_harrison@vger.nsu.edu (George C. Har
rison, Norfolk State University) writes:
|> In article <1993Sep19.225918.7196@seas.gwu.edu>, mfeldman@seas.gwu.edu (Mich
ael Feldman) writes:
|> > In article <27dgoc$814@vixen.cso.uiuc.edu> lorenzen@osiris.cso.uiuc.edu (J
ohn Lorenzen) writes:
|> >>I am in need of a doubly linked list package if you know where I might fin
d
|> >>one at I would greatly appreciate it. It must be able to handle multiple
|> >>lists.
|> > 
|> > Hmmm - is it impertinent for me to ask whether this is a class assignment?
|> > If so, does your teacher know you're on the net looking for the solution?
|> > 
|> > Mike Feldman
|> 
|> I don't know, Mike, but I did send him a WONDERFUL one... however it bounced
|> all over the place and was never delivered.  I usually can pick up on a requ
est
|> for an assignment; I guess I was just too proud of this package.
|> 
|> George
|> 
|> +---------------------------------------------------------------------------
-+
|> | George C. Harrison            | PHONE : (804) 683-8654  | "Ada Spoken Here
"|
|> | Professor of Computer Science | FAX   : (804) 683-9229  +-----------------
-+
|> | Norfolk State University      | g_harrison@vger.nsu.edu |                 
 |
|> | 2401 Corprew Avenue           +-------------------------+                 
 |
|> | Norfolk VA 23504              | loop exit when RE_TIRED; end loop;        
 |
|> +-------------------------------+-------------------------------------------
-+

As a student (currently taking data structures), this sounds to me as
if it is an assignment. ANY student (IMHO), who resorts to this method
of completing a task only hurts themselves. They won't get a solid
foundation with which they will need to build upon later (I wouldn't want
to hire them). I believe that if you having problems this arena is the best pla
ce to get some assistance. If you are working on an assignment say so and provi
de some code and ask where you may be going wrong, don't expect them to give yo
u the solution. By providing code you are at least working on it yourself and o
thers will gladly provide the needed direction with giving
detailed information.

Vince

Re: Doubly Linked List

[George C. Harrison, N orfolk State University]

In article <1993Sep19.225918.7196@seas.gwu.edu>, mfeldman@seas.gwu.edu (Michael
 Feldman) writes:
> In article <27dgoc$814@vixen.cso.uiuc.edu> lorenzen@osiris.cso.uiuc.edu (John
 Lorenzen) writes:
>>I am in need of a doubly linked list package if you know where I might find
>>one at I would greatly appreciate it. It must be able to handle multiple
>>lists.
> 
> Hmmm - is it impertinent for me to ask whether this is a class assignment?
> If so, does your teacher know you're on the net looking for the solution?
> 
> Mike Feldman

I don't know, Mike, but I did send him a WONDERFUL one... however it bounced
all over the place and was never delivered.  I usually can pick up on a request
for an assignment; I guess I was just too proud of this package.

George

+----------------------------------------------------------------------------+
| George C. Harrison            | PHONE : (804) 683-8654  | "Ada Spoken Here"|
| Professor of Computer Science | FAX   : (804) 683-9229  +------------------+
| Norfolk State University      | g_harrison@vger.nsu.edu |                  |
| 2401 Corprew Avenue           +-------------------------+                  |
| Norfolk VA 23504              | loop exit when RE_TIRED; end loop;         |
+-------------------------------+--------------------------------------------+

Re: Doubly Linked List

[Gregory Aharonian]

>In article <27dgoc$814@vixen.cso.uiuc.edu> lorenzen@osiris.cso.uiuc.edu (John 
Lorenzen) writes:
>>I am in need of a doubly linked list package if you know where I might find
>>one at I would greatly appreciate it. It must be able to handle multiple
>>lists.
>
>Hmmm - is it impertinent for me to ask whether this is a class assignment?
>If so, does your teacher know you're on the net looking for the solution?
>
>Mike Feldman

Mike,
	Give the guy the benefit of the doubt.  Maybe he is taking a course
on software reuse :-)

Greg
-- 
**************************************************************************
 Greg Aharonian                                      srctran@world.std.com
 Source Translation & Optimization                            617-489-3727
 P.O. Box 404, Belmont, MA 02178

Re: Doubly Linked List

[David Tannen]

Check w/ Asset @ librarian@source.asset.com.  I am pretty sure such 
a package exists in their library.

---
David Tannen
tannend@source.asset.com
tannen@tigger.geg.mot.com
----------------------------------------------------------------------
-- "Dependance on wizardry to mitigate the fundamental limitations
--  of software is called 'hacking'."  Grady Booch.
--
-- Developing MS-Windows applications often requires 'wizardry'.
----------------------------------------------------------------------

Re: Doubly Linked List

[agate!howland.reston.ans.net!europa.eng.gtefsd.com!darwin.sura.net!seas.g]

In article <27dgoc$814@vixen.cso.uiuc.edu> lorenzen@osiris.cso.uiuc.edu (John L
orenzen) writes:
>I am in need of a doubly linked list package if you know where I might find
>one at I would greatly appreciate it. It must be able to handle multiple
>lists.

Hmmm - is it impertinent for me to ask whether this is a class assignment?
If so, does your teacher know you're on the net looking for the solution?

Mike Feldman
------------------------------------------------------------------------
Michael B. Feldman -  co-chair, SIGAda Education Committee
Professor, Dept. of Electrical Engineering and Computer Science
The George Washington University -  Washington, DC 20052 USA
202-994-5253 (voice) - 202-994-0227 (fax) - mfeldman@seas.gwu.edu (Internet)
"We just changed our CONFIG.SYS, then pressed CTRL-ALT-DEL. It was easy."
-- Alexandre Giglavyi, director Lyceum of Information Technologies, Moscow.
------------------------------------------------------------------------