Forum: Ruby Range#overlap?

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
5da4c52f43677f395aff5bde775593c2?d=identicon&s=25 Daniel Schierbeck (dasch)
on 2007-02-20 01:08
(Received via mailing list)
(I'm sending this to the list because I think it has general interest.
Sorry if you disagree!)

Hi T. and the rest of you,

I was discussing[1] a method that tested whether one range overlaps
another, and noticed that Facets has a somewhat funny implementation
called #within?. I came up with this:

  class Range
    def overlap? other
      include? other.first or other.include? first
    end
  end

It would seem to be simpler, and I really like the method name. Can you
see any errors? Feel free to add it to Facets if you wish to.


Cheers,
Daniel


 1. http://opensoul.org/2007/2/13/ranges-include-or-ov...
Cd3312ac93f768b1b449af457c0fca06?d=identicon&s=25 unknown (Guest)
on 2007-02-20 02:57
(Received via mailing list)
I think that overlap? and within? are two different things, which I'm
not sure you think from your email. Overlap? suggests, to me, that a
subset of the things one range includes is the same as a subset of
things that the other range includes. Within? suggests that all of one
range is contained in a subset of the other range.

Otherwise, I do like both names and your implementation.

----- Original Message -----
From: Daniel Schierbeck
Date: Monday, February 19, 2007 7:08 pm
Subject: [Facets] Range#overlap?
To: ruby-talk@ruby-lang.org (ruby-talk ML)
5da4c52f43677f395aff5bde775593c2?d=identicon&s=25 Daniel Schierbeck (dasch)
on 2007-02-20 14:03
(Received via mailing list)
On Tue, 2007-02-20 at 10:56 +0900, danfinnie@optonline.net wrote:
> I think that overlap? and within? are two different things, which I'm not sure you think 
from your email. Overlap? suggests, to me, that a subset of the things one range includes 
is the same as a subset of things that the other range includes. Within? suggests that all 
of one range is contained in a subset of the other range.

Exactly, but that's not how it's implemented in Facets ;)

I don't like #within? because it seems closer to #in? than to #include?.
a.within? b suggests the following:

  a  |-----|
  b |-------|

I'd much rather have something else... #span?, perhaps?


Cheers,
Daniel
Cd3312ac93f768b1b449af457c0fca06?d=identicon&s=25 Daniel Finnie (Guest)
on 2007-02-20 14:48
(Received via mailing list)
That seems to be what facet/range/within does now.

daniel@daniel-desktop:~$ irb
 >> require 'facet/range/within'
=> true
 >> (1..3).within?(0..4)
=> true
 >> (0..3).within?(0..4)
=> true
 >> (-1..3).within?(0..4)
=> false
 >> (1..4).within?(0..4)
=> true
 >> (1..5).within?(0..4)
=> false

Whereas overlap?, IMHO, would return true to all of these.  In the cool
ASCII diagrams, it would be like this:
    |-----| a
|----| b
a.overlap? b #=> true

Dan
5da4c52f43677f395aff5bde775593c2?d=identicon&s=25 Daniel Schierbeck (dasch)
on 2007-02-20 21:35
(Received via mailing list)
On Tue, 2007-02-20 at 22:47 +0900, Daniel Finnie wrote:
> That seems to be what facet/range/within does now.

It's implementation is rather odd, though.

Here's what I'd like to have instead:

  class Range
    def span? other
      include? other.first and
      other.last <= (other.exclude_end? ? last.succ : last)
    end
  end


Cheers,
Daniel
1fba4539b6cafe2e60a2916fa184fc2f?d=identicon&s=25 unknown (Guest)
on 2007-02-21 00:00
(Received via mailing list)
Hi --

On Wed, 21 Feb 2007, Daniel Schierbeck wrote:

>      other.last <= (other.exclude_end? ? last.succ : last)
>    end
>  end

Ranges don't always have lasts that have #succ, though.  Floats don't,
and arbitrary Comparables don't.


David
Cd3312ac93f768b1b449af457c0fca06?d=identicon&s=25 Daniel Finnie (Guest)
on 2007-02-21 00:01
(Received via mailing list)
I think your implementation is cleaner however the endpoints of a Range
do not have to implement #succ.

class Range
   def span? other
     include? other.first and
       (other.exclude_end? ? other.last < last : other.last <= last )
   end
end

I think within? is a better name.

