Add support for predicates from Allen's Interval Algebra for TimeRange

Closes #659
Operators implemented:

before
meets
begins
finishes

@jminor @ssteinbach @reinecke @meshula please take a look.

Codecov Report

Merging #697 into master will decrease coverage by 0.38%.
The diff coverage is 33.33%.

@@            Coverage Diff             @@
##           master     #697      +/-   ##
==========================================
- Coverage   81.72%   81.33%   -0.39%
==========================================
  Files          72       72
  Lines        2731     2749      +18
==========================================
+ Hits         2232     2236       +4
- Misses        499      513      +14

Flag
Coverage Δ

#py27
81.33% <33.33%> (-0.37%)
:arrow_down:

#py36
?

#py37
?

Impacted Files
Coverage Δ

src/opentime/timeRange.h
72.00% <0.00%> (-28.00%)
:arrow_down:

...imelineio/opentime-bindings/opentime_timeRange.cpp
100.00% <100.00%> (ø)

...ntimelineio/opentimelineio-bindings/otio_utils.cpp
87.05% <0.00%> (-0.16%)
:arrow_down:

...elineio/opentimelineio-bindings/otio_anyVector.cpp
100.00% <0.00%> (ø)

...eio/opentimelineio-bindings/otio_anyDictionary.cpp
100.00% <0.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 234b3f3...72e614c. Read the comment docs.

Hi Karthik! On this project, let's proceed in this manner:

Make a markdown document laying out Allen's Interval algebra, and extend it to describe how it behaves in light of TimeRanges that are (ex, ex) (in, ex) (ex, in), and (in, in).

For example, "before":
+--------+-- ex/ex ----------+--in/ex-----------+--ex/in-----------+--in/in--------------------+
| before |  a.end <= b.start | a.end <= b.start | a.end <= b.start | a.end + epsilon < b.start |

In this case, a.end <= b.start is almost always okay, except for when a.end and b.start are inclusive, in which case an epsilon check is necessary.

Let's use Test Driven Development to proceed. Once the table is complete, a test for each comparator, and the four clusivity combinations, should be filled out. It would be good to test each combination for a) positive check, false check, and corner cases, such as start equals end on both sides of the comparison. As this set of checks could be combinatorically large, it would perhaps be expedient to be able to generate the tests procedurally.

once the test suite exists, fill in the functions one by one

@meshula do you mean to have 4 implementations of each function, or just implement the comparisons in the test? What is our motive for creating this table?

There's this java library that implements some part of interval algebra. They ask if the user needs an openStart or an openEnd in the constructor. Could we consider such an approach and have some good defaults? This library uses closed intervals as a default and uses the same time values for comparison.
Link to relevant part of code here.

Thanks for your questions, I should have read the code more closely in constructing my comments, instead of relying on my notions of what was actually there :)
I like the way you are thinking about this problem and driving the task forward, thank you for being proactive!
You're right about the clusivity. I had was thinking too far ahead to a revised version of the API where clusivity is explicitly represented on the object. Right now, the time range class doesn't specifiy the clusivity, and you can make inclusive and exclusive queries on it. I think this change, which you've also found implemented in that java library, is an important part of a revised version of this API.
The table is only necessary if clusivity is specified on the object, as it provides both information to the user about how to use the library, and to the implementor, for a ground truth reference. Since clusivity is not yet explicitly implemented, there's no need yet to create this table.
For the purposes of this PR, it is probably preferable to implement the remaining algebraic operators in the same manner as the existing ones. If we make the larger change, we will need to inspect all of the upstream code, such as file format adaptors, for regressions. So let's hold off on that in favor of getting the much simpler job done.
Sadly, there is no documentation in the RationalTime.h header. Could you incorporate the following notes as comments into the header in the appropriate places?
Please double check that the existing implementations of overlaps and contains match this description.

These relations implement James F. Allen's thirteen basic time interval relations.
Detailed background can be found here: https://www.ics.uci.edu/~alspaugh/cls/shr/allen.html

