This file is indexed.

/usr/include/wibble/range.h is in libwibble-dev 1.1-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
/** -*- C++ -*-
    @file wibble/range.h
    @author Peter Rockai <me@mornfall.net>
*/

#include <iostream> // for noise
#include <iterator>
#include <vector>
#include <set>
#include <algorithm>

#include <wibble/iterator.h>
#include <wibble/exception.h>

#ifndef WIBBLE_RANGE_H
#define WIBBLE_RANGE_H

namespace wibble {

template< typename _ > struct Range;
template< typename _ > struct Consumer;

// FOO: there was no test catching that we don't implement ->
// auxilliary class, used as Range< T >::iterator
template< typename R >
struct RangeIterator : mixin::Comparable< RangeIterator< R > > {
    typedef typename R::ElementType T;

    struct Proxy {
        Proxy( T _x ) : x( _x ) {}
        T x;
        const T *operator->() const { return &x; }
    };

    RangeIterator() {}
    RangeIterator( const R &r ) : m_range( r ) {}

    typedef std::forward_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T *pointer;
    typedef T &reference;
    typedef const T &const_reference;

    Proxy operator->() const { return Proxy( *(*this) ); }

    RangeIterator next() const { RangeIterator n( *this ); ++n; return n; }
    typename R::ElementType operator*() const { return m_range.head(); }
    typename R::ElementType current() const { return *(*this); }
    RangeIterator &operator++() { m_range.removeFirst(); return *this; }
    RangeIterator operator++(int) { return m_range.removeFirst(); }
    bool operator<=( const RangeIterator &r ) const {
        return m_range.operator<=( r.m_range );
    }
protected:
    R m_range;
};

// the common functionality of all ranges
template< typename T, typename Self >
struct RangeMixin : mixin::Comparable< Self >
{
    typedef Self RangeImplementation;
    typedef T ElementType;
    const Self &self() const { return *static_cast< const Self * >( this ); }
    typedef IteratorMixin< T, Self > Base;
    typedef RangeIterator< Self > iterator;
    friend struct RangeIterator< Self >;

    iterator begin() const { return iterator( this->self() ); } // STL-style iteration
    iterator end() const { Self e( this->self() ); e.setToEmpty(); return iterator( e ); }

    // range terminology
    T head() { return self().head(); }
    Self tail() const { Self e( this->self() ); e.removeFirst(); return e; }
    // Self &tail() { return self().tail(); }

    void output( Consumer< T > t ) const {
        std::copy( begin(), end(), t );
    }

    bool empty() const {
        return begin() == end();
    }

    ~RangeMixin() {}
};

// interface to be implemented by all range implementations
// refinement of IteratorInterface (see iterator.h)
// see also amorph.h on how the Morph/Amorph classes are designed
template< typename T >
struct RangeInterface {
    virtual T head() const = 0;
    virtual void removeFirst() = 0;
    virtual void setToEmpty() = 0;
    virtual ~RangeInterface() {}
};

template< typename T, typename W >
struct RangeMorph: Morph< RangeMorph< T, W >, W, RangeInterface< T > >
{
    typedef typename W::RangeImplementation Wrapped;
    RangeMorph( const Wrapped &w ) : Morph< RangeMorph, Wrapped, RangeInterface< T > >( w ) {}
    virtual void setToEmpty() { this->wrapped().setToEmpty(); }
    virtual void removeFirst() { this->wrapped().removeFirst(); }
    virtual T head() const { return this->wrapped().head(); }
};

// the Amorph of Ranges... if you still didn't check amorph.h, go and
// do it... unless you don't care in which case i am not sure why you
// are reading this anyway

/*
  Range< T > (and all its Morphs (implementations) alike) work as an
  iterable, immutable range of items -- in a way like STL
  const_begin(), const_end() pair of iterators. However, Range packs
  these two in a single object, which you can then pass as a single
  argument or return as a value. There are many Range implementations,
  some of them use STL containers (or just a pair of iterators) as
  backing (IteratorRange, BackedRange), some use other ranges.

  The latter are slightly more interesting, since they provide an
  "adapted" view on the underlying range(s). See FilteredRange,
  TransformedRange, UniqueRange, CastedRange , IntersectionRange.

  GeneratedRange has no "real" backing at all, but use a pair of
  functors and "generates" (by calling those functors) the complete
  range as it is iterated.

  Example usage:

  // create a range from a pair of STL iterators
  Range< int > i = range( myIntVector.begin(), myIntVector.end() );
  // create a range that is filtered view of another range
  Range< int > j = filteredRange( i, predicate );
  std::vector< int > vec;
  // copy out items in j into vec; see also consumer.h
  j.output( consumer( vec ) );
  // vec now contains all items from i (and thus myIntVector) that
  // match 'predicate'

  You don't have to use Range< int > all the time, since it's fairly
  inefficient (adding level of indirection). However in common cases
  it is ok. In the uncommon cases you can use the specific
  implementation type and there you won't suffer the indirection
  penalty. You can also write generic functions that have type of
  range as their template parameter and these will work more
  efficiently if Morph is used directly and less efficiently when the
  Amorph Range is used instead.
 */
template< typename T >
struct Range : Amorph< Range< T >, RangeInterface< T > >,
               RangeMixin< T, Range< T > >
{
    typedef Amorph< Range< T >, RangeInterface< T > > Super;

    template< typename C >
    Range( const C &i, typename IsType< int, typename C::RangeImplementation >::T fake = 0 )
        : Super( RangeMorph< T, C >( i ) ) { (void)fake; }
    Range() {}

    T head() const { return this->implementation()->head(); }
    void removeFirst() { this->implementation()->removeFirst(); }
    void setToEmpty() { this->implementation()->setToEmpty(); }

    template< typename C > operator Range< C >();
};

/* template< typename R >
Range< typename R::ElementType > rangeMorph( R r ) {
    return Range< typename R::ElementType > uRangeMorph< typename R::ElementType, R >( r );
    } */

}

