Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 211
  • Last Modified:

spare Delphi 3 binary search class/unit anyone please?!

does anyone have a handy class/unit for binary searching a file; any efficient way of doing it would be great though I was working along the lines of creating a fixed length (chr13&10 delimited) ASCII file (of equal record length) i.e of the format:
<text> + spaces to pad out to equal length + #D#A
<next text> + spaces to pad out to equal length + #D#A
etc.  Be most obliged!
0
Pandora
Asked:
Pandora
  • 5
  • 4
  • 3
  • +1
1 Solution
 
williams2Commented:
This will do the trick :-)

Function GetText(Filename, Separator: String; const StringList: TStrings; Fixedlength: Integer): Boolean;
Const
  BufSize = 4096;
Type
  TBuffer = Array[0..BufSize-1] of Char;
var
  Buf: TBuffer;
  Stream: TFileStream;
  S: pChar;
  i,j,Size: Integer;
  SepIndex: Integer;
  SepLength: Integer;
  TextLength: Integer;
  SaveSep: pChar;
Begin
  Result:= False;
  If FileExists(Filename) then
  begin
    {$I-}
    Stream:= TFileStream.Create(FileName,fmOpenRead OR fmShareDenyWrite);
    If IOResult = 0 then
    begin
      S:= AllocMem(Stream.Size+1);
      TextLength:= 0;
      SepLength:= Length(Separator)+1;
      SaveSep:= AllocMem(SepLength+1);
      SepIndex:= 1;
      Repeat
        Size:= Stream.Size-Stream.Position;
        If Size>BufSize then Size:= BufSize;
        Stream.ReadBuffer(Buf,Size);
        i:= 0;
        While (i<Size) do
        begin
          While (Buf[i]=Separator[SepIndex]) AND (i<Size) AND (SepIndex<SepLength) do
          begin
            inc(i);
            SaveSep[SepIndex-1]:= Separator[SepIndex];
            inc(SepIndex);
          End;
          If SepIndex=SepLength then
          Begin
            SepIndex:= 1;
            While TextLength<FixedLength do
            begin
              S[TextLength]:= #32;
              Inc(TextLength);
            End;
            S[TextLength]:= #0;
            TextLength:= 0;
            StringList.Add(StrPas(S));
            S[0]:= #0; //Reset String
          End else
          If (i<size) then
          begin
            If SepIndex>1 then
              While SepIndex>1 do
              begin
                S[Textlength]:= SaveSep[SepIndex-2];
                Inc(Textlength,1);
                Dec(SepIndex);
              End
            else
            begin
              S[Textlength]:= Buf[i];
              Inc(Textlength);
              Inc(i);
            End;
          End;
        End;
      Until Stream.Position = Stream.Size;
      If S[0]<>#0 then
      begin
        S[textLength+1]:= #0;
        StringList.Add(StrPas(S));
      End;
      FreeMem(S,Stream.Size+1);
      FreeMem(SaveSep,SepLength+1+1);
      Stream.Free;
      Result:= True;
    End;
    {$I+}
  End;
End;

Regards,
Williams
0
 
GOMFCommented:

Dear Pandora.

I was wondering! Why not use a Balanced-tree or Hashing-tables
or something else, instead of a binary search ? Any
specific reason why you wan't to use "Binary Search" ?
Binary search is a slow and cumbersome routine, compared to
other more powerfull and efficient routines. I don't
think Delphi has any of those "in it" , however I
recomend that you try this PASCAL book out!
"Data structures and problem solving with turbo pascal"
ISBN : 0-8053-1217-X
Pascal is 99% Delphi, so it shouldn't be a problem
to code a unit. There are execellent examples with
full source, and very good comments and remarks -
proof of routines, lots of ADT's and "Big O" notations.
The book contains a lot of powerfull routines that you
can actually almost just type in!

If you don't want to use a book (books are SO RETRO ;-) )
then try out this http://sunsite.icm.edu.pl/delphi/
they have A LOT of delphi code there.

Best wishes!

GOMF

0
 
rwilson032697Commented:
Williams2, you are too fast! (Though all it seems to do is read the code - where does it search for an item?)

Here is the answer I did. It searches for an item in the file using a comparison function you provide. It implements a standard binary search. This code guarantees at most log(base2)n disk reads to locate an item in the file...

