IntervalSet.h
// IntervalSet.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2007
#pragma once
#ifndef Ceda_cxUtils_IntervalSet_H
#define Ceda_cxUtils_IntervalSet_H
#include "IntervalList.h"
#include "MakeIterator.h"
#include <iterator>
namespace ceda
{
// Adapts an IntervalList<T> to have the semantic of a set of T. Indeed intention is to be
// plug-in compatible with a std::set<T>
// Public inheritance is wrong in theory, useful in practise because we inherit functions that we
// don't chose to redefine with a different semantic.
template <typename T>
class IntervalSet : public IntervalList<T>
{
public:
//typedef T value_type;
ssize_t size() const
{
return IntervalList<T>::Extent();
}
/*
bool operator==(const IntervalSet<T>& rhs) const
{
return m_list == rhs.m_list;
}
bool operator<(const IntervalSet<T>& rhs) const
{
return m_list < rhs.m_list;
}
*/
class IteratorPolicy
{
public:
IteratorPolicy() : m_t(-1), m_ts(-1), m_te(-1) {}
IteratorPolicy(typename IntervalList<T>::const_iterator i, T t, T ts, T te) :
m_i(i),
m_t(t),
m_ts(ts),
m_te(te)
{
}
IteratorPolicy(const IteratorPolicy& rhs) :
m_i(rhs.m_i),
m_t(rhs.m_t),
m_ts(rhs.m_ts),
m_te(rhs.m_te)
{
}
typedef std::bidirectional_iterator_tag iterator_category;
typedef T value_type;
// We don't have any concept of a pointer type, but this is needed to avoid compilation
// errors.
typedef void* pointer;
typedef const void* const_pointer;
typedef std::ptrdiff_t difference_type;
// Normally 'reference' would be a T&. However we instead want operator*() to return
// a T by value because the container doesn't materialise the elements.
// This actually allows the std::reverse_iterator<> adapter to be used successfully!
typedef T reference;
typedef T const_reference;
bool operator==(const IteratorPolicy& rhs) const { return m_t == rhs.m_t; }
bool operator<(const IteratorPolicy& rhs) const { return m_t < rhs.m_t; }
void next()
{
cxAssert(m_t != m_te);
if (++m_t == m_i->t2)
{
if (m_t != m_te)
{
++m_i;
m_t = m_i->t1;
}
}
}
void prev()
{
cxAssert(m_t != m_ts);
if (--m_t < m_i->t1)
{
if (m_t != m_ts)
{
--m_i;
m_t = m_i->t2-1;
}
}
}
// const_deref() would normally return a reference to a materialised element in the
// container, but this is not possible because the elements of type T are recorded
// indirectly using half open intervals. Therefore we must return by value which is ok
// because T is cheap to copy (never mind the fact that compilers now tend to use RVO).
// For this reason we use make_const_iterator2 instead of make_const_iterator which
// implements operator*() differently - returning a T by value instead of by const
// reference.
// It is not permissible to return a reference to the element m_t stored in the iterator
// itsef, because the iterator could be a temporary in client code and go out of scope
// before m_t is accessed. (see discussion below for the std::reverse_iterator<> adapter).
value_type const_deref() const
{
cxAssert(m_t != m_ts);
cxAssert(m_t != m_te);
return m_t;
}
typename IntervalList<T>::const_iterator GetIntervalListIterator() const { return m_i; }
T GetIntervalPosition() const { return m_t; }
private:
typename IntervalList<T>::const_iterator m_i; // points at the current interval we're on
T m_t; // current position in T coords
T m_ts; // One before first legal position for t
T m_te; // One after last legal position for t
};
typedef make_const_iterator<IteratorPolicy> const_iterator;
const_iterator begin() const
{
return const_iterator(IntervalList<T>::empty() ?
IteratorPolicy() :
IteratorPolicy(
IntervalList<T>::begin(),
IntervalList<T>::front().t1,
IntervalList<T>::front().t1-1,
IntervalList<T>::back().t2));
}
const_iterator end() const
{
return const_iterator(IntervalList<T>::empty() ?
IteratorPolicy() :
IteratorPolicy(
IntervalList<T>::end()-1,
IntervalList<T>::back().t2,
IntervalList<T>::front().t1-1,
IntervalList<T>::back().t2));
}
/*
The std::reverse_iterator<> adapter can't be used unless we define 'reference' to be the same
as 'value_type' because otherwise it assumes operator*() returns a reference to a
materialised element in the container. We can't use the trick of instead returning a
reference to a materialised element stored in the iterator itself because the iterator may
be a temporary. Indeed reverse_iterator::operator*() is written as follows:
template<typename _RanIt>
class reverse_iterator : public _Iterator_base_secure
{
reference operator*() const
{
_RanIt _Tmp = current;
return (*--_Tmp);
}
protected:
_RanIt current; // the wrapped iterator
};
*/
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
};
template <typename T>
IntervalList<T>& AsList(IntervalSet<T>& x)
{
return static_cast<IntervalList<T>&>(x);
}
template <typename T>
const IntervalList<T>& AsList(const IntervalSet<T>& x)
{
return static_cast<const IntervalList<T>&>(x);
}
template <typename T>
IntervalSet<T>& AsSet(IntervalList<T>& x)
{
return static_cast<IntervalSet<T>&>(x);
}
template <typename T>
const IntervalSet<T>& AsSet(const IntervalList<T>& x)
{
return static_cast<const IntervalSet<T>&>(x);
}
/*
// Calculate set-theoretic intersection of x and y.
// Efficient to return by value assuming RVO
IntervalSet Intersection(const IntervalSet& x, const IntervalSet& y)
{
IntervalList result;
< Iterate through intervals in AsList(x), AsList(y)
and add intersections of intervals to result >
return AsSet(result);
}
*/
} // namespace ceda
#endif // include guard