#ifndef __CONTAINERS_H__
#define __CONTAINERS_H__
#include "circular_list.h"
#if DEBUG_CONTAINERS
#include <debug/vector>
#include <debug/deque>
using std::__debug::vector;
using std::__debug::deque;
#else
#include <vector>
#include <deque>
using std::vector;
using std::deque;
#endif
// TODO: write documentation
template<class Container_, class Comparison_ = std::less<typename Container_::value_type> >
struct ContainerTraits
{
typedef Container_ Container;
typedef typename Container::value_type Item;
typedef typename Container::const_reference const_reference;
typedef Comparison_ Comparison;
static void reserve(Container& c, size_t sz) {}
static void sort(Container& c, const Comparison& cmp = Comparison()) { c.sort(cmp); }
static void push_front(Container& c, const_reference x) { c.push_front(x); }
};
/**
* Class: SizeStorage
*
* This class expresses how size should be stored for various containers to be able
* to deduce it in constant time. By default it is stored explicitly, so that if the
* Container is std::list everything works. However, specialization is available for
* std::vector which uses its builtin size() function.
*/
template<class Container_>
class SizeStorage
{
public:
typedef Container_ Container;
typedef SizeStorage<Container> Self;
SizeStorage(size_t size = 0): size_(size) {}
Self& operator+=(size_t inc) { size_ += inc; return *this; }
Self& operator-=(size_t dec) { size_ -= dec; return *this; }
Self& operator++() { ++size_; return *this; }
Self operator++(int) { Self tmp = *this; size_++; return tmp; }
Self& operator--() { --size_; return *this; }
Self operator--(int) { Self tmp = *this; size_--; return tmp; }
size_t size(const Container& c) const { return size_; }
void swap(SizeStorage& other) { std::swap(size_, other.size_); }
void clear() { size_ = 0; }
private:
size_t size_;
};
/**
* Class: CountingBackInserter<C>
*
* Derives from std::back_insert_iterator<C> and SizeStorage<C>,
* and keeps track of the number of inserted elements.
*/
template<class C>
struct CountingBackInserter: public std::back_insert_iterator<C>,
public SizeStorage<C>
{
typedef CountingBackInserter Self;
typedef std::back_insert_iterator<C> ParentIterator;
typedef SizeStorage<C> ParentSize;
CountingBackInserter(C& c):
ParentIterator(c) {}
Self& operator++() { ParentSize::operator++(); ParentIterator::operator++(); return *this; }
Self operator++(int i) { Self tmp = *this; ParentSize::operator++(i); ParentIterator::operator++(i); return tmp; }
};
/**
* Class: PushBackFunctor<Container>
*
* Performs the same task as std::back_insert_iterator<Container>, but as a functor.
*/
template<class Container_>
class PushBackFunctor
{
public:
typedef Container_ Container;
typedef typename Container::value_type value_type;
PushBackFunctor(Container& container):
container_(container) {}
void operator()(const value_type& v) const { container_.push_back(v); }
private:
Container& container_;
};
template<class Container>
PushBackFunctor<Container>
make_push_back_functor(Container& container) { return PushBackFunctor<Container>(container); }
/**
* Class: InsertFunctor<Container>
*
* Performs insertions of its arguments into the given container.
*/
template<class Container_>
class InsertFunctor
{
public:
typedef Container_ Container;
typedef typename Container::value_type value_type;
InsertFunctor(Container& container):
container_(container) {}
void operator()(const value_type& v) const { container_.insert(v); }
private:
Container& container_;
};
template<class Container>
InsertFunctor<Container>
make_insert_functor(Container& container) { return InsertFunctor<Container>(container); }
/* Specializations */
template<class T, class Comparison_>
struct ContainerTraits<vector<T>, Comparison_>
{
typedef T Item;
typedef vector<T> Container;
typedef typename Container::const_reference const_reference;
typedef Comparison_ Comparison;
static void reserve(Container& c, size_t sz) { c.reserve(sz); }
static void sort(Container& c, const Comparison& cmp = Comparison()) { std::sort(c.begin(), c.end(), cmp); }
static void push_front(Container& c, const_reference x) { c.insert(c.begin(), x); }
};
template<class T, class Comparison_>
struct ContainerTraits<deque<T>, Comparison_>
{
typedef T Item;
typedef deque<T> Container;
typedef typename Container::const_reference const_reference;
typedef Comparison_ Comparison;
static void reserve(Container& c, size_t sz) { }
static void sort(Container& c, const Comparison& cmp = Comparison()) { std::sort(c.begin(), c.end(), cmp); }
static void push_front(Container& c, const_reference x) { c.push_front(x); }
};
template<class T, class Comparison_>
struct ContainerTraits<List<T>, Comparison_>
{
typedef T Item;
typedef List<T> Container;
typedef typename Container::const_reference const_reference;
typedef Comparison_ Comparison;
static void reserve(Container& c, size_t sz) { }
static void sort(Container& c, const Comparison& cmp = Comparison())
{
vector<Item> tmp(c.begin(), c.end());
std::sort(tmp.begin(), tmp.end(), cmp);
std::copy(tmp.begin(), tmp.end(), c.begin());
}
static void push_front(Container& c, const_reference x) { c.push_front(x); }
};
// TODO: specialize for List (singly-linked list)
template<class T>
class SizeStorage<vector<T> >
{
public:
typedef vector<T> Container;
typedef SizeStorage<Container> Self;
SizeStorage() {}
SizeStorage(size_t) {}
Self& operator+=(size_t) { return *this; }
Self& operator-=(size_t) { return *this; }
Self& operator++() { return *this; }
Self operator++(int) { return *this; }
Self& operator--() { return *this; }
Self operator--(int) { return *this; }
size_t size(const Container& c) const { return c.size(); }
void swap(SizeStorage&) {}
void clear() {}
};
template<class T>
class SizeStorage<deque<T> >
{
public:
typedef deque<T> Container;
typedef SizeStorage<Container> Self;
SizeStorage() {}
SizeStorage(size_t) {}
Self& operator+=(size_t) { return *this; }
Self& operator-=(size_t) { return *this; }
Self& operator++() { return *this; }
Self operator++(int) { return *this; }
Self& operator--() { return *this; }
Self operator--(int) { return *this; }
size_t size(const Container& c) const { return c.size(); }
void swap(SizeStorage&) {}
void clear() {}
};
#endif // __CONTAINERS_H__