11 : components(fs->components()),
13 working(), greedy(), bf()
167 double x = range.
lower();
169 while((x < range.
upper()) && (i < map.size()))
171 if (map[i].lower() > x)
177 for( ; (i < map.size()) && (map[i].lower() <= x); i++)
179 double xupper = map[i].upper();
180 if (xupper > x_next) {
182 comp_next = map[i].componentID;
196 if (x < range.
upper())
208 double y = range.
lower();
210 while((y < range.
upper()) && (i < map.size()))
212 if (map[i].lower() > y)
219 for( ; (i < map.size()) && (map[i].lower() <= y); ++i)
221 double yupper = map[i].upper();
227 else if (yupper > y_next) {
229 comp_next = map[i].componentID;
243 if (y < range.
upper())
269 QMutexLocker guard(&working.lock);
271 if (bf.k_max == NO_SOLUTION)
274 Q_ASSERT(bf.k_min > 0 && bf.k_max > 0);
277 if (bf.k_min == bf.k_max) {
279 bf.k_current = bf.k_iteration = bf.k_optimal = bf.k_max;
280 bf.result = greedy.result;
285 bf.stack1.reserve(bf.k_max);
286 bf.stack2.reserve(bf.k_max);
288 bf.k_optimal = RUNNING;
289 for(bf.k_iteration = bf.k_min; bf.k_iteration <= bf.k_max; bf.k_iteration++)
297 emit bruteForceIteration(bf.k_iteration);
298 if (bf_search_1(cancelFlag)) {
300 Q_ASSERT((bf.stack1.size()+bf.stack2.size()) == bf.k_iteration);
302 for( ; !bf.stack2.empty(); bf.stack2.pop_back()) {
304 Q_ASSERT(!working.set.contains(comp));
308 bf.result.swap(working.set);
309 bf.k_optimal = bf.k_iteration;
310 Q_ASSERT(bf.result.count() == bf.k_optimal);
312 emit bruteForceFinished();
352 bf.
stack1.push_back(std::make_pair(i,x));
363 bf.
stack2.push_back(std::make_pair(i,x));
381 bf.stack1.push_back(std::make_pair(0,domain.H.lower()));
386 if (cancelFlag && *cancelFlag)
388 bf.k_current = bf.k_iteration = bf.k_optimal = UNKNOWN;
389 throw InterruptedException();
392 Q_ASSERT(!bf.stack1.empty());
393 int& i = bf_top1().first;
394 double& x = bf_top1().second;
396 for( ; (i < map.size()) && (map[i].lower() <= x); ++i)
398 if (map[i].upper() <= x)
continue;
404 if (map[i].upper() >= range.
upper()) {
407 if (bf_search_2())
return true;
409 working_remove(map[i]);
411 else if (bf.stack1.size() < bf.k_iteration) {
414 bf_push1(i+1,map[i].upper());
420 if (!bf_pop1())
return false;
421 working_remove(map[bf_top1().first]);
447 double y = range.
lower();
449 while((y < range.
upper()) && (i < map.size()))
451 if (map[i].lower() > y)
458 for( ; (i < map.size()) && (map[i].lower() <= y); ++i)
460 double yupper = map[i].upper();
466 else if (yupper > y_next) {
476 Q_ASSERT(i_next >= 0);
485 if (y < range.
upper())
503 std::hash<const MappedInterval*> hsh;
504 return hsh(
this) < hsh(&that);
void bf_push1(int i, double x)
push an value to first stack
initial status; the algorithm has not ye been run
Result upperBound() const
get an upper bound for the optimal result. Observe that k_optimal <= k_xy,k_yx
void greedyFinished()
raised when the 'greedy' algorithm finishes Connected to UI components to update their states.
an iterator over a BitSet
int k_x
number of components that is needed to cover the x-axis. 0 if the x-axis can not be covered.
const fs::Components & components
connected components of the free-space diagram
IntervalMap vmap
map to vertical (y-)axis
data::BitSet set
subset of currently selected interval
int k_optimal
optimal value so far
bool bf_search_1(volatile bool *cancelFlag=0)
run the brute-force algorithm on the x-axis. Results are placed in this->bf.
void working_remove(const MappedInterval &ival)
remove a mapped interval from the current working-set
struct BruteForce bf
result of the brute-force algorithm
Interval H
horizontal interval
global definitions for all algorithms.
data::IntervalPair domain
the x-axis and the y-axis of the free-space diagram (from Grid)
std::vector< MappedInterval > IntervalMap
a vector of MappedInterval objects. Usually these are sorted according to the natural ordering impose...
void bf_push2(int i, double y)
push an value to second stack
indicates that the algorithm is currently running
Result lowerBound() const
get a lower bound for the optimal result. Observe that k_x,k_y <= k_optimal
int runBruteForce(volatile bool *cancelFlag=0)
run the brute force algorithm. The greedy algorithm must have been run before!
a pair of horizonal / vertical intervals.
IntervalMap hmap
map to horizontal (x-)axis
int k_iteration
optimal value of last iteration
int k_current
current number of selected components
attaches a component ID to an interval
Interval & clear()
make this an invalid interval
void clear()
assign false to all bits
int greedy_1(const IntervalMap &map, const data::Interval &range)
run the greedy algorithm on the first axis
int runGreedy()
run the greedy algorithm
void setupMapsAndResults()
initialize working-set data structures
component_id_t count() const
data::BitSet result
subsset of selected components
int greedy_yx()
run greedy algorithm (y-axis first)
const IntervalArray & intervals() const
Interval V
vertical interval
int k_yx
number of components, when scanning the y-axis first. 0 if the axes can no be covered.
bool operator<(const MappedInterval &that) const
comparison operator, needed for sorting a list of MappedInterval objects. We first compare the lower ...
struct Greedy greedy
results of the greedy algorithm
bool contains(int offset) const
bool bf_pop1()
pop from first stack
void working_add(const MappedInterval &ival)
add a mapped interval to the current working-set
std::pair< int, double > & bf_top2()
int k_max
upper bound derived from greedy results. k_max = min{greedy.k_xy,greedy.k_yx}
bool bf_search_2()
run the brute-force algorithm on the y-axis. Results are placed in this->bf.
data::BitSet::iterator last() const
data::BitSet result
subset of selected components
data::BitSet::iterator begin() const
A simple bit vector of fixed size.
bool bf_backtrack2()
clear second stack
BitSet & swap(BitSet &that)
swap contents with other object
int greedy_2(const IntervalMap &map, const data::Interval &range)
run the greedy algorithm on the second axis
bool operator==(const MappedInterval &that) const
equality operator, needed for sorting a list of MappedInterval objects.
Stack stack1
stacks used for backtracking
int k_min
lower bound derived from greedy results. k_min = max{greedy.k_x,greedy.k_y}
int count() const
This methods is expensive, as it scans the whole array.
std::pair< int, double > & bf_top1()
struct frechet::k::kAlgorithm::WorkingSet working
int k_y
number of components that is needed to cover the y-axis. 0 if the y-axis can not be covered.
unsigned int component_id_t
used as identifier for free-space components
an interval of two double values.
int k_xy
number of components, when scanning the x-axis first. 0 if the axes can no be covered.
there is no solution at all
int greedy_12(const IntervalMap &map1, const data::Interval &range1, const IntervalMap &map2, const data::Interval &range2, int &k_1)
run the greedy algorithm on tow axes
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
int greedy_xy()
run the greedy algorithm (x-axis first)