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 In_place_list<T,&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 In_place_list_base<T>.

The class 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

The node base classes provides pointers to build linked lists. The class In_place_sl_list_base<T> provides a pointer next_link for a single linked list. The class In_place_list_base<T> provides an additional pointer prev_link for doubly linked lists. These names conform to the default parameters used in the template argument lists of the container classes. The pointers are public members.

#include <CGAL/In_place_list.h>

• Class declaration of In_place_list_base<T>.

• Class declaration of In_place_list<T,bool>.

Generic Functions

Copy $$n Items

copy_n() copies $$n items from an input iterator to an output iterator which is useful for possibly infinite sequences of random geometric objects¹.

#include <CGAL/algorithm.h>

template <class InputIterator, class Size, class OutputIterator>
OutputIterator	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

Counting_iterator.

Computing Minimal and Maximal Elements

min_max_element() computes the minimal and the maximal element of a range. It is modeled after the STL functions min_element and max_element. The advantage of min_max_element compared to calling both STL functions is that one only iterates once over the sequence. This is more efficient especially for large and/or complex sequences.

#include <CGAL/algorithm.h>

template < class ForwardIterator >
std::pair< ForwardIterator, ForwardIterator >
	min_max_element ( ForwardIterator first, ForwardIterator last)
		return a pair of iterators where the first component refers to the minimal and the second component refers to the maximal element in the range [first, last). The ordering is defined by the operator< on the value type of ForwardIterator.
template < class ForwardIterator, class CompareMin, class CompareMax >
std::pair< ForwardIterator, ForwardIterator >
	min_max_element ( ForwardIterator first, ForwardIterator last, CompareMin comp_min, CompareMax comp_max)
		return a pair of iterators where the first component refers to the minimal and the second component refers to the maximal element in the range [first, last). CompareMin and CompareMax are adaptable binary function objects: VT $$ ×  VT $$  bool where VT is the value type of ForwardIterator.

Example

#include <CGAL/algorithm.h>
#include <vector>
#include <iostream>

using std::vector;
using std::pair;
using std::cout;
using std::endl;
using CGAL::min_max_element;

int main()
{
  vector< int > v;
  v.push_back(3);
  v.push_back(6);
  v.push_back(5);
  typedef std::vector< int >::iterator iterator;
  pair< iterator, iterator > p = min_max_element(v.begin(), v.end());
  cout << "min = " << *p.first << ", max = " << *p.second << endl;
  return 0;
}

Computing Minimal/Maximal Elements of Subsets

min_element_if() and min_element_if() compute the minimum respectively maximum among the elements of a range which satisfy a certain predicate. They are modeled after the STL functions min_element and max_element.

#include <CGAL/algorithm.h>

template < class ForwardIterator, class Predicate >
ForwardIterator	min_element_if ( ForwardIterator first, ForwardIterator last, Predicate pred)
		return an iterator referring to the minimal element among those satifying the predicate pred in the range [first, last). The ordering is defined by the operator< on VT where VT is the value type of ForwardIterator. pred is an unary function object: VT $$  bool.
template < class ForwardIterator, class Predicate >
ForwardIterator	max_element_if ( ForwardIterator first, ForwardIterator last, Predicate pred)
		return an iterator referring to the maximal element among those satifying the predicate pred in the range [first, last). The ordering is defined by the operator< on VT where VT is the value type of ForwardIterator. pred is an unary function object: VT $$  bool.
template < class ForwardIterator, class Compare, class Predicate >
ForwardIterator	min_element_if ( ForwardIterator first, ForwardIterator last, Compare comp, Predicate pred)
		return an iterator referring to the minimal element among those satifying the predicate pred in the range [first, last). The ordering is defined by the binary function object comp: VT $$ ×  VT $$  bool where VT is the value type of ForwardIterator. pred is an unary function object: VT $$  bool.
template < class ForwardIterator, class Compare, class Predicate >
ForwardIterator	max_element_if ( ForwardIterator first, ForwardIterator last, Compare comp, Predicate pred)
		return an iterator referring to the maximal element among those satifying the predicate pred in the range [first, last). The ordering is defined by the binary function object comp: VT $$ ×  VT $$  bool where VT is the value type of ForwardIterator. pred is an unary function object: VT $$  bool.

Example

#include <CGAL/algorithm.h>
#include <vector>
#include <iostream>
#include <functional>

using std::vector;
using std::cout;
using std::endl;
using std::modulus;
using std::greater;
using std::compose1;
using std::bind2nd;
using CGAL::min_element_if;

int main()
{
  vector< int > v;
  v.push_back(3);
  v.push_back(5);
  v.push_back(2);
  cout << "min_odd = "
       << *min_element_if(v.begin(), 
			  v.end(), 
			  compose1(bind2nd(greater< int >(), 0),
				   bind2nd(modulus< int >(), 2)))
       << endl;
  return 0;
}

Function Objects

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

Projection Function Objects

Definition

A projection function object $$o of type $$O has an unary parentheses operator expecting an argument of type O::argument_type as a reference or constant reference, and returns a reference or constant reference of type O::result_type respectively.

#include <CGAL/function_objects.h>

Operations

O::result_type&	o.operator() ( O::argument_type &) const
const O::result_type&
	o.operator() ( const O::argument_type &) const

Creation

The following projection function objects are available:

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

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

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

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

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.

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.

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.

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.

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.

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.

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

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

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*.

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

A creator function object $$o of type $$O has a parentheses operator which acts like a constructor. The operator might expect arguments and returns an instance of type O::result_type.

#include <CGAL/function_objects.h>

Operations

O::result_type

o.operator() ( ...) const

Creation

The following creator function objects are available for one to five arguments:

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

...

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 Creator_1):

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

...

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

Join_input_iterator_1 ....

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, compose1_2 and 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	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 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	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 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 Counting_iterator<Iterator, Value>.

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

Joining Input Iterator Streams

Definition

A join of $$n input iterators and a creator function object is again an input iterator which reads an object from each stream and applies the creator function object on them whenever it advances.

#include <CGAL/Join_input_iterator.h>

Creation

The following join input iterator objects are available for one to five iterators:

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.

...

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

Creator_1 ... and Creator_uniform_2 ....

• Class declaration of Inverse_index<IC>.

• Class declaration of Random_access_adaptor<IC>.

• Class declaration of 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 copy_n.