This file is indexed.

/usr/include/CGAL/HalfedgeDS_vector.h is in libcgal-dev 4.7-4.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
// Copyright (c) 1997  
// 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); 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; either version 3 of the License,
// or (at your option) any later version.
//
// 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$
// $Id$
// 
//
// Author(s)     : Lutz Kettner  <kettner@mpi-sb.mpg.de>

#ifndef CGAL_HALFEDGEDS_VECTOR_H
#define CGAL_HALFEDGEDS_VECTOR_H 1

// Define this if HalfedgeDS_vector is based on CGAL internal vector.
#define CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR 1

#include <CGAL/basic.h>
#include <CGAL/memory.h>
#include <CGAL/HalfedgeDS_items_decorator.h>
#include <algorithm>
#include <vector>
#include <map>
#include <cstddef>

#ifdef CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR
#include <CGAL/vector.h>
#else
#include <CGAL/HalfedgeDS_iterator_adaptor.h>
#endif

namespace CGAL {


template < class Traits_, class HalfedgeDSItems, class Alloc>
class HalfedgeDS_vector_types {
public:
    typedef HalfedgeDS_vector_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;
    typedef typename Halfedge_wrapper::Halfedge        Halfedge;
    typedef typename Face_wrapper::Face                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;

#ifdef CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR
    typedef internal::vector<Vertex, Vertex_allocator>    Vertex_vector;
    typedef typename Vertex_vector::iterator           Vertex_I;
    typedef typename Vertex_vector::const_iterator     Vertex_CI;
    typedef typename Vertex_vector::iterator           Vertex_iterator;
    typedef typename Vertex_vector::const_iterator     Vertex_const_iterator;

    typedef internal::vector<Halfedge, Halfedge_allocator>  Halfedge_vector;
    typedef typename Halfedge_vector::iterator         Halfedge_I;
    typedef typename Halfedge_vector::const_iterator   Halfedge_CI;
    typedef typename Halfedge_vector::iterator         Halfedge_iterator;
    typedef typename Halfedge_vector::const_iterator   Halfedge_const_iterator;

    typedef internal::vector<Face, Face_allocator>        Face_vector;
    typedef typename Face_vector::iterator             Face_I;
    typedef typename Face_vector::const_iterator       Face_CI;
    typedef typename Face_vector::iterator             Face_iterator;
    typedef typename Face_vector::const_iterator       Face_const_iterator;
#else // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR //
    typedef std::vector<Vertex, Vertex_allocator>      Vertex_vector;
    typedef typename Vertex_vector::iterator           Vertex_I;
    typedef typename Vertex_vector::const_iterator     Vertex_CI;
    typedef HalfedgeDS_iterator_adaptor<Vertex_I>      Vertex_iterator;
    typedef HalfedgeDS_iterator_adaptor<Vertex_CI>     Vertex_const_iterator;

    typedef std::vector<Halfedge, Halfedge_allocator>  Halfedge_vector;
    typedef typename Halfedge_vector::iterator         Halfedge_I;
    typedef typename Halfedge_vector::const_iterator   Halfedge_CI;
    typedef HalfedgeDS_iterator_adaptor<Halfedge_I>    Halfedge_iterator;
    typedef HalfedgeDS_iterator_adaptor<Halfedge_CI>   Halfedge_const_iterator;

    typedef std::vector<Face, Face_allocator>          Face_vector;
    typedef typename Face_vector::iterator             Face_I;
    typedef typename Face_vector::const_iterator       Face_CI;
    typedef HalfedgeDS_iterator_adaptor<Face_I>        Face_iterator;
    typedef HalfedgeDS_iterator_adaptor<Face_CI>       Face_const_iterator;
#endif // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR //

