19 #ifndef __TPIE_PACKED_ARRAY_H__
20 #define __TPIE_PACKED_ARRAY_H__
22 #include <tpie/config.h>
40 template <
typename CT,
bool forward,
typename RT>
43 CT &
self() {
return *
reinterpret_cast<CT*
>(
this);}
47 const CT &
self()
const {
return *
reinterpret_cast<const CT*
>(
this);}
49 typedef ptrdiff_t difference_type;
50 typedef std::random_access_iterator_tag iterator_category;
51 template <
typename TT>
52 bool operator==(
const TT & o)
const {
return (
self()-o) == 0;}
53 template <
typename TT>
54 bool operator!=(
const TT & o)
const {
return (
self()-o) != 0;}
55 CT & operator++() {
self().index() += forward?1:-1;
return self();}
56 CT operator++(
int) {CT x=
self(); ++
self();
return x;}
57 CT & operator--() {
self().index() += forward?-1:1;
return self();}
58 CT operator--(
int) {CT x=
self(); --
self();
return x;}
59 bool operator<(
const CT & o)
const {
return (
self()-o) < 0;}
60 bool operator>(
const CT & o)
const {
return (
self()-o) > 0;}
61 bool operator<=(
const CT & o)
const {
return (
self()-o) <= 0;}
62 bool operator>=(
const CT & o)
const {
return (
self()-o) >= 0;}
63 ptrdiff_t operator-(
const CT & o)
const {
return forward ? (
self().index() - o.index()) : (o.index() -
self().index());}
64 CT operator+(difference_type n)
const {CT x=
self();
return x += n;}
65 CT operator-(difference_type n)
const {CT x=
self();
return x -= n;}
66 CT & operator+=(difference_type n) {
self().index() += (forward?n:-n);
return self();}
67 CT & operator-=(difference_type n) {
self().index() += (forward?n:-n);
return self();}
68 RT operator[](difference_type n) {
return *(
self() + n);}
71 template <
typename CT,
bool f,
typename RT>
88 template <
typename T,
int B>
91 typedef size_t storage_type;
94 static_assert(
sizeof(storage_type) * 8 % B == 0,
"Bad storrage");
99 static size_t perword() {
100 return sizeof(storage_type) * 8 / B;
106 static size_t high(
size_t index) {
107 return index/perword();
113 static size_t low(
size_t index) {
114 return B*(index%perword());
120 static size_t words(
size_t m) {
121 return (perword()-1+m)/perword();
127 static storage_type mask() {
131 template <
bool forward>
132 class const_iter_base;
134 template <
bool forward>
142 class iter_return_type {
144 iter_return_type(storage_type * e,
size_t i): elms(e), index(i) {}
149 operator T()
const {
return static_cast<T
>((elms[high(index)] >> low(index))&mask());}
150 iter_return_type &
operator=(
const T b) {
151 storage_type * p = elms+high(index);
152 size_t i = low(index);
153 *p = (*p & ~(mask()<<i)) | ((b & mask()) << i);
163 template <
bool forward>
166 iter_return_type elm;
168 friend class const_iter_base<forward>;
171 iter_base(storage_type * elms,
size_t index): elm(elms, index) {};
173 size_t & index() {
return elm.index;}
174 const size_t & index()
const {
return elm.index;}
177 typedef iter_return_type & reference;
178 typedef iter_return_type * pointer;
180 iter_return_type & operator*() {
return elm;}
181 iter_return_type * operator->() {
return &elm;}
182 iter_base &
operator=(
const iter_base & o) {elm.index = o.elm.index; elm.elms=o.elm.elms;
return *
this;}
183 iter_base(iter_base
const &o): elm(o.elm) {};
192 template <
bool forward>
195 const storage_type * elms;
199 friend class boost::iterator_core_access;
201 const_iter_base(
const storage_type * e,
size_t i): elms(e), idx(i) {}
203 size_t & index() {
return idx;}
204 const size_t & index()
const {
return idx;}
207 typedef vssucks reference;
208 typedef vssucks * pointer;
210 const_iter_base &
operator=(
const const_iter_base & o) {idx = o.idx; elms=o.elms;
return *
this;}
211 vssucks operator*()
const {
return static_cast<T
>(elms[high(idx)] >> low(idx) & mask());}
212 const_iter_base(const_iter_base
const& o): elms(o.elms), idx(o.idx) {}
213 const_iter_base(iter_base<forward>
const& o): elms(o.elm.elms), idx(o.elm.index) {}
226 return_type(storage_type * p_,
size_t i_): p(p_), i(i_) {}
229 operator T()
const {
return static_cast<T
>((*p >> i) & mask());}
231 *p = (*p & ~(mask()<<i)) | ((
static_cast<const storage_type
>(b) & mask()) << i);
234 return_type &
operator=(
const return_type & t){
240 storage_type * m_elements;
281 return (
double)
sizeof(
packed_array)+(
double)
sizeof(storage_type);
311 a.m_elements =
nullptr;
329 for(
size_t i=0;i<words(m_size);++i)
330 m_elements[i] = a.m_elements[i];
340 std::swap(m_elements, a.m_elements);
341 std::swap(m_size, a.m_size);
354 if (s == m_size)
return;
357 m_elements = m_size?tpie_new_array<storage_type>(words(m_size)):
nullptr;
367 for (
size_t i=0; i < perword(); ++i)
368 x = (x << B) + ((storage_type)value & mask());
369 for (
size_t i=0; i < words(m_size); ++i)
392 size_t size()
const {
return m_size;}
399 bool empty()
const {
return m_size ==0;}
409 return static_cast<T
>((m_elements[high(t)] >> low(t))&mask());
420 return return_type(m_elements+high(t), low(t));
478 std::swap(m_elements, o.m_elements);
479 std::swap(m_size, o.m_size);
486 template <
typename T,
int B>
491 #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.
void swap(packed_array &o)
Swap two arrays.
bool empty() const
Check if the array is empty.
void fill(T value)
Fill the entier array with the given value.
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.
Miscellaneous utility functions.
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.
packed_array & operator=(packed_array &&a)
Move another array.
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.
packed_array(packed_array &&a)
Move another aray into me.
void tpie_delete_array(T *a, size_t size)
Delete an array allocated with tpie_new_array.