SPAR/AIModule/BWTA/vendors/CGAL/CGAL/HalfedgeDS_list.h

Go to the documentation of this file.

// Copyright (c) 1997  Utrecht University (The Netherlands),
// ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany),
// INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg
// (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria),
// and Tel-Aviv University (Israel).  All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; version 2.1 of the License.
// See the file LICENSE.LGPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/HalfedgeDS/include/CGAL/HalfedgeDS_list.h $
// $Id: HalfedgeDS_list.h 28567 2006-02-16 14:30:13Z lsaboret $
// 
//
// Author(s)     : Lutz Kettner  <kettner@mpi-sb.mpg.de>

#ifndef CGAL_HALFEDGEDS_LIST_H
#define CGAL_HALFEDGEDS_LIST_H 1

#include <CGAL/In_place_list.h>
#include <CGAL/HalfedgeDS_items_decorator.h>
#include <CGAL/memory.h>
#include <CGAL/Unique_hash_map.h>
#include <cstddef>

CGAL_BEGIN_NAMESPACE

template < class VertexBase>
class HalfedgeDS_in_place_list_vertex
    : public VertexBase, public In_place_list_base<
                      HalfedgeDS_in_place_list_vertex< VertexBase> > {
public:
    typedef HalfedgeDS_in_place_list_vertex< VertexBase> Self;
    typedef typename VertexBase::Vertex_handle       Vertex_handle;
    typedef typename VertexBase::Vertex_const_handle Vertex_const_handle;
    HalfedgeDS_in_place_list_vertex() {}
    HalfedgeDS_in_place_list_vertex( const VertexBase& v)   // down cast
        : VertexBase(v) {}
    Self& operator=( const Self& v) {
        // This self written assignment avoids that assigning vertices will
        // overwrite the list linking of the target vertex.
        *((VertexBase*)this) = ((const VertexBase&)v);
        return *this;
    }
};

template < class HalfedgeBase>
class HalfedgeDS_in_place_list_halfedge
    : public HalfedgeBase, public In_place_list_base<
                  HalfedgeDS_in_place_list_halfedge< HalfedgeBase> > {
public:
    typedef HalfedgeDS_in_place_list_halfedge< HalfedgeBase> Self;
    typedef typename HalfedgeBase::Halfedge_handle       Halfedge_handle;
    typedef typename HalfedgeBase::Halfedge_const_handle
                                                    Halfedge_const_handle;
    HalfedgeDS_in_place_list_halfedge() {}                   // down cast
    HalfedgeDS_in_place_list_halfedge( const HalfedgeBase& h)
        : HalfedgeBase(h) {}
    Self& operator=( const Self& h) {
        // This self written assignment avoids that assigning halfedges will
        // overwrite the list linking of the target halfedge.
        *((HalfedgeBase*)this) = ((const HalfedgeBase&)h);
        return *this;
    }
};

template < class FaceBase>
class HalfedgeDS_in_place_list_face
    : public FaceBase, public In_place_list_base<
                            HalfedgeDS_in_place_list_face< FaceBase> > {
public:
    typedef HalfedgeDS_in_place_list_face< FaceBase>  Self;
    typedef typename FaceBase::Face_handle       Face_handle;
    typedef typename FaceBase::Face_const_handle Face_const_handle;
    HalfedgeDS_in_place_list_face() {}                   // down cast
    HalfedgeDS_in_place_list_face( const FaceBase& f) : FaceBase(f) {}
    Self& operator=( const Self& f) {
        // This self written assignment avoids that assigning faces will
        // overwrite the list linking of the target face.
        *((FaceBase*)this) = ((const FaceBase&)f);
        // this->FaceBase::operator=(f); // does not compile on SGI
        return *this;
    }
};

template < class Traits_, class HalfedgeDSItems, class Alloc>
class HalfedgeDS_list_types {
public:
    typedef HalfedgeDS_list_types<Traits_, HalfedgeDSItems, Alloc> Self;
    typedef Traits_                                    Traits;
    typedef HalfedgeDSItems                            Items;
    typedef Alloc                                      Allocator;
    typedef Alloc                                      allocator_type;

