This file is indexed.

/usr/include/opengm/datastructures/randomaccessset.hxx is in libopengm-dev 2.3.6+20160905-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
#pragma once
#ifndef OPENGM_RANDOM_ACCESS_SET_HXX
#define OPENGM_RANDOM_ACCESS_SET_HXX

#include <vector>
#include <algorithm>
#include <utility>

namespace opengm {
   
/// set with O(n) insert and O(1) access
///
/// \tparam Key key and value type of the set
/// \tparam Alloc allocator of the set
/// RandomAccessSet has the same interface as std::set.
/// In addition, there is operator[].
/// \warning Values in set must not be changend through the mutable iterator
/// because doing so would potentially change the order of the values
/// \\ingroup datastructures
template<class Key,class Compare=std::less<Key>,class Alloc=std::allocator<Key> >
class RandomAccessSet {
private:
   /// type of the underlying vector
   typedef std::vector<Key,Alloc> VectorType;

public:
   // typedefs
   /// key type of the set
   typedef Key key_type;
   /// value type of the set
   typedef Key ValueType;
   /// value type of the set
   typedef Key value_type;
   /// comperator
   typedef Compare key_compare;
   /// value comperator
   typedef Compare value_compare;
   /// acclocator
   typedef Alloc  allocator_type;
   /// const reference type
   typedef typename Alloc::const_reference const_reference;
   /// iterator type
   typedef typename VectorType::iterator iterator;
   /// const iterator type
   typedef typename VectorType::const_iterator const_iterator;
   /// size type
   typedef typename VectorType::size_type size_type;
   /// difference type
   typedef typename VectorType::difference_type	difference_type;
   /// const pointer type
   typedef typename VectorType::const_pointer const_pointer;
   /// const reverse iterator
   typedef typename VectorType::const_reverse_iterator	const_reverse_iterator;

   // memeber functions:
   // constructor
   RandomAccessSet(const size_t, const Compare& compare=Compare(), const Alloc& alloc=Alloc());
   RandomAccessSet(const Compare& compare=Compare(), const Alloc& alloc=Alloc());
   template <class InputIterator>
      RandomAccessSet(InputIterator, InputIterator, const Compare& compare =Compare(), const Alloc & alloc=Alloc());
   RandomAccessSet(const RandomAccessSet&);

   // operator=
   RandomAccessSet& operator=(const RandomAccessSet &);
   // operator[]
   const value_type& operator[](const size_type) const;
   // iterators
   const_iterator begin() const;
   const_iterator end() const;
   const_iterator rbegin() const;
   const_iterator rend() const;

   iterator begin();
   iterator end();
   iterator rbegin();
   iterator rend();
   bool empty() const;
   size_type size() const;
   size_type max_size() const;
   std::pair< const_iterator,bool> insert(const value_type&);
   template <class InputIterator>
      void insert(InputIterator, InputIterator);
   const_iterator insert(const_iterator , const value_type&);
   void erase(iterator position);
   size_type erase(const key_type& );
   void erase( const_iterator, const_iterator);
   void swap(RandomAccessSet&);
   void clear();
   key_compare key_comp() const;
   value_compare value_comp() const;
   const_iterator find(const key_type&) const;
   iterator find(const key_type&);
   size_type count(const key_type&) const;
   const_iterator lower_bound(const key_type&) const;
   const_iterator upper_bound(const key_type&) const;
   std::pair<const_iterator,const_iterator> equal_range(const key_type&) const;
   iterator lower_bound(const key_type&) ;
   iterator upper_bound(const key_type&) ;
   std::pair<iterator,iterator> equal_range(const key_type&) ;
   allocator_type get_allocator() const;

   // std vector functions
   void reserve(const size_t size){
       vector_.reserve(size);
   }
   size_t capacity()const{
       return vector_.capacity();
   }
   
   template<class SET>
   void assignFromSet(const SET & set){
      vector_.assign(set.begin(),set.end());
   }

private:
   std::vector<Key> vector_;
   Compare compare_;
};

/// constructor
/// \param reserveSize reserve /allocate space
/// \param compare comperator
/// \param alloc allocator
template<class Key, class Compare, class Alloc>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   const size_t reserveSize,
   const Compare& compare,
   const Alloc& alloc
)
:  vector_(alloc),
   compare_(compare) {
   vector_.reserve(reserveSize);
}

