From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI autolearn=unavailable autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,d142408257dde54c X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-12-31 02:28:07 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!headwall.stanford.edu!hub1.nntpserver.com!newsfeed01.sul.t-online.de!t-online.de!fr.clara.net!heighliner.fr.clara.net!freenix!enst!enst.fr!not-for-mail From: Michal Nowak Newsgroups: comp.lang.ada Subject: Re: Can someone help me understand this queue package? Date: Mon, 31 Dec 2001 11:32:30 +0100 Organization: ENST, France Sender: comp.lang.ada-admin@ada.eu.org Message-ID: References: Reply-To: comp.lang.ada@ada.eu.org NNTP-Posting-Host: marvin.enst.fr Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7BIT X-Trace: avanie.enst.fr 1009794482 25565 137.194.161.2 (31 Dec 2001 10:28:02 GMT) X-Complaints-To: usenet@enst.fr NNTP-Posting-Date: Mon, 31 Dec 2001 10:28:02 +0000 (UTC) To: "comp.lang.ada usegroup->mailing list gateway" Return-Path: In-reply-to: X-Mailer: Calypso Version 3.20.01.01 (3) Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org X-Mailman-Version: 2.0.6 Precedence: bulk X-Reply-To: vinnie@inetia.pl List-Help: List-Post: List-Subscribe: , List-Id: comp.lang.ada mail<->news gateway List-Unsubscribe: , Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org Xref: archiver1.google.com comp.lang.ada:18406 Date: 2001-12-31T11:32:30+01:00 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 _|__