Can someone help me understand this queue package?

Can someone help me understand this queue package?

[Liddle Feesh]

Essentially, I have a spec, and I'm trying my damndest to write a body for
it - and though I've tried (hence my previous two posts here), I'm still
quite stuck, with only a very basic stub compiling.

Does anyone have any decent queue tutorials? I've tried looking for a few on
the net - adapower, an ada program (console), and several books... However
when it comes to queues I'm none-the-wiser...

Looking at the pointers - is this some sort of linked list?

Could someone be so kind as to convert the following package into
pseudo-code for me?

Thanks in advance

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)





 package queue_package is

 -- queue type definition
  TYPE queue is LIMITED PRIVATE;
   empty_queue   :   EXCEPTION;

 procedure  initialise   (q:  in out queue);
 -- function mode 'in' added. Although the mode of all parameters must be
'in' for
 -- functions, it's always a good idea to show explicitly.
 function  is_empty_queue  (q:  in queue) return boolean;
 procedure  add    (n:  in  integer;  q:  in out queue);
 procedure  remove   (n:  out integer;  q:  in out queue);
 --remove raises the exception "empty-queue" if applied to an empty queue

 PRIVATE
 TYPE node;
 TYPE link is ACCESS node;   --ACCESS is a pointer type

 TYPE node is RECORD
    value   :   integer;
    next    :   link :=NULL;
 END RECORD;

  TYPE queue is RECORD
    head :   link;
    tail :   link;
 END RECORD;

END queue_package;

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

X-No-Archive: Yes

Re: Can someone help me understand this queue package?

[Michal Nowak]

>Essentially, I have a spec, and I'm trying my damndest to write a body for
>it - and though I've tried (hence my previous two posts here), I'm still
>quite stuck, with only a very basic stub compiling.
>
>Does anyone have any decent queue tutorials? I've tried looking for a few
>on
>the net - adapower, an ada program (console), and several books... However
>when it comes to queues I'm none-the-wiser...

Look at John English's book "ADA 95: THE CRAFT OF OBJECT-ORIENTED PROGRAMMING"
at: http://www.it.bton.ac.uk/staff/je/adacraft/

Part Two - abstract data types is what you should read. Just drop writting code
for the moment, relax and read it carefully. Athough there is example about
a list, you should have trouble write a spec for your queue. If you are in big
hurry, start from chapter 11.

You may look also at:
http://burks.bton.ac.uk/burks/language/ada/
"Object Oriented Software in Ada 95 Second Edition",
by Michael Smith.

>Looking at the pointers - is this some sort of linked list?

Linked list may be implemented using pointers.


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

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?

However, good luck and don't break down,
-Mike

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:
> >Essentially, I have a spec, and I'm trying my damndest to write a body
for
> >it - and though I've tried (hence my previous two posts here), I'm still
> >quite stuck, with only a very basic stub compiling.
> >
> >Does anyone have any decent queue tutorials? I've tried looking for a few
> >on
> >the net - adapower, an ada program (console), and several books...
However
> >when it comes to queues I'm none-the-wiser...
>
> 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.

> Part Two - abstract data types is what you should read. Just drop writting
code
> for the moment, relax and read it carefully. Athough there is example
about
> a list, you should have trouble write a spec for your queue. If you are in
big
> hurry, start from chapter 11.
>
> You may look also at:
> http://burks.bton.ac.uk/burks/language/ada/
> "Object Oriented Software in Ada 95 Second Edition",
> by Michael Smith.

I'll do that one too ;)

> >Looking at the pointers - is this some sort of linked list?
>
> Linked list may be implemented using pointers.

True - but with reference to the spec - some sort of linked list?

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

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

> 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; of course ADA
is quite a good skill to learn; esp. with the industries in my local area.

> However, good luck and don't break down,

I think I'm about to cry...


--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Michal Nowak]

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

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:
> >Essentially, I have a spec, and I'm trying my damndest to write a body
for
> >it - and though I've tried (hence my previous two posts here), I'm still
> >quite stuck, with only a very basic stub compiling.
> >
> >Does anyone have any decent queue tutorials? I've tried looking for a few
> >on
> >the net - adapower, an ada program (console), and several books...
However
> >when it comes to queues I'm none-the-wiser...
>
> 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 can't get there... can you?

