CGAL 5.5 - Manual
Coding Conventions
Author
Sven Schönherr

We do not want to impose very strict coding rules on the developers. What is most important is to follow the CGAL naming scheme described in the next section. However, there are some programming conventions (Section Programming conventions ) that should be adhered to, rules for the code format (Section Code format ), and a mandatory heading for each source file (Section File header )

Naming scheme

The CGAL naming scheme is intended to help the user use the library and the developer develop the library. The rules are simple and easy to remember. Where appropriate, they aim for similarity with the names used in the STL. Deviations from the given rules should be avoided; however, exceptions are possible if there are convincing reasons.

General rules

  • Words in the names of everything except concepts should be separated by underscores. For example, one would use function_name and Class_name instead of functionName or Classname.
  • Words in the names of concepts (e.g., template parameters) should be separated using capital letters. The only use of underscores in concept names is before the dimension suffix. For example, one should use a name such as ConvexHullTraits_2 for the concept in contrast to Convex_hull_traits_2 for the name of the class that is a model of this concept. This different naming scheme for concepts and classes was adopted mainly for two reasons (a) it is consistent with the STL (cf. InputIterator) and (b) it avoids name clashes between concepts and classes that would require one or the other to have a rather contrived name.
  • Abbreviations of words are to be avoided (e.g., use Triangulation instead of Tri). The only exceptions might be standard geometric abbreviations (such as "CH" for "convex hull") and standard data structure abbreviations (such as "DS" for "data structure"). Unfortunately, the long names that result from the absence of abbreviations are known to cause problems with some compilers.
  • Names of constants are uppercase (e.g., ORIGIN).
  • The first word of a class or enumeration name should be capitalized (e.g., Quotient, Orientation).
  • Function names are in lowercase (e.g., is_zero).
  • Boolean function names should begin with a verb. For example, use is_empty instead of simply empty and has_on_bounded_side instead of on_bounded_side.
  • Names of macros should begin with the prefix CGAL_.

Geometric objects

  • All geometric objects have the dimension as a suffix (e.g., Vector_2 and Plane_3). Exception: For \( d\)-dimensional objects there may be a dynamic and a static version. The former has the suffix _d (e.g., Point_d), while the latter has the dimension as the first template parameter (e.g., Point<d>).

Geometric data structures and algorithms

  • Names for geometric data structures and algorithms should follow the "spirit" of the rules given so far, e.g. a data structure for triangulations in the plane is named Triangulation_2, and a convex hull algorithm in 3-space is named convex_hull_3.
  • Member functions realizing predicates should start with is_ or has_, e.g. the data structure Min_ellipse_2 has member functions is_empty and has_on_bounded_side.
  • Access to data structures is given via iterators and circulators (Chapter Iterators, Circulators and Handles ). For iterators and functions returning them we extend the STL names with a prefix describing the items to be accessed. For example, the functions vertices_begin and vertices_end return a Vertex_iterator. (Note that we use the name of the items in singular for the iterator type name and in plural for the functions returning the iterator.) Names related to circulators are handled similarly, using the suffix _circulator. For example, the function edges_circulator returns an Edge_circulator.

Kernel traits

All types in the kernel concept are functor types. We distinguish the following four categories:

  1. generalized predicates, that is, standard predicates returning a Boolean value as well as functions such as orientation() that return an enumeration type (values from a finite discrete set).
  2. construction objects, which replace constructors in the kernel,
  3. constructive procedures and
  4. functors replacing operators.

As detailed below, the names of these functors reflect the actions performed by calls to operator(). This naming scheme was chosen instead of one in which the computed object determines the name because this latter naming scheme is more natural for functions that compute values where the function call can be seen as a name for the object returned instead of functors that simply maintain data associated with the computation. It was also noted that the naming of functions and functors is not consistent, either in CGAL or in the STL (In some cases the action performed by a function determines its name (e.g., multiply()) while in others the result of the action determines the name (e.g., product()).), so achieving complete consistency with an existing naming scheme is not possible.

