OpenDDS::DCPS::DisjointSequence::OrderedRanges< T > Class Template Reference

#include <DisjointSequence.h>

Public Types
typedef std::pair< T, T >	TPair
typedef bool(*	Compare) (const TPair &, const TPair &)
typedef Container::size_type	size_type
typedef Container::const_iterator	const_iterator
typedef const_iterator	iterator
typedef Container::const_reverse_iterator	const_reverse_iterator
typedef const_reverse_iterator	reverse_iterator

Public Member Functions
typedef	OPENDDS_SET_CMP (TPair, Compare) Container
	OrderedRanges ()
const_iterator	begin () const
const_iterator	cbegin () const
const_iterator	end () const
const_iterator	cend () const
const_reverse_iterator	rbegin () const
const_reverse_iterator	crbegin () const
const_reverse_iterator	rend () const
const_reverse_iterator	crend () const
bool	empty () const
size_type	size () const
void	clear ()
void	add (T lower, T upper)
void	add (T value)
void	remove (T value)
T	pop_front ()
bool	has (T lower, T upper) const
bool	has (const TPair &range) const
bool	has (T value) const
bool	has_any (T lower, T upper) const
bool	has_any (const TPair &range) const

Static Public Member Functions
static bool	range_less (const TPair &lhs, const TPair &rhs)

Private Member Functions
const_iterator	lower_bound (const TPair &p) const
const_iterator	lower_bound (T t) const
Container::iterator	lower_bound_i (T t)
const_iterator	upper_bound (const TPair &p) const
const_iterator	upper_bound (T t) const
void	remove_i (typename Container::iterator iter, T value)

Private Attributes
Container	ranges_

Friends
class	DisjointSequence
template<typename Type >
bool	operator== (const OrderedRanges< Type > &a, const OrderedRanges< Type > &b)

Detailed Description

template<typename T>
class OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >

Core data structure of DisjointSequence: Use a balanced binary tree (std::set) to store a list of ranges (std::pair of T). Maintain invariants (in addition to those from std::set):

• For any element x of the set, x.second >= x.first
• No adjacent or overlapping ranges. Given two elements ordered "x before y", y.first > x.second + 1 Common non-mutating operations on the underlying set are public members of this class. Note that due to this design, size() is the number of contiguous ranges, not individual values. Some mutating operations on the underlying set that can't violate the invariants are also provided (like clear). Type T needs to support value-initialization, construction from int, copying, addition, subtraction, and comparison using == and <.

Definition at line 125 of file DisjointSequence.h.

Member Typedef Documentation

Compare

template<typename T>

typedef bool(* OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::Compare) (const TPair &, const TPair &)

Definition at line 128 of file DisjointSequence.h.

const_iterator

template<typename T>

typedef Container::const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::const_iterator

Definition at line 131 of file DisjointSequence.h.

const_reverse_iterator

template<typename T>

typedef Container::const_reverse_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::const_reverse_iterator

Definition at line 133 of file DisjointSequence.h.

iterator

template<typename T>

typedef const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::iterator

Definition at line 132 of file DisjointSequence.h.

reverse_iterator

template<typename T>

typedef const_reverse_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::reverse_iterator

Definition at line 134 of file DisjointSequence.h.

size_type

template<typename T>

typedef Container::size_type OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::size_type

Definition at line 130 of file DisjointSequence.h.

TPair

template<typename T>

typedef std::pair<T, T> OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::TPair

Definition at line 127 of file DisjointSequence.h.

Constructor & Destructor Documentation

OrderedRanges()

template<typename T>

OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::OrderedRanges ( )

inline

Definition at line 141 of file DisjointSequence.h.

      : ranges_(range_less)
    {}

Member Function Documentation

add() [1/2]

template<typename T>

void OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::add ( T  lower, T  upper  )

inline

Definition at line 161 of file DisjointSequence.h.