    typedef typename Items::template Vertex_wrapper<Self,Traits>
                                                       Vertex_wrapper;
    typedef typename Items::template Halfedge_wrapper<Self,Traits> 
                                                       Halfedge_wrapper;
    typedef typename Items::template Face_wrapper<Self,Traits>
                                                       Face_wrapper;

    typedef typename Vertex_wrapper::Vertex            Vertex_base;
    typedef HalfedgeDS_in_place_list_vertex< Vertex_base> Vertex;
    typedef typename Halfedge_wrapper::Halfedge        Halfedge_base;
    typedef HalfedgeDS_in_place_list_halfedge< Halfedge_base> Halfedge;
    typedef typename Face_wrapper::Face                Face_base;
    typedef HalfedgeDS_in_place_list_face< Face_base>  Face;

    typedef typename Allocator::template rebind< Vertex> Vertex_alloc_rebind;
    typedef typename Vertex_alloc_rebind::other        Vertex_allocator;
    typedef typename Allocator::template rebind< Halfedge>
                                                       Halfedge_alloc_rebind;
    typedef typename Halfedge_alloc_rebind::other      Halfedge_allocator;
    typedef typename Allocator::template rebind< Face> Face_alloc_rebind;
    typedef typename Face_alloc_rebind::other          Face_allocator;

    typedef In_place_list<Vertex,false,Vertex_allocator>  Vertex_list;
    typedef typename Vertex_list::iterator             Vertex_handle;
    typedef typename Vertex_list::const_iterator       Vertex_const_handle;
    typedef typename Vertex_list::iterator             Vertex_iterator;
    typedef typename Vertex_list::const_iterator       Vertex_const_iterator;

    typedef In_place_list<Halfedge,false,Halfedge_allocator>  Halfedge_list;
    typedef typename Halfedge_list::iterator           Halfedge_handle;
    typedef typename Halfedge_list::const_iterator     Halfedge_const_handle;
    typedef typename Halfedge_list::iterator           Halfedge_iterator;
    typedef typename Halfedge_list::const_iterator     Halfedge_const_iterator;

    typedef In_place_list<Face,false,Face_allocator>   Face_list;
    typedef typename Face_list::iterator               Face_handle;
    typedef typename Face_list::const_iterator         Face_const_handle;
    typedef typename Face_list::iterator               Face_iterator;
    typedef typename Face_list::const_iterator         Face_const_iterator;

    typedef typename Halfedge_list::size_type          size_type;
    typedef typename Halfedge_list::difference_type    difference_type;
    typedef std::bidirectional_iterator_tag            iterator_category;
    static inline Vertex_handle vertex_handle( Vertex_base* v) {
        Vertex* vv = 0;
        vv = (Vertex*)((char*) v - (std::ptrdiff_t)((Vertex_base*)vv));
        return vv;
    }
    static inline Vertex_const_handle vertex_handle( const Vertex_base* v) {
        const Vertex* vv = 0;
        vv = (const Vertex*)((const char*) v -
                 (std::ptrdiff_t)((const Vertex_base*)vv));
        return vv;
    }

    static inline Halfedge_handle halfedge_handle( Halfedge_base* h) {
        Halfedge* hh = 0;
        hh = (Halfedge*)((char*) h - (std::ptrdiff_t)((Halfedge_base*)hh));
        return hh;
    }
    static inline
    Halfedge_const_handle halfedge_handle( const Halfedge_base* h) {
        const Halfedge* hh = 0;
        hh = (const Halfedge*)((const char*) h -
                 (std::ptrdiff_t)((const Halfedge_base*)hh));
        return hh;
    }

    static inline Face_handle face_handle( Face_base* f) {
        Face* ff = 0;
        ff = (Face*)((char*) f - (std::ptrdiff_t)((Face_base*)ff));
        return ff;
    }
    static inline Face_const_handle face_handle( const Face_base* f) {
        const Face* ff = 0;
        ff = (const Face*)((const char*)f -
                 (std::ptrdiff_t)((const Face_base*)ff));
        return ff;
    }
};

#ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
template < class Traits_, class HalfedgeDSItems, 
           class Alloc = CGAL_ALLOCATOR(int)>