Here are the naming rules:

  • All names in the kernel traits have the dimension as a suffix. This is necessary because in some cases (e.g., the Orientation_2 object) the absence of the suffix would cause a name conflict with an existing type or class (e.g., the enumeration type Orientation).
  • The names of generalized predicates are determined by their results. Furthermore, names are as much as possible consistent with the current kernel and the STL. So, for example, we have objects like Has_on_bounded_side_2, Is_degenerate_2, and Is_horizontal_2. According to the current kernel we also have Left_turn_2. For reasons of consistency with STL, all "less-than"-objects start with Less_, e.g., Less_xy_2. Further examples are Less_distance_to_point_2 and Less_distance_to_line_2. However, we have Equal_2, whereas the corresponding STL functor is called equal_to. Here, we give our dimension rule higher priority.
  • The names of construction objects (category 2 above) follow the pattern Construct_type_d, where type_d is the type constructed, e.g., Construct_point_2 and Construct_line_2. The operator() of these functor classes is overloaded. This reduces the number of names to remember drastically, while replacing one of the constructions gets more complicated, but is still possible.
  • Functors in category 3 above can be further subdivided into two classes:

    • constructive procedures that construct objects whose types are known a priori
    • procedures that construct objects whose types are not known a priori

    The names of functors in the first class also start with Construct_ whenever a geometric object is constructed, otherwise they start with Compute_. Here, real numbers are not considered to be 1-dimensional geometric objects. For example, on the one hand we have Construct_perpendicular_vector_2, Construct_midpoint_3, Construct_circumcenter_d, Construct_bisector_2, and Construct_point_on_3, while on the other hand there are Compute_area_2 and Compute_squared_length_3.

    For the second class, the names of the objects describe the (generic) action, e.g. Intersect_2.

  • The equality operator (operator==()) is replaced by function objects with names of the form Equal_k, where k is the dimension number (i.e., 2, 3, or d). For replacing arithmetic operators, we might also provide Add_2, Subtract_2, Multiply_2, and Divide_2. (As mentioned above, the action determines the name, not the result.) We think that these objects are not really needed. They are likely to be part of primitive operations that have a corresponding function object in the traits.

In addition, for each functor the kernel traits class has a member function that returns an instance of this functor. The name of this function should be the (uncapitalized) name of the functor followed by the suffix _object.For example, the function that returns an instance of the Less_xy_2 functor is called less_xy_2_object.

File names

  • File names should be chosen in the "spirit" of the naming rules given above.
  • If a single geometric object, data structure, or algorithm is provided in a single file, its name (and its capitalization) should be used for the file name. For example, the file Triangulation_2.h contains the data structure Triangulation_2.
  • If a file does not contain a single class, its name should not begin with a capital letter.
  • No two files should have the same names even when capitalization is ignored. This is to prevent overwriting of files on operating systems where file names are not case sensitive. A package that contains file names that are the same as files already in the release will be rejected by the submission script.
  • The names of files should not contain any characters not allowed by all the platforms the library supports. In particular, it should not contain the characters ':', '*', or ' '.
  • Internal header files - which are not documented to the user - should have Package/internal/ as a directory higher up in their hierarchy. For example CGAL/Triangulation_2/internal/predicates/my_pred.h.

Programming conventions

