• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Copyright 2013 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5import os
6import sys
7
8_BASE_PATH = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
9_BINTREES_PATH = os.path.join(
10    _BASE_PATH, os.pardir, os.pardir, 'third_party', 'bintrees')
11sys.path.insert(0, _BINTREES_PATH)
12
13from bintrees import FastRBTree  # pylint: disable=F0401
14
15
16class ExclusiveRangeDict(object):
17  """A class like dict whose key is a range [begin, end) of integers.
18
19  It has an attribute for each range of integers, for example:
20  [10, 20) => Attribute(0),
21  [20, 40) => Attribute(1),
22  [40, 50) => Attribute(2),
23  ...
24
25  An instance of this class is accessed only via iter_range(begin, end).
26  The instance is accessed as follows:
27
28  1) If the given range [begin, end) is not covered by the instance,
29  the range is newly created and iterated.
30
31  2) If the given range [begin, end) exactly covers ranges in the instance,
32  the ranges are iterated.
33  (See test_set() in tests/range_dict_tests.py.)
34
35  3) If the given range [begin, end) starts at and/or ends at a mid-point of
36  an existing range, the existing range is split by the given range, and
37  ranges in the given range are iterated.  For example, consider a case that
38  [25, 45) is given to an instance of [20, 30), [30, 40), [40, 50).  In this
39  case, [20, 30) is split into [20, 25) and [25, 30), and [40, 50) into
40  [40, 45) and [45, 50).  Then, [25, 30), [30, 40), [40, 45) are iterated.
41  (See test_split() in tests/range_dict_tests.py.)
42
43  4) If the given range [begin, end) includes non-existing ranges in an
44  instance, the gaps are filled with new ranges, and all ranges are iterated.
45  For example, consider a case that [25, 50) is given to an instance of
46  [30, 35) and [40, 45).  In this case, [25, 30), [35, 40) and [45, 50) are
47  created in the instance, and then [25, 30), [30, 35), [35, 40), [40, 45)
48  and [45, 50) are iterated.
49  (See test_fill() in tests/range_dict_tests.py.)
50  """
51  class RangeAttribute(object):
52    def __init__(self):
53      pass
54
55    def __str__(self):
56      return '<RangeAttribute>'
57
58    def __repr__(self):
59      return '<RangeAttribute>'
60
61    def copy(self):  # pylint: disable=R0201
62      return ExclusiveRangeDict.RangeAttribute()
63
64  def __init__(self, attr=RangeAttribute):
65    self._tree = FastRBTree()
66    self._attr = attr
67
68  def iter_range(self, begin=None, end=None):
69    if not begin:
70      begin = self._tree.min_key()
71    if not end:
72      end = self._tree.max_item()[1][0]
73
74    # Assume that self._tree has at least one element.
75    if self._tree.is_empty():
76      self._tree[begin] = (end, self._attr())
77
78    # Create a beginning range (border)
79    try:
80      bound_begin, bound_value = self._tree.floor_item(begin)
81      bound_end = bound_value[0]
82      if begin >= bound_end:
83        # Create a blank range.
84        try:
85          new_end, _ = self._tree.succ_item(bound_begin)
86        except KeyError:
87          new_end = end
88        self._tree[begin] = (min(end, new_end), self._attr())
89      elif bound_begin < begin and begin < bound_end:
90        # Split the existing range.
91        new_end = bound_value[0]
92        new_value = bound_value[1]
93        self._tree[bound_begin] = (begin, new_value.copy())
94        self._tree[begin] = (new_end, new_value.copy())
95      else:  # bound_begin == begin
96        # Do nothing (just saying it clearly since this part is confusing)
97        pass
98    except KeyError:  # begin is less than the smallest element.
99      # Create a blank range.
100      # Note that we can assume self._tree has at least one element.
101      self._tree[begin] = (min(end, self._tree.min_key()), self._attr())
102
103    # Create an ending range (border)
104    try:
105      bound_begin, bound_value = self._tree.floor_item(end)
106      bound_end = bound_value[0]
107      if end > bound_end:
108        # Create a blank range.
109        new_begin = bound_end
110        self._tree[new_begin] = (end, self._attr())
111      elif bound_begin < end and end < bound_end:
112        # Split the existing range.
113        new_end = bound_value[0]
114        new_value = bound_value[1]
115        self._tree[bound_begin] = (end, new_value.copy())
116        self._tree[end] = (new_end, new_value.copy())
117      else:  # bound_begin == begin
118        # Do nothing (just saying it clearly since this part is confusing)
119        pass
120    except KeyError:  # end is less than the smallest element.
121      # It must not happen.  A blank range [begin,end) has already been created
122      # even if [begin,end) is less than the smallest range.
123      # Do nothing (just saying it clearly since this part is confusing)
124      raise
125
126    missing_ranges = []
127
128    prev_end = None
129    for range_begin, range_value in self._tree.itemslice(begin, end):
130      range_end = range_value[0]
131      # Note that we can assume that we have a range beginning with |begin|
132      # and a range ending with |end| (they may be the same range).
133      if prev_end and prev_end != range_begin:
134        missing_ranges.append((prev_end, range_begin))
135      prev_end = range_end
136
137    for missing_begin, missing_end in missing_ranges:
138      self._tree[missing_begin] = (missing_end, self._attr())
139
140    for range_begin, range_value in self._tree.itemslice(begin, end):
141      yield range_begin, range_value[0], range_value[1]
142
143  def __str__(self):
144    return str(self._tree)
145