python-sortedcontainers/sortedcontainers/sortedarray.py at cbdf4e1bdc115d8b962141b46191c6e3e6b2aac7 · grantjenks/python-sortedcontainers · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
"""Sorted Array
===============


:doc:`Sorted Containers<index>` is an Apache2 licensed Python sorted
collections library, written in pure-Python, and fast as C-extensions. The
:doc:`introduction<introduction>` is the best way to get started.

Sorted list implementations:

.. currentmodule:: sortedcontainers

* :class:`SortedArray`

"""
# pylint: disable=too-many-lines
from __future__ import print_function
from sys import hexversion

from .sortedlist import SortedList, recursive_repr
from array import array

class SortedArray(SortedList):
    """Sorted array is a sorted mutable sequence.

    Sorted array values are maintained in sorted order.

    Underlying data structure is the standard library array.array
    Enables densly packed lists floats and doubles.
    Enables densly packed lists of integers in CPython.

    Methods for adding values:

    * :func:`SortedArray.add`
    * :func:`SortedArray.update`
    * :func:`SortedArray.__add__`
    * :func:`SortedArray.__iadd__`
    * :func:`SortedArray.__mul__`
    * :func:`SortedArray.__imul__`

    Methods for removing values:

    * :func:`SortedArray.clear`
    * :func:`SortedArray.discard`
    * :func:`SortedArray.remove`
    * :func:`SortedArray.pop`
    * :func:`SortedArray.__delitem__`

    Methods for looking up values:

    * :func:`SortedArray.bisect_left`
    * :func:`SortedArray.bisect_right`
    * :func:`SortedArray.count`
    * :func:`SortedArray.index`
    * :func:`SortedArray.__contains__`
    * :func:`SortedArray.__getitem__`

    Methods for iterating values:

    * :func:`SortedArray.irange`
    * :func:`SortedArray.islice`
    * :func:`SortedArray.__iter__`
    * :func:`SortedArray.__reversed__`

    Methods for miscellany:

    * :func:`SortedArray.copy`
    * :func:`SortedArray.__len__`
    * :func:`SortedArray.__repr__`
    * :func:`SortedArray._check`
    * :func:`SortedArray._reset`

    Sorted lists use lexicographical ordering semantics when compared to other
    sequences.

    Some methods of mutable sequences are not supported and will raise
    not-implemented error.

    """
    DEFAULT_LOAD_FACTOR = 1000


    def __init__(self, typecode, initializer=None):
        """Initialize sorted array instance.

        Optional `iterable` argument provides an initial iterable of values to
        initialize the sorted array.

        Runtime complexity: `O(n*log(n))`

        >>> sl = SortedArray('i')
        >>> sl
        SortedArray('i', [])
        >>> sl = SortedArray('i', [3, 1, 2, 5, 4])
        >>> sl
        SortedArray('i', [1, 2, 3, 4, 5])

        :param typecode: type code for the array, as in the array.array standard library class (required)
        :param iterable: initial values (optional)

        """
        self._typecode = typecode
        if hexversion >= 0x03000000:
            super().__init__(iterable=initializer, key=None)
        else:
            super(SortedArray, self).__init__(iterable=initializer, key=None)


    def __new__(cls, typecode, initializer=None):
        # pylint: disable=unused-argument
        if hexversion >= 0x03000000:
            return super().__new__(cls, iterable=initializer, key=None)
        else:
            return super(SortedArray, cls).__new__(cls, iterable=initializer, key=None)


    def _new_list(self):
        _typecode = self._typecode
        return array(_typecode)


    def _sort_in_place(self, _list):
        # array.array does not support sort in place
        sorted_list = sorted(_list)
        del _list[:]
        _list.extend(sorted_list)


    @recursive_repr()
    def __repr__(self):
        """Return string representation of sorted array.

        ``sa.__repr__()`` <==> ``repr(sa)``

        :return: string representation

        >>> sa = SortedArray('i',[5,4,3])
        >>> sa
        SortedArray('i', [3, 4, 5])
        """
        class_name = type(self).__name__
        _typecode = self._typecode
        return "{0}('{1}', {2!r})".format(class_name, _typecode, list(self))