    typedef Vertex_iterator                            Vertex_handle;
    typedef Vertex_const_iterator                      Vertex_const_handle;
    typedef Halfedge_iterator                          Halfedge_handle;
    typedef Halfedge_const_iterator                    Halfedge_const_handle;
    typedef Face_iterator                              Face_handle;
    typedef Face_const_iterator                        Face_const_handle;

    typedef typename Halfedge_vector::size_type        size_type;
    typedef typename Halfedge_vector::difference_type  difference_type;
    typedef std::random_access_iterator_tag            iterator_category;

    static inline Vertex_handle vertex_handle( Vertex* v) {
        return Vertex_handle( Vertex_I(v));
    }
    static inline Vertex_const_handle vertex_handle( const Vertex* v) {
        return Vertex_const_handle( Vertex_CI(v));
    }
    static inline Halfedge_handle halfedge_handle( Halfedge* h) {
        return Halfedge_handle( Halfedge_I(h));
    }
    static inline Halfedge_const_handle halfedge_handle( const Halfedge* h) {
        return Halfedge_const_handle( Halfedge_CI(h));
    }
    static inline Face_handle face_handle( Face* f) {
        return Face_handle( Face_I(f));
    }
    static inline Face_const_handle face_handle( const Face* f) {
        return Face_const_handle( Face_CI(f));
    }
};


template < class Traits_, class HalfedgeDSItems, 
           class Alloc = CGAL_ALLOCATOR(int)>
class HalfedgeDS_vector
    : public HalfedgeDS_vector_types<Traits_, HalfedgeDSItems, Alloc> {
public:
    typedef HalfedgeDS_vector<Traits_,HalfedgeDSItems,Alloc> Self;
    typedef HalfedgeDS_vector_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_vector              Vertex_vector;
    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::Vertex_I                   Vertex_I;
    typedef typename Types::Vertex_CI                  Vertex_CI;

    typedef typename Types::Halfedge_vector            Halfedge_vector;
    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::Halfedge_I                 Halfedge_I;
    typedef typename Types::Halfedge_CI                Halfedge_CI;

    typedef typename Types::Face_vector                Face_vector;
    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::Face_I                     Face_I;
    typedef typename Types::Face_CI                    Face_CI;

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

    typedef Tag_false                                  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;

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

    Vertex_vector      vertices;
    Halfedge_vector    halfedges;
    Face_vector        faces;

    size_type          nb_border_halfedges;
    size_type          nb_border_edges;
    Halfedge_iterator  border_halfedges;

#ifdef CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR
    Vertex_I    get_v_iter( const Vertex_I&  i)   const { return i; }
    Vertex_CI   get_v_iter( const Vertex_CI& i)   const { return i; }
    Halfedge_I  get_h_iter( const Halfedge_I&  i) const { return i; }
    Halfedge_CI get_h_iter( const Halfedge_CI& i) const { return i; }
    Face_I      get_f_iter( const Face_I&  i)     const { return i; }
    Face_CI     get_f_iter( const Face_CI& i)     const { return i; }
#else // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR //
    Vertex_I    get_v_iter( const Vertex_iterator&  i) const {
        return i.iterator();
    }
    Vertex_CI   get_v_iter( const Vertex_const_iterator& i)   const {
        return i.iterator();
    }
    Halfedge_I  get_h_iter( const Halfedge_iterator&  i) const {
        return i.iterator();
    }
    Halfedge_CI get_h_iter( const Halfedge_const_iterator& i) const {
        return i.iterator();
    }
    Face_I      get_f_iter( const Face_iterator&  i)     const {
        return i.iterator();
    }
    Face_CI     get_f_iter( const Face_const_iterator& i)     const {
        return i.iterator();
    }
#endif // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR //

// CREATION

private:
#define CGAL__V_UPDATE(v) (((v) == Vertex_handle()) ? (v) : \
                           (v_new + ( Vertex_CI   (get_v_iter(v)) - v_old)))
#define CGAL__H_UPDATE(h) (((h) == Halfedge_handle()) ? (h) : \
                           (h_new + ( Halfedge_CI (get_h_iter(h)) - h_old)))
