1 /* -*- C++ -*- |
|
2 * src/lemon/xy.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_XY_H |
|
18 #define LEMON_XY_H |
|
19 |
|
20 #include <iostream> |
|
21 #include <lemon/utility.h> |
|
22 |
|
23 ///\ingroup misc |
|
24 ///\file |
|
25 ///\brief A simple two dimensional vector and a bounding box implementation |
|
26 /// |
|
27 /// The class \ref lemon::xy "xy" implements |
|
28 ///a two dimensional vector with the usual |
|
29 /// operations. |
|
30 /// |
|
31 /// The class \ref lemon::BoundingBox "BoundingBox" can be used to determine |
|
32 /// the rectangular bounding box of a set of \ref lemon::xy "xy"'s. |
|
33 /// |
|
34 ///\author Attila Bernath |
|
35 |
|
36 |
|
37 namespace lemon { |
|
38 |
|
39 /// \addtogroup misc |
|
40 /// @{ |
|
41 |
|
42 /// A simple two dimensional vector (plainvector) implementation |
|
43 |
|
44 /// A simple two dimensional vector (plainvector) implementation |
|
45 ///with the usual vector |
|
46 /// operators. |
|
47 /// |
|
48 ///\author Attila Bernath |
|
49 template<typename T> |
|
50 class xy { |
|
51 |
|
52 public: |
|
53 |
|
54 typedef T Value; |
|
55 |
|
56 T x,y; |
|
57 |
|
58 ///Default constructor |
|
59 xy() {} |
|
60 |
|
61 ///Constructing the instance from coordinates |
|
62 xy(T a, T b) : x(a), y(b) { } |
|
63 |
|
64 |
|
65 ///Conversion constructor |
|
66 template<class TT> xy(const xy<TT> &p) : x(p.x), y(p.y) {} |
|
67 |
|
68 ///Gives back the square of the norm of the vector |
|
69 T normSquare() const { |
|
70 return x*x+y*y; |
|
71 } |
|
72 |
|
73 ///Increments the left hand side by u |
|
74 xy<T>& operator +=(const xy<T>& u) { |
|
75 x += u.x; |
|
76 y += u.y; |
|
77 return *this; |
|
78 } |
|
79 |
|
80 ///Decrements the left hand side by u |
|
81 xy<T>& operator -=(const xy<T>& u) { |
|
82 x -= u.x; |
|
83 y -= u.y; |
|
84 return *this; |
|
85 } |
|
86 |
|
87 ///Multiplying the left hand side with a scalar |
|
88 xy<T>& operator *=(const T &u) { |
|
89 x *= u; |
|
90 y *= u; |
|
91 return *this; |
|
92 } |
|
93 |
|
94 ///Dividing the left hand side by a scalar |
|
95 xy<T>& operator /=(const T &u) { |
|
96 x /= u; |
|
97 y /= u; |
|
98 return *this; |
|
99 } |
|
100 |
|
101 ///Returns the scalar product of two vectors |
|
102 T operator *(const xy<T>& u) const { |
|
103 return x*u.x+y*u.y; |
|
104 } |
|
105 |
|
106 ///Returns the sum of two vectors |
|
107 xy<T> operator+(const xy<T> &u) const { |
|
108 xy<T> b=*this; |
|
109 return b+=u; |
|
110 } |
|
111 |
|
112 ///Returns the neg of the vectors |
|
113 xy<T> operator-() const { |
|
114 xy<T> b=*this; |
|
115 b.x=-b.x; b.y=-b.y; |
|
116 return b; |
|
117 } |
|
118 |
|
119 ///Returns the difference of two vectors |
|
120 xy<T> operator-(const xy<T> &u) const { |
|
121 xy<T> b=*this; |
|
122 return b-=u; |
|
123 } |
|
124 |
|
125 ///Returns a vector multiplied by a scalar |
|
126 xy<T> operator*(const T &u) const { |
|
127 xy<T> b=*this; |
|
128 return b*=u; |
|
129 } |
|
130 |
|
131 ///Returns a vector divided by a scalar |
|
132 xy<T> operator/(const T &u) const { |
|
133 xy<T> b=*this; |
|
134 return b/=u; |
|
135 } |
|
136 |
|
137 ///Testing equality |
|
138 bool operator==(const xy<T> &u) const { |
|
139 return (x==u.x) && (y==u.y); |
|
140 } |
|
141 |
|
142 ///Testing inequality |
|
143 bool operator!=(xy u) const { |
|
144 return (x!=u.x) || (y!=u.y); |
|
145 } |
|
146 |
|
147 }; |
|
148 |
|
149 ///Returns a vector multiplied by a scalar |
|
150 |
|
151 ///Returns a vector multiplied by a scalar |
|
152 ///\relates xy |
|
153 template<typename T> xy<T> operator*(const T &u,const xy<T> &x) { |
|
154 return x*u; |
|
155 } |
|
156 |
|
157 ///Read a plainvector from a stream |
|
158 |
|
159 ///Read a plainvector from a stream |
|
160 ///\relates xy |
|
161 /// |
|
162 template<typename T> |
|
163 inline std::istream& operator>>(std::istream &is, xy<T> &z) { |
|
164 char c; |
|
165 if (is >> c) { |
|
166 if (c != '(') is.putback(c); |
|
167 } else { |
|
168 is.clear(); |
|
169 } |
|
170 if (!(is >> z.x)) return is; |
|
171 if (is >> c) { |
|
172 if (c != ',') is.putback(c); |
|
173 } else { |
|
174 is.clear(); |
|
175 } |
|
176 if (!(is >> z.y)) return is; |
|
177 if (is >> c) { |
|
178 if (c != ')') is.putback(c); |
|
179 } else { |
|
180 is.clear(); |
|
181 } |
|
182 return is; |
|
183 } |
|
184 |
|
185 ///Write a plainvector to a stream |
|
186 |
|
187 ///Write a plainvector to a stream |
|
188 ///\relates xy |
|
189 /// |
|
190 template<typename T> |
|
191 inline std::ostream& operator<<(std::ostream &os, const xy<T>& z) |
|
192 { |
|
193 os << "(" << z.x << ", " << z.y << ")"; |
|
194 return os; |
|
195 } |
|
196 |
|
197 ///Rotate by 90 degrees |
|
198 |
|
199 ///Returns its parameter rotated by 90 degrees in positive direction. |
|
200 ///\relates xy |
|
201 /// |
|
202 template<typename T> |
|
203 inline xy<T> rot90(const xy<T> &z) |
|
204 { |
|
205 return xy<T>(-z.y,z.x); |
|
206 } |
|
207 |
|
208 ///Rotate by 270 degrees |
|
209 |
|
210 ///Returns its parameter rotated by 90 degrees in negative direction. |
|
211 ///\relates xy |
|
212 /// |
|
213 template<typename T> |
|
214 inline xy<T> rot270(const xy<T> &z) |
|
215 { |
|
216 return xy<T>(z.y,-z.x); |
|
217 } |
|
218 |
|
219 |
|
220 |
|
221 /// A class to calculate or store the bounding box of plainvectors. |
|
222 |
|
223 /// A class to calculate or store the bounding box of plainvectors. |
|
224 /// |
|
225 ///\author Attila Bernath |
|
226 template<typename T> |
|
227 class BoundingBox { |
|
228 xy<T> bottom_left, top_right; |
|
229 bool _empty; |
|
230 public: |
|
231 |
|
232 ///Default constructor: creates an empty bounding box |
|
233 BoundingBox() { _empty = true; } |
|
234 |
|
235 ///Constructing the instance from one point |
|
236 BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; } |
|
237 |
|
238 ///Were any points added? |
|
239 bool empty() const { |
|
240 return _empty; |
|
241 } |
|
242 |
|
243 ///Makes the BoundingBox empty |
|
244 void clear() { |
|
245 _empty=1; |
|
246 } |
|
247 |
|
248 ///Gives back the bottom left corner (if the bounding box is empty, then the return value is not defined) |
|
249 xy<T> bottomLeft() const { |
|
250 return bottom_left; |
|
251 } |
|
252 |
|
253 ///Gives back the top right corner (if the bounding box is empty, then the return value is not defined) |
|
254 xy<T> topRight() const { |
|
255 return top_right; |
|
256 } |
|
257 |
|
258 ///Gives back the bottom right corner (if the bounding box is empty, then the return value is not defined) |
|
259 xy<T> bottomRight() const { |
|
260 return xy<T>(top_right.x,bottom_left.y); |
|
261 } |
|
262 |
|
263 ///Gives back the top left corner (if the bounding box is empty, then the return value is not defined) |
|
264 xy<T> topLeft() const { |
|
265 return xy<T>(bottom_left.x,top_right.y); |
|
266 } |
|
267 |
|
268 ///Gives back the bottom of the box (if the bounding box is empty, then the return value is not defined) |
|
269 T bottom() const { |
|
270 return bottom_left.y; |
|
271 } |
|
272 |
|
273 ///Gives back the top of the box (if the bounding box is empty, then the return value is not defined) |
|
274 T top() const { |
|
275 return top_right.y; |
|
276 } |
|
277 |
|
278 ///Gives back the left side of the box (if the bounding box is empty, then the return value is not defined) |
|
279 T left() const { |
|
280 return bottom_left.x; |
|
281 } |
|
282 |
|
283 ///Gives back the right side of the box (if the bounding box is empty, then the return value is not defined) |
|
284 T right() const { |
|
285 return top_right.x; |
|
286 } |
|
287 |
|
288 ///Gives back the height of the box (if the bounding box is empty, then the return value is not defined) |
|
289 T height() const { |
|
290 return top_right.y-bottom_left.y; |
|
291 } |
|
292 |
|
293 ///Gives back the width of the box (if the bounding box is empty, then the return value is not defined) |
|
294 T width() const { |
|
295 return top_right.x-bottom_left.x; |
|
296 } |
|
297 |
|
298 ///Checks whether a point is inside a bounding box |
|
299 bool inside(const xy<T>& u){ |
|
300 if (_empty) |
|
301 return false; |
|
302 else{ |
|
303 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && |
|
304 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); |
|
305 } |
|
306 } |
|
307 |
|
308 ///Increments a bounding box with a point |
|
309 BoundingBox& operator +=(const xy<T>& u){ |
|
310 if (_empty){ |
|
311 bottom_left=top_right=u; |
|
312 _empty = false; |
|
313 } |
|
314 else{ |
|
315 if (bottom_left.x > u.x) bottom_left.x = u.x; |
|
316 if (bottom_left.y > u.y) bottom_left.y = u.y; |
|
317 if (top_right.x < u.x) top_right.x = u.x; |
|
318 if (top_right.y < u.y) top_right.y = u.y; |
|
319 } |
|
320 return *this; |
|
321 } |
|
322 |
|
323 ///Sums a bounding box and a point |
|
324 BoundingBox operator +(const xy<T>& u){ |
|
325 BoundingBox b = *this; |
|
326 return b += u; |
|
327 } |
|
328 |
|
329 ///Increments a bounding box with an other bounding box |
|
330 BoundingBox& operator +=(const BoundingBox &u){ |
|
331 if ( !u.empty() ){ |
|
332 *this += u.bottomLeft(); |
|
333 *this += u.topRight(); |
|
334 } |
|
335 return *this; |
|
336 } |
|
337 |
|
338 ///Sums two bounding boxes |
|
339 BoundingBox operator +(const BoundingBox& u){ |
|
340 BoundingBox b = *this; |
|
341 return b += u; |
|
342 } |
|
343 |
|
344 };//class Boundingbox |
|
345 |
|
346 |
|
347 ///Map of x-coordinates of an xy<>-map |
|
348 |
|
349 ///\ingroup maps |
|
350 /// |
|
351 template<class M> |
|
352 class XMap |
|
353 { |
|
354 typename SmartReference<M>::Type _map; |
|
355 public: |
|
356 typedef True NeedCopy; |
|
357 |
|
358 typedef typename M::Value::Value Value; |
|
359 typedef typename M::Key Key; |
|
360 ///\e |
|
361 XMap(typename SmartParameter<M>::Type map) : _map(map) {} |
|
362 Value operator[](Key k) const {return _map[k].x;} |
|
363 void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));} |
|
364 }; |
|
365 |
|
366 ///Returns an \ref XMap class |
|
367 |
|
368 ///This function just returns an \ref XMap class. |
|
369 /// |
|
370 ///\ingroup maps |
|
371 ///\relates XMap |
|
372 template<class M> |
|
373 inline XMap<M> xMap(M &m) |
|
374 { |
|
375 return XMap<M>(m); |
|
376 } |
|
377 |
|
378 template<class M> |
|
379 inline XMap<M> xMap(const M &m) |
|
380 { |
|
381 return XMap<M>(m); |
|
382 } |
|
383 |
|
384 ///Constant (read only) version of \ref XMap |
|
385 |
|
386 ///\ingroup maps |
|
387 /// |
|
388 template<class M> |
|
389 class ConstXMap |
|
390 { |
|
391 typename SmartConstReference<M>::Type _map; |
|
392 public: |
|
393 typedef True NeedCopy; |
|
394 |
|
395 typedef typename M::Value::Value Value; |
|
396 typedef typename M::Key Key; |
|
397 ///\e |
|
398 ConstXMap(const M &map) : _map(map) {} |
|
399 Value operator[](Key k) const {return _map[k].x;} |
|
400 }; |
|
401 |
|
402 ///Returns a \ref ConstXMap class |
|
403 |
|
404 ///This function just returns an \ref ConstXMap class. |
|
405 /// |
|
406 ///\ingroup maps |
|
407 ///\relates ConstXMap |
|
408 template<class M> |
|
409 inline ConstXMap<M> xMap(const M &m) |
|
410 { |
|
411 return ConstXMap<M>(m); |
|
412 } |
|
413 |
|
414 ///Map of y-coordinates of an xy<>-map |
|
415 |
|
416 ///\ingroup maps |
|
417 /// |
|
418 template<class M> |
|
419 class YMap |
|
420 { |
|
421 typename SmartReference<M>::Type _map; |
|
422 public: |
|
423 typedef True NeedCopy; |
|
424 |
|
425 typedef typename M::Value::Value Value; |
|
426 typedef typename M::Key Key; |
|
427 ///\e |
|
428 YMap(typename SmartParameter<M>::Type map) : _map(map) {} |
|
429 Value operator[](Key k) const {return _map[k].y;} |
|
430 void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} |
|
431 }; |
|
432 |
|
433 ///Returns an \ref YMap class |
|
434 |
|
435 ///This function just returns an \ref YMap class. |
|
436 /// |
|
437 ///\ingroup maps |
|
438 ///\relates YMap |
|
439 template<class M> |
|
440 inline YMap<M> yMap(M &m) |
|
441 { |
|
442 return YMap<M>(m); |
|
443 } |
|
444 |
|
445 template<class M> |
|
446 inline YMap<M> yMap(const M &m) |
|
447 { |
|
448 return YMap<M>(m); |
|
449 } |
|
450 |
|
451 ///Constant (read only) version of \ref YMap |
|
452 |
|
453 ///\ingroup maps |
|
454 /// |
|
455 template<class M> |
|
456 class ConstYMap |
|
457 { |
|
458 typename SmartConstReference<M>::Type _map; |
|
459 public: |
|
460 typedef True NeedCopy; |
|
461 |
|
462 typedef typename M::Value::Value Value; |
|
463 typedef typename M::Key Key; |
|
464 ///\e |
|
465 ConstYMap(const M &map) : _map(map) {} |
|
466 Value operator[](Key k) const {return _map[k].y;} |
|
467 }; |
|
468 |
|
469 ///Returns a \ref ConstYMap class |
|
470 |
|
471 ///This function just returns an \ref ConstYMap class. |
|
472 /// |
|
473 ///\ingroup maps |
|
474 ///\relates ConstYMap |
|
475 template<class M> |
|
476 inline ConstYMap<M> yMap(const M &m) |
|
477 { |
|
478 return ConstYMap<M>(m); |
|
479 } |
|
480 |
|
481 |
|
482 ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map |
|
483 |
|
484 ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map |
|
485 ///\ingroup maps |
|
486 /// |
|
487 template<class M> |
|
488 class NormSquareMap |
|
489 { |
|
490 typename SmartConstReference<M>::Type _map; |
|
491 public: |
|
492 typedef True NeedCopy; |
|
493 |
|
494 typedef typename M::Value::Value Value; |
|
495 typedef typename M::Key Key; |
|
496 ///\e |
|
497 NormSquareMap(const M &map) : _map(map) {} |
|
498 Value operator[](Key k) const {return _map[k].normSquare();} |
|
499 }; |
|
500 |
|
501 ///Returns a \ref NormSquareMap class |
|
502 |
|
503 ///This function just returns an \ref NormSquareMap class. |
|
504 /// |
|
505 ///\ingroup maps |
|
506 ///\relates NormSquareMap |
|
507 template<class M> |
|
508 inline NormSquareMap<M> normSquareMap(const M &m) |
|
509 { |
|
510 return NormSquareMap<M>(m); |
|
511 } |
|
512 |
|
513 /// @} |
|
514 |
|
515 |
|
516 } //namespace lemon |
|
517 |
|
518 #endif //LEMON_XY_H |
|