In the relations that follow, epsilon indicates the tolerance,
in the sense that if abs(a-b) < epsilon, we consider a and b to be equal.

equals(a, b, epsilon)
The start of a strictly equals the start of b. The end of b strictly equals the end of b.

precedes(a, b, epsilon)
The end of a strictly precedes the start of b by a value >= epsilon
The converse is precedes(b, a, epsilon)

meets(a, b, epsilon)
The end of a strictly precedes the start of b by a value <= to epsilon
The converse is meets(b, a, epsilon)

overlaps(a, b, epsilon)
The end of a strictly precedes the end of b, the start a of strictly precedes the start of b
The converse is overlaps(b, a, epsilon)

starts(a, b, epsilon)
The start of a equals the start of b. The end of a strictly precedes the end of b
The converse is starts(b, a, epsilon)

finishes(a, b, epsilon)
The start of a strictly antecedes the start of ab. The end of a equals the end of b
The converse is finishes(b, a, epsilon)

contains(a, b, epsilon)
The start of a strictly precedes the start of b. The end of a strictly antecdes the end of b.
The converse is contains(b, a, epsilon)

A further "negative" aspect of our TimeRange object, which is highlighted by the your observations on the java library, is that our TimeRange allows construction with a negative duration. However, the logic internally is written as if duration is positive. For the purposes of this PR, let's ignore that a negative duration is possible, and write the code as if a negative duration had been disallowed. Please add a comment such as
It is possible to construct TimeRange object with a negative duration. However, the logical predicates are written as if duration is positive, and have undefined behavior for negative durations.

Finally, please remember that the unit tests need to exist for these operators. There are tests in place for contains and overlaps for reference.

@meshula I'll add the comments and change whatever needs to be changed assuming that only positive durations exist.
You have the epsilon parameter in the comments but that isn't implemented currently. Should I add the epsilon to RationalTime? If so, should we go ahead with a margin of half a frame?

If we say a meets b should that mean b meets a? In a way doesn't it? So should we return true for both cases.
I say this because that is what happens in overlaps

I think I can restate your question about epsilon as: "Should epsilon be a value stored on TimeRange, or should it be a parameter on the predicate functions, including the already written ones?"
My answer would be that currently, epsilon is not a quality of the TimeRange, but a quality of the question you are asking of it. I would prefer that we add epsilon as a parameter on the functions. A margin of half a frame as a default is unfortunately poorly defined. For the moment, a default epsilon of 1/1001 would allow us to capture tolerances that are compatible with NTSC frame rates which are multiples of that factor. It is also a number slightly less than one millisecond. We can leave the discussion of a better default for further discussion. For the moment, perhaps specify it as a constexpr, and we can revise it later.
If the end a abuts the start of b:
a meets b if the end of a is within epsilon of b but (a + epsilon) is not greater than or equal to b
meets by definition is this relation:
[   a   ][   b  ]

The converse relation, is "a is met by b"
[  b  ][  a  ]

so they are distinct.
Overlaps means
   [    a     ]
        [    b    ]

Thus -
overlaps(a, b, epsilon)
The end of a strictly precedes the end of b, the start a of strictly precedes the start of b
The converse is overlaps(b, a, epsilon)

The existing implementations of overlaps and contains are not as strict as the Allen Interval Algebra, unfortunately, which means that they don't function correctly in composed expressions of overlapping and containment.
As part of this task, we'll need to rewrite the existing overlaps and contains to conform to the algebra.
trackAlgorithm.cpp, track_widgets.py, and track_algo.py have one or two uses of contains() and overlaps() that should be spot checked to see if they need to be modified to conform to the revised specification. A quick glance suggests the algorithms might be fine as is, but it would be good to double check.

I understand. I'll make the changes by tomorrow morning. Meanwhile could you please take a look at the comment formatting and see if it's fine?

NTSC 23.976 is defined as 24000/1001, NTSC 29.97 is 30000/1001 and so on. That's why I'm proposing 1/1001 since it has fine enough resolution to capture those rather strange rates.
I have a question about the comment style you've implemented, I'm not familiar with it. Is that a format compatible with an automated documentation system such as doxygen?