Referenced by OpenDDS::XTypes::DynamicDataImpl::insert_valid_discriminator(), OpenDDS::Security::XmlUtils::parse_domain_id_set(), and OpenDDS::DCPS::DomainParticipantImpl::return_handle().

    {
      OPENDDS_ASSERT(upper >= lower);
      if (has(lower, upper)) {
        return;
      }

      const T above = upper + 1;
      for (typename Container::iterator i = lower_bound_i(lower - 1);
          i != ranges_.end() && (i->first <= above || i->second <= above);
          /* iterate in loop because of removal */) {
        lower = (std::min)(lower, i->first);
        upper = (std::max)(upper, i->second);
        ranges_.erase(i++);
      }

      ranges_.insert(TPair(lower, upper));
    }

add() [2/2]

template<typename T>

void OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::add ( T  value )

inline

Definition at line 180 of file DisjointSequence.h.

    {
      add(value, value);
    }

begin()

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::begin ( void  ) const

inline

Definition at line 145 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::cumulative_ack(), OpenDDS::DCPS::DisjointSequence::dump(), OpenDDS::DCPS::DisjointSequence::fill_bitmap_range(), OpenDDS::DCPS::DisjointSequence::insert_filtered(), OpenDDS::XTypes::DynamicDataImpl::insert_valid_discriminator(), OpenDDS::DCPS::DisjointSequence::low(), and OpenDDS::DCPS::DisjointSequence::to_bitmap().

{ return ranges_.begin(); }

cbegin()

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::cbegin ( ) const

inline

Definition at line 146 of file DisjointSequence.h.

{ return ranges_.begin(); }

cend()

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::cend ( ) const

inline

Definition at line 149 of file DisjointSequence.h.

{ return ranges_.end(); }

clear()

template<typename T>

void OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::clear ( void  )

inline

Definition at line 159 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::reset().

{ ranges_.clear(); }

crbegin()

template<typename T>

const_reverse_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::crbegin ( ) const

inline

Definition at line 152 of file DisjointSequence.h.

{ return ranges_.rbegin(); }

crend()

template<typename T>

const_reverse_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::crend ( ) const

inline

Definition at line 155 of file DisjointSequence.h.

{ return ranges_.rend(); }

empty()

template<typename T>

bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::empty ( void  ) const

inline

Definition at line 157 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DomainParticipantImpl::assign_handle(), OpenDDS::DCPS::DisjointSequence::cumulative_ack(), OpenDDS::DCPS::DisjointSequence::empty(), OpenDDS::DCPS::DisjointSequence::insert_bitmap_range(), OpenDDS::XTypes::DynamicDataImpl::insert_valid_discriminator(), OpenDDS::DCPS::DisjointSequence::last_ack(), and OpenDDS::Security::XmlUtils::parse_domain_id_set().

{ return ranges_.empty(); }

end()

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::end ( void  ) const

inline

Definition at line 148 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::dump(), OpenDDS::DCPS::DisjointSequence::fill_bitmap_range(), OpenDDS::DCPS::DisjointSequence::insert_filtered(), and OpenDDS::DCPS::DisjointSequence::to_bitmap().

{ return ranges_.end(); }

has() [1/3]

template<typename T>

bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::has ( T  lower, T  upper  ) const

inline

Definition at line 201 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::insert_filtered().

    {
      const const_iterator iter = lower_bound(upper);
      return iter != end() && !(lower < iter->first);
    }

has() [2/3]

template<typename T>

bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::has ( const TPair &  range ) const

inline

Definition at line 207 of file DisjointSequence.h.

    {
      return has(range.first, range.second);
    }

has() [3/3]

template<typename T>

bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::has ( T  value ) const

inline

Definition at line 212 of file DisjointSequence.h.

    {
      return has(value, value);
    }

has_any() [1/2]

template<typename T>

bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::has_any ( T  lower, T  upper  ) const

inline

Definition at line 217 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::insert_filtered().

    {
      const const_iterator iter = lower_bound(lower);
      return iter != end() && !(upper < iter->first);
    }

has_any() [2/2]

template<typename T>

bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::has_any ( const TPair &  range ) const

inline

Definition at line 223 of file DisjointSequence.h.

    {
      return has_any(range.first, range.second);
    }

lower_bound() [1/2]

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::lower_bound ( const TPair &  p ) const

