ToDADS: Bob Swart Review

published: Tue, 17-Jun-2003   |   updated: Sat, 20-Aug-2016

(The original can be found here on Dr Bob's site. It was also published in the UK-BUG's newsletter.)

This is a book that I've been waiting for for a long time (according to the acknowledgements, Julian has worked on it from April 1999 until February 2001, probably even longer). But it has been worth it, because it's an excellent book about algorithms and data structures implemented in Delphi (and Kylix) - usually version independent.

The book consists of 12 chapters. But even before the first chapter Julian takes on the question of "why a book on Delphi algorithms?" in the introduction. He explains that a number of Computer Science algorithms books are hardly practical, and the practical books are mainly for C, C++, or Java. This is a book about algorithms and data structures using Delphi (for Windows, but also Kylix for Linux), with a lot of focus on practical and useful techniques that make sense.

The first chapter starts by describing what an algorithm is, what algorithm analysis is and the "Big-Oh" notation is all about. Although Big-Oh is valid for a "fantasy machine", he also discusses additional issues like memory, CPU, speed vs. time, and some first Delphi specific tips regarding Long Strings (I learned a very nice technique on page 18 that changed the way I use the built-in Pos function of Delphi). Additional topics in the first chapter include debugging and testing using assertions, coverage analysis and more. Julian presents some good rules now and then, that may be common knowledge to some, but are important to mention explicitly nevertheless.

After the first chapter, which really only set the framework and mindset in a mere 26 pages, the book continues with 11 more chapters, each focused on a specific topic. Chapter 2 covers Arrays, including Dynamic Arrays of course. But also covering related classes, such as TList (an array of pointers) and what has happened with TList as of Delphi 5 to support TObjectList. Julian then designs his own TtdObjectList instead. Other topics are Arrays on Disk (just another name for a file where each line or record has a fixed length). Chapter 3 covers Linked Lists, Stacks and Queues. Like the previous chapter, we won't see an algorithm without a data structure to operate on. We see singly linked lists and doubly linked lists, a discussion on benefits and drawbacks, and then move on to stacks and queues (using linked lists and arrays). Chapter 4 covers searching, and is very much related to chapter 5 which covers sorting. The central point of both searching and sorting is the comparison routine, to compares two items. Sequential search (as an illustration of O(n)) is followed by Binary Search, both in arrays or linked lists (so you really feel the chapters "growing" onto each other). Sorting gets a bit more advanced, with about eight different sorting algorithms - each with their strong and weak points discussed in detail. It sometimes feels like reading Knuth for Delphi, and as Knuth's books, this book should be required reading for any Delphi developer who ever needs to search, sort or do anything with algorithms or data structures (which I think is pretty much every Delphi developer). Chapter 6 is a bit of a funny one, about Randomised Algorithms, which discusses random number generation, the chi-squared test and a number of attempts to write a truly random generator using different methods, as well as testing them using different tests. Might be useful if you don't want to use Random and RandSeed. Chapter 7 is about Hashing and Hash Tables, which is a technique to be able to quickly index a given item in a list (use the generated index to both store and find it quickly). Different hash functions are discussed in detail. Chapter 8 is about Binary Trees - an extension of simple linked lists. We read about creating a binary tree, inserting, deleting, and balancing, and of course searching in binary trees and related trees. Chapter 9 is about Priority Queues and Heapsort, which is an extension of chapter 3 (queues) and chapter 5 (sorting). A Priority Queue is implemented using a Heap (a binary tree with special properties and operations), which logically leads to the Heapsort - in case you wondered. Chapter 10 is about State Machines and Regular Expressions. I must admit that this was the least practical chapter in my view. We learned about finite deterministic state machines, but all I could do was remember the theory from the university I learned two decades ago. Nevertheless, the implementation was sound, although I'm not sure I'll be using it anytime soon. Chapter 11 was right back being practical, covering Data Compression. After we learn the difference between lossy and lossless compression, we continue with a few algorithms such as Minimum Redundancy Compression (Shannon-Fano, Huffman and Splay Tree) and Dictionary Compression using the LZ77 algorithm. The final chapter 12 covers some Advanced Topics, starting with the Win32 specific multithreading algorithms Readers-Writers and Producers-Consumers, as well as finding differences in two files.

Right after chapter 12, you get the epilogue, where Julian is the first to admit that even this book is not complete (where are the B-Trees, Julian), but I can forgive him easily. What follows is the list of references (on the next page), index and CD with full source code of the book as well as Julian's EZDSL freeware library and trial-runs of TurboPower software.

A great plus is that the code in the book works for every version of Delphi and Kylix (and probably also in C++Builder), and I'm fairly confident it will remain working in the next version(s) of Delphi and Kylix to come. A bonus point is the syntax high-lighting in the source code listings. A small effort for the author/publisher, but a great help for the reader who sees the source code for the first time.

The conclusion [of this review] is the same as the start: I have waited a long time for this book, but it has been worth it. If you're only half serious about data structures and algorithms (or efficiency for that matter), then you should read this book. You won't be sorry, trust me!

- Bob Swart

(Copyright (c) Bob Swart, 2001)