storage.hpp

CGAL is a collaborative effort of several sites in Europe and Israel. The goal is to make the most i

//
//  Copyright (c) 2000-2002
//  Joerg Walter, Mathias Koch
//
//  Permission to use, copy, modify, distribute and sell this software
//  and its documentation for any purpose is hereby granted without fee,
//  provided that the above copyright notice appear in all copies and
//  that both that copyright notice and this permission notice appear
//  in supporting documentation.  The authors make no representations
//  about the suitability of this software for any purpose.
//  It is provided "as is" without express or implied warranty.
//
//  The authors gratefully acknowledge the support of
//  GeNeSys mbH & Co. KG in producing this work.
//

#ifndef BOOST_UBLAS_STORAGE_H
#define BOOST_UBLAS_STORAGE_H

#include <algorithm>

#ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
#include <boost/shared_array.hpp>
#endif

#include <boost/numeric/ublas/config.hpp>
#include <boost/numeric/ublas/exception.hpp>
#include <boost/numeric/ublas/iterator.hpp>
#include <boost/numeric/ublas/traits.hpp>

namespace boost { namespace numeric { namespace ublas {

#ifndef BOOST_UBLAS_USE_FAST_SAME
// FIXME: for performance reasons we better use macros
//    template<class T>
//    BOOST_UBLAS_INLINE
//    const T &same_impl (const T &size1, const T &size2) {
//        BOOST_UBLAS_CHECK (size1 == size2, bad_argument ());
//        return (std::min) (size1, size2);
//    }
// #define BOOST_UBLAS_SAME(size1, size2) same_impl ((size1), (size2))
    template<class T>
    BOOST_UBLAS_INLINE
    // Kresimir Fresl and Dan Muller reported problems with COMO.
    // We better change the signature instead of libcomo ;-)
    // const T &same_impl_ex (const T &size1, const T &size2, const char *file, int line) {
    T same_impl_ex (const T &size1, const T &size2, const char *file, int line) {
        BOOST_UBLAS_CHECK_EX (size1 == size2, file, line, bad_argument ());
        return (std::min) (size1, size2);
    }
#define BOOST_UBLAS_SAME(size1, size2) same_impl_ex ((size1), (size2), __FILE__, __LINE__)
#else
// FIXME: for performance reasons we better use macros
//    template<class T>
//    BOOST_UBLAS_INLINE
//    const T &same_impl (const T &size1, const T &size2) {
//        return size1;
//    }
// #define BOOST_UBLAS_SAME(size1, size2) same_impl ((size1), (size2))
#define BOOST_UBLAS_SAME(size1, size2) (size1)
#endif

// If no standard allocator assume it is because hint must be specified. This fixes VC6
#ifdef BOOST_NO_STD_ALLOCATOR
#define BOOST_UBLAS_ALLOCATOR_HINT , 0
#else
#define BOOST_UBLAS_ALLOCATOR_HINT
#endif


    // Base class for Storage Arrays - see the Barton Nackman trick
    template<class E>
    class storage_array:
        private nonassignable {
    };