The first list of items are meant as rules, i.e., you should follow them.

  • Give typedefs for all template arguments of a class that may be accessed later from outside the class. The template parameter is a concept and should follow the concept naming scheme outlines in the previous section. As a general rule, the typedef should identify the template parameter with a type of the same name that follows the naming convention of types. For example
    template < class GeometricTraits_2 >
    class Something {
    public:
    typedef GeometricTraits_2 Geometric_traits_2;
    };
    For one-word template arguments, the template parameter name should be followed by an underscore. (Note that using a preceding underscore is not allowed according to the C++ standard; all such names are reserved.)
    template < class Arg_ >
    class Something {
    public:
    typedef Arg_ Arg;
    };
  • Use const when a call by reference argument is not modified, e.g. int f( const A& a).
  • Use const to indicate that a member function does not modify the object to which it is applied, e.g., class A { int f( void) const; };. This should also be done when it is only conceptually const. This means that the member function f() is const as seen from the outside, but internally it may modify some data members that are declared mutable. An example is the caching of results from expensive computations. For more information about conceptually const functions and mutable data members see [9].
  • Prefer C++-style to C-style casts, e.g., use static_cast<double>( i) instead of (double)i.
  • Protect header files against multiple inclusion, e.g. the file This_is_an_example.h should begin/end with
    #ifndef CGAL_THIS_IS_AN_EXAMPLE_H
    #define CGAL_THIS_IS_AN_EXAMPLE_H
    ...
    #endif // CGAL_THIS_IS_AN_EXAMPLE_H
  • Support the result_of protocol whenever your functors have more than one return type otherwise provide a result_type member typedef. An example for this is a C++03 style identity functor:
    struct Identity {
    template<typename T>
    T& operator()(T& t) { return t; }
    template<typename T>
    const T& operator()(const T& t) { return t; }
    template<typename>
    struct result;
    template<typename F, typename T>
    struct result<F(T&)> {
    typedef T& type;
    };
    template<typename F, typename T>
    struct result<F(const T&)> {
    typedef const T& type;
    };
    };

The following items can be seen as recommendations in contrast to the rules of previous paragraph.

  • Use #define sparingly.
  • Do not rename the base types of C++ using typedef.
  • When using an overloaded call, always give the exact match. Use explicit casting if necessary.
  • Do not call global functions unqualified, that is, always specify explicitly the namespace where the function is defined.

Code format

  • Use indentation with at least two spaces extra per level.
  • Write only one statement per line.
  • Use C++-style comments, e.g., // some comment.

File header

Each CGAL source file must start with a heading that allows for an easy identification of the file. The file header contains:

  • a copyright notice, specifying all the years during which the file has been written or modified, as well as the owner(s) (typically the institutions employing the authors) of this work, a pointer to the file containing its text in the CGAL distribution,
  • then, there are 2 keywords, which are automatically expanded at the creation of a new release:
    • $URL$ : canonical path to the file on github,
    • $Id$ : the release version the file is from.
  • Then SPDX license identifier. For GPL-3+ it should be SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial, and SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial for LGPL-3+.
  • Then the authors of (non-negligible parts of) this file are listed, with optional affiliation or e-mail address.

Note that since CGAL 5.0 the license text is not present in headers anymore, only SPDX tags are present.

For example and demo programs, the inclusion of the copyright notice is not necessary as this will get in the way if the program is included in the documentation. However, these files should always contain the name of the file relative to the CGAL_HOME directory (e.g., examples/Convex_hull_3/convex_hull_3.cpp) so the file can be located when seen out of context (e.g., in the documentation or from the demos web page).

For the test-suite and the documentation source, these are not distributed at the moment, so there is no policy for now.

GPL version

Here follows what this gives for a file under the GPL :

// Copyright (c) 1999,2000,2001,2002 INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
//
// $URL$
// $Id$
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
//
// Author(s) : Monique Teillaud <Monique.Teillaud@sophia.inria.fr>
// Sylvain Pion

LGPL version

Here follows what this gives for a file under the LGPL :

// Copyright (c) 2000,2001,2002,2003 Utrecht University (The Netherlands),
// ETH Zurich (Switzerland),
// INRIA Sophia-Antipolis (France),
// Max-Planck-Institute Saarbruecken (Germany),
// and Tel-Aviv University (Israel). All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL$
// $Id$
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
// Author(s) : Herve Bronnimann, Sylvain Pion

Requirements and recommendations

Requirements:

  • Follow the naming schemes outlined above.
  • Provide typedefs of template arguments as necessary to make the template parameters accessible elsewhere.
  • Label member function and parameters with const where appropriate
  • Use C++-style type casts.
  • Protect header files from multiple inclusions.
  • Obey the code format rules outlined above.
  • Provide a header for each submitted file in the proper format.
