summaryrefslogtreecommitdiff
path: root/agg/inc/agg_array.h
diff options
context:
space:
mode:
Diffstat (limited to 'agg/inc/agg_array.h')
-rwxr-xr-xagg/inc/agg_array.h887
1 files changed, 887 insertions, 0 deletions
diff --git a/agg/inc/agg_array.h b/agg/inc/agg_array.h
new file mode 100755
index 000000000000..2970181c4510
--- /dev/null
+++ b/agg/inc/agg_array.h
@@ -0,0 +1,887 @@
+//----------------------------------------------------------------------------
+// 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: mcseem@antigrain.com
+// mcseemagg@yahoo.com
+// 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 continous 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 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_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>
+ const pod_deque<T, S>& pod_deque<T, S>::operator = (const pod_deque<T, S>& v)
+ {
+ unsigned i;
+ for(i = m_num_blocks; i < v.m_num_blocks; ++i)
+ {
+ allocate_block(i);
+ }
+ for(i = 0; i < v.m_num_blocks; ++i)
+ {
+ memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T));
+ }
+ m_size = v.m_size;
+ return *this;
+ }
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ void pod_deque<T, S>::allocate_block(unsigned nb)
+ {
+ if(nb >= m_max_blocks)
+ {
+ T** new_blocks = new T* [m_max_blocks + m_block_ptr_inc];
+
+ if(m_blocks)
+ {
+ memcpy(new_blocks,
+ m_blocks,
+ m_num_blocks * sizeof(T*));
+
+ delete [] m_blocks;
+ }
+ m_blocks = new_blocks;
+ m_max_blocks += m_block_ptr_inc;
+ }
+ m_blocks[nb] = new T [block_size];
+ m_num_blocks++;
+ }
+
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ inline T* pod_deque<T, S>::data_ptr()
+ {
+ unsigned nb = m_size >> block_shift;
+ if(nb >= m_num_blocks)
+ {
+ allocate_block(nb);
+ }
+ return m_blocks[nb] + (m_size & block_mask);
+ }
+
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ inline void pod_deque<T, S>::add(const T& val)
+ {
+ *data_ptr() = val;
+ ++m_size;
+ }
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ inline void pod_deque<T, S>::remove_last()
+ {
+ if(m_size) --m_size;
+ }
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ void pod_deque<T, S>::modify_last(const T& val)
+ {
+ remove_last();
+ add(val);
+ }
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ int pod_deque<T, S>::allocate_continuous_block(unsigned num_elements)
+ {
+ if(num_elements < block_size)
+ {
+ data_ptr(); // Allocate initial block if necessary
+ unsigned rest = block_size - (m_size & block_mask);
+ unsigned index;
+ if(num_elements <= rest)
+ {
+ // The rest of the block is good, we can use it
+ //-----------------
+ index = m_size;
+ m_size += num_elements;
+ return index;
+ }
+
+ // New block
+ //---------------
+ m_size += rest;
+ data_ptr();
+ index = m_size;
+ m_size += num_elements;
+ return index;
+ }
+ return -1; // Impossible to allocate
+ }
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ unsigned pod_deque<T, S>::byte_size() const
+ {
+ return m_size * sizeof(T);
+ }
+
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ void pod_deque<T, S>::serialize(int8u* ptr) const
+ {
+ unsigned i;
+ for(i = 0; i < m_size; i++)
+ {
+ memcpy(ptr, &(*this)[i], sizeof(T));
+ ptr += sizeof(T);
+ }
+ }
+
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ void pod_deque<T, S>::deserialize(const int8u* data, unsigned _byte_size)
+ {
+ remove_all();
+ _byte_size /= sizeof(T);
+ for(unsigned i = 0; i < _byte_size; ++i)
+ {
+ T* ptr = data_ptr();
+ memcpy(ptr, data, sizeof(T));
+ ++m_size;
+ data += sizeof(T);
+ }
+ }
+
+
+ // Replace or add a number of elements starting from "start" position
+ //------------------------------------------------------------------------
+ template<class T, unsigned S>
+ void pod_deque<T, S>::deserialize(unsigned start, const T& empty_val,
+ const int8u* data, unsigned _byte_size)
+ {
+ while(m_size < start)
+ {
+ add(empty_val);
+ }
+
+ _byte_size /= sizeof(T);
+ for(unsigned i = 0; i < _byte_size; ++i)
+ {
+ if(start + i < m_size)
+ {
+ memcpy(&((*this)[start + i]), data, sizeof(T));
+ }
+ else
+ {
+ T* ptr = data_ptr();
+ memcpy(ptr, data, sizeof(T));
+ ++m_size;
+ }
+ data += sizeof(T);
+ }
+ }
+
+
+ //-----------------------------------------------------------pod_allocator
+ // Allocator for arbitrary POD data. Most usable in different cache
+ // systems for efficient memory allocations.
+ // Memory is allocated with blocks of fixed size ("block_size" in
+ // the constructor). If required size exceeds the block size the allocator
+ // creates a new block of the required size. However, the most efficient
+ // use is when the average reqired size is much less than the block size.
+ //------------------------------------------------------------------------
+ class pod_allocator
+ {
+ public:
+ void remove_all()
+ {
+ if(m_num_blocks)
+ {
+ int8u** blk = m_blocks + m_num_blocks - 1;
+ while(m_num_blocks--)
+ {
+ delete [] *blk;
+ --blk;
+ }
+ delete [] m_blocks;
+ }
+ m_num_blocks = 0;
+ m_max_blocks = 0;
+ m_blocks = 0;
+ m_buf_ptr = 0;
+ m_rest = 0;
+ }
+
+ ~pod_allocator()
+ {
+ remove_all();
+ }
+
+ pod_allocator(unsigned block_size, unsigned block_ptr_inc=256-8) :
+ m_block_size(block_size),
+ m_block_ptr_inc(block_ptr_inc),
+ m_num_blocks(0),
+ m_max_blocks(0),
+ m_blocks(0),
+ m_buf_ptr(0),
+ m_rest(0)
+ {
+ }
+
+
+ int8u* allocate(unsigned size, unsigned alignment=1)
+ {
+ if(size == 0) return 0;
+ if(size <= m_rest)
+ {
+ int8u* ptr = m_buf_ptr;
+ if(alignment > 1)
+ {
+ unsigned align = (alignment - unsigned((size_t)ptr) % alignment) % alignment;
+ size += align;
+ ptr += align;
+ if(size <= m_rest)
+ {
+ m_rest -= size;
+ m_buf_ptr += size;
+ return ptr;
+ }
+ allocate_block(size);
+ return allocate(size - align, alignment);
+ }
+ m_rest -= size;
+ m_buf_ptr += size;
+ return ptr;
+ }
+ allocate_block(size + alignment - 1);
+ return allocate(size, alignment);
+ }
+
+
+ private:
+ void allocate_block(unsigned size)
+ {
+ if(size < m_block_size) size = m_block_size;
+ if(m_num_blocks >= m_max_blocks)
+ {
+ int8u** new_blocks = new int8u* [m_max_blocks + m_block_ptr_inc];
+
+ if(m_blocks)
+ {
+ memcpy(new_blocks,
+ m_blocks,
+ m_num_blocks * sizeof(int8u*));
+
+ delete [] m_blocks;
+ }
+ m_blocks = new_blocks;
+ m_max_blocks += m_block_ptr_inc;
+ }
+ m_blocks[m_num_blocks] = m_buf_ptr = new int8u [size];
+ m_num_blocks++;
+ m_rest = size;
+ }
+
+ unsigned m_block_size;
+ unsigned m_block_ptr_inc;
+ unsigned m_num_blocks;
+ unsigned m_max_blocks;
+ int8u** m_blocks;
+ int8u* m_buf_ptr;
+ unsigned m_rest;
+ };
+
+
+
+
+
+
+
+
+ //------------------------------------------------------------------------
+ enum
+ {
+ quick_sort_threshold = 9
+ };
+
+
+ //-----------------------------------------------------------swap_elements
+ template<class T> inline void swap_elements(T& a, T& b)
+ {
+ T temp = a;
+ a = b;
+ b = temp;
+ }
+
+
+ //--------------------------------------------------------------quick_sort
+ template<class Array, class Less>
+ void quick_sort(Array& arr, Less less)
+ {
+ if(arr.size() < 2) return;
+
+ typename Array::value_type* e1;
+ typename Array::value_type* e2;
+
+ int stack[80];
+ int* top = stack;
+ int limit = arr.size();
+ int base = 0;
+
+ for(;;)
+ {
+ int len = limit - base;
+
+ int i;
+ int j;
+ int pivot;
+
+ if(len > quick_sort_threshold)
+ {
+ // we use base + len/2 as the pivot
+ pivot = base + len / 2;
+ swap_elements(arr[base], arr[pivot]);
+
+ i = base + 1;
+ j = limit - 1;
+
+ // now ensure that *i <= *base <= *j
+ e1 = &(arr[j]);
+ e2 = &(arr[i]);
+ if(less(*e1, *e2)) swap_elements(*e1, *e2);
+
+ e1 = &(arr[base]);
+ e2 = &(arr[i]);
+ if(less(*e1, *e2)) swap_elements(*e1, *e2);
+
+ e1 = &(arr[j]);
+ e2 = &(arr[base]);
+ if(less(*e1, *e2)) swap_elements(*e1, *e2);
+
+ for(;;)
+ {
+ do i++; while( less(arr[i], arr[base]) );
+ do j--; while( less(arr[base], arr[j]) );
+
+ if( i > j )
+ {
+ break;
+ }
+
+ swap_elements(arr[i], arr[j]);
+ }
+
+ swap_elements(arr[base], arr[j]);
+
+ // now, push the largest sub-array
+ if(j - base > limit - i)
+ {
+ top[0] = base;
+ top[1] = j;
+ base = i;
+ }
+ else
+ {
+ top[0] = i;
+ top[1] = limit;
+ limit = j;
+ }
+ top += 2;
+ }
+ else
+ {
+ // the sub-array is small, perform insertion sort
+ j = base;
+ i = j + 1;
+
+ for(; i < limit; j = i, i++)
+ {
+ for(; less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--)
+ {
+ swap_elements(*e1, *e2);
+ if(j == base)
+ {
+ break;
+ }
+ }
+ }
+ if(top > stack)
+ {
+ top -= 2;
+ base = top[0];
+ limit = top[1];
+ }
+ else
+ {
+ break;
+ }
+ }
+ }
+ }
+
+
+
+
+ //------------------------------------------------------remove_duplicates
+ // Remove duplicates from a sorted array. It doesn't cut the the
+ // tail of the array, it just returns the number of remaining elements.
+ //-----------------------------------------------------------------------
+ template<class Array, class Equal>
+ unsigned remove_duplicates(Array& arr, Equal equal)
+ {
+ if(arr.size() < 2) return arr.size();
+
+ unsigned i, j;
+ for(i = 1, j = 1; i < arr.size(); i++)
+ {
+ typename Array::value_type& e = arr[i];
+ if(!equal(e, arr[i - 1]))
+ {
+ arr[j++] = e;
+ }
+ }
+ return j;
+ }
+
+
+
+
+}
+
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-18 12:57:42 +0000