coco
97 lines
3.0 KiB
C++
97 lines
3.0 KiB
C++
// Copyright (C) 2011 Davis E. King (davis@dlib.net)
|
|
// License: Boost Software License See LICENSE.txt for the full license.
|
|
#undef DLIB_DISJOINT_SUBsETS_ABSTRACT_Hh_
|
|
#ifdef DLIB_DISJOINT_SUBsETS_ABSTRACT_Hh_
|
|
|
|
#include <vector>
|
|
#include "../algs.h"
|
|
|
|
namespace dlib
|
|
{
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
class disjoint_subsets
|
|
{
|
|
/*!
|
|
INITIAL VALUE
|
|
- size() == 0
|
|
|
|
WHAT THIS OBJECT REPRESENTS
|
|
This object represents a set of integers which is partitioned into
|
|
a number of disjoint subsets. It supports the two fundamental operations
|
|
of finding which subset a particular integer belongs to as well as
|
|
merging subsets.
|
|
!*/
|
|
public:
|
|
|
|
void clear (
|
|
) noexcept;
|
|
/*!
|
|
ensures
|
|
- #size() == 0
|
|
- returns this object to its initial value
|
|
!*/
|
|
|
|
void set_size (
|
|
unsigned long new_size
|
|
);
|
|
/*!
|
|
ensures
|
|
- #size() == new_size
|
|
- for all valid i:
|
|
- #find_set(i) == i
|
|
(i.e. this object contains new_size subsets, each containing exactly one element)
|
|
!*/
|
|
|
|
size_t size (
|
|
) const noexcept;
|
|
/*!
|
|
ensures
|
|
- returns the total number of integer elements represented
|
|
by this object.
|
|
!*/
|
|
|
|
unsigned long find_set (
|
|
unsigned long item
|
|
) const;
|
|
/*!
|
|
requires
|
|
- item < size()
|
|
ensures
|
|
- Each disjoint subset can be represented by any of its elements (since
|
|
the sets are all disjoint). In particular, for each subset we define
|
|
a special "representative element" which is used to represent it.
|
|
Therefore, this function returns the representative element for the
|
|
set which contains item.
|
|
- find_set(find_set(item)) == find_set(item)
|
|
- Note that if A and B are both elements of the same subset then we always
|
|
have find_set(A) == find_set(B).
|
|
!*/
|
|
|
|
unsigned long merge_sets (
|
|
unsigned long a,
|
|
unsigned long b
|
|
);
|
|
/*!
|
|
requires
|
|
- a != b
|
|
- a < size()
|
|
- b < size()
|
|
- find_set(a) == a
|
|
(i.e. a is the representative element of some set)
|
|
- find_set(b) == b
|
|
(i.e. b is the representative element of some set)
|
|
ensures
|
|
- #find_set(a) == #find_set(b)
|
|
(i.e. merges the set's containing a and b)
|
|
- returns #find_set(a)
|
|
!*/
|
|
};
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
}
|
|
|
|
#endif // DLIB_DISJOINT_SUBsETS_ABSTRACT_Hh_
|