array.h

//---------------------------------------------------------------------
//  Algorithmic Conjurings @ http://www.coyotegulch.com
//
//  array.h (libcoyotl)
//
//  Templatized array classes compatible with STL containers and
//  algorithms.
//---------------------------------------------------------------------
//
//  Copyright 1990-2005 Scott Robert Ladd
//
//  This program is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//  
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//  
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the
//      Free Software Foundation, Inc.
//      59 Temple Place - Suite 330
//      Boston, MA 02111-1307, USA.
//
//-----------------------------------------------------------------------
//
//  For more information on this software package, please visit
//  Scott's web site, Coyote Gulch Productions, at:
//
//      http://www.coyotegulch.com
//  
//-----------------------------------------------------------------------
 
#if !defined(LIBCOYOTL_ARRAY_H)
#define LIBCOYOTL_ARRAY_H
 
// Microsoft Visual C++-specific pragmas
#if defined(_MSC_VER)
#pragma warning(disable : 4290 4101) // "exception specification ignored", "unused var"
#endif
 
#include <cstddef>   // for size_t
#include <algorithm> // for lexicographical_compare
 
#include "validator.h" // validation functions
#include "realutil.h"  // need min_of function
 
#if defined(LIBCOYOTL_BOUNDS_CHECKING)
#include <stdexcept>
#include <sstream>
#define LIBCOYOTL_ARRAY_EXCEPTIONS validation_error<size_t>
#define LIBCOYOTL_ARRAY_CHECK_INDEX(n) validate_less(n,m_size,LIBCOYOTL_LOCATION);
#else
#define LIBCOYOTL_ARRAY_EXCEPTIONS
#define LIBCOYOTL_ARRAY_CHECK_INDEX(n)
#endif
 
namespace libcoyotl
{
 
    template <typename Type>
    class array
    {
    public:
        typedef Type         value_type;
 
        typedef Type *       pointer;
 
        typedef const Type * const_pointer;
 
        typedef Type &       reference;
 
        typedef const Type & const_reference;
 
        typedef ptrdiff_t    difference_type;
 
        typedef size_t       size_type;
 
        typedef Type *       iterator;
 
        typedef const Type * const_iterator;
 
        typedef Type *       reverse_iterator;
 
        typedef const Type * const_reverse_iterator;
 
 
        array(size_t a_length);
 
 
        array(size_t a_length, const Type & a_init_value);
 
 
        array(const array<Type> & a_source);
 
 
        array(size_t a_length, const Type * a_carray);
 
 
        virtual ~array() throw();
 
 
        array & operator = (const array<Type> & a_source) throw();
 
 
        array & operator = (const Type & a_value) throw();
 
 
        array & operator = (const Type * a_carray) throw();
 
 
        const Type * c_array() const throw();
 
 
        Type & operator [] (size_t n) throw(LIBCOYOTL_ARRAY_EXCEPTIONS);
 
 
        Type operator [] (size_t n) const throw(LIBCOYOTL_ARRAY_EXCEPTIONS);
 
 
        void append(const array<Type> & a_array);
 
 
        iterator begin() throw();
 
 
        const_iterator begin() const throw();
 
 
        iterator end() throw();
 
 
        const_iterator end() const throw();
 
 
        iterator rbegin() throw();
 
 
        const_iterator rbegin() const throw();
 
 
        iterator rend() throw();
 
 
        const_iterator rend() const throw();
 
 
        bool operator == (const array<Type> & a_comparand) const throw();
 
 
        bool operator != (const array<Type> & a_comparand) const throw();
 
 
        bool operator <  (const array<Type> & a_comparand) const throw();
 
 
        bool operator <= (const array<Type> & a_comparand) const throw();
 
 
        bool operator >  (const array<Type> & a_comparand) const throw();
 
 
        bool operator >= (const array<Type> & a_comparand) const throw();
 
 
        void swap(array<Type> & a_source) throw();
        
 
        size_t size() const throw();
 
 
        size_t max_size() const throw();
 
 
        bool empty() const throw();
 
    protected:
        Type * m_array;
 
        size_t m_size;
 
    private:
        // assign a single a_value to all elements
        void assign_value(const Type & a_value) throw();
 
