Search Queue

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;

LittleRedHatAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

mlmccCommented:
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
LittleRedHatAuthor Commented:
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
mlmccCommented:
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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

VGRCommented:
missed "the" pascal problem of the week. Too bad.
0
LittleRedHatAuthor Commented:
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
LittleRedHatAuthor Commented:
Hi VGR ... hope you're well.  I've been quadruple checking that I'm reading mimcc's replies correctly.

Little Red Face :-)
0
mlmccCommented:
You need to fix the else part at the end of the seearch

Replace(jData);

to
Replace(item);

mlmcc
0
VGRCommented:
at least it's NICE to see AT LEAST someone taking care of preconditions and postconditions 8-))))))))
0
LittleRedHatAuthor Commented:
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
LittleRedHatAuthor Commented:
I'll try harde or the method, VGR. :-)))
0
LittleRedHatAuthor Commented:
Panic!  It looks like my Grade A didn't take.  Sorry mimcc.  I'll post to Support to have changed.

LRH
0
Computer101Commented:
Seems all is well

Little, thanks for thinking of those that helped you

:-)

Computer101
E-E Admin
0
mlmccCommented:
Glad to help

mlmcc
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Pascal

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.