/// const access values
/// \param index index of the value in the set
/// \return value / key at the position index
template<class Key, class Compare, class Alloc>
inline const typename RandomAccessSet<Key,Compare,Alloc>::value_type&
RandomAccessSet<Key,Compare,Alloc>::operator[]
(
   const typename RandomAccessSet<Key,Compare,Alloc>::size_type  index
) const
{
   return vector_[index];
}

/// constructor
/// \param compare comperator
/// \allloc allocator
template<class Key, class Compare, class Alloc>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   const Compare& compare,
   const Alloc& alloc
)
:  vector_(alloc),
   compare_(compare)
{}

/// constructor
/// \tparam InputIterator (key/value) input iterator
/// \param beginInput
/// \param endInput
template<class Key, class Compare, class Alloc>
template <class InputIterator>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   InputIterator beginInput,
   InputIterator endInput,
   const Compare& compare,
   const Alloc& alloc
)
:  vector_(alloc),
   compare_(compare)
{
   while(beginInput!=endInput) {
      this->insert(*beginInput);
      ++beginInput;
   }
}

/// copy constructor
/// \param src other random access set
template<class Key, class Compare, class Alloc>
inline
RandomAccessSet<Key,Compare,Alloc>::RandomAccessSet
(
   const RandomAccessSet<Key,Compare,Alloc>& src
)
:  vector_(src.vector_),
   compare_(src.compare_) {
}

/// assignment operator
/// \param src other random access set
template<class Key, class Compare, class Alloc>
inline RandomAccessSet<Key,Compare,Alloc>&
RandomAccessSet<Key,Compare,Alloc>::operator=
(
   const RandomAccessSet<Key,Compare,Alloc> & src
)
{
    if(this!=&src) {
      vector_=src.vector_;
      compare_=src.compare_;
   }
   return *this;
}

/// const begin iterator
/// \returns begin iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::begin() const
{
   return vector_.begin();
}

/// const end iterator
/// \returns end iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::end() const
{
    return vector_.end();
}
/// reverse const begin iterator
/// \returns reverse begin iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::rbegin() const
{
   return vector_.rbegin();
}

/// reverse const end iterator
/// \param reverse end iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::rend() const
{
    return vector_.rend();
}

/// begin iterator
/// \param begin iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::begin()
{
   return vector_.begin();
}

/// end iterator
/// \param end iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::end()
{
    return vector_.end();
}

/// reverse  begin iterator
/// \param reverse begin iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::rbegin()
{
   return vector_.rbegin();
}

/// reverse end iterator
/// \param reverse end iterator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::rend()
{
    return vector_.rend();
}

/// query if the set is empty
/// \return true if empty
template<class Key, class Compare, class Alloc>
inline bool
RandomAccessSet<Key,Compare,Alloc>::empty() const
{
   return vector_.empty();
}

/// number of elements of the set
/// \returns number of elements in the set
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::size() const
{
   return vector_.size();
}

/// maximum size of the underlying container
/// \return the maximum size
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::max_size() const
{
   return vector_.max_size();
}

// modifiers
/// insert an element into the set
///
/// \param value element to insert
/// \return pair in which the first entry is an iterator pointing to inserted
/// value and the second entry is true iff the value had not already been in the
/// set
template<class Key, class Compare, class Alloc>
inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,bool>
RandomAccessSet<Key,Compare,Alloc>::insert
(
   const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
) {
   bool found(true);
   iterator i(lower_bound(static_cast<Key>(value)));
   if(i == end() || compare_(static_cast<Key>(value), *i)) {
      i = vector_.insert(i, static_cast<Key>(value));
      found = false;
   }
   return std::make_pair(i, !found);
}

/// insert a sequence of elements
///
/// \param first iterator to the first element
/// \param last iterator to the last element
template<class Key, class Compare, class Alloc>
template <class InputIterator>
inline void
RandomAccessSet<Key,Compare,Alloc>::insert
(
   InputIterator first,
   InputIterator last
)
{
   while(first!=last) {
      this->insert(*first);
      ++first;
   }
}

