Asp Forum - [Facets] Range#overlap?

Daniel Schierbeck

2/20/2007 12:08:00 AM

(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-w...

21 Answers

Daniel Finnie

2/20/2007 1:56:00 AM

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)

> (I'm sending this to the list because I think it has general interest.<BR>> 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-ove...
> ranges
>
>

Daniel Schierbeck

2/20/2007 1:02:00 PM

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

Daniel Finnie

2/20/2007 1:48:00 PM

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

Daniel Schierbeck wrote:
> 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
>
>
>

Daniel Schierbeck

2/20/2007 8:34:00 PM

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

dblack

2/20/2007 10:59:00 PM

Daniel Finnie

2/20/2007 11:01:00 PM

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

Daniel Schierbeck wrote:
> 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
>
>
>

Daniel Schierbeck

2/20/2007 11:46:00 PM

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

Daniel Finnie

2/20/2007 11:54:00 PM

Which is, IMHO, correct:
>> (4..8).include? 8.5
=> false
>> (6...9).include? 8.5
=> true

Dan

Daniel Schierbeck wrote:
> 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
>
>
>

dblack

2/21/2007 12:05:00 AM

Bernard Kenik

2/21/2007 2:42:00 AM

On Feb 20, 7:04 pm, dbl...@wobblini.net wrote:
> Hi --
>
>
>
>
>
> On Wed, 21 Feb 2007, Daniel Schierbeck wrote:
> > 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 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
>
> --
> Q. What is THE Ruby book for Rails developers?
> A. RUBY FOR RAILS by David A. Black (http://www.manning...)
> (See what readers are saying! http://www.r.../r...)
> Q. Where can I get Ruby/Rails on-site training, consulting, coaching?
> A. Ruby Power and Light, LLC (http://www.r...)- 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>

comp.lang.ruby

[Facets] Range#overlap?

Daniel Schierbeck

Daniel Finnie

Daniel Schierbeck

Daniel Finnie

Daniel Schierbeck

dblack

Daniel Finnie

Daniel Schierbeck

Daniel Finnie

dblack

Bernard Kenik

x Login to ForumsZone