Range同士の関係を判定する述語についてまとめてみる
非常につまらないミスをやらかして凹んでいるので、反省の意味を込めて、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」の位置関係について、全パターンを列挙してみようと思う。
- Rangeの中にendを含むケース
●━━━━━━━━● (01)●───● (02)●──────● (03)●───────────● (04)●───────────────● (05)●──────────────────────● (06) ●────● (07) ●────────● (08) ●───────────────● (09) ●───● (10) ●──────────● (11) ●──────● (12) ●───●
- Rangeの中にendは含まないケース
●━━━━━━━━○ (01)●───○ (02)●──────○ (03)●───────────○ (04)●───────────────○ (05)●──────────────────────○ (06) ●────○ (07) ●────────○ (08) ●───────────────○ (09) ●───○ (10) ●──────────○ (11) ●──────○ (12) ●───○
overlaps
overlapsとは、一言で言うと、2つのRange間に重なりがあるかどうかの判定である。 列挙した全パターンのうち、overlapsに該当するのはそれぞれ以下のとおりである。
- Rangeの中にendを含むケース
●━━━━━━━━● (02)●──────● (03)●───────────● (04)●───────────────● (05)●──────────────────────● (06) ●────● (07) ●────────● (08) ●───────────────● (09) ●───● (10) ●──────────● (11) ●──────●
全パターンから除外されたのが以下の2パターンである。
- range2.end < range1.begin
- range1.end < range2.begin
つまり、それ以外は「overlaps」とみなされるので、以下のような条件式で判定できる。
public boolean overlaps(Range that) { return this.begin <= that.end && that.begin <= this.end; }
- Rangeの中にendは含まないケース
●━━━━━━━━○ (03)●───────────○ (04)●───────────────○ (05)●──────────────────────○ (06) ●────○ (07) ●────────○ (08) ●───────────────○ (09) ●───○ (10) ●──────────○
全パターンから除外されたのが以下の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)」なのでここでは考えない。
- Rangeの中にendを含むケース
先にも述べたように、これは「overlaps」に内包されると考えるので、このケースでの「meets」は無いとみなす。
- Rangeの中にendは含まないケース
●━━━━━━━━○ (11) ●──────○
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean meets(Range that) { return this.end == that.begin; }
precedes
「precedes」とは、range1がrange2より前に位置するかどうかを判定する述語である。
- Rangeの中にendを含むケース
●━━━━━━━━● (12) ●───●
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean precedes(Range that) { return this.end < that.begin; }
- Rangeの中にendは含まないケース
●━━━━━━━━○ (12) ●───○
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean precedes(Range that) { return this.end < that.begin; }
succeeds
「succeeds」とは、range1がrange2より後に位置するかどうかを判定する述語である。
- Rangeの中にendを含むケース
●━━━━━━━━● (01)●───●
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean succeeds(Range that) { return this.begin > that.end; }
- Rangeの中にendは含まないケース
●━━━━━━━━○ (01)●───○
見ての通り、1パターンしかないので、条件式は以下のようになる。
public boolean succeeds(Range that) { return this.begin > that.end; }
contains
「contains」とは、文字通りrange1がrange2の範囲を完全に含むかどうかを判定する述語である。
- Rangeの中にendを含むケース
●━━━━━━━━● (06) ●────● (07) ●────────● (09) ●───●
条件式は以下のようになる。
public boolean contains(Range that) { return this.begin <= that.begin && that.end <= this.end; }
- Rangeの中にendは含まないケース
●━━━━━━━━○ (06) ●────○ (07) ●────────○ (09) ●───○
条件式は以下のようになる。
public boolean contains(Range that) { return this.begin <= that.begin && that.end <= this.end; }
equals
「equals」とは、言うまでもなくrange1とrange2が同じ範囲を表しているかどうかを判定する述語である。
- Rangeの中にendを含むケース
●━━━━━━━━● (07) ●────────●
条件式は以下のようになる。
public boolean equals(Range that) { return this.begin == that.begin && this.end == that.end; }
- Rangeの中にendは含まないケース
●━━━━━━━━○ (07) ●────────○
条件式は以下のようになる。
public boolean equals(Range that) { return this.begin == that.begin && this.end == that.end; }