18cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/** 28cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @file growable_vector.h 38cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Auto-expanding vector type 48cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 58cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Copyright 2002 OProfile authors 68cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Read the file COPYING 78cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 88cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @author John Levon 98cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @author Philippe Elie 108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#ifndef GROWABLE_VECTOR_H 138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#define GROWABLE_VECTOR_H 148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <vector> 168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <algorithm> 178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#include <functional> 188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/** 208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * A simple growable vector template. 218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddtemplate <typename T> class growable_vector { 238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddpublic: 248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef std::vector<T> container_type; 258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef typename container_type::size_type size_type; 268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Index into the vector for a value. An out of 308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * bounds index will return a default-constructed value. 318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd T operator[](size_type index) const { 338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (index >= container.size()) 348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return T(); 358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return container[index]; 368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Index into the vector for a value. If the index is larger than 418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * the current max index, the array is expanded, default-filling 428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * any intermediary gaps. 438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd T & operator[](size_type index) { 458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (index >= container.size()) 468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container.resize(index + 1); 478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return container[index]; 488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * vectorized += operator 538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd growable_vector<T> & operator+=(growable_vector<T> const & rhs) { 558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (rhs.container.size() > container.size()) 568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container.resize(rhs.container.size()); 578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd size_type min_size = min(container.size(), rhs.container.size()); 598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (size_type i = 0 ; i < min_size; ++i) 608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container[i] += rhs.container[i]; 618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return *this; 638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * vectorized -= operator, overflow shouldn't occur during substraction 688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * (iow: for each components lhs[i] >= rhs[i] 698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd growable_vector<T> & operator-=(growable_vector<T> const & rhs) { 718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (rhs.container.size() > container.size()) 728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container.resize(rhs.container.size()); 738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd size_type min_size = min(container.size(), rhs.container.size()); 758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for (size_type i = 0 ; i < min_size; ++i) 768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container[i] -= rhs.container[i]; 778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return *this; 798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// return current size of vector 838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd size_type size() const { 848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return container.size(); 858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// fill container with given value 898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd void fill(size_type size, T const & value) { 908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container.resize(size, value); 918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// return true if all elements have the default constructed value 958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd bool zero() const { 968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return std::find_if(container.begin(), container.end(), 978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd std::bind2nd(std::not_equal_to<T>(), T())) 988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd == container.end(); 998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 1008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1018cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddprivate: 1028cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container_type container; 1038cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd}; 1048cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1058cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#endif // GROWABLE_VECTOR_H 106