Dan
5da4c52f43677f395aff5bde775593c2?d=identicon&s=25 Daniel Schierbeck (dasch)
on 2007-02-21 00:47
(Received via mailing list)
On Wed, 2007-02-21 at 08:00 +0900, Daniel Finnie wrote:
> I think your implementation is cleaner however the endpoints of a Range
> do not have to implement #succ.
>
> class Range
>    def span? other
>      include? other.first and
>        (other.exclude_end? ? other.last < last : other.last <= last )
>    end
> end

I've tried that implementation, but i doesn't work if you consider this
valid:

  (4..8).span? 6...9

Since 6...9 yields the same values as 6..8. Or am I wrong to expect the
above?

I know #last doesn't have to support #succ, and I'd be happy to see a
better implementation. Challenge? ;)


Cheers,
Daniel
Cd3312ac93f768b1b449af457c0fca06?d=identicon&s=25 Daniel Finnie (Guest)
on 2007-02-21 00:54
(Received via mailing list)
Which is, IMHO, correct:
 >> (4..8).include? 8.5
=> false
 >> (6...9).include? 8.5
=> true


Dan
1fba4539b6cafe2e60a2916fa184fc2f?d=identicon&s=25 unknown (Guest)
on 2007-02-21 01:05
(Received via mailing list)
Hi --

On Wed, 21 Feb 2007, Daniel Schierbeck wrote:

>
> I've tried that implementation, but i doesn't work if you consider this
> valid:
>
>  (4..8).span? 6...9
>
> Since 6...9 yields the same values as 6..8. Or am I wrong to expect the
> above?

I don't think ranges really yield values.  Some of them can be
converted to arrays, but a range qua range is really just two
endpoints, between which everything comparable to those endpoints
either is or isn't.

I'm not sure I have my head around what span? is supposed to be doing.
Can you write some test cases?  I keep thinking of this:

   include?(other.first) and include?(other.last)

but I don't think that's what you're trying to do with span?.


