Adding intervals to an interval store

Question

Write a program to do addition of intervals to an interval store.

An interval is represented by an array of two elements - the lower and the upper bound (you can assume integers). Assume that intervals are constructed properly (e.g. the lower bound is not greater than the upper bound, etc.).

Implement the #add method that will add a new interval, handling the merges properly.

Example:

> store = IntervalStore.new
[]
> store.add(1, 2)
[[1, 2]]
> store.add(5, 6)
[[1, 2], [5, 6]]
> store.add(1, 4)
[[1, 4], [5, 6]]
> store.add(1, 2)
[[1, 4], [5, 6]]
> store.add(3, 5)
[[1, 6]]
> store.add(0, 7)
[[0, 7]]

Here is my Python code. It works but is not perfect.

class IntervalStore(object):
    def __init__(self):
        self.store = []

    def filter_result(self, flatten_store, low_index, upp_index):
        useless_values = filter(lambda value: low_index < flatten_store.index(value) < upp_index, flatten_store)
        flatten_store = filter(lambda value: value not in useless_values, flatten_store)
        self.store = []
        for i, k in zip(flatten_store[0::2], flatten_store[1::2]):
            self.store.append([i, k])

    def add(self, low, upp):
        flatten_store = [number for pair in self.store for number in pair]
        low_index, upp_index = self.index_of(low, flatten_store), self.index_of(upp, flatten_store)

        if low_index >= 0 and upp_index >= 0:
            if low_index % 2 != 0:
                low_index -= 1
            if upp_index % 2 == 0:
                upp_index += 1
        elif low_index >= 0 > upp_index:
            if low_index % 2 != 0:
                low_index -= 1
            flatten_store.append(upp)
            flatten_store = sorted(flatten_store)
            upp_index = self.index_of(upp, flatten_store)
            if upp_index % 2 != 0:
                upp_index += 1
        elif low_index < 0 <= upp_index:
            if upp_index % 2 == 0:
                upp_index += 1
            flatten_store.append(low)
            flatten_store = sorted(flatten_store)
            low_index = self.index_of(low, flatten_store)
            if low_index % 2 != 0:
                low_index -= 1
            upp_index += 1
        else:
            flatten_store.append(low)
            flatten_store.append(upp)
            flatten_store = sorted(flatten_store)
            low_index, upp_index = self.index_of(low, flatten_store), self.index_of(upp, flatten_store)

            if low_index % 2 != 0:
                low_index -= 1
            if upp_index % 2 == 0:
                upp_index += 1
        self.filter_result(flatten_store, low_index, upp_index)

    def index_of(self, value, list):
        try:
            return list.index(value)
        except ValueError:
            return -1

same as Ruby code:

