COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 11 years ago

#126 closed enhancement (fixed)

dim2::BoundingBox improvements

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.0 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

I made patch files that improves the implementation of dim2::BoundingBox and the related test file.

The current implementation of the empty() function is not correct in all cases. E.g. in the following code it returns false, but the coordinates of the box is ((1,1),(2,0)), so it is empty.

  dim2::BoundingBox b(1,1,2,2);
  b.top(0);
  std::cout << b.empty();

Attachments (9)

dim2_bounding_box_2ccb860dfdcb.patch (10.9 KB) - added by Peter Kovacs 11 years ago.
Some cleanup in the implementation of dim2::BoundingBox?
dim_test_37bc38e00613.patch (1.9 KB) - added by Peter Kovacs 11 years ago.
Improve test/dim_test.cc. It depends on [2ccb860dfdcb].
dim2_bb_0b0f802b14aa.patch (12.6 KB) - added by Peter Kovacs 11 years ago.
dim_test_e21124d389ac.patch (1.9 KB) - added by Peter Kovacs 11 years ago.
dim2_bb_92f046dd7f6c.patch (10.8 KB) - added by Peter Kovacs 11 years ago.
dim_test_dbe3fc9c875d.patch (1.9 KB) - added by Peter Kovacs 11 years ago.
d0aae16df1bb.patch (1.8 KB) - added by Peter Kovacs 11 years ago.
4eb768c0cccc.patch (9.6 KB) - added by Peter Kovacs 11 years ago.
dbe309b5e855.patch (12.8 KB) - added by Peter Kovacs 11 years ago.

Download all attachments as: .zip

Change History (38)

Changed 11 years ago by Peter Kovacs

Some cleanup in the implementation of dim2::BoundingBox?

Changed 11 years ago by Peter Kovacs

Attachment: dim_test_37bc38e00613.patch added

Improve test/dim_test.cc. It depends on [2ccb860dfdcb].

comment:1 Changed 11 years ago by Peter Kovacs

Status: newassigned

[2ccb860dfdcb] modifies the implementation, [37bc38e00613] modifies the test file (it depends on the former one).

comment:2 in reply to:  description ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

I made patch files that improves the implementation of dim2::BoundingBox and the related test file.

The current implementation of the empty() function is not correct in all cases. E.g. in the following code it returns false, but the coordinates of the box is ((1,1),(2,0)), so it is empty.

  dim2::BoundingBox b(1,1,2,2);
  b.top(0);
  std::cout << b.empty();

I'm not sure if we should allow this. For me it is more reasonable to require the top() must always be at least as high as the bottom(). And also, it should be the user's responsibility to keep this invariant.

In other words, I do not like too much this "implicit" emptying of a BoundingBox. Or do you know any practical use case for this behavior?

Of course, the documentation should be more specific in this question, particularly if we keep the current behavior.

comment:3 in reply to:  2 ; Changed 11 years ago by Balazs Dezso

Replying to alpar:

Replying to kpeter:

I made patch files that improves the implementation of dim2::BoundingBox and the related test file.

The current implementation of the empty() function is not correct in all cases. E.g. in the following code it returns false, but the coordinates of the box is ((1,1),(2,0)), so it is empty.

  dim2::BoundingBox b(1,1,2,2);
  b.top(0);
  std::cout << b.empty();

I'm not sure if we should allow this. For me it is more reasonable to require the top() must always be at least as high as the bottom(). And also, it should be the user's responsibility to keep this invariant.

In other words, I do not like too much this "implicit" emptying of a BoundingBox. Or do you know any practical use case for this behavior?

Of course, the documentation should be more specific in this question, particularly if we keep the current behavior.

In my opinion, that the bottom() <= top() and left() <= right() could be invariant in the class, what the user should guarantee (assert or debug would be recommended). However, in my point of view, the problem is come from that the class is a bounding box, but it provides some general box features. The best way would be that, if the class was renamed to simply Box, the empty() function was renamed to undefined().

comment:4 in reply to:  2 ; Changed 11 years ago by Peter Kovacs

Replying to alpar:

In other words, I do not like too much this "implicit" emptying of a BoundingBox. Or do you know any practical use case for this behavior?

The main reason for creating this ticket was the incosistent behavior of the operator& function and the other functions. The other functions like top() and bottom() don't check whether bottom<=top or left<=right, however the intersection method sets the empty parameter according to these comparisons.

Maybe it would be better if all functions checked or all functions did not checked these conditions.

comment:5 in reply to:  3 Changed 11 years ago by Peter Kovacs

Replying to deba:

In my opinion, that the bottom() <= top() and left() <= right() could be invariant in the class, what the user should guarantee (assert or debug would be recommended).

What about just setting empty=true in the problematic functions (bottom(), top(), left(), right(), bootmLeft(), topRgiht() etc.) if one of the conditions are violated? Or assert/debug would be better?

The above solution would be easier than the suggested one. I chose that one only to avoid making these setting functions slightly slower. However it needs the empty() function to be slower.