David
Feee221f9eb7818d90625ea141bfd60c?d=identicon&s=25 bbiker (Guest)
on 2007-02-21 03:46
(Received via mailing list)
On Feb 20, 7:04 pm, dbl...@wobblini.net wrote:
>
> >  (4..8).span? 6...9
> Can you write some test cases?  I keep thinking of this:
>     (See what readers are saying!  http://www.rubypal.com/r4rrevs.pdf)
> Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
> A. Ruby Power and Light, LLC (http://www.rubypal.com)- Hide quoted text -
>
> - Show quoted text -

Here is my entry for overlap?
<code>
require 'facets/core/range/within'

class Range

  # Uses the Range#within and Range#include methods to determine
  # if another Range _overlap_ this Range.
  # neither Range is within the other Range
  #   (1..3).overlap?(2..4)  #=> true
  #
  def overlap?(other)
    #   |---|      |---|   |-----|  |-----|  |-----|
    #   |-----|   |-----|  |-----|   |---|     |---|
    !self.within?(other) && !other.within?(self) &&
    #  |-------|    |------|
    #   |-------|          |-------|
    (self.include?(other.first) && other.include?(self.last) ||
    #   |-------|          |-------|
    #  |-------|    |------|
     other.include?(self.first) && self.include?(other.last))
  end
end


=begin test

  require 'test/unit'

  class TCRange < Test::Unit::TestCase

    def test_overlap?
      assert(!(3..6).overlap?(3..6) )
      assert(!(4..5).overlap?(3..6) )
      assert(!(2..7).overlap?(3..6) )
      assert( (2..5).overlap?(3..6) )
      assert( (2..3).overlap?(3..6) )
      assert( (7..10).overlap?(6..9) )
      assert( (9..12).overlap?(6..9) )
    end
  end
=end
</code>
Bc368ef524130e8d0deb386de961e24a?d=identicon&s=25 Suraj Kurapati (snk)
on 2007-02-21 03:55
unknown wrote:
> I think that overlap? and within? are two different things, which I'm
> not sure you think from your email. Overlap? suggests, to me, that a
> subset of the things one range includes is the same as a subset of
> things that the other range includes. Within? suggests that all of one
> range is contained in a subset of the other range.

Agreed. These terms evoke the following synonyms in my mind:

  overlap?   means   intersect?

  within?    means   subset?
1fba4539b6cafe2e60a2916fa184fc2f?d=identicon&s=25 unknown (Guest)
on 2007-02-21 04:02
(Received via mailing list)
HI --

On Wed, 21 Feb 2007, bbiker wrote:

>>>> do not have to implement #succ.
>>
>> I'm not sure I have my head around what span? is supposed to be doing.
>
>    !self.within?(other) && !other.within?(self) &&
> =begin test
>      assert( (2..3).overlap?(3..6) )
>      assert( (7..10).overlap?(6..9) )
>      assert( (9..12).overlap?(6..9) )
>    end
>  end
> =end
> </code>

Here's a slightly shorter method that makes all the tests pass:

     def overlap?(other)
       self.include?(other.first) &&! self.include?(other.last) or
       other.include?(self.first) &&! other.include?(self.last)
     end


David
31e038e4e9330f6c75ccfd1fca8010ee?d=identicon&s=25 Gregory Brown (Guest)
on 2007-02-21 05:29
(Received via mailing list)
On 2/20/07, Suraj Kurapati <snk@gna.org> wrote:
>
>   within?    means   subset?

These are much better names, I think.  Of course, it'll only be so if
you are mathematically inclined.
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2007-02-21 05:37
(Received via mailing list)
On Wed, 21 Feb 2007, Gregory Brown wrote:

>>   overlap?   means   intersect?
>>
>>   within?    means   subset?
>
> These are much better names, I think.  Of course, it'll only be so if
> you are mathematically inclined.
>

indeed.

overlaps would normally be defined as

   def overlap? other
     first < other.last and other.first < last
   end

in math is always means 'proper subset'.  in otherwords

   (0..42).overlap? (1..10) #=> true
   (1..10).overlap? (0..42) #=> true


ignoring issues of inclusive and exclusive end which, i might add, all
the
presented implimentations do as well.

regards.

-a
F0d821a746f93cece1240d52d3e2617f?d=identicon&s=25 Pierre-Charles David (Guest)
on 2007-02-21 11:24
(Received via mailing list)
FWIW, people working with temporal logics and event algebras define 13
possible relationships between two intervals (see Fig. 4 page 10 of
[1]), with a precise (if not always intuitive) vocabulary.

In Ruby, these would be (not tested):

class Range
  # self:   |---|
  # other:         |---|
  def before?(other)
    self.end < other.begin
  end

  # self:          |---|
  # other:  |---|
  def after?(other)
    other.before? self
  end

  # self:  |---|
  # other:     |---|
  def meets?(other)
    self.end == other.begin
  end

  # self:      |---|
  # other: |---|
  def met_by?(other)
    other.meets?(self)
  end

  # self:  |---|
  # other:   |---|
  def overlaps?(other)
    (self.begin < other.begin) and other.include?(self.end)
  end

  # self:    |---|
  # other: |---|
  def overlapped_by?(other)
    other.overlaps?(self)
  end

  # self:  |-----|
  # other:   |---|
  def finished_by?(other)
    (self.begin < other.begin) and (self.end == other.end)
  end

  # self:  |-----|
  # other: |---|
  def started_by?(other)
    (self.begin == other.begin) and (self.end > other.end)
  end

  # self:  |---|
  # other: |-----|
  def starts?(other)
    other.started_by?(self)
  end

  # self:    |---|
  # other: |-----|
  def finishes?(other)
    other.finished_by?(self)
  end

  # self:  |-------|
  # other:   |---|
  def contains?(other)
    (self.begin < other.begin) and (self.end > other.end)
  end

  # self:   |---|
  # other:  |---|
  def equals?(other)
    (self.begin == other.begin) and (self.end == other.end)
  end

  # self:     |---|
  # other:  |-------|
  def during?(other)
    other.contains?(self)
  end
end

[1] Allen, J.F. and Ferguson, G. Actions and Events in Interval
Temporal Logic, J. Logic and Computation 4, 5, 1994.
http://tinyurl.com/2twek7
5da4c52f43677f395aff5bde775593c2?d=identicon&s=25 Daniel Schierbeck (dasch)
on 2007-02-21 20:35
(Received via mailing list)
On Wed, 2007-02-21 at 09:04 +0900, dblack@wobblini.net wrote:
> >>      include? other.first and
> > above?
>
> but I don't think that's what you're trying to do with span?.

Here are my tests:

  class RangeSpanTest < Test::Unit::TestCase
    def setup
      @range = 4..8
    end

    def test_spans_subrange
      assert @range.span?(5..7)
    end

    def test_not_spans_range
      assert !@range.span?(9..14)
    end

    def test_spans_excluding_range
      assert @range.span?(6...9)
    end

    def test_not_spans_superrange
      assert !@range.span?(2..10)
    end
  end

Daniel Finnie has a point about end-excluding ranges. But in that case,
wouldn't this suffice?

  def span? other
    include? other.first and include? other.last
  end

#overlap? should return true if the two ranges *overlap*, e.g.

   |-----|
        |-----|

span? should only return true if the receiver spans at least the
entirety of the argument, e.g.

   |--------------|
      |-------|


Cheers,
Daniel
Cd3312ac93f768b1b449af457c0fca06?d=identicon&s=25 Daniel Finnie (Guest)
on 2007-02-22 05:33
(Received via mailing list)
I see a potential flaw in this if the ends were equal but other has
exclude end.

a:  |-----| (1...6, exclude end)
b:   |---| (3..6)

a.include?(6) #=> false
b.include?(6) #=> true

a.span?(b) #=> false
b.span?(a) #=> true, but should be false, IMHO.

I think the only way to do this is to make a mapping of
self  other   operation
  ..    ...      >=/>/etc
...     ..      >=/>/etc

Dan

Daniel Schierbeck wrote:
> Daniel Finnie has a point about end-excluding ranges. But in that case,
> wouldn't this suffice?
>
>   def span? other
>     include? other.first and include? other.last
>   end
E3c79c779c0b390049289cdfe7cb9705?d=identicon&s=25 Bob Hutchison (Guest)
on 2007-02-22 15:37
(Received via mailing list)
Hi,

I've worked in systems requiring temporal and interval logics for
years. Here is something I can pretty much guarantee: if you don't
get your terminology right you are going to spend almost all of your
time trying to figure out what each other is saying. Allen's
terminology is described and illustrated on page 10 of the paper:

On 21-Feb-07, at 5:23 AM, Pierre-Charles David wrote:
>
> [1] Allen, J.F. and Ferguson, G. Actions and Events in Interval
> Temporal Logic, J. Logic and Computation 4, 5, 1994.
> http://tinyurl.com/2twek7


There are 14 relationships described in that paper, 12 relationships
illustrated plus equal and disjoint which I guess the authors felt
too trivial to be worth illustrating. Allen's work in the early 80s
is the first widely accepted systematic terminology available and is
the vocabulary pretty much *everyone* who talks about intervals
regularly uses.

Anyway...

On 21-Feb-07, at 11:32 PM, Daniel Finnie wrote:

> b.span?(a) #=> true, but should be false, IMHO.
I don't know what either 'include' or 'span' actually means. And from
this question Daniel asks, it isn't just me.

You'll get a lot futher a lot faster if you use Allen's terminology.

You know, this probably is worth writing up as a trivial library and
sharing... but how to represent an interval :-)

Cheers,
Bob



----
Bob Hutchison                  -- blogs at <http://www.recursive.ca/
hutch/>
Recursive Design Inc.          -- <http://www.recursive.ca/>
Raconteur                      -- <http://www.raconteur.info/>
xampl for Ruby                 -- <http://rubyforge.org/projects/xampl/>
Cb48ca5059faf7409a5ab3745a964696?d=identicon&s=25 unknown (Guest)
on 2007-02-22 16:07
(Received via mailing list)
On Thu, 22 Feb 2007, Bob Hutchison wrote:

> I've worked in systems requiring temporal and interval logics for years.
> Here is something I can pretty much guarantee: if you don't get your
> terminology right you are going to spend almost all of your time trying to
> figure out what each other is saying. Allen's terminology is described and
> illustrated on page 10 of the paper:
<snip>
> You know, this probably is worth writing up as a trivial library and
> sharing... but how to represent an interval :-)

