[ppwcode commit] r3256 - in java/value/trunk/src/main/java/org/ppwcode/value_III/time: . interval
codesite...@google.com
Date: Thu Oct 23 06:51:23 2008
New Revision: 3256
Modified:
java/value/trunk/src/main/java/org/ppwcode/value_III/time/Duration.java
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/AllenRelation.java
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/BeginEndTimeInterval.java
Log:
AllenRelation done? It compiles at least, and there are loads of
documentation.
Modified:
java/value/trunk/src/main/java/org/ppwcode/value_III/time/Duration.java
==============================================================================
--- java/value/trunk/src/main/java/org/ppwcode/value_III/time/Duration.java
(original)
+++ java/value/trunk/src/main/java/org/ppwcode/value_III/time/Duration.java
Thu Oct 23 06:51:23 2008
@@ -36,7 +36,7 @@
* (right half-open interval).
*
* The {@link #compareTo(Object) compare method} compares the
- * {@link #getStartDate()}.
+ * {@link #getBegin()}.
*
* @author nsmeets
* @author Peopleware NV
Modified:
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/AllenRelation.java
==============================================================================
---
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/AllenRelation.java
(original)
+++
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/AllenRelation.java
Thu Oct 23 06:51:23 2008
@@ -16,14 +16,12 @@
package org.ppwcode.value_III.time.interval;
+
import static
org.ppwcode.vernacular.exception_II.ProgrammingErrorHelpers.pre;
import static
org.ppwcode.vernacular.exception_II.ProgrammingErrorHelpers.preArgumentNotNull;
-import java.util.ArrayList;
import java.util.Date;
-import java.util.List;
-import org.ppwcode.vernacular.exception_II.ProgrammingErrorHelpers;
import org.toryt.annotations_I.Basic;
import org.toryt.annotations_I.Expression;
import org.toryt.annotations_I.Invars;
@@ -31,13 +29,238 @@
/**
- * The {@link Object#equals(Object)} is not overridden, because we want to
use this
- * type with reference equality. {@link #hashCode()} is overridden
nevertheless,
- * to guarantee a better spread (it also happens to give a peek inside the
encapsulation,
- * for people who know the implementation details).
+ * <p>Support for reasoning about relations between time intervals and
constraints on time intervals.
+ * <strong>We highly advise to use this class when working with
relations between time intervals.
+ * Reasoning about relations between time intervals is treacherously
difficult.</p>
+ * <p>When working with time intervals, we often want to express
constraints (invariants) that limit
+ * acceptable intervals. Expressing this correctly proves extremely
difficult in practice. Falling
+ * back to working with isolated begin and end dates, and reasoning
about their relations, in
+ * practice proves to be even much more difficult and error prone.</p>
+ * <p>This problem was tackled in 1983 by James Allen
+ * (<a
href="http://www.cs.brandeis.edu/~cs101a/readings/allen-1983.pdf"><cite>Allen,
James F. "Maintaining knowledge
+ * about temporal intervals"; Communications of the ACM 26(11)
pages 832-843; November 1983</cite></a>).
+ * A good synopsis of this theory is
+ * <a
href="http://www.isr.uci.edu/~alspaugh/foundations/allen.html"><cite>Thomas
A. Alspaugh "Allen's interval
+ * algebra"</cite></a>. This class implements this theory, and in
this text we give some guidelines
+ * on how to use this class.</p>
+ *
+ * <h3>Quick overview</h3>
+ * <p>Allen found that there are 13 <em>basic relations</em> possible
between 2 definite time intervals:</p>
+ * <ul>
+ * <li><code><var>I1</var> {@link #PRECEDES} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #MEETS} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #OVERLAPS} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #FINISHED_BY}
<var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #CONTAINS} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #STARTS} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #EQUALS} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #STARTED_BY} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #DURING} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #FINISHES} <var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #OVERLAPPED_BY}
<var>I2</var></code>,</li>
+ * <li><code><var>I1</var> {@link #MET_BY} <var>I2</var></code>, or</li>
+ * <li><code><var>I1</var> {@link #PRECEDED_BY}
<var>I2</var></code>.</li>
+ * </ul>
+ * <p>These basic relations can be compared to <code><</code>,
<code>==</code> and <code>></code>
+ * with time instances.</p>
+ * <p>When reasoning about the relationship between time intervals
however, like when comparing time instances,
+ * we also often employ indeterminate relations, such as
+ * <code><var>I1</var> ({@link #PRECEDES} || {@link #MEETS})
<var>I2</var></code>. This is comparable to
+ * reasoning with <code>≤</code>, <code>≥</code> and
<code>!=</code> with time instances.
+ * For time intervals, given 13 basic relations, we get 8192 (==
2<super>13</super>) possible <em>general
+ * relations</em>. This includes the {@link #EMPTY empty relationship}
for algebraic reasons, and the
+ * {@link #FULL full relationship} (comparable to <code>< || == ||
></code> with time instances)},
+ * which expresses the maximal uncertainty about the relation between 2
time intervals.</p>
+ *
+ * <h3>Interval constraints</h3>
+ * <p>Allen relations will most often be used in business code to
constrain relations between time intervals.
+ * This is notoriously, treacherously difficult. It is for this reason
that you should use code like this,
+ * that at least forces you to think things trough, and tries to offers
tools to ease reasoning. The idiom
+ * todo this is explained next.</p>
+ * <p>First we need to determine the relation we want to uphold
(<code><var>cond</var></code>). E.g., we want
+ * to assert that 2 given intervals <code><var>I1</var></code> and
<code><var>I2</var></code> do not concur.
+ * The relationship that expresses this is <code><var>cond</var> ==
{@link #CONCURS_WITH}.complement()</code>.</p>
+ * <p>Next, we want to determine the relationship from
<code><var>I1</var></code> to <code><var>I2</var></code>
+ * as precisely as possible. If both <code><var>I1</var></code> and
<code><var>I2</var></code> are completely
+ * determined, i.e., neither their begin date nor their end date is
{@code null}, the result will be a
+ * {@link #BASIC_RELATIONS basic relation}. Otherwise, the result will be
a less certain relation. To determine
+ * this relationship, use {@link #allenRelation(TimeInterval,
TimeInterval)}. See below for dealing
+ * with constrained begin and end dates.</p>
+ * <p>The idiom for the assertion we want to express is then:</p>
+ * <pre>
+ * allenRelation(<var>I1</var>, <var>I2</var>).implies(<var>cond</var>)
+ * </pre>
+ * <p>This is often the form of an invariant. Note that this can fail, on
the one hand because the actual
+ * relation is not acceptable, but also because <em>we cannot be 100%
sure that the actual relationship
+ * satisfies the condition. In our example, we would have:</p>
+ * <pre>
+ * allenRelation(<var>I1</var>,
<var>I2</var>).implies(CONCURS_WITH.complement())
+ * </pre>
+ * <p>{@link #CONCURS_WITH} being {@code (oFDseSdfO)},
<code>CONCURS_WITH.complement() == (pmMP)</code>.
+ * If the actual relation results in {@code (e)}, e.g., the constraint is
clearly not satisfied. If
+ * the actual relation results in {@code OMP} for example, it means that
it is possible that the relation
+ * is satisfied, but there is also a chance that it is not (if
<code><var>I1</var></code> begins before
+ * <code><var>I2</var></code> ends).</p>
+ * <p>In code then, we often want to throw an exception to interrupt an
algorithm that would violate the
+ * invariant. The idiom for this is usually of the form:</p>
+ * <pre>
+ * ...
+ * TimeInterval i1 = ...;
+ * TimeInterval i2 = ...;
+ * AllenRelation condition = ...;
+ * AllenRelation actual = allenRelation(i1, i2);
+ * if (! actual.implies(condition)) {
+ * throw new ....
+ * }
+ * ...
+ * </pre>
+ * <p>In our example, this would become</p>
+ * <pre>
+ * ...
+ * TimeInterval i1 = ...;
+ * TimeInterval i2 = ...;
+ * if (! allenRelation(i1, i2).implies(CONCURS_WITH.complement())) {
+ * throw new ....
+ * }
+ * ...
+ * </pre>
+ * <p><strong>Note that in general {@code (! actual.implies(condition))}
is <em>not equivalent</em> with
+ * {@code actual.implies(condition.complement())} (see {@link
#complement()}).</strong> In our example
+ * this is already clear. If the actual relation results in {@code (e)},
+ * {@code ! allenRelation(i1, i2).implies(CONCURS_WITH.complement())}
evaluates to</p>
+ * <pre>
+ * ! allenRelation(i1, i2).implies(CONCURS_WITH.complement())
+ * == ! (e).implies((pmMP))
+ * == ! false
+ * == true
+ * </pre>
+ * <p>and {@code allenRelation(i1, i2).implies(CONCURS_WITH)} evaluates
to</p>
+ * <pre>
+ * allenRelation(i1, i2).implies(CONCURS_WITH)
+ * == (e).implies((oFDseSdfO))
+ * == true
+ * </pre>
+ * <p>But in the case where the actual relation results in {@code OMP}
+ * {@code ! allenRelation(i1, i2).implies(CONCURS_WITH.complement())}
evaluates to</p>
+ * <pre>
+ * ! allenRelation(i1, i2).implies(CONCURS_WITH.complement())
+ * == ! (OMP).implies((pmMP))
+ * == ! false
+ * == true
+ * </pre>
+ * <p>and {@code allenRelation(i1, i2).implies(CONCURS_WITH)} evaluates
to</p>
+ * <pre>
+ * allenRelation(i1, i2).implies(CONCURS_WITH)
+ * == (OMP).implies((oFDseSdfO))
+ * == <strong>false</strong>
+ * </pre>
+ * <p>{@code ! allenRelation(i1, i2).implies(CONCURS_WITH.complement())}
expresses that [we want to throw an
+ * exception if] <em>it is not guaranteed that
<code><var>i1</var></code> and <code><var>i2</var></code> do
+ * not concur</em>. {@code allenRelation(i1, i2).implies(CONCURS_WITH)}
expresses that [we want to throw an
+ * exception if] <em>it is guaranteed that <code><var>i1</var></code>
and <code><var>i2</var></code> do
+ * concur</em>. <strong>These 2 phrases are not equivalent.</strong></p>
+ *
+ * <h3>Reasoning with unknown but constrained begin and end dates</h3>
+ * <p>In time intervals, the begin or end end can be {@code null}. The
semantics of this is in general that
+ * the begin date, respectively the end date, is unknown. Comparing such
an interval with another interval
+ * results in a relatively broad Allen relation, expression an amount of
uncertainty.</p>
+ * <p>In several use cases however, we do no know a definite begin or end
date, but we do know that the
+ * begin or end date have constraints. E.g., consider contracts that have
a definite begin date, but are
+ * open ended. The contract interval thus is incompletely known. However,
since at the moment of our reasoning
+ * no definite end date is set, we know that the end date is at least
later than {@code now}. In comparing
+ * this contract interval with another interval, this constraint can be
of use to limit the extend, i.e., the
+ * uncertainty, of the Allen relation. The same applies, e.g., with
contracts that will start once payment is
+ * received. Since it is not received yet at the moment of our
evaluation, we know that the begin date is at
+ * least later than or equal to {@code now}.</p>
+ * <p>In such cases, the interval object <code><var>I</var></code> we are
focusing on can be interpreted in
+ * another way. Suppose we are comparing <code><var>I</var></code> with
<code><var>Other</var></code>. We are
+ * actually not interested in <code>allenRelation(<var>I</var>,
<var>Other</var>)</code>, but rather in
+ * <code>allenRelation(<var>I<sub>constrained</sub></var>,
<var>Other</var>)</code>. Sadly, there is no easy
+ * syntax (or code) to express
<code><var>I<sub>constrained</sub></var></code>. What we can express is an
+ * <var>I<sub>determinate</sub></var>, where the border times are filled
out in place of the unknown begin
+ * date or end date.
<code>allenRelation(<var>I<sub>determinate</sub></var>,
<var>Other</var>)</code>
+ * can be calculated, and will be much less uncertain than
+ * <code>allenRelation(<var>I</var>, <var>Other</var>)</code>. If now can
determine the Allen relation from
+ * <code><var>I<sub>constrained</sub></var></code> to
<code><var>I<sub>determinate</sub></var></code>,
+ * we can find <code>allenRelation(<var>I<sub>constrained</sub></var>,
<var>Other</var>)</code> as:</p>
+ * <pre>
+ * allenRelation(<var>I<sub>constrained</sub></var>, <var>Other</var>) ==
+ * compose(allenRelation(<var>I<sub>constrained</sub></var>,
<var>I<sub>determinate</sub></var>),
allenRelation(<var>I<sub>determinate</sub></var>, <var>Other</var>))
+ * </pre>
+ * <p>The Allen relation from an interval we are focusing on with
constrained semantics to a determinate
+ * interval is a constant that can be determined by reasoning. E.g., for
our open ended contract, that lasts
+ * at least longer than today (<code>[I<sub>begin</sub>, >
now[</code>, supposing <code>I<sub>begin</sub> ≤
+ * yesterday</code>), we can say that its relation to the determinate
interval <code>[I<sub>begin</sub>, now[</code> is
+ * {@code (S)} ({@link #STARTED_BY}). Suppose
+ * <code>allenRelation(<var>I<sub>determinate</sub></var>,
<var>Other</var>) == (o)</code> (say
+ * <code><var>Other</var> == [<var>yesterday</var>, <var>next
year</var>[</code>), we can now say
+ * that <code>allenRelation(<var>I<sub>constrained</sub></var>,
<var>Other</var>) == (S).(o) == (oFD)</code>.
+ * The comparison of the indeterminate interval with
<code><var>Other</var></code>,
+ * <code>allenRelation(<var>I</var>, <var>Other</var>)</code>, would
have resulted in:</p>
+ * <pre>
+ * allenRelation(<var>I</var>, <var>Other</var>)
+ * == allenRelation([I<sub>begin</sub>, null[, [<var>yesterday</var>,
<var>next year</var>[)
+ * == (pmoFD)
+ * </pre>
+ * <p>If you reason directly about
<code>allenRelation(<var>I<sub>constrained</sub></var>,
<var>Other</var>)</code></p>
+ * <pre>
+ * allenRelation(<var>I<sub>constrained</sub></var>, <var>Other</var>)
+ * == allenRelation([I<sub>begin</sub>, > now[, [<var>yesterday</var>,
<var>next year</var>[)
+ * == (oFD)
+ * </pre>
+ * <p>you will see that {@code (oFD)} is indeed the most certain answer.
+ * <p>Be aware that in a number of cases, the non-determinate character of
<code><var>I</var></code> doesn't matter.
+ * If you suppose in the previous example that
+ * <code>allenRelation(<var>I<sub>determinate</sub></var>,
<var>Other</var>) == (p)</code> (say
+ * <code><var>Other</var> == [<var>next year</var>,
Other<sub>end</sub>[</code>),
+ * <code>allenRelation(<var>I<sub>constrained</sub></var>,
<var>Other</var>) == (S).(p) == (pmoFD)</code>.
+ * The comparison of the indeterminate interval with
<code><var>Other</var></code>,
+ * <code>allenRelation(<var>I</var>, <var>Other</var>)</code>, in this
case, results in the same Allen relation:</p>
+ * <pre>
+ * allenRelation(<var>I</var>, <var>Other</var>)
+ * == allenRelation([I<sub>begin</sub>, null[, [<var>next year</var>,
Other<sub>end</sub>[)
+ * == (pmoFD)
+ * </pre>
+ *
+ * <h3>Inference</h3>
+ * <p><strong>Be aware that, in general, inference over intervals, also
using Allen relations, is NP-complete.</strong>
+ * This means that the time the execution of algorithms will take, is at
least difficult to ascertain, and quickly
+ * completely impractical (i.e., with realistic parameters the algorithm
would take longer than the universe exists
+ * — no kidding).</p>
+ * <p>There are subsets of the Allen relations for which there exist
algorithms that perform much better. These issues
+ * are not implemented here at this time.</p>
+ *
+ * <h3>About the code</h3>
+ * <p>We have chosen to introduce a full-featured type for working with
Allen relations, to make encapsulation as
+ * good as possible. This has a slight performance overhead, but we
believe that this is worth it, considering the
+ * immense complexity of reasoning about relations between time
intervals.</p>
+ * <p>Allen relations are not implemented as a value according to the
ppwcode value vernacular, although they do form
+ * an algebra. We presume Allen relations are never shown to end users
as values.</p>
+ * <p>Allen relations follow the "8192-fold singleton pattern".
All possible instances are created when this
+ * class is loaded, and it is impossible for a user of the class to
create new instances. This means that reference
+ * equality ("{@code ==}") can be used to compare Allen
relations, Instances are to be obtained
+ * using the constants this class offers, or using the combination
methods {@link #or(AllenRelation...)},
+ * {@link #and(AllenRelation...)}, {@link #compose(AllenRelation,
AllenRelation)}, and
+ * {@link #min(AllenRelation, AllenRelation)}, and the unary methods
{@link #complement()} and {@link #converse()}.
+ * Also, an AllenRelation can be determined {@link
#allenRelation(TimeInterval, TimeInterval) based on 2 time intervals}.
+ * {@link #VALUES} lists all possible Allen relations.</p>
+ * <p>The {@link Object#equals(Object)} is not overridden, because we want
to use this type with reference equality.
+ * {@link #hashCode()} is overridden nevertheless, to guarantee a better
spread (it also happens to give a peek inside
+ * the encapsulation, for people who know the implementation
details).</p>
*/
public final class AllenRelation {
+ /*
+ * Implementation note:
+ *
+ * Allen relations are implemented as a 13-bit bit pattern, stored in
the 13 least significant bits of a 32-bit int.
+ * Each of those 13 bits represents a basic relation, being in the
general relation ({@code 1}) or not being in the
+ * general relation ({@code 0}).
+ * The order of the basic relations in the bit pattern is important for
some of the algorithms. There is some
+ * trickery involved.
+ */
+
+
/*<section name="population">*/
//------------------------------------------------------------------
@@ -93,7 +316,7 @@
* consistencey with some operations on Allen relations.
* The converse of the empty relation is the empty relation itself.
*/
- @Invars(@Expression("for (AllenRelation basic : BASIC_RELATIONS) {!
EMPTY.CONTAINS(basic)}"))
+ @Invars(@Expression("for (AllenRelation basic : BASIC_RELATIONS) {!
EMPTY.impliedBy(basic)}"))
public final static AllenRelation EMPTY = VALUES[EMPTY_BIT_PATTERN];
/**
@@ -104,6 +327,7 @@
* (I1.end != null) && (I2.begin != null) && (I1.end
< I2.begin)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-precedes.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>p</strong></code>".
* The converse of this relation is {@link #PRECEDED_BY}.
*/
public final static AllenRelation PRECEDES =
VALUES[PRECEDES_BIT_PATTERN];
@@ -116,6 +340,7 @@
* (I1.end != null) && (I2.begin != null) && (I1.end
== I2.begin)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-meets.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>m</strong></code>".
* The converse of this relation is {@link #MET_BY}.
*/
public final static AllenRelation MEETS = VALUES[MEETS_BIT_PATTERN];
@@ -131,6 +356,7 @@
* (I1.begin < I2.begin) && (I1.end > I2.begin)
&& (I1.end < I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-overlaps.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>o</strong></code>".
* The converse of this relation is {@link #OVERLAPPED_BY}.
*/
public final static AllenRelation OVERLAPS =
VALUES[OVERLAPS_BIT_PATTERN];
@@ -145,6 +371,7 @@
* (I1.begin < I2.begin) && (I1.end == I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-finishedBy.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>F</strong></code>".
* The converse of this relation is {@link #FINISHED_BY}.
*/
public final static AllenRelation FINISHED_BY =
VALUES[FINISHED_BY_BIT_PATTERN];
@@ -159,6 +386,7 @@
* (I1.begin < I2.begin) && (I1.end > I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-contains.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>D</strong></code>".
* The converse of this relation is {@link #DURING}.
*/
public final static AllenRelation CONTAINS =
VALUES[CONTAINS_BIT_PATTERN];
@@ -173,6 +401,7 @@
* (I1.begin == I2.begin) && (I1.end < I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-starts.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>s</strong></code>".
* The converse of this relation is {@link #STARTED_BY}.
*/
public final static AllenRelation STARTS = VALUES[STARTS_BIT_PATTERN];
@@ -187,6 +416,7 @@
* (I1.begin == I2.begin) && (I1.end == I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-equals.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>e</strong></code>".
* The converse of this relation is itself.
*/
public final static AllenRelation EQUALS = VALUES[EQUALS_BIT_PATTERN];
@@ -201,6 +431,7 @@
* (I1.begin == I2.begin) && (I1.end > I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-startedBy.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>S</strong></code>".
* The converse of this relation is {@link #STARTS}.
*/
public final static AllenRelation STARTED_BY =
VALUES[STARTED_BY_BIT_PATTERN];
@@ -215,6 +446,7 @@
* (I1.begin > I2.begin) && (I1.end < I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-during.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>d</strong></code>".
* The converse of this relation is {@link #CONTAINS}.
*/
public final static AllenRelation DURING = VALUES[DURING_BIT_PATTERN];
@@ -229,6 +461,7 @@
* (I1.begin > I2.begin) && (I1.end == I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-finishes.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>f</strong></code>".
* The converse of this relation is {@link #FINISHES}.
*/
public final static AllenRelation FINISHES =
VALUES[FINISHES_BIT_PATTERN];
@@ -244,6 +477,7 @@
* (I1.begin > I2.begin) && (I1.begin < I2.end)
&& (I1.end > I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-overlappedBy.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>O</strong></code>".
* The converse of this relation is {@link #OVERLAPS}.
*/
public final static AllenRelation OVERLAPPED_BY =
VALUES[OVERLAPPED_BY_BIT_PATTERN];
@@ -256,6 +490,7 @@
* (I1.begin != null) && (I2.end != null) && (I1.begin
== I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-metBy.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>M</strong></code>".
* The converse of this relation is {@link #MEETS}.
*/
public final static AllenRelation MET_BY = VALUES[MET_BY_BIT_PATTERN];
@@ -268,6 +503,7 @@
* (I1.begin != null) && (I2.end != null) && (I1.begin
> I2.end)
* </pre>
* <img style="text-align: center;"
src="doc-files/AllenRelation-precededBy.png">
+ * The conventional sort representation of this Allen relation is
"<code><strong>P</strong></code>".
* The converse of this relation is {@link #PRECEDES}.
*/
public final static AllenRelation PRECEDED_BY =
VALUES[PRECEDED_BY_BIT_PATTERN];
@@ -290,6 +526,7 @@
* <var>I2</var>.end</code>).
*/
@Invars({
+ @Expression("for (BasicRelation br : BASIC_RELATIONS)
{BASIC_RELATIONS[br.basicRelationOrdinal()] == br}"),
@Expression("BASIC_RELATIONS[ 0] == PRECEDES"),
@Expression("BASIC_RELATIONS[ 1] == MEETS"),
@Expression("BASIC_RELATIONS[ 2] == OVERLAPS"),
@@ -304,22 +541,11 @@
@Expression("BASIC_RELATIONS[11] == MET_BY"),
@Expression("BASIC_RELATIONS[12] == PRECEDED_BY")
})
- public final static List<AllenRelation> BASIC_RELATIONS = new
ArrayList<AllenRelation>(13);
- static {
- BASIC_RELATIONS.add(PRECEDES);
- BASIC_RELATIONS.add(MEETS);
- BASIC_RELATIONS.add(OVERLAPS);
- BASIC_RELATIONS.add(FINISHED_BY);
- BASIC_RELATIONS.add(CONTAINS);
- BASIC_RELATIONS.add(STARTS);
- BASIC_RELATIONS.add(EQUALS);
- BASIC_RELATIONS.add(STARTED_BY);
- BASIC_RELATIONS.add(DURING);
- BASIC_RELATIONS.add(FINISHES);
- BASIC_RELATIONS.add(OVERLAPPED_BY);
- BASIC_RELATIONS.add(MET_BY);
- BASIC_RELATIONS.add(PRECEDED_BY);
- }
+ public final static AllenRelation[] BASIC_RELATIONS = {PRECEDES, MEETS,
OVERLAPS, FINISHED_BY, CONTAINS, STARTS,
+ EQUALS,
+ STARTED_BY,
DURING, FINISHES, OVERLAPPED_BY, MET_BY, PRECEDED_BY};
+
+ private final static String[] BASIC_CODES =
{"p", "m", "o", "F", "D", "s", "e", "S", "d", "f", "O", "M", "P"};
/*</section>*/
@@ -480,19 +706,177 @@
/**
* The main factory method for AllenRelations. Although this is intended
to create
* any disjunction of the basic relations, you can use any relation in
the argument
- * list.
+ * list. This is the union of all Allen relations in {@code gr}, when
they are considered
+ * as sets of basic relations.
*/
@MethodContract(post = {
- @Expression("for (AllenRelation br : BASIC_RELATIONS) {exists
(AllenRelation ar : _gr) {ar.CONTAINS(br)} ?? result.CONTAINS(br)}")
+ @Expression("for (AllenRelation br : BASIC_RELATIONS) {exists
(AllenRelation ar : _gr) {ar.impliedBy(br)} ?? result.impliedBy(br)}")
})
public static AllenRelation or(AllenRelation... gr) {
- int acc = EMPTY.$bitPattern;
+ int acc = EMPTY_BIT_PATTERN;
for (AllenRelation allenRelation : gr) {
acc |= allenRelation.$bitPattern;
}
return VALUES[acc];
}
+ /**
+ * The conjunction of the Allen relations in {@code gr}.
+ * This is the intersection of all Allen relations in {@code gr}, when
they are considered
+ * as sets of basic relations.
+ */
+ @MethodContract(post = {
+ @Expression("for (AllenRelation br : BASIC_RELATIONS) {for
(AllenRelation ar : _gr) {ar.impliedBy(br)} ?? result.impliedBy(br)}")
+ })
+ public static AllenRelation and(AllenRelation... gr) {
+ int acc = FULL_BIT_PATTERN;
+ for (AllenRelation allenRelation : gr) {
+ acc &= allenRelation.$bitPattern;
+ }
+ return VALUES[acc];
+ }
+
+ /**
+ * Remove basic relations in {@code gr2} from {@code gr1}.
+ */
+ @MethodContract(
+ pre = {
+ @Expression("_base != null"),
+ @Expression("_term != null")
+ },
+ post = @Expression("for (AllenRelation br : BASIC_RELATIONS)
{br.implies(result) ?? br.implies(_base) && ! br.implies(_term)}")
+ )
+ public static AllenRelation min(AllenRelation base, AllenRelation term) {
+ assert preArgumentNotNull(base, "base");
+ assert preArgumentNotNull(term, "term");
+ int xor = base.$bitPattern ^ term.$bitPattern;
+ int min = base.$bitPattern & xor;
+ return VALUES[min];
+ }
+
+ /**
+ * This matrix holds the compositions of basic Allen relations. These
are part of the given semantics, and cannot be
+ * calculated. See {@link #compose(AllenRelation, AllenRelation)}.
+ */
+ public final static AllenRelation[][] BASIC_COMPOSITIONS =
+ {
+
{PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,ENDS_EARLIER,ENDS_EARLIER,ENDS_EARLIER,ENDS_EARLIER,FULL},
+
{PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,MEETS,MEETS,MEETS,ENDS_IN,ENDS_IN,ENDS_IN,END_TOGETHER,ENDS_LATER},
+
{PRECEDES,PRECEDES,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER,OVERLAPS,OVERLAPS,CONTAINS_BEGIN,ENDS_IN,ENDS_IN,CONCURS_WITH,CONTAINS_END,ENDS_LATER},
+
{PRECEDES,MEETS,OVERLAPS,FINISHED_BY,CONTAINS,OVERLAPS,FINISHED_BY,CONTAINS,ENDS_IN,END_TOGETHER,CONTAINS_END,CONTAINS_END,ENDS_LATER},
+
{BEGINS_EARLIER,CONTAINS_BEGIN,CONTAINS_BEGIN,CONTAINS,CONTAINS,CONTAINS_BEGIN,CONTAINS,CONTAINS,CONCURS_WITH,CONTAINS_END,CONTAINS_END,CONTAINS_END,ENDS_LATER},
+
{PRECEDES,PRECEDES,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER,STARTS,STARTS,BEGIN_TOGETHER,DURING,DURING,BEGINS_IN,MET_BY,PRECEDED_BY},
+
{PRECEDES,MEETS,OVERLAPS,FINISHED_BY,CONTAINS,STARTS,EQUALS,STARTED_BY,DURING,FINISHES,OVERLAPPED_BY,MET_BY,PRECEDED_BY},
+
{BEGINS_EARLIER,CONTAINS_BEGIN,CONTAINS_BEGIN,CONTAINS,CONTAINS,BEGIN_TOGETHER,STARTED_BY,STARTED_BY,BEGINS_IN,OVERLAPPED_BY,OVERLAPPED_BY,MET_BY,PRECEDED_BY},
+
{PRECEDES,PRECEDES,ENDS_EARLIER,ENDS_EARLIER,FULL,DURING,DURING,BEGINS_LATER,DURING,DURING,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY},
+
{PRECEDES,MEETS,ENDS_IN,END_TOGETHER,ENDS_LATER,DURING,FINISHES,BEGINS_LATER_AND_ENDS_LATER,DURING,FINISHES,BEGINS_LATER_AND_ENDS_LATER,PRECEDED_BY,PRECEDED_BY},
+
{BEGINS_EARLIER,CONTAINS_BEGIN,CONCURS_WITH,CONTAINS_END,ENDS_LATER,BEGINS_IN,OVERLAPPED_BY,BEGINS_LATER_AND_ENDS_LATER,BEGINS_IN,OVERLAPPED_BY,BEGINS_LATER_AND_ENDS_LATER,PRECEDED_BY,PRECEDED_BY},
+
{BEGINS_EARLIER,BEGIN_TOGETHER,BEGINS_IN,MET_BY,PRECEDED_BY,BEGINS_IN,MET_BY,PRECEDED_BY,BEGINS_IN,MET_BY,PRECEDED_BY,PRECEDED_BY,PRECEDED_BY},
+
{FULL,BEGINS_LATER,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY,PRECEDED_BY,PRECEDED_BY}
+ };
+
+ /**
+ * Given 3 time intervals <code><var>I1</var></code>,
<code><var>I2</var></code> and <code><var>I3</var></code>, given
+ * <code>gr1 == allenRelation(<var>I1</var>, <var>I2</var>)</code> and
<code>gr2 == allenRelation(<var>I2</var>, <var>I3</var>)</code>,
+ * <code>compose(gr1, gr2) == allenRelation(<var>I1</var>,
<var>I3</var>)</code>.
+ */
+ @MethodContract(
+ pre = {
+ @Expression("_gr1 != null"),
+ @Expression("_gr2 != null")
+ },
+ post = {
+ @Expression("for (AllenRelation br1 : BASIC_RELATIONS) {for
(AllenRelation br2: BASIC_RELATIONS) {" +
+ "br1.implies(_gr1) && br2.implies(_gr2) ?
result.impliedBy(BASIC_COMPOSITIONS[br1.basicRelationOrdinal()][br2.basicRelationOrdinal()])"
+
+ "}}")
+ })
+ public static AllenRelation compose(AllenRelation gr1, AllenRelation
gr2) {
+ assert preArgumentNotNull(gr1, "gr1");
+ assert preArgumentNotNull(gr2, "gr2");
+ AllenRelation acc = EMPTY;
+ for (AllenRelation br1 : BASIC_RELATIONS) {
+ if (gr1.impliedBy(br1)) {
+ for (AllenRelation br2 : BASIC_RELATIONS) {
+ if (gr2.impliedBy(br2)) {
+ acc = or(acc,
BASIC_COMPOSITIONS[br1.basicRelationOrdinal()][br2.basicRelationOrdinal()]);
+ }
+ }
+ }
+ }
+ return acc;
+ }
+
+ /**
+ * The relation from {@code i1} to {@code i2} with the lowest possible
{@link #uncertainty()}.
+ * {@code null} as {@link TimeInterval#getBegin()} or {@link
TimeInterval#getEnd()} is considered
+ * as unknown, and thus is not used to restrict the relation more,
leaving it with
+ * more {@link #uncertainty()}.
+ *
+ * @mudo contract
+ */
+ public static AllenRelation allenRelation(TimeInterval i1, TimeInterval
i2) {
+ Date i1Begin = i1.getBegin();
+ Date i1End = i1.getEnd();
+ Date i2Begin = i2.getBegin();
+ Date i2End = i2.getEnd();
+ AllenRelation result = FULL;
+ if (i1Begin != null) {
+ if (i2Begin != null) {
+ if (i1Begin.before(i2Begin)) {
+ result = min(result, BEGINS_EARLIER.complement());
+ }
+ else if (i1Begin.equals(i2Begin)) {
+ result = min(result, BEGIN_TOGETHER.complement());
+ }
+ else {
+ assert i1Begin.after(i2Begin);
+ result = min(result, BEGINS_LATER.complement());
+ }
+ }
+ if (i2End != null) {
+ if (i1Begin.before(i2End)) { // pmoFDseSdfO, not MP; begins before
end
+ result = min(result, MET_BY);
+ result = min(result, PRECEDED_BY);
+ }
+ else if (i1Begin.equals(i2End)) {
+ return MET_BY;
+ }
+ else {
+ assert i1Begin.after(i2End);
+ return PRECEDED_BY;
+ }
+ }
+ }
+ if (i1End != null) {
+ if (i2Begin != null) {
+ if (i1End.before(i2Begin)) {
+ return PRECEDES;
+ }
+ else if (i1End.equals(i2Begin)) {
+ return MEETS;
+ }
+ else {
+ assert i1End.after(i2Begin); // not pm, oFDseSdfOMP, ends after
begin
+ result = min(result, PRECEDES);
+ result = min(result, MEETS);
+ }
+ }
+ if (i2End != null) {
+ if (i1End.before(i2End)) {
+ result = min(result, ENDS_EARLIER.complement());
+ }
+ else if (i1End.equals(i2End)) {
+ result = min(result, END_TOGETHER.complement());
+ }
+ else {
+ assert i1End.after(i2End);
+ result = min(result, ENDS_LATER);
+ }
+ }
+ }
+ return result;
+ }
+
/*</section>*/
@@ -536,6 +920,20 @@
//------------------------------------------------------------------
/**
+ * An ordinal for basic relations.
+ */
+ @Basic(pre = @Expression("isBasic()"),
+ invars = {@Expression("result >= 0"), @Expression("result < 13")})
+ public int basicRelationOrdinal() {
+ /*
+ * This is the bit position, 0-based, in the 13-bit bit pattern, of
the bit
+ * representing this as basic relation.
+ */
+ assert pre(isBasic());
+ return Integer.numberOfTrailingZeros($bitPattern);
+ }
+
+ /**
* This is a basic Allen relation.
*/
@MethodContract(post = @Expression("BASIC_RELATIONS.contains(this)"))
@@ -561,6 +959,28 @@
}
/**
+ * A measure about the uncertainty this Allen relation expresses.
+ * This is the fraction of the 13 basic relations that imply this
general relation.
+ * {@link #FULL} is complete uncertainty, and returns {@code 1}.
+ * A basic relation is complete certainty, and returns {@code 0}.
+ * The {@link #EMPTY empty} relation has no meaningful uncertainty. This
method returns
+ * {@link Float#NaN} as value for {@link #EMPTY}.
+ */
+ @MethodContract(post = {
+ @Expression("this != EMPTY ? result == count (AllenRelation br :
BASIC_RELATIONS) {br.implies(this)} - 1) / 12"),
+ @Expression("this == EMPTY ? result == Float.NaN")
+ })
+ public float uncertainty() {
+ int count = Integer.bitCount($bitPattern);
+ if (count == 0) {
+ return Float.NaN;
+ }
+ count--;
+ count /= 12;
+ return count;
+ }
+
+ /**
* The <dfn>converse</dfn> of an Allen relation from an interval
<var>I1</var> to an interval <var>I2</var>
* is the relation from the interval <var>I2</var> to the interval
<var>I1</var>:
* <pre>
@@ -584,7 +1004,7 @@
@Expression("this == OVERLAPPED_BY ? converse() == OVERLAPS"),
@Expression("this == MET_BY ? converse() == MEETS"),
@Expression("this == PRECEDED_BY ? converse() == PRECEDES"),
- @Expression("for (AllenRelation br : BASIC_RELATIONS) {CONTAINS(br) ??
converse().CONTAINS(br.converse())}")
+ @Expression("for (AllenRelation br : BASIC_RELATIONS)
{impliedBy(br) ?? converse().impliedBy(br.converse())}")
})
public final AllenRelation converse() {
/*
@@ -599,17 +1019,70 @@
}
/**
- * The complement of an Allen relation is the logic negation of the
condition the Allen relation expresses.
- * The complement of a basic Allen relation is the disjunction of all
the other basic Allen relations.
- * The complement of a general Allen relation is the disjunction of all
basic Allen relations that are
- * not implied by the general Allen relation. NIEt KLAAR
- * <pre>
- * R.CONTAINS(A) ?? ! R.CONTAINS(A.complement())
+ * <p>The complement of an Allen relation is the logic negation of the
condition the Allen relation expresses.
+ * The complement of a basic Allen relation is the disjunction of all
the other basic Allen relations.
+ * The complement of a general Allen relation is the disjunction of
all basic Allen relations that are
+ * not implied by the general Allen relation.</p>
+ * <p>This method is key to validating semantic constraints on time
intervals, using the following idiom:</p>
+ * <pre>
+ * ...
+ * TimeInterval i1 = ...;
+ * TimeInterval i2 = ...;
+ * AllenRelation condition = ...;
+ * AllenRelation actual = allenRelation(i1, i2);
+ * if (! actual.implies(condition)) {
+ * throw new ....
+ * }
+ * ...
* </pre>
+ * <p><strong>Be aware that the complement has in general not the same
meaning as a logic negation.</strong>
+ * For a basic relation <var>br</var> and a general Allen relation
<var>cond</var>, it is true that</p>
+ * <p><code><var>br</var>.implies(<var>cond</var>)</code> ⇔
+ * <code>!
<var>br</var>.implies(<var>cond</var>.complement())</code></p>
+ * <p><strong>This is however not so for non-basic, and thus general
Allen relations</strong>, as the following
+ * counterexample proofs. Suppose a condition is that, for a general
relation <var>gr</var>:</p>
+ * <pre><var>gr</var>.implies(<var>cond</var>)</pre>
+ * <p>Suppose <code><var>gr</var> == (mFO)</code>. Then we can rewrite
in the following way:</p>
+ *
<p> <code><var>gr</var>.implies(<var>cond</var>)</code><br
/>
+ * ⇔ <code>(mFO).implies(<var>cond</var>)</code><br />
+ * ⇔ <code>(mFO) ⊆ <var>cond</var></code><br />
+ * ⇔ <code>(mFO) ⊆ <var>cond</var></code><br />
+ * ⇔ <code>(m ∈ <var>cond</var>) && (F ∈
<var>cond</var>) && (O ∈ <var>cond</var>)</code></p>
+ * <p>From the definition of the complement, it follows that, for a
basic relation <var>br</var> and a general
+ * relation <var>GR</var> as set</p>
+ * <p><code>br ∈ GR</code> ⇔ <code>br ∉
GR.complement()</code></p>
+ * <p>Thus:</p>
+ * <p>⇔ <code>(m ∉ <var>cond</var>.complement()) && (F
∉ <var>cond</var>.complement()) &&
+ * (O ∉ <var>cond</var>.complement())</code><br />
+ * ⇔ <code>! ((m ∈ <var>cond</var>.complement()) || (F
∈ <var>cond</var>.complement()) ||
+ * (O ∈ <var>cond</var>.complement())</code> (1)</p>
+ * <p>While, from the other side:</p>
+ * <p> <code>!
<var>gr</var>.implies(<var>cond</var>.complement())</code><br />
+ * ⇔ <code>!
(mFO).implies(<var>cond</var>.complement())</code><br />
+ * ⇔ <code>! (mFO) ⊆
(<var>cond</var>.complement())</code><br />
+ * ⇔ <code>! ((m ∈ <var>cond</var>.complement()) && (F
∈ <var>cond</var>.complement()) &&
+ * (O ∈ <var>cond</var>.complement()))</code> (2)</p>
+ * <p>It is clear that (1) is incompatible with (2), except for the case
where the initial relation is basic.</p>
+ * <p>In the reverse case, for a basic relation <var>br</var> and a
general Allen relation <var>actual</var>, nothing
+ * special can be said about the complement of <var>actual</var>, as
the following reasoning illustrates:</p>
+ *
<p> <code><var>actual</var>.implies(<var>br</var>)</code><br
/>
+ * ⇔<code><var>actual</var> ⊆ <var>br</var></code><br />
+ * ⇔<code><var>actual</var> ⊆ (<var>br</var>)</code><br />
+ * ⇔<code><var>actual</var> == (<var>br</var>) ||
<var>actual</var> == ∅</code><br />
+ * ⇔<code><var>actual</var>.complement() ==
(<var>br</var>).complement() || <var>actual</var>.complement() ==
FULL</code> (3)</p>
+ * <p>From the other side:</p>
+ * <p> <code>!
<var>actual</var>.complement().implies(<var>br</var>)</code><br />
+ * ⇔<code>! (<var>actual</var>.complement() ⊆
<var>br</var>)</code><br />
+ * ⇔<code>! (<var>actual</var>.complement() ⊆
(<var>br</var>))</code><br />
+ * ⇔<code>! (<var>actual</var>.complement() == (<var>br</var>) ||
<var>actual</var>.complement() == ∅)</code><br />
+ * ⇔<code><var>actual</var>.complement() != (<var>br</var>) &&
<var>actual</var>.complement() != ∅</code> (4)</p>
+ * <p>It is clear that (3) expresses something completely different then
(4), and this effect is obviously even stronger with
+ * non-basic relations.</p>
+ * <p>Note that it is exactly this counter-intuitivity that makes
reasoning with time intervals so difficult.</p>
*/
@MethodContract(post = {
@Expression("for (AllenRelation br : BASIC_RELATIONS) {" +
- "(CONTAINS(br) ?? ! complement().CONTAINS(br)) && (!
CONTAINS(br) ?? complement().CONTAINS(br))" +
+ "(impliedBy(br) ?? ! complement().impliedBy(br)) && (!
impliedBy(br) ?? complement().impliedBy(br))" +
"}")
})
public final AllenRelation complement() {
@@ -622,155 +1095,39 @@
return VALUES[result];
}
+ /**
+ * Is {@code this} implied by {@code gr}? In other words, when
considering the relations as a set
+ * of basic relations, is {@code this} a superset of {@code gr}
(considering equality as also acceptable)?
+ */
@Basic(
pre = @Expression("_gr != null"),
invars = {
- @Expression("CONTAINS(this)"),
- @Expression("basic ? for (AllenRelation br : BASIC_RELATIONS) :
{br != this ? ! CONTAINS(br)}"),
- @Expression("for (AllenRelation ar) {CONTAINS(ar) == for
(AllenRelation br : BASIC_RELATIONS) : {ar.CONTAINS(br) ? CONTAINS(br)}")
+ @Expression("impliedBy(this)"),
+ @Expression("basic ? for (AllenRelation br : BASIC_RELATIONS) :
{br != this ? ! impliedBy(br)}"),
+ @Expression("for (AllenRelation ar) {impliedBy(ar) == for
(AllenRelation br : BASIC_RELATIONS) : {ar.impliedBy(br) ? impliedBy(br)}")
}
)
- public final boolean CONTAINS(AllenRelation gr) {
+ public final boolean impliedBy(AllenRelation gr) {
assert preArgumentNotNull(gr, "gr");
return (($bitPattern & gr.$bitPattern) == gr.$bitPattern) ||
($bitPattern == 0);
}
- /*</section>*/
-
- /*</section>*/
-
-
-
- /*<section name="n-ary operations">*/
- //------------------------------------------------------------------
-
-
-
-
/**
- * Union
+ * Does {@code this} imply {@code gr}? In other words, when considering
the relations as a set
+ * of basic relations, is {@code this} a subset of {@code gr}
(considering equality as also acceptable)?
*/
- public static AllenRelation or(AllenRelation gr1, AllenRelation gr2) {
- int or = gr1.$bitPattern | gr2.$bitPattern;
- return VALUES[or];
- }
-
- /**
- * Intersection
- */
- public static AllenRelation and(AllenRelation gr1, AllenRelation gr2) {
- int and = gr1.$bitPattern & gr2.$bitPattern;
- return VALUES[and];
- }
-
- /**
- * Remove basic relations in {@code gr2} from {@code gr1}.
- */
- public static AllenRelation min(AllenRelation gr1, AllenRelation gr2) {
- int xor = gr1.$bitPattern ^ gr2.$bitPattern;
- int min = gr1.$bitPattern & xor;
- return VALUES[min];
+ @Basic(
+ pre = @Expression("_gr != null"),
+ invars = @Expression("_gr.impliedBy(this)")
+ )
+ public final boolean implies(AllenRelation gr) {
+ assert preArgumentNotNull(gr, "gr");
+ return ((gr.$bitPattern & $bitPattern) == $bitPattern) ||
(gr.$bitPattern == 0);
}
+ /*</section>*/
- public final static AllenRelation[][] BASIC_COMPOSITIONS =
- {
-
{PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,ENDS_EARLIER,ENDS_EARLIER,ENDS_EARLIER,ENDS_EARLIER,FULL},
-
{PRECEDES,PRECEDES,PRECEDES,PRECEDES,PRECEDES,MEETS,MEETS,MEETS,ENDS_IN,ENDS_IN,ENDS_IN,END_TOGETHER,ENDS_LATER},
-
{PRECEDES,PRECEDES,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER,OVERLAPS,OVERLAPS,CONTAINS_BEGIN,ENDS_IN,ENDS_IN,CONCURS_WITH,CONTAINS_END,ENDS_LATER},
-
{PRECEDES,MEETS,OVERLAPS,FINISHED_BY,CONTAINS,OVERLAPS,FINISHED_BY,CONTAINS,ENDS_IN,END_TOGETHER,CONTAINS_END,CONTAINS_END,ENDS_LATER},
-
{BEGINS_EARLIER,CONTAINS_BEGIN,CONTAINS_BEGIN,CONTAINS,CONTAINS,CONTAINS_BEGIN,CONTAINS,CONTAINS,CONCURS_WITH,CONTAINS_END,CONTAINS_END,CONTAINS_END,ENDS_LATER},
-
{PRECEDES,PRECEDES,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER_AND_ENDS_EARLIER,BEGINS_EARLIER,STARTS,STARTS,BEGIN_TOGETHER,DURING,DURING,BEGINS_IN,MET_BY,PRECEDED_BY},
-
{PRECEDES,MEETS,OVERLAPS,FINISHED_BY,CONTAINS,STARTS,EQUALS,STARTED_BY,DURING,FINISHES,OVERLAPPED_BY,MET_BY,PRECEDED_BY},
-
{BEGINS_EARLIER,CONTAINS_BEGIN,CONTAINS_BEGIN,CONTAINS,CONTAINS,BEGIN_TOGETHER,STARTED_BY,STARTED_BY,BEGINS_IN,OVERLAPPED_BY,OVERLAPPED_BY,MET_BY,PRECEDED_BY},
-
{PRECEDES,PRECEDES,ENDS_EARLIER,ENDS_EARLIER,FULL,DURING,DURING,BEGINS_LATER,DURING,DURING,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY},
-
{PRECEDES,MEETS,ENDS_IN,END_TOGETHER,ENDS_LATER,DURING,FINISHES,BEGINS_LATER_AND_ENDS_LATER,DURING,FINISHES,BEGINS_LATER_AND_ENDS_LATER,PRECEDED_BY,PRECEDED_BY},
-
{BEGINS_EARLIER,CONTAINS_BEGIN,CONCURS_WITH,CONTAINS_END,ENDS_LATER,BEGINS_IN,OVERLAPPED_BY,BEGINS_LATER_AND_ENDS_LATER,BEGINS_IN,OVERLAPPED_BY,BEGINS_LATER_AND_ENDS_LATER,PRECEDED_BY,PRECEDED_BY},
-
{BEGINS_EARLIER,BEGIN_TOGETHER,BEGINS_IN,MET_BY,PRECEDED_BY,BEGINS_IN,MET_BY,PRECEDED_BY,BEGINS_IN,MET_BY,PRECEDED_BY,PRECEDED_BY,PRECEDED_BY},
-
{FULL,BEGINS_LATER,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY,BEGINS_LATER,PRECEDED_BY,PRECEDED_BY,PRECEDED_BY,PRECEDED_BY}
- };
-
- /**
- * O(13^2)
- */
- public static AllenRelation compose(AllenRelation gr1, AllenRelation
gr2) {
- AllenRelation acc = EMPTY;
- for (AllenRelation br1 : BASIC_RELATIONS) {
- if (gr1.CONTAINS(br1)) {
- int p1 = Integer.numberOfTrailingZeros(br1.hashCode());
- for (AllenRelation br2 : BASIC_RELATIONS) {
- if (gr2.CONTAINS(br2)) {
- int p2 = Integer.numberOfTrailingZeros(br2.hashCode());
- acc = or(acc, BASIC_COMPOSITIONS[p1][p2]);
- }
- }
- }
- }
- return acc;
- }
- public static AllenRelation compare(TimeInterval p1, TimeInterval p2) {
- Date p1Begin = p1.getBegin();
- Date p1End = p1.getEnd();
- Date p2Begin = p2.getBegin();
- Date p2End = p2.getEnd();
- AllenRelation result = FULL;
- if (p1Begin != null) {
- if (p2Begin != null) {
- if (p1Begin.before(p2Begin)) {
- result = min(result, BEGINS_EARLIER.complement());
- }
- else if (p1Begin.equals(p2Begin)) {
- result = min(result, BEGIN_TOGETHER.complement());
- }
- else {
- assert p1Begin.after(p2Begin);
- result = min(result, BEGINS_LATER.complement());
- }
- }
- if (p2End != null) {
- if (p1Begin.before(p2End)) { // pmoFDseSdfO, not MP; begins before end
- result = min(result, MET_BY);
- result = min(result, PRECEDED_BY);
- }
- else if (p1Begin.equals(p2End)) {
- return MET_BY;
- }
- else {
- assert p1Begin.after(p2End);
- return PRECEDED_BY;
- }
- }
- }
- if (p1End != null) {
- if (p2Begin != null) {
- if (p1End.before(p2Begin)) {
- return PRECEDES;
- }
- else if (p1End.equals(p2Begin)) {
- return MEETS;
- }
- else {
- assert p1End.after(p2Begin); // not pm, oFDseSdfOMP, ends after begin
- result = min(result, PRECEDES);
- result = min(result, MEETS);
- }
- }
- if (p2End != null) {
- if (p1End.before(p2End)) {
- result = min(result, ENDS_EARLIER.complement());
- }
- else if (p1End.equals(p2End)) {
- result = min(result, END_TOGETHER.complement());
- }
- else {
- assert p1End.after(p2End);
- result = min(result, ENDS_LATER);
- }
- }
- }
- return result;
- }
@Override
public final int hashCode() {
@@ -781,8 +1138,6 @@
return $bitPattern;
}
- private final static String[] BASIC_CODES =
{"p", "m", "o", "F", "D", "s", "e", "S", "d", "f", "O", "M", "P"};
-
/**
* This returns a representation of the Allen relation in the most used
short notation (pmoFDseSdfOMP).
*/
@@ -791,11 +1146,11 @@
StringBuilder result = new StringBuilder();
result.append("(");
if (isBasic()) {
-
result.append(BASIC_CODES[Integer.numberOfTrailingZeros($bitPattern)]);
+ result.append(BASIC_CODES[basicRelationOrdinal()]);
}
else {
for (int i = 0; i < BASIC_CODES.length; i++) {
- if (CONTAINS(BASIC_RELATIONS.get(i))) {
+ if (impliedBy(BASIC_RELATIONS[i])) {
result.append(BASIC_CODES[i]);
}
}
Modified:
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/BeginEndTimeInterval.java
==============================================================================
---
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/BeginEndTimeInterval.java
(original)
+++
java/value/trunk/src/main/java/org/ppwcode/value_III/time/interval/BeginEndTimeInterval.java
Thu Oct 23 06:51:23 2008
@@ -25,6 +25,7 @@
import org.ppwcode.metainfo_I.License;
import org.ppwcode.metainfo_I.vcs.SvnInfo;
import org.ppwcode.value_III.legacy.DayPeriod;
+import org.ppwcode.value_III.time.Duration;
import org.ppwcode.vernacular.value_III.AbstractMutableValue;
@@ -55,7 +56,8 @@
@License(APACHE_V2)
@SvnInfo(revision = "$Revision$",
date = "$Date$")
-public class BeginEndTimeInterval extends AbstractMutableValue implements
Comparable {
+public class BeginEndTimeInterval extends AbstractMutableValue implements
TimeInterval {
+
/*<construction>*/
@@ -67,6 +69,18 @@
* @post getStartDate() == null;
* @post getEndDate() == null;
*/
+ public BeginEndTimeInterval(Date begin, Date end) {
+ // Since we demand of subtypes of MutableValue that they implement
+ // {@link java.io.Serializable}, a default constructor is mandatory.
+ // NOP
+ }
+
+ /**
+ * Create a new empty period object.
+ *
+ * @post getStartDate() == null;
+ * @post getEndDate() == null;
+ */
public BeginEndTimeInterval() {
// Since we demand of subtypes of MutableValue that they implement
// {@link java.io.Serializable}, a default constructor is mandatory.
@@ -379,6 +393,16 @@
public boolean contains(final Date date) {
return containsInclusive(date);
+ }
+
+ public AllenRelation compareTo(TimeInterval other) {
+ // TODO Auto-generated method stub
+ return null;
+ }
+
+ public Duration getDuration() {
+ // TODO Auto-generated method stub
+ return null;
}
}