38 #include <boost/foreach.hpp> 39 #include <boost/dynamic_bitset.hpp> 45 class BacktrackRefinement;
61 template<
class ForwardIterator>
62 bool intersect(ForwardIterator begin, ForwardIterator end,
unsigned int j);
68 template<
class ForwardIterator>
69 bool intersects(ForwardIterator begin, ForwardIterator end,
unsigned int j)
const;
71 typedef std::vector<unsigned int> vector_t;
79 unsigned long cells()
const;
81 unsigned long cellSize(
unsigned int c)
const;
83 typedef vector_t::const_iterator CellIt;
85 CellIt cellBegin(
unsigned long cell)
const {
86 BOOST_ASSERT(cell <
cells());
87 return partition.begin() + partitionCellBorder[cell];
90 CellIt cellEnd(
unsigned long cell)
const {
91 BOOST_ASSERT(cell <
cells());
92 return partition.begin() + partitionCellBorder[cell] + partitionCellLength[cell];
95 explicit Partition(
unsigned long n,
bool);
98 vector_t partitionCellBorder;
99 vector_t partitionCellLength;
100 vector_t partitionCellOf;
105 unsigned int cellCounter;
111 unsigned int fixCounter;
113 friend std::ostream& operator<<(std::ostream& out,
const Partition& p);
119 inline std::ostream& operator<<(std::ostream& out,
const Partition& p) {
121 Partition::vector_t::const_iterator border = p.partitionCellBorder.begin();
122 Partition::vector_t::const_iterator length = p.partitionCellLength.begin();
123 for (
unsigned int j = 0; j < p.cellCounter; ++j) {
124 for (
unsigned int i = *border; i < *border + *length; ++i) {
125 out << (p.partition[i] + 1) <<
" ";
132 int countFix = p.fixCounter;
133 BOOST_FOREACH(
unsigned long alpha, p.fix) {
136 out << (alpha+1) <<
",";
143 : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(1), fix(n), fixCounter(0)
145 for (
unsigned int i=0; i<n; ++i) {
149 partitionCellBorder[0] = 0;
150 partitionCellLength[0] = n;
154 : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(0), fix(n), fixCounter(0)
168 return fix.begin() + fixCounter;
171 return partitionCellLength[c];
174 template<
class ForwardIterator>
176 while (begin != end) {
178 if (partitionCellOf[*begin++] == j)
185 template<
class ForwardIterator>
186 inline bool Partition::intersect(ForwardIterator otherCellBegin, ForwardIterator otherCellEnd,
unsigned int j) {
187 if (!
intersects(otherCellBegin, otherCellEnd, j))
190 vector_t& newCell = m_newCell;
192 ForwardIterator otherCellIt = otherCellBegin;
193 vector_t::iterator cellIt;
194 vector_t::reverse_iterator newCellIt;
195 vector_t::reverse_iterator newCellBeginIt;
196 vector_t::iterator newCell2It;
197 vector_t::iterator borderIt;
198 bool createdNewCell =
false;
199 const unsigned int partitionCellSize = partitionCellLength[j];
200 if (j >= cellCounter)
202 if (partitionCellSize <= 1)
204 vector_t::iterator cellBeginIt = partition.begin() + partitionCellBorder[j];
205 vector_t::iterator cellEndIt = partition.begin() + (partitionCellBorder[j] + partitionCellLength[j]);
207 newCellBeginIt = newCell.rbegin() + (partition.size() - partitionCellSize);
208 newCellIt = newCellBeginIt;
209 newCell2It = newCell.begin();
210 unsigned int newCellCounter = 0;
212 for (cellIt = cellBeginIt; cellIt != cellEndIt; ++cellIt) {
213 while (otherCellIt != otherCellEnd && *otherCellIt < *cellIt) {
216 if (otherCellIt != otherCellEnd && *cellIt == *otherCellIt) {
217 *newCell2It = *cellIt;
219 if (newCellCounter == 0) {
223 newCellIt = std::copy(cellBeginIt, cellIt, newCellIt);
226 }
else if (newCellCounter) {
227 *newCellIt = *cellIt;
232 if (newCellCounter > 0 && newCellCounter < partitionCellSize) {
233 std::reverse(newCellBeginIt, newCellIt);
234 std::copy(newCell.begin(), newCell.begin() + partitionCellSize, cellBeginIt);
238 vector_t::iterator fixIt = fix.begin() + fixCounter;
240 if (newCellCounter == 1) {
245 if (newCellCounter == partitionCellSize - 1) {
246 *fixIt = newCell[partitionCellSize - 1];
259 partitionCellLength[j] = newCellCounter;
262 partitionCellBorder[cellCounter] = partitionCellBorder[j] + newCellCounter;
263 partitionCellLength[cellCounter] = partitionCellSize - newCellCounter;
264 for (
unsigned int i = partitionCellBorder[cellCounter]; i < partitionCellBorder[j] + partitionCellSize; ++i) {
265 BOOST_ASSERT( i < partition.size() );
266 BOOST_ASSERT( partition[i] < partitionCellOf.size() );
267 partitionCellOf[partition[i]] = cellCounter;
271 createdNewCell =
true;
274 return createdNewCell;
278 if (partitionCellBorder[cellCounter-1] < 1)
281 unsigned int splitFromCellNumber = partitionCellOf[ partition[partitionCellBorder[cellCounter] - 1] ];
283 BOOST_ASSERT(partitionCellBorder[splitFromCellNumber] < partitionCellBorder[cellCounter]);
284 BOOST_ASSERT(partitionCellLength[cellCounter] > 0 );
288 for (
unsigned int i=partitionCellBorder[cellCounter]; i<partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]; ++i) {
289 partitionCellOf[partition[i]] = splitFromCellNumber;
291 std::inplace_merge(partition.begin() + partitionCellBorder[splitFromCellNumber],
292 partition.begin() + partitionCellBorder[cellCounter],
293 partition.begin() + (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]));
296 if (partitionCellLength[cellCounter] == 1) {
300 if (partitionCellLength[splitFromCellNumber] == 1) {
305 partitionCellLength[splitFromCellNumber] += partitionCellLength[cellCounter];
307 partitionCellLength[cellCounter] = 0;
308 partitionCellBorder[cellCounter] = 0;
316 #endif // -- PARTITION_H_ Partition(unsigned long n)
constructs an empty partition of length n
Definition: partition.h:142
vector_t::const_iterator fixPointsEnd() const
iterator to the end of fix points
Definition: partition.h:167
partition
Definition: partition.h:48
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j)
intersects the j-th cell of this partition with a given set
Definition: partition.h:186
unsigned int fixPointsSize() const
number of fix points in this partition
Definition: partition.h:161
bool intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const
Definition: partition.h:175
backtrack refinement
Definition: backtrack_refinement.h:45
bool undoIntersection()
reverts the last intersection if there is one
Definition: partition.h:277
vector_t::const_iterator fixPointsBegin() const
iterator to the begin of fix points
Definition: partition.h:164
Definition: abstract_bsgs.h:49
unsigned long cellSize(unsigned int c) const
size of the c-th cell
Definition: partition.h:170