        // copy elements from a c-style array
        void copy_carray(const Type * a_carray) throw();
 
        // copy elements from another array
        void copy_array(const array<Type> & a_source) throw();
    };
 
    // assign a single a_value to all elements
    template <typename Type>
    void array<Type>::assign_value(const Type & a_value) throw()
    {
        Type * element_ptr = m_array;
 
        for (size_t n = 0; n < m_size; ++n)
        {
            *element_ptr = a_value;
            ++element_ptr;
        }
    }
 
    // copy elements from a c-style array
    template <typename Type>
    void array<Type>::copy_carray(const Type * a_carray) throw()
    {
        // use pointers for speed
        Type * target_ptr = m_array;
        const Type * carray_ptr  = a_carray;
 
        for (size_t n = 0; n < m_size; ++n)
        {
            *target_ptr = *carray_ptr;
            ++target_ptr;
            ++carray_ptr;
        }
    }
 
    // copy elements from another array
    template <typename Type>
    void array<Type>::copy_array(const array<Type> & a_source) throw()
    {
        // find minimum a_length between the two arrays
        size_t copy_length = min_of(m_size,a_source.m_size);
 
        // use pointers for speed
        Type * target_ptr = m_array;
        const Type * source_ptr = a_source.m_array;
 
        for (size_t n = 0; n < copy_length; ++n)
        {
            *target_ptr = *source_ptr;
            ++target_ptr;
            ++source_ptr;
        }
    }
 
    // default constructor
    template <typename Type>
    array<Type>::array(size_t a_length)
      : m_array(NULL),
        m_size(a_length)
    {
        // enforce lower limit on a_length
        enforce_lower_limit(m_size,size_t(1));
 
        // allocate array
        m_array = new Type [m_size];
    }
 
    // a_value constructor
    template <typename Type>
    array<Type>::array(size_t a_length, const Type & a_init_value)
      : m_array(NULL),
        m_size(a_length)
    {
        // enforce lower limit on a_length
        enforce_lower_limit(m_size,size_t(1));
 
        // allocate array
        m_array = new Type [m_size];
 
        // assign values
        assign_value(a_init_value);
    }
 
    // copy constructor
    template <typename Type>
    array<Type>::array(const array<Type> & a_source)
      : m_array(NULL),
        m_size(a_source.m_size)
    {
        // allocate array
        m_array = new Type [m_size];
 
        // copy a_source array
        copy_array(a_source);
    }
 
    // construct from C-style array
    template <typename Type>
    array<Type>::array(size_t a_length, const Type * a_carray)
      : m_array(NULL),
        m_size(a_length)
    {
        // validate a_source
        validate_not(a_carray,(const Type *)NULL,LIBCOYOTL_LOCATION);
 
        // enforce lower limit on a_length
        enforce_lower_limit(m_size,size_t(1));
 
        // allocate array
        m_array = new Type [m_size];
 
        // copy elements of c array
        copy_carray(a_carray);
    }
 
    // destructor
    template <typename Type>
    array<Type>::~array() throw()
    {
        // clean up resources
        delete [] m_array;
        m_array  = NULL;
        m_size = 0;
    }
 
    // assignment operator
    template <typename Type>
    array<Type> & array<Type>::operator = (const array<Type> & a_source) throw()
    {
        copy_array(a_source);
        return *this;
    }
 
    // assign all operator
    template <typename Type>
    array<Type> & array<Type>::operator = (const Type & a_value) throw()
    {
        assign_value(a_value);
        return *this;
    }
 
    // assign from C-style array
    template <typename Type>
    array<Type> & array<Type>::operator = (const Type * a_source) throw()
    {
        copy_carray(a_source);
        return *this;
    }
 
    // conversion to C-style array
    template <typename Type>
    inline const Type * array<Type>::c_array() const throw()
    {
        return m_array;
    }
 
    // element access
    template <typename Type>
    inline Type & array<Type>::operator [] (size_t n) throw(LIBCOYOTL_ARRAY_EXCEPTIONS)
    {
        LIBCOYOTL_ARRAY_CHECK_INDEX(n)
        return m_array[n];
    }
 
