class Antlr4::Runtime::IntervalSet

Attributes

intervals[RW]

Public Class Methods

new(a = nil, b = nil) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 8
def initialize(a = nil, b = nil)
  @readonly = false
  @intervals = []
  add(a, b) unless a.nil?
end
of(a, b = nil) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 14
def self.of(a, b = nil)
  if b.nil?
    IntervalSet.new(a)
  else
    IntervalSet.new(a, b)
  end
end
or_sets(sets) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 81
def self.or_sets(sets)
  r = IntervalSet.new
  i = 0
  while i < sets.length
    r.add_all(sets[i])
    i += 1
  end
  r
end

Public Instance Methods

==(obj) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 310
def ==(obj)
  return false if obj.nil? || !(obj.is_a? IntervalSet)

  other = obj
  @intervals == other.intervals
end
add(el1, el2 = nil) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 28
def add(el1, el2 = nil)
  raise IllegalStateException, "can't alter readonly IntervalSet" if @readonly

  if el1.is_a? Interval
    add_interval(el1)
  elsif el1.is_a? IntervalSet
    add_all(el1)
  elsif el2.nil?
    add_interval(Interval.of(el1, el1))
  else
    add_interval(Interval.of(el1, el2))
  end
end
add_all(set) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 91
def add_all(set)
  return this if set.nil?

  if set.is_a? IntervalSet
    other = set

    n = other.intervals.length
    i = 0
    while i < n
      interval = other.intervals[i]
      add(interval.a, interval.b)
      i += 1
    end
  end

  self
end
add_interval(addition) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 42
def add_interval(addition)
  raise IllegalStateException, "can't alter readonly IntervalSet" if @readonly

  return if addition.b < addition.a

  # Find where to insert the Interval and remember where it went

  i = 0 # An index into @intervals
  while i < @intervals.length
    r = @intervals[i]
    return if addition == r

    if addition.adjacent(r) || !addition.disjoint(r)
      bigger = addition.union(r)
      @intervals[i] = bigger

      while i < (@intervals.length - 1)
        i += 1
        next_interval = @intervals[i]
        if !bigger.adjacent(next_interval) && bigger.disjoint(next_interval)
          break
        end

        @intervals.delete_at i
        i -= 1
        @intervals[i] = bigger.union(next_interval)
      end
      return
    end

    if addition.starts_before_disjoint r
      @intervals.insert(i, addition)
      return
    end
    i += 1
  end
  @intervals << addition
end
and(other) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 197
def and(other)
  if other.nil? # || !(other.is_a? IntervalSet) )
    return nil # nothing in common with nil set
  end

  my_intervals = @intervals
  their_intervals = other.intervals
  intersection = nil
  my_size = my_intervals.length
  their_size = their_intervals.length
  i = 0
  j = 0

  while i < my_size && j < their_size
    mine = my_intervals[i]
    theirs = their_intervals[j]
    # System.out.println("mine="+mine+" and theirs="+theirs)
    if mine.starts_before_disjoint(theirs)
      # move this iterator looking for interval that might overlap
      i += 1
    elsif theirs.starts_before_disjoint(mine)
      # move other iterator looking for interval that might overlap
      j += 1
    elsif mine.properlyContains(theirs)
      # overlap, add intersection, get next theirs
      intersection = IntervalSet.new if intersection.nil?
      intersection.add(mine.intersection(theirs))
      j += 1
    elsif theirs.properlyContains(mine)
      # overlap, add intersection, get next mine
      intersection = IntervalSet.new if intersection.nil?
      intersection.add(mine.intersection(theirs))
      i += 1
    elsif !mine.disjoint(theirs)
      # overlap, add intersection
      intersection = IntervalSet.new if intersection.nil?
      intersection.add(mine.intersection(theirs))
      # Move the iterator of lower range [a..b], but not
      # the upper range as it may contain elements that will collide
      # with the next iterator. So, if mine=[0..115] and
      # theirs=[115..200], then intersection is 115 and move mine
      # but not theirs as theirs may collide with the next range
      # in thisIter.
      # move both iterators to next ranges
      if mine.startsAfterNonDisjoint(theirs)
        j += 1
      elsif theirs.startsAfterNonDisjoint(mine)
        i += 1
      end
    end
  end
  return IntervalSet.new if intersection.nil?

  intersection
end
clear() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 22
def clear
  raise IllegalStateException, "can't alter readonly IntervalSet" if @readonly

  @intervals.clear
end
complement(min_element, max_element) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 109
def complement(min_element, max_element)
  complement_interval_set(IntervalSet.of(min_element, max_element))
end
complement_interval_set(intervalSet) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 113
def complement_interval_set(intervalSet)
  if intervalSet.nil? || intervalSet.is_nil
    return nil # nothing in common with nil set
  end

  if intervalSet.is_a? IntervalSet
    intervalSet.subtract(self)
  end

end
contains(el) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 253
def contains(el)
  n = @intervals.length
  l = 0
  r = n - 1
  # Binary search for the element in the (sorted,
  # disjoint) array of @intervals.
  while l <= r
    m = (l + r) / 2
    interval = @intervals[m]
    a = interval.a
    b = interval.b
    if b < el
      l = m + 1
    elsif a > el
      r = m - 1
    else # el >= a && el <= b
      return true
    end
  end
  false
end
element_name_in_vocabulary(vocabulary, a) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 377
def element_name_in_vocabulary(vocabulary, a)
  if a == Token::EOF
    '<EOF>'
  elsif a == Token::EPSILON
    '<EPSILON>'
  else
    vocabulary.display_name(a)
  end
