Set of integers optimized for when the integers are concentrated in closed intervals. More...

#include <interval_set.h>

Inheritance diagram for sheaf::interval_set:

Friends
class	interval_set_iterator

SHEAF_DLL_SPEC size_t	deep_size (const interval_set &xset, bool xinclude_shallow)
	The deep size of the referenced object of type interval_set. More...

INTERVAL_SET FACET
typedef pod_index_type	pod_type
	The "plain old data" index type for this set. More...

	interval_set ()
	Default constructor. More...

	interval_set (const interval_set &xother)
	Copy constructor. More...

	~interval_set ()
	Destructor. More...

bool	operator== (const interval_set &xother) const
	True if this is equivalent to xother. More...

void	insert_interval (pod_type xbegin, pod_type xend)
	Insert an interval of members [xbegin, xend] into this set. More...

void	insert_member (pod_type xmbr)
	Insert xmbr into this set. More...

void	remove_interval (pod_type xbegin, pod_type xend)
	Remove an interval of members [xbegin, xend] from this set. More...

void	remove_member (pod_type xmbr)
	Remove xmbr from this set. More...

bool	contains_member (pod_type xmbr) const
	True, if the integer xmbr is in this set. More...

size_type	member_ct (pod_type xbegin, pod_type xend) const
	The number of members in the interval [xbegin, xend]. More...

bool	interval_is_empty (pod_type xbegin, pod_type xend) const
	True, if there are no members in this set for the interval [xbegin, xend]. More...

bool	interval_is_full (pod_type xbegin, pod_type xend) const
	True, if there is a continuous interval of members [xbegin, xend] in this set. More...

pod_type	begin () const
	The first member in this set. More...

pod_type	end () const
	The last member in this set. More...

void	clear ()
	Clear this set. More...

bool	is_empty () const
	True, if this set is empty. More...

interval_set_iterator *	iterator (bool xis_full_iterator) const
	Iterator for this set. If xis_full_iterator, iterate over the members in the set. Otherwise, iterate over the non-members in [begin(), end()]. More...

MAP FACET
typedef std::map< pod_type, bool >	map_type
	The type of the interval map. More...

typedef map_type::const_iterator	map_iterator_type
	The type of the interval map iterator. More...

const map_type &	interval_map () const
	Map that defines the intervals of this set. More...

bool	first_map_entry () const
	Value of the first map entry. More...

bool	last_map_entry () const
	Value of the last map entry. More...

ANY FACET
virtual bool	is_ancestor_of (const any *other) const
	Conformance test; true if other conforms to this. More...

virtual interval_set *	clone () const
	Virtual constructor, makes a new instance of the same type as this. More...

interval_set &	operator= (const interval_set &xother)
	Assignment operator. More...

virtual bool	invariant () const
	Class invariant. More...

Additional Inherited Members
Public Member Functions inherited from sheaf::any
bool	is_same_type (const any *other) const
	True if other is the same type as this. More...

virtual	~any ()
	Destructor. More...

bool	invariant_check () const
	True if invariant checking is enabled. More...

void	enable_invariant_check () const
	Enable invariant checking. More...

void	disable_invariant_check () const
	Disable invariant check. Intended for preventing recursive calls to invariant and for suppressing invariant checking during multi-phase initialization. More...

int	disable_invariance_check_request_depth () const
	Number of times disable_invariant_check has been called without matching call to enable_invariant_check. More...

Protected Member Functions inherited from sheaf::any
	any ()
	default constructor More...

Detailed Description

Set of integers optimized for when the integers are concentrated in closed intervals.

Definition at line 70 of file interval_set.h.

Member Typedef Documentation

◆ map_iterator_type

typedef map_type::const_iterator sheaf::interval_set::map_iterator_type

The type of the interval map iterator.

Definition at line 203 of file interval_set.h.

◆ map_type

typedef std::map<pod_type, bool> sheaf::interval_set::map_type

The type of the interval map.

Definition at line 198 of file interval_set.h.

◆ pod_type

typedef pod_index_type sheaf::interval_set::pod_type

The "plain old data" index type for this set.

Definition at line 86 of file interval_set.h.

Constructor & Destructor Documentation

◆ interval_set() [1/2]

sheaf::interval_set::interval_set ( )

Default constructor.

Postcondition

invariant()

Definition at line 35 of file interval_set.cc.

◆ interval_set() [2/2]

sheaf::interval_set::interval_set ( const interval_set & xother )