If you have it locally, and have a few seconds and a teeny bit of bandwidth
to spare, can you email the page(s) to me?

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:
> >Essentially, I have a spec, and I'm trying my damndest to write a body
for
> >it - and though I've tried (hence my previous two posts here), I'm still
> >quite stuck, with only a very basic stub compiling.
> >
> >Does anyone have any decent queue tutorials? I've tried looking for a few
> >on
> >the net - adapower, an ada program (console), and several books...
However
> >when it comes to queues I'm none-the-wiser...
>
> 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 can't get to http://www.it.bton.ac.uk/staff/je/adacraft/part2.htm ... can
you?

If you have it locally, and have a few seconds and a teeny bit of bandwidth
to spare, can you email the page(s) to me?

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:
> >Essentially, I have a spec, and I'm trying my damndest to write a body
for
> >it - and though I've tried (hence my previous two posts here), I'm still
> >quite stuck, with only a very basic stub compiling.
> >
> >Does anyone have any decent queue tutorials? I've tried looking for a few
> >on
> >the net - adapower, an ada program (console), and several books...
However
> >when it comes to queues I'm none-the-wiser...
>
> 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 can't get to http://www.it.bton.ac.uk/staff/je/adacraft/part2.htm ... can
you?

If you have it locally, and have a few seconds and a teeny bit of bandwidth
to spare, can you email the page(s) to me?

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

Now that's a bug within OE that I've never seen before!


--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Liddle Feesh" wrote:

> I can't get to http://www.it.bton.ac.uk/staff/je/adacraft/part2.htm ...
can
> you?

I'm now using google's cache server. Not ideal, but much better than BT's
(British Telecom's) offerings:
http://www.google.com/search?q=cache:i4dwpbMsB_U:www.it.bton.ac.uk/staff/je/
adacraft/part2.htm+&hl=en


--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[martin.m.dowie]

> > 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 can't get there... can you?
>
> If you have it locally, and have a few seconds and a teeny bit of
bandwidth
> to spare, can you email the page(s) to me?

I expect Brighton Uni have their machines down over the feastive period -
save
a few pennies on the 'leccy meter! :-)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"martin.m.dowie" 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 can't get there... can you?
> >
> > If you have it locally, and have a few seconds and a teeny bit of
> bandwidth
> > to spare, can you email the page(s) to me?
>
> I expect Brighton Uni have their machines down over the feastive period -
> save
> a few pennies on the 'leccy meter! :-)

When students want to access them?

Gah - I'd expect at least a mirror to somewhere!


--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:

> You may even download all zipped files.

If you have them, would you mind emailing them to me, since the website is
currently down.

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

I'll see if that particular section is on Google's Cache.

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

Some lovely diagrams :) Best viewed in fixed-point font though!

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

Uh - yes, and I couldn't have asked for a better, more clear explanation. I
hope this sits on Google's archive for a long time to come to help out all
those other hapless newbies!

> >> 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 :-))

Another Difficult Addon. or A Dysfunctional Analogy ;)

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

It's quite common here. Check out www.jobserve.co.uk for Ada - I think this
should bring back some interesting reading.

> >> However, good luck and don't break down,
> >
> >I think I'm about to cry...
>
> Oh, boy, don't joke ;-))

*Grabs some Gin and Tonic*


--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Michal Nowak]

On 01-12-29 at 19:37 Liddle Feesh wrote:

>"Michal Nowak" wrote:
>
>> You may even download all zipped files.
>
>If you have them, would you mind emailing them to me, since the website is
>currently down.

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Any hint how to decode it? What alghoritm have you used
Vigenere? substitution? rotation? modulus? Sorry, but
I'm doing some data analysis from to days for labs and
my brain is rather close to expolosion, so I got no enough
brain power to sit and think about a way to decode your
mail address...
But, sure, I got the zip files.

See you,
Mike
-----------------------------------------
                             ____|
                             \%/ |~~\
  O                                  |
 o>>        Mike Nowak               |
 T                                   |
/ >       vinnie@inetia.pl           |
http://www.geocities.com/vinnie14pl _|__

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:

> Any hint how to decode it? What alghoritm have you used
> Vigenere? substitution? rotation? modulus? Sorry, but
> I'm doing some data analysis from to days for labs and
> my brain is rather close to expolosion, so I got no enough
> brain power to sit and think about a way to decode your
> mail address...
> But, sure, I got the zip files.

