Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 45099409f4a0
Choose a base ref
...
head repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 8b3c3ac44aaa
Choose a head ref
  • 9 commits
  • 6 files changed
  • 1 contributor

Commits on Oct 29, 2021

  1. Copy the full SHA
    6009e06 View commit details
  2. Copy the full SHA
    289221c View commit details
  3. Make a test faster.

    pleroy committed Oct 29, 2021
    Copy the full SHA
    c5f35c5 View commit details

Commits on Oct 30, 2021

  1. Merge pull request #3177 from pleroy/Fixes

    Serialization of empty segments
    pleroy authored Oct 30, 2021
    Copy the full SHA
    438d530 View commit details
  2. Copy the full SHA
    5753d98 View commit details
  3. Merge pull request #3178 from pleroy/SegmentEnd

    Support for using segments().end() as a marker for nonexistent trajectory segments.
    pleroy authored Oct 30, 2021
    Copy the full SHA
    9eced77 View commit details
  4. Change FindSegment to avoid failing when given a time before the begi…

    …nning of the trajectory.
    pleroy committed Oct 30, 2021
    Copy the full SHA
    b74b638 View commit details
  5. Merge pull request #3179 from pleroy/FindSegment

    Change FindSegment to avoid failing when given a time before the beginning of the trajectory
    pleroy authored Oct 30, 2021
    Copy the full SHA
    9de6bdc View commit details
  6. Copy the full SHA
    8b3c3ac View commit details