Copy constructor.

Postcondition

*this == xother

Definition at line 51 of file interval_set.cc.

References ~interval_set().

◆ ~interval_set()

sheaf::interval_set::~interval_set ( )

Destructor.

Definition at line 69 of file interval_set.cc.

References operator==().

Referenced by interval_set().

Member Function Documentation

◆ begin()

sheaf::interval_set::pod_type sheaf::interval_set::begin ( ) const

The first member in this set.

Postcondition

is_empty() ? !is_valid(result) : true

Definition at line 305 of file interval_set.cc.

References end(), sheaf::invalid_pod_index(), and sheaf::is_valid().

Referenced by interval_is_full(), sheaf::operator<<(), and sheaf::primary_sum_index_space_state::update_extrema().

◆ clear()

void sheaf::interval_set::clear ( )

Clear this set.

Postcondition

invariant()

is_empty()

Definition at line 364 of file interval_set.cc.

References is_empty().

Referenced by sheaf::primary_sum_index_space_state::clear(), and end().

◆ clone()

sheaf::interval_set * sheaf::interval_set::clone ( ) const

virtual

Virtual constructor, makes a new instance of the same type as this.

Postcondition

result != 0

result->is_empty()

Reimplemented from sheaf::any.

Definition at line 670 of file interval_set.cc.

References is_empty(), and operator=().

Referenced by is_ancestor_of().

◆ contains_member()

bool sheaf::interval_set::contains_member ( pod_type xmbr ) const

True, if the integer xmbr is in this set.

Definition at line 185 of file interval_set.cc.

References member_ct().

Referenced by sheaf::primary_sum_index_space_state::contains(), sheaf::primary_sum_index_space_state::contains_glued_hub(), sheaf::primary_sum_index_space_state::contains_unglued_hub(), sheaf::primary_sum_index_space_state::delete_id(), and remove_member().

◆ end()

sheaf::interval_set::pod_type sheaf::interval_set::end ( ) const

The last member in this set.

Postcondition

is_empty() ? !is_valid(result) : true

Definition at line 333 of file interval_set.cc.

References clear(), sheaf::invalid_pod_index(), and sheaf::is_valid().

Referenced by begin(), sheaf::operator<<(), and sheaf::primary_sum_index_space_state::update_extrema().

◆ first_map_entry()

bool sheaf::interval_set::first_map_entry ( ) const

Value of the first map entry.

Precondition

!is_empty()

Definition at line 602 of file interval_set.cc.

References last_map_entry().

Referenced by interval_map().

◆ insert_interval()

void sheaf::interval_set::insert_interval	(	pod_type	xbegin,
		pod_type	xend
	)

Insert an interval of members [xbegin, xend] into this set.

Postcondition

invariant()

interval_is_full(xbegin, xend)

Definition at line 105 of file interval_set.cc.

References insert_member().

Referenced by sheaf::primary_sum_index_space_state::extend_last_term(), sheaf::primary_sum_index_space_state::new_primary_term(), and operator==().

◆ insert_member()

void sheaf::interval_set::insert_member ( pod_type xmbr )

Insert xmbr into this set.

Postcondition

invariant()

contains_member(xmbr)

Definition at line 125 of file interval_set.cc.

References remove_interval().

Referenced by insert_interval(), and sheaf::primary_sum_index_space_state::new_id().

◆ interval_is_empty()

bool sheaf::interval_set::interval_is_empty	(	pod_type	xbegin,
		pod_type	xend
	)		const

True, if there are no members in this set for the interval [xbegin, xend].

Definition at line 259 of file interval_set.cc.

References interval_is_full().

Referenced by sheaf::primary_sum_index_space_state::interval_is_empty(), and member_ct().

◆ interval_is_full()

bool sheaf::interval_set::interval_is_full	(	pod_type	xbegin,
		pod_type	xend
	)		const

True, if there is a continuous interval of members [xbegin, xend] in this set.

Definition at line 282 of file interval_set.cc.

References begin().

Referenced by interval_is_empty(), and sheaf::primary_sum_index_space_state::interval_is_full().

◆ interval_map()

const sheaf::interval_set::map_type & sheaf::interval_set::interval_map ( ) const

Map that defines the intervals of this set.

Definition at line 595 of file interval_set.cc.

References first_map_entry().

Referenced by iterator(), and sheaf::primary_sum_index_space_state::update_gathered_id_space().

◆ invariant()

bool sheaf::interval_set::invariant ( ) const