CGAL 5.5 - Manual
Coding Conventions
Author
Sven Schönherr

We do not want to impose very strict coding rules on the developers. What is most important is to follow the CGAL naming scheme described in the next section. However, there are some programming conventions (Section Programming conventions ) that should be adhered to, rules for the code format (Section Code format ), and a mandatory heading for each source file (Section File header )

Naming scheme

The CGAL naming scheme is intended to help the user use the library and the developer develop the library. The rules are simple and easy to remember. Where appropriate, they aim for similarity with the names used in the STL. Deviations from the given rules should be avoided; however, exceptions are possible if there are convincing reasons.

General rules

  • Words in the names of everything except concepts should be separated by underscores. For example, one would use function_name and Class_name instead of functionName or Classname.
  • Words in the names of concepts (e.g., template parameters) should be separated using capital letters. The only use of underscores in concept names is before the dimension suffix. For example, one should use a name such as ConvexHullTraits_2 for the concept in contrast to Convex_hull_traits_2 for the name of the class that is a model of this concept. This different naming scheme for concepts and classes was adopted mainly for two reasons (a) it is consistent with the STL (cf. InputIterator) and (b) it avoids name clashes between concepts and classes that would require one or the other to have a rather contrived name.
  • Abbreviations of words are to be avoided (e.g., use Triangulation instead of Tri). The only exceptions might be standard geometric abbreviations (such as "CH" for "convex hull") and standard data structure abbreviations (such as "DS" for "data structure"). Unfortunately, the long names that result from the absence of abbreviations are known to cause problems with some compilers.
  • Names of constants are uppercase (e.g., ORIGIN).
  • The first word of a class or enumeration name should be capitalized (e.g., Quotient, Orientation).
  • Function names are in lowercase (e.g., is_zero).
  • Boolean function names should begin with a verb. For example, use is_empty instead of simply empty and has_on_bounded_side instead of on_bounded_side.
  • Names of macros should begin with the prefix CGAL_.

Geometric objects

  • All geometric objects have the dimension as a suffix (e.g., Vector_2 and Plane_3). Exception: For \( d\)-dimensional objects there may be a dynamic and a static version. The former has the suffix _d (e.g., Point_d), while the latter has the dimension as the first template parameter (e.g., Point<d>).

Geometric data structures and algorithms

  • Names for geometric data structures and algorithms should follow the "spirit" of the rules given so far, e.g. a data structure for triangulations in the plane is named Triangulation_2, and a convex hull algorithm in 3-space is named convex_hull_3.
  • Member functions realizing predicates should start with is_ or has_, e.g. the data structure Min_ellipse_2 has member functions is_empty and has_on_bounded_side.
  • Access to data structures is given via iterators and circulators (Chapter Iterators, Circulators and Handles ). For iterators and functions returning them we extend the STL names with a prefix describing the items to be accessed. For example, the functions vertices_begin and vertices_end return a Vertex_iterator. (Note that we use the name of the items in singular for the iterator type name and in plural for the functions returning the iterator.) Names related to circulators are handled similarly, using the suffix _circulator. For example, the function edges_circulator returns an Edge_circulator.

Kernel traits

All types in the kernel concept are functor types. We distinguish the following four categories:

  1. generalized predicates, that is, standard predicates returning a Boolean value as well as functions such as orientation() that return an enumeration type (values from a finite discrete set).
  2. construction objects, which replace constructors in the kernel,
  3. constructive procedures and
  4. functors replacing operators.

As detailed below, the names of these functors reflect the actions performed by calls to operator(). This naming scheme was chosen instead of one in which the computed object determines the name because this latter naming scheme is more natural for functions that compute values where the function call can be seen as a name for the object returned instead of functors that simply maintain data associated with the computation. It was also noted that the naming of functions and functors is not consistent, either in CGAL or in the STL (In some cases the action performed by a function determines its name (e.g., multiply()) while in others the result of the action determines the name (e.g., product()).), so achieving complete consistency with an existing naming scheme is not possible.

