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: bae4f883e7ab
Choose a base ref
...
head repository: mockingbirdnest/Principia
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 4fb24d42ebb4
Choose a head ref
  • 13 commits
  • 5 files changed
  • 1 contributor

Commits on Sep 4, 2021

  1. Try to prepend in Forkable.

    pleroy committed Sep 4, 2021
    Copy the full SHA
    484821f View commit details
  2. Compilation errors.

    pleroy committed Sep 4, 2021
    Copy the full SHA
    0d1f6c2 View commit details
  3. A simple test.

    pleroy committed Sep 4, 2021
    Copy the full SHA
    b462dd3 View commit details

Commits on Sep 5, 2021

  1. One test passing.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    4c9bed4 View commit details
  2. More tests.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    5709b81 View commit details
  3. More tests.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    73f8304 View commit details
  4. Decent test coverage.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    469648b View commit details
  5. A wall of text.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    fae8b9c View commit details
  6. After egg's review.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    1e8ed57 View commit details
  7. Update the tests.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    806ff9a View commit details
  8. Copy the full SHA
    bbf4db3 View commit details
  9. Lint.

    pleroy committed Sep 5, 2021
    Copy the full SHA
    c15a4e8 View commit details
  10. Merge pull request #3122 from pleroy/Prepend2

    A mechanism for prepending a Forkable to another Forkable
    pleroy authored Sep 5, 2021
    Copy the full SHA
    4fb24d4 View commit details
Showing with 602 additions and 0 deletions.
  1. +3 −0 physics/discrete_trajectory.hpp
  2. +8 −0 physics/discrete_trajectory_body.hpp
  3. +30 −0 physics/forkable.hpp
  4. +93 −0 physics/forkable_body.hpp
  5. +468 −0 physics/forkable_test.cpp
3 changes: 3 additions & 0 deletions physics/discrete_trajectory.hpp
Original file line number Diff line number Diff line change
@@ -7,6 +7,7 @@
#include <memory>
#include <optional>
#include <set>
#include <utility>
#include <vector>

#include "absl/status/status.h"
@@ -207,6 +208,8 @@ class DiscreteTrajectory : public Forkable<DiscreteTrajectory<Frame>,
not_null<DiscreteTrajectory*> that() override;
not_null<DiscreteTrajectory const*> that() const override;

std::pair<TimelineConstIterator, bool> timeline_insert(
const typename TimelineConstIterator::value_type& value) override;
TimelineConstIterator timeline_begin() const override;
TimelineConstIterator timeline_end() const override;
TimelineConstIterator timeline_find(Instant const& time) const override;
8 changes: 8 additions & 0 deletions physics/discrete_trajectory_body.hpp
Original file line number Diff line number Diff line change
@@ -8,6 +8,7 @@
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "astronomy/epoch.hpp"
@@ -403,6 +404,13 @@ DiscreteTrajectory<Frame>::that() const {
return this;
}

template<typename Frame>
std::pair<typename DiscreteTrajectory<Frame>::TimelineConstIterator, bool>
DiscreteTrajectory<Frame>::timeline_insert(
const typename TimelineConstIterator::value_type& value) {
return timeline_.insert(value);
}