I haven't used doxygen before, so I am not aware of its comment style. I used this comment style because I thought it would be easier to read. Does OTIO have a specific comment style, something compatible with doxygen?

So far OTIO has a lack of header based documentation. As a future effort such a documentation effort should be undertaken, but for the moment, there's no precedent. What you've done is fine, I was just curious about the styling; the part I hadn't seen commonly was having two leading asterisks on each line. I'm not suggesting anything needs to change, I was just curious about the style choice.

BTW, I will give the implementation a closer read after your changes of tomorrow morning. It's looking promising so far!

For some reason I'm unable to specify the epsilon as a RationalTime. The build is successful but when I import otio in python, it gives me an error:
ImportError: /home/karthik/venv3/lib/python3.6/site-packages/opentimelineio/_opentime.cpython-36m-x86_64-linux-gnu.so: undefined symbol: _ZN8opentime4v1_09TimeRange14defaultEpsilonE

So I'm using a double epsilon and writing the comparisons like start.value/start.rate - end.value/end.rate >= epsilon.
Also, using your definition of overlaps the tests fail.
[    a     ]
        [    b    ]

According to line 888 in test_opentime.py ,  b.overlaps(a) is true. So I'm keeping the rules same for the moment.

I've not used epsilon in contains. There is a specfic test that check if a timeRange is contained in itself and it expects true. In case I change that some additional opentimelineio tests fail.

Hmm...the tests pass on my local machine but not on travis. Why is that?

For before:
if
a = TimeRange(start = 10, dur = 2)
b = TimeRange(start = 12, dur = 3)

shouldn't a.before(b) be true? I know we're using epsilon for rounding errors but in case there's a case like this without a rounding error this will turn out to be false.

Yes, epsilon should be a double, not a RationalTime.
As I mentioned earlier, the existing versions of overlaps and contains do not match the definitions in the interval algebra, it's expected that they would fail. Let's open a second issue to correct their operation, and not solve it on this PR. https://github.com/PixarAnimationStudios/OpenTimelineIO/issues/700
a = TimeRange(start = 10, dur = 2)
b = TimeRange(start = 12, dur = 3)

For the purposes of this PR, let's decide that dur implies an exclusive end, so we can treat the intervals as "inclusive start, exclusive end" for all of the predicates. Under that definition a is indeed before b, so in the case of the "meets" predicate, meets(a, b, eps) is true.
Let's also add a line of documentation at the top of the class:
The duration on a TimeRange indicates a time range that is inclusive of the start time, and
exclusive of the end time. All of the predicates are computed accordingly.

I was looking at the clusivity functions in timeRange. In end_time_inclusive we're taking the floor or excluding the last frame. Shouldn't that be the case in end_time_exclusive?

This is something I wanted to ask. I might be wrong but I think the exclusive and inclusive parts are interchanged right now.
RationalTime end_time_inclusive() const {
                RationalTime et = end_time_exclusive();

                if ((et - _start_time.rescaled_to(_duration))._value > 1) {
                    return _duration._value != floor(_duration._value) ? et._floor() :
                           et - RationalTime(1, _duration._rate);
                } else {
                    return _start_time;
                }
            }

RationalTime end_time_exclusive() const {
            return _duration + _start_time.rescaled_to(_duration);
}

So if we want the a.before(b) thing to be true, the last frame should be excluded.
@meshula could you please take a closer look at my changes and point out if I'm wrong anywhere?

You are right ~ they are swapped!

We should swap them, and grep the codebase for usages. Since the unit tests pass currently, it is probably safe to say that all the existing usages need to be swapped.

:+1:  I'll do this first.

@ssteinbach Tells me that we are reading the API backwards with regards to how the inclusive and exclusive methods are to be read. There is clear documentation in the original python implementation, and we should (1) copy that documentation into the .h file, and (2) we therefore don't have to modify the code. I'll close out the other issue. @ssteinbach could you drop the link here in this thread?