Here are the naming rules:

  • All names in the kernel traits have the dimension as a suffix. This is necessary because in some cases (e.g., the Orientation_2 object) the absence of the suffix would cause a name conflict with an existing type or class (e.g., the enumeration type Orientation).
  • The names of generalized predicates are determined by their results. Furthermore, names are as much as possible consistent with the current kernel and the STL. So, for example, we have objects like Has_on_bounded_side_2, Is_degenerate_2, and Is_horizontal_2. According to the current kernel we also have Left_turn_2. For reasons of consistency with STL, all "less-than"-objects start with Less_, e.g., Less_xy_2. Further examples are Less_distance_to_point_2 and Less_distance_to_line_2. However, we have Equal_2, whereas the corresponding STL functor is called equal_to. Here, we give our dimension rule higher priority.
  • The names of construction objects (category 2 above) follow the pattern Construct_type_d, where type_d is the type constructed, e.g., Construct_point_2 and Construct_line_2. The operator() of these functor classes is overloaded. This reduces the number of names to remember drastically, while replacing one of the constructions gets more complicated, but is still possible.
  • Functors in category 3 above can be further subdivided into two classes:

    • constructive procedures that construct objects whose types are known a priori
    • procedures that construct objects whose types are not known a priori

    The names of functors in the first class also start with Construct_ whenever a geometric object is constructed, otherwise they start with Compute_. Here, real numbers are not considered to be 1-dimensional geometric objects. For example, on the one hand we have Construct_perpendicular_vector_2, Construct_midpoint_3, Construct_circumcenter_d, Construct_bisector_2, and Construct_point_on_3, while on the other hand there are Compute_area_2 and Compute_squared_length_3.

    For the second class, the names of the objects describe the (generic) action, e.g. Intersect_2.

  • The equality operator (operator==()) is replaced by function objects with names of the form Equal_k, where k is the dimension number (i.e., 2, 3, or d). For replacing arithmetic operators, we might also provide Add_2, Subtract_2, Multiply_2, and Divide_2. (As mentioned above, the action determines the name, not the result.) We think that these objects are not really needed. They are likely to be part of primitive operations that have a corresponding function object in the traits.

In addition, for each functor the kernel traits class has a member function that returns an instance of this functor. The name of this function should be the (uncapitalized) name of the functor followed by the suffix _object.For example, the function that returns an instance of the Less_xy_2 functor is called less_xy_2_object.

File names

  • File names should be chosen in the "spirit" of the naming rules given above.
  • If a single geometric object, data structure, or algorithm is provided in a single file, its name (and its capitalization) should be used for the file name. For example, the file Triangulation_2.h contains the data structure Triangulation_2.
  • If a file does not contain a single class, its name should not begin with a capital letter.
  • No two files should have the same names even when capitalization is ignored. This is to prevent overwriting of files on operating systems where file names are not case sensitive. A package that contains file names that are the same as files already in the release will be rejected by the submission script.
  • The names of files should not contain any characters not allowed by all the platforms the library supports. In particular, it should not contain the characters ':', '*', or ' '.
  • Internal header files - which are not documented to the user - should have Package/internal/ as a directory higher up in their hierarchy. For example CGAL/Triangulation_2/internal/predicates/my_pred.h.

Programming conventions