class HalfedgeDS_list
    : public HalfedgeDS_list_types<Traits_, HalfedgeDSItems, Alloc> {
public:
    typedef HalfedgeDS_list<Traits_, HalfedgeDSItems, Alloc> Self;
#else
struct HalfedgeDS_list {
template < class Traits_, class HalfedgeDSItems, 
           class Alloc = CGAL_ALLOCATOR(int)>
class HDS : public HalfedgeDS_list_types<Traits_, HalfedgeDSItems, Alloc> {
public:
    typedef HDS<Traits_, HalfedgeDSItems, Alloc> Self;
#endif
public:
    typedef HalfedgeDS_list_types<Traits_, HalfedgeDSItems, Alloc> Types;
    typedef typename Types::Traits                     Traits;
    typedef typename Types::Items                      Items;
    typedef typename Types::Allocator                  Allocator;
    typedef typename Types::allocator_type             allocator_type;

    typedef typename Types::Vertex                     Vertex;
    typedef typename Types::Halfedge                   Halfedge;
    typedef typename Types::Face                       Face;

    typedef typename Types::Vertex_allocator           Vertex_allocator;
    typedef typename Types::Vertex_list                Vertex_list;
    typedef typename Types::Vertex_handle              Vertex_handle;
    typedef typename Types::Vertex_const_handle        Vertex_const_handle;
    typedef typename Types::Vertex_iterator            Vertex_iterator;
    typedef typename Types::Vertex_const_iterator      Vertex_const_iterator;

    typedef typename Types::Halfedge_allocator         Halfedge_allocator;
    typedef typename Types::Halfedge_list              Halfedge_list;
    typedef typename Types::Halfedge_handle            Halfedge_handle;
    typedef typename Types::Halfedge_const_handle      Halfedge_const_handle;
    typedef typename Types::Halfedge_iterator          Halfedge_iterator;
    typedef typename Types::Halfedge_const_iterator    Halfedge_const_iterator;

    typedef typename Types::Face_allocator             Face_allocator;
    typedef typename Types::Face_list                  Face_list;
    typedef typename Types::Face_handle                Face_handle;
    typedef typename Types::Face_const_handle          Face_const_handle;
    typedef typename Types::Face_iterator              Face_iterator;
    typedef typename Types::Face_const_iterator        Face_const_iterator;

    typedef typename Types::size_type                  size_type;
    typedef typename Types::difference_type            difference_type;
    typedef typename Types::iterator_category          iterator_category;

    typedef Tag_true                                   Supports_removal;

    typedef typename Vertex::Supports_vertex_halfedge Supports_vertex_halfedge;
    typedef typename Halfedge::Supports_halfedge_prev Supports_halfedge_prev;
    typedef typename Halfedge::Supports_halfedge_vertex
                                                      Supports_halfedge_vertex;
    typedef typename Halfedge::Supports_halfedge_face
                                                      Supports_halfedge_face;
    typedef typename Face::Supports_face_halfedge     Supports_face_halfedge;

    // Halfedges are allocated in pairs. Here is the type for that.
    typedef std::pair<Halfedge,Halfedge>              Halfedge_pair;

    typedef typename Allocator::template rebind< Halfedge_pair>
                                                       Edge_alloc_rebind;
    typedef typename Edge_alloc_rebind::other          Edge_allocator;

protected:
    // Changed from static to local variable
    Vertex_allocator vertex_allocator;
    Edge_allocator   edge_allocator;  // allocates pairs of halfedges
    Face_allocator   face_allocator;
    
    Vertex* get_vertex_node( const Vertex& t) {
        Vertex* p = vertex_allocator.allocate(1);
        vertex_allocator.construct(p, t);
        return p;
    }
    void put_vertex_node( Vertex* p) {
        vertex_allocator.destroy( p);
        vertex_allocator.deallocate( p, 1);
    }

    Halfedge* get_edge_node( const Halfedge& h, const Halfedge& g) {
        // creates a new pair of opposite border halfedges.
        Halfedge_pair* hpair = edge_allocator.allocate(1);
        edge_allocator.construct(hpair, Halfedge_pair( h, g));
        Halfedge* h2 = &(hpair->first);
        Halfedge* g2 = &(hpair->second);
        CGAL_assertion( h2 == (Halfedge*)hpair);
        CGAL_assertion( g2 == h2 + 1);
        h2->HBase_base::set_opposite(g2);
        g2->HBase_base::set_opposite(h2);
        return h2;
    }
    void put_edge_node( Halfedge* h) {
        // deletes the pair of opposite halfedges h and h->opposite().
        Halfedge_handle g = h->opposite();
        Halfedge_pair* hpair = (Halfedge_pair*)(&*h);
        if ( &*h > &*g)
            hpair = (Halfedge_pair*)(&*g);
        CGAL_assertion( &(hpair->first) == (Halfedge*)hpair);
        edge_allocator.destroy( hpair);
        edge_allocator.deallocate( hpair, 1);
    }

    Face* get_face_node( const Face& t) {
        Face* p = face_allocator.allocate(1);
        face_allocator.construct(p, t);
        return p;
    }
    void put_face_node( Face* p) {
        face_allocator.destroy( p);
        face_allocator.deallocate( p, 1);
    }

    typedef typename Vertex::Base                      VBase;
    typedef typename Halfedge::Base                    HBase;
    typedef typename Halfedge::Base_base               HBase_base;
    typedef typename Face::Base                        FBase;

    Vertex_list        vertices;
    Halfedge_list      halfedges;
    Face_list          faces;

    size_type          nb_border_halfedges;
    size_type          nb_border_edges;
    Halfedge_iterator  border_halfedges;

// CREATION

private:
    void pointer_update( const Self& hds) {
        // Update own pointers assuming that they lived previously
        // in a halfedge data structure `hds' with lists.
        // Update own pointers assuming that they lived previously
        // in a halfedge data structure `hds' with lists.
        typedef Unique_hash_map< Vertex_const_iterator, Vertex_iterator> V_map;
        typedef Unique_hash_map< Halfedge_const_iterator, Halfedge_iterator>
                                                                         H_map;
        typedef Unique_hash_map< Face_const_iterator, Face_iterator>     F_map;
        // initialize maps.
        H_map h_map( hds.halfedges_begin(), hds.halfedges_end(),
                     halfedges_begin(), Halfedge_iterator(), 
                     3 * hds.size_of_halfedges() / 2);
        Vertex_iterator vii;
        V_map v_map( vii, 3 * hds.size_of_vertices() / 2);
        Face_iterator fii;
        F_map f_map( fii, 3 * hds.size_of_faces() / 2);
        // some special values
        h_map[Halfedge_const_iterator()] = Halfedge_iterator();
        h_map[hds.halfedges_end()]       = halfedges_end();
        v_map[Vertex_const_iterator()]   = Vertex_iterator();
        v_map[hds.vertices_end()]        = vertices_end();
        f_map[Face_const_iterator()]     = Face_iterator();
        f_map[hds.faces_end()]           = faces_end();
        // vertices and faces are optional
        if ( check_tag( Supports_halfedge_vertex())) {
            v_map.insert( hds.vertices_begin(),
                          hds.vertices_end(),
                          vertices_begin());
        }
        if ( check_tag( Supports_halfedge_face())) {
            f_map.insert( hds.faces_begin(), hds.faces_end(), faces_begin());
        }
        HalfedgeDS_items_decorator<Self> D;
        for (Halfedge_iterator h = halfedges_begin(); h!=halfedges_end(); ++h){
            h->HBase::set_next( h_map[ h->next()]);
            // Superfluous and false: opposite pointer get set upon creation
            // h->HBase_base::set_opposite( h_map[ h->opposite()]);
            if ( check_tag( Supports_halfedge_prev()))
                D.set_prev( h, h_map[ D.get_prev(h)]);
            if ( check_tag( Supports_halfedge_vertex()))
                D.set_vertex( h, v_map[ D.get_vertex(h)]);
            if ( check_tag( Supports_halfedge_face()))
                D.set_face( h, f_map[ D.get_face(h)]);
        }
        border_halfedges = h_map[ border_halfedges];
        if (check_tag( Supports_vertex_halfedge())) {
            for (Vertex_iterator v = vertices_begin(); v != vertices_end();++v)
                D.set_vertex_halfedge(v, h_map[ D.get_vertex_halfedge(v)]);
        }
        if (check_tag( Supports_face_halfedge())) {
            for ( Face_iterator f = faces_begin(); f != faces_end(); ++f)
                D.set_face_halfedge(f, h_map[ D.get_face_halfedge(f)]);
        }
        //h_map.statistics();
        //v_map.statistics();
        //f_map.statistics();
    }

public:
#ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
    HalfedgeDS_list()
        : nb_border_halfedges(0), nb_border_edges(0) {}
        // the empty polyhedron `P'.

    HalfedgeDS_list( size_type, size_type, size_type)
        : nb_border_halfedges(0), nb_border_edges(0) {}
        // Parameter order is v,h,f.
        // a polyhedron `P' with storage reserved for v vertices, h
        // halfedges, and f faces. The reservation sizes are a hint for
        // optimizing storage allocation. They are not used here.

    ~HalfedgeDS_list() { clear(); }

    HalfedgeDS_list( const Self& hds)
#else
    HDS() : nb_border_halfedges(0), nb_border_edges(0) {}
    HDS( size_type, size_type, size_type)
          : nb_border_halfedges(0), nb_border_edges(0) {}
    ~HDS() { clear(); }
    HDS( const Self& hds)
#endif // CGAL_CFG_NO_TMPL_IN_TMPL_PARAM //
    :  vertices( hds.vertices),
       //halfedges( hds.halfedges),
       faces( hds.faces),
       nb_border_halfedges( hds.nb_border_halfedges),
       nb_border_edges( hds.nb_border_edges),
       border_halfedges( hds.border_halfedges)
    {
        // goal is halfedges = hds.halfedges, but we have pairs here
        Halfedge_const_iterator i = hds.halfedges_begin();
        for ( ; i != hds.halfedges_end(); ++ ++ i) {
            edges_push_back( *i);
        }
        pointer_update( hds);
    }

    Self& operator=( const Self& hds)  {
        if ( this != &hds) {
            clear();
            vertices            = hds.vertices;
            // goal is halfedges = hds.halfedges, but we have pairs here
            halfedges = Halfedge_list();
            Halfedge_const_iterator i = hds.halfedges_begin();
            for ( ; i != hds.halfedges_end(); ++ ++ i) {
                edges_push_back( *i);
            }
            faces               = hds.faces;
            nb_border_halfedges = hds.nb_border_halfedges;
            nb_border_edges     = hds.nb_border_edges;
            border_halfedges    = hds.border_halfedges;
            pointer_update( hds);
        }
        return *this;
    }

    void reserve( size_type, size_type, size_type) {}
        // Parameter order is v,h,f.
        // reserve storage for v vertices, h halfedges, and f faces. The
        // reservation sizes are a hint for optimizing storage allocation.
        // If the `capacity' is already greater than the requested size
        // nothing happens. If the `capacity' changes all iterators and
        // circulators invalidates. The function is void here.

// Access Member Functions

    allocator_type  get_allocator() const { return allocator_type(); }

    size_type size_of_vertices() const  { return vertices.size();}
    size_type size_of_halfedges() const { return halfedges.size();}
        // number of all halfedges (including border halfedges).
    size_type size_of_faces() const     { return faces.size();}

    size_type capacity_of_vertices() const    { return vertices.max_size();}
    size_type capacity_of_halfedges() const   { return halfedges.max_size();}
    size_type capacity_of_faces() const       { return faces.max_size();}

    std::size_t bytes() const {
        return sizeof(Self)
               + vertices.size()  * sizeof( Vertex)
               + halfedges.size() * sizeof( Halfedge)
               + faces.size()     * sizeof( Face);
    }
    std::size_t bytes_reserved() const { return bytes();}

    Vertex_iterator   vertices_begin()   { return vertices.begin();}
    Vertex_iterator   vertices_end()     { return vertices.end();}
    Halfedge_iterator halfedges_begin()  { return halfedges.begin();}
    Halfedge_iterator halfedges_end()    { return halfedges.end();}
    Face_iterator     faces_begin()      { return faces.begin();}
    Face_iterator     faces_end()        { return faces.end();}

    // The constant iterators and circulators.

    Vertex_const_iterator   vertices_begin()  const{ return vertices.begin();}
    Vertex_const_iterator   vertices_end()    const{ return vertices.end();}
    Halfedge_const_iterator halfedges_begin() const{ return halfedges.begin();}
    Halfedge_const_iterator halfedges_end()   const{ return halfedges.end();}
    Face_const_iterator     faces_begin()     const{ return faces.begin();}
    Face_const_iterator     faces_end()       const{ return faces.end();}

// Insertion
//
// The following operations simply allocate a new element of that type.
// Halfedges are always allocated in pairs of opposite halfedges. The
// opposite pointers are automatically set.

    Vertex_handle vertices_push_back( const Vertex& v) {
        vertices.push_back( * get_vertex_node(v));
        Vertex_handle vh = vertices.end();
        return --vh;
    }

    Halfedge_handle edges_push_back( const Halfedge& h, const Halfedge& g) {
        // creates a new pair of opposite border halfedges.
        Halfedge* ptr = get_edge_node( h, g);
        halfedges.push_back( *ptr);
        Halfedge_handle hh = halfedges.end();
        --hh;
        halfedges.push_back( *(ptr->opposite()));
        return hh;
    }

    Halfedge_handle edges_push_back( const Halfedge& h) {
        CGAL_precondition( h.opposite() != Halfedge_const_handle());
        return edges_push_back( h, *(h.opposite()));
    }

    Face_handle faces_push_back( const Face& f) {
        faces.push_back( * get_face_node(f));
        Face_handle fh = faces.end();
        return --fh;
    }


// Removal
//
// The following operations erase an element referenced by a handle.
// Halfedges are always deallocated in pairs of opposite halfedges. Erase
// of single elements is optional. The deletion of all is mandatory.

    void vertices_pop_front() {
        Vertex* v = &(vertices.front());
        vertices.pop_front();
        put_vertex_node( v);
    }
    void vertices_pop_back() {
        Vertex* v = &(vertices.back());
        vertices.pop_back();
        put_vertex_node( v);
    }
    void vertices_erase( Vertex_handle v) {
        Vertex* ptr = &*v;
        vertices.erase(v);
        put_vertex_node( ptr);
    }
    void vertices_erase( Vertex_iterator first, Vertex_iterator last) {
        while (first != last)
            vertices_erase(first++);
    }

    void edges_erase( Halfedge_handle h) {
        // deletes the pair of opposite halfedges h and h->opposite().
        Halfedge_handle g = h->opposite();
        halfedges.erase(h);
        halfedges.erase(g);
        put_edge_node(&*h);
    }
    void edges_pop_front() { edges_erase( halfedges.begin()); }
    void edges_pop_back()  {
        Halfedge_iterator h = halfedges.end();
        edges_erase( --h);
    }
    void edges_erase( Halfedge_iterator first, Halfedge_iterator last) {
        while (first != last) {
            Halfedge_iterator nxt = first;
            ++nxt;
            CGAL_assertion( nxt != last);
            ++nxt;
            edges_erase(first);
            first = nxt;
        }
    }

    void faces_pop_front() {
        Face* f = &(faces.front());
        faces.pop_front();
        put_face_node( f);
    }
    void faces_pop_back() {
        Face* f = &(faces.back());
        faces.pop_back();
        put_face_node( f);
    }
    void faces_erase( Face_handle f) {
        Face* ptr = &*f;
        faces.erase(f);
        put_face_node( ptr);
    }
    void faces_erase( Face_iterator first, Face_iterator last) {
        while (first != last)
            faces_erase(first++);
    }

    void vertices_clear() { vertices.destroy(); }
    void edges_clear() {
        edges_erase( halfedges.begin(), halfedges.end());
        nb_border_halfedges = 0;
        nb_border_edges = 0;
        border_halfedges = Halfedge_handle();
    }
    void faces_clear() { faces.destroy(); }
    void clear() {
        vertices_clear();
        edges_clear();
        faces_clear();
    }

    void vertices_splice( Vertex_iterator target, Self &source,
                          Vertex_iterator begin, Vertex_iterator end) {
        vertices.splice( target, source.vertices, begin, end);
    }

    void halfedges_splice( Halfedge_iterator target, Self &source,
                           Halfedge_iterator begin, Halfedge_iterator end) {
        halfedges.splice( target, source.halfedges, begin, end);
    }

    void faces_splice( Face_iterator target, Self &source,
                       Face_iterator begin, Face_iterator end) {
        faces.splice( target, source.faces, begin, end);
    }

// Operations with Border Halfedges

    size_type size_of_border_halfedges() const { return nb_border_halfedges;}
        // number of border halfedges. An edge with no incident face
        // counts as two border halfedges. Precondition: `normalize_border()'
        // has been called and no halfedge insertion or removal and no
        // change in border status of the halfedges have occured since
        // then.

    size_type size_of_border_edges() const { return nb_border_edges;}
        // number of border edges. If `size_of_border_edges() ==
        // size_of_border_halfedges()' all border edges are incident to a
        // face on one side and to a hole on the other side.
        // Precondition: `normalize_border()' has been called and no
        // halfedge insertion or removal and no change in border status of
        // the halfedges have occured since then.

    Halfedge_iterator border_halfedges_begin() {
        // halfedge iterator starting with the border edges. The range [
        // `halfedges_begin(), border_halfedges_begin()') denotes all
        // non-border edges. The range [`border_halfedges_begin(),
        // halfedges_end()') denotes all border edges. Precondition:
        // `normalize_border()' has been called and no halfedge insertion
        // or removal and no change in border status of the halfedges have
        // occured since then.
        return border_halfedges;
    }

    Halfedge_const_iterator border_halfedges_begin() const {
        return border_halfedges;
    }

    void normalize_border() {
        // sorts halfedges such that the non-border edges precedes the
        // border edges. For each border edge that is incident to a face
        // the halfedge iterator will reference the halfedge incident to
        // the face right before the halfedge incident to the hole.
        CGAL_assertion_code( size_type count = halfedges.size();)
        nb_border_halfedges = 0;
        nb_border_edges = 0;
        Halfedge_list  border;
        Halfedge_iterator i = halfedges_begin();
        while ( i != halfedges_end()) {
            Halfedge_iterator j = i;
            ++i;
            ++i;
            Halfedge_iterator k = j;
            ++k;
            if ( j->is_border()) {
                nb_border_halfedges++;
                nb_border_edges++;
                if (k->is_border())
                    nb_border_halfedges++;
                border.splice( border.end(), halfedges, k);
                border.splice( border.end(), halfedges, j);
            } else if ( k->is_border()) {
                nb_border_halfedges++;
                nb_border_edges++;
                border.splice( border.end(), halfedges, j);
                border.splice( border.end(), halfedges, k);
            } else {
                CGAL_assertion_code( count -= 2;)
            }
        }
        CGAL_assertion( count == 2 * nb_border_edges );
        CGAL_assertion( count == border.size());
        if ( i == halfedges_begin()) {
            halfedges.splice( halfedges.end(), border);
            i = halfedges_begin();
        } else {
            --i;
            --i;
            CGAL_assertion( ! i->is_border() && ! i->opposite()->is_border());
            halfedges.splice( halfedges.end(), border);
            ++i;
            ++i;
        }
        CGAL_assertion( i == halfedges_end() || i->opposite()->is_border());
        border_halfedges = i;
    }
};
#ifdef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
};
#endif


//  #ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
//  #define CGAL__HDS_IP_List HalfedgeDS_list
//  #else
//  #define CGAL__HDS_IP_List HalfedgeDS_list::HDS
//  #endif

// init static member allocator objects (no longer static)
//template < class Traits_, class HalfedgeDSItems, class Alloc>
//typename CGAL__HDS_IP_List<Traits_, HalfedgeDSItems, Alloc>::Vertex_allocator
//CGAL__HDS_IP_List<Traits_, HalfedgeDSItems, Alloc>::vertex_allocator;
//
//template < class Traits_, class HalfedgeDSItems, class Alloc>
//typename CGAL__HDS_IP_List<Traits_, HalfedgeDSItems, Alloc>::Edge_allocator
//CGAL__HDS_IP_List<Traits_, HalfedgeDSItems, Alloc>::edge_allocator;
//
//template < class Traits_, class HalfedgeDSItems, class Alloc>
//typename CGAL__HDS_IP_List<Traits_, HalfedgeDSItems, Alloc>::Face_allocator
//CGAL__HDS_IP_List<Traits_, HalfedgeDSItems, Alloc>::face_allocator;


//  #undef CGAL__HDS_IP_List

CGAL_END_NAMESPACE
#endif // CGAL_HALFEDGEDS_LIST_H //
// EOF //