I put the link to the python documentation of the methods from opentime in an issue that proposes bringing that documentation forward to the new C++ api:
https://github.com/PixarAnimationStudios/OpenTimelineIO/issues/704
To make simple, here is the links to the original implementation w/ docstrings:
https://github.com/PixarAnimationStudios/OpenTimelineIO/blob/last_pure_python/opentimelineio/opentime.py
Sorry about the confusion!

Oh I see. So the way I've implemented the operators should be alright? I'll make the changes suggested.
Although this is documented in the pure python version, I thought it was swapped when going through the code without the doc. The current choice seems a little unintuitive. Is there a reason for the choice?

Naming things is always difficult.  In the original implementation of TimeRange it had a single .end_time() method, which would compute the exclusive end point of the time range (or the first coordinate that was outside of the range).  We found this confused people - even in our own code base the end_time() method was treated as inclusive and sometimes it was treated as exclusive, and there were use cases for both interpretations.
We split the method up into end_time_inclusive(), representing the start of the last region of time of size rate inside the TimeRange, and end_time_exclusive(), representing the first time that is outside the TimeRange.  The benefit being that the clusivity of the point was explicit in the method call.  We tried to document this in the docstrings, but those weren't brought over when the codebase was rebuilt in C++ w/ Python bindings (@meshula added an issue for this).
This split was done in this PR: https://github.com/PixarAnimationStudios/OpenTimelineIO/pull/79
How were you interpreting those names?  Is there a better name you would propose?

I thought end_time_exclusive was end_time_inclusive and vice versa. I compared them to exclusive & inclusive class intervals.
https://www.quora.com/What-is-the-difference-between-exclusive-and-inclusive-class-interval
I think it would be easier if the implementations are swapped, but maybe they shouldn't be changed as people must have gotten used to this definition and it must be used at multiple places already.

To elaborate on what @ssteinbach said about our thought process in naming those methods: We were thinking of the end time as included inside the clip, or the end time outside the clip.
For example, if you have a clip that runs from frame 10-90, then you often want the end time to be 90 (e.g. the last frame) and other times to be 91, the frame where the next clip should start.
To see this visually, consider Figure 1 here: https://opentimelineio.readthedocs.io/en/stable/tutorials/otio-timeline-structure.html  Clip-001's source_range covers frames 3, 4, and 5 of Media-001. end_time_inclusive() returns 5, which is included in the clip, while end_time_exclusive() returns 6 which is outside the clip.
By introducing the two methods end_time_inclusive() and end_time_exclusive() we hoped to eliminate the various +1 or -1 calculations that we saw in many frame-based code paths. For example, folks using EDLs or image sequences do this all the time. You'll notice that the implementation of end_time_inclusive() uses et - RationalTime(1, _duration._rate) to go back "one frame" based on the rate.
Now that we're in the mindset of interval algebra, the intuitive sense of "inclusive" and "exclusive" are swapped. The specific concept is similar, but I would expect that the interval algebra's meaning of these two terms concerns the infinitesimal endpoint, not a whole frame at the end.
We could consider renaming these methods using different words (inside, outside?) if we can make the meaning clear. This is also an area where mixing continuous time with discrete frame-based time is causing confusion.

maybe .... end_time_inclusive() could be range_end_boundary(), and end_time_exclusive() could be range_end_final_frame(double rate)   ?

end_time_exclusive is not the "final frame" of the range, its the start of the first "frame" (really the first continuous time coordinate) that is outside of the range, and TimeRange itself has some utility beyond "Frames".  I think we should hold off on renaming it, if we rename it at all, until finishing up the discrete/continuous math design that we're working on.  We can fold this into that.

Agreed on deferring the discussion. To be clear, I'm not proposing equivalence between the inclusive/exclusive methods and my proposed names. I'm proposing that the inclusive/exclusive naming is sufficiently vague that perhaps the way forward is to make new functions that are explicit in what they return, whether or not that happens to be an inclusive/exclusive value.

