agg_array.h

okular

//----------------------------------------------------------------------------
// Anti-Grain Geometry - Version 2.3
// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
//
// Permission to copy, use, modify, sell and distribute this software 
// is granted provided this copyright notice appears in all copies. 
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
//
//----------------------------------------------------------------------------
// Contact: [e-mail]
//          [e-mail]
//          http://www.antigrain.com
//----------------------------------------------------------------------------
#ifndef AGG_ARRAY_INCLUDED
#define AGG_ARRAY_INCLUDED

#include <stddef.h>
#include <string.h>
#include "agg_basics.h"

namespace agg
{



    //-------------------------------------------------------pod_array_adaptor
    template<class T> class pod_array_adaptor
    {
    public:
        typedef T value_type;
        pod_array_adaptor(T* array, unsigned size) : 
            m_array(array), m_size(size) {}

        unsigned size() const { return m_size; }
        const T& operator [] (unsigned idx) const { return m_array[idx]; }
              T& operator [] (unsigned idx)       { return m_array[idx]; }
    private:
        T*       m_array;
        unsigned m_size;
    };



    //---------------------------------------------------------pod_auto_array
    template<class T, unsigned Size> class pod_auto_array
    {
    public:
        typedef T value_type;
        typedef pod_auto_array<T, Size> self_type;

        pod_auto_array() {}
        explicit pod_auto_array(const T* c)
        {
            memcpy(m_array, c, sizeof(T) * Size);
        }

        const self_type& operator = (const T* c)
        {
            memcpy(m_array, c, sizeof(T) * Size);
            return *this;
        }

        static unsigned size() { return Size; }
        const T& operator [] (unsigned i) const { return m_array[i]; }
              T& operator [] (unsigned i)       { return m_array[i]; }
    private:
        T m_array[Size];
    };





    //---------------------------------------------------------------pod_array
    // A simple class template to store Plain Old Data, a vector
    // of a fixed size. The data is continuous in memory
    //------------------------------------------------------------------------
    template<class T> class pod_array
    {
    public:
        typedef T value_type;

        ~pod_array() { delete [] m_array; }
        pod_array() : m_size(0), m_capacity(0), m_array(0) {}
        pod_array(unsigned cap, unsigned extra_tail=0);

        // Copying
        pod_array(const pod_array<T>&);
        const pod_array<T>& operator = (const pod_array<T>&);

        unsigned capacity() const { return m_capacity; }
        void capacity(unsigned cap, unsigned extra_tail=0);

        void resize(unsigned new_size);

        void add(const T& v)  { m_array[m_size++] = v; }
        void inc_size(unsigned size) { m_size += size; } 
        unsigned size()      const { return m_size; }
        unsigned byte_size() const { return m_size * sizeof(T); }
        void serialize(int8u* ptr) const;
        void deserialize(const int8u* data, unsigned byte_size);
        const T& operator [] (unsigned idx) const { return m_array[idx]; }
              T& operator [] (unsigned idx)       { return m_array[idx]; }

        void remove_all()         { m_size = 0; }
        void cut_at(unsigned num) { if(num < m_size) m_size = num; }

    private:
        unsigned m_size;
        unsigned m_capacity;
        T*       m_array;
    };

    //------------------------------------------------------------------------
    template<class T> 
    void pod_array<T>::capacity(unsigned cap, unsigned extra_tail)
    {
        m_size = 0;
        if(cap > m_capacity)
        {
            delete [] m_array;
            m_capacity = cap + extra_tail;
            m_array = m_capacity ? new T [m_capacity] : 0;
        }
    }

    //------------------------------------------------------------------------
    template<class T> 
    void pod_array<T>::resize(unsigned new_size)
    {
        if(new_size > m_size)
        {
            if(new_size > m_capacity)
            {
                T* data = new T[new_size];
                memcpy(data, m_array, m_size * sizeof(T));
                delete [] m_array;
                m_array = data;
            }
        }
        else
        {
            m_size = new_size;
        }
    }

    //------------------------------------------------------------------------
    template<class T> pod_array<T>::pod_array(unsigned cap, unsigned extra_tail) :
        m_size(cap), m_capacity(cap + extra_tail), m_array(new T[m_capacity]) {}

    //------------------------------------------------------------------------
    template<class T> pod_array<T>::pod_array(const pod_array<T>& v) :
        m_size(v.m_size),
        m_capacity(v.m_capacity),
        m_array(v.m_capacity ? new T [v.m_capacity] : 0)
    {
        memcpy(m_array, v.m_array, sizeof(T) * v.m_size);
    }

    //------------------------------------------------------------------------
    template<class T> const pod_array<T>& 
    pod_array<T>::operator = (const pod_array<T>&v)
    {
        capacity(v.m_capacity);
        if(v.m_size) memcpy(m_array, v.m_array, sizeof(T) * v.m_size);
        return *this;
    }

    //------------------------------------------------------------------------
    template<class T> void pod_array<T>::serialize(int8u* ptr) const
    { 
        if(m_size) memcpy(ptr, m_array, m_size * sizeof(T)); 
    }

    //------------------------------------------------------------------------
    template<class T> 
    void pod_array<T>::deserialize(const int8u* data, unsigned byte_size)
    {
        byte_size /= sizeof(T);
        capacity(byte_size);
        if(byte_size) memcpy(m_array, data, byte_size * sizeof(T));
    }