    // Unbounded array - with allocator
    template<class T, class ALLOC>
    class unbounded_array:
        public storage_array<unbounded_array<T, ALLOC> > {
    public:
        typedef ALLOC allocator_type;
        typedef typename ALLOC::size_type size_type;
        typedef typename ALLOC::difference_type difference_type;
        typedef T value_type;
        typedef const T &const_reference;
        typedef T &reference;
        typedef const T *const_pointer;
        typedef T *pointer;
        typedef const_pointer const_iterator;
        typedef pointer iterator;
    private:
        typedef unbounded_array<T, ALLOC> self_type;

    public:
        // Construction and destruction
        explicit BOOST_UBLAS_INLINE
        unbounded_array (const ALLOC &a = ALLOC()):
            alloc_ (a), size_ (0), data_ (0) {
        }
        explicit BOOST_UBLAS_INLINE
        unbounded_array (size_type size, const ALLOC &a = ALLOC()):
            alloc_(a), size_ (size) {
            if (size_) {
                data_ = alloc_.allocate (size_ BOOST_UBLAS_ALLOCATOR_HINT);
                // ISSUE some compilers may zero POD here
#ifdef BOOST_UBLAS_USEFUL_ARRAY_PLACEMENT_NEW
                // array form fails on some compilers due to size cookie, is it standard conforming?
                new (data_) value_type[size_];
#else
                for (pointer d = data_; d != data_ + size_; ++d)
                    new (d) value_type;
#endif
            }
        }
        // No value initialised, but still be default constructed
        BOOST_UBLAS_INLINE
        unbounded_array (size_type size, const value_type &init, const ALLOC &a = ALLOC()):
            alloc_ (a), size_ (size) {
            if (size_) {
                data_ = alloc_.allocate (size_ BOOST_UBLAS_ALLOCATOR_HINT);
                std::uninitialized_fill (begin(), end(), init);
            }
        }
        BOOST_UBLAS_INLINE
        unbounded_array (const unbounded_array &c):
            storage_array<self_type> (),
            alloc_ (c.alloc_), size_ (c.size_) {
            if (size_) {
                data_ = alloc_.allocate (size_ BOOST_UBLAS_ALLOCATOR_HINT);
                std::uninitialized_copy (c.begin(), c.end(), begin());
            }
            else
                data_ = 0;
        }
        BOOST_UBLAS_INLINE
        ~unbounded_array () {
            if (size_) {
                const iterator i_end = end();
                for (iterator i = begin (); i != i_end; ++i) {
                    iterator_destroy (i); 
                }
                alloc_.deallocate (data_, size_);
            }
        }

        // Resizing
    private:
        BOOST_UBLAS_INLINE
        void resize_internal (size_type size, value_type init, bool preserve) {
            if (size != size_) {
                pointer data;
                if  (size) {
                    data = alloc_.allocate (size BOOST_UBLAS_ALLOCATOR_HINT);
                    if (preserve) {
                        const_iterator si = begin ();
                        pointer di = data;
                        if (size < size_) {
                            for (; di != data + size; ++di) {
                                alloc_.construct (di, *si);
                                ++si;
                            }
                        }
                        else {
                            for (const_iterator si_end = end (); si != si_end; ++si) {
                                alloc_.construct (di, *si);
                                ++di;
                            }
                            for (; di != data + size; ++di) {
                                alloc_.construct (di, init);
                            }
                        }
                    }
                    else {
                        // ISSUE some compilers may zero POD here
#ifdef BOOST_UBLAS_USEFUL_ARRAY_PLACEMENT_NEW
                        // array form fails on some compilers due to size cookie, is it standard conforming?
                        new (data) value_type[size];
#else
                        for (pointer d = data; d != data + size; ++d)
                            new (d) value_type;
#endif
                    }                    
                }
                else
                    data = 0;
                if (size_) {
                    const iterator i_end = end();
                    for (iterator i = begin(); i != i_end; ++i) {
                        iterator_destroy (i); 
                    }
                    alloc_.deallocate (data_, size_);
                }
                size_ = size;
                data_ = data;
            }
        }
    public:
        BOOST_UBLAS_INLINE
        void resize (size_type size) {
            resize_internal (size, value_type (), false);
        }
        BOOST_UBLAS_INLINE
        void resize (size_type size, value_type init) {
            resize_internal (size, init, true);
        }
                    
        BOOST_UBLAS_INLINE
        size_type size () const {
            return size_;
        }

        // Element access
        BOOST_UBLAS_INLINE
        const_reference operator [] (size_type i) const {
            BOOST_UBLAS_CHECK (i < size_, bad_index ());
            return data_ [i];
        }
        BOOST_UBLAS_INLINE
        reference operator [] (size_type i) {
            BOOST_UBLAS_CHECK (i < size_, bad_index ());
            return data_ [i];
        }

        // Assignment
        BOOST_UBLAS_INLINE
        unbounded_array &operator = (const unbounded_array &a) {
            if (this != &a) {
                resize (a.size_);
                std::copy (a.data_, a.data_ + a.size_, data_);
            }
            return *this;
        }
        BOOST_UBLAS_INLINE
        unbounded_array &assign_temporary (unbounded_array &a) {
            swap (a);
            return *this;
        }

        // Swapping
        BOOST_UBLAS_INLINE
        void swap (unbounded_array &a) {
            if (this != &a) {
                std::swap (size_, a.size_);
                std::swap (data_, a.data_);
            }
        }
#ifndef BOOST_UBLAS_NO_MEMBER_FRIENDS
        BOOST_UBLAS_INLINE
        friend void swap (unbounded_array &a1, unbounded_array &a2) {
            a1.swap (a2);
        }
#endif

        BOOST_UBLAS_INLINE
        const_iterator begin () const {
            return data_;
        }
        BOOST_UBLAS_INLINE
        const_iterator end () const {
            return data_ + size_;
        }

        BOOST_UBLAS_INLINE
        iterator begin () {
            return data_;
        }
        BOOST_UBLAS_INLINE
        iterator end () {
            return data_ + size_;
        }

        // Reverse iterators

#ifdef BOOST_MSVC_STD_ITERATOR
        typedef std::reverse_iterator<const_iterator, value_type, const_reference> const_reverse_iterator;
#else
        typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
#endif

        BOOST_UBLAS_INLINE
        const_reverse_iterator rbegin () const {
            return const_reverse_iterator (end ());
        }
        BOOST_UBLAS_INLINE
        const_reverse_iterator rend () const {
            return const_reverse_iterator (begin ());
        }

#ifdef BOOST_MSVC_STD_ITERATOR
        typedef std::reverse_iterator<iterator, value_type, reference> reverse_iterator;
#else
        typedef std::reverse_iterator<iterator> reverse_iterator;
#endif

        BOOST_UBLAS_INLINE
        reverse_iterator rbegin () {
            return reverse_iterator (end ());
        }
        BOOST_UBLAS_INLINE
        reverse_iterator rend () {
            return reverse_iterator (begin ());
        }

        // Allocator
        allocator_type get_allocator () {
            return alloc_;
        }

    private:
        // Handle explict destroy on a (possibly indexed) iterator
        BOOST_UBLAS_INLINE
        static void iterator_destroy (iterator &i) {
            (&(*i)) -> ~value_type ();
        }
        ALLOC alloc_;
        size_type size_;
        pointer data_;
    };

