Frobby
0.9.5
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
}
nameFactoryRegister
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
Definition
NameFactory.h:142
Partition.h
Partition
Definition
Partition.h:20
Partition::_partitions
int * _partitions
Definition
Partition.h:48
Partition::getSetCount
size_t getSetCount() const
Definition
Partition.cpp:72
Partition::_setCount
size_t _setCount
Definition
Partition.h:52
Partition::~Partition
~Partition()
Definition
Partition.cpp:35
Partition::_size
size_t _size
Definition
Partition.h:49
Partition::getSetSize
size_t getSetSize(size_t set) const
Definition
Partition.cpp:88
Partition::print
void print(FILE *file) const
Definition
Partition.cpp:121
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
Partition::reset
void reset(size_t size)
Definition
Partition.cpp:39
Partition::getSize
size_t getSize() const
Definition
Partition.cpp:117
Partition::addToSet
void addToSet(size_t i)
Definition
Partition.cpp:111
Partition::_capacity
size_t _capacity
Definition
Partition.h:50
Partition::Partition
Partition()
Definition
Partition.cpp:20
Partition::getRoot
size_t getRoot(size_t i) const
Definition
Partition.cpp:102
ASSERT
#define ASSERT(X)
Definition
stdinc.h:86
stdinc.h
Generated by
1.9.8