libDAI
spvector.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  * Copyright (C) 2010 Vicenç Gomez [v dot gomez at science dot ru dot nl]
9  * Copyright (C) 2010 Radboud University Nijmegen, The Netherlands
10  */
11 
12 
15 
16 
17 #ifndef __defined_libdai_spvector_h
18 #define __defined_libdai_spvector_h
19 
20 
21 #include <ostream>
22 #include <vector>
23 
24 
25 namespace dai {
26 
27 
29 template <typename T1, typename T2>
30 struct first_less : public std::binary_function<const std::pair<T1,T2> &, const std::pair<T1,T2> &, bool> {
31  bool operator()( const std::pair<T1,T2> &a, const std::pair<T1,T2> &b ) { return a.first < b.first; }
32 };
33 
34 
35 template <typename T>
36 class spvector {
37  public:
39  typedef std::pair<size_t, T> nondefault_type;
40 
42  typedef std::vector<nondefault_type> nondefaults_type;
43 
44  private:
46 
48  nondefaults_type _p;
50  size_t _size;
52  T _def;
53 
54  public:
56 
57 
58  spvector() : _p(), _size(0), _def(T()) {}
59 
61  explicit spvector( size_t n, T p ) : _p(), _size(n), _def(p) {}
62 
64 
72  template <typename TIterator>
73  spvector( TIterator begin, TIterator end, size_t sizeHint, T def=T() ) : _p(), _size(0), _def(def) {
74  if( sizeHint )
75  reserve( sizeHint );
76  size_t iter = 0;
77  for( TIterator it = begin; it != end; it++, iter++ )
78  if( *it != def )
79  push_back( iter, *it );
80  _size = iter;
81  }
82 
84 
91  template <typename S>
92  spvector( const std::vector<S> &v, size_t sizeHint, T def=T() ) : _p(), _size(v.size()), _def(def) {
93  if( sizeHint )
94  reserve( sizeHint );
95  for( size_t i = 0; i < v.size(); i++ )
96  if( v[i] != def )
97  push_back( i, v[i] );
98  }
100 
102 
103 
104  typedef typename nondefaults_type::const_iterator const_iterator;
106  typedef typename nondefaults_type::iterator iterator;
108  typedef typename nondefaults_type::const_reverse_iterator const_reverse_iterator;
110  typedef typename nondefaults_type::reverse_iterator reverse_iterator;
111 
113  iterator begin() { return _p.begin(); }
115  const_iterator begin() const { return _p.begin(); }
116 
118  iterator end() { return _p.end(); }
120  const_iterator end() const { return _p.end(); }
121 
123  reverse_iterator rbegin() { return _p.rbegin(); }
125  const_reverse_iterator rbegin() const { return _p.rbegin(); }
126 
128  reverse_iterator rend() { return _p.rend(); }
130  const_reverse_iterator rend() const { return _p.rend(); }
132 
134 
135 
136  void reserve( size_t n ) { _p.reserve( n ); }
137 
139  size_t size() const { return _size; }
140 
142  void resize( size_t n ) {
143  _size = n;
144  if( _p.size() ) {
145  if( _p.back().first >= n ) {
146  iterator it = lower_bound( _p.begin(), _p.end(), std::make_pair(n, T()), first_less<size_t, T>() );
147  _p.resize( distance( _p.begin(), it ) );
148  }
149  }
150  }
151 
153  iterator erase( iterator position ) {
154  return _p.erase( position );
155  }
157 
159  void push_back( size_t idx, T val ) { _p.push_back( std::make_pair( idx, val ) ); }
160 
162  void setDefault( T def ) { _def = def; }
163 
165  T getDefault() const { return _def; }
166 
168  void clearNonDef() { _p.clear(); }
169 
171  void set( size_t i, T val ) {
172  DAI_DEBASSERT( i < _size );
173  iterator it = lower_bound( _p.begin(), _p.end(), std::make_pair(i, T()), first_less<size_t, T>() );
174  if( (it != _p.end()) && (it->first == i) ) {
175  // nondefault value already present
176  if( val == _def )
177  _p.erase( it );
178  else
179  it->second = val;
180  } else {
181  // no nondefault value present yet
182  if( val == _def )
183  ; // do nothing
184  else
185  _p.insert( it, std::make_pair(i, val) );
186  }
187  }
188 
190  T get( size_t i ) const {
191  DAI_DEBASSERT( i < _size );
192  const_iterator it = lower_bound( _p.begin(), _p.end(), std::make_pair(i, T()), first_less<size_t, T>() );
193  if( (it != _p.end()) && (it->first == i) )
194  return it->second;
195  else
196  return _def;
197  }
198 
200  T operator[]( size_t i ) const { return get(i); }
201 
203  bool operator==( const spvector<T>& q ) const {
204  if( size() != q.size() )
205  return false;
206  // OPTIMIZE
207  for( size_t i = 0; i < size(); i++ )
208  if( !(get(i) == q.get(i)) )
209  return false;
210  return true;
211  }
212 
214  size_t nrNonDef() const { return _p.size(); }
215 
217  size_t nrDef() const { return _size - _p.size(); }
218 
220  T def() const { return _def; }
221 
223  void setDef( T def ) { _def = def; }
224 
226  const nondefaults_type & nonDef() const { return _p; }
227 };
228 
229 
231 template<class T>
232 std::ostream& operator << (std::ostream& os, const spvector<T> &x) {
233  os << "(";
234  os << "size:" << x.size();
235  os << ", def:" << x.def();
236  for( typename spvector<T>::const_iterator it = x.begin(); it != x.end(); it++ )
237  os << ", " << it->first << ":" << it->second;
238  os << ")";
239  return os;
240 }
241 
242 
243 } // end of namespace dai
244 
245 
246 #endif