Solved

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

Posted on 1999-01-10
13
201 Views
Last Modified: 2010-04-06
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
Comment
Question by:Pandora
  • 5
  • 4
  • 3
  • +1
13 Comments
 
LVL 3

Accepted Solution

by:
williams2 earned 200 total points
ID: 1355736
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
 

Expert Comment

by:GOMF
ID: 1355737

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
 
LVL 12

Expert Comment

by:rwilson032697
ID: 1355738
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
Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

 
LVL 1

Author Comment

by:Pandora
ID: 1355739
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
 
LVL 1

Author Comment

by:Pandora
ID: 1355740
ahh; this seems to have done the trick!
0
 
LVL 12

Expert Comment

by:rwilson032697
ID: 1355741
I am confused. You accepted an answer that wasn't an answer to your question!

What was your real question then?

Raymond.
0
 
LVL 3

Expert Comment

by:williams2
ID: 1355742
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
 
LVL 12

Expert Comment

by:rwilson032697
ID: 1355743
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
 
LVL 3

Expert Comment

by:williams2
ID: 1355744
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
 
LVL 12

Expert Comment

by:rwilson032697
ID: 1355745
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
 
LVL 1

Author Comment

by:Pandora
ID: 1355746
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
 
LVL 3

Expert Comment

by:williams2
ID: 1355747
Raymond: I guess I owe you then..
0
 
LVL 12

Expert Comment

by:rwilson032697
ID: 1355748
Pandora: Thanks for clarifying this:

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

Cheers,

Raymond.
0

Featured Post

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

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

Suggested Solutions

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Creating an auto free TStringList The TStringList is a basic and frequently used object in Delphi. On many occasions, you may want to create a temporary list, process some items in the list and be done with the list. In such cases, you have to…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Nobody understands Phishing better than an anti-spam company. That’s why we are providing Phishing Awareness Training to our customers. According to a report by Verizon, only 3% of targeted users report malicious emails to management. With compan…

776 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