Re: Can someone help me understand this queue package?

[Michal Nowak <vinnie@inetia.pl>]

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 _|__