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);
116 friend class BacktrackRefinement;
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)
186inline 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;
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