// ----- individual range implementations follow
#include <wibble/consumer.h>

namespace wibble {

// a simple pair of iterators -- suffers the same invalidation
// semantics as normal STL iterators and also same problems when the
// backing storage goes out of scope

// this is what you get when using range( iterator1, iterator2 )
// see also range()
template< typename It >
struct IteratorRange : public RangeMixin<
    typename std::iterator_traits< It >::value_type,
    IteratorRange< It > >
{
    typedef typename std::iterator_traits< It >::value_type Value;

    IteratorRange() {}
    IteratorRange( It c, It e )
        : m_current( c ), m_end( e ) {}

    Value head() const { return *m_current; }
    void removeFirst() { ++m_current; }

    bool operator<=( const IteratorRange &r ) const {
        return r.m_current == m_current && r.m_end == m_end;
    }

    void setToEmpty() {
        m_current = m_end;
    }

protected:
    It m_current, m_end;
};

// first in the series of ranges that use another range as backing
// this one just does static_cast to specified type on all the
// returned elements

// this is what you get when casting Range< S > to Range< T > and S is
// static_cast-able to T

template< typename T, typename Casted >
struct CastedRange : public RangeMixin< T, CastedRange< T, Casted > >
{
    CastedRange() {}
    CastedRange( Range< Casted > r ) : m_casted( r ) {}
    T head() const {
        return static_cast< T >( m_casted.head() );
    }
    void removeFirst() { m_casted.removeFirst(); }

    bool operator<=( const CastedRange &r ) const {
        return m_casted <= r.m_casted;
    }

    void setToEmpty() {
        m_casted.setToEmpty();
    }

protected:
    Range< Casted > m_casted;
};

// explicit range-cast... probably not very useful explicitly, just
// use the casting operator of Range
template< typename T, typename C >
Range< T > castedRange( C r ) {
    return CastedRange< T, typename C::ElementType >( r );
}

// old-code-compat for castedRange... slightly silly
template< typename T, typename C >
Range< T > upcastRange( C r ) {
    return CastedRange< T, typename C::ElementType >( r );
}

// the range-cast operator, see castedRange and CastedRange
template< typename T > template< typename C >
Range< T >::operator Range< C >() {
    return castedRange< C >( *this );
}

// range( iterator1, iterator2 ) -- see IteratorRange
template< typename In >
Range< typename In::value_type > range( In b, In e ) {
    return IteratorRange< In >( b, e );
}

template< typename C >
Range< typename C::iterator::value_type > range( C &c ) {
    return range( c.begin(), c.end() );
}

template< typename T >
struct IntersectionRange : RangeMixin< T, IntersectionRange< T > >
{
    IntersectionRange() {}
    IntersectionRange( Range< T > r1, Range< T > r2 )
        : m_first( r1 ), m_second( r2 ),
        m_valid( false )
    {
    }

    void find() const {
        if (!m_valid) {
            while ( !m_first.empty() && !m_second.empty() ) {
                if ( m_first.head() < m_second.head() )
                    m_first.removeFirst();
                else if ( m_second.head() < m_first.head() )
                    m_second.removeFirst();
                else break; // equal
            }
            if ( m_second.empty() ) m_first.setToEmpty();
            else if ( m_first.empty() ) m_second.setToEmpty();
        }
        m_valid = true;
    }

    void removeFirst() {
        find();
        m_first.removeFirst();
        m_second.removeFirst();
        m_valid = false;
    }

    T head() const {
        find();
        return m_first.head();
    }

