source: NonGTP/Boost/boost/numeric/ublas/storage.hpp @ 857

Revision 857, 58.7 KB checked in by igarcia, 19 years ago (diff)
Line 
1//
2//  Copyright (c) 2000-2002
3//  Joerg Walter, Mathias Koch
4//
5//  Permission to use, copy, modify, distribute and sell this software
6//  and its documentation for any purpose is hereby granted without fee,
7//  provided that the above copyright notice appear in all copies and
8//  that both that copyright notice and this permission notice appear
9//  in supporting documentation.  The authors make no representations
10//  about the suitability of this software for any purpose.
11//  It is provided "as is" without express or implied warranty.
12//
13//  The authors gratefully acknowledge the support of
14//  GeNeSys mbH & Co. KG in producing this work.
15//
16
17#ifndef BOOST_UBLAS_STORAGE_H
18#define BOOST_UBLAS_STORAGE_H
19
20#include <algorithm>
21#ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
22#include <boost/shared_array.hpp>
23#endif
24
25#include <boost/numeric/ublas/exception.hpp>
26#include <boost/numeric/ublas/detail/iterator.hpp>
27
28
29namespace boost { namespace numeric { namespace ublas {
30
31
32    // Base class for Storage Arrays - see the Barton Nackman trick
33    template<class E>
34    class storage_array:
35        private nonassignable {
36    };
37
38
39    // Unbounded array - with allocator
40    template<class T, class ALLOC>
41    class unbounded_array:
42        public storage_array<unbounded_array<T, ALLOC> > {
43
44        typedef unbounded_array<T, ALLOC> self_type;
45    public:
46        typedef ALLOC allocator_type;
47        typedef typename ALLOC::size_type size_type;
48        typedef typename ALLOC::difference_type difference_type;
49        typedef T value_type;
50        typedef const T &const_reference;
51        typedef T &reference;
52        typedef const T *const_pointer;
53        typedef T *pointer;
54        typedef const_pointer const_iterator;
55        typedef pointer iterator;
56
57        // Construction and destruction
58        explicit BOOST_UBLAS_INLINE
59        unbounded_array (const ALLOC &a = ALLOC()):
60            alloc_ (a), size_ (0), data_ (0) {
61        }
62        explicit BOOST_UBLAS_INLINE
63        unbounded_array (size_type size, const ALLOC &a = ALLOC()):
64            alloc_(a), size_ (size) {
65            if (size_) {
66                data_ = alloc_.allocate (size_);
67                // ISSUE some compilers may zero POD here
68#ifdef BOOST_UBLAS_USEFUL_ARRAY_PLACEMENT_NEW
69                // array form fails on some compilers due to size cookie, is it standard conforming?
70                new (data_) value_type[size_];
71#else
72                for (pointer d = data_; d != data_ + size_; ++d)
73                    new (d) value_type;
74#endif
75            }
76        }
77        // No value initialised, but still be default constructed
78        BOOST_UBLAS_INLINE
79        unbounded_array (size_type size, const value_type &init, const ALLOC &a = ALLOC()):
80            alloc_ (a), size_ (size) {
81            if (size_) {
82                data_ = alloc_.allocate (size_);
83                std::uninitialized_fill (begin(), end(), init);
84            }
85        }
86        BOOST_UBLAS_INLINE
87        unbounded_array (const unbounded_array &c):
88            storage_array<self_type> (),
89            alloc_ (c.alloc_), size_ (c.size_) {
90            if (size_) {
91                data_ = alloc_.allocate (size_);
92                std::uninitialized_copy (c.begin(), c.end(), begin());
93            }
94            else
95                data_ = 0;
96        }
97        BOOST_UBLAS_INLINE
98        ~unbounded_array () {
99            if (size_) {
100                const iterator i_end = end();
101                for (iterator i = begin (); i != i_end; ++i) {
102                    iterator_destroy (i);
103                }
104                alloc_.deallocate (data_, size_);
105            }
106        }
107
108        // Resizing
109    private:
110        BOOST_UBLAS_INLINE
111        void resize_internal (size_type size, value_type init, bool preserve) {
112            if (size != size_) {
113                pointer data;
114                if  (size) {
115                    data = alloc_.allocate (size);
116                    if (preserve) {
117                        const_iterator si = begin ();
118                        pointer di = data;
119                        if (size < size_) {
120                            for (; di != data + size; ++di) {
121                                alloc_.construct (di, *si);
122                                ++si;
123                            }
124                        }
125                        else {
126                            for (const_iterator si_end = end (); si != si_end; ++si) {
127                                alloc_.construct (di, *si);
128                                ++di;
129                            }
130                            for (; di != data + size; ++di) {
131                                alloc_.construct (di, init);
132                            }
133                        }
134                    }
135                    else {
136                        // ISSUE some compilers may zero POD here
137#ifdef BOOST_UBLAS_USEFUL_ARRAY_PLACEMENT_NEW
138                        // array form fails on some compilers due to size cookie, is it standard conforming?
139                        new (data) value_type[size];
140#else
141                        for (pointer d = data; d != data + size; ++d)
142                            new (d) value_type;
143#endif
144                    }                   
145                }
146                else
147                    data = 0;
148                if (size_) {
149                    const iterator i_end = end();
150                    for (iterator i = begin(); i != i_end; ++i) {
151                        iterator_destroy (i);
152                    }
153                    alloc_.deallocate (data_, size_);
154                }
155                size_ = size;
156                data_ = data;
157            }
158        }
159    public:
160        BOOST_UBLAS_INLINE
161        void resize (size_type size) {
162            resize_internal (size, value_type (), false);
163        }
164        BOOST_UBLAS_INLINE
165        void resize (size_type size, value_type init) {
166            resize_internal (size, init, true);
167        }
168                   
169        BOOST_UBLAS_INLINE
170        size_type size () const {
171            return size_;
172        }
173
174        // Element access
175        BOOST_UBLAS_INLINE
176        const_reference operator [] (size_type i) const {
177            BOOST_UBLAS_CHECK (i < size_, bad_index ());
178            return data_ [i];
179        }
180        BOOST_UBLAS_INLINE
181        reference operator [] (size_type i) {
182            BOOST_UBLAS_CHECK (i < size_, bad_index ());
183            return data_ [i];
184        }
185
186        // Assignment
187        BOOST_UBLAS_INLINE
188        unbounded_array &operator = (const unbounded_array &a) {
189            if (this != &a) {
190                resize (a.size_);
191                std::copy (a.data_, a.data_ + a.size_, data_);
192            }
193            return *this;
194        }
195        BOOST_UBLAS_INLINE
196        unbounded_array &assign_temporary (unbounded_array &a) {
197            swap (a);
198            return *this;
199        }
200
201        // Swapping
202        BOOST_UBLAS_INLINE
203        void swap (unbounded_array &a) {
204            if (this != &a) {
205                std::swap (size_, a.size_);
206                std::swap (data_, a.data_);
207            }
208        }
209        BOOST_UBLAS_INLINE
210        friend void swap (unbounded_array &a1, unbounded_array &a2) {
211            a1.swap (a2);
212        }
213
214        BOOST_UBLAS_INLINE
215        const_iterator begin () const {
216            return data_;
217        }
218        BOOST_UBLAS_INLINE
219        const_iterator end () const {
220            return data_ + size_;
221        }
222
223        BOOST_UBLAS_INLINE
224        iterator begin () {
225            return data_;
226        }
227        BOOST_UBLAS_INLINE
228        iterator end () {
229            return data_ + size_;
230        }
231
232        // Reverse iterators
233        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
234        typedef std::reverse_iterator<iterator> reverse_iterator;
235
236        BOOST_UBLAS_INLINE
237        const_reverse_iterator rbegin () const {
238            return const_reverse_iterator (end ());
239        }
240        BOOST_UBLAS_INLINE
241        const_reverse_iterator rend () const {
242            return const_reverse_iterator (begin ());
243        }
244        BOOST_UBLAS_INLINE
245        reverse_iterator rbegin () {
246            return reverse_iterator (end ());
247        }
248        BOOST_UBLAS_INLINE
249        reverse_iterator rend () {
250            return reverse_iterator (begin ());
251        }
252
253        // Allocator
254        allocator_type get_allocator () {
255            return alloc_;
256        }
257
258    private:
259        // Handle explict destroy on a (possibly indexed) iterator
260        BOOST_UBLAS_INLINE
261        static void iterator_destroy (iterator &i) {
262            (&(*i)) -> ~value_type ();
263        }
264        ALLOC alloc_;
265        size_type size_;
266        pointer data_;
267    };
268
269    // Bounded array - with allocator for size_type and difference_type
270    template<class T, std::size_t N, class ALLOC>
271    class bounded_array:
272        public storage_array<bounded_array<T, N, ALLOC> > {
273
274        typedef bounded_array<T, N, ALLOC> self_type;
275    public:
276        // No allocator_type as ALLOC is not used for allocation
277        typedef typename ALLOC::size_type size_type;
278        typedef typename ALLOC::difference_type difference_type;
279        typedef T value_type;
280        typedef const T &const_reference;
281        typedef T &reference;
282        typedef const T *const_pointer;
283        typedef T *pointer;
284        typedef const_pointer const_iterator;
285        typedef pointer iterator;
286
287        // Construction and destruction
288        BOOST_UBLAS_INLINE
289        bounded_array ():
290            size_ (0), data_ () {   // size 0 - use bounded_vector to default construct with size N
291        }
292        explicit BOOST_UBLAS_INLINE
293        bounded_array (size_type size):
294            size_ (size) /*, data_ ()*/ {
295            BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
296            // data_ (an array) elements are already default constructed
297        }
298        BOOST_UBLAS_INLINE
299        bounded_array (size_type size, const value_type &init):
300            size_ (size) /*, data_ ()*/ {
301            BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
302            // ISSUE elements should be value constructed here, but we must fill instead as already default constructed
303            std::fill (begin(), end(), init) ;
304        }
305        BOOST_UBLAS_INLINE
306        bounded_array (const bounded_array &c):
307            storage_array<self_type> (),
308            size_ (c.size_)  {
309            // ISSUE elements should be copy constructed here, but we must copy instead as already default constructed
310            std::copy (c.data_, c.data_ + c.size_, data_);
311        }
312       
313        // Resizing
314        BOOST_UBLAS_INLINE
315        void resize (size_type size) {
316            BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
317            size_ = size;
318        }
319        BOOST_UBLAS_INLINE
320        void resize (size_type size, value_type init) {
321            BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
322            if (size > size_)
323                std::fill (data_ + size_, data_ + size, init);
324            size_ = size;
325        }
326
327        BOOST_UBLAS_INLINE
328        size_type size () const {
329            return size_;
330        }
331
332        // Element access
333        BOOST_UBLAS_INLINE
334        const_reference operator [] (size_type i) const {
335            BOOST_UBLAS_CHECK (i < size_, bad_index ());
336            return data_ [i];
337        }
338        BOOST_UBLAS_INLINE
339        reference operator [] (size_type i) {
340            BOOST_UBLAS_CHECK (i < size_, bad_index ());
341            return data_ [i];
342        }
343
344        // Assignment
345        BOOST_UBLAS_INLINE
346        bounded_array &operator = (const bounded_array &a) {
347            if (this != &a) {
348                resize (a.size_);
349                std::copy (a.data_, a.data_ + a.size_, data_);
350            }
351            return *this;
352        }
353        BOOST_UBLAS_INLINE
354        bounded_array &assign_temporary (bounded_array &a) {
355            *this = a;
356            return *this;
357        }
358
359        // Swapping
360        BOOST_UBLAS_INLINE
361        void swap (bounded_array &a) {
362            if (this != &a) {
363                std::swap (size_, a.size_);
364                std::swap_ranges (data_, data_ + (std::max) (size_, a.size_), a.data_);
365            }
366        }
367        BOOST_UBLAS_INLINE
368        friend void swap (bounded_array &a1, bounded_array &a2) {
369            a1.swap (a2);
370        }
371
372        BOOST_UBLAS_INLINE
373        const_iterator begin () const {
374            return data_;
375        }
376        BOOST_UBLAS_INLINE
377        const_iterator end () const {
378            return data_ + size_;
379        }
380
381        BOOST_UBLAS_INLINE
382        iterator begin () {
383            return data_;
384        }
385        BOOST_UBLAS_INLINE
386        iterator end () {
387            return data_ + size_;
388        }
389
390        // Reverse iterators
391        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
392        typedef std::reverse_iterator<iterator> reverse_iterator;
393
394        BOOST_UBLAS_INLINE
395        const_reverse_iterator rbegin () const {
396            return const_reverse_iterator (end ());
397        }
398        BOOST_UBLAS_INLINE
399        const_reverse_iterator rend () const {
400            return const_reverse_iterator (begin ());
401        }
402        BOOST_UBLAS_INLINE
403        reverse_iterator rbegin () {
404            return reverse_iterator (end ());
405        }
406        BOOST_UBLAS_INLINE
407        reverse_iterator rend () {
408            return reverse_iterator (begin ());
409        }
410
411    private:
412        size_type size_;
413        BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [N];
414    };
415
416
417    // Array adaptor with normal deep copy semantics of elements
418    template<class T>
419    class array_adaptor:
420        public storage_array<array_adaptor<T> > {
421
422        typedef array_adaptor<T> self_type;
423    public:
424        typedef std::size_t size_type;
425        typedef std::ptrdiff_t difference_type;
426        typedef T value_type;
427        typedef const T &const_reference;
428        typedef T &reference;
429        typedef const T *const_pointer;
430        typedef T *pointer;
431
432        // Construction and destruction
433        BOOST_UBLAS_INLINE
434        array_adaptor ():
435            size_ (0), own_ (true), data_ (new value_type [0]) {
436        }
437        explicit BOOST_UBLAS_INLINE
438        array_adaptor (size_type size):
439            size_ (size), own_ (true), data_ (new value_type [size]) {
440        }
441        BOOST_UBLAS_INLINE
442        array_adaptor (size_type size, const value_type &init):
443            size_ (size), own_ (true), data_ (new value_type [size]) {
444            std::fill (data_, data_ + size_, init);
445        }
446        BOOST_UBLAS_INLINE
447        array_adaptor (size_type size, pointer data):
448            size_ (size), own_ (false), data_ (data) {}
449        BOOST_UBLAS_INLINE
450        array_adaptor (const array_adaptor &a):
451            storage_array<self_type> (),
452            size_ (a.size_), own_ (true), data_ (new value_type [a.size_]) {
453            *this = a;
454        }
455        BOOST_UBLAS_INLINE
456        ~array_adaptor () {
457            if (own_) {
458                delete [] data_;
459            }
460        }
461
462        // Resizing
463    private:
464        BOOST_UBLAS_INLINE
465        void resize_internal (size_type size, value_type init, bool preserve = true) {
466           if (size != size_) {
467                pointer data = new value_type [size];
468                if (preserve) {
469                    std::copy (data_, data_ + (std::min) (size, size_), data);
470                    std::fill (data + (std::min) (size, size_), data + size, init);
471                }
472                if (own_)
473                    delete [] data_;
474                size_ = size;
475                own_ = true;
476                data_ = data;
477            }
478        }
479        BOOST_UBLAS_INLINE
480        void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
481            if (data != data_) {
482                if (preserve) {
483                    std::copy (data_, data_ + (std::min) (size, size_), data);
484                    std::fill (data + (std::min) (size, size_), data + size, init);
485                }
486                if (own_)
487                    delete [] data_;
488                own_ = false;
489                data_ = data;
490            }
491            else {
492                std::fill (data + (std::min) (size, size_), data + size, init);
493            }
494            size_ = size;
495        }
496    public:
497        BOOST_UBLAS_INLINE
498        void resize (size_type size) {
499            resize_internal (size, value_type (), false);
500        }
501        BOOST_UBLAS_INLINE
502        void resize (size_type size, value_type init) {
503            resize_internal (size, init, true);
504        }
505        BOOST_UBLAS_INLINE
506        void resize (size_type size, pointer data) {
507            resize_internal (size, data, value_type (), false);
508        }
509        BOOST_UBLAS_INLINE
510        void resize (size_type size, pointer data, value_type init) {
511            resize_internal (size, data, init, true);
512        }
513
514        BOOST_UBLAS_INLINE
515        size_type size () const {
516            return size_;
517        }
518
519        // Element access
520        BOOST_UBLAS_INLINE
521        const_reference operator [] (size_type i) const {
522            BOOST_UBLAS_CHECK (i < size_, bad_index ());
523            return data_ [i];
524        }
525        BOOST_UBLAS_INLINE
526        reference operator [] (size_type i) {
527            BOOST_UBLAS_CHECK (i < size_, bad_index ());
528            return data_ [i];
529        }
530
531        // Assignment
532        BOOST_UBLAS_INLINE
533        array_adaptor &operator = (const array_adaptor &a) {
534            if (this != &a) {
535                resize (a.size_);
536                std::copy (a.data_, a.data_ + a.size_, data_);
537            }
538            return *this;
539        }
540        BOOST_UBLAS_INLINE
541        array_adaptor &assign_temporary (array_adaptor &a) {
542            if (own_ && a.own_)
543                swap (a);
544            else
545                *this = a;
546            return *this;
547        }
548
549        // Swapping
550        BOOST_UBLAS_INLINE
551        void swap (array_adaptor &a) {
552            if (this != &a) {
553                std::swap (size_, a.size_);
554                std::swap (own_, a.own_);
555                std::swap (data_, a.data_);
556            }
557        }
558        BOOST_UBLAS_INLINE
559        friend void swap (array_adaptor &a1, array_adaptor &a2) {
560            a1.swap (a2);
561        }
562
563        // Iterators simply are pointers.
564
565        typedef const_pointer const_iterator;
566
567        BOOST_UBLAS_INLINE
568        const_iterator begin () const {
569            return data_;
570        }
571        BOOST_UBLAS_INLINE
572        const_iterator end () const {
573            return data_ + size_;
574        }
575
576        typedef pointer iterator;
577
578        BOOST_UBLAS_INLINE
579        iterator begin () {
580            return data_;
581        }
582        BOOST_UBLAS_INLINE
583        iterator end () {
584            return data_ + size_;
585        }
586
587        // Reverse iterators
588        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
589        typedef std::reverse_iterator<iterator> reverse_iterator;
590
591        BOOST_UBLAS_INLINE
592        const_reverse_iterator rbegin () const {
593            return const_reverse_iterator (end ());
594        }
595        BOOST_UBLAS_INLINE
596        const_reverse_iterator rend () const {
597            return const_reverse_iterator (begin ());
598        }
599        BOOST_UBLAS_INLINE
600        reverse_iterator rbegin () {
601            return reverse_iterator (end ());
602        }
603        BOOST_UBLAS_INLINE
604        reverse_iterator rend () {
605            return reverse_iterator (begin ());
606        }
607
608    private:
609        size_type size_;
610        bool own_;
611        pointer data_;
612    };
613
614#ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
615    // Array adaptor with shallow (reference) copy semantics of elements.
616    // shared_array is used to maintain reference counts.
617    // This class breaks the normal copy semantics for a storage container and is very dangerous!
618    template<class T>
619    class shallow_array_adaptor:
620        public storage_array<shallow_array_adaptor<T> > {
621
622        typedef shallow_array_adaptor<T> self_type;
623
624        template<class TT>
625        struct leaker {
626            typedef void result_type;
627            typedef TT *argument_type;
628
629            BOOST_UBLAS_INLINE
630            result_type operator () (argument_type x) {}
631        };
632
633    public:
634        typedef std::size_t size_type;
635        typedef std::ptrdiff_t difference_type;
636        typedef T value_type;
637        typedef const T &const_reference;
638        typedef T &reference;
639        typedef const T *const_pointer;
640        typedef T *pointer;
641
642        // Construction and destruction
643        BOOST_UBLAS_INLINE
644        shallow_array_adaptor ():
645            size_ (0), own_ (true), data_ (new value_type [0]) {
646        }
647        explicit BOOST_UBLAS_INLINE
648        shallow_array_adaptor (size_type size):
649            size_ (size), own_ (true), data_ (new value_type [size]) {
650        }
651        BOOST_UBLAS_INLINE
652        shallow_array_adaptor (size_type size, const value_type &init):
653            size_ (size), own_ (true), data_ (new value_type [size]) {
654            std::fill (data_.get (), data_.get () + size_, init);
655        }
656        BOOST_UBLAS_INLINE
657        shallow_array_adaptor (size_type size, pointer data):
658            size_ (size), own_ (false), data_ (data, leaker<value_type> ()) {}
659
660        BOOST_UBLAS_INLINE
661        shallow_array_adaptor (const shallow_array_adaptor &a):
662            storage_array<self_type> (),
663            size_ (a.size_), own_ (a.own_), data_ (a.data_) {}
664
665        BOOST_UBLAS_INLINE
666        ~shallow_array_adaptor () {
667        }
668
669        // Resizing
670    private:
671        BOOST_UBLAS_INLINE
672        void resize_internal (size_type size, value_type init, bool preserve = true) {
673            if (size != size_) {
674                shared_array<value_type> data (new value_type [size]);
675                if (preserve) {
676                    std::copy (data_.get (), data_.get () + (std::min) (size, size_), data.get ());
677                    std::fill (data.get () + (std::min) (size, size_), data.get () + size, init);
678                }
679                size_ = size;
680                data_ = data;
681            }
682        }
683        BOOST_UBLAS_INLINE
684        void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
685            if (preserve) {
686                std::copy (data_.get (), data_.get () + (std::min) (size, size_), data);
687                std::fill (data + (std::min) (size, size_), data + size, init);
688            }
689            size_ = size;
690            data_ = data;
691        }
692    public:
693        BOOST_UBLAS_INLINE
694        void resize (size_type size) {
695            resize_internal (size, value_type (), false);
696        }
697        BOOST_UBLAS_INLINE
698        void resize (size_type size, value_type init) {
699            resize_internal (size, init, true);
700        }
701        BOOST_UBLAS_INLINE
702        void resize (size_type size, pointer data) {
703            resize_internal (size, data, value_type (), false);
704        }
705        BOOST_UBLAS_INLINE
706        void resize (size_type size, pointer data, value_type init) {
707            resize_internal (size, data, init, true);
708        }
709
710        BOOST_UBLAS_INLINE
711        size_type size () const {
712            return size_;
713        }
714
715        // Element access
716        BOOST_UBLAS_INLINE
717        const_reference operator [] (size_type i) const {
718            BOOST_UBLAS_CHECK (i < size_, bad_index ());
719            return data_ [i];
720        }
721        BOOST_UBLAS_INLINE
722        reference operator [] (size_type i) {
723            BOOST_UBLAS_CHECK (i < size_, bad_index ());
724            return data_ [i];
725        }
726
727        // Assignment
728        BOOST_UBLAS_INLINE
729        shallow_array_adaptor &operator = (const shallow_array_adaptor &a) {
730            if (this != &a) {
731                resize (a.size_);
732                std::copy (a.data_.get (), a.data_.get () + a.size_, data_.get ());
733            }
734            return *this;
735        }
736        BOOST_UBLAS_INLINE
737        shallow_array_adaptor &assign_temporary (shallow_array_adaptor &a) {
738            if (own_ && a.own_)
739                swap (a);
740            else
741                *this = a;
742            return *this;
743        }
744
745        // Swapping
746        BOOST_UBLAS_INLINE
747        void swap (shallow_array_adaptor &a) {
748            if (this != &a) {
749                std::swap (size_, a.size_);
750                std::swap (own_, a.own_);
751                std::swap (data_, a.data_);
752            }
753        }
754        BOOST_UBLAS_INLINE
755        friend void swap (shallow_array_adaptor &a1, shallow_array_adaptor &a2) {
756            a1.swap (a2);
757        }
758
759        // Iterators simply are pointers.
760
761        typedef const_pointer const_iterator;
762
763        BOOST_UBLAS_INLINE
764        const_iterator begin () const {
765            return data_.get ();
766        }
767        BOOST_UBLAS_INLINE
768        const_iterator end () const {
769            return data_.get () + size_;
770        }
771
772        typedef pointer iterator;
773
774        BOOST_UBLAS_INLINE
775        iterator begin () {
776            return data_.get ();
777        }
778        BOOST_UBLAS_INLINE
779        iterator end () {
780            return data_.get () + size_;
781        }
782
783        // Reverse iterators
784        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
785        typedef std::reverse_iterator<iterator> reverse_iterator;
786
787        BOOST_UBLAS_INLINE
788        const_reverse_iterator rbegin () const {
789            return const_reverse_iterator (end ());
790        }
791        BOOST_UBLAS_INLINE
792        const_reverse_iterator rend () const {
793            return const_reverse_iterator (begin ());
794        }
795        BOOST_UBLAS_INLINE
796        reverse_iterator rbegin () {
797            return reverse_iterator (end ());
798        }
799        BOOST_UBLAS_INLINE
800        reverse_iterator rend () {
801            return reverse_iterator (begin ());
802        }
803
804    private:
805        size_type size_;
806        bool own_;
807        shared_array<value_type> data_;
808    };
809
810#endif
811
812    // Range class
813    template <class Z, class D>
814    class basic_range {
815        typedef basic_range<Z, D> self_type;
816    public:
817        typedef Z size_type;
818        typedef D difference_type;
819        typedef size_type value_type;
820        typedef value_type const_reference;
821        typedef const_reference reference;
822        typedef const value_type *const_pointer;
823        typedef value_type *pointer;
824
825        // Construction and destruction
826        BOOST_UBLAS_INLINE
827        basic_range ():
828            start_ (0), size_ (0) {}
829        BOOST_UBLAS_INLINE
830        basic_range (size_type start, size_type stop):
831            start_ (start), size_ (stop - start) {
832            BOOST_UBLAS_CHECK (start_ <= stop, bad_index ());
833        }
834
835        BOOST_UBLAS_INLINE
836        size_type start () const {
837            return start_;
838        }
839        BOOST_UBLAS_INLINE
840        size_type size () const {
841            return size_;
842        }
843
844        // Assignment
845        basic_range operator=( basic_range const& r ) {
846           start_ = r.start_ ;
847           size_ = r.size_ ;
848           return *this ;
849        }
850
851        // Element access
852        BOOST_UBLAS_INLINE
853        const_reference operator () (size_type i) const {
854            BOOST_UBLAS_CHECK (i < size_, bad_index ());
855            return start_ + i;
856        }
857
858        // Composition
859        BOOST_UBLAS_INLINE
860        basic_range compose (const basic_range &r) const {
861            return basic_range (start_ + r.start_, start_ + r.start_ + r.size_);
862        }
863
864        // Comparison
865        BOOST_UBLAS_INLINE
866        bool operator == (const basic_range &r) const {
867            return start_ == r.start_ && size_ == r.size_;
868        }
869        BOOST_UBLAS_INLINE
870        bool operator != (const basic_range &r) const {
871            return ! (*this == r);
872        }
873
874        // Iterator types
875    private:
876        // Use and index
877        typedef size_type const_subiterator_type;
878
879    public:
880#ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
881        typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
882#else
883        class const_iterator:
884            public container_const_reference<basic_range>,
885            public random_access_iterator_base<std::random_access_iterator_tag,
886                                               const_iterator, value_type> {
887        public:
888            typedef typename basic_range::value_type value_type;
889            typedef typename basic_range::difference_type difference_type;
890            typedef typename basic_range::const_reference reference;
891            typedef typename basic_range::const_pointer pointer;
892
893            // Construction and destruction
894            BOOST_UBLAS_INLINE
895            const_iterator ():
896                container_const_reference<basic_range> (), it_ () {}
897            BOOST_UBLAS_INLINE
898            const_iterator (const basic_range &r, const const_subiterator_type &it):
899                container_const_reference<basic_range> (r), it_ (it) {}
900
901            // Arithmetic
902            BOOST_UBLAS_INLINE
903            const_iterator &operator ++ () {
904                ++ it_;
905                return *this;
906            }
907            BOOST_UBLAS_INLINE
908            const_iterator &operator -- () {
909                BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
910                -- it_;
911                return *this;
912            }
913            BOOST_UBLAS_INLINE
914            const_iterator &operator += (difference_type n) {
915                BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
916                it_ += n;
917                return *this;
918            }
919            BOOST_UBLAS_INLINE
920            const_iterator &operator -= (difference_type n) {
921                BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
922                it_ -= n;
923                return *this;
924            }
925            BOOST_UBLAS_INLINE
926            difference_type operator - (const const_iterator &it) const {
927                return it_ - it.it_;
928            }
929
930            // Dereference
931            BOOST_UBLAS_INLINE
932            const_reference operator * () const {
933                BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
934                BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
935                return it_;
936            }
937
938            // Index
939            BOOST_UBLAS_INLINE
940            size_type index () const {
941                BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
942                BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
943                return it_ - (*this) ().start ();
944            }
945
946            // Assignment
947            BOOST_UBLAS_INLINE
948            const_iterator &operator = (const const_iterator &it) {
949                // Comeau recommends...
950                this->assign (&it ());
951                it_ = it.it_;
952                return *this;
953            }
954
955            // Comparison
956            BOOST_UBLAS_INLINE
957            bool operator == (const const_iterator &it) const {
958                BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
959                return it_ == it.it_;
960            }
961            BOOST_UBLAS_INLINE
962            bool operator < (const const_iterator &it) const {
963                BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
964                return it_ < it.it_;
965            }
966
967        private:
968            const_subiterator_type it_;
969        };
970#endif
971
972        BOOST_UBLAS_INLINE
973        const_iterator begin () const {
974            return const_iterator (*this, start_);
975        }
976        BOOST_UBLAS_INLINE
977        const_iterator end () const {
978            return const_iterator (*this, start_ + size_);
979        }
980
981        // Reverse iterator
982        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
983
984        BOOST_UBLAS_INLINE
985        const_reverse_iterator rbegin () const {
986            return const_reverse_iterator (end ());
987        }
988        BOOST_UBLAS_INLINE
989        const_reverse_iterator rend () const {
990            return const_reverse_iterator (begin ());
991        }
992
993        BOOST_UBLAS_INLINE
994        basic_range preprocess (size_type size) const {
995            if (this != &all_)
996                return *this;
997            return basic_range (0, size);
998        }
999        static
1000        BOOST_UBLAS_INLINE
1001        const basic_range &all () {
1002            return all_;
1003        }
1004
1005    private:
1006        size_type start_;
1007        size_type size_;
1008        static const basic_range all_;
1009    };
1010
1011    template <class Z, class D>
1012    const basic_range<Z,D> basic_range<Z,D>::all_  (0, size_type (-1));
1013
1014
1015    // Slice class
1016    template <class Z, class D>
1017    class basic_slice {
1018        typedef basic_slice<Z, D> self_type;
1019    public:
1020        typedef Z size_type;
1021        typedef D difference_type;
1022        typedef size_type value_type;
1023        typedef value_type const_reference;
1024        typedef const_reference reference;
1025        typedef const value_type *const_pointer;
1026        typedef value_type *pointer;
1027
1028        // Construction and destruction
1029        BOOST_UBLAS_INLINE
1030        basic_slice ():
1031            start_ (0), stride_ (0), size_ (0) {}
1032        BOOST_UBLAS_INLINE
1033        basic_slice (size_type start, difference_type stride, size_type size):
1034            start_ (start), stride_ (stride), size_ (size) {}
1035
1036        BOOST_UBLAS_INLINE
1037        size_type start () const {
1038            return start_;
1039        }
1040        BOOST_UBLAS_INLINE
1041        difference_type stride () const {
1042            return stride_;
1043        }
1044        BOOST_UBLAS_INLINE
1045        size_type size () const {
1046            return size_;
1047        }
1048
1049        // Element access
1050        BOOST_UBLAS_INLINE
1051        const_reference operator () (size_type i) const {
1052            BOOST_UBLAS_CHECK (i < size_, bad_index ());
1053            BOOST_UBLAS_CHECK (stride_ >= 0 || start_ >= i * -stride_, bad_index ());
1054            return start_ + i * stride_;
1055        }
1056
1057        // Composition
1058        BOOST_UBLAS_INLINE
1059        basic_slice compose (const basic_range<size_type, difference_type> &r) const {
1060            BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * r.start(), bad_index ());
1061            return basic_slice (start_ + stride_ * r.start (), stride_, r.size ());
1062        }
1063        BOOST_UBLAS_INLINE
1064        basic_slice compose (const basic_slice &s) const {
1065            BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * s.start_, bad_index ());
1066            return basic_slice (start_ + stride_ * s.start_, stride_ * s.stride_, s.size_);
1067        }
1068
1069        // Comparison
1070        BOOST_UBLAS_INLINE
1071        bool operator == (const basic_slice &s) const {
1072            return start_ == s.start_ && stride_ == s.stride_ && size_ == s.size_;
1073        }
1074        BOOST_UBLAS_INLINE
1075        bool operator != (const basic_slice &s) const {
1076            return ! (*this == s);
1077        }
1078
1079        // Iterator types
1080    private:
1081        // Use and index
1082        typedef size_type const_subiterator_type;
1083
1084    public:
1085#ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1086        typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1087#else
1088        class const_iterator:
1089            public container_const_reference<basic_slice>,
1090            public random_access_iterator_base<std::random_access_iterator_tag,
1091                                               const_iterator, value_type> {
1092        public:
1093            typedef typename basic_slice::value_type value_type;
1094            typedef typename basic_slice::difference_type difference_type;
1095            typedef typename basic_slice::const_reference reference;
1096            typedef typename basic_slice::const_pointer pointer;
1097
1098            // Construction and destruction
1099            BOOST_UBLAS_INLINE
1100            const_iterator ():
1101                container_const_reference<basic_slice> (), it_ () {}
1102            BOOST_UBLAS_INLINE
1103            const_iterator (const basic_slice &s, const const_subiterator_type &it):
1104                container_const_reference<basic_slice> (s), it_ (it) {}
1105
1106            // Arithmetic
1107            BOOST_UBLAS_INLINE
1108            const_iterator &operator ++ () {
1109                ++it_;
1110                return *this;
1111            }
1112            BOOST_UBLAS_INLINE
1113            const_iterator &operator -- () {
1114                BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
1115                --it_;
1116                return *this;
1117            }
1118            BOOST_UBLAS_INLINE
1119            const_iterator &operator += (difference_type n) {
1120                BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
1121                it_ += n;
1122                return *this;
1123            }
1124            BOOST_UBLAS_INLINE
1125            const_iterator &operator -= (difference_type n) {
1126                BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
1127                it_ -= n;
1128                return *this;
1129            }
1130            BOOST_UBLAS_INLINE
1131            difference_type operator - (const const_iterator &it) const {
1132                return it_ - it.it_;
1133            }
1134
1135            // Dereference
1136            BOOST_UBLAS_INLINE
1137            const_reference operator * () const {
1138                BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
1139                return (*this) ().start () + it_* (*this) ().stride ();
1140            }
1141
1142            // Index
1143            BOOST_UBLAS_INLINE
1144            size_type index () const {
1145                BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
1146                return it_;
1147            }
1148
1149            // Assignment
1150            BOOST_UBLAS_INLINE
1151            const_iterator &operator = (const const_iterator &it) {
1152                // Comeau recommends...
1153                this->assign (&it ());
1154                it_ = it.it_;
1155                return *this;
1156            }
1157
1158            // Comparison
1159            BOOST_UBLAS_INLINE
1160            bool operator == (const const_iterator &it) const {
1161                BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1162                return it_ == it.it_;
1163            }
1164            BOOST_UBLAS_INLINE
1165            bool operator < (const const_iterator &it) const {
1166                BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1167                return it_ < it.it_;
1168            }
1169
1170        private:
1171            const_subiterator_type it_;
1172        };
1173#endif
1174
1175        BOOST_UBLAS_INLINE
1176        const_iterator begin () const {
1177            return const_iterator (*this, 0);
1178        }
1179        BOOST_UBLAS_INLINE
1180        const_iterator end () const {
1181            return const_iterator (*this, size_);
1182        }
1183
1184        // Reverse iterator
1185        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1186
1187        BOOST_UBLAS_INLINE
1188        const_reverse_iterator rbegin () const {
1189            return const_reverse_iterator (end ());
1190        }
1191        BOOST_UBLAS_INLINE
1192        const_reverse_iterator rend () const {
1193            return const_reverse_iterator (begin ());
1194        }
1195
1196        BOOST_UBLAS_INLINE
1197        basic_slice preprocess (size_type size) const {
1198            if (this != &all_)
1199                return *this;
1200            return basic_slice (0, 1, size);
1201        }
1202        static
1203        BOOST_UBLAS_INLINE
1204        const basic_slice &all () {
1205            return all_;
1206        }
1207
1208    private:
1209        size_type start_;
1210        difference_type stride_;
1211        size_type size_;
1212        static const basic_slice all_;
1213    };
1214
1215    template <class Z, class D>
1216    const basic_slice<Z,D> basic_slice<Z,D>::all_  (0, 1, size_type (-1));
1217
1218
1219    // Indirect array class
1220    template<class A>
1221    class indirect_array {
1222        typedef indirect_array<A> self_type;
1223    public:
1224        typedef A array_type;
1225        typedef const A const_array_type;
1226        typedef typename A::size_type size_type;
1227        typedef typename A::difference_type difference_type;
1228        typedef typename A::value_type value_type;
1229        typedef typename A::const_reference const_reference;
1230        typedef typename A::reference reference;
1231        typedef typename A::const_pointer const_pointer;
1232        typedef typename A::pointer pointer;
1233
1234        // Construction and destruction
1235        BOOST_UBLAS_INLINE
1236        indirect_array ():
1237            size_ (), data_ () {}
1238        explicit BOOST_UBLAS_INLINE
1239        indirect_array (size_type size):
1240            size_ (size), data_ (size) {}
1241        BOOST_UBLAS_INLINE
1242        indirect_array (size_type size, const array_type &data):
1243            size_ (size), data_ (data) {}
1244        BOOST_UBLAS_INLINE
1245        indirect_array (pointer start, pointer stop):
1246            size_ (stop - start), data_ (stop - start) {
1247            std::copy (start, stop, data_.begin ());
1248        }
1249
1250        BOOST_UBLAS_INLINE
1251        size_type size () const {
1252            return size_;
1253        }
1254        BOOST_UBLAS_INLINE
1255        const_array_type data () const {
1256            return data_;
1257        }
1258        BOOST_UBLAS_INLINE
1259        array_type data () {
1260            return data_;
1261        }
1262
1263        // Element access
1264        BOOST_UBLAS_INLINE
1265        const_reference operator () (size_type i) const {
1266            BOOST_UBLAS_CHECK (i < size_, bad_index ());
1267            return data_ [i];
1268        }
1269        BOOST_UBLAS_INLINE
1270        reference operator () (size_type i) {
1271            BOOST_UBLAS_CHECK (i < size_, bad_index ());
1272            return data_ [i];
1273        }
1274
1275        BOOST_UBLAS_INLINE
1276        const_reference operator [] (size_type i) const {
1277            return (*this) (i);
1278        }
1279        BOOST_UBLAS_INLINE
1280        reference operator [] (size_type i) {
1281            return (*this) (i);
1282        }
1283
1284        // Composition
1285        BOOST_UBLAS_INLINE
1286        indirect_array compose (const basic_range<size_type, difference_type> &r) const {
1287            BOOST_UBLAS_CHECK (r.start () + r.size () <= size_, bad_size ());
1288            array_type data (r.size ());
1289            for (size_type i = 0; i < r.size (); ++ i)
1290                data [i] = data_ [r.start () + i];
1291            return indirect_array (r.size (), data);
1292        }
1293        BOOST_UBLAS_INLINE
1294        indirect_array compose (const basic_slice<size_type, difference_type> &s) const {
1295            BOOST_UBLAS_CHECK (s.start () + s.stride () * (s.size () - (s.size () > 0)) <= size (), bad_size ());
1296            array_type data (s.size ());
1297            for (size_type i = 0; i < s.size (); ++ i)
1298                data [i] = data_ [s.start () + s.stride () * i];
1299            return indirect_array (s.size (), data);
1300        }
1301        BOOST_UBLAS_INLINE
1302        indirect_array compose (const indirect_array &ia) const {
1303            array_type data (ia.size_);
1304            for (size_type i = 0; i < ia.size_; ++ i) {
1305                BOOST_UBLAS_CHECK (ia.data_ [i] <= size_, bad_size ());
1306                data [i] = data_ [ia.data_ [i]];
1307            }
1308            return indirect_array (ia.size_, data);
1309        }
1310
1311        // Comparison
1312        template<class OA>
1313        BOOST_UBLAS_INLINE
1314        bool operator == (const indirect_array<OA> &ia) const {
1315            if (size_ != ia.size_)
1316                return false;
1317            for (size_type i = 0; i < BOOST_UBLAS_SAME (size_, ia.size_); ++ i)
1318                if (data_ [i] != ia.data_ [i])
1319                    return false;
1320            return true;
1321        }
1322        template<class OA>
1323        BOOST_UBLAS_INLINE
1324        bool operator != (const indirect_array<OA> &ia) const {
1325            return ! (*this == ia);
1326        }
1327
1328        // Iterator types
1329    private:
1330        // Use a index difference
1331        typedef difference_type const_subiterator_type;
1332
1333    public:
1334#ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1335        typedef indexed_const_iterator<indirect_array, std::random_access_iterator_tag> const_iterator;
1336#else
1337        class const_iterator:
1338            public container_const_reference<indirect_array>,
1339            public random_access_iterator_base<std::random_access_iterator_tag,
1340                                               const_iterator, value_type> {
1341        public:
1342            typedef typename indirect_array::value_type value_type;
1343            typedef typename indirect_array::difference_type difference_type;
1344            typedef typename indirect_array::const_reference reference;
1345            typedef typename indirect_array::const_pointer pointer;
1346
1347            // Construction and destruction
1348            BOOST_UBLAS_INLINE
1349            const_iterator ():
1350                container_const_reference<indirect_array> (), it_ () {}
1351            BOOST_UBLAS_INLINE
1352            const_iterator (const indirect_array &ia, const const_subiterator_type &it):
1353                container_const_reference<indirect_array> (ia), it_ (it) {}
1354
1355            // Arithmetic
1356            BOOST_UBLAS_INLINE
1357            const_iterator &operator ++ () {
1358                ++ it_;
1359                return *this;
1360            }
1361            BOOST_UBLAS_INLINE
1362            const_iterator &operator -- () {
1363                -- it_;
1364                return *this;
1365            }
1366            BOOST_UBLAS_INLINE
1367            const_iterator &operator += (difference_type n) {
1368                it_ += n;
1369                return *this;
1370            }
1371            BOOST_UBLAS_INLINE
1372            const_iterator &operator -= (difference_type n) {
1373                it_ -= n;
1374                return *this;
1375            }
1376            BOOST_UBLAS_INLINE
1377            difference_type operator - (const const_iterator &it) const {
1378                return it_ - it.it_;
1379            }
1380
1381            // Dereference
1382            BOOST_UBLAS_INLINE
1383            const_reference operator * () const {
1384                return (*this) () (it_);
1385            }
1386
1387            // Index
1388            BOOST_UBLAS_INLINE
1389            size_type index () const {
1390                return it_;
1391            }
1392
1393            // Assignment
1394            BOOST_UBLAS_INLINE
1395            const_iterator &operator = (const const_iterator &it) {
1396                // Comeau recommends...
1397                this->assign (&it ());
1398                it_ = it.it_;
1399                return *this;
1400            }
1401
1402            // Comparison
1403            BOOST_UBLAS_INLINE
1404            bool operator == (const const_iterator &it) const {
1405                BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1406                return it_ == it.it_;
1407            }
1408            BOOST_UBLAS_INLINE
1409            bool operator < (const const_iterator &it) const {
1410                BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1411                return it_ < it.it_;
1412            }
1413
1414        private:
1415            const_subiterator_type it_;
1416        };
1417#endif
1418
1419        BOOST_UBLAS_INLINE
1420        const_iterator begin () const {
1421            return const_iterator (*this, 0);
1422        }
1423        BOOST_UBLAS_INLINE
1424        const_iterator end () const {
1425            return const_iterator (*this, size_);
1426        }
1427
1428        // Reverse iterator
1429        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1430
1431        BOOST_UBLAS_INLINE
1432        const_reverse_iterator rbegin () const {
1433            return const_reverse_iterator (end ());
1434        }
1435        BOOST_UBLAS_INLINE
1436        const_reverse_iterator rend () const {
1437            return const_reverse_iterator (begin ());
1438        }
1439
1440        BOOST_UBLAS_INLINE
1441        indirect_array preprocess (size_type size) const {
1442            if (this != &all_)
1443                return *this;
1444            indirect_array ia (size);
1445            for (size_type i = 0; i < size; ++ i)
1446               ia (i) = i;
1447            return ia;
1448        }
1449        static
1450        BOOST_UBLAS_INLINE
1451        const indirect_array &all () {
1452            return all_;
1453        }
1454
1455    private:
1456        size_type size_;
1457        array_type data_;
1458        static const indirect_array all_;
1459    };
1460
1461    template<class A>
1462    const indirect_array<A> indirect_array<A>::all_;
1463
1464
1465
1466    // Gunter Winkler contributed the classes index_pair, index_pair_array,
1467    // index_triple and index_triple_array to enable inplace sort of parallel arrays.
1468
1469    template <class V>
1470    class index_pair :
1471        private boost::noncopyable,
1472        public container_reference<V> {
1473
1474        typedef index_pair<V> self_type;
1475    public:
1476        typedef typename V::size_type size_type;
1477
1478        BOOST_UBLAS_INLINE
1479        index_pair(V& v, size_type i) :
1480            container_reference<V>(v), i_(i),
1481            v1_(v.data1_[i]), v2_(v.data2_[i]),
1482            dirty_(false), is_copy_(false) {}
1483         BOOST_UBLAS_INLINE
1484        index_pair(const self_type& rhs) :
1485            container_reference<V>(rhs()), i_(0),
1486            v1_(rhs.v1_), v2_(rhs.v2_),
1487            dirty_(false), is_copy_(true) {}
1488         BOOST_UBLAS_INLINE
1489        ~index_pair() {
1490            if (dirty_ && (!is_copy_) ) {
1491                (*this)().data1_[i_] = v1_;
1492                (*this)().data2_[i_] = v2_;
1493            }
1494        }
1495
1496        BOOST_UBLAS_INLINE
1497        self_type& operator=(const self_type& rhs) {
1498            v1_ = rhs.v1_;
1499            v2_ = rhs.v2_;
1500            dirty_ = true;
1501            return *this;
1502        }
1503
1504        BOOST_UBLAS_INLINE
1505        void swap(self_type rhs) {
1506            self_type tmp(rhs);
1507            rhs = *this;
1508            *this = tmp;
1509        }
1510        BOOST_UBLAS_INLINE
1511        friend void swap(self_type lhs, self_type rhs) {
1512            lhs.swap(rhs);
1513        }
1514
1515        BOOST_UBLAS_INLINE
1516        bool equal(const self_type& rhs) const {
1517            return (v1_ == rhs.v1_);
1518        }
1519        bool less(const self_type& rhs) const {
1520            return (v1_ < rhs.v1_);
1521        }
1522        BOOST_UBLAS_INLINE
1523        friend bool operator == (const self_type& lhs, const self_type& rhs) {
1524            return lhs.equal(rhs);
1525        }
1526        BOOST_UBLAS_INLINE
1527        friend bool operator != (const self_type& lhs, const self_type& rhs) {
1528            return !lhs.equal(rhs);
1529        }
1530        BOOST_UBLAS_INLINE
1531        friend bool operator < (const self_type& lhs, const self_type& rhs) {
1532            return lhs.less(rhs);
1533        }
1534
1535    private:
1536        size_type i_;
1537        typename V::value1_type v1_;
1538        typename V::value2_type v2_;
1539        bool dirty_;
1540        bool is_copy_;
1541     };
1542
1543    template <class V1, class V2>
1544    class index_pair_array:
1545        private boost::noncopyable {
1546
1547        typedef index_pair_array<V1, V2> self_type;
1548    public:
1549        typedef typename V1::value_type value1_type;
1550        typedef typename V2::value_type value2_type;
1551
1552        typedef typename V1::size_type size_type;
1553        typedef typename V1::difference_type difference_type;
1554        typedef index_pair<self_type> value_type;
1555        // There is nothing that can be referenced directly. Always return a copy of the index_pair
1556        typedef value_type reference;
1557        typedef const value_type const_reference;
1558
1559        BOOST_UBLAS_INLINE
1560        index_pair_array(size_type size, V1& data1, V2& data2) :
1561              size_(size),data1_(data1),data2_(data2) {}
1562
1563        BOOST_UBLAS_INLINE
1564        size_type size() const {
1565            return size_;
1566        }
1567
1568        BOOST_UBLAS_INLINE
1569        const_reference operator () (size_type i) const {
1570            return value_type((*this), i);
1571        }
1572        BOOST_UBLAS_INLINE
1573        reference operator () (size_type i) {
1574            return value_type((*this), i);
1575        }
1576
1577        typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
1578        typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1579
1580        BOOST_UBLAS_INLINE
1581        iterator begin() {
1582            return iterator( (*this), 0);
1583        }
1584        BOOST_UBLAS_INLINE
1585        iterator end() {
1586            return iterator( (*this), size());
1587        }
1588
1589        BOOST_UBLAS_INLINE
1590        const_iterator begin() const {
1591            return const_iterator( (*this), 0);
1592        }
1593        BOOST_UBLAS_INLINE
1594        const_iterator end() const {
1595            return const_iterator( (*this), size());
1596        }
1597
1598        // unnecessary function:
1599        BOOST_UBLAS_INLINE
1600        bool equal(size_type i1, size_type i2) const {
1601            return data1_[i1] == data1_[i2];
1602        }
1603        BOOST_UBLAS_INLINE
1604        bool less(size_type i1, size_type i2) const {
1605            return data1_[i1] < data1_[i2];
1606        }
1607
1608        // gives a large speedup
1609        BOOST_UBLAS_INLINE
1610        friend void iter_swap(const iterator& lhs, const iterator& rhs) {
1611            const size_type i1 = lhs.index();
1612            const size_type i2 = rhs.index();
1613            std::swap(lhs().data1_[i1], rhs().data1_[i2]);
1614            std::swap(lhs().data2_[i1], rhs().data2_[i2]);
1615        }
1616
1617    private:
1618        size_type size_;
1619        V1& data1_;
1620        V2& data2_;
1621
1622        // friend class value_type;
1623        friend class index_pair<self_type>;
1624    };
1625
1626    template <class M>
1627    class index_triple :
1628        private boost::noncopyable,
1629        public container_reference<M> {
1630
1631        typedef index_triple<M> self_type;
1632    public:
1633        typedef typename M::size_type size_type;
1634
1635        BOOST_UBLAS_INLINE
1636        index_triple(M& m, size_type i) :
1637            container_reference<M>(m), i_(i),
1638            v1_(m.data1_[i]), v2_(m.data2_[i]), v3_(m.data3_[i]),
1639            dirty_(false), is_copy_(false) {}
1640        BOOST_UBLAS_INLINE
1641        index_triple(const self_type& rhs) :
1642            container_reference<M>(rhs()), i_(0),
1643            v1_(rhs.v1_), v2_(rhs.v2_), v3_(rhs.v3_),
1644            dirty_(false), is_copy_(true) {}
1645        BOOST_UBLAS_INLINE
1646        ~index_triple() {
1647            if (dirty_ && (!is_copy_) ) {
1648                (*this)().data1_[i_] = v1_;
1649                (*this)().data2_[i_] = v2_;
1650                (*this)().data3_[i_] = v3_;
1651            }
1652        }
1653
1654        BOOST_UBLAS_INLINE
1655        self_type& operator=(const self_type& rhs) {
1656            v1_ = rhs.v1_;
1657            v2_ = rhs.v2_;
1658            v3_ = rhs.v3_;
1659            dirty_ = true;
1660            return *this;
1661        }
1662
1663        BOOST_UBLAS_INLINE
1664        void swap(self_type rhs) {
1665            self_type tmp(rhs);
1666            rhs = *this;
1667            *this = tmp;
1668        }
1669        BOOST_UBLAS_INLINE
1670        friend void swap(self_type lhs, self_type rhs) {
1671            lhs.swap(rhs);
1672        }
1673
1674        BOOST_UBLAS_INLINE
1675        bool equal(const self_type& rhs) const {
1676            return ((v1_ == rhs.v1_) && (v2_ == rhs.v2_));
1677        }
1678        BOOST_UBLAS_INLINE
1679        bool less(const self_type& rhs) const {
1680            return ((v1_ < rhs.v1_) ||
1681                    (v1_ == rhs.v1_ && v2_ < rhs.v2_));
1682        }
1683        BOOST_UBLAS_INLINE
1684        friend bool operator == (const self_type& lhs, const self_type& rhs) {
1685            return lhs.equal(rhs);
1686        }
1687        BOOST_UBLAS_INLINE
1688        friend bool operator != (const self_type& lhs, const self_type& rhs) {
1689            return !lhs.equal(rhs);
1690        }
1691        BOOST_UBLAS_INLINE
1692        friend bool operator < (const self_type& lhs, const self_type& rhs) {
1693            return lhs.less(rhs);
1694        }
1695
1696    private:
1697        size_type i_;
1698        typename M::value1_type v1_;
1699        typename M::value2_type v2_;
1700        typename M::value3_type v3_;
1701        bool dirty_;
1702        bool is_copy_;
1703    };
1704
1705    template <class V1, class V2, class V3>
1706    class index_triple_array:
1707        private boost::noncopyable {
1708
1709        typedef index_triple_array<V1, V2, V3> self_type;
1710    public:
1711        typedef typename V1::value_type value1_type;
1712        typedef typename V2::value_type value2_type;
1713        typedef typename V3::value_type value3_type;
1714
1715        typedef typename V1::size_type size_type;
1716        typedef typename V1::difference_type difference_type;
1717        typedef index_triple<self_type> value_type;
1718        // There is nothing that can be referenced directly. Always return a copy of the index_triple
1719        typedef value_type reference;
1720        typedef const value_type const_reference;
1721
1722        BOOST_UBLAS_INLINE
1723        index_triple_array(size_type size, V1& data1, V2& data2, V3& data3) :
1724              size_(size),data1_(data1),data2_(data2),data3_(data3) {}
1725
1726        BOOST_UBLAS_INLINE
1727        size_type size() const {
1728            return size_;
1729        }
1730
1731        BOOST_UBLAS_INLINE
1732        const_reference operator () (size_type i) const {
1733            return value_type((*this), i);
1734        }
1735        BOOST_UBLAS_INLINE
1736        reference operator () (size_type i) {
1737            return value_type((*this), i);
1738        }
1739
1740        typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
1741        typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1742
1743        BOOST_UBLAS_INLINE
1744        iterator begin() {
1745            return iterator( (*this), 0);
1746        }
1747        BOOST_UBLAS_INLINE
1748        iterator end() {
1749            return iterator( (*this), size());
1750        }
1751
1752        BOOST_UBLAS_INLINE
1753        const_iterator begin() const {
1754            return const_iterator( (*this), 0);
1755        }
1756        BOOST_UBLAS_INLINE
1757        const_iterator end() const {
1758            return const_iterator( (*this), size());
1759        }
1760
1761        // unnecessary function:
1762        BOOST_UBLAS_INLINE
1763        bool equal(size_type i1, size_type i2) const {
1764            return ((data1_[i1] == data1_[i2]) && (data2_[i1] == data2_[i2]));
1765        }
1766        BOOST_UBLAS_INLINE
1767        bool less(size_type i1, size_type i2) const {
1768            return ((data1_[i1] < data1_[i2]) ||
1769                    (data1_[i1] == data1_[i2] && data2_[i1] < data2_[i2]));
1770        }
1771
1772        // gives a large speedup
1773        BOOST_UBLAS_INLINE
1774        friend void iter_swap(const iterator& lhs, const iterator& rhs) {
1775            const size_type i1 = lhs.index();
1776            const size_type i2 = rhs.index();
1777            std::swap(lhs().data1_[i1], rhs().data1_[i2]);
1778            std::swap(lhs().data2_[i1], rhs().data2_[i2]);
1779            std::swap(lhs().data3_[i1], rhs().data3_[i2]);
1780        }
1781
1782    private:
1783        size_type size_;
1784        V1& data1_;
1785        V2& data2_;
1786        V3& data3_;
1787
1788        // friend class value_type;
1789        friend class index_triple<self_type>;
1790    };
1791
1792}}}
1793
1794#endif
Note: See TracBrowser for help on using the repository browser.