My email address is :
MikeLWilsonUNDERPANTS@bcs.org.uk

However, you need to remove the word UNDERPANTS to re-ply. Get it?

I know, it was supposed to be a funny way to protect my email address from
spam.

If you could email me the files I would be really happy!

Hope you have a very happy new year - and that your basketball goes well.

Kind Regards,

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:

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

Okay. In the example given from that page - adding a new "Node" or
"Appoinment" would be done using the procedure (in my example) "Add".

This procedure is listed as follows:

 procedure add (n:  in integer;  q:  in out queue) is
 begin
  null; -- Do nothing
 end add;

Now - in the example from the site:

    New_Item := new Appointment_Record;
    if Current /= null then        -- insert after another appointment
        New_Item.Next := Current.Next;
        Current.Next  := New_Item;
    else                           -- insert at start of list
        New_Item.Next := Diary.First;
        Diary.First   := New_Item;
    end if;


But the problem comes when you think, what is "New_Item"? Is it a function
call? No - it can't be, no parameters. Is it an instance of a record? Maybe,
but my compiler (OE) throws up the error "Direct name, New_Item is not
visable" leading me to believe that I haven't instantiated the name
somewhere. But what does it instantiate to? And surely when setting up
"New_Item", you want to fill it with data - which happens in the example
above. But how can you fill it with data when it doesn't exist...?

Even if I wrote:

New_Item := new Node;

This would still fall over with the same error.


How do I create a new node, and point the 'next' value to the 'value' of the
next node? I know how this is done on paper...

V = Value
N = Next

[V|N]--->[V|N]--->[V|N] -- etc. The last node containing 'null' for the
'next'.

But - HOW do I do this?

Surely:

New_Item := new Node;

would work, then all I would have to do is :
New_Item.Next := Current.Next;
Current.Next := New_Item;

(as from the website)

But the values for New_Item and Current have not been instantiated. In the
example they are not instantiated. In every book I read they are never
instantiated. What am I missing here?

--
Liddle Feesh
 '  O 0 o <"//><  ' o'^
(Remove UNDERPANTS to reply)

Re: Can someone help me understand this queue package?

[Michal Nowak]

On 01-12-29 at 22:02 Liddle Feesh wrote:

>"Michal Nowak" wrote:
>
>> "ADA 95: THE CRAFT OF OBJECT-ORIENTED PROGRAMMING" - chapter 11
>> (in particular - 11.4)
>
>Okay. In the example given from that page - adding a new "Node" or
>"Appoinment" would be done using the procedure (in my example) "Add".
>
>This procedure is listed as follows:
>
> procedure add (n:  in integer;  q:  in out queue) is
> begin
>  null; -- Do nothing
> end add;
>
>Now - in the example from the site:
>
>    New_Item := new Appointment_Record;
>    if Current /= null then        -- insert after another appointment
>        New_Item.Next := Current.Next;
>        Current.Next  := New_Item;
>    else                           -- insert at start of list
>        New_Item.Next := Diary.First;
>        Diary.First   := New_Item;
>    end if;
>
>
>But the problem comes when you think, what is "New_Item"? Is it a function
>call? No - it can't be, no parameters. Is it an instance of a record?
>Maybe,
>but my compiler (OE) throws up the error "Direct name, New_Item is not
>visable" leading me to believe that I haven't instantiated the name
>somewhere. But what does it instantiate to? And surely when setting up
>"New_Item", you want to fill it with data - which happens in the example
>above. But how can you fill it with data when it doesn't exist...?
>
>Even if I wrote:
>
>New_Item := new Node;
>
>This would still fall over with the same error.


Here is your package spec:
-------------------------------
package queue_package is

  TYPE queue is LIMITED PRIVATE;
   empty_queue   :   EXCEPTION;  -- !! FIRST ERROR REPORTED HERE
          -- !! SECOND ERROR REPORTED HERE
  procedure initialise (q:  in out queue);
  function is_empty_queue (q:  queue) return boolean;
  procedure add(n:  in integer;  q:  in out queue);
  procedure remove(n:  out integer;  q: in out queue);
  --remove raises the exception "empty-queue" if applied to an empty queue

  PRIVATE
  TYPE node;
  TYPE link is ACCESS node;   --ACCESS is a pointer type
  TYPE node is RECORD
    value   :     integer;
    next    :   link :=NULL;
  END RECORD;

  TYPE queue is RECORD
    head :  link;
    tail :  link;
  END RECORD;