indeed.  if people are looking fo a concrete example of why these
definitions
are important, including some nice confusing examples, see

   http://codeforpeople.com/lib/ruby/btpgsql/btpgsql-0.2.4/doc/

regards.

-a
Cd3312ac93f768b1b449af457c0fca06?d=identicon&s=25 Daniel Finnie (Guest)
on 2007-02-22 20:51
(Received via mailing list)
I have made some tests for the code and shown the results at
http://pastie.caboo.se/42266 .  Please check the assertions with # I
assume by them, the paper referenced went way over my head.

Dan
E3c79c779c0b390049289cdfe7cb9705?d=identicon&s=25 Bob Hutchison (Guest)
on 2007-02-22 23:36
(Received via mailing list)
Hi,

On 22-Feb-07, at 2:51 PM, Daniel Finnie wrote:

> I have made some tests for the code and shown the results at http://
> pastie.caboo.se/42266 .  Please check the assertions with # I
> assume by them, the paper referenced went way over my head.
>
> Dan

I modified your stuff and changed the tests around a bit. I don't
know, maybe it'll help, maybe it won't. I'm not sure how to use the
pastie thing, so I've just appended the code.

Cheers,
Bob

----
Bob Hutchison                  -- blogs at <http://www.recursive.ca/
hutch/>
Recursive Design Inc.          -- <http://www.recursive.ca/>
Raconteur                      -- <http://www.raconteur.info/>
xampl for Ruby                 -- <http://rubyforge.org/projects/xampl/>



