CODEWITHSUNDEEP
ruby-on-railsruby
Matías Hernán García
Matías Hernán García

Reputation: 241

Range doesn't conflict with other ranges

So I have to make a rails validation that handles the following situation:

I have a set of ranges, and I need to know if the asked range has a conflict with any of these ranges at all.

For example, I have the following ranges:

The only thing I have achieved is the first and easiest case with this line:

def is_not_conflictive_range?
  ranges = ServicePrice.where(property: self.property).pluck(:from_value, :to_value).map { |range| range.first..range.second }
  conflictive_range = ranges.find do |range|
     range.include? (self.from_value..self.to_value)
  end
  errors.add(:service_price, "range from #{self.from_value} to #{self.to_value} is including in existing range from #{conflictive_range.first} to #{conflictive_range.last}") if conflictive_range
end

But I can't really figure out how to handle the other cases in a simple way.

Upvotes: 4

Views: 167

Answers (5)

Alejandro Babio
Alejandro Babio

Reputation: 5229

I do this in plain ruby. (Edited: thanks for the help of Cary Swoveland)

First, define a conflict? method that show if 2 ranges are overlaped (this can be do at model level)

class Range
  def conflict?(other)
    self.begin < other.end && self.end > other.begin
  end
end

Then I define an invalid_range method that returns true if the range is invalid for the set:

def invalid_range(range, set)
  set.any? {|s| s.conflict?(range)}
end

Verify with user data:

set = [(0..3000), (3000..4000), (4000..5000), (6000..7000)]

cases = [(1..10), (1..3100), (2800..4500), (5000..6000)]

# verifying:
cases.each {|c| puts "testing range: #{c} on set result: #{invalid_range(c,set)}"}

Output of cases.each ...

testing range: 1..10 on set result: true
testing range: 1..3100 on set result: true
testing range: 2800..4500 on set result: true
testing range: 5000..6000 on set result: false

If you like this approach, I think you can modify your models to do the same. If you have problems with this, please publish your models and I help you.

I hope it helps.

Edited: change invalid for invalid_range because it isn't AR compatible.

Upvotes: 0

Cary Swoveland
Cary Swoveland

Reputation: 110675

This is one of those questions that's straightforward when viewed the right way, but otherwise messy and complex. After a couple of false starts I addressed the question, "how can an overlap be avoided?

I have assumed that the ranges in the array are ordered in the sense that the end of each range is not greater than the start of the next and the start of each range is not less than the end of previous. This is what you have in your example. If that condition does not hold, the first step would be to modify the array so that this condition holds, which would not be difficult.

Code

def no_overlap?(arr, range)
  range.last  <= arr.first.first ||
  range.first >= arr.last.last   ||
  arr.each_cons(2).any? { |r1,r2|
    range.first >= r1.last && range.last <= r2.first }
end

Examples

arr = [1000..3000, 3000..4000, 4000..4000, 4000..5000, 6000..7000]

no_overlap?(arr,    1..1010) #=> false
no_overlap?(arr, 2800..4500) #=> false
no_overlap?(arr, 2500..5500) #=> false
no_overlap?(arr, 5000..6000) #=> true
no_overlap?(arr,    0..500)  #=> true
no_overlap?(arr, 8000..9000) #=> true

Upvotes: 1

Harsh Gupta
Harsh Gupta

Reputation: 4538

We don't need to check for inclusion of ranges in Ruby, just check the boundaries.

def valid_range?
  ranges = ServicePrice.where(property: self.property).pluck(:from_value, :to_value).map { |range| [range.first, range.second] }

  conflict = nil
  conflict = ranges.map do |min, max|
    [
      self.from_value > min && self.from_value < max,
      self.to_value > min && self.to_value < max
    ].any?
  end.index(true)

  errors.add(:service_price, "range from #{self.from_value} to #{self.to_value} is including in existing range from #{ranges[conflict].first} to #{ranges[conflict].last}") unless conflict.blank?
end

I think I have covered all the possible cases, but not sure at the moment.

Upvotes: 0

Doguita
Doguita

Reputation: 15703

You need to check:

  • If the first number of the range is included in any range;
  • If the last number of the range is included in any range;
  • If any range is included itself in the selected range.

So, you can change your code to: 

conflictive_range = ranges.find_all do |range|
  range.include?(self.from_value) ||
  range.include?(self.to_value) ||
  (range.first > self.from_value && range.last < self.to_value)
end

And as I commented 5000..6000 will be in conflict because there is a range with 5000 and other with 6000.

Upvotes: 0

davegson
davegson

Reputation: 8331

First off, I'd rename the function to something more readable. I chose valid_range.

You came pretty close with your code, my end result is:

def valid_range?
  ranges = ServicePrice.where(property: self.property).pluck(:from_value, :to_value).map { |range| range.first..range.second }

  ranges.each do |range|
    # check if either values are part of the range
    if range.include?(from_value) || range.include?(to_value)
      # invalid, so return false
      return false
    end
  end

  # if it 'survived' the loop return true
  return true
end

So it loops through all existing loops and returns false on an error.

Though with this your currently existing ranges aren't valid since 4000..5000 is part of the 3000..4000 range.

A solution to this would be to use ranges with three dots instead. So adjust the map part to

.map { |range| range.first...range.second }

Upvotes: 0

Related Questions