Want more features on Pastebin? Sign Up, it's FREE!
Guest

IntervalTree.py

By: a guest on May 21st, 2013  |  syntax: Python  |  size: 2.88 KB  |  views: 32  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. '''
  2. Interval Tree implementation in Python
  3. Copyright (C) 2010  Tyler Kahn
  4.  
  5. Original from https://github.com/tylerkahn/intervaltree-python, 2013
  6.  
  7. This program is free software: you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation, either version 3 of the License, or
  10. (at your option) any later version.
  11.  
  12. This program is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19. '''
  20.  
  21. class IntervalTree:
  22.         def __init__(self, intervals):
  23.                 ## Modification to original code.
  24.                 i = 0
  25.                 for interval in intervals:
  26.                         if not hasattr(interval, 'key'):
  27.                                 interval.key = i
  28.                                 i += 1
  29.                
  30.                 self.top_node = self.divide_intervals(intervals)
  31.  
  32.         def divide_intervals(self, intervals):
  33.  
  34.                 if not intervals:
  35.                         return None
  36.  
  37.                 x_center = self.center(intervals)
  38.  
  39.                 s_center = []
  40.                 s_left = []
  41.                 s_right = []
  42.  
  43.                 for k in intervals:
  44.                         if k.get_end() < x_center:
  45.                                 s_left.append(k)
  46.                         elif k.get_begin() > x_center:
  47.                                 s_right.append(k)
  48.                         else:
  49.                                 s_center.append(k)
  50.  
  51.                 return Node(x_center, s_center, self.divide_intervals(s_left), self.divide_intervals(s_right))
  52.                
  53.  
  54.         def center(self, intervals):
  55.                 fs = sort_by_begin(intervals)
  56.                 length = len(fs)
  57.  
  58.                 return fs[int(length/2)].get_begin()
  59.  
  60.         def search(self, begin, end=None):
  61.                 if end:
  62.                         result = []
  63.  
  64.                         for j in xrange(begin, end+1):
  65.                                 for k in self.search(j):
  66.                                         result.append(k)
  67.                                 result = list(set(result))
  68.                         return sort_by_begin(result)
  69.                 else:
  70.                         return self._search(self.top_node, begin, [])
  71.         def _search(self, node, point, result):
  72.                
  73.                 for k in node.s_center:
  74.                         if k.get_begin() <= point <= k.get_end():
  75.                                 result.append(k)
  76.                 if point < node.x_center and node.left_node:
  77.                         for k in self._search(node.left_node, point, []):
  78.                                 result.append(k)
  79.                 if point > node.x_center and node.right_node:
  80.                         for k in self._search(node.right_node, point, []):
  81.                                 result.append(k)
  82.  
  83.                 return list(set(result))
  84.  
  85. class Interval:
  86.         def __init__(self, begin, end):
  87.                 self.begin = begin
  88.                 self.end = end
  89.                
  90.         def get_begin(self):
  91.                 return self.begin
  92.         def get_end(self):
  93.                 return self.end
  94.  
  95. class Node:
  96.         def __init__(self, x_center, s_center, left_node, right_node):
  97.                 self.x_center = x_center
  98.                 self.s_center = sort_by_begin(s_center)
  99.                 self.left_node = left_node
  100.                 self.right_node = right_node
  101.  
  102. def sort_by_begin(intervals):
  103.         return sorted(intervals, key=lambda x: x.get_begin())
clone this paste RAW Paste Data