template<typename Frame>
typename DiscreteTrajectory<Frame>::TimelineConstIterator
DiscreteTrajectory<Frame>::timeline_begin() const {
30 changes: 30 additions & 0 deletions physics/forkable.hpp
Original file line number Diff line number Diff line change
@@ -5,6 +5,7 @@
#include <memory>
#include <optional>
#include <set>
#include <utility>
#include <vector>

#include "absl/container/inlined_vector.h"
@@ -118,6 +119,28 @@ class Forkable {
// |trajectory|.
void DeleteFork(Tr4jectory*& trajectory);

// Prepends |prefix| to |suffix|, which must be a root. |prefix_root| must be
// the root of |prefix|. The algorithm proceeds as follows, where t is the
// start of the timeline of |suffix|:
// 1. Locate the most-forked timeline of |prefix| that contains a point
// (strictly) before t. Call the trajectory containing that timeline T.
// 2. Prepend the beginning (strictly before t) of the timeline of T to the
// timeline of |suffix|.
// 3. Attach the forks (strictly) before t to |suffix|.
// 4. If T is a root, delete the entire tree rooted at T.
// 5. Otherwise, attach |suffix| as a fork of the parent of T instead of T and
// delete T.
// When returning from this method, it is generally not safe to touch any part
// of the tree rooted at |prefix_root|, unless the client knows a lot about
// the structure of the various trajectories (that's the case in tests).
// |suffix.get()| and all its forks are still valid pointers.
// The returned value is the root of the result, and may either be
// |prefix_root| or |suffix|.
static not_null<std::unique_ptr<Tr4jectory>> Prepend(
not_null<std::unique_ptr<Tr4jectory>> prefix_root,
Tr4jectory const& prefix,
not_null<std::unique_ptr<Tr4jectory>> suffix);

// Returns true if this is a root trajectory.
bool is_root() const;

@@ -159,6 +182,8 @@ class Forkable {
virtual not_null<Tr4jectory const*> that() const = 0;

// STL-like operations.
virtual std::pair<TimelineConstIterator, bool> timeline_insert(
const typename TimelineConstIterator::value_type& value) = 0;
virtual TimelineConstIterator timeline_begin() const = 0;
virtual TimelineConstIterator timeline_end() const = 0;
virtual TimelineConstIterator timeline_find(Instant const& time) const = 0;
@@ -179,6 +204,11 @@ class Forkable {
// |timeline_it| may be at end if it denotes the fork time of this object.
not_null<Tr4jectory*> NewFork(TimelineConstIterator const& timeline_it);

// |fork| must be a non-empty root and its first point must be after the last
// point of this object. |fork| is attached to this object as a child at the
// end of the timeline.
void AttachFork(not_null<std::unique_ptr<Tr4jectory>> fork);

// |fork| must be a non-empty root and its first point must be at the same
// time as the last point of this object. |fork| is attached to this object
// as a child at the end of the timeline. The caller must then delete the
93 changes: 93 additions & 0 deletions physics/forkable_body.hpp
Original file line number Diff line number Diff line change
@@ -142,6 +142,75 @@ DeleteFork(Tr4jectory*& trajectory) {
LOG(FATAL) << "argument is not a child of this trajectory";
}

template<typename Tr4jectory, typename It3rator, typename Traits>
not_null<std::unique_ptr<Tr4jectory>>
Forkable<Tr4jectory, It3rator, Traits>::Prepend(
not_null<std::unique_ptr<Tr4jectory>> prefix_root,
Tr4jectory const& prefix,
not_null<std::unique_ptr<Tr4jectory>> suffix) {
CHECK(prefix_root->is_root());
CHECK_EQ(&*prefix_root, &*prefix.root());
CHECK(suffix->is_root());

It3rator it; // In |prefix|.
if (suffix->Empty()) {
it = prefix.end();
} else {
Instant const suffix_begin_time = Traits::time(suffix->begin().current_);
// |it| designates the first point of |prefix| that is at or after the
// beginning of |suffix|.
it = prefix.LowerBound(suffix_begin_time);
}
if (it == prefix.begin()) {
// |prefix| is entirely in the future with respect to |suffix|. Nothing to
// do.
return suffix;
}

// Move |it| to designate a point in |prefix| which is strictly before the
// first point of |suffix|.
--it;
// The trajectory whose timeline is suitable for prepending to |suffix|.
Tr4jectory* trajectory_to_prepend =
const_cast<Tr4jectory*>(&*it.ancestry_.back());
// Remove all the forks that are at or after the first point of |suffix|.
// That may include entire subtrees.
trajectory_to_prepend->DeleteAllForksAfter(Traits::time(it.current_));
// Transfer the end of the timeline of |trajectory_to_prepend| to the
// beginning of the timeline of |suffix|.
for (TimelineConstIterator it2 = trajectory_to_prepend->timeline_begin();
it2 != trajectory_to_prepend->timeline_end() &&
Traits::time(it2) <= Traits::time(it.current_);
++it2) {
auto const [_, inserted] = suffix->timeline_insert(*it2);
CHECK(inserted) << Traits::time(it2);
}

// Adjust the remaining forks of |trajectory_to_prepend| to point in the
// timeline and children of |suffix|.
for (auto& [time, child] : trajectory_to_prepend->children_) {
auto timeline_it = suffix->timeline_find(time);
CHECK(timeline_it != suffix->timeline_end()) << time;
child->position_in_parent_timeline_ = timeline_it;
auto child_it = suffix->children_.emplace(time, std::move(child));
child_it->second->position_in_parent_children_ = child_it;
child_it->second->parent_ = suffix.get();
}

// In all cases, |trajectory_to_prepend| gets deleted because it may now
// contain moved-from pointers to children.
if (trajectory_to_prepend->is_root()) {
return suffix;
} else {
// If needed, attach |suffix| as a fork of the parent of
// |trajectory_to_prepend|.
auto const parent = trajectory_to_prepend->parent_;
parent->DeleteFork(trajectory_to_prepend);
parent->AttachFork(std::move(suffix));
return prefix_root;
}
}

template<typename Tr4jectory, typename It3rator, typename Traits>
bool Forkable<Tr4jectory, It3rator, Traits>::is_root() const {
return parent_ == nullptr;
@@ -387,6 +456,30 @@ not_null<Tr4jectory*> Forkable<Tr4jectory, It3rator, Traits>::NewFork(
return child_forkable.get();
}

template<typename Tr4jectory, typename It3rator, typename Traits>
void Forkable<Tr4jectory, It3rator, Traits>::AttachFork(
not_null<std::unique_ptr<Tr4jectory>> fork) {
CHECK(fork->is_root());
CHECK(!timeline_empty());
auto this_timeline_end = timeline_end();
Instant const this_timeline_back = Traits::time(--this_timeline_end);
if (!fork->timeline_empty()) {
auto const fork_timeline_begin = fork->timeline_begin();
CHECK_LT(this_timeline_back, Traits::time(fork_timeline_begin));
}

// Insert |fork| in the |children_| of this object.
auto const child_it = children_.emplace_hint(children_.end(),
this_timeline_back,
std::move(fork));

// Set the pointer into this object. Note that |fork| is no longer usable.
child_it->second->parent_ = that();
child_it->second->position_in_parent_children_ = child_it;
child_it->second->position_in_parent_timeline_ = timeline_end();
--*child_it->second->position_in_parent_timeline_;
}

template<typename Tr4jectory, typename It3rator, typename Traits>
void Forkable<Tr4jectory, It3rator, Traits>::AttachForkToCopiedBegin(
not_null<std::unique_ptr<Tr4jectory>> fork) {
Loading