#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
Создание классов коллекций посредством наследования
'''
# # 323
_identity = lambda x: x
class SortedList:
def __init__(self, sequence=None, key=None):
self.__key = key or _identity
assert hasattr(self.__key, "__call__")
if sequence is None:
self.__list = []
elif (isinstance(sequence, SortedList) and
sequence.key == self.__key):
self.__list = sequence.__list[:]
else:
self.__list = sorted(list(sequence), key=self.__key)
@property
def key(self):
return self.__key
def clear(self):
self.__list = []
def __bisect_left(self, value):
key = self.__key(value)
left, right = 0, len(self.__list)
while left < right:
middle = (left + right) // 2
if self.__key(self.__list[middle]) < key:
left = middle + 1
else:
right = middle
return left
def add(self, value):
index = self.__bisect_left(value)
if index == len(self.__list):
self.__list.append(value)
else:
self.__list.insert(index, value)
def pop(self, index=-1):
return self.__list.pop(index)
def remove(self, value):
index = self.__bisect_left(value)
if index < len(self.__list) and self.__list[index] == value:
del self.__list[index]
else:
raise ValueError("{0}.remove(x): x not in list".format(
self.__class__.__name__))
def remove_every(self, value):
count = 0
index = self.__bisect_left(value)
while (index < len(self.__list) and
self.__list[index] == value):
del self.__list[index]
count += 1
return count
def count(self, value):
count = 0
index = self.__bisect_left(value)
while (index < len(self.__list) and
self.__list[index] == value):
index += 1
count += 1
return count
def index(self, value):
index = self.__bisect_left(value)
if index < len(self.__list) and self.__list[index] == value:
return index
raise ValueError("{0}.index(x): x not in list".format(
self.__class__.__name__))
def __delitem__(self, index):
del self.__list[index]
def __getitem__(self, index):
return self.__list[index]
def __setitem__(self, index, value):
raise TypeError("use add() to insert a value and rely on "
"the list to put it in the right place")
def __iter__(self):
return iter(self.__list)
def __reversed__(self):
return reversed(self.__list)
def __contains__(self, value):
index = self.__bisect_left(value)
return (index < len(self.__list) and
self.__list[index] == value)
def __len__(self):
return len(self.__list)
def __str__(self):
return str(self.__list)
def copy(self):
return SortedList(self, self.__key)
__copy__ = copy
class SortedDict(dict):
def __init__(self, dictionary=None, key=None, **kwargs):
dictionary = dictionary or {}
super(SortedDict, self).__init__(dictionary, **kwargs)
if kwargs:
super(SortedDict, self).update(kwargs)
self.__keys = SortedList(super(SortedDict, self).keys(), key)
def update(self, dictionary=None, **kwargs):
if dictionary is None:
pass
elif isinstance(dictionary, dict):
super(SortedDict, self).update(dictionary)
else:
for key, value in dictionary.items():
super(SortedDict, self).__setitem__(key, value)
if kwargs:
super(SortedDict, self).update(kwargs)
self.__keys = SortedList.SortedList(super(SortedList, self).keys(),
self.__keys.key)
@classmethod
def fromkeys(cls, iterable, value=None, key=None):
return cls({k: value for k in iterable}, key)
def value_at(self, index):
return self[self.__keys[index]]
def set_value_at(self, index, value):
self[self.__keys[index]] = value
def clear(self):
super(SortedList, self).clear()
self.__keys.clear()
def setdefault(self, key, value=None):
if key not in self:
self.__keys.add(key)
return super(SortedDict, self).setdefault(key, value)
def pop(self, key, *args):
if key not in self:
if len(args) == 0:
raise KeyError(key)
return args[0]
self.__keys.remove(key)
return super(SortedDict, self).pop(key, args)
def popitem(self):
item = super(SortedDict, self).popitem()
self.__keys.remove(item[0])
return item
def values(self):
for key in self.__keys:
yield self[key]
def items(self):
for key in self.__keys:
yield (key, self[key])
def __iter__(self):
return iter(self.__keys)
keys = __iter__
def __delitem__(self, key):
try:
self.__keys.remove(key)
except ValueError:
raise KeyError(key)
return super(SortedDict, self).__delitem__(key)
def __setitem__(self, key, value):
if key not in self:
self.__keys.add(key)
return super(SortedDict, self).__setitem__(key, value)
def __repr__(self):
return object.__repr__(self)
def __str__(self):
return ("{" + ", ".join(["{0!r}: {1!r}".format(k, v)
for k, v in self.items()]) + "}")
def copy(self):
d = SortedDict()
super(SortedDict, d).update(self)
d.__keys = self.__keys.copy()
return d
__copy__ = copy
# class SortedDict(dict):
# def __init__(self, dictionary=None, key=None, **kwargs):
# dictionary = dictionary or {}
# super(dict, self).__init__(dictionary, **kwargs)
# if kwargs:
# super(SortedDict, self).update(kwargs)
# self.__keys = SortedList(super(SortedDict, self).keys(), key)
# def __delitem__(self, key):
# # """Deletes the item with the given key from the dictionary
# # >>> d = SortedDict(dict(s=1, a=2, n=3, i=4, t=5, y=6))
# # >>> del d["s"]
# # >>> del d["y"]
# # >>> del d["a"]
# # >>> list(d.keys())
# # ['i', 'n', 't']
# # >>> del d["X"]
# # Traceback (most recent call last):
# # ...
# # KeyError: 'X'
# # """
# try:
# self.__keys.remove(key)
# except ValueError:
# raise KeyError(key)
# return super(key, self).__delitem__(key)
d = SortedDict(dict(s=1, A=2, y=6), str.lower)
d["z"] = 4
d["T"] = 5
del d["y"]
d["n"] = 3
d["A"] = 17
print str(d) # вернет: "{'А': 17, 'n': 3, 's': 1, T: 5, 'z'\ 4>"
