mln::util::set< T > Class Template Reference [Utilities]

An "efficient" mathematical set class. More...

#include <set.hh>

Inheritance diagram for mln::util::set< T >:

List of all members.

Public Types
typedef set_bkd_iter< T >	bkd_eiter
	Backward iterator associated type.
typedef Object< void >	category
typedef fwd_eiter	eiter
	Iterator associated type.
typedef T	element
	Element associated type.
typedef mln::util::set< T >	exact_t
typedef set_fwd_iter< T >	fwd_eiter
	Forward iterator associated type.
Public Member Functions
void	clear ()
	Empty the set.
const T	first_element () const
	Return the first element of the set.
bool	has (const T &elt) const
	Test if the object elt belongs to the set.
set< T > &	insert (const T &elt)
	Insert an element elt into the set.
template<typename U >
set< T > &	insert (const set< U > &other)
	Insert the elements of other into the set.
bool	is_empty () const
	Test if the set is empty.
bool	is_frozen_ () const
	Test if the set is frozen.
const T	last_element () const
	Return the last element of the set.
std::size_t	memory_size () const
	Return the size of this set in memory.
unsigned	nelements () const
	Return the number of elements of the set.
const T &	operator[] (unsigned i) const
	Return the i-th element of the set.
set< T > &	remove (const T &elt)
	Remove an element elt into the set.
	set ()
	Constructor without arguments.
const std::vector< T > &	std_vector () const
	Give access to the set elements.
Private Member Functions
unsigned	dicho_ (const T &elt, unsigned beg, unsigned end) const
void	freeze_ () const
	Freeze the contents of the set (update v_ from s_, then clear s_).
void	unfreeze_ () const
	Unfreeze the contents of the set.
bool	v_has_ (const T &elt) const
Private Attributes
bool	frozen_
	Tell if the set is frozen.
std::set< T, util::ord< T > >	s_
	Set of elements.
std::vector< T >	v_
	Array of elements.

---

Detailed Description

template<typename T>
class mln::util::set< T >

An "efficient" mathematical set class.

This set class is designed to store a mathematical set and to present it to the user as a linear array (std::vector).

Elements are stored by copy. Implementation is lazy.

The set has two states: frozen or not. There is an automatic switch of state when the user modifies its contents (insert, remove, or clear) or access to its contents (op[i]).

The parameter T is the element type, which shall not be const-qualified.

The unicity of set elements is handled by the mln::util::ord mechanism.

See also:

mln::util::ord

---

Member Typedef Documentation

template<typename T>

typedef set_bkd_iter<T> mln::util::set< T >::bkd_eiter

Backward iterator associated type.

typedef Object<void> mln::Object< mln::util::set< T > >::category [inherited]

template<typename T>

typedef fwd_eiter mln::util::set< T >::eiter

Iterator associated type.

template<typename T>

typedef T mln::util::set< T >::element

Element associated type.

typedef mln::util::set< T > mln::Object< mln::util::set< T > >::exact_t [inherited]

template<typename T>

typedef set_fwd_iter<T> mln::util::set< T >::fwd_eiter

Forward iterator associated type.

---

Constructor & Destructor Documentation

template<typename T >

mln::util::set< T >::set

(

)

[inline]

Constructor without arguments.

References mln::util::set< T >::frozen_.

---

Member Function Documentation

template<typename T >

void mln::util::set< T >::clear

(

)

[inline]

Empty the set.

All elements contained in the set are destroyed so the set is emptied.

Postcondition:

is_empty() == true

References mln::util::set< T >::frozen_, mln::util::set< T >::is_empty(), mln::util::set< T >::s_, and mln::util::set< T >::v_.

Referenced by mln::window< D >::clear(), mln::p_set_of< S >::clear(), mln::p_set< P >::clear(), and mln::p_key< K, P >::clear().

template<typename T>

unsigned mln::util::set< T >::dicho_	(	const T &	elt,
		unsigned	beg,
		unsigned	end
	)			const [inline, private]

References mln::util::set< T >::frozen_, mln::util::ord_strict(), and mln::util::set< T >::v_.

Referenced by mln::util::set< T >::v_has_().

template<typename T >