    //---------------------------------------------------------------pod_deque
    // A simple class template to store Plain Old Data, similar to std::deque
    // It doesn't reallocate memory but instead, uses blocks of data of size 
    // of (1 << S), that is, power of two. The data is NOT continuous in memory, 
    // so the only valid access method is operator [] or curr(), prev(), next()
    // 
    // There reallocs occure only when the pool of pointers to blocks needs 
    // to be extended (it happens very rear). You can control the value 
    // of increment to reallocate the pointer buffer. See the second constructor.
    // By default, the incremeent value equals (1 << S), i.e., the block size.
    //------------------------------------------------------------------------
    template<class T, unsigned S=6> class pod_deque
    {
    public:
        enum 
        {   
            block_shift = S,
            block_size  = 1 << block_shift,
            block_mask  = block_size - 1
        };

        typedef T value_type;

        ~pod_deque();
        pod_deque();
        pod_deque(unsigned block_ptr_inc);

        // Copying
        pod_deque(const pod_deque<T, S>& v);
        const pod_deque<T, S>& operator = (const pod_deque<T, S>& v);

        void remove_all() { m_size = 0; }
        void free_all() { free_tail(0); }
        void free_tail(unsigned size);
        void add(const T& val);
        void modify_last(const T& val);
        void remove_last();

        int allocate_continuous_block(unsigned num_elements);

        void add_array(const T* ptr, unsigned num_elem)
        {
            while(num_elem--)
            {
                add(*ptr++);
            }
        }

        template<class DataAccessor> void add_data(DataAccessor& data)
        {
            while(data.size())
            {
                add(*data);
                ++data;
            }
        }

        void cut_at(unsigned size)
        {
            if(size < m_size) m_size = size;
        }

        unsigned size() const { return m_size; }

        const T& operator [] (unsigned idx) const
        {
            return m_blocks[idx >> block_shift][idx & block_mask];
        }

        T& operator [] (unsigned idx)
        {
            return m_blocks[idx >> block_shift][idx & block_mask];
        }

        const T& curr(unsigned idx) const
        {
            return (*this)[idx];
        }

        T& curr(unsigned idx)
        {
            return (*this)[idx];
        }

        const T& prev(unsigned idx) const
        {
            return (*this)[(idx + m_size - 1) % m_size];
        }

        T& prev(unsigned idx)
        {
            return (*this)[(idx + m_size - 1) % m_size];
        }

        const T& next(unsigned idx) const
        {
            return (*this)[(idx + 1) % m_size];
        }

        T& next(unsigned idx)
        {
            return (*this)[(idx + 1) % m_size];
        }

        const T& last() const
        {
            return (*this)[m_size - 1];
        }

        T& last()
        {
            return (*this)[m_size - 1];
        }

        unsigned byte_size() const;
        void serialize(int8u* ptr) const;
        void deserialize(const int8u* data, unsigned byte_size);
        void deserialize(unsigned start, const T& empty_val, 
                         const int8u* data, unsigned byte_size);

        template<class ByteAccessor> 
        void deserialize(ByteAccessor data)
        {
            remove_all();
            unsigned elem_size = data.size() / sizeof(T);

            for(unsigned i = 0; i < elem_size; ++i)
            {
                int8u* ptr = (int8u*)data_ptr();
                for(unsigned j = 0; j < sizeof(T); ++j)
                {
                    *ptr++ = *data;
                    ++data;
                }
                ++m_size;
            }
        }

        template<class ByteAccessor>
        void deserialize(unsigned start, const T& empty_val, ByteAccessor data)
        {
            while(m_size < start)
            {
                add(empty_val);
            }

            unsigned elem_size = data.size() / sizeof(T);
            for(unsigned i = 0; i < elem_size; ++i)
            {
                int8u* ptr;
                if(start + i < m_size)
                {
                    ptr = (int8u*)(&((*this)[start + i]));
                }
                else
                {
                    ptr = (int8u*)data_ptr();
                    ++m_size;
                }
                for(unsigned j = 0; j < sizeof(T); ++j)
                {
                    *ptr++ = *data;
                    ++data;
                }
            }
        }

        const T* block(unsigned nb) const { return m_blocks[nb]; }

    private:
        void allocate_block(unsigned nb);
        T*   data_ptr();

        unsigned        m_size;
        unsigned        m_num_blocks;
        unsigned        m_max_blocks;
        T**             m_blocks;
        unsigned        m_block_ptr_inc;
    };


    //------------------------------------------------------------------------
    template<class T, unsigned S> pod_deque<T, S>::~pod_deque()
    {
        if(m_num_blocks)
        {
            T** blk = m_blocks + m_num_blocks - 1;
            while(m_num_blocks--)
            {
                delete [] *blk;
                --blk;
            }
            delete [] m_blocks;
        }
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    void pod_deque<T, S>::free_tail(unsigned size)
    {
        if(size < m_size)
        {
            unsigned nb = (size + block_mask) >> block_shift;
            while(m_num_blocks > nb)
            {
                delete [] m_blocks[--m_num_blocks];
            }
            m_size = size;
        }
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S> pod_deque<T, S>::pod_deque() :
        m_size(0),
        m_num_blocks(0),
        m_max_blocks(0),
        m_blocks(0),
        m_block_ptr_inc(block_size)
    {
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    pod_deque<T, S>::pod_deque(unsigned block_ptr_inc) :
        m_size(0),
        m_num_blocks(0),
        m_max_blocks(0),
        m_blocks(0),
        m_block_ptr_inc(block_ptr_inc)
    {
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S> 
    pod_deque<T, S>::pod_deque(const pod_deque<T, S>& v) :
        m_size(v.m_size),
        m_num_blocks(v.m_num_blocks),
        m_max_blocks(v.m_max_blocks),
        m_blocks(v.m_max_blocks ? new T* [v.m_max_blocks] : 0),
        m_block_ptr_inc(v.m_block_ptr_inc)
    {
        unsigned i;
        for(i = 0; i < v.m_num_blocks; ++i)
        {
            m_blocks[i] = new T [block_size];
            memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T));
        }
    }


    //------------------------------------------------------------------------
    template<class T, unsigned S>