END queue_package;
----------------------------

Look at the line where you defined access type to node (you even marked
it with comment).

You had errors, because you did not declared a variable of this type.
Try now:

> procedure add (n:  in integer;  q:  in out queue) is
    New_Item : Link;   --declare a variable of link type
> begin
    New_Item := new node;

    --now set appriopriate fields in New_Item,
    --set Head and Tail for queue, and should be OK.

>  null; -- Do nothing
> end add;

>
>How do I create a new node, and point the 'next' value to the 'value' of
>the
>next node? I know how this is done on paper...

link is access type to node. So speaking in C language, it should point
to element of type node. In your queue you have components Head and Tail,
that should point to first and last element in the queue. They are of the
same type as New_Item is. So:

New_Item.Next := Tail;     --next points you to element, which is still
                           --considered to be on the end of the queue
Tail          := New_Item; --now the last element is the one you created.

Was that helpful?
Mike
-----------------------------------------
                             ____|
                             \%/ |~~\
  O                                  |
 o>>        Mike Nowak               |
 T                                   |
/ >       vinnie@inetia.pl           |
http://www.geocities.com/vinnie14pl _|__

Re: Can someone help me understand this queue package?

[Liddle Feesh]

"Michal Nowak" wrote:

> Look at the line where you defined access type to node (you even marked
> it with comment).
>
> You had errors, because you did not declared a variable of this type.
> Try now:
>
> > procedure add (n:  in integer;  q:  in out queue) is
>     New_Item : Link;   --declare a variable of link type
> > begin
>     New_Item := new node;
>
>     --now set appriopriate fields in New_Item,
>     --set Head and Tail for queue, and should be OK.

No - after adding those lines the package spec no longer compiles. I don't
understand why you want to add those lines in there.

Errors generated are : "Direct Name, Link, is not visable, Ignoring future
references",  and "Parse error expecting declaration, got BEGIN,
Skipping..."

[snip]
> >How do I create a new node, and point the 'next' value to the 'value' of
> >the
> >next node? I know how this is done on paper...
>
> link is access type to node. So speaking in C language, it should point
> to element of type node. In your queue you have components Head and Tail,
> that should point to first and last element in the queue. They are of the
> same type as New_Item is. So:
>
> New_Item.Next := Tail;     --next points you to element, which is still
>                            --considered to be on the end of the queue
> Tail          := New_Item; --now the last element is the one you created.

Link is access type to node - okay
Should point to element of type node - okay (HOW is this done?)
Queue is made up of a Head, and the remainder(Queue). Tail in this case will
point to the last element, although this is not strictly correct.

New_Item.Next := Tail   -- Next is the pointer to the value section of the
next element (node). I see - you assign "Tail" to the New_Item's NEXT
pointer. Excellent. Thanks.

Tail := New_Item -- Now, this I don't understand. You are assigning a new
element to the tail?

----

What I don't get - from the original post, is what is the syntax for
manipulating this queue stuff, and where do I put it? I'm completely stuck
when it comes to these three files - 1. Test Harness, 2. Package Body, and
3. Package Spec.

Okay - so I can call procedures and functions in the spec from the from the
test harness, but what do I do? I mean - I've added the line

add;

into a main menu in the test harness - to call the procedure 'add' - which
currrently has just a 'null;' in it. It doesn't do anything!

Thanks for your help though,

Mike

Re: Can someone help me understand this queue package?

[Michal Nowak]

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

>> You had errors, because you did not declared a variable of this type.
>> Try now:
>>
>> > procedure add (n:  in integer;  q:  in out queue) is
>>     New_Item : Link;   --declare a variable of link type
>> > begin
>>     New_Item := new node;
>>
>>     --now set appriopriate fields in New_Item,
>>     --set Head and Tail for queue, and should be OK.
>
>No - after adding those lines the package spec no longer compiles. I don't
>understand why you want to add those lines in there.
>

>How do I create a new node, and point the 'next' value to the 'value' of
>the
>next node? I know how this is done on paper...

