Public Types | Public Member Functions | Private Member Functions | Private Attributes

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

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

#include <set.hh>

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

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

Definition at line 81 of file util/set.hh.


Member Typedef Documentation

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

Backward iterator associated type.

Definition at line 93 of file util/set.hh.

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

Definition at line 174 of file object.hh.

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

Iterator associated type.

Definition at line 96 of file util/set.hh.

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

Element associated type.

Definition at line 86 of file util/set.hh.

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

Definition at line 173 of file object.hh.

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

Forward iterator associated type.

Definition at line 90 of file util/set.hh.


Constructor & Destructor Documentation

template<typename T >
mln::util::set< T >::set (  )  [inline]

Constructor without arguments.

Definition at line 348 of file util/set.hh.

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

Definition at line 390 of file util/set.hh.

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]
template<typename T >
const T mln::util::set< T >::first_element (  )  const [inline]

Return the first element of the set.

Precondition:
not is_empty()

Definition at line 427 of file util/set.hh.

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_).

Definition at line 470 of file util/set.hh.

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.

Definition at line 445 of file util/set.hh.

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.

Definition at line 367 of file util/set.hh.

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.

Definition at line 356 of file util/set.hh.

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]
template<typename T >
bool mln::util::set< T >::is_frozen_ (  )  const [inline]

Test if the set is frozen.

Definition at line 502 of file util/set.hh.

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()

Definition at line 436 of file util/set.hh.

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.

Definition at line 494 of file util/set.hh.

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]
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.

Definition at line 417 of file util/set.hh.

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.

Definition at line 380 of file util/set.hh.

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.

Definition at line 461 of file util/set.hh.

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.

Definition at line 482 of file util/set.hh.

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]

Member Data Documentation

template<typename T>
bool mln::util::set< T >::frozen_ [mutable, private]
template<typename T>
std::set< T, util::ord<T> > mln::util::set< T >::s_ [mutable, private]
template<typename T>
std::vector<T> mln::util::set< T >::v_ [mutable, private]