00001
00002
00003 #ifndef _FIXED_CAPACITY_VECTOR_H
00004 #define _FIXED_CAPACITY_VECTOR_H
00005
00006 #include "osl/misc/carray.h"
00007 #include "osl/misc/cstdint.h"
00008 #include <algorithm>
00009 #include <cstddef>
00010 #include <cassert>
00011 namespace osl
00012 {
00013 namespace misc
00014 {
00015 template <typename T, size_t Capacity>
00016 class FixedCapacityVector
00017 {
00018 protected:
00019 typedef CArray<T, Capacity> array_t;
00020 CArray<int64_t, (sizeof(T[Capacity])+sizeof(int64_t)-1)/sizeof(int64_t)> relements;
00021 size_t index;
00022 private:
00023 const array_t &elements() const{
00024 return *reinterpret_cast<const array_t*>(&relements);
00025 }
00026 array_t &elements(){
00027 return *reinterpret_cast<array_t*>(&relements);
00028 }
00029 public:
00030 typedef typename array_t::iterator iterator;
00031 typedef typename array_t::const_iterator const_iterator;
00032
00033 FixedCapacityVector() : index(0) {}
00034 ~FixedCapacityVector()
00035 {
00036 std::_Destroy(begin(),end());
00037 }
00038 FixedCapacityVector(FixedCapacityVector const& rhs){
00039 index=rhs.size();
00040 std::uninitialized_copy(rhs.begin(),rhs.end(),begin());
00041 }
00042 FixedCapacityVector& operator=(FixedCapacityVector const& rhs){
00043 if (this == &rhs)
00044 return *this;
00045
00046 if(size()>rhs.size()){
00047 iterator it=std::copy(rhs.begin(),rhs.end(),begin());
00048 std::_Destroy(it,end());
00049 }
00050 else{
00051 iterator it=std::copy(&(rhs.elements()[0]),
00052 &(rhs.elements()[size()]),begin());
00053 std::uninitialized_copy(&(rhs.elements()[size()]),
00054 &(rhs.elements()[rhs.size()]),it);
00055 }
00056 index=rhs.size();
00057 return *this;
00058 }
00059
00060 T& operator[] (size_t i)
00061 {
00062 assert(i < size());
00063 return elements()[i];
00064 }
00065
00066 iterator begin() { return &elements()[0]; }
00067 iterator end() { return &elements()[0]+index; }
00068
00069 T& front() { return *begin(); }
00070 T& back() { return *(end() - 1); }
00071
00072 void push_back(const T& e)
00073 {
00074 assert(index < Capacity);
00075 std::_Construct(&elements()[index++],e);
00076 }
00077 template <class RangeIterator>
00078 void push_back(const RangeIterator& first, const RangeIterator& last);
00079 void pop_back() {
00080 std::_Destroy(&elements().elements[index]);
00081 --index;
00082 }
00083
00084 void clear() {
00085 std::_Destroy(begin(),end());
00086 index = 0;
00087 }
00088
00089 void erase(const T& e)
00090 {
00091 const iterator new_end = std::remove(begin(), end(), e);
00092 std::_Destroy(new_end,end());
00093 index -= (end() - new_end);
00094 }
00095
00097 void unique()
00098 {
00099 std::sort(begin(),end());
00100 iterator last = std::unique(begin(), end());
00101 std::_Destroy(last,end());
00102 index = (last - begin());
00103 }
00104
00105 size_t size() const { return index; }
00106 bool empty() const { return size() == 0; }
00107 size_t capacity() const { return Capacity; }
00108
00109 T const& operator[] (size_t i) const
00110 {
00111 assert(i < size());
00112 return elements()[i];
00113 }
00114 const_iterator begin() const { return &elements()[0]; }
00115 const_iterator end() const { return &elements()[0]+index; }
00116
00117 const T& front() const { return *begin(); }
00118 const T& back() const { return *(end() - 1); }
00119
00120 bool isMember(const T& e, const_iterator first, const_iterator last) const
00121 {
00122 return std::find(first, last, e) != last;
00123 }
00124 bool isMember(const T& e) const
00125 {
00126 return isMember(e, begin(), end());
00127 }
00128 };
00129 template <typename T, size_t C> inline
00130 bool operator==(const FixedCapacityVector<T,C>& l, const FixedCapacityVector<T,C>& r)
00131 {
00132 return l.size() == r.size() && std::equal(l.begin(), l.end(), r.begin());
00133 }
00134 }
00135 using misc::FixedCapacityVector;
00136 }
00137
00138 template <typename T, size_t Capacity>
00139 template <class RangeIterator>
00140 void osl::misc::FixedCapacityVector<T,Capacity>::push_back(const RangeIterator& first, const RangeIterator& last)
00141 {
00142 iterator insert_point = end();
00143 index += (last - first);
00144 assert(index <= Capacity);
00145 std::uninitialized_copy(first, last, insert_point);
00146 }
00147
00148
00149 #endif
00150
00151
00152
00153