const T mln::util::set< T >::first_element

(

)

const [inline]

Return the first element of the set.

Precondition:

not is_empty()

References mln::util::set< T >::frozen_, mln::util::set< T >::is_empty(), mln::util::set< T >::s_, and mln::util::set< T >::v_.

template<typename T >

void mln::util::set< T >::freeze_

(

)

const [inline, private]

Freeze the contents of the set (update v_ from s_, then clear s_).

References mln::util::set< T >::frozen_, mln::util::set< T >::s_, and mln::util::set< T >::v_.

Referenced by mln::util::set< T >::operator[](), and mln::util::set< T >::std_vector().

template<typename T>

bool mln::util::set< T >::has

(

const T &

elt

)

const [inline]

Test if the object elt belongs to the set.

Parameters:

[in]

elt

A possible element of the set.

Returns:

True is elt is in the set.

References mln::util::set< T >::frozen_, mln::util::set< T >::s_, and mln::util::set< T >::v_has_().

Referenced by mln::p_key< K, P >::exists_key(), mln::window< D >::has(), mln::p_set_of< S >::has(), mln::p_set< P >::has(), mln::p_key< K, P >::insert(), mln::window< D >::is_centered(), mln::p_key< K, P >::remove(), and mln::p_key< K, P >::set_2_().

template<typename T >

template<typename U >

set< T > & mln::util::set< T >::insert

(

const set< U > &

other

)

[inline]

Insert the elements of other into the set.

Parameters:

[in]

other

The set containing the elements to be inserted.

Returns:

The set itself after insertion.

References mln::util::set< T >::frozen_, mln::util::set< T >::is_empty(), mln::util::set< T >::s_, mln::util::set< T >::std_vector(), and mln::util::set< T >::unfreeze_().

template<typename T>

set< T > & mln::util::set< T >::insert

(

const T &

elt

)

[inline]

Insert an element elt into the set.

Parameters:

[in]

elt

The element to be inserted.

If elt is already in the set, this method is a no-op.

Returns:

The set itself after insertion.

References mln::util::set< T >::frozen_, mln::util::set< T >::s_, and mln::util::set< T >::unfreeze_().

Referenced by mln::p_key< K, P >::change_key(), mln::p_key< K, P >::change_keys(), mln::window< D >::insert(), mln::p_set_of< S >::insert(), mln::p_set< P >::insert(), mln::p_key< K, P >::insert(), and mln::p_key< K, P >::unsafe_insert_().

template<typename T >

bool mln::util::set< T >::is_empty

(

)

const [inline]

Test if the set is empty.

References mln::util::set< T >::nelements().

Referenced by mln::util::set< T >::clear(), mln::util::set< T >::first_element(), mln::util::set< T >::insert(), mln::window< D >::is_empty(), mln::util::set< T >::last_element(), mln::p_key< K, P >::run_(), and mln::util::set< T >::v_has_().

template<typename T >

bool mln::util::set< T >::is_frozen_

(

)

const [inline]

Test if the set is frozen.

References mln::util::set< T >::frozen_.

template<typename T >

const T mln::util::set< T >::last_element

(

)

const [inline]

Return the last element of the set.

Precondition:

not is_empty()

References mln::util::set< T >::frozen_, mln::util::set< T >::is_empty(), mln::util::set< T >::s_, and mln::util::set< T >::v_.

template<typename T >

std::size_t mln::util::set< T >::memory_size

(

)

const [inline]

Return the size of this set in memory.

References mln::util::set< T >::nelements().

Referenced by mln::p_set_of< S >::memory_size(), and mln::p_set< P >::memory_size().

template<typename T >

unsigned mln::util::set< T >::nelements

(

)

const [inline]

Return the number of elements of the set.

References mln::util::set< T >::frozen_, mln::util::set< T >::s_, and mln::util::set< T >::v_.

Referenced by mln::p_set_of< S >::has(), mln::util::set< T >::is_empty(), mln::util::set< T >::memory_size(), mln::p_set_of< S >::nelements(), mln::p_set< P >::nsites(), mln::util::operator<<(), mln::util::operator==(), mln::util::set< T >::operator[](), mln::p_set_of< S >::operator[](), mln::p_key< K, P >::run_(), mln::window< D >::size(), and mln::util::set< T >::v_has_().

