Wayne's Little Data Structures and Algorithms Library

One thing that many people ask me is ``why didn't you use C++?'' Two reasons. First, I started libwayne in 1992, before C++ had become widely accepted and long before it was standardized. Second--without going into a long tirade--suffice it to say that, although I am not a C++ expert (actually, the only stuff I haven't learned in intimate detail is templates), I know enough C++ to realize that it is not the be-all, end-all of programming languages. In fact, after several years of C++ being around, it is already beginning a slow fading into history, with Java being its successor --- and not a very good one, at that. At the risk of sounding like the 40-50 year olds out there who still insist that FORTRAN is a good enough language for everything, I'll be a 30-something who insists that, until something better comes along, C is still a good all-purpose language in which to write heavy, data-structure intensive programs. I believe it was Dennis Ritchie who said something like, "C is rarely the best language for a given task, but it's often the second-best," the implication being that it's better to learn one language that is second-best for everything, than to learn a new language for every programming task. (One could say the same of English.)

I started libwayne when I realized that I was constantly re-writing little bits of code that did important things that should be in the C standard, but are not. For example, how many times have you written code like this:

if((p = malloc(n)) == NULL)	/* or some other fatal error condition */
{
    fprintf(stderr, "error: %s\n", err_msg);
    exit(1);
}

void Fatal(char *fmt, ...);  /* generates an assertion failure */

Eventually "misc.c" started getting pretty big, with macros for MIN, MAX, ABS, SQR, etc, so I created misc.h and compiled misc.c into an object module. That was about 1993.

About that time I started to realize that, at least in C, we need a way to pass "objects" around in a reasonably transparent way, but sometimes we want to treat pointers as integers. This makes some people's teeth sweat (my own included), so I invented the voint datatype, which is (you guessed it) a union of (void*) and (int).

Then I started adding more complex algorithms to libwayne, whenever I needed them. Each and every piece of libwayne was written because I needed it, but only things that I took careful time to do well went into libwayne. Any algorithm that needs to compare objects needs a comparison function like the one used by the ANSI standard qsort routine.

Some of the sub-libraries in libwayne

Discrete (integer) Algorithms

• Heap: heap implementation of a priority queue. The array grows as necessary using realloc, so you don't need to know the maximum size a priori, although you need to give it an initial guess. The standard priority queue operations are supported: create, destroy, insert, getnext, size, and each takes time no longer than O(log n). In addition, I support (slow) deletion, and once you have insert and getnext, it's trivial to write a heap sort. Here's what its header file looks like.

  #include "misc.h"   /* for voint */
  
  /* this is returned if any errors occur */
  #define HEAPERROR ABSTRACT_ERROR
  
  typedef struct _heaptype
  {
      int HEAPSIZE;
      pCmpFcn HeapCmp;	/* pointer to comparison function */
      voint *heap;
  } HEAP;
  
  
  HEAP    *HeapAlloc(int maxNumber, pCmpFcn);
  void    HeapReset(HEAP*);   /* make heap empty */
  int     HeapSize(HEAP*);    /* how many things currently in heap? */
  void    HeapFree(HEAP*);    /* free the entire heap */
  voint   HeapPeek(HEAP*);    /* what's the top element? */
  voint   HeapNext(HEAP*);    /* pop and return top element */
  voint   HeapInsert(HEAP*, voint);
  /*
  ** delete is slow O(n); if more than one match, only one is deleted, but
  ** no guarantees on which gets deleted.
  */
  voint   HeapDelete(HEAP*, voint);
  int     HeapSort(voint *list, pCmpFcn);
  int     HeapCheck(HEAP*);   /* sanity check, for debugging */
  void    HeapPrint(HEAP*);   /* dump an entire heap.  You must define a HeapTypeP
  rint function */
  void    HeapTypePrint();
  