virtual

Class invariant.

Invariant

any::invariant()

is_empty() || !first_map_entry()

for( map_iterator_type itr = interval_map().begin(); pod_type i=0 ; itr != interval_map().end() ; ++itr; ++i ) itr->second == (i%2 == 1)

is_empty() || last_map_entry()

Reimplemented from sheaf::any.

Definition at line 709 of file interval_set.cc.

Referenced by operator=().

◆ is_ancestor_of()

bool sheaf::interval_set::is_ancestor_of ( const any * other ) const

virtual

Conformance test; true if other conforms to this.

Precondition

other != 0

Reimplemented from sheaf::any.

Definition at line 651 of file interval_set.cc.

References clone().

Referenced by last_map_entry().

◆ is_empty()

bool sheaf::interval_set::is_empty ( ) const

True, if this set is empty.

Postcondition

is_basic_query

Definition at line 384 of file interval_set.cc.

References iterator().

Referenced by clear(), and clone().

◆ iterator()

sheaf::interval_set_iterator * sheaf::interval_set::iterator ( bool xis_full_iterator ) const

Iterator for this set. If xis_full_iterator, iterate over the members in the set. Otherwise, iterate over the non-members in [begin(), end()].

Definition at line 405 of file interval_set.cc.

References interval_map().

Referenced by sheaf::hub_index_space_iterator::attach_to(), is_empty(), and sheaf::operator<<().

◆ last_map_entry()

bool sheaf::interval_set::last_map_entry ( ) const

Value of the last map entry.

Precondition

!is_empty()

Definition at line 621 of file interval_set.cc.

References is_ancestor_of().

Referenced by first_map_entry().

◆ member_ct()

sheaf::size_type sheaf::interval_set::member_ct	(	pod_type	xbegin,
		pod_type	xend
	)		const

The number of members in the interval [xbegin, xend].

Definition at line 208 of file interval_set.cc.

References interval_is_empty().

Referenced by sheaf::primary_sum_index_space_state::clear_ids(), contains_member(), and sheaf::primary_sum_index_space_state::remove_term().

◆ operator=()

sheaf::interval_set & sheaf::interval_set::operator= ( const interval_set & xother )

Assignment operator.

Postcondition

*this == xother

Definition at line 690 of file interval_set.cc.

References invariant().

Referenced by clone().

◆ operator==()

bool sheaf::interval_set::operator== ( const interval_set & xother ) const

True if this is equivalent to xother.

Definition at line 86 of file interval_set.cc.

References insert_interval().

Referenced by ~interval_set().

◆ remove_interval()

void sheaf::interval_set::remove_interval	(	pod_type	xbegin,
		pod_type	xend
	)

Remove an interval of members [xbegin, xend] from this set.

Postcondition

invariant()

interval_is_empty(xbegin, xend)

Definition at line 145 of file interval_set.cc.

References remove_member().

Referenced by sheaf::primary_sum_index_space_state::clear_ids(), insert_member(), and sheaf::primary_sum_index_space_state::remove_term().

◆ remove_member()

void sheaf::interval_set::remove_member ( pod_type xmbr )

Remove xmbr from this set.

Postcondition

invariant()

!contains_member(xmbr)

Definition at line 165 of file interval_set.cc.

References contains_member().

Referenced by sheaf::primary_sum_index_space_state::delete_id(), and remove_interval().

Friends And Related Function Documentation

◆ deep_size

SHEAF_DLL_SPEC size_t deep_size	(	const interval_set &	xset,
		bool	xinclude_shallow
	)

friend

The deep size of the referenced object of type interval_set.

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

Friends

INTERVAL_SET FACET

MAP FACET

ANY FACET

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ map_iterator_type

◆ map_type

◆ pod_type

Constructor & Destructor Documentation

◆ interval_set() [1/2]

◆ interval_set() [2/2]

◆ ~interval_set()

Member Function Documentation

◆ begin()

◆ clear()

◆ clone()

◆ contains_member()

◆ end()

◆ first_map_entry()

◆ insert_interval()

◆ insert_member()

◆ interval_is_empty()

◆ interval_is_full()

◆ interval_map()

◆ invariant()

◆ is_ancestor_of()

◆ is_empty()

◆ iterator()

◆ last_map_entry()

◆ member_ct()

◆ operator=()

◆ operator==()

◆ remove_interval()

◆ remove_member()

Friends And Related Function Documentation

◆ deep_size