?
Solved

Search Queue

Posted on 2003-03-02
13
Medium Priority
?
224 Views
Last Modified: 2010-04-16
I am attempting to write a program that emulates First In First Out Page Replacement.

Ultimately the program will read files of random integers, generated from a seperate program.  Currently I am entering integers manually for testing purposes.

I need to to include a search procedure that will check if the integer has already been added.  If the integer is found a "Page found : No change" message will be displayed.  If the item has not already been added the Replace procedure will be intitiated.

I've got myself in a muddle with the Search procedure and would be glad of help.

WTA

LRH

{Unit to simulate First In First Out Page Replacement }

unit FIFOCls4;
interface
uses crt;
type TQptr = ^QRec; {define Q record structure}
QRec = record
     element: integer;
     next: TQptr;
end;

QType = object {define Q structure and methods}
      head, tail : TQptr;
      Qsize, numInQ, Counter: integer;
 
      procedure Init(iMax : integer);
      procedure Add(nData : integer);
      procedure Retrieve;
      procedure DisplayQ;
      procedure Search (item : integer);
      procedure Replace(jData:integer);
      {procedure Output;}
end;

implementation

{
Method : Used to initialise Q
precondition : Q is defined
postcondition: maxsize of Q, num in Q and head & tail properties and counter set
}

procedure QType.Init(iMax : integer); {Set maximum Q size}
begin
     Qsize := iMax;
     NumInQ := 0;
     head := nil;
     tail := nil;
     Counter := 0;
end;

{
Method : Used to ADD data to Q
precondition : Q is initialised, and input data is an integer
postcondition: data added to Q and tail referenced to new element
}

procedure QType.Add(nData : integer);
var i : integer;
newElem : TQptr;
begin
   new(newElem);
   newElem^.element := nData; {set data to new element}
   newElem^.next := nil; {as element will be tail then set to nil}
      if tail <> nil then tail^.next := newElem; {point current tail of Q to new element}
      tail := newElem; {set tail to new element}
         if head = nil then head := tail; {set head to tail if nohing in Q}
         Inc(numInQ);
end;

{
Method : Used to RETRIEVE data from Q
precondition : Q has integer data present
postcondition: head of Q is removed and head moved to next item
}

procedure QType.Retrieve;
var i : integer;
tempQ : TQptr;
begin
   tempQ := head;
   head := head^.next; {point head of Q to next element}
   dispose(tempQ); {release memory}
   Dec(numInQ); {reduce number in Q}
      if numInq = 0 then tail := nil; {reset tail if no data in Q}
   Inc(Counter);
end;

{
Method : Used to DISPLAY data from Q
precondition : Q has integer data present
postcondition: data displayed from head onwards.
}

PROCEDURE QType.DisplayQ;
var tempQ : TQptr;
begin
   writeln('Items in Q ...');
   tempQ:= head;
      while tempQ <> nil do
      begin
      writeln(tempQ^.element);
      tempQ := tempQ^.next;
      end
end;

{
Method : Used to REPLACE data in Q
precondition : the data is not in Q
postcondition: head of Q is removed and
             the new data added to Q
}

procedure QType.Replace(jData:integer);
begin
   if NumInQ < Qsize then
   begin
   QType.Add(jData);
   writeln('Not Full Int Added : ',jData);
   writeln ('No items in Q : ', NumInQ);
   DisplayQ;
   end
      else
      begin
      QType.Retrieve;
      writeln('Q Full Int Removed');
      writeln ('No items in Q : ', NumInQ);
      QType.Add(jData);
      writeln('New Int Added : ',jData);
      writeln ('No items in Q : ', NumInQ);
      DisplayQ;
      end;
writeln('Fault Count = ', counter);
writeln;
end;

{
Method : Used to SEARCH for data
precondition : Q must be initialised and item to search for must be an integer
postcondition: if item found, confirmation message is displayed
               if item not found, Replace procedure intiated
}

Procedure QType.Search(item : integer);
var i, jData : integer;
currPos : TQptr;
begin
   currPos := head;
      if head <> nil then
      begin
         while currPos <> nil do
         begin
            if item = currPos^.element then
            begin
            Search := currPos;
            Exit;
            end;
         currPos := currPos^.next;
         end;
      end;
   Search := nil;  

{If Search <> nil then writeln ('Page found : No change');}
{If Search = nil then Replace(jData);}
     
end;

0
Comment
Question by:LittleRedHat
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 4
  • 2
  • +1
13 Comments
 
LVL 101

Expert Comment

by:mlmcc
ID: 8054293
Actually it is quite easy.  The exit only exits the loop not the subroutine.  Set Search to nil upfront then change it.  Also remove the commented lines that test search.

begin

  Search := nil;    
  currPos := head;
     if head <> nil then
     begin
        while currPos <> nil do
        begin
           if item = currPos^.element then
           begin
           Search := currPos;
           Exit;
           end;
        currPos := currPos^.next;
        end;
     end;
