Content area
Full text
Making advanced algorithms and data structures a programming reality
Once mainly used as number processors to perform fast numerical computations, computers have evolved into information processors for storing, analyzing, searching, transferring, and updating large collections of structured information. For computer programs to perform these tasks effectively, the data they manipulate must be well organized, and the methods for accessing and maintaining those data must be reliable and efficient. In other words, programs need advanced data structures and algorithms. However, implementing advanced data structures and algorithms is not an easy task and presents some risks because of their complexity, proneness to subtle errors, and long development time. Consequently, programmers tend to ignore advanced data structures and algorithms, opting for simple, less efficient ones that are easier to implement and test. Clearly, the development of complex software applications-- in particular their rapid prototyping- can benefit from libraries of reliable and efficient data structures and algorithms.
Various libraries are available for C++, including the Standard Template Library (STL; see STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, by D.R. Musser and A. Saini, Addison-Wesley, 1996), now part of the C++ Standard; the Library of Efficient Data Structures and Algorithms (LEDA; see LEDA: A Platform for Combinatorial and Geometric Computing, by K. Mehlhorn and S. Naher, Cambridge University Press, 1999); and the Generic Graph Component Library (GGCL; see "The Generic Graph Component Library," by J. Siek, Lie-Quan Lee, and A. Lumsdaine, DDJ, September 2000).
The situation with Java is different, however. A small library of data structures and algorithms, usually referred to as "Java Collections" (JC), is included in the Java 2 java.util package (http:// java.sun.com/j2se/1.3/). Likewise, there's the Generic Library for Java (JGL) by ObjectSpace (http://www.objectspace.com/ products/voyager/jgl.asp), which is patterned after STL. Both the JC and JGL provide implementations of basic data structures such as maps, sets, dictionaries, and sequences. JGL also provides a number of template-based algorithms for permuting data. The Graph Foundation Classes for Java (GFC) by IBM's alphaWorks (http://www.alphaworks.ibm.com/tech/gfc), a framework for programming with graphs, is still in a preliminary stage. The GFC provides more advanced data structures (such as trees and graphs) and some graph drawing algorithms. However, none of these Java libraries provide a coherent framework- capable...