blob: ecc5ef0055bf34b359ccd5a2f3260796a64da927 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
// Copyright (C) 2011 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#undef DLIB_DISJOINT_SUBsETS_SIZED_ABSTRACT_Hh_
#ifdef DLIB_DISJOINT_SUBsETS_SIZED_ABSTRACT_Hh_
#include <vector>
#include "../algs.h"
namespace dlib
{
// ----------------------------------------------------------------------------------------
class disjoint_subsets_sized
{
/*!
INITIAL VALUE
- size() == 0
- get_number_of_sets() == 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. It also allows you to find out how big each subset is. It
is therefore essentially the same thing as dlib::disjoint_subsets, except
it also keeps track of of the size of each subset.
!*/
public:
void clear (
) noexcept;
/*!
ensures
- #size() == 0
- #get_number_of_sets() == 0
- returns this object to its initial value
!*/
void set_size (
unsigned long new_size
);
/*!
ensures
- #size() == new_size
- #get_number_of_sets() == new_size
- for all valid i:
- #find_set(i) == i
(i.e. this object contains new_size subsets, each containing exactly one element)
- #get_size_of_set(i) == 1
!*/
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)
- #get_size_of_set(#find_set(a)) == get_size_of_set(a) + get_size_of_set(b)
- #get_number_of_sets() == get_number_of_sets() - 1
- returns #find_set(a)
!*/
unsigned long get_number_of_sets (
) const noexcept;
/*!
ensures
- returns the current number of different subsets.
!*/
unsigned long get_size_of_set(
unsigned long item
) const;
/*!
requires
- item < size()
- find_set(item) == item
(i.e. item is the representative element of some set)
ensures
- returns the number of elements which belongs to the set where item is the representative element.
!*/
};
// ----------------------------------------------------------------------------------------
}
#endif // DLIB_DISJOINT_SUBsETS_ABSTRACT_Hh_
|