#define CGAL__F_UPDATE(f) (((f) == Face_handle()) ? (f) : \
                           (f_new + ( Face_CI     (get_f_iter(f)) - f_old)))

    void pointer_update( Vertex_CI v_old, Halfedge_CI h_old, Face_CI f_old) {
        // Update own pointers assuming that they lived previously
        // in a halfedge data structure with vector starting addresses
        // as given as parameters v_old, h_old, f_old.
        HalfedgeDS_items_decorator<Self> D;
        Vertex_iterator   v_new = vertices.begin();
        Halfedge_iterator h_new = halfedges.begin();
        Face_iterator     f_new = faces.begin();
        for (Halfedge_iterator h = halfedges_begin();h != halfedges_end();++h){
            h->HBase::set_next( CGAL__H_UPDATE( h->next()));
            h->HBase_base::set_opposite( CGAL__H_UPDATE( h->opposite()));
            D.set_prev(   h, CGAL__H_UPDATE( D.get_prev(h)));
            D.set_vertex( h, CGAL__V_UPDATE( D.get_vertex(h)));
            D.set_face(   h, CGAL__F_UPDATE( D.get_face(h)));
        }
        border_halfedges = CGAL__H_UPDATE( border_halfedges);
        if (check_tag( Supports_vertex_halfedge())) {
            for (Vertex_iterator v = vertices_begin();v != vertices_end();++v){
                D.set_vertex_halfedge(v, CGAL__H_UPDATE(
                    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,CGAL__H_UPDATE( D.get_face_halfedge(f)));
            }
        }
    }
#undef CGAL__V_UPDATE
#undef CGAL__H_UPDATE
#undef CGAL__F_UPDATE

public:

    HalfedgeDS_vector()
        : nb_border_halfedges(0), nb_border_edges(0) {}
        // empty halfedge data structure.

    HalfedgeDS_vector( size_type v, size_type h, size_type f)
        : nb_border_halfedges(0), nb_border_edges(0) {
        // halfedge data structure 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.
        vertices.reserve(v);
        halfedges.reserve(h);
        faces.reserve(f);
    }

    HalfedgeDS_vector( const Self& hds)
    :  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)
    {
        pointer_update( hds.vertices.begin(),
                        hds.halfedges.begin(),
                        hds.faces.begin());
    }

    Self& operator=( const Self& hds)  {
        if ( this != &hds) {
            clear();
            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;
            pointer_update( hds.vertices.begin(),
                            hds.halfedges.begin(),
                            hds.faces.begin());
        }
        return *this;
    }

    void reserve( size_type v, size_type h, size_type 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. Function is void here.
        if ( (check_tag( Supports_halfedge_vertex())
                && v > capacity_of_vertices())
             || h > capacity_of_halfedges()
             || (check_tag( Supports_halfedge_face())
                && f > capacity_of_faces())) {
            Vertex_CI   v_old = vertices.begin();
            Halfedge_CI h_old = halfedges.begin();
            Face_CI     f_old = faces.begin();
            if ( check_tag( Supports_halfedge_vertex()))
                vertices.reserve(v);
            halfedges.reserve(h);
            if ( check_tag( Supports_halfedge_face()))
                faces.reserve(f);
            pointer_update( v_old, h_old, f_old);
        }
    }