Would it be alright to add the clang-format file and reformat in this PR or would a separate PR be better?

It's a good practice to keep PR's functionally distinct. So the way I think of it is that the formatting file is unrelated to the notion of a TimeRange, therefore it should be a separate PR.
Why don't we continue the discussion of the clang-format in the clang-format issue? https://github.com/PixarAnimationStudios/OpenTimelineIO/issues/706 If you have one you want to propose, could you post it there? We could all grab it and experiment a little.

@ssteinbach When you have a moment, could you check the resolution of your requested changes? I think we are close to being able to land this PR!

Codecov Report

Merging #697 into master will increase coverage by 0.15%.
The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #697      +/-   ##
==========================================
+ Coverage   81.72%   81.88%   +0.15%
==========================================
  Files          72       72
  Lines        2731     2755      +24
==========================================
+ Hits         2232     2256      +24
  Misses        499      499

Flag
Coverage Δ

#py27
81.86% <100.00%> (+0.15%)
:arrow_up:

#py36
81.86% <100.00%> (+0.15%)
:arrow_up:

#py37
?

Impacted Files
Coverage Δ

src/opentime/timeRange.h
100.00% <100.00%> (ø)

...imelineio/opentime-bindings/opentime_timeRange.cpp
100.00% <100.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update e7a52a4...2d88c61. Read the comment docs.

@ssteinbach
Changes made:

Add title and link for Interval Algebra paper
Change pythonic reference self to this
Remove dead code
Change defaultEpsilon_s to DEFAULT_EPSILON_s and change it's scope to namespace
Document DEFAULT_EPSILON_s
Use doxygen style comments

Now, only the & formatting revert is left. That is included in a commit with other non formatting changes. Is it possible to revert that using git?

Exciting to see this land! Thanks Karthik!

Currently going through otio-core, working on c-bindings. Will come back to this later!

@ssteinbach It looks like you merged this work in https://github.com/PixarAnimationStudios/OpenTimelineIO/commit/c61d309c9b00cedd13ed256db8e9c2b659128bca however, this PR is still open. Are there new commits, and that's why it's open, or do we need to manually close the PR?


added note about UpperCamelCase for ES6 classes

proposed note in issue #17864

[x] I have read freeCodeCamp's contribution guidelines.
[x] My pull request has a descriptive title (not a vague title like Update index.md)
[x] My pull request targets the master branch of freeCodeCamp.
[x] None of my changes are plagiarized from another source without proper attribution.
[x] My article does not contain shortened URLs or affiliate links.

If your pull request closes a GitHub issue, replace the XXXXX below with the issue number.
Closes #17864

useful edit

Hi @bannon-tanner,
Can you add note like a new heading? Example:
Note
UpperCamelCase should be used by convention for ES6 class names, as in SpaceShuttle used above.

you got it, sorry about that. Let me know if it shows up correctly on your end

I accidentally clicked on approved, I added a suggestion. Please add that as well.
Thanks!

Done. Forgot about that one

Thank you @bannon-tanner for your contribution!


Clarify continuous sync

DMS is for one time migration and cut over to SQL server running in Azure, if I understand correctly.
Can you please explain continuous sync? Does it service fit in the ongoing replication from source to target?
[Enter feedback here]

Document Details
⚠ Do not edit this section. It is required for docs.microsoft.com ➟ GitHub issue linking.

ID: 8c8dc618-bff7-b1aa-be2c-b6b933f75545
Version Independent ID: 9a608dd8-d781-eb4a-c796-34f758f0d58a
Content: Database migration scenario status - Azure Database Migration Service
Content Source: articles/dms/resource-scenario-status.md
Service: dms
GitHub Login: @pochiraju
Microsoft Alias: rajpo

@RonnieQuan Thanks for the feedback! We are currently investigating and will update you shortly.

@RonnieQuan For continuous synchronization, please look at Azure Data Sync
The documentation has all the details.

