1 /* Copyright (C) 2010 LinBox 2 * Written by JG Dumas <Jean-Guillaume.Dumas@imag.fr> 3 * 4 * 5 * ========LICENCE======== 6 * This file is part of the library LinBox. 7 * 8 * LinBox is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with this library; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 * ========LICENCE======== 22 */ 23 24 25 // =================================================================== // 26 // LightContainer : std::vector like container 27 // =================================================================== // 28 29 #ifndef __LINBOX_light_vector_container_H 30 #define __LINBOX_light_vector_container_H 31 32 #include <iostream> 33 #include <cstdlib> 34 #include "linbox/util/contracts.h" 35 #include "linbox/vector/vector-traits.h" 36 37 38 namespace LinBox 39 { 40 41 template<typename Elem> struct LightContainer { 42 private: 43 typedef LightContainer<Elem> Self_t; 44 size_t allocated; 45 Elem * _container; 46 Elem * _finish; 47 public: 48 typedef Elem value_type; 49 typedef Elem* iterator; 50 typedef const Elem* const_iterator; 51 LightContainerLightContainer52 LightContainer() : 53 allocated(2), _container(new Elem[allocated]), _finish(_container) 54 { 55 ENSURE( (allocated == 2) && (size() == 0) ); 56 57 } LightContainerLightContainer58 LightContainer(size_t s) : 59 allocated(s), _container(new Elem[s]), _finish(_container+s) 60 { 61 62 ENSURE( (allocated == s) && (size() == s) ); 63 ENSURE( allocated >= size() ); 64 65 } 66 67 Self_t& operator=(const Self_t& v) 68 { 69 this->resize(v.size()); 70 const_iterator vit = v.begin(); 71 for(iterator tit = begin(); tit != end(); ++tit, ++vit) 72 *tit = *vit; 73 return *this; 74 } 75 LightContainerLightContainer76 LightContainer(const Self_t& v) : 77 allocated(v.allocated) 78 { 79 _container = new Elem[allocated]; 80 _finish = _container +v.size(); 81 const_iterator vit = v.begin(); 82 for(iterator tit = begin(); tit != end(); ++tit, ++vit) 83 *tit = *vit; 84 } 85 reserveLightContainer86 void reserve(size_t s) 87 { 88 STATE( size_t oldsize = size() ); 89 reallocate(s, size() ); 90 ENSURE( (allocated >= s) && (size() == oldsize) && ( allocated >= size() ) ); 91 } 92 sizeLightContainer93 size_t size() const 94 { 95 return size_t(_finish - _container); 96 } 97 98 Elem& operator[](size_t i) 99 { 100 REQUIRE( (i >= 0) && (i < allocated) && (i < size()) ); 101 return _container[i]; 102 } 103 104 const Elem& operator[](size_t i) const 105 { 106 REQUIRE( (i >= 0) && (i < allocated) && (i < size()) ); 107 return _container[i]; 108 } 109 clearLightContainer110 void clear() 111 { 112 _finish = _container; 113 ENSURE( (size() == 0) ); 114 115 } resizeLightContainer116 void resize(size_t s) 117 { 118 if (s>allocated) reallocate( s+(s>>1), s ); 119 else _finish = _container + s; 120 ENSURE( allocated >= size() ); 121 } beginLightContainer122 iterator begin() { return _container; } endLightContainer123 iterator end() { return _finish; } beginLightContainer124 const_iterator begin() const { return const_iterator(_container); } endLightContainer125 const_iterator end() const { return const_iterator(_finish); } frontLightContainer126 Elem& front() { return *_container; } frontLightContainer127 const Elem& front() const { return *_container; } backLightContainer128 Elem& back() { return *(_finish-1); } backLightContainer129 const Elem& back() const { return *(_finish-1); } 130 push_backLightContainer131 void push_back(const Elem& c) 132 { 133 STATE( size_t oldsize = size() ); 134 if (size() == allocated) reserve(allocated+(allocated>>1)); 135 *(_finish) = c; ++_finish; 136 137 ENSURE( size() == (oldsize+1) ); 138 ENSURE( allocated >= size() ); 139 } pop_backLightContainer140 void pop_back() 141 { 142 STATE( size_t oldsize = size() ); 143 REQUIRE( oldsize >= 1 ); 144 --_finish; 145 ENSURE( size() == (oldsize-1) ); 146 ENSURE( allocated >= size() ); 147 } 148 ~LightContainerLightContainer149 ~LightContainer() { delete[] _container; } 150 151 insertLightContainer152 iterator insert(iterator pos, const Elem& c) 153 { 154 REQUIRE( (pos-begin()) <= (end()-begin()) ); 155 REQUIRE( (pos-begin()) >= 0 ); 156 STATE( size_t oldsize = size() ); 157 iterator newpos; 158 if (pos == _finish) { 159 push_back(c); 160 newpos = _finish-1; 161 } 162 else { 163 if (allocated > size()) 164 newpos = insertwithspace(pos,c); 165 else 166 newpos = insertwithrealloc(pos,c); 167 } 168 ENSURE( size() == oldsize+1 ); 169 ENSURE( allocated >= size() ); 170 return newpos; 171 } 172 insertLightContainer173 iterator insert(iterator pos, const_iterator Beg, const_iterator End) 174 { 175 REQUIRE( (pos-begin()) <= (end()-begin()) ); 176 REQUIRE( (pos-begin()) >= 0 ); 177 if (pos == _finish) { 178 for(const_iterator iter=Beg; iter != End; ++iter) 179 push_back(*iter); 180 } 181 else { 182 for(const_iterator iter=Beg; iter != End; ++iter) 183 insert(pos, *iter); 184 } 185 ENSURE( allocated >= size() ); 186 return pos; 187 } 188 189 eraseLightContainer190 iterator erase(iterator pos) 191 { 192 REQUIRE( (pos-begin()) < (end()-begin()) ); 193 REQUIRE( (pos-begin()) >= 0 ); 194 STATE( size_t oldsize = size() ); 195 iterator ppos=pos+1; 196 if ( ppos == _finish) { 197 pop_back(); 198 } 199 else { 200 *(pos)=*(ppos); 201 erase(ppos); 202 } 203 ENSURE( size() == oldsize-1 ); 204 ENSURE( allocated >= size() ); 205 ENSURE( _finish >= _container ); 206 return pos; 207 } 208 eraseLightContainer209 iterator erase(iterator first, iterator last) 210 { 211 REQUIRE( (first-begin()) < (end()-begin()) ); 212 REQUIRE( (last-begin()) <= (end()-begin()) ); 213 REQUIRE( (last-first) > 0 ); 214 REQUIRE( (first-begin()) >= 0 ); 215 STATE( size_t oldsize = size() ); 216 const size_t lmf = last-first; 217 if ( last == _finish) { 218 for(size_t i=0; i<lmf; ++i) pop_back(); 219 } 220 else { 221 iterator nf(first), nl(last); 222 for( ; (nf != last) && (nl != _finish); ++nf, ++nl) 223 *(nf) = *(nl); 224 erase(nf,nl); 225 } 226 ENSURE( size() == oldsize-lmf ); 227 ENSURE( allocated >= size() ); 228 ENSURE( _finish >= _container ); 229 return first; 230 } 231 232 #if 0 233 friend std::ostream& operator<< (std::ostream& o, const Self_t& C) { 234 o << '['; 235 const_iterator refs = C.begin(); 236 for( ; refs != (C.end()-1) ; ++refs ) 237 o << (*refs) << ','; 238 return o << (*refs) << ']'; 239 } 240 friend std::ostream& operator<< (std::ostream& o, const Self_t& C) { 241 o << '['; 242 for(size_t i=0; i<(C.size()-1); ++i) 243 o << C[i] << ','; 244 return o << C[C.size()-1] << ']'; 245 } 246 #endif 247 248 friend std::ostream& operator<< (std::ostream& o, const Self_t& C) 249 { 250 o << '['; 251 for(const_iterator refs = C.begin(); refs != C.end() ; ++refs ) 252 o << (*refs) << ','; 253 return o << ']'; 254 } 255 256 257 258 protected: reallocateLightContainer259 void reallocate(size_t s, size_t endc) 260 { 261 REQUIRE( (s >= endc) ); 262 if (allocated < s) { 263 Elem * futur = new Elem[s]; 264 for(size_t i=0; (i<s) && (i < allocated); ++i) 265 futur[i] = _container[i]; 266 size_t olds = size(); 267 delete [] _container; 268 _container = futur; 269 _finish = _container + olds; 270 allocated = s; 271 } 272 _finish = _container + endc; 273 ENSURE( allocated >= size() ); 274 } 275 insertwithspaceLightContainer276 iterator insertwithspace(iterator pos, const Elem& c) 277 { 278 STATE( size_t oldsize = size() ); 279 STATE( size_t oldalloc = allocated ); 280 REQUIRE( (size()+1) <= allocated ); 281 REQUIRE( (pos-begin()) <= (end()-begin()) ); 282 REQUIRE( (pos-begin()) >= 0 ); 283 if (pos == _finish) { 284 push_back(c); 285 } 286 else { 287 insertwithspace(pos+1, *(pos)); 288 *(pos) = c; 289 } 290 ENSURE( size() == oldsize+1 ); 291 ENSURE( allocated >= size() ); 292 ENSURE( allocated == oldalloc ); 293 return pos; 294 } 295 insertwithreallocLightContainer296 iterator insertwithrealloc(iterator pos, const Elem& c) 297 { 298 REQUIRE( (pos-begin()) <= (end()-begin()) ); 299 REQUIRE( (pos-begin()) >= 0 ); 300 allocated += (allocated>>1); 301 Elem * futur = new Elem[allocated]; 302 iterator newcont = futur; 303 iterator oldcont=_container; 304 for( ; oldcont != pos; ++oldcont,++newcont) 305 *newcont = *oldcont; 306 *newcont = c; 307 iterator newpos = newcont; 308 for(++newcont ; oldcont != _finish; ++oldcont,++newcont) 309 *newcont = *oldcont; 310 size_t olds = size(); 311 delete [] _container; 312 _container = futur; 313 _finish = _container + (++olds); 314 ENSURE( allocated >= size() ); 315 return newpos; 316 } 317 318 319 320 }; 321 322 323 // Specialization for LightContainer 324 template <class Element> 325 struct VectorTraits< LightContainer<Element> > { 326 typedef LightContainer<Element> VectorType; 327 typedef typename VectorCategories::DenseVectorTag VectorCategory; 328 }; 329 330 // Specialization for LightContainer of pairs of size_t and elements 331 template <class Element> 332 struct VectorTraits< LightContainer< std::pair<size_t, Element> > > { 333 typedef LightContainer< std::pair<size_t, Element> > VectorType; 334 typedef typename VectorCategories::SparseSequenceVectorTag VectorCategory; 335 336 static void sort (VectorType& v) { std::stable_sort(v.begin(), v.end(), SparseSequenceVectorPairLessThan<Element>()); } 337 }; 338 339 } // namespace LinBox 340 341 #endif //__LINBOX_light_vector_container_H 342 343 // Local Variables: 344 // mode: C++ 345 // tab-width: 4 346 // indent-tabs-mode: nil 347 // c-basic-offset: 4 348 // End: 349 // vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s 350