9 changes: 6 additions & 3 deletions physics/discrete_traject0ry.hpp
Original file line number Diff line number Diff line change
@@ -73,6 +73,9 @@ class DiscreteTraject0ry : public Trajectory<Frame> {
bool empty() const;
std::int64_t size() const;

// Doesn't invalidate iterators to the first segment.
void clear();

iterator find(Instant const& t) const;

iterator lower_bound(Instant const& t) const;
@@ -86,7 +89,7 @@ class DiscreteTraject0ry : public Trajectory<Frame> {

DiscreteTraject0ry DetachSegments(SegmentIterator begin);
SegmentIterator AttachSegments(DiscreteTraject0ry&& trajectory);
void DeleteSegments(SegmentIterator begin);
void DeleteSegments(SegmentIterator& begin);

// Deletes the trajectory points with a time in [t, end[. Drops the segments
// that are empty as a result.
@@ -134,8 +137,8 @@ class DiscreteTraject0ry : public Trajectory<Frame> {
// t ∈ [t1, t2[. For the last segment, t2 is assumed to be +∞. A 1-point
// segment is never returned, unless it is the last one (because its upper
// bound is assumed to be +∞). Returns segment_by_left_endpoint_->end() iff
// the trajectory is empty(). Fails if t is before the first time of the
// trajectory.
// t is before the first time of the trajectory or if the trajectory is
// empty().
typename SegmentByLeftEndpoint::iterator FindSegment(Instant const& t);
typename SegmentByLeftEndpoint::const_iterator
FindSegment(Instant const& t) const;
79 changes: 49 additions & 30 deletions physics/discrete_traject0ry_body.hpp
Original file line number Diff line number Diff line change
@@ -78,6 +78,13 @@ std::int64_t DiscreteTraject0ry<Frame>::size() const {
return size;
}

template<typename Frame>
void DiscreteTraject0ry<Frame>::clear() {
segments_->erase(std::next(segments_->begin()), segments_->end());
segments_->front().clear();
segment_by_left_endpoint_.clear();
}

template<typename Frame>
typename DiscreteTraject0ry<Frame>::iterator
DiscreteTraject0ry<Frame>::find(Instant const& t) const {
@@ -98,7 +105,8 @@ typename DiscreteTraject0ry<Frame>::iterator
DiscreteTraject0ry<Frame>::lower_bound(Instant const& t) const {
auto const leit = FindSegment(t);
if (leit == segment_by_left_endpoint_.cend()) {
return end();
// This includes an empty trajectory.
return begin();
}
auto const sit = leit->second;
auto const it = sit->lower_bound(t);
@@ -113,7 +121,8 @@ typename DiscreteTraject0ry<Frame>::iterator
DiscreteTraject0ry<Frame>::upper_bound(Instant const& t) const {
auto const leit = FindSegment(t);
if (leit == segment_by_left_endpoint_.cend()) {
return end();
// This includes an empty trajectory.
return begin();
}
auto const sit = leit->second;
auto const it = sit->upper_bound(t);
@@ -225,7 +234,7 @@ DiscreteTraject0ry<Frame>::AttachSegments(
}

template<typename Frame>
void DiscreteTraject0ry<Frame>::DeleteSegments(SegmentIterator const begin) {
void DiscreteTraject0ry<Frame>::DeleteSegments(SegmentIterator& begin) {
segments_->erase(begin.iterator(), segments_->end());
if (segments_->empty()) {
segment_by_left_endpoint_.clear();
@@ -242,6 +251,8 @@ void DiscreteTraject0ry<Frame>::DeleteSegments(SegmentIterator const begin) {
segment_by_left_endpoint_.end());
}
}
// Make sure that the client doesn't try to use the invalid iterator.
begin = segments().end();

DCHECK_OK(ConsistencyStatus());
}
@@ -250,6 +261,7 @@ template<typename Frame>
void DiscreteTraject0ry<Frame>::ForgetAfter(Instant const& t) {
auto const leit = FindSegment(t);
if (leit == segment_by_left_endpoint_.end()) {
clear();
return;
}
auto const sit = leit->second;
@@ -282,7 +294,8 @@ void DiscreteTraject0ry<Frame>::ForgetBefore(Instant const& t) {
return;
}
auto const sit = leit->second;
// This call never makes the segment |*sit| empty.
// This call may make the segment |*sit| empty if |t| is after the end of
// |*sit|.
sit->ForgetBefore(t);
for (auto s = segments_->begin(); s != sit; ++s) {
// This call may either make the segment |*s| empty or leave it with a
@@ -295,10 +308,13 @@ void DiscreteTraject0ry<Frame>::ForgetBefore(Instant const& t) {
// just have truncated.
segment_by_left_endpoint_.erase(segment_by_left_endpoint_.begin(),
std::next(leit));
// Recreate an entry for |sit| with its new left endpoint.
segment_by_left_endpoint_.insert_or_assign(segment_by_left_endpoint_.begin(),
sit->front().time,
sit);
// It |*sit| is not empty, recreate an entry with its new left endpoint.
if (!sit->empty()) {
segment_by_left_endpoint_.insert_or_assign(
segment_by_left_endpoint_.begin(),
sit->front().time,
sit);
}

DCHECK_OK(ConsistencyStatus());
}
@@ -312,15 +328,18 @@ template<typename Frame>
void DiscreteTraject0ry<Frame>::Append(
Instant const& t,
DegreesOfFreedom<Frame> const& degrees_of_freedom) {
auto leit = FindSegment(t);
typename Segments::iterator sit;
if (leit == segment_by_left_endpoint_.end()) {
if (segment_by_left_endpoint_.empty()) {
// If this is the first point appended to this trajectory, insert it in the
// time-to-segment map.
sit = --segments_->end();
leit = segment_by_left_endpoint_.insert_or_assign(
segment_by_left_endpoint_.insert_or_assign(
segment_by_left_endpoint_.end(), t, sit);
} else {
auto const leit = FindSegment(t);
CHECK(leit != segment_by_left_endpoint_.end())
<< "Append at " << t << " before the beginning of the trajectory at "
<< front().time;
// The segment is expected to always have a point copied from its
// predecessor.
sit = leit->second;
@@ -370,7 +389,9 @@ void DiscreteTraject0ry<Frame>::WriteToMessage(
absl::flat_hash_map<DiscreteTrajectorySegment<Frame> const*, int>
segment_to_position;
for (int i = 0; i < tracked.size(); ++i) {
segment_to_position.emplace(&*tracked[i], i);
if (tracked[i] != segments().end()) {
segment_to_position.emplace(&*tracked[i], i);
}
}

// Initialize the tracked positions to be able to recognize if some are
@@ -407,13 +428,6 @@ void DiscreteTraject0ry<Frame>::WriteToMessage(
t.WriteToMessage(segment_by_left_endpoint->mutable_left_endpoint());
segment_by_left_endpoint->set_segment(i);
}

// Check that all the segments in |tracked| were mapped.
// NOTE(phl): This might be too strong a constraint in Entwurf.
for (auto const tracked_position : message->tracked_position()) {
CHECK_NE(serialization::DiscreteTrajectory::MISSING_TRACKED_POSITION,
tracked_position);
}
}

template<typename Frame>
@@ -450,9 +464,12 @@ DiscreteTraject0ry<Frame>::ReadFromMessage(
CHECK_EQ(tracked.size(), message.tracked_position_size());
for (int i = 0; i < message.tracked_position_size(); ++i) {
int const tracked_position = message.tracked_position(i);
CHECK_NE(serialization::DiscreteTrajectory::MISSING_TRACKED_POSITION,
tracked_position);
*tracked[i] = segment_iterators[tracked_position];
if (tracked_position ==
serialization::DiscreteTrajectory::MISSING_TRACKED_POSITION) {
*tracked[i] = trajectory.segments().end();
} else {
*tracked[i] = segment_iterators[tracked_position];
}
}

// Finally restore the left endpoints.
@@ -482,24 +499,26 @@ template<typename Frame>
typename DiscreteTraject0ry<Frame>::SegmentByLeftEndpoint::iterator
DiscreteTraject0ry<Frame>::FindSegment(
Instant const& t) {
if (segment_by_left_endpoint_.empty()) {
auto it = segment_by_left_endpoint_.upper_bound(t);
if (it == segment_by_left_endpoint_.begin()) {
// This includes an empty trajectory.
return segment_by_left_endpoint_.end();
} else {
return --it;
}
auto it = segment_by_left_endpoint_.upper_bound(t);
CHECK(it != segment_by_left_endpoint_.begin()) << "No segment covering " << t;
return --it;
}

template<typename Frame>
typename DiscreteTraject0ry<Frame>::SegmentByLeftEndpoint::const_iterator
DiscreteTraject0ry<Frame>::FindSegment(
Instant const& t) const {
if (segment_by_left_endpoint_.empty()) {
auto it = segment_by_left_endpoint_.upper_bound(t);
if (it == segment_by_left_endpoint_.begin()) {
// This includes an empty trajectory.
return segment_by_left_endpoint_.cend();
} else {
return --it;
}
auto it = segment_by_left_endpoint_.upper_bound(t);
CHECK(it != segment_by_left_endpoint_.begin()) << "No segment covering " << t;
return --it;
}

template<typename Frame>
54 changes: 40 additions & 14 deletions physics/discrete_traject0ry_test.cpp
Original file line number Diff line number Diff line change
@@ -266,6 +266,11 @@ TEST_F(DiscreteTraject0ryTest, LowerBound) {
auto const it = trajectory.lower_bound(t0_ + 14.2 * Second);
EXPECT_TRUE(it == trajectory.end());
}
{
auto const it = trajectory.lower_bound(t0_ - 99 * Second);
auto const& [t, _] = *it;
EXPECT_EQ(t, t0_);
}
}

TEST_F(DiscreteTraject0ryTest, UpperBound) {
@@ -310,6 +315,11 @@ TEST_F(DiscreteTraject0ryTest, UpperBound) {
auto const it = trajectory.upper_bound(t0_ + 14.2 * Second);
EXPECT_TRUE(it == trajectory.end());
}
{
auto const it = trajectory.upper_bound(t0_ - 99 * Second);
auto const& [t, _] = *it;
EXPECT_EQ(t, t0_);
}
}

TEST_F(DiscreteTraject0ryTest, Segments) {
@@ -446,11 +456,12 @@ TEST_F(DiscreteTraject0ryTest, AttachSegments) {
TEST_F(DiscreteTraject0ryTest, DeleteSegments) {
auto trajectory = MakeTrajectory();
auto const first_segment = trajectory.segments().begin();
auto const second_segment = std::next(first_segment);
auto second_segment = std::next(first_segment);
trajectory.DeleteSegments(second_segment);
EXPECT_EQ(1, trajectory.segments().size());
EXPECT_EQ(t0_, trajectory.begin()->time);
EXPECT_EQ(t0_ + 4 * Second, trajectory.rbegin()->time);
EXPECT_TRUE(second_segment == trajectory.segments().end());
}

TEST_F(DiscreteTraject0ryTest, ForgetAfter) {
@@ -470,6 +481,9 @@ TEST_F(DiscreteTraject0ryTest, ForgetAfter) {
EXPECT_EQ(1, trajectory.segments().size());
EXPECT_EQ(t0_, trajectory.begin()->time);
EXPECT_EQ(t0_ + 4 * Second, trajectory.rbegin()->time);

trajectory.ForgetAfter(t0_ - 99 * Second);
EXPECT_TRUE(trajectory.empty());
}

TEST_F(DiscreteTraject0ryTest, ForgetBefore) {
@@ -518,6 +532,9 @@ TEST_F(DiscreteTraject0ryTest, ForgetBefore) {
t0_ + 10 * Second,
t0_ + 9 * Second));
}

trajectory.ForgetBefore(t0_ + 99 * Second);
EXPECT_TRUE(trajectory.empty());
}

TEST_F(DiscreteTraject0ryTest, TMinTMaxEvaluate) {
@@ -546,23 +563,31 @@ TEST_F(DiscreteTraject0ryTest, SerializationRoundTrip) {
auto const trajectory = MakeTrajectory();
auto const trajectory_first_segment = trajectory.segments().begin();
auto const trajectory_second_segment = std::next(trajectory_first_segment);
auto const trajectory_past_the_end = trajectory.segments().end();

serialization::DiscreteTrajectory message1;
trajectory.WriteToMessage(&message1,
/*tracked=*/{trajectory_second_segment},
/*tracked=*/{trajectory_second_segment,
trajectory_past_the_end},
/*exact=*/
{trajectory.lower_bound(t0_ + 2 * Second),
trajectory.lower_bound(t0_ + 3 * Second)});

DiscreteTrajectorySegmentIterator<World> deserialized_second_segment;
DiscreteTrajectorySegmentIterator<World> deserialized_past_the_end;
auto const deserialized_trajectory =
DiscreteTraject0ry<World>::ReadFromMessage(
message1, /*tracked=*/{&deserialized_second_segment});
message1, /*tracked=*/{&deserialized_second_segment,
&deserialized_past_the_end});

// Check that the tracked segment was properly retrieved.
EXPECT_EQ(t0_ + 4 * Second, deserialized_second_segment->begin()->time);
EXPECT_EQ(t0_ + 9 * Second, deserialized_second_segment->rbegin()->time);

// Check that the past-the-end iterator was properly set.
EXPECT_TRUE(deserialized_past_the_end ==
deserialized_trajectory.segments().end());

// Check that the exact points are exact.
EXPECT_EQ(
deserialized_trajectory.lower_bound(t0_ + 2 * Second)->degrees_of_freedom,
@@ -574,7 +599,8 @@ TEST_F(DiscreteTraject0ryTest, SerializationRoundTrip) {
serialization::DiscreteTrajectory message2;
deserialized_trajectory.WriteToMessage(
&message2,
/*tracked=*/{deserialized_second_segment},
/*tracked=*/{deserialized_second_segment,
deserialized_past_the_end},
/*exact=*/
{deserialized_trajectory.lower_bound(t0_ + 2 * Second),
deserialized_trajectory.lower_bound(t0_ + 3 * Second)});
@@ -588,8 +614,8 @@ TEST_F(DiscreteTraject0ryTest, SerializationExactEndpoints) {
Length const r = 2 * Metre;
Time const Δt = 1.0 / 3.0 * Milli(Second);
Instant const t1 = t0_;
Instant const t2 = t0_ + 1000.0 / 7.0 * Second;
Instant const t3 = t0_ + 2000.0 / 11.0 * Second;
Instant const t2 = t0_ + 100.0 / 7.0 * Second;
Instant const t3 = t0_ + 200.0 / 11.0 * Second;
// Downsampling is required for ZFP compression.
DiscreteTrajectorySegment<World>::DownsamplingParameters const
downsampling_parameters{.max_dense_intervals = 100,
@@ -607,9 +633,9 @@ TEST_F(DiscreteTraject0ryTest, SerializationExactEndpoints) {
trajectory);

auto const degrees_of_freedom1 =
trajectory.EvaluateDegreesOfFreedom(t1 + 100 * Second);
trajectory.EvaluateDegreesOfFreedom(t1 + 10 * Second);
auto const degrees_of_freedom2 =
trajectory.EvaluateDegreesOfFreedom(t2 + 20 * Second);
trajectory.EvaluateDegreesOfFreedom(t2 + 2 * Second);

serialization::DiscreteTrajectory message;
trajectory.WriteToMessage(&message, /*tracked=*/{}, /*exact=*/{});
@@ -619,26 +645,26 @@ TEST_F(DiscreteTraject0ryTest, SerializationExactEndpoints) {
DiscreteTraject0ry<World>::ReadFromMessage(message, /*tracked=*/{});

auto const deserialized_degrees_of_freedom1 =
deserialized_trajectory.EvaluateDegreesOfFreedom(t1 + 100 * Second);
deserialized_trajectory.EvaluateDegreesOfFreedom(t1 + 10 * Second);
auto const deserialized_degrees_of_freedom2 =
deserialized_trajectory.EvaluateDegreesOfFreedom(t2 + 20 * Second);
deserialized_trajectory.EvaluateDegreesOfFreedom(t2 + 2 * Second);

// These checks verify that ZFP compression actually happened (so we observe
// small errors on the degrees of freedom).
EXPECT_THAT(
(deserialized_degrees_of_freedom1.position() - World::origin).Norm(),
AbsoluteErrorFrom((degrees_of_freedom1.position() - World::origin).Norm(),
IsNear(0.24_⑴*Milli(Metre))));
IsNear(0.27_⑴*Milli(Metre))));
EXPECT_THAT(deserialized_degrees_of_freedom1.velocity().Norm(),
AbsoluteErrorFrom(degrees_of_freedom1.velocity().Norm(),
IsNear(1.5_⑴ * Micro(Metre) / Second)));
IsNear(82_⑴ * Milli(Metre) / Second)));
EXPECT_THAT(
(deserialized_degrees_of_freedom2.position() - World::origin).Norm(),
AbsoluteErrorFrom((degrees_of_freedom2.position() - World::origin).Norm(),
IsNear(0.16_⑴*Milli(Metre))));
IsNear(0.19_⑴*Milli(Metre))));
EXPECT_THAT(deserialized_degrees_of_freedom2.velocity().Norm(),
AbsoluteErrorFrom(degrees_of_freedom2.velocity().Norm(),
IsNear(0.39_⑴ * Metre / Second)));
IsNear(0.36_⑴ * Metre / Second)));
}

TEST_F(DiscreteTraject0ryTest, DISABLED_SerializationPreΖήνωνCompatibility) {
2 changes: 2 additions & 0 deletions physics/discrete_trajectory_segment.hpp
Original file line number Diff line number Diff line change
@@ -86,6 +86,8 @@ class DiscreteTrajectorySegment : public Trajectory<Frame> {
bool empty() const;
std::int64_t size() const;

void clear();

iterator find(Instant const& t) const;

iterator lower_bound(Instant const& t) const;
Loading