TEAMFLY

Julian Bucknall
Wordware Publishing, Inc.
Library of Congress Cataloging-in-Publication Data
Bucknall, Julian
Tomes of Delphi: algorithms and data structures / by Julian Bucknall.
p. cm.
Includes bibliographical references and index.
ISBN 1-55622-736-1 (pbk. : alk. paper)
1. Computer software—Development. 2. Delphi (Computer file). 3. Computer
algorithms. 4. Data structures (Computer science) I. Title.
QA76.76.D47 .B825 2001 2001033258
005.1 dc21 CIP
© 2001, Wordware Publishing, Inc.
Code © 2001, Julian Bucknall
All Rights Reserved
2320 Los Rios Boulevard
Plano, Texas 75074
No part of this book may be reproduced in any form or by
any means without permission in writing from
Wordware Publishing, Inc.
Printed in the United States of America
ISBN 1-55622-736-1
10987654321
0105
Delphi is a trademark of Inprise Corporation.
Other product names mentioned are used for identification purposes only and may be trademarks of their respective companies.
All inquiries for volume purchases of this book should be addressed to Wordware Publishing, Inc., at the
above address. Telephone inquiries may be made by calling:
(972) 423-0090
For Donna and the Greek cats

Array Types in Delphi 28
Standard Arrays 28
Dynamic Arrays 32
New-style Dynamic Arrays 40
TList Class, an Array of Pointers 41
Overview of the TList Class 41
TtdObjectList Class 43
v
Arrays on Disk 49
Summary 62
Chapter 3 Linked Lists, Stacks, and Queues 63
Singly Linked Lists 63
Linked List Nodes 65
Creating a Singly Linked List 65
Inserting into and Deleting from a Singly Linked List 65
Traversing a Linked List 68
Efficiency Considerations 69
Using a Head Node 69
Using a Node Manager 70
The Singly Linked List Class 76
Doubly Linked Lists 84
Inserting and Deleting from a Doubly Linked List 85
Efficiency Considerations 88
Using Head and Tail Nodes 88
Using a Node Manager 88
The Doubly Linked List Class 88
Benefits and Drawbacks of Linked Lists 96
Stacks 97
Stacks Using Linked Lists 97
Stacks Using Arrays 100

Merge Sort 152
Quicksort 161
Merge Sort with Linked Lists 176
Summary 181
Chapter 6 Randomized Algorithms 183
Random Number Generation 184
Chi-Squared Tests 185
Middle-Square Method 188
Linear Congruential Method 189
Testing 194
The Uniformity Test 195
TheGapTest 195
The Poker Test 197
The Coupon Collector’s Test 198
Results of Applying Tests 200
Combining Generators 201
Additive Generators 203
Shuffling Generators 205
Summary of Generator Algorithms 207
Other Random Number Distributions 208
Skip Lists 210
Searching through a Skip List 211
Insertion into a Skip List 215
Deletion from a Skip List 218
Full Skip List Class Implementation 219
Summary 225
Chapter 7 Hashing and Hash Tables 227
Hash Functions 228
Simple Hash Function for Strings 230
The PJW Hash Functions 230

Class Implementation of a Splay Tree 309
Red-Black Trees 312
Insertion into a Red-Black Tree 314
Deletion from a Red-Black Tree 319
Summary 329
Chapter 9 Priority Queues and Heapsort 331
The Priority Queue 331
First Simple Implementation 332
Second Simple Implementation 335
The Heap 337
Insertion into a Heap 338
Deletion from a Heap 338
Implementation of a Priority Queue with a Heap 340
Heapsort 345
Floyd’s Algorithm 345
Completing Heapsort 346
Extending the Priority Queue 348
Re-establishing the Heap Property 349
Finding an Arbitrary Item in the Heap 350
Implementation of the Extended Priority Queue 350
Summary 356
viii
Contents
Chapter 10 State Machines and Regular Expressions 357
State Machines 357
Using State Machines: Parsing 357
Parsing Comma-Delimited Files 363
Deterministic and Non-deterministic State Machines 366
Regular Expressions 378
Using Regular Expressions 380

