非常につまらないミスをやらかして凹んでいるので、反省の意味を込めて、Rangeに対して実装できる述語を整理してみるテスト。
ちなみに、Rangeとは開始と終了（begin & end、from & to、left & right、etc.）の範囲を表現することができる何か。
Javaでクラスとして実装すると以下のような感じだろうか。
public class Range {
private long begin;
private long end;
public Range(long begin, long end) {
if (begin > end) {
throw new RuntimeException("begin > end");
}
this.begin = begin;
this.end = end;
}
public long getBegin() {
return begin;
}
public long getEnd() {
return end;
}
}
さて、これに述語をメソッドとして追加していきたいのだが、その前に「述語」って何？って話からしていくと、要はそのRangeが他のRangeと被ってるの？含んでるの？等しいの？とかそういうことである。
述語として考えられるものは、Rangeが表す意味によって2系統に分けられる。
- Rangeの中にendを含むケース
- Rangeの中にendは含まないケース
つまり、new Range(1, 10)としたときに、10をRange(範囲)に含むか含まないかということである（各プログラム言語でRangeがどう扱われるかについては、以前に「rangeによるrangeの違い - HHeLiBeXの日記 正道編」でまとめたので、興味があれば参考にしてください）。
で、それぞれのケースに於いて、どんな述語が考えられるかを列挙したのが以下である。
- Rangeの中にendを含むケース
- overlaps
- precedes
- succeeds
- contains
- equals
- Rangeの中にendは含まないケース
- overlaps
- meets
- precedes
- succeeds
- contains
- equals
こんなところだろうか（ほかにあったら教えて・・）。
「Rangeの中にendは含まないケース」にだけ「meets」というのがあるが、これはendがexclusiveだからこその述語である。これらは「Rangeの中にendを含むケース」では「overlaps」に内包されるものである（beginとendが例えば整数値しか取らないようなケースでは、「range1.end + 1 == range2.begin」は「meets」じゃないのか？という議論もあるが、それはここでは考えないことにする）。
では順に見て行こう‥と言いたいところだが、上記の順で見ていくと説明が二重になりそうなので、述語ごとに見ていくことにする。
それぞれの述語の説明において、パターンを図示し、最終的に判定式にまとめ上げていく。
なお、それぞれの図示の中での記号の意味は以下の通りである。
- 「●」はその値をRangeに含むこと
- 「○」はその値をRangeに含まないこと
- 「━」は「range1」の範囲に含まれる値
- 「─」は「range2」の範囲に含まれる値
- 左側の「●」はbeginを表す
- 右側の「●」または「○」はendを表す
全パターンの列挙
まずは、「range1」と「range2」の位置関係について、全パターンを列挙してみようと思う。
●━━━━━━━━●
（０１）●───●
（０２）●──────●
（０３）●───────────●
（０４）●───────────────●
（０５）●──────────────────────●
（０６） ●────●
（０７） ●────────●
（０８） ●───────────────●
（０９） ●───●
（１０） ●──────────●
（１１） ●──────●
（１２） ●───●
●━━━━━━━━○
（０１）●───○
（０２）●──────○
（０３）●───────────○
（０４）●───────────────○
（０５）●──────────────────────○
（０６） ●────○
（０７） ●────────○
（０８） ●───────────────○
（０９） ●───○
（１０） ●──────────○
（１１） ●──────○
（１２） ●───○
overlaps
overlapsとは、一言で言うと、2つのRange間に重なりがあるかどうかの判定である。
列挙した全パターンのうち、overlapsに該当するのはそれぞれ以下のとおりである。
●━━━━━━━━●
（０２）●──────●
（０３）●───────────●
（０４）●───────────────●
（０５）●──────────────────────●
（０６） ●────●
（０７） ●────────●
（０８） ●───────────────●
（０９） ●───●
（１０） ●──────────●
（１１） ●──────●
全パターンから除外されたのが以下の2パターンである。
- range2.end < range1.begin
- range1.end < range2.begin
つまり、それ以外は「overlaps」とみなされるので、以下のような条件式で判定できる。
public boolean overlaps(Range that) {
return this.begin <= that.end && that.begin <= this.end;
}
●━━━━━━━━○
（０３）●───────────○
（０４）●───────────────○
（０５）●──────────────────────○
（０６） ●────○
（０７） ●────────○
（０８） ●───────────────○
（０９） ●───○
（１０） ●──────────○
全パターンから除外されたのが以下の4パターンである。
- range2.end < range1.begin
- range2.end = range1.begin
- range1.end = range2.begin
- range1.end < range2.begin
注意してほしいのは、endはRangeに『含まれない』ということである。
まとめると、以下のような条件式で「overlaps」を判定できる。
public boolean overlaps(Range that) {
return this.begin < that.end && that.begin < this.end;
}
meets
「meets」とは、range1がrange2にちょうど接続するかどうか（連続した1つのRangeにマージできるかどうか）を判定する述語である。
ものによっては「metBy」という述語を入れる場合もあるが、「range1.meets(range2) == range2.metBy(range1)」なのでここでは考えない。
先にも述べたように、これは「overlaps」に内包されると考えるので、このケースでの「meets」は無いとみなす。
●━━━━━━━━○
（１１） ●──────○
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean meets(Range that) {
return this.end == that.begin;
}
precedes
「precedes」とは、range1がrange2より前に位置するかどうかを判定する述語である。
●━━━━━━━━●
（１２） ●───●
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean precedes(Range that) {
return this.end < that.begin;
}
●━━━━━━━━○
（１２） ●───○
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean precedes(Range that) {
return this.end < that.begin;
}
succeeds
「succeeds」とは、range1がrange2より後に位置するかどうかを判定する述語である。
●━━━━━━━━●
（０１）●───●
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean succeeds(Range that) {
return this.begin > that.end;
}
●━━━━━━━━○
（０１）●───○
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean succeeds(Range that) {
return this.begin > that.end;
}
contains
「contains」とは、文字通りrange1がrange2の範囲を完全に含むかどうかを判定する述語である。
●━━━━━━━━●
（０６） ●────●
（０７） ●────────●
（０９） ●───●
条件式は以下のようになる。
public boolean contains(Range that) {
return this.begin <= that.begin && that.end <= this.end;
}
●━━━━━━━━○
（０６） ●────○
（０７） ●────────○
（０９） ●───○
条件式は以下のようになる。
public boolean contains(Range that) {
return this.begin <= that.begin && that.end <= this.end;
}
equals
「equals」とは、言うまでもなくrange1とrange2が同じ範囲を表しているかどうかを判定する述語である。
●━━━━━━━━●
（０７） ●────────●
条件式は以下のようになる。
public boolean equals(Range that) {
return this.begin == that.begin && this.end == that.end;
}
●━━━━━━━━○
（０７） ●────────○
条件式は以下のようになる。
public boolean equals(Range that) {
return this.begin == that.begin && this.end == that.end;
}