DMS provides ongoing sync for various source and target pairs to minimize the migration downtime to near zero, and this capability should be used only for pure migration purposes to Azure Data.  DMS can't be used for ongoing sync purposes.   If you can provide more details around continuous sync needs, we can be able to point you to the right solution.

@RonnieQuan I hope your query has been addressed.
We will proceed to close this issue now.
If there are further questions regarding this matter, please comment and we will gladly continue the discussion.
You could also post future issues on our new community forum Microsoft Q&A for better visibility


Need to set 'min-height: 0' for blank columns.

Before opening:

Search for duplicate or closed issues
Validate and lint any HTML to avoid common problems
Read the contributing guidelines

Bug reports must include:

Operating system and version (Windows, macOS, Android, iOS, Win10 Mobile): Windows
Browser and version (Chrome, Firefox, Safari, IE, MS Edge, Opera 15+, Android Browser): Chrome 67+
Reduced test case

Just to elaborate on this, it's currently set to 1px to prevent collapsing:
https://github.com/twbs/bootstrap/blob/a194abbb5aaa999f5c0eba4bba4f7aff6ab2d0ad/scss/mixins/_grid-framework.scss#L8-L14
Maybe someone can explain why this is done exactly and why columns may not collapse when empty?


Run getMore integration test in one connection pool

Description
Closes #1807.

This PR fixes tests but does not address all points raised in the issue. Here are the things not addressed.

create one client that uses MongoDB URI query parameters to fix connection pool size to 1, ensuring that all commands run with this client use the same connection;

Do we want to test this only for FerretDB? As far as I know, MongoDB does not provide information related to uniquely identifying a connection for commands. They have session for that, but multiple sessions would be created for a single client.

create a separate client like the first one, ensuring that different clients use different connections.

Also this can be implemented for FerretDB, but I didn't find equivalent check for MongoDB.
If we want to ensure FerretDB does use the same connection, I think PostgreSQL such as pg_backend_pid() can be used. However, initially the tests were failing for MongoDB only so I want to ensure what we want to achieve from this issue :hugs:
Readiness checklist

[ ] I added/updated unit tests.
[x] I added/updated integration/compatibility tests.
[ ] I added/updated comments and checked rendering.
[x] I made spot refactorings.
[ ] I updated user documentation.
[ ] I ran task all, and it passed.
[x] I ensured that PR title is good enough for the changelog.
[x] (for maintainers only) I set Reviewers (@FerretDB/core), Labels, Project and project's Sprint fields.
[ ] I marked all done items in this checklist.

Do we want to test this only for FerretDB?

First of all, we want to understand how MongoDB works. We can't do that if we don't run tests for it.

As far as I know, MongoDB does not provide information related to uniquely identifying a connection for commands.

That's why we fix *mongo.Client's pool size to 1 – it is easy to uniquely identify a connection if there is only one of them.

create a separate client like the first one, ensuring that different clients use different connections.

Also this can be implemented for FerretDB, but I didn't find equivalent check for MongoDB.

Not sure I understand why we can't create a separate *mongo.Client instance for MongoDB. See TestCommandsDiagnosticWhatsMyURI for example.

If we want to ensure FerretDB does use the same connection,

It will use the same connection if there is only one. And if there is only one, if we configure *mongo.Client to use the only one.


[Renderer] portal is not working

void __cdecl ClientPortalManager::DrawPortalSurface(int this, ClientPortal *portal, int surface, GLuint portal_texture_id)
hook this and do portal rendering + gamma correction with shader.

clipplane should be appliied in shader

localplayer should be visible within mirror in firstperson mode


:seedling: Assert the status of ACM ready with CRD

Summary
Related issue(s)
Fixes #
Tests

[ ] Unit/function tests have been added and incorporated into make unit-tests.
[ ] Integration tests have been added and incorporated into make integration-test.
[ ] E2E tests have been added and incorporated into make e2e-test-all.
[ ] List other manual tests you have done.

/retest

/retest

/cc @clyang82 @ldpliu

/lgtm