Index 518
Contents
ix
Introduction
You’ve just picked this book up in the bookshop, or you’ve bought it, taken it
home and opened it, and now you’re wondering…
Why a Book on Delphi Algorithms?
Although there are numerous books on algorithms in the bookstores, few of
them go beyond the standard Computer Science 101 course to approach algo
-
rithms from a practical perspective. The code that is shown in the book is to
illustrate the algorithm in question, and generally no consideration is given to
real-life, drop-in-and-use application of the technique being discussed. Even
worse, from the viewpoint of the commercial programmer, many are text-
books to be used in a college or university course and hence some of the more
interesting topics are left as exercises for the reader, with little or no answers.
Of course, the vast majority of them don’t use Delphi, Kylix, or Pascal. Some
use pseudocode, some C, some C++, some the language du jour; and the
most celebrated and referenced algorithms book uses an assembly language
that doesn’t even exist (the MIX assembly language in The Art of Computer
Programming [11,12,13]—see the references section). Indeed, those books
that do have the word “practical” in their titles are for C, C++, or Java. Is
that such a problem? After all, an algorithm is an algorithm is an algorithm;
surely, it doesn’t matter how it’s demonstrated, right? Why bother buying and
reading one based on Delphi?
Delphi is, I contend, unique amongst the languages and environments used in
application development today. Firstly, like Visual Basic, Delphi is an environ
-
ment for developing applications rapidly, for either 16-bit or 32-bit Windows,
or, using Kylix, for Linux. With dexterous use of the mouse, components rain


and weaknesses, what they are used for and why, and have an implementa-
tion you could use at a moment’s notice, then you will look at the design of
the subsystem or application you’re currently working on in a new light, and
identify places where you could profitably use one. If sorts hold no terrors for
you, you understand how they work, and you know when to use a selection
sort versus a quicksort, then you’ll be more likely to code one in your applica
-
tion, rather than try and twist a standard Delphi component to your needs
(for example, a modern horror story: I remember hearing about someone
who used a hidden TListBox component, adding a bunch of strings, and then
setting the Sorted property to true to get them in order).
“OK,” I hear you say, “writing about algorithms is fine, but why bother with
Delphi or Kylix?”
By the way, let’s set a convention early on; otherwise I shall be writing the
phrase “Delphi or Kylix” an awful lot. When I say “Delphi,” I really mean
either Delphi or Kylix. Kylix was, after all, known for much of its pre-release
life as “Delphi” for Linux. In this book, then, “Delphi” means either Delphi for
Windows or Kylix for Linux.
Introduction
xi
So, why Delphi? Well, two reasons: the Object Pascal language and the oper
-
ating system. Delphi’s language has several constructs that are not available
in other languages, constructs that make encapsulating efficient algorithms
and data structures easier and more natural. Things like properties, for exam
-
ple. Exceptions for when unforeseen errors occur. Although it is perfectly
possible to code standard algorithms in Delphi without using these Delphi-
specific language constructs, it is my contention that we miss out on the
beauty and efficiency of the language if we do. We miss out on the ability to

phism, and delegation. The object model in Delphi shouldn’t scare you!
Having said that, a lot of the concepts described in this book are simple in the
extreme. A beginner programmer should find much in the book to teach him
xii
Introduction
or her the basics of standard algorithms and data structures. Indeed, looking
at the code should teach such a programmer many tips and tricks of the
advanced programmer. The more advanced structures can be left for a rainy
day, or when you think you might need them.
So, essentially, you need to have been programming in Delphi for a while.
Every now and then you need some kind of data structure beyond what TList
and its family can give you, but you’re not sure what’s available, or even how
to use it if you found one. Or, you want a simple sort routine, but the only
reference book you can find has code written in C++, and to be honest you’d
rather watch paint dry than translate it. Or, you want to read an algorithms
book where performance and efficiency are just as prominent as the descrip
-
tion of the algorithm. This book is for you.
Which Delphi Do I Need?
Are you ready for this? Any version. With the exception of the section discuss-
ing dynamic arrays using Delphi 4 or above and Kylix in Chapter 2, and parts
of Chapter 12, and little pieces here and there, the code will compile and run
with any version of Delphi. Apart from the small amount of the version-
specific code I have just mentioned, I have tested all code in this book with all
versions of Delphi and with Kylix.
You can therefore assume that all code printed in this book will work with
every version of Delphi. Some code listings are version-specific though, and
have been so noted.
What Will I Find, and Where?
This book is divided into 12 chapters and a reference section.