// 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.capacity();}
    size_type capacity_of_halfedges() const   { return halfedges.capacity();}
    size_type capacity_of_faces() const       { return faces.capacity();}

    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 sizeof(Self)
               + vertices.capacity()  * sizeof( Vertex)
               + halfedges.capacity() * sizeof( Halfedge)
               + faces.capacity()     * sizeof( Face);
    }

    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) {
        CGAL_precondition( 1+size_of_vertices() <= capacity_of_vertices());
        vertices.push_back(v);
        Vertex_handle vv = vertices.end();
        return --vv;
    }

    Halfedge_handle edges_push_back( const Halfedge& h, const Halfedge& g) {
        // creates a new pair of opposite border halfedges.
        CGAL_precondition( 1 + size_of_halfedges() < capacity_of_halfedges());
        halfedges.push_back(h);
        Halfedge_handle hh = halfedges.end();
        --hh;
        halfedges.push_back(g);
        Halfedge_handle gg = halfedges.end();
        --gg;
        CGAL_assertion( hh + 1 == gg);
        CGAL_assertion( (char*)(&*gg) - (char*)(&*hh) == sizeof( Halfedge));
        hh->HBase_base::set_opposite(gg);
        gg->HBase_base::set_opposite(hh);
        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) {
        CGAL_precondition( 1+size_of_faces() <= capacity_of_faces());
        faces.push_back(f);
        Face_handle ff = faces.end();
        return --ff;
    }


// 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_back() { vertices.pop_back(); }
    void edges_pop_back()    {
        CGAL_precondition(( halfedges_end()-1)->opposite() ==
                          ( halfedges_end()-2));
        halfedges.pop_back();
        halfedges.pop_back();
    }
    void faces_pop_back()    { faces.pop_back(); }

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

// Special Operations on Polyhedral Surfaces
protected:
    // Update operation used in pointer_update(...).
    void update_opposite( Halfedge_I h) {
        Halfedge_I g = h + 1;
        h->HBase_base::set_opposite(g);
        g->HBase_base::set_opposite(h);
    }

