Re: Can someone help me understand this queue package?

[Michal Nowak <vinnie@inetia.pl>]

On 01-12-28 at 22:57 Liddle Feesh wrote:

>"Michal Nowak" wrote:

>> Look at John English's book "ADA 95: THE CRAFT OF OBJECT-ORIENTED
>PROGRAMMING"
>> at: http://www.it.bton.ac.uk/staff/je/adacraft/
>
>I'll give it a shot - esp as it's online, and I won't have to take it out
>of the library.

You may even download all zipped files.

>> >Could someone be so kind as to convert the following package into
>> >pseudo-code for me?
>>
>> No :-)).
>> Solution 1.
>> Treat a queue as a simple list (you may abandon Iterators idea for
>> simplicity), with operations Add and Remove.
>> Add is something like Insert at beginning,
>> and Remove is like delete at the end.
>
>Will do... What is Iterators idea?

"ADA 95: THE CRAFT OF OBJECT-ORIENTED PROGRAMMING" - chapter 11
(in particular - 11.4)

>> Solution 2.
>> Take paper, pencil and draw what is happening with pointers (access
>> types) during addition and removal (such as on pictures in chapter 11).
>> Than implement it.
>
>Yes, but what >IS< happening with pointers? I'll have a go.

Ooops, I don't get what you mean by it. Hmm, you create a node, a then
set some variables f access types (pointers) to point you to this node,
and some pointers from this node to point to another node.

    end of queue                       Beginning of queue
        |                                     |
       \|/                                   \|/
        V                                     V
  --------------      ---------------     ----------------
  | Data | Next|--->  | Data | Next |---> | Data | Next |
  --------------      ---------------     ----------------
      Node 3             Node 2               Node 1

Suppose now you add something to the end of the queue.
You create new node (let's call it New_Node) and set its
Next pointer to point to last element in the queue.

      end of queue                      Beginning of queue
       (Tail)                               (Head)
         |                                     |
        \|/                                   \|/
         V                                     V
  --------------      ---------------      ---------------
  | Data | Next|--->  |Data  | Next |---> | Data | Next |
  --------------      ---------------      ---------------
      Node 3             Node 2               Node 1


  --------------
  | Data| Next  |
  ---------------
   New_Node

New_Node.Next := Tail;
Tail          := New_Node;

So now you have something like this:

      end of queue                               Beginning of queue
       (Tail)                                          (Head)
         |                                                |
        \|/                                              \|/
         V                                                V
 -------------     ------------    -------------     --------------
 | Data| Next |-->| Data | Next|-->| Data| Next |-->| Data | Next |
 -------------     -------------   -------------     --------------
    New node        Node 3             Node 2              Node 1


Removal is similar, although you may need to add Prev to node to point for
previous item for convenience (unless you want to go through whole queue to
search for element before the last one).

So if we remove Node_1 element (Node_2 := Node_1.Prev)
Node_2.next := null;
Head        := Node_2;

Is this what you were looking for?

>> BTW it looks like a homework or something. Do you want to stay with Ada
>> for a longer time, or just write the program, pass the subject, and
>forget?
>
>I like the principals of ADA - it'll probably be something I'll stick with
>and have to learn. I'm trying to read it as part of my degree;

Great. So you should know a secret - it is Ada :-))

>of course
>ADA
>is quite a good skill to learn; esp. with the industries in my local area.

I may envy you that...

>> However, good luck and don't break down,
>
>I think I'm about to cry...

Oh, boy, don't joke ;-))

Mike