Guest User

Untitled

a guest
Feb 17th, 2019
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. class TrackerError(Exception):
  2. pass
  3.  
  4.  
  5. class TrackerMethodNotImplemented(TrackerError):
  6. pass
  7.  
  8.  
  9. class StackTracker(object):
  10. def __init__(self, limit, items = None):
  11. self.__limit__ = limit
  12. self.__items__ = items or []
  13.  
  14. def push(self, item):
  15. if self.current_size == 0:
  16. self.__items__.append(item)
  17. elif self.current_size == self.limit:
  18. self.__cap__(item)
  19. else:
  20. self.__insert__(item)
  21.  
  22. return self.items
  23.  
  24. def __cap__(self, item):
  25. raise TrackerMethodNotImplemented
  26.  
  27. def __insert__(self, item):
  28. start = 0
  29. end = self.current_size
  30. index = (start + end) // 2
  31.  
  32. while start != index and end != index:
  33. current_item = self.__items__[index]
  34.  
  35. if current_item > item:
  36. end = index
  37. else:
  38. start = index
  39.  
  40. index = (start + end) // 2
  41.  
  42. if item > self.__items__[index]:
  43. self.__items__.insert(index + 1, item)
  44. else:
  45. self.__items__.insert(index, item)
  46.  
  47. @property
  48. def current_size(self):
  49. return len(self.__items__)
  50.  
  51. @property
  52. def items(self):
  53. return self.__items__[:]
  54.  
  55. @property
  56. def last(self):
  57. return self.__items__[-1] if self.current_size else None
  58.  
  59. @property
  60. def first(self):
  61. return self.__items__[0] if self.current_size else None
  62.  
  63. @property
  64. def limit(self):
  65. return self.__limit__
  66.  
  67.  
  68. class MinTracker(StackTracker):
  69. def __cap__(self, item):
  70. if self.last < item:
  71. return
  72.  
  73. self.__items__.pop()
  74. self.__insert__(item)
  75.  
  76.  
  77. class MaxTracker(StackTracker):
  78. def __cap__(self, item):
  79. if self.first > item:
  80. return
  81.  
  82. del self.__items__[0]
  83. self.__insert__(item)
Add Comment
Please, Sign In to add comment