// Operations with Border Halfedges
public:
    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.
        nb_border_halfedges = 0;
        nb_border_edges = 0;
        border_halfedges = halfedges_end();
        // Lets run one partition step over the array of halfedges.
        // First find a pivot -- that means a border edge.
        Halfedge_I ll = halfedges.begin();
        while ( ll != halfedges.end() && (! ll->is_border()) &&
                (! ll->opposite()->is_border() ))
            ++ ++ll;
        if ( ll == halfedges.end()) // Done. No border edges found.
            return;

        // An array of pointers to update the changed halfedge pointers.
        typedef typename Allocator::template rebind< Halfedge_I>
                                                      HI_alloc_rebind;
        typedef typename HI_alloc_rebind::other       HI_allocator;

        typedef std::vector<Halfedge_I, HI_allocator> HVector;
        typedef typename HVector::iterator Hiterator;
        HVector hvector;
        // Initialize it.
        hvector.reserve( halfedges.size());
        for ( Halfedge_I i = halfedges.begin(); i != halfedges.end(); ++i) {
            hvector.push_back(i);
        }
        Hiterator llhv = hvector.begin() + (ll-halfedges.begin());
        // Start with the partitioning.
        Halfedge_I rr = halfedges.end();
        -- --rr;
        Hiterator rrhv = hvector.end();
        -- --rrhv;
        // The comments proove the invariant of the partitioning step.
        // Note that + 1 or - 1 denotes plus one edge or minus one edge,
        // so they mean actually + 2 and - 2.
                              // Pivot is in *ll
                              // Elements in [rr+1..end) >= pivot (border)
                              // Elements in [begin..ll) <  pivot (non border)
        while (ll < rr) {
                              // Pivot is in *ll, ll <= rr.
            while ( rr > ll && (rr->is_border() 
                              || rr->opposite()->is_border())) {
                if ( ! rr->opposite()->is_border()) {
                    CGAL_assertion( rr + 1 == get_h_iter(rr->opposite()));
                    std::swap( *rr, *(rr+1));
                    update_opposite( rr);
                    std::swap( *rrhv, *(rrhv+1));
                }
                -- --rr;
                -- --rrhv;
            }
                              // Elements in [rr+1..end) >= pivot (border)
                              // *rr <= pivot, ll <= rr.
            CGAL_assertion( rr + 1 == get_h_iter( rr->opposite()));
            CGAL_assertion( ll + 1 == get_h_iter( ll->opposite()));
            std::swap( *(ll+1), *(rr+1));
            std::swap( *ll, *rr);
            update_opposite( ll);
            update_opposite( rr);
            std::swap( *(llhv+1), *(rrhv+1));
            std::swap( *llhv, *rrhv);
                              // Elements in [begin..ll) < pivot
                              // Pivot is in *rr, ll <= rr.
            while ( !ll->is_border() && ! ll->opposite()->is_border()) {
                ++ ++ll;
                ++ ++llhv;
            }
                              // Elements in [begin..ll) < pivot
                              // *ll >= pivot
                              // ll <= rr (since *rr is pivot.)
            CGAL_assertion( ll <= rr);
            CGAL_assertion( llhv <= rrhv);
            CGAL_assertion( rr + 1 == get_h_iter( rr->opposite()));
            CGAL_assertion( ll + 1 == get_h_iter( ll->opposite()));
            std::swap( *(ll+1), *(rr+1));
            std::swap( *ll, *rr);
            update_opposite( ll);
            update_opposite( rr);
            std::swap( *(llhv+1), *(rrhv+1));
            std::swap( *llhv, *rrhv);
            if ( ! rr->opposite()->is_border()) {
                CGAL_assertion( rr + 1 == get_h_iter( rr->opposite()));
                std::swap( *rr, *(rr+1));
                update_opposite( rr);
                std::swap( *rrhv, *(rrhv+1));
            }

            // This guard is needed here because, rr==ll==begin, might be true
            // at this point, causing the decrement to result in undefined
            // behaviour.
            // [Fernando Cacciola]
            if ( ll < rr )
            {
              -- --rr;
              -- --rrhv;
            }
                              // Elements in [rr+1..end) >= pivot
                              // Pivot is in *ll
        }
        CGAL_assertion( llhv >= rrhv);
                              // rr + 1 >= ll >= rr
                              // Elements in [rr+1..end) >= pivot
                              // Elemente in [begin..ll) <  pivot
                              // Pivot is in a[ll]
        if ( ll == rr) {
            // Check for the possibly missed swap.
            if ( rr->is_border() && ! rr->opposite()->is_border()) {
                CGAL_assertion( rr + 1 == get_h_iter (rr->opposite()));
                std::swap( *rr, *(rr+1));
                update_opposite( rr);
                std::swap( *rrhv, *(rrhv+1));
            }
        }
        CGAL_assertion( ll->opposite()->is_border());
        CGAL_assertion( ll == halfedges.begin() || ! (ll-2)->is_border());
        CGAL_assertion( ll == halfedges.begin() || ! (ll-1)->is_border());
        border_halfedges = ll;
        nb_border_edges = (halfedges.end() - ll) / 2;
        nb_border_halfedges = 0;

        HVector inv_vector( halfedges.size());
        // Initialize inverse index.
        for ( Hiterator k = hvector.begin(); k != hvector.end(); ++k){
            inv_vector[*k - halfedges.begin()] =
                halfedges.begin() + (k - hvector.begin());
        }
        // Update halfedge pointers.
        HalfedgeDS_items_decorator<Self> D;
        for (Halfedge_iterator h = halfedges_begin();h != halfedges_end();++h){
            h->HBase::set_next( inv_vector[ h->next() - halfedges_begin()]);
            D.set_vertex_halfedge(h);
            if ( D.get_prev( h) == Halfedge_iterator())
                D.set_prev( h, Halfedge_iterator());
            else
                D.set_prev( h, inv_vector[ D.get_prev(h) - halfedges_begin()]);
            if ( h->is_border())
                nb_border_halfedges++;
            else
                D.set_face_halfedge(h);
        }
    }
};


} //namespace CGAL
#endif // CGAL_HALFEDGEDS_VECTOR_H //
// EOF //