**Go backward to** What Kind of Standards Should There Be

for Generic Algorithm Performance?

*David Musser*

**Go up to** Libraries and Standardization

### Generic Programming in CGAL

*Stefan Schirra*

CGAL (Computational Geometry Algorithms Library) is a C`++`
software library of geometric algorithms and data structures. It
is developed by several European research institutes and universities,
see `http://www.cs.ruu.nl/CGAL`

for further information.
We give three examples of genericity in CGAL. In the first two examples
genericity is achieved by parameterization. Thus they are examples
for generic programming via parameterized programming.

The first example is parameterization of the classes in the kernel of
CGAL. All constant-size geometric types in the kernel are parameterized
by a "representation class." Essentially, this parameter must provide
an implementation for the kernel types. CGAL currently offers two concrete
models for the concept representation class, a model which uses Cartesian
coordinates for the implementation and a model using homogeneous coordinates.
Both models are parameterized by the number type used for the coordinates.
We use computation of minimum diameter of a set of moving points to
illustrate the use of the number type `real` from LEDA (see
`http://www.mpi-sb.mpg.de/LEDA`

) in the CGAL kernel classes to abolish
precision problems.

The second example is data types and algorithms in the basic library part
of CGAL. They are parameterized by the types on which they operate and the
components that are used to operate on these types. Instead of having a long
parameter list, parameters are collected into a single class called "traits
class" in CGAL. The name was chosen because of the conceptual similarity to
the traits classes used in the C`++` standard library.
By the parameterization CGAL gains a lot of flexibility and adaptability.

The third example is the *circulator* concept. It has been contributed
to CGAL by Lutz Kettner (ETH Zürich). A circulator is a variation of
the iterator concept for circular sequences. Circular sequences arise
frequently in geometry. CGAL data types provide access to such circular
sequences through circulators. Circulators turned out to be very useful
in CGAL.