STL Extensions for CGAL

CGAL is designed in the spirit of the generic programming paradigm to work together with the Standard Template Library (STL) [C++96, MS96]. This chapter documents non-geometric STL-like components that are not provided in the STL standard but in CGAL: a doubly-connected list managing items in place (where inserted items are not copied), generic functions, function objects for projection and creation, classes for composing function objects and adaptor classes around iterators and circulators. See also circulators in Chapter .

Doubly-Connected List Managing Items in Place

The class CGAL_In_place_list<T,bool,&T::next,&T::prev> manages a sequence of items in place in a doubly-connected list. Its goals are the flexible handling of memory management and performance optimization. The item type is supposed to provide the two necessary pointers &T::next_link and &T::prev_link. One possibility to obtain these pointers is to inherit them from the base class CGAL_In_place_list_base<T>.

The class CGAL_In_place_list<T> is a container and quite similar to STL containers, with the advantage that it is able to handle the stored elements by reference instead of copying them. It is possible to delete an element only knowing its address and no iterator to it. This simplifies mutually pointered data structures like a halfedge data structure for planar maps or polyhedral surfaces. The usual iterators are also available. Another container with this property of working with pointers to objects is the STL vector (at least in the current STL implementations).

Base Classes for List Nodes

Definition

#include <CGAL/In_place_list.h>

• Class declaration of CGAL_In_place_list_base<T>.

• Class declaration of CGAL_In_place_list<T,bool>.

Generic Functions

Copy $n$ Items

CGAL_copy_n() copies $n$ items from an input iterator to an output iterator which is useful for possibly infinite sequences of random geometric objects[^1].

#include <CGAL/copy_n.h>

template <class InputIterator, class Size, class OutputIterator>
OutputIterator	CGAL_copy_n ( InputIterator first, Size n, OutputIterator result)
		copies the first $n$ items from first to result. Returns the value of result after inserting the $n$ items.

See Also

Function Objects

Two kinds of function objects are provided: Projections and Creators.

Projection Function Objects

Definition

#include <CGAL/function_objects.h>

Operations

Creation

CGAL_Identity<Value> o;
	the identity function for projection objects. argument_type and result_type are equal to Value.

CGAL_Compose<Fct1, Fct2> o;
	composes two projections: $$Fct1$$o Fct2$$o x = Fct1()( Fct2()(x))$$. argument_type is equal to Fct2::argument_type, result_type to Fct1::result_type.

CGAL_Dereference<Value> o;
	dereferences a pointer. argument_type is equal to Value* and result_type is equal to Value.

CGAL_Get_address<Value> o;
	Get the address for a reference. argument_type is equal to Value and result_type is equal to Value*.

CGAL_Cast_function_object<Arg, Result> o;
	applies a C-style type cast to its argument. argument_type is equal to Arg and result_type is equal to Result.

The following function objects are provided with respect to the polyhedral surfaces in the basic library.

CGAL_Project_vertex<Node> o;
	calls the member function vertex() on an instance of type Node. argument_type is equal to Node and result_type is equal to Node::Vertex.

CGAL_Project_facet<Node> o;
	calls the member function facet() on an instance of type Node. argument_type is equal to Node and result_type is equal to Node::Facet.

CGAL_Project_point<Node> o;
	calls the member function point() on an instance of type Node. argument_type is equal to Node and result_type is equal to Node::Point.

CGAL_Project_normal<Node> o;
	calls the member function normal() on an instance of type Node. argument_type is equal to Node and result_type is equal to Node::Normal.

CGAL_Project_plane<Node> o;
	calls the member function plane() on an instance of type Node. argument_type is equal to Node and result_type is equal to Node::Plane.

CGAL_Project_next<Node> o;
	calls the member function next() on an instance of type Node. argument_type and result_type are equal to Node*.

CGAL_Project_prev<Node> o;
	calls the member function prev() on an instance of type Node. argument_type and result_type are equal to Node*.

CGAL_Project_next_opposite<Node> o;
	calls the member functions next()->opposite() on an instance of type Node. argument_type and result_type are equal to Node*.

