1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2006 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_XY_H |
|
20 #define LEMON_XY_H |
|
21 |
|
22 #include <iostream> |
|
23 #include <lemon/bits/utility.h> |
|
24 |
|
25 ///\ingroup misc |
|
26 ///\file |
|
27 ///\brief A simple two dimensional vector and a bounding box implementation |
|
28 /// |
|
29 /// The class \ref lemon::xy "xy" implements |
|
30 ///a two dimensional vector with the usual |
|
31 /// operations. |
|
32 /// |
|
33 /// The class \ref lemon::BoundingBox "BoundingBox" can be used to determine |
|
34 /// the rectangular bounding box of a set of \ref lemon::xy "xy"'s. |
|
35 /// |
|
36 ///\author Attila Bernath |
|
37 |
|
38 |
|
39 namespace lemon { |
|
40 |
|
41 /// \addtogroup misc |
|
42 /// @{ |
|
43 |
|
44 /// A simple two dimensional vector (plainvector) implementation |
|
45 |
|
46 /// A simple two dimensional vector (plainvector) implementation |
|
47 ///with the usual vector |
|
48 /// operators. |
|
49 /// |
|
50 ///\note As you might have noticed, this class does not follow the |
|
51 ///\ref naming_conv "LEMON Coding Style" (it should be called \c Xy |
|
52 ///according to it). There is a stupid Hungarian proverb, "A kivétel |
|
53 ///erõsíti a szabályt" ("An exception |
|
54 ///reinforces a rule", which is |
|
55 ///actually a mistranslation of the Latin proverb "Exceptio probat regulam"). |
|
56 ///This class is an example for that. |
|
57 ///\author Attila Bernath |
|
58 template<typename T> |
|
59 class xy { |
|
60 |
|
61 public: |
|
62 |
|
63 typedef T Value; |
|
64 |
|
65 ///First co-ordinate |
|
66 T x; |
|
67 ///Second co-ordinate |
|
68 T y; |
|
69 |
|
70 ///Default constructor |
|
71 xy() {} |
|
72 |
|
73 ///Construct an instance from coordinates |
|
74 xy(T a, T b) : x(a), y(b) { } |
|
75 |
|
76 |
|
77 ///Conversion constructor |
|
78 template<class TT> xy(const xy<TT> &p) : x(p.x), y(p.y) {} |
|
79 |
|
80 ///Give back the square of the norm of the vector |
|
81 T normSquare() const { |
|
82 return x*x+y*y; |
|
83 } |
|
84 |
|
85 ///Increment the left hand side by u |
|
86 xy<T>& operator +=(const xy<T>& u) { |
|
87 x += u.x; |
|
88 y += u.y; |
|
89 return *this; |
|
90 } |
|
91 |
|
92 ///Decrement the left hand side by u |
|
93 xy<T>& operator -=(const xy<T>& u) { |
|
94 x -= u.x; |
|
95 y -= u.y; |
|
96 return *this; |
|
97 } |
|
98 |
|
99 ///Multiply the left hand side with a scalar |
|
100 xy<T>& operator *=(const T &u) { |
|
101 x *= u; |
|
102 y *= u; |
|
103 return *this; |
|
104 } |
|
105 |
|
106 ///Divide the left hand side by a scalar |
|
107 xy<T>& operator /=(const T &u) { |
|
108 x /= u; |
|
109 y /= u; |
|
110 return *this; |
|
111 } |
|
112 |
|
113 ///Return the scalar product of two vectors |
|
114 T operator *(const xy<T>& u) const { |
|
115 return x*u.x+y*u.y; |
|
116 } |
|
117 |
|
118 ///Return the sum of two vectors |
|
119 xy<T> operator+(const xy<T> &u) const { |
|
120 xy<T> b=*this; |
|
121 return b+=u; |
|
122 } |
|
123 |
|
124 ///Return the neg of the vectors |
|
125 xy<T> operator-() const { |
|
126 xy<T> b=*this; |
|
127 b.x=-b.x; b.y=-b.y; |
|
128 return b; |
|
129 } |
|
130 |
|
131 ///Return the difference of two vectors |
|
132 xy<T> operator-(const xy<T> &u) const { |
|
133 xy<T> b=*this; |
|
134 return b-=u; |
|
135 } |
|
136 |
|
137 ///Return a vector multiplied by a scalar |
|
138 xy<T> operator*(const T &u) const { |
|
139 xy<T> b=*this; |
|
140 return b*=u; |
|
141 } |
|
142 |
|
143 ///Return a vector divided by a scalar |
|
144 xy<T> operator/(const T &u) const { |
|
145 xy<T> b=*this; |
|
146 return b/=u; |
|
147 } |
|
148 |
|
149 ///Test equality |
|
150 bool operator==(const xy<T> &u) const { |
|
151 return (x==u.x) && (y==u.y); |
|
152 } |
|
153 |
|
154 ///Test inequality |
|
155 bool operator!=(xy u) const { |
|
156 return (x!=u.x) || (y!=u.y); |
|
157 } |
|
158 |
|
159 }; |
|
160 |
|
161 ///Return an xy |
|
162 |
|
163 ///Return an xy |
|
164 ///\relates xy |
|
165 template <typename T> |
|
166 inline xy<T> make_xy(const T& x, const T& y) { |
|
167 return xy<T>(x, y); |
|
168 } |
|
169 |
|
170 ///Return a vector multiplied by a scalar |
|
171 |
|
172 ///Return a vector multiplied by a scalar |
|
173 ///\relates xy |
|
174 template<typename T> xy<T> operator*(const T &u,const xy<T> &x) { |
|
175 return x*u; |
|
176 } |
|
177 |
|
178 ///Read a plainvector from a stream |
|
179 |
|
180 ///Read a plainvector from a stream |
|
181 ///\relates xy |
|
182 /// |
|
183 template<typename T> |
|
184 inline std::istream& operator>>(std::istream &is, xy<T> &z) { |
|
185 char c; |
|
186 if (is >> c) { |
|
187 if (c != '(') is.putback(c); |
|
188 } else { |
|
189 is.clear(); |
|
190 } |
|
191 if (!(is >> z.x)) return is; |
|
192 if (is >> c) { |
|
193 if (c != ',') is.putback(c); |
|
194 } else { |
|
195 is.clear(); |
|
196 } |
|
197 if (!(is >> z.y)) return is; |
|
198 if (is >> c) { |
|
199 if (c != ')') is.putback(c); |
|
200 } else { |
|
201 is.clear(); |
|
202 } |
|
203 return is; |
|
204 } |
|
205 |
|
206 ///Write a plainvector to a stream |
|
207 |
|
208 ///Write a plainvector to a stream |
|
209 ///\relates xy |
|
210 /// |
|
211 template<typename T> |
|
212 inline std::ostream& operator<<(std::ostream &os, const xy<T>& z) |
|
213 { |
|
214 os << "(" << z.x << ", " << z.y << ")"; |
|
215 return os; |
|
216 } |
|
217 |
|
218 ///Rotate by 90 degrees |
|
219 |
|
220 ///Returns its parameter rotated by 90 degrees in positive direction. |
|
221 ///\relates xy |
|
222 /// |
|
223 template<typename T> |
|
224 inline xy<T> rot90(const xy<T> &z) |
|
225 { |
|
226 return xy<T>(-z.y,z.x); |
|
227 } |
|
228 |
|
229 ///Rotate by 180 degrees |
|
230 |
|
231 ///Returns its parameter rotated by 180 degrees. |
|
232 ///\relates xy |
|
233 /// |
|
234 template<typename T> |
|
235 inline xy<T> rot180(const xy<T> &z) |
|
236 { |
|
237 return xy<T>(-z.x,-z.y); |
|
238 } |
|
239 |
|
240 ///Rotate by 270 degrees |
|
241 |
|
242 ///Returns its parameter rotated by 90 degrees in negative direction. |
|
243 ///\relates xy |
|
244 /// |
|
245 template<typename T> |
|
246 inline xy<T> rot270(const xy<T> &z) |
|
247 { |
|
248 return xy<T>(z.y,-z.x); |
|
249 } |
|
250 |
|
251 |
|
252 |
|
253 /// A class to calculate or store the bounding box of plainvectors. |
|
254 |
|
255 /// A class to calculate or store the bounding box of plainvectors. |
|
256 /// |
|
257 ///\author Attila Bernath |
|
258 template<typename T> |
|
259 class BoundingBox { |
|
260 xy<T> bottom_left, top_right; |
|
261 bool _empty; |
|
262 public: |
|
263 |
|
264 ///Default constructor: creates an empty bounding box |
|
265 BoundingBox() { _empty = true; } |
|
266 |
|
267 ///Construct an instance from one point |
|
268 BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; } |
|
269 |
|
270 ///Were any points added? |
|
271 bool empty() const { |
|
272 return _empty; |
|
273 } |
|
274 |
|
275 ///Make the BoundingBox empty |
|
276 void clear() { |
|
277 _empty=1; |
|
278 } |
|
279 |
|
280 ///Give back the bottom left corner |
|
281 |
|
282 ///Give back the bottom left corner. |
|
283 ///If the bounding box is empty, then the return value is not defined. |
|
284 xy<T> bottomLeft() const { |
|
285 return bottom_left; |
|
286 } |
|
287 |
|
288 ///Set the bottom left corner |
|
289 |
|
290 ///Set the bottom left corner. |
|
291 ///It should only bee used for non-empty box. |
|
292 void bottomLeft(xy<T> p) { |
|
293 bottom_left = p; |
|
294 } |
|
295 |
|
296 ///Give back the top right corner |
|
297 |
|
298 ///Give back the top right corner. |
|
299 ///If the bounding box is empty, then the return value is not defined. |
|
300 xy<T> topRight() const { |
|
301 return top_right; |
|
302 } |
|
303 |
|
304 ///Set the top right corner |
|
305 |
|
306 ///Set the top right corner. |
|
307 ///It should only bee used for non-empty box. |
|
308 void topRight(xy<T> p) { |
|
309 top_right = p; |
|
310 } |
|
311 |
|
312 ///Give back the bottom right corner |
|
313 |
|
314 ///Give back the bottom right corner. |
|
315 ///If the bounding box is empty, then the return value is not defined. |
|
316 xy<T> bottomRight() const { |
|
317 return xy<T>(top_right.x,bottom_left.y); |
|
318 } |
|
319 |
|
320 ///Set the bottom right corner |
|
321 |
|
322 ///Set the bottom right corner. |
|
323 ///It should only bee used for non-empty box. |
|
324 void bottomRight(xy<T> p) { |
|
325 top_right.x = p.x; |
|
326 bottom_left.y = p.y; |
|
327 } |
|
328 |
|
329 ///Give back the top left corner |
|
330 |
|
331 ///Give back the top left corner. |
|
332 ///If the bounding box is empty, then the return value is not defined. |
|
333 xy<T> topLeft() const { |
|
334 return xy<T>(bottom_left.x,top_right.y); |
|
335 } |
|
336 |
|
337 ///Set the top left corner |
|
338 |
|
339 ///Set the top left corner. |
|
340 ///It should only bee used for non-empty box. |
|
341 void topLeft(xy<T> p) { |
|
342 top_right.y = p.y; |
|
343 bottom_left.x = p.x; |
|
344 } |
|
345 |
|
346 ///Give back the bottom of the box |
|
347 |
|
348 ///Give back the bottom of the box. |
|
349 ///If the bounding box is empty, then the return value is not defined. |
|
350 T bottom() const { |
|
351 return bottom_left.y; |
|
352 } |
|
353 |
|
354 ///Set the bottom of the box |
|
355 |
|
356 ///Set the bottom of the box. |
|
357 ///It should only bee used for non-empty box. |
|
358 void bottom(T t) { |
|
359 bottom_left.y = t; |
|
360 } |
|
361 |
|
362 ///Give back the top of the box |
|
363 |
|
364 ///Give back the top of the box. |
|
365 ///If the bounding box is empty, then the return value is not defined. |
|
366 T top() const { |
|
367 return top_right.y; |
|
368 } |
|
369 |
|
370 ///Set the top of the box |
|
371 |
|
372 ///Set the top of the box. |
|
373 ///It should only bee used for non-empty box. |
|
374 void top(T t) { |
|
375 top_right.y = t; |
|
376 } |
|
377 |
|
378 ///Give back the left side of the box |
|
379 |
|
380 ///Give back the left side of the box. |
|
381 ///If the bounding box is empty, then the return value is not defined. |
|
382 T left() const { |
|
383 return bottom_left.x; |
|
384 } |
|
385 |
|
386 ///Set the left side of the box |
|
387 |
|
388 ///Set the left side of the box. |
|
389 ///It should only bee used for non-empty box |
|
390 void left(T t) { |
|
391 bottom_left.x = t; |
|
392 } |
|
393 |
|
394 /// Give back the right side of the box |
|
395 |
|
396 /// Give back the right side of the box. |
|
397 ///If the bounding box is empty, then the return value is not defined. |
|
398 T right() const { |
|
399 return top_right.x; |
|
400 } |
|
401 |
|
402 ///Set the right side of the box |
|
403 |
|
404 ///Set the right side of the box. |
|
405 ///It should only bee used for non-empty box |
|
406 void right(T t) { |
|
407 top_right.x = t; |
|
408 } |
|
409 |
|
410 ///Give back the height of the box |
|
411 |
|
412 ///Give back the height of the box. |
|
413 ///If the bounding box is empty, then the return value is not defined. |
|
414 T height() const { |
|
415 return top_right.y-bottom_left.y; |
|
416 } |
|
417 |
|
418 ///Give back the width of the box |
|
419 |
|
420 ///Give back the width of the box. |
|
421 ///If the bounding box is empty, then the return value is not defined. |
|
422 T width() const { |
|
423 return top_right.x-bottom_left.x; |
|
424 } |
|
425 |
|
426 ///Checks whether a point is inside a bounding box |
|
427 bool inside(const xy<T>& u){ |
|
428 if (_empty) |
|
429 return false; |
|
430 else{ |
|
431 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && |
|
432 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); |
|
433 } |
|
434 } |
|
435 |
|
436 ///Increments a bounding box with a point |
|
437 BoundingBox& add(const xy<T>& u){ |
|
438 if (_empty){ |
|
439 bottom_left=top_right=u; |
|
440 _empty = false; |
|
441 } |
|
442 else{ |
|
443 if (bottom_left.x > u.x) bottom_left.x = u.x; |
|
444 if (bottom_left.y > u.y) bottom_left.y = u.y; |
|
445 if (top_right.x < u.x) top_right.x = u.x; |
|
446 if (top_right.y < u.y) top_right.y = u.y; |
|
447 } |
|
448 return *this; |
|
449 } |
|
450 |
|
451 // ///Sums a bounding box and a point |
|
452 // BoundingBox operator +(const xy<T>& u){ |
|
453 // BoundingBox b = *this; |
|
454 // return b += u; |
|
455 // } |
|
456 |
|
457 ///Increments a bounding box with another bounding box |
|
458 BoundingBox& add(const BoundingBox &u){ |
|
459 if ( !u.empty() ){ |
|
460 this->add(u.bottomLeft()); |
|
461 this->add(u.topRight()); |
|
462 } |
|
463 return *this; |
|
464 } |
|
465 |
|
466 ///Sums two bounding boxes |
|
467 BoundingBox operator +(const BoundingBox& u){ |
|
468 BoundingBox b = *this; |
|
469 return b.add(u); |
|
470 } |
|
471 |
|
472 |
|
473 ///Intersection of two bounding boxes |
|
474 BoundingBox operator &(const BoundingBox& u){ |
|
475 BoundingBox b; |
|
476 b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x); |
|
477 b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y); |
|
478 b.top_right.x=std::min(this->top_right.x,u.top_right.x); |
|
479 b.top_right.y=std::min(this->top_right.y,u.top_right.y); |
|
480 b._empty = this->_empty || u._empty || |
|
481 b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y; |
|
482 return b; |
|
483 } |
|
484 |
|
485 };//class Boundingbox |
|
486 |
|
487 |
|
488 ///Map of x-coordinates of an xy<>-map |
|
489 |
|
490 ///\ingroup maps |
|
491 /// |
|
492 template<class M> |
|
493 class XMap |
|
494 { |
|
495 M& _map; |
|
496 public: |
|
497 |
|
498 typedef typename M::Value::Value Value; |
|
499 typedef typename M::Key Key; |
|
500 ///\e |
|
501 XMap(M& map) : _map(map) {} |
|
502 Value operator[](Key k) const {return _map[k].x;} |
|
503 void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));} |
|
504 }; |
|
505 |
|
506 ///Returns an \ref XMap class |
|
507 |
|
508 ///This function just returns an \ref XMap class. |
|
509 /// |
|
510 ///\ingroup maps |
|
511 ///\relates XMap |
|
512 template<class M> |
|
513 inline XMap<M> xMap(M &m) |
|
514 { |
|
515 return XMap<M>(m); |
|
516 } |
|
517 |
|
518 template<class M> |
|
519 inline XMap<M> xMap(const M &m) |
|
520 { |
|
521 return XMap<M>(m); |
|
522 } |
|
523 |
|
524 ///Constant (read only) version of \ref XMap |
|
525 |
|
526 ///\ingroup maps |
|
527 /// |
|
528 template<class M> |
|
529 class ConstXMap |
|
530 { |
|
531 const M& _map; |
|
532 public: |
|
533 |
|
534 typedef typename M::Value::Value Value; |
|
535 typedef typename M::Key Key; |
|
536 ///\e |
|
537 ConstXMap(const M &map) : _map(map) {} |
|
538 Value operator[](Key k) const {return _map[k].x;} |
|
539 }; |
|
540 |
|
541 ///Returns a \ref ConstXMap class |
|
542 |
|
543 ///This function just returns an \ref ConstXMap class. |
|
544 /// |
|
545 ///\ingroup maps |
|
546 ///\relates ConstXMap |
|
547 template<class M> |
|
548 inline ConstXMap<M> xMap(const M &m) |
|
549 { |
|
550 return ConstXMap<M>(m); |
|
551 } |
|
552 |
|
553 ///Map of y-coordinates of an xy<>-map |
|
554 |
|
555 ///\ingroup maps |
|
556 /// |
|
557 template<class M> |
|
558 class YMap |
|
559 { |
|
560 M& _map; |
|
561 public: |
|
562 |
|
563 typedef typename M::Value::Value Value; |
|
564 typedef typename M::Key Key; |
|
565 ///\e |
|
566 YMap(M& map) : _map(map) {} |
|
567 Value operator[](Key k) const {return _map[k].y;} |
|
568 void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} |
|
569 }; |
|
570 |
|
571 ///Returns an \ref YMap class |
|
572 |
|
573 ///This function just returns an \ref YMap class. |
|
574 /// |
|
575 ///\ingroup maps |
|
576 ///\relates YMap |
|
577 template<class M> |
|
578 inline YMap<M> yMap(M &m) |
|
579 { |
|
580 return YMap<M>(m); |
|
581 } |
|
582 |
|
583 template<class M> |
|
584 inline YMap<M> yMap(const M &m) |
|
585 { |
|
586 return YMap<M>(m); |
|
587 } |
|
588 |
|
589 ///Constant (read only) version of \ref YMap |
|
590 |
|
591 ///\ingroup maps |
|
592 /// |
|
593 template<class M> |
|
594 class ConstYMap |
|
595 { |
|
596 const M& _map; |
|
597 public: |
|
598 |
|
599 typedef typename M::Value::Value Value; |
|
600 typedef typename M::Key Key; |
|
601 ///\e |
|
602 ConstYMap(const M &map) : _map(map) {} |
|
603 Value operator[](Key k) const {return _map[k].y;} |
|
604 }; |
|
605 |
|
606 ///Returns a \ref ConstYMap class |
|
607 |
|
608 ///This function just returns an \ref ConstYMap class. |
|
609 /// |
|
610 ///\ingroup maps |
|
611 ///\relates ConstYMap |
|
612 template<class M> |
|
613 inline ConstYMap<M> yMap(const M &m) |
|
614 { |
|
615 return ConstYMap<M>(m); |
|
616 } |
|
617 |
|
618 |
|
619 ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map |
|
620 |
|
621 ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map |
|
622 ///\ingroup maps |
|
623 /// |
|
624 template<class M> |
|
625 class NormSquareMap |
|
626 { |
|
627 const M& _map; |
|
628 public: |
|
629 |
|
630 typedef typename M::Value::Value Value; |
|
631 typedef typename M::Key Key; |
|
632 ///\e |
|
633 NormSquareMap(const M &map) : _map(map) {} |
|
634 Value operator[](Key k) const {return _map[k].normSquare();} |
|
635 }; |
|
636 |
|
637 ///Returns a \ref NormSquareMap class |
|
638 |
|
639 ///This function just returns an \ref NormSquareMap class. |
|
640 /// |
|
641 ///\ingroup maps |
|
642 ///\relates NormSquareMap |
|
643 template<class M> |
|
644 inline NormSquareMap<M> normSquareMap(const M &m) |
|
645 { |
|
646 return NormSquareMap<M>(m); |
|
647 } |
|
648 |
|
649 /// @} |
|
650 |
|
651 |
|
652 } //namespace lemon |
|
653 |
|
654 #endif //LEMON_XY_H |
|