Go to the documentation of this file.00001
00011
00012
00013
00014 #pragma once
00015
00016 #include <stdlib.h>
00017 #include <string.h>
00018 #include <mlist.h>
00019
00021 typedef unsigned int uint ;
00023 typedef const uint cuint ;
00024
00026 #define INITIAL_MVECTOR_SIZE ((uint)1024)
00027
00028
00029
00030
00032 template< typename Data > class mvector
00033
00034 {
00035
00036 public :
00038 mvector() : _data((Data*)NULL), _allocated_size(0), _used_size(0) {} ;
00039
00041 ~mvector() { clear() ; }
00042
00043
00044
00045
00046
00047 public :
00049 void clear() { free(_data) ; _data = (Data*)NULL ; _allocated_size = 0 ; _used_size = 0 ; _deleted.clear() ; }
00050
00052 bool reserve( uint n )
00053 {
00054 if( n < INITIAL_MVECTOR_SIZE ) n = INITIAL_MVECTOR_SIZE ;
00055 if( n <= _allocated_size ) return true ;
00056
00057 Data *temp = _data ;
00058 _data = (Data*)malloc( n*sizeof(Data) ) ;
00059 if( temp ) memcpy( _data, temp, _used_size*sizeof(Data) ) ;
00060 memset( _data + _used_size, 0, (n-_used_size)*sizeof(Data) ) ;
00061 free( temp ) ;
00062
00063 _allocated_size = n ;
00064 return _data != (Data*)NULL ;
00065 }
00066
00068 bool reserve_more( uint n )
00069 {
00070 if( _used_size + n > _allocated_size + _deleted.size() )
00071 {
00072 uint new_size = 2*_allocated_size ;
00073 if( new_size < _used_size + n ) new_size = _used_size + n ;
00074
00075 return reserve( new_size ) ;
00076 }
00077 return true ;
00078 }
00079
00081 bool allocate_more( uint n )
00082 {
00083 if( !reserve_more( n ) ) return false ;
00084 _used_size += n ;
00085 return true ;
00086 }
00087
00089 Data &add( uint &id )
00090 {
00091 if( _deleted.empty() )
00092 {
00093 id = _used_size ;
00094 allocate_more( 1 ) ;
00095 }
00096 else
00097 {
00098 id = _deleted.first() ;
00099 _deleted.remove_first() ;
00100 }
00101 return at(id) ;
00102 }
00103
00105 bool remove( uint id )
00106 {
00107 if( id+1 == _used_size )
00108 --_used_size ;
00109 else
00110 _deleted.insert(id) ;
00111 return true ;
00112 }
00113
00114
00115
00116
00117 public :
00119 uint size() { return _used_size - _deleted.size() ; }
00120
00122 uint used_size() { return _used_size ; }
00123
00125 const Data &at( uint id ) const { return _data[id] ; }
00127 Data &at( uint id ) { return _data[id] ; }
00128
00130 const Data &operator[]( uint id ) const { return at(id) ; }
00132 Data &operator[]( uint id ) { return at(id) ; }
00133
00135 Data *operator +( uint id ) { return _data + id ; }
00136
00138 bool is_valid( uint id ) { return (id < size() && id>=0) ; }
00139
00141 bool is_deleted( uint id ) { return is_valid(id) && _deleted.find(id) () ; }
00142
00143
00144
00145
00146 private :
00148 Data *_data ;
00149
00151 uint _allocated_size ;
00152
00154 uint _used_size ;
00155
00157 List<uint> _deleted ;
00158
00159
00160
00161
00162 public :
00164 class iterator
00165 {
00166 public :
00167
00169 iterator( mvector<Data> &vec_, uint id_ = 0 ) : _vec(vec_), _id(id_) {}
00170
00172 ~iterator() {}
00173
00175 iterator( const iterator &it ) : _vec(it._vec), _id(it._id) {}
00176
00178 iterator &operator = ( const iterator &it )
00179 { _vec = it._vec; _id = it._id; return *this; }
00180
00181
00182
00183 public :
00185 inline bool operator ==( const iterator &it ) const { return &_vec == &it._vec && _id == it._id ; }
00187 inline bool operator !=( const iterator &it ) const { return &_vec != &it._vec || _id != it._id ; }
00188
00190 inline bool operator ()() const { return _vec.is_valid( _id ) ; }
00191
00193 inline uint id () const { return _id ; }
00194
00196 inline const Data &operator * () const { return _vec[_id] ; }
00197
00199 inline Data &operator * () { return _vec[_id] ; }
00200
00202 inline iterator &operator ++() { do ++_id ; while( _vec.is_valid(_id) && _vec.is_deleted(_id) ) ; return *this ; }
00203
00204
00205
00206 private :
00207 mvector<Data> &_vec ;
00208 uint _id ;
00209 };
00210
00211
00212
00213 public :
00215 class const_iterator
00216 {
00217 public :
00218
00220 const_iterator( const mvector<Data> &vec_, uint id_ = 0 ) : _vec(vec_), _id(id_) {}
00221
00223 ~const_iterator() {}
00224
00225
00226
00227 public :
00229 inline bool operator ==( const const_iterator &it ) const { return &_vec == &it._vec && _id == it._id ; }
00231 inline bool operator !=( const const_iterator &it ) const { return &_vec != &it._vec || _id != it._id ; }
00232
00234 inline bool operator ()() const { return _vec.is_valid( _id ) ; }
00235
00237 inline uint id () const { return _id ; }
00238
00240 inline const Data &operator * () const { return _vec[_id] ; }
00241
00243 inline const_iterator &operator ++() { do ++_id ; while( _vec.is_valid(_id) && _vec.is_deleted(_id) ) ; return *this ; }
00244
00245
00246
00247 private :
00248 const mvector<Data> &_vec ;
00249 uint _id ;
00250 };
00251
00252 public :
00254 iterator begin( uint id = 0 ) { return iterator( *this, id ) ; }
00256 const_iterator cbegin( uint id = 0 ) { return const_iterator( *this, id ) ; }
00257
00258 };
00259
00260
00261