text: # Copyright 2013 The Chromium Authors. All rights reserved.
  # Use of this source code is governed by a BSD-style license that can be
  # found in the LICENSE file.
  
  import os
  import sys
  
  _BASE_PATH = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
  _BINTREES_PATH = os.path.join(
      _BASE_PATH, os.pardir, os.pardir, 'third_party', 'bintrees')
  sys.path.insert(0, _BINTREES_PATH)
  
  from bintrees import FastRBTree  # pylint: disable=F0401
  
  
  class ExclusiveRangeDict(object):
    """A class like dict whose key is a range [begin, end) of integers.
  
    It has an attribute for each range of integers, for example:
    [10, 20) => Attribute(0),
    [20, 40) => Attribute(1),
    [40, 50) => Attribute(2),
    ...
  
    An instance of this class is accessed only via iter_range(begin, end).
    The instance is accessed as follows:
  
    1) If the given range [begin, end) is not covered by the instance,
    the range is newly created and iterated.
  
    2) If the given range [begin, end) exactly covers ranges in the instance,
    the ranges are iterated.
    (See test_set() in tests/range_dict_tests.py.)
  
    3) If the given range [begin, end) starts at and/or ends at a mid-point of
    an existing range, the existing range is split by the given range, and
    ranges in the given range are iterated.  For example, consider a case that
    [25, 45) is given to an instance of [20, 30), [30, 40), [40, 50).  In this
    case, [20, 30) is split into [20, 25) and [25, 30), and [40, 50) into
    [40, 45) and [45, 50).  Then, [25, 30), [30, 40), [40, 45) are iterated.
    (See test_split() in tests/range_dict_tests.py.)
  
    4) If the given range [begin, end) includes non-existing ranges in an
    instance, the gaps are filled with new ranges, and all ranges are iterated.
    For example, consider a case that [25, 50) is given to an instance of
    [30, 35) and [40, 45).  In this case, [25, 30), [35, 40) and [45, 50) are
    created in the instance, and then [25, 30), [30, 35), [35, 40), [40, 45)
    and [45, 50) are iterated.
    (See test_fill() in tests/range_dict_tests.py.)
    """
    class RangeAttribute(object):
      def __init__(self):
        pass
  
      def __str__(self):
        return '<RangeAttribute>'
  
      def __repr__(self):
        return '<RangeAttribute>'
  
      def copy(self):  # pylint: disable=R0201
        return ExclusiveRangeDict.RangeAttribute()
  
    def __init__(self, attr=RangeAttribute):
      self._tree = FastRBTree()
      self._attr = attr
  
    def iter_range(self, begin=None, end=None):
      if not begin:
        begin = self._tree.min_key()
      if not end:
        end = self._tree.max_item()[1][0]
  
      # Assume that self._tree has at least one element.
      if self._tree.is_empty():
        self._tree[begin] = (end, self._attr())
  
      # Create a beginning range (border)
      try:
        bound_begin, bound_value = self._tree.floor_item(begin)
        bound_end = bound_value[0]
        if begin >= bound_end:
          # Create a blank range.
          try:
            new_end, _ = self._tree.succ_item(bound_begin)
          except KeyError:
            new_end = end
          self._tree[begin] = (min(end, new_end), self._attr())
        elif bound_begin < begin and begin < bound_end:
          # Split the existing range.
          new_end = bound_value[0]
          new_value = bound_value[1]
          self._tree[bound_begin] = (begin, new_value.copy())
          self._tree[begin] = (new_end, new_value.copy())
        else:  # bound_begin == begin
          # Do nothing (just saying it clearly since this part is confusing)
          pass
      except KeyError:  # begin is less than the smallest element.
        # Create a blank range.
        # Note that we can assume self._tree has at least one element.
        self._tree[begin] = (min(end, self._tree.min_key()), self._attr())
  
      # Create an ending range (border)
      try:
        bound_begin, bound_value = self._tree.floor_item(end)
        bound_end = bound_value[0]
        if end > bound_end:
          # Create a blank range.
          new_begin = bound_end
          self._tree[new_begin] = (end, self._attr())
        elif bound_begin < end and end < bound_end:
          # Split the existing range.
          new_end = bound_value[0]
          new_value = bound_value[1]
          self._tree[bound_begin] = (end, new_value.copy())
          self._tree[end] = (new_end, new_value.copy())
        else:  # bound_begin == begin
          # Do nothing (just saying it clearly since this part is confusing)
          pass
      except KeyError:  # end is less than the smallest element.
        # It must not happen.  A blank range [begin,end) has already been created
        # even if [begin,end) is less than the smallest range.
        # Do nothing (just saying it clearly since this part is confusing)
        raise
  
      missing_ranges = []
  
      prev_end = None
      for range_begin, range_value in self._tree.itemslice(begin, end):
        range_end = range_value[0]
        # Note that we can assume that we have a range beginning with |begin|
        # and a range ending with |end| (they may be the same range).
        if prev_end and prev_end != range_begin:
          missing_ranges.append((prev_end, range_begin))
        prev_end = range_end
  
      for missing_begin, missing_end in missing_ranges:
        self._tree[missing_begin] = (missing_end, self._attr())
  
      for range_begin, range_value in self._tree.itemslice(begin, end):
        yield range_begin, range_value[0], range_value[1]
  
    def __str__(self):
      return str(self._tree)
  