HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

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;
    }