CGAL_Project_opposite_prev<Node> o;
	calls the member functions opposite()->prev() on an instance of type Node. argument_type and result_type are equal to Node*.

Creator Function Objects

Definition

#include <CGAL/function_objects.h>

Operations

Creation

CGAL_Creator_1<Arg, Result> o;
	applies the constructor Result(Arg). result_type is equal to Result.

...

CGAL_Creator_5<Arg1, Arg2, Arg3, Arg4, Arg5, Result> o;
	applies the constructor Result(Arg1, Arg2, Arg3, Arg4, Arg5) . result_type is equal to Result.

The following creator function objects are available for two to nine arguments (one argument is already captured with CGAL_Creator_1):

CGAL_Creator_uniform_2<Arg, Result> o;
	applies the constructor Result(Arg,Arg). result_type is equal to Result.

...

CGAL_Creator_uniform_9<Arg, Result> o;
	applies the constructor for Result with nine arguments of type Arg. result_type is equal to Result.

See Also

Classes for Composing Function Objects

Although not mentioned in the ANSI draft(CD2), most STL implementations provide two global functions for composing function objects, compose1 and compose2, defined in function.h. Since for both the resulting function is unary, one can only construct unary function objects in this way. This seems to be quite a limitation, since many (also STL) algorithms can be parameterized with binary (e.g. comparison) functions.

In analogy to STL compose1/2 we define two functions, CGAL_compose1_2 and CGAL_compose2_2, that can be used to construct a binary function object via composition.

• Class declaration of AdaptableUnaryFunction.

• Class declaration of AdaptableBinaryFunction.

Composing Binary into Unary Functions

#include <CGAL/function_objects.h>

template < class Operation1, class Operation2 >
Composition	CGAL_compose1_2 ( Operation1 op1, Operation2 op2)

Operation1 must be an adaptable unary function, Operation2 an adaptable binary function and Operation2::result_type convertible to Operation1::argument_type. Then CGAL_compose1_2 returns an adaptable binary function object c (of some complicated type Composition) such that

Operation1::result_type
	c ( Operation2::first_argument_type x, Operation2::second_argument_type y)

is equal to Operation1()( Operation2()( x, y)).

Composing Unary into Binary Functions

#include <CGAL/function_objects.h>

template < class Operation1, class Operation2, class Operation3 >
Composition	CGAL_compose2_2 ( Operation1 op1, Operation2 op2, Operation3 op3)

Operation1 must be an adaptable binary function, Operation2 and Operation3 must be adaptable unary functions, Operation2::result_type must be convertible to Operation1::first_argument_type and Operation3::result_type must be convertible to Operation1::second_argument_type. Then CGAL_compose2_2 returns an adaptable binary function object c (of some complicated type Composition) such that

Operation1::result_type
	c ( Operation2::first_argument_type x, Operation2::second_argument_type y)

is equal to Operation1()( Operation2()( x), Operation3()( y)).

Adaptor Classes around Iterators and Circulators

• Class declaration of CGAL_Counting_iterator<Iterator, Value>.

• Class declaration of CGAL_N_step_adaptor<I,int N,Ref,Ptr,Val,Dst,Ctg>.

Joining Input Iterator Streams

Definition

#include <CGAL/Join_input_iterator.h>

Creation

CGAL_Join_input_iterator_1<Iterator, Creator> join ( Iterator i);
	the join of a single iterator $i$. Applies Creator to each item read from $i$. value_type is equal to Creator::result_type.

...

CGAL_Join_input_iterator_5<I1, I2, I3, I4, I5, Creator> join ( I1 i1, I2 i2, I3 i3, I4 i4, I5 i5);
	the join of five iterators i1 to i5. Applies Creator with five arguments *i1 up to *i5. value_type is equal to Creator::result_type.

See Also

• Class declaration of CGAL_Inverse_index<IC>.

• Class declaration of CGAL_Random_access_adaptor<IC>.

• Class declaration of CGAL_Random_access_value_adaptor<IC,T>.

Footnotes

1. The STL release June 13, 1997, from SGI has a new function copy_n which is equivalent with CGAL_copy_n.