Chapter 7 considers hashing and hash tables, why they’re used, and what
benefits and drawbacks they have. Several standard hashing algorithms are
introduced. One problem that occurs with hash tables is collisions; we shall
see how to resolve this by using a couple of types of probing and also by
chaining.
Chapter 8 presents binary trees, a very important data structure in wide gen-
eral use. We’ll look at how to build and maintain a binary tree and how to
traverse the nodes in the tree. We’ll also address its unbalanced trees created
by inserting data in sorted order. A couple of balancing algorithms will be
shown: splay trees and red-black trees.
Chapter 9 deals with priority queues and, in doing so, shows us the heap
structure. We’ll consider the important heap operations, bubble up and trickle
down, and look at how the heap structure gives us a sort algorithm for free:
the heapsort.
Chapter 10 provides information about state machines and how they can be
used to solve a certain class of problems. After some introductory examples
with finite deterministic state machines, the chapter considers regular expres
-
sions, how to parse them and compile them to a finite non-deterministic state
machine, and then apply the state machine to accept or reject strings.
Chapter 11 squeezes in some data compression techniques. Algorithms such
as Shannon-Fano, Huffman, Splay, and LZ77 will be shown.
Chapter 12 includes a variety of advanced topics that may whet your appetite
for researching algorithms and structures. Of course, they still will be useful
to your programming requirements.
xiv
Introduction
Finally, there is a reference section listing references to help you find out
more about the algorithms described in this book; these references not only
include other algorithms books but also academic papers and articles.

KylixN define for a particular Kylix version,N=1
KylixNPlus define for a particular Kylix version or later,N=1
HasAssert define if compiler supports Assert
Introduction
xv
I also make the assumption that every compiler except Delphi 1 has support
for long strings.
What about Bugs?
This book is a book of human endeavor, written, checked, and edited by
human beings. To quote Alexander Pope in An Essay on Criticism, “To err is
human, to forgive, divine.” This book will contain misstatements of facts,
grammatical errors, spelling mistakes, bugs, whatever, no matter how hard I
try going over it with Fowler’s Modern English Usage, a magnifying glass, and
a fine-toothed comb. For a technical book like this, which presents hard facts
permanently printed on paper, this could be unforgivable.
Hence, I shall be maintaining an errata list on my Web site, together with any
bug fixes to the code. Also on the site you’ll find other articles that go into
greater depth on certain topics than this book. You can always find the latest
errata and fixes at />. If you do find an error, I
would be grateful if you would send me the details by e-mail to

. I can then fix it and update the Web site.
xvi
Introduction
Acknowledgments
There are several people without whom this book would never have been
completed. I’d like to present them in what might be termed historical order,
the order of their influence on me.
The first two are a couple of gentlemen I’ve never met or spoken to, and yet
who managed to open my eyes to and kindle my enthusiasm for the world of

-
out him and his support, this book might have been written, but it certainly
wouldn’t have been as good. I certainly recommend a subscription to The
Delphi Magazine, as it remains, in my view, the most in-depth, intelligent ref
-
erence for Delphi programmers. Thanks to all my readers, as well, for their
suggestions and comments on the column.
Next to last, thanks to all the people at Wordware (d-
ware.com), including my editors, publisher Jim Hill, and developmental edi
-
tor Wes Beckwith. Jim was a bit dubious at first when I proposed publishing a
book on algorithms, but he soon came round to my way of thinking and has
been very supportive during its gestation. I’d also like to give my warmest
thanks to my tech editors: Steve Teixeira, the co-author of the tome on how
to get the best out of Delphi, Delphi n Developer’s Guide (where, at the time of
writing, n = 5), and my friend Anton Parris.
Finally, my thanks and my love go to my wife, Donna (she chivvied me to
write this book in the first place). Without her love, enthusiasm, and encour-
agement, I’d have given up ages ago. Thank you, sweetheart. Here’s to the
next one!
Julian M. Bucknall
Colorado Springs, April 1999 to February 2001
xviii
Acknowledgments
Chapter 1
What is an Algorithm?What is an Algorithm?
For a book on algorithms, we have to make sure that we know what we are
going to be discussing. As we’ll see, one of the main reasons for understand
-
ing and researching algorithms is to make our applications faster. Oh, I’ll