The first list of items are meant as rules, i.e., you should follow them.

  • Give typedefs for all template arguments of a class that may be accessed later from outside the class. The template parameter is a concept and should follow the concept naming scheme outlines in the previous section. As a general rule, the typedef should identify the template parameter with a type of the same name that follows the naming convention of types. For example
    template < class GeometricTraits_2 >
    class Something {
    public:
    typedef GeometricTraits_2 Geometric_traits_2;
    };
    For one-word template arguments, the template parameter name should be followed by an underscore. (Note that using a preceding underscore is not allowed according to the C++ standard; all such names are reserved.)
    template < class Arg_ >
    class Something {
    public:
    typedef Arg_ Arg;
    };
  • Use const when a call by reference argument is not modified, e.g. int f( const A& a).
  • Use const to indicate that a member function does not modify the object to which it is applied, e.g., class A { int f( void) const; };. This should also be done when it is only conceptually const. This means that the member function f() is const as seen from the outside, but internally it may modify some data members that are declared mutable. An example is the caching of results from expensive computations. For more information about conceptually const functions and mutable data members see [9].
  • Prefer C++-style to C-style casts, e.g., use static_cast<double>( i) instead of (double)i.
  • Protect header files against multiple inclusion, e.g. the file This_is_an_example.h should begin/end with
    #ifndef CGAL_THIS_IS_AN_EXAMPLE_H
    #define CGAL_THIS_IS_AN_EXAMPLE_H
    ...
    #endif // CGAL_THIS_IS_AN_EXAMPLE_H
  • Support the result_of protocol whenever your functors have more than one return type otherwise provide a result_type member typedef. An example for this is a C++03 style identity functor:
    struct Identity {
    template<typename T>
    T& operator()(T& t) { return t; }
    template<typename T>
    const T& operator()(const T& t) { return t; }
    template<typename>
    struct result;
    template<typename F, typename T>
    struct result<F(T&)> {
    typedef T& type;
    };
    template<typename F, typename T>
    struct result<F(const T&)> {
    typedef const T& type;
    };
    };

The following items can be seen as recommendations in contrast to the rules of previous paragraph.

  • Use #define sparingly.
  • Do not rename the base types of C++ using typedef.
  • When using an overloaded call, always give the exact match. Use explicit casting if necessary.
  • Do not call global functions unqualified, that is, always specify explicitly the namespace where the function is defined.

Code format

  • Use indentation with at least two spaces extra per level.
  • Write only one statement per line.
  • Use C++-style comments, e.g., // some comment.

File header

Each CGAL source file must start with a heading that allows for an easy identification of the file. The file header contains:

  • a copyright notice, specifying all the years during which the file has been written or modified, as well as the owner(s) (typically the institutions employing the authors) of this work, a pointer to the file containing its text in the CGAL distribution,
  • then, there are 2 keywords, which are automatically expanded at the creation of a new release:
    • $URL$ : canonical path to the file on github,
    • $Id$ : the release version the file is from.
  • Then SPDX license identifier. For GPL-3+ it should be SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial, and SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial for LGPL-3+.
  • Then the authors of (non-negligible parts of) this file are listed, with optional affiliation or e-mail address.

Note that since CGAL 5.0 the license text is not present in headers anymore, only SPDX tags are present.

For example and demo programs, the inclusion of the copyright notice is not necessary as this will get in the way if the program is included in the documentation. However, these files should always contain the name of the file relative to the CGAL_HOME directory (e.g., examples/Convex_hull_3/convex_hull_3.cpp) so the file can be located when seen out of context (e.g., in the documentation or from the demos web page).

For the test-suite and the documentation source, these are not distributed at the moment, so there is no policy for now.

GPL version

Here follows what this gives for a file under the GPL :

// Copyright (c) 1999,2000,2001,2002 INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
//
// $URL$
// $Id$
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
//
// Author(s) : Monique Teillaud <Monique.Teillaud@sophia.inria.fr>
// Sylvain Pion

LGPL version

Here follows what this gives for a file under the LGPL :

// Copyright (c) 2000,2001,2002,2003 Utrecht University (The Netherlands),
// ETH Zurich (Switzerland),
// INRIA Sophia-Antipolis (France),
// Max-Planck-Institute Saarbruecken (Germany),
// and Tel-Aviv University (Israel). All rights reserved.
//
// This file is part of CGAL (www.cgal.org)
//
// $URL$
// $Id$
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
// Author(s) : Herve Bronnimann, Sylvain Pion

Requirements and recommendations

Requirements:

  • Follow the naming schemes outlined above.
  • Provide typedefs of template arguments as necessary to make the template parameters accessible elsewhere.
  • Label member function and parameters with const where appropriate
  • Use C++-style type casts.
  • Protect header files from multiple inclusions.
  • Obey the code format rules outlined above.
  • Provide a header for each submitted file in the proper format.