agg_array.h

windows ce 下的画各种b样条曲线

//----------------------------------------------------------------------------
// Anti-Grain Geometry (AGG) - Version 2.5
// A high quality rendering engine for C++
// Copyright (C) 2002-2006 Maxim Shemanarev
// Contact: [e-mail]
//          [e-mail]
//          http://antigrain.com
// 
// AGG 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.
// 
// AGG 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 AGG; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 
// MA 02110-1301, USA.
//----------------------------------------------------------------------------

#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 i) const { return m_array[i]; }
              T& operator [] (unsigned i)       { return m_array[i]; }
        const T& at(unsigned i) const           { return m_array[i]; }
              T& at(unsigned i)                 { return m_array[i]; }
        T  value_at(unsigned i) const           { return m_array[i]; }

    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]; }
        const T& at(unsigned i) const           { return m_array[i]; }
              T& at(unsigned i)                 { return m_array[i]; }
        T  value_at(unsigned i) const           { return m_array[i]; }

    private:
        T m_array[Size];
    };


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

        pod_auto_vector() : m_size(0) {}

        void remove_all()            { m_size = 0; }
        void clear()                 { m_size = 0; }
        void add(const T& v)         { m_array[m_size++] = v; }
        void push_back(const T& v)   { m_array[m_size++] = v; }
        void inc_size(unsigned size) { m_size += size; }
        
        unsigned size() const { return m_size; }
        const T& operator [] (unsigned i) const { return m_array[i]; }
              T& operator [] (unsigned i)       { return m_array[i]; }
        const T& at(unsigned i) const           { return m_array[i]; }
              T& at(unsigned i)                 { return m_array[i]; }
        T  value_at(unsigned i) const           { return m_array[i]; }

    private:
        T m_array[Size];
        unsigned m_size;
    };


    //---------------------------------------------------------------pod_array
    template<class T> class pod_array
    {
    public:
        typedef T value_type;
        typedef pod_array<T> self_type;

        ~pod_array() { pod_allocator<T>::deallocate(m_array, m_size); }
        pod_array() : m_array(0), m_size(0) {}

        pod_array(unsigned size) : 
            m_array(pod_allocator<T>::allocate(size)), 
            m_size(size) 
        {}

        pod_array(const self_type& v) : 
            m_array(pod_allocator<T>::allocate(v.m_size)), 
            m_size(v.m_size) 
        {
            memcpy(m_array, v.m_array, sizeof(T) * m_size);
        }

        void resize(unsigned size)
        {
            if(size != m_size)
            {
                pod_allocator<T>::deallocate(m_array, m_size);
                m_array = pod_allocator<T>::allocate(m_size = size);
            }
        }
        const self_type& operator = (const self_type& v)
        {
            resize(v.size());
            memcpy(m_array, v.m_array, sizeof(T) * m_size);
            return *this;
        }

        unsigned size() const { return m_size; }
        const T& operator [] (unsigned i) const { return m_array[i]; }
              T& operator [] (unsigned i)       { return m_array[i]; }
        const T& at(unsigned i) const           { return m_array[i]; }
              T& at(unsigned i)                 { return m_array[i]; }
        T  value_at(unsigned i) const           { return m_array[i]; }

        const T* data() const { return m_array; }
              T* data()       { return m_array; }
    private:
        T*       m_array;
        unsigned m_size;
    };



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

        ~pod_vector() { pod_allocator<T>::deallocate(m_array, m_capacity); }
        pod_vector() : m_size(0), m_capacity(0), m_array(0) {}
        pod_vector(unsigned cap, unsigned extra_tail=0);

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

        // Set new capacity. All data is lost, size is set to zero.
        void capacity(unsigned cap, unsigned extra_tail=0);
        unsigned capacity() const { return m_capacity; }

        // Allocate n elements. All data is lost, 
        // but elements can be accessed in range 0...size-1. 
        void allocate(unsigned size, unsigned extra_tail=0);

        // Resize keeping the content.
        void resize(unsigned new_size);

        void zero()
        {
            memset(m_array, 0, sizeof(T) * m_size);
        }

        void add(const T& v)         { m_array[m_size++] = v; }
        void push_back(const T& v)   { m_array[m_size++] = v; }
        void insert_at(unsigned pos, const T& val);
        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 i) const { return m_array[i]; }
              T& operator [] (unsigned i)       { return m_array[i]; }
        const T& at(unsigned i) const           { return m_array[i]; }
              T& at(unsigned i)                 { return m_array[i]; }
        T  value_at(unsigned i) const           { return m_array[i]; }

        const T* data() const { return m_array; }
              T* data()       { return m_array; }

        void remove_all()         { m_size = 0; }
        void clear()              { 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_vector<T>::capacity(unsigned cap, unsigned extra_tail)
    {
        m_size = 0;
        if(cap > m_capacity)
        {
            pod_allocator<T>::deallocate(m_array, m_capacity);
            m_capacity = cap + extra_tail;
            m_array = m_capacity ? pod_allocator<T>::allocate(m_capacity) : 0;
        }
    }

    //------------------------------------------------------------------------
    template<class T> 
    void pod_vector<T>::allocate(unsigned size, unsigned extra_tail)
    {
        capacity(size, extra_tail);
        m_size = size;
    }


    //------------------------------------------------------------------------
    template<class T> 
    void pod_vector<T>::resize(unsigned new_size)
    {
        if(new_size > m_size)
        {
            if(new_size > m_capacity)
            {
                T* data = pod_allocator<T>::allocate(new_size);
                memcpy(data, m_array, m_size * sizeof(T));
                pod_allocator<T>::deallocate(m_array, m_capacity);
                m_array = data;
            }
        }
        else
        {
            m_size = new_size;
        }
    }

    //------------------------------------------------------------------------
    template<class T> pod_vector<T>::pod_vector(unsigned cap, unsigned extra_tail) :
        m_size(0), 
        m_capacity(cap + extra_tail), 
        m_array(pod_allocator<T>::allocate(m_capacity)) {}

    //------------------------------------------------------------------------
    template<class T> pod_vector<T>::pod_vector(const pod_vector<T>& v) :
        m_size(v.m_size),
        m_capacity(v.m_capacity),
        m_array(v.m_capacity ? pod_allocator<T>::allocate(v.m_capacity) : 0)
    {
        memcpy(m_array, v.m_array, sizeof(T) * v.m_size);
    }

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

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

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

    //------------------------------------------------------------------------
    template<class T> 
    void pod_vector<T>::insert_at(unsigned pos, const T& val)
    {
        if(pos >= m_size) 
        {
            m_array[m_size] = val;
        }
        else
        {
            memmove(m_array + pos + 1, m_array + pos, (m_size - pos) * sizeof(T));
            m_array[pos] = val;
        }
        ++m_size;
    }

    //---------------------------------------------------------------pod_bvector
    // 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 contiguous 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 rarely). 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_bvector
    {
    public:
        enum block_scale_e
        {   
            block_shift = S,
            block_size  = 1 << block_shift,
            block_mask  = block_size - 1
        };

        typedef T value_type;

        ~pod_bvector();
        pod_bvector();
        pod_bvector(unsigned block_ptr_inc);

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

        void remove_all() { m_size = 0; }
        void clear()      { m_size = 0; }
        void free_all()   { free_tail(0); }
        void free_tail(unsigned size);
        void add(const T& val);
        void push_back(const T& val) { add(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())