Binary searches are OK if you will not be doing large numbers of them. And reading from the file enables arbitrary size files to be used...

Off the top of my head this code should do it. It compiles but I have not tested it.

Cheers,

Raymond.


type
  TCompareProc = function(a, b : string) : Integer; // (a<b) < 0, (a=b) = 0, (a > b) > 0

const
  Reclen = 20;

Function Find(const FName : TFileName;
              const S : String;
              Compare : TCompareProc) : Integer; // index of record, -1 if not found
var
  Start, middle, finish : integer;
  TheFile : File of byte;
  s1, s2, s3 : string;
  found : boolean;
  CompareResult : Integer;

function GetRecord(Index : Integer) : String;
begin
  Seek(TheFile, Index * RecLen);
  BlockRead(TheFile, Result, RecLen);
end;

begin
  Result := -1;
  Found := False;
  SetLength(s1, RecLen);
  SetLength(s2, RecLen);
  SetLength(s3, RecLen);
  assignfile(TheFile, FName);
  try
    reset(TheFile);
    try
      Start := 0;
      Finish := FileSize(TheFile) DIV RecLen - 1;
      s1 := GetRecord(start);
      s3 := GetRecord(finish);
      while not found and (Middle <> finish) do
      begin
        Middle := (Start + Finish) DIV 2;
        S2 := GetRecord(Middle);
        CompareResult := Compare(S2, S);
        if CompareResult = 0 then
          begin
            Found := True;
            Result := Middle;
          end
        else
          if CompareResult < 0 then
            begin
              Start := middle;
              S2 := s1;
            end
          else
            begin
              Finish := Middle;
              S2 := s3;
            end;
      end
    finally
      CloseFile(TheFile);
    end;
  except
    // handle exception here
  end;
end;
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
PandoraAuthor Commented:
thanks for your help; I felt it could have been a little more modular (!) - cheeky aren't I!

I wanted to thank GOMF & rwilson too; because their advice was also invaluable - do u know any way of doing this please?
best wishes
P.

0
 
PandoraAuthor Commented:
ahh; this seems to have done the trick!
0
 
rwilson032697Commented:
I am confused. You accepted an answer that wasn't an answer to your question!

What was your real question then?

Raymond.
0
 
williams2Commented:
Raymond:

The guy doesn't want a BSP search tree, he wants an utility able to search and replace some specific matches in a file, such like end-of-line characters.

I know what you think :-) ..but since the guy needs a search in a binary file and not a binary search in a file, this could confuse the most, don't you think ?

Cheers,
Williams
0
 
rwilson032697Commented:
Williams2: Stop smoking that weed! Pandora's question very specifically states that he/she wanted to do a binary search (as in locate a specific item using a binary search algorithm) in a text file. Pandora did NOT mention BSP (which, BTW, stand for Binary Space Partition trees), nor did Pandora mention that they wanted to search a binary (as in non-text) file.

Cheers,

Raymond.
0
 
williams2Commented:
I know what you mean, but how would you do an effiecient binary search in a file which is not sorted ?? I also read the context of his question and got a little confused, so I guessed he was looking for that kind of functionality.

The function identyfies a given separator in a large file, and pastes the contents between as lines in a stringgrid, this type of code is not trivial, but might be done faster, have you got any suggestions ?

Regards,
Williams
0
 
rwilson032697Commented:
I assumed when Pandora said that she wanted to do a binary search that the file was sorted - perhaps I assumed too much (but I don't think so :-)

Raymond.
0
 
PandoraAuthor Commented:
Just to clarify; yes I did want a binary search of a sorted file and yes, I apologise to Raymond his answer was actually more useful because it set me off on the right track (although doesn't quite work as the loop would get stuck!) - However the last time I used this site, i swear you could award points between respondents which is what i would have liked to do; this time i was only given the option of throwing it open to others or saying yes - in retrospect i should have thrown it open and so Raymond please accept my apologies; I'll remember you next time!
0
 
williams2Commented:
Raymond: I guess I owe you then..
0
 
rwilson032697Commented:
Pandora: Thanks for clarifying this:

Williams2: Its nothing to worry about :-) :-) !

Cheers,

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

Join & Write a Comment

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

  • 5
  • 4
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now