Maybe it is allowable to perform a check in these functions to keep the _empty variable consistent. E.g.:

void left(T t) {
  _bottom_left.x = t;
  _empty = _empty || _bottom_left.x > _top_right.x;
}

Would you like this solution?

However, in my point of view, the problem is come from that the class is a bounding box, but it provides some general box features. The best way would be that, if the class was renamed to simply Box, the empty() function was renamed to undefined().

I support the BoundingBox --> Box renaming, but I do not find undefined() better than empty().

comment:6 in reply to:  4 Changed 11 years ago by Alpar Juttner

Replying to kpeter:

The main reason for creating this ticket was the incosistent behavior of the operator& function and the other functions. The other functions like top() and bottom() don't check whether bottom<=top or left<=right, however the intersection method sets the empty parameter according to these comparisons.

I can't see any inconsistency here. The checking is operatior& is because this is how the intersection of two box must be computed. The invariant we have currently is that

  • if _empty is true, then the values of top, bottom, left, and right are undefined
  • if _empty is false, then the top>=bottom and left>=right.

Currently all operations keep this invariant except top(), bottom(), left() and right(), where it is the user's responsibility.

Maybe it would be better if all functions checked or all functions did not checked these conditions.

I don't think operator&() does more checking than the others and what is absolute necessary for setting the values appropriately.

comment:7 Changed 11 years ago by Peter Kovacs

So there are only two questions.

  1. The implementation of top(), bottom(), left() and right():
    1. Do not check conditions, it is the user's responsibility (the current behavior).
    2. Check conditions with assert/debug.
    3. Set _empty=true if the conditions are violated.
  1. Should we rename the followings?
    1. BoundingBox --> Box
    2. empty() --> undefined()

comment:8 in reply to:  7 ; Changed 11 years ago by Balazs Dezso

Replying to kpeter:

So there are only two questions.

  1. The implementation of top(), bottom(), left() and right():
    1. Do not check conditions, it is the user's responsibility (the current behavior).
    2. Check conditions with assert/debug.
    3. Set _empty=true if the conditions are violated.

I think b. is the correct solution, it is logically equal to the a., but it helps to find bugs in the program.

  1. Should we rename the followings?
    1. BoundingBox --> Box
    2. empty() --> undefined()

I think, it should be done. I would also drop the _empty flag from the type, and I would use a state, which violates the invariants for undefined.

comment:9 in reply to:  8 ; Changed 11 years ago by Alpar Juttner

Replying to deba:

Replying to kpeter:

  1. The implementation of top(), bottom(), left() and right():
    1. Do not check conditions, it is the user's responsibility (the current behavior).
    2. Check conditions with assert/debug.
    3. Set _empty=true if the conditions are violated.

I think b. is the correct solution, it is logically equal to the a., but it helps to find bugs in the program.

I agree. a. and b. are equivalent and this should be our choice.

  1. Should we rename the followings?
    1. BoundingBox --> Box

I'm certainly support this.

  1. empty() --> undefined()

I'm not sure. I'm obviously biased, for I was who introduced empty(). But I still slightly prefer it to the undefined()/unset(), because it is shorter and easier to remember. I'm sure that If we change, I will always forget if it is unset() or undefined().

I think, it should be done. I would also drop the _empty flag from the type, and I would use a state which violates the invariants for undefined.

It is not trivial to do in a type independent way, and more importantly it may confuse the debug checking. I don't think the extra bool member causes real efficiency drop, but it make the implementation a lot easier.

comment:10 Changed 11 years ago by Peter Kovacs

I found another problem with the current implementation.

The following code works properly.

dim2::BoundingBox bb(1,1,2,2);
std::cout << bb.empty();

However the following one results empty=true.

dim2::BoundingBox bb;
bb.bottomLeft(1,1);
bb.topRight(2,2);
std::cout << bb.empty();

comment:11 in reply to:  9 Changed 11 years ago by Peter Kovacs

Replying to alpar:

  1. Should we rename the followings?
    1. BoundingBox --> Box

I'm certainly support this.

Okay. Should we rename the class? Than the doc should also be modified. E.g. it is not clear what "increments a box with a point" means (if we use box instead of bounding box).

comment:12 Changed 11 years ago by Peter Kovacs

Another question: should we implement an operator<< and operator>> for the BoundingBox (like dim2::Point)? E.g. ((1,2),(3,4))

Btw. the operator<< prints a Point like (1, 2) not (1,2). However the latter one seems to be a better choice if we would like to use LGF IO for graphs that have maps with dim2::Point<> as value type, since we wouldn't have to use quotes. Maybe the former one is a bit nicer. What form should be used?

comment:13 in reply to:  10 Changed 11 years ago by Peter Kovacs

Replying to kpeter:

I found another problem with the current implementation.

There is a note in the doc of functions that set the coordinates of the box: "It should only be used for non-empty box". So maybe the above problem isn't a problem. What do you think? Should the following code result empty=false? Or it is incorrect code.

  dim2::BoundingBox bb;
  bb.bottomLeft(1,1);
  bb.topRight(2,2);
  std::cout << bb.empty();

