Frobby
0.9.1
src
Partition.cpp
Go to the documentation of this file.
1
/* Frobby: Software for monomial ideal computations.
2
Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
4
This program is free software; you can redistribute it and/or modify
5
it under the terms of the GNU General Public License as published by
6
the Free Software Foundation; either version 2 of the License, or
7
(at your option) any later version.
8
9
This program is distributed in the hope that it will be useful,
10
but WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
GNU General Public License for more details.
13
14
You should have received a copy of the GNU General Public License
15
along with this program. If not, see http://www.gnu.org/licenses/.
16
*/
17
#include "
stdinc.h
"
18
#include "
Partition.h
"
19
20
Partition::Partition
():
21
_partitions(0),
22
_size(0),
23
_capacity(0) {
24
}
25
26
Partition::Partition
(
const
Partition
& partition):
27
_size(partition._size),
28
_capacity(partition._size),
29
_setCount(partition._setCount) {
30
_partitions
=
new
int
[
_size
];
31
std::copy(partition.
_partitions
,
32
partition.
_partitions
+
_size
,
_partitions
);
33
}
34
35
Partition::~Partition
() {
36
delete
[]
_partitions
;
37
}
38
39
void
Partition::reset
(
size_t
size) {
40
if
(size >
_capacity
) {
41
delete
[]
_partitions
;
42
_partitions
=
new
int
[size];
43
_capacity
= size;
44
}
45
46
_size
= size;
47
_setCount
= size;
48
fill_n(
_partitions
,
_size
, -1);
49
}
50
51
bool
Partition::join
(
size_t
i,
size_t
j) {
52
ASSERT
(i <
_size
);
53
ASSERT
(j <
_size
);
54
55
size_t
rootI =
getRoot
(i);
56
size_t
rootJ =
getRoot
(j);
57
58
if
(rootI == rootJ)
59
return
false
;
60
61
ASSERT
(
_partitions
[rootJ] < 0);
62
ASSERT
(
_partitions
[rootI] < 0);
63
64
// +1 to subtract the initial -1
65
_partitions
[rootI] +=
_partitions
[rootJ] + 1;
66
_partitions
[rootJ] = rootI;
67
--
_setCount
;
68
69
return
true
;
70
}
71
72
size_t
Partition::getSetCount
()
const
{
73
#ifdef DEBUG
74
size_t
setCount = 0;
75
for
(
size_t
i = 0; i <
_size
; ++i)
76
if
(i ==
getRoot
(i))
77
++setCount;
78
ASSERT
(
_setCount
== setCount);
79
#endif
80
81
return
_setCount
;
82
}
83
84
size_t
Partition::getSizeOfClassOf
(
size_t
i)
const
{
85
return
-
_partitions
[
getRoot
(i)];
86
}
87
88
size_t
Partition::getSetSize
(
size_t
set)
const
{
89
for
(
size_t
i = 0; i <
_size
; ++i) {
90
if
(i ==
getRoot
(i)) {
91
if
(set == 0) {
92
ASSERT
(
_partitions
[i] < 0);
93
return
-(
_partitions
[i] + 1);
// +1 to offset the initial -1
94
}
95
--set;
96
}
97
}
98
ASSERT
(
false
);
99
return
0;
100
}
101
102
size_t
Partition::getRoot
(
size_t
i)
const
{
103
ASSERT
(i <
_size
);
104
if
(
_partitions
[i] >= 0) {
105
_partitions
[i] =
getRoot
(
_partitions
[i]);
106
return
_partitions
[i];
107
}
else
108
return
i;
109
}
110
111
void
Partition::addToSet
(
size_t
i) {
112
ASSERT
(i <
_size
);
113
ASSERT
(
_partitions
[
getRoot
(i)] < 0);
114
_partitions
[
getRoot
(i)] -= 1;
115
}
116
117
size_t
Partition::getSize
()
const
{
118
return
_size
;
119
}
120
121
void
Partition::print
(FILE* file)
const
{
122
fprintf(file,
"Partition(size=%lu sets:"
, (
unsigned
long
)
_size
);
123
for
(
size_t
i = 0; i <
_size
; ++i)
124
fprintf(file,
" %li"
, (
long
)
_partitions
[i]);
125
fputc(
'\n'
, file);
126
}
Partition::_capacity
size_t _capacity
Definition:
Partition.h:50
stdinc.h
Partition::~Partition
~Partition()
Definition:
Partition.cpp:35
Partition
Definition:
Partition.h:20
Partition::_setCount
size_t _setCount
Definition:
Partition.h:52
Partition::addToSet
void addToSet(size_t i)
Definition:
Partition.cpp:111
Partition::print
void print(FILE *file) const
Definition:
Partition.cpp:121
Partition::getSetSize
size_t getSetSize(size_t set) const
Definition:
Partition.cpp:88
Partition::Partition
Partition()
Definition:
Partition.cpp:20
Partition::_size
size_t _size
Definition:
Partition.h:49
Partition::getSize
size_t getSize() const
Definition:
Partition.cpp:117
Partition::reset
void reset(size_t size)
Definition:
Partition.cpp:39
Partition::getSetCount
size_t getSetCount() const
Definition:
Partition.cpp:72
Partition.h
Partition::_partitions
int * _partitions
Definition:
Partition.h:48
Partition::getRoot
size_t getRoot(size_t i) const
Definition:
Partition.cpp:102
ASSERT
#define ASSERT(X)
Definition:
stdinc.h:86
Partition::getSizeOfClassOf
size_t getSizeOfClassOf(size_t i) const
Definition:
Partition.cpp:84
Partition::join
bool join(size_t i, size_t j)
Definition:
Partition.cpp:51
Generated by
1.8.17