Remove parametrization of end iterators #2168

frozar · 2017-12-23T08:25:54Z

I add an octree test to check the behavior of current iterator with a 'for loop' (which is the main usage in reality I think). This test curently fails. In the second for loop, I got this message:

test_octree_iterator: /home/frozar/wk/pcl_repo/octree/include/pcl/octree/octree_iterator.h:190:
pcl::octree::OctreeNode* pcl::octree::OctreeIteratorBase<OctreeT>::getCurrentOctreeNode() const [with OctreeT = pcl::octree::OctreeBase<int>]:
Assertion `current_state_!=0' failed.

I think that the iterator goes over every node of depth egal to 0 and 1, as expected, but it is never equal to the end iterator. If you look at the source:

pcl/octree/include/pcl/octree/octree_iterator.h

Lines 131 to 139 in 6d4c5c8

    
           bool operator==(const OctreeIteratorBase& other) const 
        
           { 
        
             return (this == &other) || 
        
                       ((octree_ == other.octree_) && 
        
                        (max_octree_depth_ == other.max_octree_depth_) && 
        
                        ((current_state_ == other.current_state_) || // end state case 
        
                         (current_state_ && other.current_state_ &&  // null dereference protection 
        
                           (current_state_->key_ == other.current_state_->key_)))); 
        
           }

to be equal, two iterators must have the same max_octree_depth value. I'm not sure checking that is fair. When you look at the creation of the end iterator:

pcl/octree/include/pcl/octree/octree_base.h

Lines 118 to 121 in 6d4c5c8

    
           const Iterator end (unsigned int max_depth_arg = 0u) 
        
           { 
        
             return Iterator (this, max_depth_arg? max_depth_arg : this->octree_depth_ , NULL); 
        
           };

the default max_depth_arg is 0, so max depth of the end iterator will be the depth of the octree by default. So in a for loop, when one specifies a max depth inferior to the depth of an octree, the exit condition will never match.

Proposition

delete the check max_octree_depth_ == other.max_octree_depth_
delete the max_depth_arg for the end iterators, it is not necessary

SergioRAgostinho · 2017-12-24T01:30:32Z

I don't agree with what you're proposing but maybe I'm failing to see the point. Maybe it's better to elaborate on the changes you want by actually implementing them, plus the necessary adjustments to the units tests.

Based simply on what your wrote it's still unclear why you don't think it's "fair". When you use octree.begin(depth) you need to use the appropriate octree.end(depth). I believe that if the begin iterator is parameterized on a desired depth, the end iterator must also be.

Iterators with different max depths don't perform traversal the same way, therefore the max depth needs to be taken into account during the equivalence comparison. If something is really equal, it means that if you apply the same operations to both "copies", they need to end up in the same state after those operations. With your proposal, you can no longer ensure this.

frozar · 2017-12-24T06:29:21Z

When you use octree.begin(depth) you need to use the appropriate octree.end(depth).

This is the point of my proposition. Before the recent change of the iterator implementation, whatever the depth you use to walk over an octree, it was possible to reach the exit condition with an octree.end(), without specifying the depth accordingly to the begin iterator.

My preference is to allow the use of octree.end() whatever the initial depth of the begin iterator. What I propose it to sacrifice the checking of max_octree_depth_ during comparison, and I know you're right without this check, you cannot know if two iterators are really equivalent.

I don't want to care about the initial depth of an iterator to parametrise the end iterator accordingly. Maybe it's possible to adjust the comparison operator to get both behavior:

say two iterators are equivalent,
say an iterator is in its end state whatever the max_octree_depth_ is.

I'll do another proposition.

frozar · 2017-12-24T06:53:37Z

In my last commit, I modify the comparison of iterator to preserve/get the behaviors I was talking about.

Of course after this change, on the unit test './test/octree/test_octree_iterator' I get the following failures:

[  FAILED  ] 6 tests, listed below:
[  FAILED  ] OctreeBaseBeginEndIteratorsTest.End
[  FAILED  ] OctreeBaseBeginEndIteratorsTest.LeafEnd
[  FAILED  ] OctreeBaseBeginEndIteratorsTest.DepthEnd
[  FAILED  ] OctreeBaseBeginEndIteratorsTest.BreadthEnd
[  FAILED  ] OctreePointCloudAdjacencyBeginEndIteratorsTest.DepthEnd
[  FAILED  ] OctreePointCloudAdjacencyBeginEndIteratorsTest.LeafEnd

as expected.

@SergioRAgostinho : Before to go further, do you agree with the spirit of this comparison operator?

SergioRAgostinho · 2017-12-24T14:53:56Z

Iterators with different max depths don't perform traversal the same way, therefore the max depth needs to be taken into account during the equivalence comparison. If something is really equal, it means that if you apply the same operations to both "copies", they need to end up in the same state after those operations. With your proposal, you can no longer ensure this.

This is the main point I'm not willing to violate/wave. If you come up with a solution which respects this constraint and doesn't require octree.end() to be parameterized on the depth, then I'm totally in favor of merging it.

I understand passing a parameter to end() doesn't feel normal, but passing a parameter to begin() is also non existent in the standard library.

SergioRAgostinho · 2017-12-24T15:00:09Z

@SergioRAgostinho : Before to go further, do you agree with the spirit of this comparison operator?

Just noticed you asked me this directly. Can you change the failing units tests to showcase the new logic you implemented with your modifications i.e., modify them so that they all pass.

Edit: In theory your comparison logic should do it. You'll need to remove all the end methods I added, to stop accepting a depth parameter.

taketwo · 2017-12-25T11:27:44Z

My preference is to allow the use of octree.end() whatever the initial depth of the begin iterator.

As far as I can see, our iterators are not decrementable. If they were, end() would absolutely need to parametrized. But in currently situation it is maybe okay to make it parameterless. Just my two cents.

frozar · 2017-12-25T17:40:19Z

Ok, in this pull request, we have:

add a new octree test,
update the operator==() to be able to use the end iterator method without any max depth parameter,
delete the max_octree_depth_ of the end() iterator methods,
update the previous octree test to respect the new logic: end iterators don't take care of the max depth parameter.

Ready for a review.

SergioRAgostinho · 2017-12-26T10:51:04Z

test/octree/test_octree_iterator.cpp

-
-  EXPECT_NE (it_m_1, it_m_2);
-  EXPECT_EQ (it_m_2, it_m); // tree depth is 2
-  EXPECT_NE (it_m_1, it_m_b_1);


You should leave the test in which you verify that the end iterators from different octrees are not the same.

These tests concern iterators from different depth and differnet octree. The test about iterators from different octrees is preserved above.

frozar

Wait for your feedback.

frozar · 2017-12-26T16:28:15Z

test/octree/test_octree_iterator.cpp

@@ -258,16 +258,6 @@ TEST_F (OctreeBaseBeginEndIteratorsTest, End)
  EXPECT_EQ (it_a_1, it_a_2);
  EXPECT_NE (it_a_1, it_b);
  EXPECT_NE (it_a_2, it_b);


@SergioRAgostinho: This is the test about iterator from different octrees.

frozar · 2017-12-27T13:55:26Z

A rebase has been done.

taketwo · 2018-01-02T10:50:44Z

octree/include/pcl/octree/octree_iterator.h

+                     ((!(current_state_) && !(other.current_state_)) || // end state case
+                      ((max_octree_depth_ == other.max_octree_depth_) &&
+                       (current_state_ && other.current_state_ &&  // null dereference protection
+                        (current_state_->key_ == other.current_state_->key_)))));


Am I the only one who finds this return statement extremely convoluted and confusing? What about something like this? I suppose the compiler will produce the same assembly anyway.

if (this == &other) // same object return true; if (octree_ != other.octree_) // refer to different octrees return false; if (!current_state_ && !other.current_state_) // both are end iterators return true; if (max_octree_depth_ == other.max_octree_depth_ && current_state_ && other.current_state_ && // null dereference protection current_state_->key_ == other.current_state_.key_) return true; return false;

I should test it, but I completely agree with you, your proposition is obviously more readable @taketwo 👍

Adapt the operator==() of iterator to not take into account of the depth for iterators in end state.

…rator.

taketwo · 2018-01-27T08:11:50Z

BTW, why are we breaking API without first deprecating it? I think we should keep parametrized versions for several releases.

SergioRAgostinho · 2018-01-27T08:13:33Z

IIRC I introduced the parameterized version in this development stage. It never saw a public release. Or did I overlook something?

Edit: Yep, just confirmed it. ABI Laboratory is reporting 100% between this current version and 1.8.1 for libpcl_octree. Supposedly it compiled the master branch on 2018-01-04 12:55, ~~already after we pushed this~~.

taketwo · 2018-01-27T08:25:10Z

But parametrized versions have been around like... forever. Here is how OctreeBase looked in 1.8.1: https://github.com/PointCloudLibrary/pcl/blob/pcl-1.8.1/octree/include/pcl/octree/octree_base.h, it has parameters.

SergioRAgostinho · 2018-01-27T08:29:33Z

The end iterators don't have it. Only the begin ones. This PR just removed the parametrization I introduced in the end iterators. Are you mentioning something else?

~~Even so, the ABI report is completely clean.~~ There was no report generated yet, this was merged Jan 9 and the report is Jan 4

taketwo · 2018-01-27T08:33:51Z

Sorry, apparently I need a second coffee this morning. Everything is alright indeed.

taketwo · 2018-01-27T08:35:13Z

Only... why do we have the "Breaks API" tag then?

SergioRAgostinho · 2018-01-27T08:42:47Z

Well... if you see it individually it breaks the API of the "current snapshot", the same way the parametrization I introduced before broke the ABI. When all changes are combined together, it no longer does. So the question is what is the policy we want to apply in these cases?

I'm perfectly OK with both options (having/not having the API breakage tag) and we can always create more tags to provide more information in cases as special as this one.

taketwo · 2018-01-27T08:56:25Z

I think that the tags are supposed to help us put together a changelog. And in the changelog we list cumulative changes with respect to the previously released version. Whatever happened during the development stage does not really matter. E.g. if we introduced a bug and the fixed it, the world does not need to know about this, right? Same for API changes that were introduced and then removed.

SergioRAgostinho · 2018-01-27T08:57:55Z

I think that the tags are supposed to help us put together a changelog

I'll tag with this in mind from now on.

SergioRAgostinho · 2018-09-25T11:46:20Z

I'm removing the breaks API tag, because it didn't affect the API between 1.8.1 and 1.9.0.

SergioRAgostinho added the needs: more work Specify why not closed/merged yet label Dec 24, 2017

frozar changed the title ~~WIP: Add another octree test~~ [OCTREE] end iterator without parametrisation Dec 25, 2017

SergioRAgostinho added needs: code review Specify why not closed/merged yet and removed needs: more work Specify why not closed/merged yet labels Dec 26, 2017

SergioRAgostinho reviewed Dec 26, 2017

View reviewed changes

frozar commented Dec 26, 2017

View reviewed changes

frozar force-pushed the add_test_octree branch from 42faab9 to e3e23af Compare December 27, 2017 12:21

frozar force-pushed the add_test_octree branch from e3e23af to 2b4a7d1 Compare December 29, 2017 06:12

taketwo reviewed Jan 2, 2018

View reviewed changes

frozar force-pushed the add_test_octree branch from d521c6e to 601288f Compare January 3, 2018 17:13

frozar mentioned this pull request Jan 8, 2018

Implementation of the iterator 'OctreeFixedDepthIterator'. #1983

Merged

frozar added 6 commits January 8, 2018 09:11

[TEST] Octree: Add a 'for loop' test: currently fail.

35c5b24

[OCTREE] Comparison operator: deal with end iterator

4de1eae

Adapt the operator==() of iterator to not take into account of the depth for iterators in end state.

[TEST:OCTREE] Delete tests about end iterator with dfferent depth.

6196c84

[OCTREE] Delete the default parameter 'max_depth_arg' for all end ite…

510ae01

…rator.

[ITERATOR] Rewrite operator== of octree iterator.

e50a3d2

[TEST] Rename and adapt the For Loop test for every iterators.

8af7753

frozar force-pushed the add_test_octree branch from 601288f to 8af7753 Compare January 8, 2018 08:12

SergioRAgostinho approved these changes Jan 9, 2018

View reviewed changes

SergioRAgostinho added changelog: API break Meta-information for changelog generation and removed needs: code review Specify why not closed/merged yet labels Jan 9, 2018

SergioRAgostinho merged commit 491819b into PointCloudLibrary:master Jan 9, 2018

frozar deleted the add_test_octree branch January 9, 2018 12:59

taketwo removed the changelog: API break Meta-information for changelog generation label Jan 27, 2018

SergioRAgostinho mentioned this pull request Sep 2, 2018

Change Log generation tool. Automates change log generation. #2396

Merged

taketwo changed the title ~~[OCTREE] end iterator without parametrisation~~ Remove parametrization of end iterators Sep 2, 2018

taketwo added changelog: API break Meta-information for changelog generation module: octree labels Sep 2, 2018

SergioRAgostinho removed the changelog: API break Meta-information for changelog generation label Sep 25, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Remove parametrization of end iterators #2168

Remove parametrization of end iterators #2168

frozar commented Dec 23, 2017

SergioRAgostinho commented Dec 24, 2017

frozar commented Dec 24, 2017

frozar commented Dec 24, 2017

SergioRAgostinho commented Dec 24, 2017 •

edited

Loading

SergioRAgostinho commented Dec 24, 2017 •

edited

Loading

taketwo commented Dec 25, 2017

frozar commented Dec 25, 2017

SergioRAgostinho Dec 26, 2017

frozar Dec 26, 2017

frozar left a comment

frozar Dec 26, 2017

frozar commented Dec 27, 2017

taketwo Jan 2, 2018

frozar Jan 2, 2018

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018 •

edited

Loading

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018 •

edited

Loading

taketwo commented Jan 27, 2018

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018

SergioRAgostinho commented Sep 25, 2018

	bool operator==(const OctreeIteratorBase& other) const
	{
	return (this == &other) \|\|
	((octree_ == other.octree_) &&
	(max_octree_depth_ == other.max_octree_depth_) &&
	((current_state_ == other.current_state_) \|\| // end state case
	(current_state_ && other.current_state_ && // null dereference protection
	(current_state_->key_ == other.current_state_->key_))));
	}

	const Iterator end (unsigned int max_depth_arg = 0u)
	{
	return Iterator (this, max_depth_arg? max_depth_arg : this->octree_depth_ , NULL);
	};

Remove parametrization of end iterators #2168

Remove parametrization of end iterators #2168

Conversation

frozar commented Dec 23, 2017

Proposition

SergioRAgostinho commented Dec 24, 2017

frozar commented Dec 24, 2017

frozar commented Dec 24, 2017

SergioRAgostinho commented Dec 24, 2017 • edited Loading

SergioRAgostinho commented Dec 24, 2017 • edited Loading

taketwo commented Dec 25, 2017

frozar commented Dec 25, 2017

SergioRAgostinho Dec 26, 2017

Choose a reason for hiding this comment

frozar Dec 26, 2017

Choose a reason for hiding this comment

frozar left a comment

Choose a reason for hiding this comment

frozar Dec 26, 2017

Choose a reason for hiding this comment

frozar commented Dec 27, 2017

taketwo Jan 2, 2018

Choose a reason for hiding this comment

frozar Jan 2, 2018

Choose a reason for hiding this comment

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018 • edited Loading

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018 • edited Loading

taketwo commented Jan 27, 2018

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018

taketwo commented Jan 27, 2018

SergioRAgostinho commented Jan 27, 2018

SergioRAgostinho commented Sep 25, 2018

SergioRAgostinho commented Dec 24, 2017 •

edited

Loading

SergioRAgostinho commented Dec 24, 2017 •

edited

Loading

SergioRAgostinho commented Jan 27, 2018 •

edited

Loading

SergioRAgostinho commented Jan 27, 2018 •

edited

Loading