end;

These lines need to go in the calling routine.
{If Search <> nil then writeln ('Page found : No change');}
{If Search = nil then Replace(jData);}
In main use
{If Search(ITEM) <> nil then
   writeln ('Page found : No change')
  else
   Replace(jData);}
         
In my opinion exits are not good coding style.  You should set the loop up like this


  Search := nil;    
  currPos := head;
  while currPos <> nil do
     begin
        if item = currPos^.element then
           begin
              Search := currPos;
              currPos = nil;
           end
        else
           currPos := currPos^.next;
     end;
 
mlmcc    
0
 

Author Comment

by:LittleRedHat
ID: 8054523
Thanks for your reply, mimcc.  

I have taken your advice and changed my coding, but still have the same problem ... it wont compile.

At Search := nil;  it asks for a "(" after Search.
I've tried using Search(item), but it then asks for a ";" after (item)

(The same happened with my code at Search := currPos;)

LRH


0
 
LVL 101

Accepted Solution

by:
mlmcc earned 400 total points
ID: 8054990
I missed the fact that you are using search as a procedure not a function.

Try this

Procedure QType.Search(item : integer);
Var
   Found : boolean;
   currPos : TQptr;
begin

 Found := false;
 currPos := head;
 while (currPos <> nil) and (Not Found) do
    begin
       if item = currPos^.element then
          Found := true;
       else
          currPos := currPos^.next;
    end;
 If found then
   writeln ('Page found : No change')
 else
   Replace(jData);

end;

mlmcc
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 15

Expert Comment

by:VGR
ID: 8055559
missed "the" pascal problem of the week. Too bad.
0
 

Author Comment

by:LittleRedHat
ID: 8059783
Hi mimcc,

Sorry I didn't get back sooner, but I'd run into the early hours and out of midnight oil.

I've corrected my procedure as you suggested and it compiles(big thanks), but I've just spent two hours trying to work out how to use it and am totally baffled as to what I'm doing wrong.  My main program (below)compiles and runs, but whatever integer I enter it comes up as 2192.  If I keep adding integers the add/retreive/fault count all run correctly.  If I repeat enter one of the integers it does not recognise it as a duplicate, but if I enter 2192 it displays "page found" and, as wanted, asks for the next entry.

Confusing me even further ... if I omit the Search procedure and instead include the search code as part of the replace procedure everything works just fine.

Hope you wont mind bearing with me a little longer on this.

Regards.

LRH

{
Program which simulates First In First Out Page Replacement
}

program FIFOprg6;

uses crt, FIFOcls6;

  var q1 : qType; i, iData : integer;

  begin
    q1.Init(3); {set max. size of Q}
    for i := 1 to 5 do
    begin
      write('Enter Page Number : ');
      readln(iData);
      q1.Search(iData);
    end;

  writeln('Press return to exit');
  readln;
end.

   
0
 

Author Comment

by:LittleRedHat
ID: 8059819
Hi VGR ... hope you're well.  I've been quadruple checking that I'm reading mimcc's replies correctly.

Little Red Face :-)
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 8065907
You need to fix the else part at the end of the seearch

Replace(jData);

to
Replace(item);

mlmcc
0
 
LVL 15

Expert Comment

by:VGR
ID: 8065932
at least it's NICE to see AT LEAST someone taking care of preconditions and postconditions 8-))))))))
0
 

Author Comment

by:LittleRedHat
ID: 8076036
Hi mimcc!

;-)))))}}}}}})))))))))))))))))

Apols for the delayed thanks.  I think we must be opposite sides of the world.  I tried staying up late the other night, but the zzzz's won and then yesterday I was away.

I can't believe I missed Replace(item)in all the permutations and combinations I tried. Tut!Tut!

Many thanks for your help, time and patience.  

With all best wishes.

LRH
0
 

Author Comment

by:LittleRedHat
ID: 8076105
I'll try harde or the method, VGR. :-)))
0
 

Author Comment

by:LittleRedHat
ID: 8076114
Panic!  It looks like my Grade A didn't take.  Sorry mimcc.  I'll post to Support to have changed.

LRH
0
 
LVL 1

Expert Comment

by:Computer101
ID: 8077214
Seems all is well

Little, thanks for thinking of those that helped you

:-)

Computer101
E-E Admin
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 8077623
Glad to help

mlmcc
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Ready to improve network connectivity? Watch this webinar to learn how SD-WANs and a one-click instant connect tool can boost provisions, deployment, and management of your cloud connection.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

New style of hardware planning for Microsoft Exchange server.
Active Directory can easily get cluttered with unused service, user and computer accounts. In this article, I will show you the way I like to implement ADCleanup..
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…
Have you created a query with information for a calendar? ... and then, abra-cadabra, the calendar is done?! I am going to show you how to make that happen. Visualize your data!  ... really see it To use the code to create a calendar from a q…

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question