libDAI
spvector_map.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * libDAI is licensed under the terms of the GNU General Public License version
4  * 2, or (at your option) any later version. libDAI is distributed without any
5  * warranty. See the file COPYING for more details.
6  *
7  * Copyright (C) 2010 Joris Mooij [joris dot mooij at libdai dot org]
8  */
9 
10 
13 
14 
15 #ifndef __defined_libdai_spvector_map_h
16 #define __defined_libdai_spvector_map_h
17 
18 
19 #include <ostream>
20 #include <vector>
21 
22 
23 namespace dai {
24 
25 
26 template <typename T>
27 class spvector_map {
28  public:
30  typedef std::pair<size_t, T> nondefault_type;
31 
33  typedef std::map<size_t, T> nondefaults_type;
34 
35  private:
37  nondefaults_type _p;
39  size_t _size;
41  T _def;
42 
43  public:
45 
46 
47  spvector_map() : _p(), _size(0), _def(T()) {}
48 
50  explicit spvector_map( size_t n, T p ) : _p(), _size(n), _def(p) {}
51 
53 
61  template <typename TIterator>
62  spvector_map( TIterator begin, TIterator end, size_t sizeHint, T def=T() ) : _p(), _size(0), _def(def) {
63  if( sizeHint )
64  reserve( sizeHint );
65  size_t iter = 0;
66  for( TIterator it = begin; it != end; it++, iter++ )
67  if( *it != def )
68  push_back( iter, *it );
69  _size = iter;
70  }
71 
73 
80  template <typename S>
81  spvector_map( const std::vector<S> &v, size_t sizeHint, T def=T() ) : _p(), _size(v.size()), _def(def) {
82  if( sizeHint )
83  reserve( sizeHint );
84  for( size_t i = 0; i < v.size(); i++ )
85  if( v[i] != def )
86  push_back( i, v[i] );
87  }
89 
91 
92 
93  typedef typename nondefaults_type::const_iterator const_iterator;
95  typedef typename nondefaults_type::iterator iterator;
97  typedef typename nondefaults_type::const_reverse_iterator const_reverse_iterator;
99  typedef typename nondefaults_type::reverse_iterator reverse_iterator;
100 
102  iterator begin() { return _p.begin(); }
104  const_iterator begin() const { return _p.begin(); }
105 
107  iterator end() { return _p.end(); }
109  const_iterator end() const { return _p.end(); }
110 
112  reverse_iterator rbegin() { return _p.rbegin(); }
114  const_reverse_iterator rbegin() const { return _p.rbegin(); }
115 
117  reverse_iterator rend() { return _p.rend(); }
119  const_reverse_iterator rend() const { return _p.rend(); }
121 
123 
124 
125  void reserve( size_t /*n*/ ) {}
126 
128  size_t size() const { return _size; }
129 
131  void resize( size_t n ) {
132  _size = n;
133  if( _p.size() ) {
134  for( iterator it = begin(); it != end(); ) {
135  if( it->first >= n )
136  _p.erase( it++ );
137  else
138  it++;
139  }
140  }
141  }
142 
144  iterator erase( iterator position ) {
145  iterator next = position;
146  next++;
147  _p.erase( position );
148  return next;
149  }
151 
153  void push_back( size_t idx, T val ) { _p[idx] = val; }
154 
156  void setDefault( T def ) { _def = def; }
157 
159  T getDefault() const { return _def; }
160 
162  void clearNonDef() { _p.clear(); }
163 
165  void set( size_t i, T val ) {
166  DAI_DEBASSERT( i < _size );
167  if( val != _def )
168  _p[i] = val;
169  else
170  _p.erase( i );
171  }
172 
174  T get( size_t i ) const {
175  DAI_DEBASSERT( i < _size );
176  const_iterator it = _p.find( i );
177  if( it != _p.end() )
178  return it->second;
179  else
180  return _def;
181  }
182 
184  T operator[]( size_t i ) const { return get(i); }
185 
187  bool operator==( const spvector_map<T>& q ) const {
188  if( size() != q.size() )
189  return false;
190  // OPTIMIZE
191  for( size_t i = 0; i < size(); i++ )
192  if( !(get(i) == q.get(i)) )
193  return false;
194  return true;
195  }
196 
198  size_t nrNonDef() const { return _p.size(); }
199 
201  size_t nrDef() const { return _size - _p.size(); }
202 
204  T def() const { return _def; }
205 
207  void setDef( T def ) { _def = def; }
208 
210  const nondefaults_type & nonDef() const { return _p; }
211 };
212 
213 
215 template<class T>
216 std::ostream& operator << (std::ostream& os, const spvector_map<T> &x) {
217  os << "(";
218  os << "size:" << x.size();
219  os << ", def:" << x.def();
220  for( typename spvector_map<T>::const_iterator it = x.begin(); it != x.end(); it++ )
221  os << ", " << it->first << ":" << it->second;
222  os << ")";
223  return os;
224 }
225 
226 
227 } // end of namespace dai
228 
229 
230 #endif