/// insert a sequence of elements with a hint for the position
///
/// \param position iterator to the position
/// \param value element to insert
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::insert
(
   typename RandomAccessSet<Key,Compare,Alloc>::const_iterator position,
   const typename RandomAccessSet<Key,Compare,Alloc>::value_type& value
)
{
   if((position == begin() || this->operator()(*(position-1),value))
   && (position == end() || this->operator()(value, *position))) {
       return vector_.insert(position, value);
   }
   return insert(value).first;
}

/// erase an element
/// \param position iterator to the position
template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::erase
(
   typename RandomAccessSet<Key,Compare,Alloc>::iterator position
)
{
   vector_.erase(position);
}

/// erease and element
/// \param x element
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::erase
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& x
)
{
   iterator i =find(x);
   if(i!=vector_.end())
   {
      erase(i);
      return 1;
   }
   return 0;
}

/// erase a sequence of elements
/// \param first iterator to the beginning of the sequence to erase
/// \param last iterator to the end of the sequence to erase
template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::erase
(
   const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator first,
   const typename RandomAccessSet<Key,Compare,Alloc>::const_iterator last
)
{
   vector_.erase(first,last);
}

/// swap random access sets
/// \param rhs set to swap with
template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::swap
(
   RandomAccessSet<Key,Compare,Alloc>& rhs
)
{
   vector_.swap(rhs.vector_);
   compare_=rhs.compare_;
}

/// clear the set
///
/// erases all elements
template<class Key, class Compare, class Alloc>
inline void
RandomAccessSet<Key,Compare,Alloc>::clear()
{
   vector_.clear();
}

/// key comparator
/// \return key comparator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::key_compare
RandomAccessSet<Key,Compare,Alloc>::key_comp() const
{
   return compare_;
}

/// value comparator
/// \return value comparator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::value_compare
RandomAccessSet<Key,Compare,Alloc>::value_comp() const
{
   return compare_;
}

/// find an element
/// \param value element
/// \return const_iterator to the position where element was found or end
/// iterator if the element was not found
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::find
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   const_iterator i(lower_bound(value));
   if (i != end() && compare_(value, *i))
   {
       i = end();
   }
   return i;
}

/// find an element
/// \param value element
/// \return iterator to the position where the element was found or end
/// iterator if the element was not found
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::find
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   iterator i(lower_bound(value));
   if (i != end() && compare_(value, *i))
   {
       i = end();
   }
   return i;
}

/// count elements
/// \param element
/// \return zero or one
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::size_type
RandomAccessSet<Key,Compare,Alloc>::count
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type&  value
) const
{
   return find(value) != end();
}

/// lower bound
/// \param value
/// \return iterator to lower bound
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::lower_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
}

/// lower bound
/// \param value
/// \return iterator to lower bound
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::lower_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   return std::lower_bound(vector_.begin(), vector_.end(), value, compare_);
}

/// upper bound
/// \param value
/// \return iterator to upper bound
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::const_iterator
RandomAccessSet<Key,Compare,Alloc>::upper_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
}

/// upper bound
/// \param value
/// \return iterator to upper bound
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::iterator
RandomAccessSet<Key,Compare,Alloc>::upper_bound
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   return std::upper_bound(vector_.begin(), vector_.end(), value, compare_);
}

/// equal range
/// \param value
/// \return iterator pair to lower equal range
template<class Key, class Compare, class Alloc>
inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::const_iterator,typename RandomAccessSet<Key,Compare,Alloc>::const_iterator>
RandomAccessSet<Key,Compare,Alloc>::equal_range
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
) const
{
   return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
}

/// equal range
/// \param value
/// \return iterator pair to lower equal range
template<class Key, class Compare, class Alloc>
inline std::pair<typename RandomAccessSet<Key,Compare,Alloc>::iterator,typename RandomAccessSet<Key,Compare,Alloc>::iterator>
RandomAccessSet<Key,Compare,Alloc>::equal_range
(
   const typename RandomAccessSet<Key,Compare,Alloc>::key_type& value
)
{
   return std::equal_range(vector_.begin(), vector_.end(), value, compare_);
}
/// allocators
/// \return allocator
template<class Key, class Compare, class Alloc>
inline typename RandomAccessSet<Key,Compare,Alloc>::allocator_type
RandomAccessSet<Key,Compare,Alloc>::get_allocator() const
{
   return vector_.get_allocator();
}

} // namespace opengm

#endif // OPENGM_RANDOM_ACCESS_SET_HXX