OK, here is lightweighted queue, very simple and basic. I compiled it with GNAT.

------Spec ----------------
package Queues is
    TYPE Queue_Type is LIMITED PRIVATE;

    Empty_Queue   :   EXCEPTION;

    procedure Initialise (q:  in out Queue_Type);
    function is_empty_queue (q:  Queue_Type) return boolean;
    procedure add(n:  in integer;  q:  in out Queue_Type);
    procedure remove(n:  out integer;  q: in out Queue_Type);
  --remove raises the exception "empty-queue" if applied to an empty queue

    PRIVATE
        TYPE Node;
        TYPE Link is ACCESS Node;   --ACCESS is a pointer type
        TYPE Node is RECORD
            Value : Integer;
            Next  : Link := null;
            Prev  : Link := null;
        END RECORD;

        TYPE Queue_Type is RECORD
            Number_Of_Elements : Natural := 0;
            Head               : Link := null;
            Tail               : Link := null;
        END RECORD;

END Queues;
----------------------------------------------------

------------Body -----------------------------------
with Ada.Unchecked_Deallocation;

package body Queues is

    procedure Delete_Node is new Ada.Unchecked_Deallocation(Node, Link);

    procedure Add (n:  in integer;  q:  in out Queue_Type) is
        New_Item : Link;
    begin
        New_Item       := new Node;
        New_Item.Value := n;

        if Is_Empty_Queue(q) then
            -- this is first element in queue, so Head must point
            -- to it. Tail will be set later.
            q.Head := New_Item;
        else
            -- if there are other elements in queue (so Head points
            -- to some element already), the prev pointer from last
            -- last element points to new_element
            q.Tail.Prev := New_Item;
        end if;

        -- Now point to Tail;
        New_Item.Next  := q.Tail;

        -- of course now New_Item is the last element, but the Tail
        -- still points to old last element, so update value of Tail
        q.Tail               := New_Item;
        q.Number_Of_Elements := q.Number_Of_Elements + 1;
    end add;

    procedure Remove (n:  out integer;  q: in out Queue_Type) is
        Old_Head : Link;
    begin
        -- can't remove from empty queue
        if Is_Empty_Queue(q) then
            raise Empty_Queue;
        end if;

        -- retrieve value from Head
        n      := q.Head.Value;

        -- Now Old_Head and Head point to the same element - the Head
        -- of queue
        Old_Head   := q.Head;

        -- new Head will be the previous element (becuse if
        -- we remove current Head we will lost it).
        q.Head := q.Head.Prev;

        -- Delete Old_Head
        Delete_Node (Old_Head);
        q.Number_Of_Elements := q.Number_Of_Elements - 1;

        -- in case when before removal there was only 1 element in queue
        -- (so after removal the queue is empty), we must also update
        -- the value of Tail (when there is only one element, Head and
        -- Tail point to the same one.
        if Is_Empty_Queue(q) then
            q.Tail := null;
        end if;
    end Remove;

    procedure Initialise (q:  in out Queue_Type) is
    begin
        null; -- Do nothing
    end Initialise;

    function is_empty_queue (q:  Queue_Type) return boolean is
    begin
        if q.Number_Of_Elements = 0 then
            return True;
        else
            return False;
        end if;
    end Is_Empty_Queue;
end Queues;
--------------------------------------------------

-------- Just to see results ...-----------------
with Ada.Integer_Text_IO;
    use Ada.Integer_Text_IO;
with Ada.Text_IO;
    use Ada.Text_IO;
with Queues;

procedure Main is
    Queue   : Queues.Queue_Type;
    Element : Integer;
begin
    for I in 1 .. 10 loop
        Queues.Add (I, Queue);
    end loop;

    while not (Queues.Is_Empty_Queue(Queue) ) loop
        Queues.Remove (Element, Queue);
        Put(Element);
        New_Line;
    end loop;

end Main;
-----------------------------------------

I changes a bit names is your spec, but now you should have
not trouble to get what is going on.

Happy New Year,
Mike
-----------------------------------------
                             ____|
                             \%/ |~~\
  O                                  |
 o>>        Mike Nowak               |
 T                                   |
/ >       vinnie@inetia.pl           |
http://www.geocities.com/vinnie14pl _|__