    template <typename Type>
    inline Type array<Type>::operator [] (size_t n) const throw(LIBCOYOTL_ARRAY_EXCEPTIONS)
    {
        LIBCOYOTL_ARRAY_CHECK_INDEX(n)
        return m_array[n];
    }
 
    // appending
    template <typename Type>
    void array<Type>::append(const array<Type> & other)
    {
        size_t new_size = m_size + other.m_size;
        Type * new_array = new Type[new_size];
 
        Type * target = new_array;
        Type * a_source = m_array;
        size_t n;
 
        // copy from this array
        for (n = 0; n < m_size; ++n)
        {
            *target = *a_source;
            ++target;
            ++a_source;
        }
 
        // copy from other array
        a_source = other.m_array;
 
        for (n = 0; n < other.m_size; ++n)
        {
            *target = *a_source;
            ++target;
            ++a_source;
        }
 
        // set this to use new array, destroying old one
        m_size = new_size;
        delete [] m_array;
        m_array = new_array;
    }
 
    // iterator functions
    template <typename Type>
    inline typename array<Type>::iterator array<Type>::begin() throw()
    {
        return &(m_array[0]);
    }
 
    template <typename Type>
    inline typename array<Type>::const_iterator array<Type>::begin() const throw()
    {
        return &(m_array[0]);
    }
 
    template <typename Type>
    inline typename array<Type>::iterator array<Type>::end() throw()
    {
        return &(m_array[m_size]);
    }
 
    template <typename Type>
    inline typename array<Type>::const_iterator array<Type>::end() const throw()
    {
        return &(m_array[m_size]);
    }
 
    template <typename Type>
    inline typename array<Type>::reverse_iterator array<Type>::rbegin() throw()
    {
        return end();
    }
 
    template <typename Type>
    inline typename array<Type>::const_reverse_iterator array<Type>::rbegin() const throw()
    {
        return end();
    }
 
    template <typename Type>
    inline typename array<Type>::reverse_iterator array<Type>::rend() throw()
    {
        return begin();
    }
 
    template <typename Type>
    inline typename array<Type>::const_reverse_iterator array<Type>::rend() const throw()
    {
        return begin();
    }
 
    // comparisons (required by std. container definition)
    template <typename Type>
    inline bool array<Type>::operator == (const array<Type> & a_array) const throw()
    {
        return equal(begin(),end(),a_array.begin());
    }
 
    template <typename Type>
    inline bool array<Type>::operator != (const array<Type> & a_array) const throw()
    {
        return !(*this == a_array);
    }
 
    template <typename Type>
    inline bool array<Type>::operator < (const array<Type> & a_array) const throw()
    {
        return lexicographical_compare(begin(),end(),a_array.begin(),a_array.end());
    }
 
    template <typename Type>
    inline bool array<Type>::operator > (const array<Type> & a_array) const throw()
    {
        return (a_array < *this);
    }
 
    template <typename Type>
    inline bool array<Type>::operator <= (const array<Type> & a_array) const throw()
    {
        return !(*this > a_array);
    }
 
    template <typename Type>
    inline bool array<Type>::operator >= (const array<Type> & a_array) const throw()
    {
        return !(*this < a_array);
    }
 
    // swap (required by std. container definition)
    template <typename Type>
    void array<Type>::swap(array<Type> & a_source) throw()
    {
        // in this case, both arrays must be the same a_length
        validate_equals(m_size,a_source.m_size,LIBCOYOTL_LOCATION);
 
        // use pointers for copy
        Type * target_ptr = m_array;
        Type * source_ptr = a_source.m_array;
 
        for (size_t n = 0; n < m_size; ++n)
        {
            Type temp   = *target_ptr;
            *target_ptr = *source_ptr;
            *source_ptr = temp;
 
            ++target_ptr;
            ++source_ptr;
        }
    }
 
    // number of elements
    template <typename Type>
    inline size_t array<Type>::size() const throw()
    {
        return m_size;
    }
 
    // max_size (required by std. container definition)
    template <typename Type>
    inline size_t array<Type>::max_size() const throw()
    {
        return m_size;
    }
 
    // empty (always false; required by std. container definition)
    template <typename Type>
    inline bool array<Type>::empty() const throw()
    {
        return false;
    }
 
};
 
#endif