    // Bounded array - with allocator for size_type and difference_type
    template<class T, std::size_t N, class ALLOC>
    class bounded_array:
        public storage_array<bounded_array<T, N, ALLOC> > {
    public:
        // No allocator_type as ALLOC is not used for allocation
        typedef typename ALLOC::size_type size_type;
        typedef typename ALLOC::difference_type difference_type;
        typedef T value_type;
        typedef const T &const_reference;
        typedef T &reference;
        typedef const T *const_pointer;
        typedef T *pointer;
        typedef const_pointer const_iterator;
        typedef pointer iterator;
    private:
        typedef bounded_array<T, N, ALLOC> self_type;

    public:
        // Construction and destruction
        BOOST_UBLAS_INLINE
        bounded_array ():
            size_ (0), data_ () {   // size 0 - use bounded_vector to default construct with size N
        }
        explicit BOOST_UBLAS_INLINE
        bounded_array (size_type size):
            size_ (size) /*, data_ ()*/ {
            if (size_ > N)
                bad_size ().raise ();
            // data_ (an array) elements are already default constructed
        }
        BOOST_UBLAS_INLINE
        bounded_array (size_type size, const value_type &init):
            size_ (size) /*, data_ ()*/ {
            if (size_ > N)
                bad_size ().raise ();
            // ISSUE elements should be value constructed here, but we must fill instead as already default constructed
            std::fill (begin(), end(), init) ;
        }
        BOOST_UBLAS_INLINE
        bounded_array (const bounded_array &c):
            storage_array<self_type> (),
            size_ (c.size_)  {
            // ISSUE elements should be copy constructed here, but we must copy instead as already default constructed
            std::copy (c.data_, c.data_ + c.size_, data_);
        }
        
        // Resizing
        BOOST_UBLAS_INLINE
        void resize (size_type size) {
            if (size > N)
                bad_size ().raise ();
            size_ = size;
        }
        BOOST_UBLAS_INLINE
        void resize (size_type size, value_type init) {
            if (size > N)
                bad_size ().raise ();
            if (size > size_)
                std::fill (data_ + size_, data_ + size, init);
            size_ = size;
        }

        BOOST_UBLAS_INLINE
        size_type size () const {
            return size_;
        }

        // Element access
        BOOST_UBLAS_INLINE