## These are the tests and the code from P-C David
class Range
   # self:   |---|
   # other:         |---|
   def before?(other)
     self.end < other.begin
   end

   # self:          |---|
   # other:  |---|
   def after?(other)
     other.before?(self)
   end

   # self:  |---|
   # other:     |---|
   def meets?(other)
     self.end == other.begin
   end

   # self:      |---|
   # other: |---|
   def met_by?(other)
     other.meets?(self)
   end

   # self:  |---|
   # other:   |---|
   def overlaps?(other)
     (self.begin < other.begin) and
     (other.begin < self.end) and
     (self.end < other.end)
   end

   # self:    |---|
   # other: |---|
   def overlapped_by?(other)
     other.overlaps?(self)
   end

   # self:  |---|
   # other: |-----|
   def starts?(other)
     (self.begin == other.begin) and
     (self.end < other.end)
   end

   # self:  |-----|
   # other: |---|
   def started_by?(other)
     other.starts?(self)
   end

   # self:    |---|
   # other: |-----|
   def finishes?(other)
     (self.end == other.end) and
     (other.begin < self.begin)
   end

   # self:  |-----|
   # other:   |---|
   def finished_by?(other)
     other.finishes?(self)
   end

   # self:     |---|
   # other:  |-------|
   def during?(other)
     (other.begin < self.begin) and
     (self.end < other.end)
   end

   # self:  |-------|
   # other:   |---|
   def contains?(other)
     other.during?(self)
   end

   # self:   |---|
   # other:  |---|
   def equals?(other)
     (self.begin == other.begin) and
     (self.end == other.end)
   end

   def disjoint?(other)
     (self.end <= other.begin) or
     (other.end <= self.begin)
   end

end

if $0 == __FILE__
   require 'test/unit'

   class TestRange < Test::Unit::TestCase
     def determine(a, b)
       m = a.match(/([\. ]*)([^\. ]*)/)
       interval1 = (1 + $1.length)..($1.length + $2.length)

       m = b.match(/([\. ]*)([^\. ]*)/)
       interval2 = (1 + $1.length)..($1.length + $2.length)

       result = []

       result << :before if interval1.before?(interval2)
       result << :after if interval1.after?(interval2)
       result << :meets if interval1.meets?(interval2)
       result << :met_by if interval1.met_by?(interval2)
       result << :overlaps if interval1.overlaps?(interval2)
       result << :overlapped_by if interval1.overlapped_by?(interval2)
       result << :starts if interval1.starts?(interval2)
       result << :started_by if interval1.started_by?(interval2)
       result << :finishes if interval1.finishes?(interval2)
       result << :finished_by if interval1.finished_by?(interval2)
       result << :during if interval1.during?(interval2)
       result << :contains if interval1.contains?(interval2)
       result << :equals if interval1.equals?(interval2)
       result << :disjoint if interval1.disjoint?(interval2)

       puts "[#{interval1}] [#{interval2}] --> #{result.inspect}"

       return result
     end

     def test_intervals
       assert (determine("111........",
                         "....222....") - [:before, :disjoint]).empty?
       assert (determine("11111......",
                         "....222....") - [:meets, :disjoint]).empty?
       assert (determine("111111......",
                         "....222....") - [:overlaps]).empty?
       assert (determine("1111111....",
                         "....222....") - [:finished_by]).empty?
       assert (determine("....111....",
                         "2222222....") - [:finishes]).empty?
       assert (determine("11111111111",
                         "....222....") - [:contains]).empty?
       assert (determine("....111....",
                         "22222222222") - [:during]).empty?
       assert (determine("....111....",
                         "....222....") - [:equals]).empty?
       assert (determine("....11.....",
                         "....222....") - [:starts]).empty?
       assert (determine("....1111111",
                         "....222....") - [:started_by]).empty?
       assert (determine(".....111111",
                         "....222....") - [:overlapped_by]).empty?
       assert (determine("......11111",
                         "....222....") - [:met_by, :disjoint]).empty?
       assert (determine("........111",
                         "....222....") - [:after, :disjoint]).empty?
     end
   end
end
This topic is locked and can not be replied to.