Solved

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

Posted on 1999-01-10
13
198 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
Comment Utility
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
Comment Utility

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
Comment Utility
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
 
LVL 1

Author Comment

by:Pandora
Comment Utility
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
Comment Utility
ahh; this seems to have done the trick!
0
 
LVL 12

Expert Comment

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

What was your real question then?

Raymond.
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 3

Expert Comment

by:williams2
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Raymond: I guess I owe you then..
0
 
LVL 12

Expert Comment

by:rwilson032697
Comment Utility
Pandora: Thanks for clarifying this:

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

Cheers,

Raymond.
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

In this tutorial I will show you how to use the Windows Speech API in Delphi. I will only cover basic functions such as text to speech and controlling the speed of the speech. SAPI Installation First you need to install the SAPI type library, th…
Hello everybody This Article will show you how to validate number with TEdit control, What's the TEdit control? TEdit is a standard Windows edit control on a form, it allows to user to write, read and copy/paste single line of text. Usua…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

762 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now