    void setToEmpty() {
        m_first.setToEmpty();
        m_second.setToEmpty();
    }

    bool operator<=( const IntersectionRange &f ) const {
        find();
        f.find();
        return m_first == f.m_first;
    }

protected:
    mutable Range< T > m_first, m_second;
    mutable bool m_valid:1;
};

template< typename R >
IntersectionRange< typename R::ElementType > intersectionRange( R r1, R r2 ) {
    return IntersectionRange< typename R::ElementType >( r1, r2 );
}

template< typename R, typename Pred >
struct FilteredRange : RangeMixin< typename R::ElementType,
                                  FilteredRange< R, Pred > >
{
    typedef typename R::ElementType ElementType;
    // FilteredRange() {}
    FilteredRange( const R &r, Pred p ) : m_range( r ), m_current( r.begin() ), m_pred( p ),
        m_valid( false ) {}

    void find() const {
        if (!m_valid)
            m_current = std::find_if( m_current, m_range.end(), pred() );
        m_valid = true;
    }

    void removeFirst() {
        find();
        ++m_current;
        m_valid = false;
    }

    ElementType head() const {
        find();
        return *m_current;
    }

    void setToEmpty() {
        m_current = m_range.end();
    }

    bool operator<=( const FilteredRange &f ) const {
        find();
        f.find();
        return m_current == f.m_current;
        // return m_pred == f.m_pred && m_range == f.m_range;
    }

protected:
    const Pred &pred() const { return m_pred; }
    R m_range;
    mutable typename R::iterator m_current;
    Pred m_pred;
    mutable bool m_valid:1;
};

template< typename R, typename Pred >
FilteredRange< R, Pred > filteredRange(
    R r, Pred p ) {
    return FilteredRange< R, Pred >( r, p );
}

template< typename T >
struct UniqueRange : RangeMixin< T, UniqueRange< T > >
{
    UniqueRange() {}
    UniqueRange( Range< T > r ) : m_range( r ), m_valid( false ) {}

    void find() const {
        if (!m_valid)
            while ( !m_range.empty()
                    && !m_range.tail().empty()
                    && m_range.head() == m_range.tail().head() )
                m_range = m_range.tail();
        m_valid = true;
    }

    void removeFirst() {
        find();
        m_range.removeFirst();
        m_valid = false;
    }

    T head() const {
        find();
        return m_range.head();
    }

    void setToEmpty() {
        m_range.setToEmpty();
    }

    bool operator<=( const UniqueRange &r ) const {
        find();
        r.find();
        return m_range == r.m_range;
    }

protected:
    mutable Range< T > m_range;
    mutable bool m_valid:1;
};

template< typename R >
UniqueRange< typename R::ElementType > uniqueRange( R r1 ) {
    return UniqueRange< typename R::ElementType >( r1 );
}

template< typename Transform >
struct TransformedRange : RangeMixin< typename Transform::result_type,
                                     TransformedRange< Transform > >
{
    typedef typename Transform::argument_type Source;
    typedef typename Transform::result_type Result;
    TransformedRange( Range< Source > r, Transform t )
        : m_range( r ), m_transform( t ) {}

    bool operator<=( const TransformedRange &o ) const {
        return m_range <= o.m_range;
    }

    Result head() const { return m_transform( m_range.head() ); }
    void removeFirst() { m_range.removeFirst(); }
    void setToEmpty() { m_range.setToEmpty(); }

protected:
    Range< Source > m_range;
    Transform m_transform;
};

template< typename Trans >
TransformedRange< Trans > transformedRange(
    Range< typename Trans::argument_type > r, Trans t ) {
    return TransformedRange< Trans >( r, t );
}

template< typename T, typename _Advance, typename _End >
struct GeneratedRange : RangeMixin< T, GeneratedRange< T, _Advance, _End > >
{
    typedef _Advance Advance;
    typedef _End End;

    GeneratedRange() {}
    GeneratedRange( const T &t, const Advance &a, const End &e )
        : m_current( t ), m_advance( a ), m_endPred( e ), m_end( false )
    {
    }

    void removeFirst() {
        m_advance( m_current );
    }

    void setToEmpty() {
        m_end = true;
    }

    T head() const { return m_current; }

    bool isEnd() const { return m_end || m_endPred( m_current ); }

    bool operator<=( const GeneratedRange &r ) const {
        if ( isEnd() == r.isEnd() && !isEnd() )
            return m_current <= r.m_current;
        return isEnd() <= r.isEnd();
    }

protected:
    T m_current;
    Advance m_advance;
    End m_endPred;
    bool m_end;
};

template< typename T, typename A, typename E >
GeneratedRange< T, A, E > generatedRange( T t, A a, E e )
{
    return GeneratedRange< T, A, E >( t, a, e );
}

}

#endif