Range#overlap?


#1

(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-overlap-with-ranges

#2

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 S.
Date: Monday, February 19, 2007 7:08 pm
Subject: [Facets] Range#overlap?
To: removed_email_address@domain.invalid (ruby-talk ML)


#3

On Tue, 2007-02-20 at 10:56 +0900, removed_email_address@domain.invalid 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 :wink:

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


#4

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


#5

Hi –

On Wed, 21 Feb 2007, Daniel S. 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


#6

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


#7

On Tue, 2007-02-20 at 22:47 +0900, Daniel F. 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


#8

On Wed, 2007-02-21 at 08:00 +0900, Daniel F. 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? :wink:

Cheers,
Daniel


#9

Which is, IMHO, correct:

(4…8).include? 8.5
=> false

(6…9).include? 8.5
=> true

Dan


#10

Hi –

On Wed, 21 Feb 2007, Daniel S. 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


#11

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?


#12

On Feb 20, 7:04 pm, removed_email_address@domain.invalid 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?

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


#13

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

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


#14

On Wed, 21 Feb 2007, Gregory B. 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


#15

On 2/20/07, Suraj K. removed_email_address@domain.invalid wrote:

within? means subset?

These are much better names, I think. Of course, it’ll only be so if
you are mathematically inclined.


#16

On Wed, 2007-02-21 at 09:04 +0900, removed_email_address@domain.invalid 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 F. 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


#17

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


#18

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 S. wrote:

Daniel F. 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


#19

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 D. 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 F. 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 :slight_smile:

Cheers,
Bob


Bob H. – 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/


#20

On Thu, 22 Feb 2007, Bob H. 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:

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

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