list.h
Go to the documentation of this file.
// -*- C++ -*-
#include <memory>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstddef>
#ifndef WIBBLE_LIST_H
#define WIBBLE_LIST_H
namespace wibble {
namespace list {
template< typename List >
struct ListIterator
{
typedef std::forward_iterator_tag iterator_category;
typedef typename List::Type value_type;
typedef ptrdiff_t difference_type;
typedef value_type &pointer;
typedef value_type &reference;
List l;
ListIterator &operator++() {
l = l.tail();
return *this;
}
ListIterator operator++(int) {
ListIterator i = *this;
operator++();
return i;
}
typename List::Type operator*() {
return l.head();
}
bool operator==( const ListIterator &o ) const {
return l.empty() && o.l.empty();
}
bool operator!=( const ListIterator &o ) const {
return !(l.empty() && o.l.empty());
}
ListIterator( List _l = List() ) : l( _l )
{}
};
template< typename List >
struct Sorted
{
typedef std::vector< typename List::Type > Vec;
struct SharedVec {
int refs;
Vec vec;
SharedVec() : refs( 1 ) {}
void _ref() { ++refs; }
void _deref() { --refs; }
};
struct SharedPtr {
SharedVec *vec;
SharedPtr( bool a = false ) { vec = a ? new SharedVec : 0; }
SharedPtr( const SharedPtr &o ) {
vec = o.vec;
if ( vec )
vec->_ref();
}
SharedPtr &operator=( const SharedPtr &o ) {
vec = o.vec;
if ( vec )
vec->_ref();
return *this;
}
operator bool() { return vec; }
Vec &operator*() { return vec->vec; }
Vec *operator->() { return &(vec->vec); }
~SharedPtr() {
if ( vec ) {
vec->_deref();
if ( !vec->refs )
delete vec;
}
}
};
typedef typename List::Type Type;
List m_list;
mutable SharedPtr m_sorted;
size_t m_pos;
void sort() const {
if ( m_sorted )
return;
m_sorted = SharedPtr( true );
std::copy( ListIterator< List >( m_list ), ListIterator< List >(),
std::back_inserter( *m_sorted ) );
std::sort( m_sorted->begin(), m_sorted->end() );
}
Type head() const {
sort();
return (*m_sorted)[ m_pos ];
}
Sorted tail() const {
sort();
Sorted s = *this;
s.m_pos ++;
return s;
}
bool empty() const {
sort();
return m_pos == m_sorted->size();
}
Sorted( const Sorted &o ) : m_list( o.m_list ), m_sorted( o.m_sorted ),
m_pos( o.m_pos ) {}
Sorted &operator=( const Sorted &o ) {
m_sorted = o.m_sorted;
m_list = o.m_list;
m_pos = o.m_pos;
return *this;
}
Sorted( List l = List() ) : m_list( l ), m_sorted( 0 ), m_pos( 0 ) {}
};
template< typename List, typename Predicate >
struct Filtered
{
typedef typename List::Type Type;
mutable List m_list;
Predicate m_pred;
bool empty() const {
seek();
return m_list.empty();
}
Type head() const {
seek();
return m_list.head();
}
void seek() const
{
while ( !m_list.empty() && !m_pred( m_list.head() ) )
m_list = m_list.tail();
}
Filtered tail() const
{
Filtered r = *this;
r.seek();
r.m_list = r.m_list.tail();
return r;
}
Filtered( List l, Predicate p )
: m_list( l ), m_pred( p )
{
}
Filtered() {}
};
template< typename List >
struct Unique
{
typedef typename List::Type Type;
mutable List m_list;
bool empty() const {
seek();
return m_list.empty();
}
Type head() const {
seek();
return m_list.head();
}
void seek() const
{
if ( m_list.empty() )
return;
if ( m_list.tail().empty() )
return;
if ( m_list.head() == m_list.tail().head() ) {
m_list = m_list.tail();
return seek();
}
}
Unique tail() const
{
Unique r = *this;
r.seek();
r.m_list = r.m_list.tail();
return r;
}
Unique( List l = List() )
: m_list( l )
{
}
};
template< typename List >
struct Take {
List l;
int remaining;
typedef typename List::Type Type;
Type head() const {
return l.head();
}
bool empty() const {
return l.empty() || remaining == 0;
}
Take tail() const {
Take t;
t.remaining = remaining - 1;
t.l = l.tail();
return t;
}
Take( List _l, int m ) : l( _l ), remaining( m ) {}
Take() : remaining( 0 ) {}
};
template< typename List, typename F >
struct Map {
List l;
char f_space[ sizeof( F ) ];
F &f() {
return *static_cast<F *>(f_space);
}
const F &f() const {
return *static_cast<const F *>(f_space);
}
typedef typename F::result_type Type;
Type head() const {
return f()( l.head() );
}
Map tail() const {
Map m;
m.l = l.tail();
m.f() = f();
return m;
}
bool empty() const {
return l.empty();
}
Map() {}
Map( const List &_l, const F &_f )
: l( _l )
{
f() = _f;
}
};
template< typename T >
struct Empty {
typedef T Type;
T head() const { return T(); }
bool empty() const { return true; }
Empty tail() const { return Empty(); }
};
template< typename T >
struct Singular {
typedef T Type;
T m_value;
bool m_empty;
Singular() : m_empty( true ) {}
Singular( T i ) : m_value( i ), m_empty( false ) {}
T head() const { return m_value; }
bool empty() const { return m_empty; }
Singular tail() const { return Singular(); }
};
template< typename T1, typename T2 >
struct Append {
typedef typename T1::Type Type;
T1 m_1;
T2 m_2;
Append() {}
Append( T1 a, T2 b ) : m_1( a ), m_2( b ) {}
Type head() const {
if ( m_1.empty() )
return m_2.head();
return m_1.head();
}
bool empty() const { return m_1.empty() && m_2.empty(); }
Append tail() const {
Append t = *this;
if ( !t.m_1.empty() )
t.m_1 = t.m_1.tail();
else
t.m_2 = t.m_2.tail();
return t;
}
};
template< typename X >
Singular< X > singular( const X &x ) {
return Singular< X >( x );
}
template< typename X, typename Y >
Append< X, Y > append( const X &x, const Y &y ) {
return Append< X, Y >( x, y );
}
template< typename List >
size_t count( List l ) {
size_t count = 0;
while ( !l.empty() ) {
l = l.tail();
++ count;
}
return count;
}
#undef foreach // Work around Qt braindamage.
template< typename List, typename F >
void foreach( List l, F f ) {
while ( !l.empty() ) {
f( l.head() );
l = l.tail();
}
}
template< typename List, template< typename > class F >
void foreach( List l, F< typename List::Type > f ) {
while ( !l.empty() ) {
f( l.head() );
l = l.tail();
}
}
template< typename List, typename Pred >
Filtered< List, Pred > filter( List l, Pred p )
{
return Filtered< List, Pred >( l, p );
}
template< typename List, template< typename > class Pred >
Filtered< List, Pred< List > > filter( List l, Pred< List > p )
{
return Filtered< List, Pred< List > >( l, p );
}
template< typename List, typename F >
Map< List, F > map( const List &l, const F &f )
{
return Map< List, F >( l, f );
}
template< typename List >
Sorted< List > sort( List l )
{
return Sorted< List >( l );
}
template< typename List >
Unique< List > unique( List l )
{
return Unique< List >( l );
}
template< typename List >
Take< List > take( int t, List l )
{
return Take< List >( l, t );
}
template< typename List >
List drop( int t, List l )
{
while ( t > 0 ) {
l = l.tail();
-- t;
}
return l;
}
template< typename List, typename Out >
void output( List l, Out it ) {
std::copy( ListIterator< List >( l ), ListIterator< List >(), it );
}
template< typename List >
ListIterator< List > begin( List l ) {
return ListIterator< List >( l );
}
template< typename List >
ListIterator< List > end( List ) {
return ListIterator< List >();
}
}
}
#endif
wibble::list::end
ListIterator< List > end(List)
Definition: list.h:425
wibble::list::begin
ListIterator< List > begin(List l)
Definition: list.h:420
wibble::list::singular
Singular< X > singular(const X &x)
Definition: list.h:331
wibble::list::map
Map< List, F > map(const List &l, const F &f)
Definition: list.h:381
wibble::list::append
Append< X, Y > append(const X &x, const Y &y)
Definition: list.h:336
wibble::list::unique
Unique< List > unique(List l)
Definition: list.h:393
wibble::list::count
size_t count(List l)
Definition: list.h:341
wibble::list::filter
Filtered< List, Pred > filter(List l, Pred p)
Definition: list.h:369
wibble::list::take
Take< List > take(int t, List l)
Definition: list.h:399
wibble::list::sort
Sorted< List > sort(List l)
Definition: list.h:387
wibble::list::output
void output(List l, Out it)
Definition: list.h:415
wibble::list::drop
List drop(int t, List l)
Definition: list.h:405
wibble
Definition: amorph.h:17
wibble::list::Append
Definition: list.h:305
wibble::list::Append::empty
bool empty() const
Definition: list.h:318
wibble::list::Append::Type
T1::Type Type
Definition: list.h:306
wibble::list::Append::m_1
T1 m_1
Definition: list.h:307
wibble::list::Append::Append
Append(T1 a, T2 b)
Definition: list.h:311
wibble::list::Append::head
Type head() const
Definition: list.h:312
wibble::list::Append::m_2
T2 m_2
Definition: list.h:308
wibble::list::Append::Append
Append()
Definition: list.h:310
wibble::list::Append::tail
Append tail() const
Definition: list.h:319
wibble::list::Empty
Definition: list.h:284
wibble::list::Empty::head
T head() const
Definition: list.h:286
wibble::list::Empty::Type
T Type
Definition: list.h:285
wibble::list::Empty::empty
bool empty() const
Definition: list.h:287
wibble::list::Empty::tail
Empty tail() const
Definition: list.h:288
wibble::list::Filtered
Definition: list.h:141
wibble::list::Filtered::empty
bool empty() const
Definition: list.h:146
wibble::list::Filtered::Filtered
Filtered(List l, Predicate p)
Definition: list.h:170
wibble::list::Filtered::head
Type head() const
Definition: list.h:151
wibble::list::Filtered::Filtered
Filtered()
Definition: list.h:175
wibble::list::Filtered::Type
List::Type Type
Definition: list.h:142
wibble::list::Filtered::m_pred
Predicate m_pred
Definition: list.h:144
wibble::list::Filtered::tail
Filtered tail() const
Definition: list.h:162
wibble::list::Filtered::m_list
List m_list
Definition: list.h:143
wibble::list::Filtered::seek
void seek() const
Definition: list.h:156
wibble::list::ListIterator
Definition: list.h:16
wibble::list::ListIterator::ListIterator
ListIterator(List _l=List())
Definition: list.h:48
wibble::list::ListIterator::value_type
List::Type value_type
Definition: list.h:18
wibble::list::ListIterator::reference
value_type & reference
Definition: list.h:21
wibble::list::ListIterator::l
List l
Definition: list.h:23
wibble::list::ListIterator::pointer
value_type & pointer
Definition: list.h:20
wibble::list::ListIterator::difference_type
ptrdiff_t difference_type
Definition: list.h:19
wibble::list::ListIterator::operator*
List::Type operator*()
Definition: list.h:36
wibble::list::ListIterator::operator++
ListIterator operator++(int)
Definition: list.h:30
wibble::list::ListIterator::operator++
ListIterator & operator++()
Definition: list.h:25
wibble::list::ListIterator::operator==
bool operator==(const ListIterator &o) const
Definition: list.h:40
wibble::list::ListIterator::operator!=
bool operator!=(const ListIterator &o) const
Definition: list.h:44
wibble::list::ListIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: list.h:17
wibble::list::Map
Definition: list.h:247
wibble::list::Map::Map
Map(const List &_l, const F &_f)
Definition: list.h:276
wibble::list::Map::Map
Map()
Definition: list.h:275
wibble::list::Map::head
Type head() const
Definition: list.h:260
wibble::list::Map::Type
F::result_type Type
Definition: list.h:258
wibble::list::Map::f
const F & f() const
Definition: list.h:254
wibble::list::Map::l
List l
Definition: list.h:248
wibble::list::Map::f_space
char f_space[sizeof(F)]
Definition: list.h:250
wibble::list::Map::empty
bool empty() const
Definition: list.h:271
wibble::list::Map::f
F & f()
Definition: list.h:251
wibble::list::Map::tail
Map tail() const
Definition: list.h:264
wibble::list::Singular
Definition: list.h:292
wibble::list::Singular::Type
T Type
Definition: list.h:293
wibble::list::Singular::Singular
Singular(T i)
Definition: list.h:298
wibble::list::Singular::empty
bool empty() const
Definition: list.h:300
wibble::list::Singular::Singular
Singular()
Definition: list.h:297
wibble::list::Singular::head
T head() const
Definition: list.h:299
wibble::list::Singular::m_value
T m_value
Definition: list.h:294
wibble::list::Singular::tail
Singular tail() const
Definition: list.h:301
wibble::list::Singular::m_empty
bool m_empty
Definition: list.h:295
wibble::list::Sorted::SharedPtr
Definition: list.h:65
wibble::list::Sorted::SharedPtr::vec
SharedVec * vec
Definition: list.h:66
wibble::list::Sorted::SharedPtr::operator*
Vec & operator*()
Definition: list.h:83
wibble::list::Sorted::SharedPtr::SharedPtr
SharedPtr(bool a=false)
Definition: list.h:67
wibble::list::Sorted::SharedPtr::operator=
SharedPtr & operator=(const SharedPtr &o)
Definition: list.h:75
wibble::list::Sorted::SharedPtr::operator->
Vec * operator->()
Definition: list.h:84
wibble::list::Sorted::SharedPtr::SharedPtr
SharedPtr(const SharedPtr &o)
Definition: list.h:69
wibble::list::Sorted::SharedPtr::~SharedPtr
~SharedPtr()
Definition: list.h:86
wibble::list::Sorted::SharedVec
Definition: list.h:57
wibble::list::Sorted::SharedVec::_ref
void _ref()
Definition: list.h:61
wibble::list::Sorted::SharedVec::vec
Vec vec
Definition: list.h:59
wibble::list::Sorted::SharedVec::refs
int refs
Definition: list.h:58
wibble::list::Sorted::SharedVec::_deref
void _deref()
Definition: list.h:62
wibble::list::Sorted::SharedVec::SharedVec
SharedVec()
Definition: list.h:60
wibble::list::Sorted
Definition: list.h:55
wibble::list::Sorted::m_sorted
SharedPtr m_sorted
Definition: list.h:97
wibble::list::Sorted::operator=
Sorted & operator=(const Sorted &o)
Definition: list.h:129
wibble::list::Sorted::tail
Sorted tail() const
Definition: list.h:114
wibble::list::Sorted::Sorted
Sorted(List l=List())
Definition: list.h:136
wibble::list::Sorted::empty
bool empty() const
Definition: list.h:121
wibble::list::Sorted::sort
void sort() const
Definition: list.h:100
wibble::list::Sorted::m_list
List m_list
Definition: list.h:96
wibble::list::Sorted::Type
List::Type Type
Definition: list.h:95
wibble::list::Sorted::m_pos
size_t m_pos
Definition: list.h:98
wibble::list::Sorted::Sorted
Sorted(const Sorted &o)
Definition: list.h:126
wibble::list::Sorted::Vec
std::vector< typename List::Type > Vec
Definition: list.h:56
wibble::list::Sorted::head
Type head() const
Definition: list.h:109
wibble::list::Take
Definition: list.h:221
wibble::list::Take::Type
List::Type Type
Definition: list.h:225
wibble::list::Take::Take
Take(List _l, int m)
Definition: list.h:242
wibble::list::Take::empty
bool empty() const
Definition: list.h:231
wibble::list::Take::remaining
int remaining
Definition: list.h:223
wibble::list::Take::head
Type head() const
Definition: list.h:227
wibble::list::Take::Take
Take()
Definition: list.h:243
wibble::list::Take::tail
Take tail() const
Definition: list.h:235
wibble::list::Take::l
List l
Definition: list.h:222
wibble::list::Unique
Definition: list.h:180
wibble::list::Unique::m_list
List m_list
Definition: list.h:182
wibble::list::Unique::Type
List::Type Type
Definition: list.h:181
wibble::list::Unique::empty
bool empty() const
Definition: list.h:184
wibble::list::Unique::tail
Unique tail() const
Definition: list.h:206
wibble::list::Unique::seek
void seek() const
Definition: list.h:194
wibble::list::Unique::Unique
Unique(List l=List())
Definition: list.h:214
wibble::list::Unique::head
Type head() const
Definition: list.h:189