end
hash() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 292
def hash
  ints = @intervals.each_with_object([]) do |interval, ret|
    ret << interval.a
    ret << interval.b
  end

  hash_code = RumourHash.calculate(ints)

  unless @_hash.nil?
    if hash_code == @_hash
      puts 'Same hash_code for IntervalSet'
    else
      puts 'Different hash_code for IntervalSet'
    end
  end
  @_hash = hash_code
end
is_nil() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 275
def is_nil
  @intervals.nil? || @intervals.empty?
end
max_element() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 279
def max_element
  raise StandardEror, 'set is empty' if is_nil

  last = @intervals[-1]
  last.b
end
min_element() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 286
def min_element
  raise StandardEror, 'set is empty' if is_nil

  @intervals[0].a
end
or(a) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 190
def or(a)
  o = IntervalSet.new
  o.add_all(self)
  o.add_all(a)
  o
end
readonly(readonly) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 484
def readonly(readonly)
  if @readonly && !readonly
    raise IllegalStateException, "can't alter readonly IntervalSet"
  end

  @readonly = readonly
end
remove(el) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 446
def remove(el)
  raise IllegalStateException, "can't alter readonly IntervalSet" if @readonly

  n = @intervals.length
  i = 0
  while i < n
    interval = @intervals[i]
    a = interval.a
    b = interval.b
    if el < a
      break # list is sorted and el is before this interval not here
    end

    # if whole interval x..x, rm
    if el == a && el == b
      @intervals.delete_at(i)
      break
    end
    # if on left edge x..b, adjust left
    if el == a
      interval.a += 1
      break
    end
    # if on right edge a..x, adjust right
    if el == b
      interval.b -= 1
      break
    end
    # if in middle a..x..b, split interval
    if el > a && el < b # found in this interval
      oldb = interval.b
      interval.b = el - 1 # [a..x-1]
      add(el + 1, oldb) # add [x+1..b]
    end
    i += 1
  end
end
size() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 387
def size
  n = 0
  num_intervals = @intervals.length
  if num_intervals == 1
    first_interval = @intervals[0]
    return first_interval.b - first_interval.a + 1
  end
  i = 0
  while i < num_intervals
    interval = @intervals[i]
    n += (interval.b - interval.a + 1)
    i += 1
  end
  n
end
subtract(a) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 124
def subtract(a)
  return IntervalSet.new self if a.nil? || a.is_nil

  subtract_interval_sets(self, a)
end
subtract_interval_sets(left, right) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 130
def subtract_interval_sets(left, right)
  return new IntervalSet if left.nil? || left.is_nil

  result = IntervalSet.new(left)
  return result if right.nil? || right.is_nil

  result_i = 0
  right_i = 0
  while result_i < result.intervals.length && right_i < right.intervals.length
    result_interval = result.intervals[result_i]
    right_interval = right.intervals[right_i]

    if right_interval.b < result_interval.a
      right_i += 1
      next
    end

    if right_interval.a > result_interval.b
      result_i += 1
      next
    end

    before_current = nil
    after_current = nil
    if right_interval.a > result_interval.a
      before_current = Interval.new(result_interval.a, right_interval.a - 1)
    end

    if right_interval.b < result_interval.b
      after_current = Interval.new(right_interval.b + 1, result_interval.b)
    end

    if !before_current.nil?
      if !after_current.nil?
        # split the current interval into two
        result.intervals[result_i] = before_current
        result.intervals[result_i + 1] = after_current
        result_i += 1
        right_i += 1
        next
      else # replace the current interval
        result.intervals[result_i] = before_current
        result_i += 1
        next
      end
    else
      if !after_current.nil?
        result.intervals[result_i] = after_current
        right_i += 1
        next
      else
        result.intervals.delete_at(result_i)
        next
      end
    end
  end

  result
end
to_a() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 442
def to_a
  to_integer_list
end
to_integer_list() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 403
def to_integer_list
  values = []
  n = @intervals.length
  i = 0
  while i < n
    interval = @intervals[i]
    a = interval.a
    b = interval.b
    v = a
    while v <= b
      values.push(v)
      v += 1
    end
    i += 1
  end
  values
end
to_list() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 421
def to_list
  to_integer_list
end
to_set() click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 425
def to_set
  s = Set.new
  k = 0
  while k < @intervals.length
    i = @intervals[k]
    a = i.a
    b = i.b
    v = a
    while v <= b
      s.add(v)
      v += 1
    end
    k += 1
  end
  s
end
to_string(elem_are_char = false) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 317
def to_string(elem_are_char = false)
  buf = ''
  return 'end' if @intervals.nil? || @intervals.empty?

  buf << '' if size > 1

  i = 0
  while i < @intervals.length
    interval = @intervals[i]
    a = interval.a
    b = interval.b
    if a == b
      if a == Token::EOF
        buf << '<EOF>'
      elsif elem_are_char
        buf << "'" << a << "'"
      else
        buf << a
      end
    else
      if elem_are_char
        buf << "'" << a << "'..'" << b << "'"
      else
        buf << a << '..' << b
      end
    end
    buf << ', ' if i < @intervals.length
    i += 1
  end
  buf << 'end' if size > 1
  buf
end
to_string_from_vocabulary(vocabulary) click to toggle source
# File lib/antlr4/runtime/interval_set.rb, line 350
def to_string_from_vocabulary(vocabulary)
  buf = '{'
  return '{end}' if @intervals.nil? || @intervals.empty?

  buf << '' if size > 1
  i = 0
  while i < @intervals.length
    interval = @intervals[i]
    a = interval.a
    b = interval.b
    if a == b
      buf << element_name_in_vocabulary(vocabulary, a)
    else
      j = a
      while j <= b
        buf << ', ' if j > a
        buf << element_name_in_vocabulary(vocabulary, j)
        j += 1
      end
    end
    buf << ', ' if i < (@intervals.length - 1)
    i += 1
  end
  buf << '}' if size > 1
  buf
end