18cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd/** 28cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @file sparse_array.h 38cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Auto-expanding sparse array type 48cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 58cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Copyright 2007 OProfile authors 68cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Copyright (c) International Business Machines, 2007. 78cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @remark Read the file COPYING 88cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * 98cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * @author Dave Nomura <dcnltc@us.ibm.com> 108cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 118cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 128cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#ifndef SPARSE_ARRAY_H 138cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#define SPARSE_ARRAY_H 148cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 158cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddtemplate <typename I, typename T> class sparse_array { 168cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddpublic: 178cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef std::map<I, T> container_type; 188cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typedef typename container_type::size_type size_type; 198cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 208cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 218cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Index into the map for a value. 228cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * NOTE: since std::map does/can not have a const member function for 238cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * operator[], this const member function simply returns 0 for 248cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * profile classes that aren't represented in the map. 258cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * This member function will only be invoked for queries of the 268cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * sparse array. 278cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 288cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd T operator[](size_type index) const { 298cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it = container.find(index); 308cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (it != container.end()) 318cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return it->second; 328cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd else 338cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return 0; 348cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 358cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 368cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 378cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 388cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * Index into the vector for a value. If the index is larger than 398cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * the current max index, a new array entry is created. 408cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 418cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd T & operator[](size_type index) { 428cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return container[index]; 438cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 448cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 458cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 468cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 478cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * vectorized += operator 488cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 498cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sparse_array & operator+=(sparse_array const & rhs) { 508cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it = rhs.container.begin(); 518cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it_end = rhs.container.end(); 528cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for ( ; it != it_end; it++) 538cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container[it->first] += it->second; 548cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 558cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return *this; 568cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 578cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 588cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 598cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 608cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * vectorized -= operator, overflow shouldn't occur during substraction 618cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * (iow: for each components lhs[i] >= rhs[i] 628cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 638cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd sparse_array & operator-=(sparse_array const & rhs) { 648cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it = rhs.container.begin(); 658cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it_end = rhs.container.end(); 668cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for ( ; it != it_end; it++) 678cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container[it->first] -= it->second; 688cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 698cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return *this; 708cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 718cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 728cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 738cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /** 748cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * return the maximum index of the array + 1 or 0 if the array 758cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd * is empty. 768cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd */ 778cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd size_type size() const { 788cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (container.size() == 0) 798cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return 0; 808cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator last = container.end(); 818cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd --last; 828cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return last->first + 1; 838cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 848cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 858cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 868cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd /// return true if all elements have the default constructed value 878cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd bool zero() const { 888cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it = container.begin(); 898cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd typename container_type::const_iterator it_end = container.end(); 908cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd for ( ; it != it_end; it++) 918cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd if (it->second != 0) 928cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return false; 938cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd return true; 948cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd } 958cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 968cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Doddprivate: 978cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd container_type container; 988cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd}; 998cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd 1008cfa702f803c5ef6a2b062a489a1b2cf66b45b5eMike Dodd#endif // SPARSE_ARRAY_H 101