template<typename T >

const T & mln::util::set< T >::operator[]

(

unsigned

i

)

const [inline]

Return the i-th element of the set.

Parameters:

[in]

i

Index of the element to retrieve.

Precondition:

i < nelements()

The element is returned by reference and is constant.

References mln::util::set< T >::freeze_(), mln::util::set< T >::frozen_, mln::util::set< T >::nelements(), and mln::util::set< T >::v_.

template<typename T>

set< T > & mln::util::set< T >::remove

(

const T &

elt

)

[inline]

Remove an element elt into the set.

Parameters:

[in]

elt

The element to be inserted.

If elt is already in the set, this method is a no-op.

Returns:

The set itself after suppression.

References mln::util::set< T >::frozen_, mln::util::set< T >::s_, and mln::util::set< T >::unfreeze_().

Referenced by mln::p_key< K, P >::change_key(), mln::p_set< P >::remove(), mln::p_key< K, P >::remove(), and mln::p_key< K, P >::remove_key().

template<typename T >

const std::vector< T > & mln::util::set< T >::std_vector

(

)

const [inline]

Give access to the set elements.

The complexity of this method is O(1).

Postcondition:

The set is frozen.

Returns:

An array (std::vector) of elements.

References mln::util::set< T >::freeze_(), mln::util::set< T >::frozen_, and mln::util::set< T >::v_.

Referenced by mln::util::set< T >::insert(), mln::window< D >::std_vector(), and mln::p_set< P >::std_vector().

template<typename T >

void mln::util::set< T >::unfreeze_

(

)

const [inline, private]

Unfreeze the contents of the set.

References mln::util::set< T >::frozen_, mln::util::set< T >::s_, and mln::util::set< T >::v_.

Referenced by mln::util::set< T >::insert(), and mln::util::set< T >::remove().

template<typename T>

bool mln::util::set< T >::v_has_

(

const T &

elt

)

const [inline, private]

References mln::util::set< T >::dicho_(), mln::util::set< T >::frozen_, mln::util::set< T >::is_empty(), mln::util::set< T >::nelements(), mln::util::ord_strict(), and mln::util::set< T >::v_.

Referenced by mln::util::set< T >::has().

---

Member Data Documentation

template<typename T>

bool mln::util::set< T >::frozen_ [mutable, private]

Tell if the set is frozen.

Referenced by mln::util::set< T >::clear(), mln::util::set< T >::dicho_(), mln::util::set< T >::first_element(), mln::util::set< T >::freeze_(), mln::util::set< T >::has(), mln::util::set< T >::insert(), mln::util::set< T >::is_frozen_(), mln::util::set< T >::last_element(), mln::util::set< T >::nelements(), mln::util::set< T >::operator[](), mln::util::set< T >::remove(), mln::util::set< T >::set(), mln::util::set< T >::std_vector(), mln::util::set< T >::unfreeze_(), and mln::util::set< T >::v_has_().

template<typename T>

std::set< T, util::ord<T> > mln::util::set< T >::s_ [mutable, private]

Set of elements.

This structure is always up-to-date w.r.t. the set contents.

Referenced by mln::util::set< T >::clear(), mln::util::set< T >::first_element(), mln::util::set< T >::freeze_(), mln::util::set< T >::has(), mln::util::set< T >::insert(), mln::util::set< T >::last_element(), mln::util::set< T >::nelements(), mln::util::set< T >::remove(), and mln::util::set< T >::unfreeze_().

template<typename T>

std::vector<T> mln::util::set< T >::v_ [mutable, private]

Array of elements.

This structure is only updated (if required) when elements are accessed.

Referenced by mln::util::set< T >::clear(), mln::util::set< T >::dicho_(), mln::util::set< T >::first_element(), mln::util::set< T >::freeze_(), mln::util::set< T >::last_element(), mln::util::set< T >::nelements(), mln::util::set< T >::operator[](), mln::util::set< T >::std_vector(), mln::util::set< T >::unfreeze_(), and mln::util::set< T >::v_has_().