class IntervalStore

  def initialize
    @store = []
  end

  def to_s
    "[#{@store.map{ |i| "[#{i.first}, #{i.last}]" }.join(', ')}]"
  end

  # TODO - implement this method
  def add(low, upp)
    flatten_store = @store.flatten

    low_index, upp_index = flatten_store.index(low), flatten_store.index(upp)
    if low_index and upp_index
      low_index -=1 if low_index.odd?
      upp_index +=1 if upp_index.even?
    elsif low_index and !upp_index
      low_index -= 1 if low_index.odd?
      (flatten_store << upp).sort!
      upp_index = flatten_store.index(upp)
      upp_index += 1 if upp_index.odd?
    elsif !low_index and upp_index
      upp_index += 1 if upp_index.even?
      (flatten_store << low).sort!
      low_index = flatten_store.index(low)
      low_index -= 1 if low_index.odd?
      upp_index += 1
    else
      (flatten_store << low << upp).sort!
      low_index, upp_index = flatten_store.index(low), flatten_store.index(upp)

      low_index -= 1 if low_index.odd?
      upp_index += 1 if upp_index.even?
    end

    filter_result = filter_store(flatten_store, low_index, upp_index)
    format_result(filter_result)
  end

  def format_result(rest)
    @store = []
    rest.each_slice(2) { |pair_values| @store << pair_values }
    @store
  end

  def filter_store(flatten_store, low_index, upp_index)
    flatten_store.clone.delete_if do |value|
      flatten_store_index = flatten_store.index(value)
      low_index < flatten_store_index and flatten_store_index < upp_index
    end
  end
end

I want to know how you would do it in other ways to make it smarter.

Answer 1

Others have suggested different strategies, I'll comment on your code:

Meaningful naming
low and upp are abbreviations, which are rather ambiguous. Better call them lower_limit and upper_limit. The name of the method (add) adds to the confusion, since it is not apparent what exactly are you adding. add_interval is more descriptive.

Method names should be actions (add_XXX, format_XXX, filter_XXX), but variable names should be nouns (flattened_store instead of flatten_store). This is especially important in ruby, where the same syntax might either call a method or refer to a local variable.

Make your code human-readable
The innards of your add method are quite 'magic'. For the casual reader there is no way to understand why what you do there works. A lot of .odd?s and .even?s, and += 1 and -= 1 with no rhyme or reason.
Build your solution in a way that a reader who is not familiar with it will understand what you are trying to do. Otherwise, she won't be able to maintain your code when needed. You won't be able to maintain it to in a couple of months, or even weeks.
Break it up to meaningful helper methods. Try to keep meaningful structures (if you are concerned with whether the ID is odd or even, maybe a better solution will not include flattening the store in the first place?).
If you find that you are still left with unintelligible code (and only as a last resort!) a couple of comments explaining what you are doing and why may be very helpful.

Redundant logic

• Your to_s method is totally redundant, as @store.to_s will result in exactly the same string.

• format_result could be simplified to

  def format_result(rest)
    @store = rest.each_slice(2).to_a
  end
  

• .clone.delete_if could be simplified to .reject.

• filter_store as a whole could be simplified to

  def filter_store(flatten_store, low_index, upp_index)
    flatten_store[0..low_index] + flatten_store[high_index..-1]
  end
  

# TODO - implement this method
I guess you already did that - you can safely delete the comment.

Answer 2

If you have range [a,b], and want to add a range [c,d], there are 6 possible scenarios if you make the assumption, a < b, c < d

b < c - undershoot
a < c, b >= c, b <= d - left overlap
a <= c, b >= d - total overlap
a >= c, b <= d - subsection
a > c, b > d - right overlap
a > d - overshoot

The first and the last cases simply add a new range, while left/right/total overlap edit the current range... and subsection can be ignored.

My solution is to edit the function add, such that it follows this algorithm:

• 1 - look at all ranges
• 2 - if subsection found return
• 3 - if left/right/total overlap found remove the current range being evaluated from the range list, merge the two ranges, then call add with the larger range.
• 4 - if ends up being an over/under shoot for all ranges, add the range

class IntervalStore(object):
    def __init__(self):
        self.range_list = []
    def __str__(self):
        return str(self.range_list)

    def __repr__(self):
        return str(self)

    def add(self, low, high):
        for interval in self.range_list:
            if interval[0] <= low and interval[1] >= high:
                return
            if interval[0] > high or interval[1] < low:
                continue
            else:
                self.range_list.remove(interval)
                self.add(min([interval[0], low]), max([interval[1], high]))
                return
        if len(self.range_list) == 0:
            self.range_list.append( [low, high])
        else:
            insert_index = 0
            while insert_index < len(self.range_list) and high > self.range_list[insert_index][0]:
                insert_index += 1
            self.range_list.insert(insert_index, [low, high])

EDIT If you wanted to avoid an error regarding low > high input, then add low, high = sorted([low,high]) at the beginning of the add function.

Also add if low == high: return

Answer 3

I'll stick to the ruby code, as python isn't my strong suit. But I imagine it wouldn't take much to make the approach below more pythonic.

There is a lot going on that #add method. A lot more than there needs to be. I'd create a more specific Interval class to go along with IntervalStore.

I'd subclass Range to model the intervals, and give that subclass some methods that let's it check for overlaps and performs the merging. Subclassing Array is also an option, but Range has a couple of useful methods already, and besides, it's defined by its upper and lower bounds - like an interval. Only thing to note is that Range objects are immutable, so any merging will have to return a new instance, rather than modify an existing one.

This will make the IntervalStore class a lot simpler, now that can deal with objects that know what they are.

For there, the steps when adding a new interval are:

1. Appending: Push the interval to the internal array
2. Sorting: Sort the array
3. Coalescing: Loop through and check if two consecutive intervals can be merged into one

Based on all that, I get this Interval class:

class Interval < Range
  # Check if another interval overlaps this one
  def overlap?(other)
    cover?(other.min) || cover?(other.max)
  end

  # Return a new Interval by merging this one with another
  def merge(other)
    Interval.new([min, other.min].min, [max, other.max].max)
  end

  # Simplified array representation
  def to_a
    [min, max]
  end
end

And for IntervalStore:

class IntervalStore
  def initialize
    @intervals = []
  end

  def add(min, max)
    @intervals.push(Interval.new(min, max))
    @intervals.sort_by!(&:min)
    @intervals = @intervals.inject([]) do |merged, interval|
      if merged.any? && merged.last.overlap?(interval)
        merged << merged.pop.merge(interval)
      else
        merged << interval
      end
    end
  end

  # Returns an array representation
  def to_a
    @intervals.map(&:to_a)
  end
end

And bingo.

---

Update: If you want a solution that's true to the very letter of the task, here's one:

class IntervalStore < Array
  def initialize
    super
  end

  def add(low, high)
    push([low, high])
    sort_by!(&:first)
    collapse
  end

  private

  def collapse
    collapsed = inject([]) do |merged, interval|
      can_merge = merged.any? && overlap?(merged.last, interval)
      merged << (can_merge ? merge(merged.pop, interval) : interval)
    end
    clear.concat(collapsed)
  end

  def overlap?(a, b)
    a = Range.new(*a) # just for the `cover?` method
    a.cover?(b.first) || a.cover?(b.last)
  end

  def merge(a, b)
    [ [a.first, b.first].min , [a.last, b.last].max ]
  end
end

Personally, I don't like it quite as much, apart from its conciseness. I'm subclassing Array to have IntervalStore exactly match the "output" in the task (just for the heck of it), but I wouldn't recommend that - it's an array now, so if you call, say, flatten! on it, everything screws up. The class now also contains a few non-OOPish functions that don't operate on self in any way.

But all that aside, the point is that you literally get this:

store = IntervalStore.new # => []
store.add(1, 2) # => [[1, 2]]
store.add(5, 6) # => [[1, 2], [5, 6]]
store.add(1, 4) # => [[1, 4], [5, 6]]
store.add(1, 2) # => [[1, 4], [5, 6]]
store.add(3, 5) # => [[1, 6]]
store.add(0, 7) # => [[0, 7]]

Answer 4

Here is another way of doing it. (I have omitted comments on your code because I have nothing to add to @Uri's excellent answer.)

Code

First define an Interval class. This allows us to keep intervals as single objects in the main class, without having to fuss much with end points of intervals.

class Interval
  attr_reader :left, :right

  def initialize(left,right)
    @left = left
    @right = right
  end

  # Is self entirely to the left of other?
  def < (other)
    self.right < other.left
  end

  # Is self entirely to the right of other?
  def > (other)
    self.left > other.right
  end

  # Return the lessor of the left end of self and the left end of other
  def left_most(other)
    [self.left, other.left].min
  end 

  # Return the greater of the right end of self and the right end of other
  def right_most(other)
    [self.right, other.right].max
  end

  # How intervals are to be displayed  
  def inspect
    "#{self.left}..#{self.right}"
  end
end

The main class:

class IntervalStore
  attr_reader :intervals

  def initialize
    # Array to hold Interval objects
    @intervals = []
  end

  def add(left, right)
    # Create an Interval object 
    interval_to_add = Interval.new(left,right)

    if @intervals.empty?
       @intervals = [interval_to_add]
      return
    end

    # intervals in @intervals entirely to the left of interval_to_add
    before = @intervals.find_all {|i| i < interval_to_add }
    # intervals in @intervals entirely to the right of interval_to_add
    after  = @intervals.find_all {|i| i > interval_to_add }

    # We will replace all intervals between the before and after
    # intervals (if any) with an interval new_interval

    if  ([email protected] || [email protected])
      # Case where all intervals are to the left of interval_to_add or to the
      # right of interval_to_add
      new_interval = interval_to_add
    else
      # before.size is the offset of the left-most interval in @intervals
      # that is not in before
      # @intervals.size-after.size-1 is the offset of the right-most
      # interval in @intervals that is not in after
      new_interval = Interval.new(interval_to_add.left_most(@intervals[before.size]),
        interval_to_add.right_most(@intervals[@intervals.size-after.size-1]))
    end
    @intervals = before + [new_interval] + after
  end
end

Notice that this approach keeps the intervals in sorted order.

Example

is = IntervalStore.new
is.add(2 , 5) #=> [2..5]
is.add(6 , 8) #=> [2..5, 6..8]
is.add(8 ,10) #=> [2..5, 6..10]
is.add(0 , 1) #=> [0..1, 2..5, 6..10]
is.add(1 , 7) #=> [0..10]
is.add(0 , 1) #=> [0..10]
is.add(1 ,11) #=> [0..11]
is.add(-1,10) #=> [-1..11]
is.add(-2,12) #=> [-2..12]