19 #ifndef __TPIE_PACKED_ARRAY_H__
20 #define __TPIE_PACKED_ARRAY_H__
22 #include <tpie/config.h>
23 #include <boost/static_assert.hpp>
38 template <
typename CT,
bool forward,
typename RT>
41 CT &
self() {
return *
reinterpret_cast<CT*
>(
this);}
45 const CT &
self()
const {
return *
reinterpret_cast<const CT*
>(
this);}
47 typedef ptrdiff_t difference_type;
48 typedef std::random_access_iterator_tag iterator_category;
49 template <
typename TT>
50 inline bool operator==(
const TT & o)
const {
return (
self()-o) == 0;}
51 template <
typename TT>
52 inline bool operator!=(
const TT & o)
const {
return (
self()-o) != 0;}
53 inline CT & operator++() {
self().index() += forward?1:-1;
return self();}
54 inline CT operator++(
int) {CT x=
self(); ++
self();
return x;}
55 inline CT & operator--() {
self().index() += forward?-1:1;
return self();}
56 inline CT operator--(
int) {CT x=
self(); --
self();
return x;}
57 inline bool operator<(
const CT & o)
const {
return (
self()-o) < 0;}
58 inline bool operator>(
const CT & o)
const {
return (
self()-o) > 0;}
59 inline bool operator<=(
const CT & o)
const {
return (
self()-o) <= 0;}
60 inline bool operator>=(
const CT & o)
const {
return (
self()-o) >= 0;}
61 inline ptrdiff_t operator-(
const CT & o)
const {
return forward ? (
self().index() - o.index()) : (o.index() -
self().index());}
62 inline CT operator+(difference_type n)
const {CT x=
self();
return x += n;}
63 inline CT operator-(difference_type n)
const {CT x=
self();
return x -= n;}
64 inline CT & operator+=(difference_type n) {
self().index() += (forward?n:-n);
return self();}
65 inline CT & operator-=(difference_type n) {
self().index() += (forward?n:-n);
return self();}
66 inline RT operator[](difference_type n) {
return *(
self() + n);}
69 template <
typename CT,
bool f,
typename RT>
86 template <
typename T,
int B>
89 typedef size_t storage_type;
92 BOOST_STATIC_ASSERT(
sizeof(storage_type) * 8 % B == 0);
97 static inline size_t perword() {
98 return sizeof(storage_type) * 8 / B;
104 static inline size_t high(
size_t index) {
105 return index/perword();
111 static inline size_t low(
size_t index) {
112 return B*(index%perword());
118 static inline size_t words(
size_t m) {
119 return (perword()-1+m)/perword();
125 static inline storage_type mask() {
129 template <
bool forward>
130 class const_iter_base;
132 template <
bool forward>
140 class iter_return_type {
142 iter_return_type(storage_type * e,
size_t i): elms(e), index(i) {}
146 template <
bool>
friend class packed_array::iter_base;
147 template <
bool>
friend class packed_array::const_iter_base;
148 operator T()
const {
return static_cast<T
>((elms[high(index)] >> low(index))&mask());}
149 inline iter_return_type &
operator=(
const T b) {
150 storage_type * p = elms+high(index);
151 size_t i = low(index);
152 *p = (*p & ~(mask()<<i)) | ((b & mask()) << i);
162 template <
bool forward>
165 iter_return_type elm;
167 friend class const_iter_base<forward>;
170 iter_base(storage_type * elms,
size_t index): elm(elms, index) {};
172 inline size_t & index() {
return elm.index;}
173 inline const size_t & index()
const {
return elm.index;}
176 typedef iter_return_type & reference;
177 typedef iter_return_type * pointer;
179 iter_return_type & operator*() {
return elm;}
180 iter_return_type * operator->() {
return &elm;}
181 iter_base &
operator=(
const iter_base & o) {elm.index = o.elm.index; elm.elms=o.elm.elms;
return *
this;}
182 iter_base(iter_base
const &o): elm(o.elm) {};
191 template <
bool forward>
194 const storage_type * elms;
198 friend class boost::iterator_core_access;
200 const_iter_base(
const storage_type * e,
size_t i): elms(e), idx(i) {}
202 inline size_t & index() {
return idx;}
203 inline const size_t & index()
const {
return idx;}
206 typedef vssucks reference;
207 typedef vssucks * pointer;
209 const_iter_base &
operator=(
const const_iter_base & o) {idx = o.idx; elms=o.elms;
return *
this;}
210 vssucks operator*()
const {
return static_cast<T
>(elms[high(idx)] >> low(idx) & mask());}
211 const_iter_base(const_iter_base
const& o): elms(o.elms), idx(o.idx) {}
212 const_iter_base(iter_base<forward>
const& o): elms(o.elm.elms), idx(o.elm.index) {}
225 return_type(storage_type * p_,
size_t i_): p(p_), i(i_) {}
228 inline operator T()
const {
return static_cast<T
>((*p >> i) & mask());}
229 inline return_type &
operator=(
const T b) {
230 *p = (*p & ~(mask()<<i)) | ((
static_cast<const storage_type
>(b) & mask()) << i);
233 inline return_type &
operator=(
const return_type & t){
239 storage_type * m_elements;
280 return (
double)
sizeof(
packed_array)+(
double)
sizeof(storage_type);
319 for(
size_t i=0;i<words(m_size);++i)
320 m_elements[i] = a.m_elements[i];
332 if (s == m_size)
return;
335 m_elements = m_size?tpie_new_array<storage_type>(words(m_size)):0;
349 for (
size_t i=0; i < perword(); ++i)
350 x = (x << B) + ((storage_type)value & mask());
351 for (
size_t i=0; i < words(m_size); ++i)
360 inline size_t size()
const {
return m_size;}
367 inline bool empty()
const {
return m_size ==0;}
377 return static_cast<T
>((m_elements[high(t)] >> low(t))&mask());
388 return return_type(m_elements+high(t), low(t));
444 #endif //__TPIE_PACKED_ARRAY_H__
const_iterator find(size_type i) const
Return a const iterator to the i'th element of the array.
const_iterator begin() const
Return a const iterator to the beginning of the array.
iter_base< true > iterator
Iterator over an array.
const_iter_base< true > const_iterator
Iterator over a const array.
Base class of data structures with linear memory usage.
iterator find(size_type i)
Return an iterator to the i'th element of the array.
void resize(size_t s, T value)
Change the size of the array.
T value_type
Type of values containd in the array.
static double memory_overhead()
Return the memory overhead of the structure.
const_iter_base< false > const_reverse_iterator
Reverse iterator over a const array.
An array storring elements of type T using B bits to to store a element.
iterator begin()
Return an iterator to the beginning of the array.
const_iterator end() const
Return a const iterator to the end of the array.
~packed_array()
Free up all memory used by the array.
void resize(size_t s)
Change the size of the array.
bool empty() const
Check if the array is empty.
packed_array(size_t s, T value)
Construct array of given size.
packed_array(const packed_array &a)
Construct a copy of another array.
static double memory_coefficient()
Return the memory coefficient of the structure.
packed_array & operator=(const packed_array &a)
Copy elements from another array into this.
size_t size() const
Return the size of the array.
return_type operator[](size_t t)
Return a object behaving like a reference to an array entry.
iterator end()
Return an iterator to the end of the array.
T operator[](size_t t) const
Return an array entry.
iter_base< false > reverse_iterator
Reverse iterator over an array.
packed_array(size_t s=0)
Construct array of given size.
Base class for the iterators.
void tpie_delete_array(T *a, size_t size)
Delete an array allocated with tpie_new_array.