Victorman5

Python.Multiset

Feb 26th, 2021
713
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # импортируем нужные функции
  2. from bisect import bisect_left, bisect_right, insort_left, insort_right
  3.  
  4.  
  5. class Multiset:
  6.     def __init__(self, iterable=None):
  7.         # конструктор
  8.         if iterable is None:
  9.             self.__dataset = []  # пустое множество
  10.         else:
  11.             self.__dataset = [e for e in iterable]  # перекидываем данные
  12.             self.__dataset.sort()  # поддерживаем отсортированность
  13.  
  14.     def insert(self, item):
  15.         # добавить элемент
  16.         self.insert_right(item)
  17.  
  18.     def insert_right(self, item):
  19.         # вставить элемент как можно правее
  20.         insort_right(self.__dataset, item)
  21.  
  22.     def insert_left(self, item):
  23.         # вставить элемент как можно левее
  24.         insort_left(self.__dataset, item)
  25.  
  26.     def erase(self, item):
  27.         # у-да-лить
  28.         self.erase_right(item)
  29.  
  30.     def erase_all(self, item):
  31.         # удалить все такие элементы
  32.         left = self.__left_index_or_none(item)
  33.         right = self.__right_index_or_none(item)
  34.         del self.__dataset[left: right + 1]  # левая граница в сделку не входила
  35.  
  36.     def erase_right(self, item):
  37.         # удаляем правый элемент (нафик из этой жизни, блин)
  38.         i = self.__right_index_or_none(item)
  39.         if i:
  40.             del self.__dataset[i]
  41.         else:
  42.             raise ValueError("No such item in set!")
  43.  
  44.     def erase_left(self, item):
  45.         # удаляем левый элемент
  46.         i = self.__left_index_or_none(item)
  47.         if i:
  48.             del self.__dataset[i]
  49.         else:
  50.             raise ValueError("No such item in set!")
  51.  
  52.     def pop(self, item):
  53.         return self.pop_right(item)
  54.  
  55.     def pop_left(self, item):
  56.         i = self.__left_index_or_none(item)
  57.         if i is None:
  58.             # падаем скорей!! (главное правило программирования)
  59.             raise ValueError("No such item in set!")
  60.         v = self.__dataset[i]  # запоминаем, что надо вернуть
  61.         del self.__dataset[i]  # удаляем эту пакость
  62.         return v
  63.  
  64.     def pop_right(self, item):
  65.         i = self.__right_index_or_none(item)
  66.         if i is None:
  67.             raise ValueError("No such item in set!")
  68.         v = self.__dataset[i]
  69.         del self.__dataset[i]
  70.         return v
  71.  
  72.     def lower(self, item):
  73.         i = self.__left_index_or_none(item)
  74.         if i is None:
  75.             raise ValueError("No such item in set!")
  76.         return self.__dataset[i]
  77.  
  78.     def upper(self, item):
  79.         i = self.__right_index_or_none(item)
  80.         if i is None:
  81.             raise ValueError("No such item in set!")
  82.         return self.__dataset[i]
  83.  
  84.     def count(self, item):
  85.         # кол-во элементов: len([l; r]) = r - l + 1
  86.         left = self.__left_index_or_none(item)
  87.         right = self.__right_index_or_none(item)
  88.         if left is None or right is None:
  89.             return 0
  90.         return right - left + 1
  91.  
  92.     def max(self):
  93.         return self.__dataset[-1]
  94.  
  95.     def min(self):
  96.         return self.__dataset[0]
  97.  
  98.     def count_of_greater_than(self, item):
  99.         return self.__dataset.__len__() - bisect_right(self.__dataset, item)
  100.  
  101.     def count_of_less_than(self, item):
  102.         return bisect_left(self.__dataset, item)
  103.  
  104.     def __right_index_or_none(self, item):
  105.         # вспомогательный метод: ищет самый правый элемент
  106.         i = bisect_right(self.__dataset, item) - 1
  107.         if i >= 0 and self.__dataset[i] == item:
  108.             return i
  109.         return None
  110.  
  111.     def __left_index_or_none(self, item):
  112.         # вспомогательный метод: ищет самый левый элемент
  113.         i = bisect_left(self.__dataset, item)
  114.         if i != len(self.__dataset) and self.__dataset[i] == item:
  115.             return i
  116.         return None
  117.  
  118.     def __len__(self):
  119.         # сколько элементов во множестве
  120.         return self.__dataset.__len__()
  121.  
  122.     def __iter__(self):
  123.         # итератор, чтобы можно было проходится по элементам в цикле for
  124.         return self.__dataset.__iter__()
  125.  
  126.     def __contains__(self, item):
  127.         # item in self.dataset; проверяет, есть ли значение во множестве
  128.         return self.__left_index_or_none(item) is not None
  129.  
  130.     def __str__(self):
  131.         # возвращает красивое строковое представление объекта
  132.         return self.__dataset.__str__()
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×