-
centrated answer: 62.
Notice that what you had been taught was an algorithm to perform this and
any similar addition. You were not taught how to add 45 and 17 specifically
but were instead taught a general way of adding two numbers. Indeed, pretty
soon, you could add many numbers, with lots of digits, by applying the same
algorithm. Of course, in those days, you weren’t told that this was an algo-
rithm; it was just how you added up numbers.
In the programming world we tend to think of algorithms as being complex
methods to perform some calculation. For example, if we have an array of
customer records and we want to find a particular one (say, John Smith), we
might read through the entire array, element by element, until we either
found the John Smith one or reached the end of the array. This seems an
obvious way of doing it and we don’t think of it being an algorithm, but it
is—it’s known as a sequential search.
There might be other ways of finding “John Smith” in our hypothetical array.
For example, if the array were sorted by last name, we could use the binary
search algorithm to find John Smith. We look at the middle element in the
array. Is it John Smith? If so, we’re done. If it is less than John Smith (by “less
than,” I mean earlier in alphabetic sequence), then we can assume that John
Smith is in the first half of the array. If greater than, it’s in the latter half of
the array. We can then do the same thing again, that is, look at the middle
item and select the portion of the array that should have John Smith, slicing
and dicing the array into smaller and smaller parts, until we either find it or
the bit of the array we have left is empty.
Well, that algorithm certainly seems much more complicated than our origi
-
nal sequential search. The sequential search could be done with a nice simple
For loop with a call to Break at the right moment; the code for the binary
search would need a lot more calculations and local variables. So it might

Team-Fly
®


L:=0;
R := pred(aCount);
while (L <= R) do begin
M:=(L+R)div 2;
CompareResult := CompareText(aStrs^[M], aName);
if (CompareResult = 0) then begin
Result := M;
Exit;
end
else if (CompareResult < 0) then
L:=M+1
else
3
Chapter 1—What is an Algorithm?
R:=M-1;
end;
Result := -1;
end;
Just by looking at both routines it’s very hard to make a judgment about
performance. In fact, this is a philosophy that we should embrace whole-
heartedly: it can be very hard to tell how speed efficient some code is just by
looking at it. The only way we can truly find out how fast code is, is to run it.
Nothing else will do. Whenever we have a choice between algorithms, as we
do here, we should test and time the code under different environments, with
different inputs, in order to ascertain which algorithm is better for our needs.
The traditional way to do this timing is with a profiler. The profiler program
loads up our test application and then accurately times the various routines
we’re interested in. My advice is to use a profiler as a matter of course in all
your programming projects. It is only with a profiler that you can truly deter-
mine where your application spends most of its time, and hence which

Sequential
100 0.14 0.10
1,000 1.44 1.05
10,000 15.28 10.84
100,000 149.42 106.35
Binary
100 0.01 0.01
1,000 0.01 0.01
10,000 0.02 0.02
100,000 0.03 0.02
As you can see, the timings make for some very interesting reading. The time
taken to perform a sequential search is proportional to the number of ele-
ments in the array. We say that the execution characteristics of sequential
search are linear.
However, the binary search statistics are somewhat more difficult to charac-
terize. Indeed, it even seems as if we’re falling into a timing resolution
problem because the algorithm is so fast. The relationship between the time
taken and the number of elements in the array is no longer a simple linear
one. It seems to be something much less than this, and something that is not
brought out by these tests.
I reran the tests and scaled the binary timings by a factor of 100.
Table 1.2: Retiming binary searches
Fail Success
100 0.89 0.57
1,000 1.47 1.46
10,000 2.06 2.06
100,000 2.50 2.41
Here we get a much more impressive set of data. You can see that increasing
the number of elements tenfold results in a run time that’s increased the time
5

For this notation, we work out the mathematical function of n, the number of
items, to which the algorithm’s performance is proportional, and say that the
algorithm is a O(f(n)) algorithm, where f(n) is some function of n. We read
this as “big-Oh of f(n)”, or, less rigorously, as “proportional to f(n).”
For example, our experiments showed us that sequential search is a O(n)
algorithm. Binary search, on the other hand, is a O(log(n)) algorithm. Since
log(n)<n, for all positive n we could say that binary search is always faster
than sequential search; however, in a moment, I will give you a couple of
warnings about taking conclusions from the big-Oh notation too far.
6
Chapter 1—What is an Algorithm?