• Event: Routines for event-driven simulation. Of course, they use my heap routines. Operations supported: InitEventList, InsertEvent, NextEvent. Events are function pointers that get called when the appropriate event is activated. I found it very useful for prototyping even complicated event-driven simulations. (Although, for serious research, I "upgraded" to a more sophisticated event-driven simulation package.)

• Queue and stack.h: circular buffer (first-in-first-out) and stack (last-in-first-out).

• Set: bit-string implemenation sets of integers. Operations supported: SetAlloc, SetFree, SetEmpty (delete all members), SetCopy, SetAdd, SetDelete, SetIn (query membership), SetUnion, SetIntersection, SetCardinality. All these routines are very fast, since almost every operation is just a few bit manipualitons. It's also memory efficient, taking up N/8 bytes of storage, where N is the maximum integer you want to store in the set.

• Graph: algorithms for manipulating graphs (node and edge graphs, not mathematical functions). I wrote these for my Ramsey Graph searching. Operations supported: GraphAlloc, GraphFree, GraphDeleteAllEdges, GraphConnect (two nodes), GraphDisconnect (two nodes), GraphAreConnected (query connection between two nodes), GraphComplement (the entire graph), GraphUnion (two graphs), GraphInduced (induce a subgraph on a set of nodes), GraphsIsomorphic (reasonably clever but not genius algorithm for graph isomorphism), GraphClique, GraphIndepSet. The last two search for cliques and independent sets on an arbitrary graph using the brute-force exponential time algorithm.

• Combin: some basic combinatorial algorithms, used by the clique-searching routines in graph. Operations supported: generate all permutations or combinations; count them without generating them; generate Nth permutation or combination quickly.

• sorts: various sorting routines with the exact same interface is ANSI qsort: QuickSort, Insertion sort, Heapsort, CombSort, MergeSort, FredSort, PointerSort. The latter is good for sorting large objects. It creates a list of pointers, sorts the pointers, and then permutes all the big objects in O(n) time. For 16384 elements each about 1K in size, it's about 10 times faster than qsort. FredSort is Fredrickson's Sort, which is an O(n log n) time, near-space-optimal sorting routine, based on a talk I saw in Toronto in 1998.

• BinTree: algorithms for a binary tree: BinTreeAlloc, BinTreeInsert, BinTreeLookup, BinTreeLookupKey, BinTreeFree.

• Oalloc: allocate chunks of memory that can not be freed individually, but can all be freed in one call. I wrote this for use in a graphical renderer/animator, which needs to allocate literally millions of small chunks of memory (small = 8-20 bytes), and when the picture is finished being generated, all the memory associated with its generation can be thrown away in one step, in preparation for the next image. Oalloc means "Once Alloc".

Floating Point Algorithms

• sdriv2: a C language interface to the very good FORTRAN ODE integrator sdriv2, from the book Numerical Methods and Software by Kahaner, Molar and Nash, Prentice Hall 1988. I also have ddriv2, the double-precision version.

• lsode: a C interface to another very good FORTRAN ODE integrator called LSODE. Also here for more details.

• leapfrog: an sdriv2 and LSODE-like interface to a simple leapfrog integrator.

• matvec: routines for matrix and vector manipulations.

• stats: routines for simple hand-calculator-like statistics, like mean, variance, geometric mean, skewness. I used these in my network research.

Download libwayne

[A very old, deprecated version of libwayne is available as a tar'd gzip'd archive, or as a ZIP archive). In any case, after reading The Cathedral and the Bazaar, I've decided to release it. If you'd just like to get it quickly, you can download a tar'd, gzip'd archive of the entire tree here. It's about 1.5MB. (Most of that is actually high-quality FORTRAN numerical stuff that I didn't write, but for which I've written C front-ends to.) If you find any bugs, or make any improvements, please contact me via e-mail.]

libwayne is dual-licensed: the default is the Library GNU General Public License (LGPL), but you can contact me if you are interested in arranging another mutually agreeable licensing scheme.

If you came to this page looking for my quad precision routines, don't bother: I found a much better implementation.