Frobby 0.9.5
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
21 _partitions(0),
22 _size(0),
23 _capacity(0) {
24}
25
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
38
39void 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;
49}
50
51bool 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
63
64 // +1 to subtract the initial -1
67 --_setCount;
68
69 return true;
70}
71
72size_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;
79#endif
80
81 return _setCount;
82}
83
84size_t Partition::getSizeOfClassOf(size_t i) const {
85 return -_partitions[getRoot(i)];
86}
87
88size_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
102size_t Partition::getRoot(size_t i) const {
103 ASSERT(i < _size);
104 if (_partitions[i] >= 0) {
106 return _partitions[i];
107 } else
108 return i;
109}
110
111void Partition::addToSet(size_t i) {
112 ASSERT(i < _size);
114 _partitions[getRoot(i)] -= 1;
115}
116
117size_t Partition::getSize() const {
118 return _size;
119}
120
121void 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}
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
int * _partitions
Definition Partition.h:48
size_t getSetCount() const
Definition Partition.cpp:72
size_t _setCount
Definition Partition.h:52
size_t _size
Definition Partition.h:49
size_t getSetSize(size_t set) const
Definition Partition.cpp:88
void print(FILE *file) const
size_t getSizeOfClassOf(size_t i) const
Definition Partition.cpp:84
bool join(size_t i, size_t j)
Definition Partition.cpp:51
void reset(size_t size)
Definition Partition.cpp:39
size_t getSize() const
void addToSet(size_t i)
size_t _capacity
Definition Partition.h:50
size_t getRoot(size_t i) const
#define ASSERT(X)
Definition stdinc.h:86