inlineprivate

Definition at line 232 of file DisjointSequence.h.

{ return ranges_.lower_bound(p); }

lower_bound() [2/2]

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::lower_bound ( T  t ) const

inlineprivate

Definition at line 234 of file DisjointSequence.h.

    {
      return ranges_.lower_bound(TPair(T() /*ignored*/, t));
    }

lower_bound_i()

template<typename T>

Container::iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::lower_bound_i ( T  t )

inlineprivate

Definition at line 240 of file DisjointSequence.h.

    {
      return ranges_.lower_bound(TPair(T() /*ignored*/, t));
    }

OPENDDS_SET_CMP()

template<typename T>

typedef OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::OPENDDS_SET_CMP	(	TPair	,
		Compare
	)

pop_front()

template<typename T>

T OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::pop_front ( )

inline

Definition at line 194 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DomainParticipantImpl::assign_handle().

    {
      const T value = begin()->first;
      remove_i(ranges_.begin(), value);
      return value;
    }

range_less()

template<typename T>

static bool OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::range_less ( const TPair &  lhs, const TPair &  rhs  )

inlinestatic

Definition at line 136 of file DisjointSequence.h.

    {
      return lhs.second < rhs.second;
    }

rbegin()

template<typename T>

const_reverse_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::rbegin ( void  ) const

inline

Definition at line 151 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::high(), and OpenDDS::DCPS::DisjointSequence::last_ack().

{ return ranges_.rbegin(); }

remove()

template<typename T>

void OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::remove ( T  value )

inline

Definition at line 185 of file DisjointSequence.h.

    {
      const typename Container::iterator iter = lower_bound_i(value);
      if (iter == end() || value < iter->first) {
        return;
      }
      remove_i(iter, value);
    }

remove_i()

template<typename T>

void OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::remove_i ( typename Container::iterator  iter, T  value  )

inlineprivate

Definition at line 253 of file DisjointSequence.h.

    {
      const TPair orig = *iter;
      ranges_.erase(iter);
      if (value == orig.first) {
        if (value < orig.second) {
          ranges_.insert(TPair(value + T(1), orig.second));
        }
      } else if (value == orig.second) {
        ranges_.insert(TPair(orig.first, value - T(1)));
      } else {
        ranges_.insert(TPair(orig.first, value - T(1)));
        ranges_.insert(TPair(value + T(1), orig.second));
      }
    }

rend()

template<typename T>

const_reverse_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::rend ( void  ) const

inline

Definition at line 154 of file DisjointSequence.h.

{ return ranges_.rend(); }

size()

template<typename T>

size_type OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::size ( void  ) const

inline

Definition at line 158 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::disjoint().

{ return ranges_.size(); }

upper_bound() [1/2]

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::upper_bound ( const TPair &  p ) const

inlineprivate

Definition at line 245 of file DisjointSequence.h.

{ return ranges_.upper_bound(p); }

upper_bound() [2/2]

template<typename T>

const_iterator OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::upper_bound ( T  t ) const

inlineprivate

Definition at line 247 of file DisjointSequence.h.

    {
      return ranges_.upper_bound(TPair(T() /*ignored*/, t));
    }

Friends And Related Function Documentation

DisjointSequence

template<typename T>

friend class DisjointSequence

friend

Definition at line 269 of file DisjointSequence.h.

operator==

template<typename T>

template<typename Type >

bool operator== ( const OrderedRanges< Type > &  a, const OrderedRanges< Type > &  b  )

friend

Member Data Documentation

ranges_

template<typename T>

Container OpenDDS::DCPS::DisjointSequence::OrderedRanges< T >::ranges_

private

Definition at line 270 of file DisjointSequence.h.

Referenced by OpenDDS::DCPS::DisjointSequence::erase(), OpenDDS::DCPS::DisjointSequence::insert(), OpenDDS::DCPS::DisjointSequence::insert_bitmap_range(), OpenDDS::DCPS::DisjointSequence::insert_i(), and OpenDDS::DCPS::operator==().

---

The documentation for this class was generated from the following file:

• DisjointSequence.h