Changed 11 years ago by Peter Kovacs

Attachment: dim2_bb_0b0f802b14aa.patch added

Changed 11 years ago by Peter Kovacs

Attachment: dim_test_e21124d389ac.patch added

comment:14 Changed 11 years ago by Peter Kovacs

[0b0f802b14aa] contains improvements for the class (e.g. using LEMON_ASSERT in setting functions and constructors). What do you think, is it okay? Should we use LEMON_ASSERT or just LEMON_DEBUG?

[e21124d389ac] improves the test file.

comment:15 Changed 11 years ago by Peter Kovacs

Could someone check [0b0f802b14aa] and [e21124d389ac], please?

comment:16 in reply to:  14 ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

[0b0f802b14aa] contains improvements for the class (e.g. using LEMON_ASSERT in setting functions and constructors). What do you think, is it okay? Should we use LEMON_ASSERT or just LEMON_DEBUG?

We certainly should not use LEMON_ASSERT, but I'm even very concerned about using LEMON_DEBUG. Firstly, I can hardly imagine any realistic scenario when this check would reveal a real programming bug. Therefore it is completely superfluous.

Secondly it causes some very awkward situations. For example if bb is ((0,0),(1,1)), then the code

bb.right(3);
bb.left(2);

is correct, but

bb.left(2);
bb.right(3);

do not pass the invariant test (though the code looks quite OK for me).

Or imagine that you want to write a function to set left and right at the same time using left() and right(). The safe code would look something like this.

void leftRigth(double l,double r)
{
  if(l<=bb.left()) {
    bb.left(l);
    bb.right(r);
  }
  else {
    bb.right(r);
    bb.left(l);
  }
}

comment:17 in reply to:  16 Changed 11 years ago by Peter Kovacs

Replying to alpar:

We certainly should not use LEMON_ASSERT, but I'm even very concerned about using LEMON_DEBUG. Firstly, I can hardly imagine any realistic scenario when this check would reveal a real programming bug. Therefore it is completely superfluous.

Secondly it causes some very awkward situations.

I also found problems like you wrote, but it was first suggested by Balazs. I will remove the LEMON_ASSERT-s.

Changed 11 years ago by Peter Kovacs

Attachment: dim2_bb_92f046dd7f6c.patch added

Changed 11 years ago by Peter Kovacs

Attachment: dim_test_dbe3fc9c875d.patch added

comment:18 Changed 11 years ago by Peter Kovacs

See [92f046dd7f6c] and [dbe3fc9c875d]. They contain the same changes without assertions.

comment:19 Changed 11 years ago by Peter Kovacs

What do you think about the other two questions: renaming and operator<<, operator>>.

comment:20 Changed 11 years ago by Peter Kovacs

Alpar put [92f046dd7f6c] and [dbe3fc9c875d] to the main branch. Thank you.

comment:21 in reply to:  19 Changed 11 years ago by Alpar Juttner

Replying to kpeter:

What do you think about the other two questions: renaming and operator<<, operator>>.

Renaming::

I'm OK with using either Box or BoundingBox. Box is better for it is shorter, BoundingBox is better for it emphasizes its primary use.

stream operators::

I prefer the space-less output.

comment:22 Changed 11 years ago by Peter Kovacs

[d0aae16df1bb] adds stream operators for BoundingBox and makes Point<T>::operator<< to be space-less.

Changed 11 years ago by Peter Kovacs

Attachment: d0aae16df1bb.patch added

comment:23 Changed 11 years ago by Peter Kovacs

[4eb768c0cccc] renames BoundingBox to Box (it depends on [d0aae16df1bb]).

What do you think, should we apply this changeset?

Changed 11 years ago by Peter Kovacs

Attachment: 4eb768c0cccc.patch added

comment:24 in reply to:  22 ; Changed 11 years ago by Alpar Juttner

Replying to kpeter:

[d0aae16df1bb] adds stream operators for BoundingBox and makes Point<T>::operator<< to be space-less.

I cannot apply this with --exact.

comment:25 in reply to:  24 Changed 11 years ago by Peter Kovacs

Replying to alpar:

I cannot apply this with --exact.

I can apply this with --exact. It depends on [f0b89f242745].

comment:26 Changed 11 years ago by Peter Kovacs

[d0aae16df1bb] went to the main branch.

The only outstanding question in this ticket is the renaming. [4eb768c0cccc] is imperfect, if we would like to perform the renaming, this changeset should be extended.

Changed 11 years ago by Peter Kovacs

Attachment: dbe309b5e855.patch added

comment:27 Changed 11 years ago by Peter Kovacs

[dbe309b5e855] renames BoundingBox to Box, and I hope it is correct.

comment:28 Changed 11 years ago by Peter Kovacs

[dbe309b5e855] went to the main branch. Can we close this ticket?

comment:29 in reply to:  28 Changed 11 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

Replying to kpeter:

[dbe309b5e855] went to the main branch. Can we close this ticket?

Yes, for sure.

Note: See TracTickets for help on using tickets.