dim2::BoundingBox improvements

[Peter Kovacs]

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();

[Peter Kovacs]

Some cleanup in the implementation of dim2::BoundingBox?

[Peter Kovacs]

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

[Peter Kovacs]

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

[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.

[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().

[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.

[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().

[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.

[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.

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

[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.

2. 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.

[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.

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

I'm certainly support this.

2. 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.

[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();

[Peter Kovacs]

Replying to alpar:

2. 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).

[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?

[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();

[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.

[Peter Kovacs]

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

[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);
  }
}

[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.

[Peter Kovacs]

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

[Peter Kovacs]

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

[Peter Kovacs]

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

[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.

[Peter Kovacs]

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

[Peter Kovacs]

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

What do you think, should we apply this changeset?

[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.

[Peter Kovacs]

Replying to alpar:

I cannot apply this with --exact.

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

[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.

[Peter Kovacs]

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

[Peter Kovacs]

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

[Alpar Juttner]

Replying to kpeter:

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

Yes, for sure.