Changeset View
Changeset View
Standalone View
Standalone View
swh/core/collections.py
| # Copyright (C) 2020 The Software Heritage developers | # Copyright (C) 2020 The Software Heritage developers | ||||
| # See the AUTHORS file at the top-level directory of this distribution | # See the AUTHORS file at the top-level directory of this distribution | ||||
| # License: GNU General Public License version 3, or any later version | # License: GNU General Public License version 3, or any later version | ||||
| # See top-level LICENSE file for more information | # See top-level LICENSE file for more information | ||||
| import bisect | import bisect | ||||
| import collections | |||||
| import itertools | import itertools | ||||
| from typing import Any, Callable, Generic, Iterator, List, Optional, Tuple, TypeVar | from typing import Any, Callable, Generic, Iterator, List, Optional, Tuple, TypeVar | ||||
| SortedListItem = TypeVar("SortedListItem") | SortedListItem = TypeVar("SortedListItem") | ||||
| SortedListKey = TypeVar("SortedListKey") | SortedListKey = TypeVar("SortedListKey") | ||||
| class SortedList(collections.UserList, Generic[SortedListKey, SortedListItem]): | class SortedList(Generic[SortedListKey, SortedListItem]): | ||||
| data: List[Tuple[SortedListKey, SortedListItem]] | data: List[Tuple[SortedListKey, SortedListItem]] | ||||
| # https://github.com/python/mypy/issues/708 | # https://github.com/python/mypy/issues/708 | ||||
| # key: Callable[[SortedListItem], SortedListKey] | # key: Callable[[SortedListItem], SortedListKey] | ||||
| def __init__( | def __init__( | ||||
| self, | self, | ||||
| data: List[SortedListItem] = None, | data: List[SortedListItem] = None, | ||||
| key: Optional[Callable[[SortedListItem], SortedListKey]] = None, | key: Optional[Callable[[SortedListItem], SortedListKey]] = None, | ||||
| ): | ): | ||||
| if key is None: | if key is None: | ||||
| def key(item): | def key(item): | ||||
| return item | return item | ||||
| assert key is not None # for mypy | assert key is not None # for mypy | ||||
| super().__init__(sorted((key(x), x) for x in data or [])) | self.data = sorted((key(x), x) for x in data or []) | ||||
| self.key: Callable[[SortedListItem], SortedListKey] = key | self.key: Callable[[SortedListItem], SortedListKey] = key | ||||
| def add(self, item: SortedListItem): | def add(self, item: SortedListItem): | ||||
| k = self.key(item) | k = self.key(item) | ||||
| bisect.insort(self.data, (k, item)) | bisect.insort(self.data, (k, item)) | ||||
| def __iter__(self) -> Iterator[SortedListItem]: | def __iter__(self) -> Iterator[SortedListItem]: | ||||
| Show All 22 Lines | |||||