Source

pypy / lib_pypy / array.py

  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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
"""This module defines an object type which can efficiently represent
an array of basic values: characters, integers, floating point
numbers.  Arrays are sequence types and behave very much like lists,
except that the type of objects stored in them is constrained.  The
type is specified at object creation time by using a type code, which
is a single character.  The following type codes are defined:

    Type code   C Type             Minimum size in bytes 
    'c'         character          1 
    'b'         signed integer     1 
    'B'         unsigned integer   1 
    'u'         Unicode character  2 
    'h'         signed integer     2 
    'H'         unsigned integer   2 
    'i'         signed integer     2 
    'I'         unsigned integer   2 
    'l'         signed integer     4 
    'L'         unsigned integer   4 
    'f'         floating point     4 
    'd'         floating point     8 

The constructor is:

array(typecode [, initializer]) -- create a new array
"""

from struct import calcsize, pack, pack_into, unpack_from
import operator

# the buffer-like object to use internally: trying from
# various places in order...
try:
    import _rawffi                    # a reasonable implementation based
    _RAWARRAY = _rawffi.Array('c')    # on raw_malloc, and providing a
    def bytebuffer(size):             # real address
        return _RAWARRAY(size, autofree=True)
    def getbufaddress(buf):
        return buf.buffer
except ImportError:
    try:
        from __pypy__ import bytebuffer     # a reasonable implementation
        def getbufaddress(buf):             # compatible with oo backends,
            return 0                        # but no address
    except ImportError:
        # not running on PyPy.  Fall back to ctypes...
        import ctypes
        bytebuffer = ctypes.create_string_buffer
        def getbufaddress(buf):
            voidp = ctypes.cast(ctypes.pointer(buf), ctypes.c_void_p)
            return voidp.value

# ____________________________________________________________

TYPECODES = "cbBuhHiIlLfd"

class array(object):
    """array(typecode [, initializer]) -> array
    
    Return a new array whose items are restricted by typecode, and
    initialized from the optional initializer value, which must be a list,
    string. or iterable over elements of the appropriate type.
    
    Arrays represent basic values and behave very much like lists, except
    the type of objects stored in them is constrained.
    
    Methods:
    
    append() -- append a new item to the end of the array
    buffer_info() -- return information giving the current memory info
    byteswap() -- byteswap all the items of the array
    count() -- return number of occurences of an object
    extend() -- extend array by appending multiple elements from an iterable
    fromfile() -- read items from a file object
    fromlist() -- append items from the list
    fromstring() -- append items from the string
    index() -- return index of first occurence of an object
    insert() -- insert a new item into the array at a provided position
    pop() -- remove and return item (default last)
    read() -- DEPRECATED, use fromfile()
    remove() -- remove first occurence of an object
    reverse() -- reverse the order of the items in the array
    tofile() -- write all items to a file object
    tolist() -- return the array converted to an ordinary list
    tostring() -- return the array converted to a string
    write() -- DEPRECATED, use tofile()
    
    Attributes:
    
    typecode -- the typecode character used to create the array
    itemsize -- the length in bytes of one array item
    """
    __slots__ = ["typecode", "itemsize", "_data", "_descriptor", "__weakref__"]

    def __new__(cls, typecode, initializer=[], **extrakwds):
        self = object.__new__(cls)
        if cls is array and extrakwds:
            raise TypeError("array() does not take keyword arguments")
        if not isinstance(typecode, str) or len(typecode) != 1:
            raise TypeError(
                     "array() argument 1 must be char, not %s" % type(typecode))
        if typecode not in TYPECODES:
            raise ValueError(
                  "bad typecode (must be one of %s)" % ', '.join(TYPECODES))
        self._data = bytebuffer(0)
        self.typecode = typecode
        self.itemsize = calcsize(typecode)
        if isinstance(initializer, list):
            self.fromlist(initializer)
        elif isinstance(initializer, str):
            self.fromstring(initializer)
        elif isinstance(initializer, unicode) and self.typecode == "u":
            self.fromunicode(initializer)
        else:
            self.extend(initializer)
        return self

    def _clear(self):
        self._data = bytebuffer(0)

    ##### array-specific operations

    def fromfile(self, f, n):
        """Read n objects from the file object f and append them to the end of
        the array. Also called as read."""
        if not isinstance(f, file):
            raise TypeError("arg1 must be open file")
        size = self.itemsize * n
        item = f.read(size)
        if len(item) < size:
            raise EOFError("not enough items in file")
        self.fromstring(item)

    def fromlist(self, l):
        """Append items to array from list."""
        if not isinstance(l, list):
            raise TypeError("arg must be list")
        self._fromiterable(l)
        
    def fromstring(self, s):
        """Appends items from the string, interpreting it as an array of machine
        values, as if it had been read from a file using the fromfile()
        method."""
        if isinstance(s, unicode):
            s = str(s)
        self._frombuffer(s)

    def _frombuffer(self, s):
        length = len(s)
        if length % self.itemsize != 0:
            raise ValueError("string length not a multiple of item size")
        boundary = len(self._data)
        newdata = bytebuffer(boundary + length)
        newdata[:boundary] = self._data
        newdata[boundary:] = s
        self._data = newdata

    def fromunicode(self, ustr):
        """Extends this array with data from the unicode string ustr. The array
        must be a type 'u' array; otherwise a ValueError is raised. Use
        array.fromstring(ustr.encode(...)) to append Unicode data to an array of
        some other type."""
        if not self.typecode == "u":
            raise ValueError(
                          "fromunicode() may only be called on type 'u' arrays")
        # XXX the following probable bug is not emulated:
        # CPython accepts a non-unicode string or a buffer, and then
        # behaves just like fromstring(), except that it strangely truncates
        # string arguments at multiples of the unicode byte size.
        # Let's only accept unicode arguments for now.
        if not isinstance(ustr, unicode):
            raise TypeError("fromunicode() argument should probably be "
                            "a unicode string")
        # _frombuffer() does the currect thing using
        # the buffer behavior of unicode objects
        self._frombuffer(buffer(ustr))

    def tofile(self, f):
        """Write all items (as machine values) to the file object f.  Also
        called as write."""
        if not isinstance(f, file):
            raise TypeError("arg must be open file")
        f.write(self.tostring())
        
    def tolist(self):
        """Convert array to an ordinary list with the same items."""
        count = len(self._data) // self.itemsize
        return list(unpack_from('%d%s' % (count, self.typecode), self._data))

    def tostring(self):
        return self._data[:]

    def __buffer__(self):
        return buffer(self._data)

    def tounicode(self):
        """Convert the array to a unicode string. The array must be a type 'u'
        array; otherwise a ValueError is raised. Use array.tostring().decode()
        to obtain a unicode string from an array of some other type."""
        if self.typecode != "u":
            raise ValueError("tounicode() may only be called on type 'u' arrays")
        # XXX performance is not too good
        return u"".join(self.tolist())

    def byteswap(self):
        """Byteswap all items of the array.  If the items in the array are not
        1, 2, 4, or 8 bytes in size, RuntimeError is raised."""
        if self.itemsize not in [1, 2, 4, 8]:
            raise RuntimeError("byteswap not supported for this array")
        # XXX slowish
        itemsize = self.itemsize
        bytes = self._data
        for start in range(0, len(bytes), itemsize):
            stop = start + itemsize
            bytes[start:stop] = bytes[start:stop][::-1]

    def buffer_info(self):
        """Return a tuple (address, length) giving the current memory address
        and the length in items of the buffer used to hold array's contents. The
        length should be multiplied by the itemsize attribute to calculate the
        buffer length in bytes. On PyPy the address might be meaningless
        (returned as 0), depending on the available modules."""
        return (getbufaddress(self._data), len(self))
    
    read = fromfile

    write = tofile

    ##### general object protocol
    
    def __repr__(self):
        if len(self._data) == 0:
            return "array('%s')" % self.typecode
        elif self.typecode == "c":
            return "array('%s', %s)" % (self.typecode, repr(self.tostring()))
        elif self.typecode == "u":
            return "array('%s', %s)" % (self.typecode, repr(self.tounicode()))
        else:
            return "array('%s', %s)" % (self.typecode, repr(self.tolist()))

    def __copy__(self):
        a = array(self.typecode)
        a._data = bytebuffer(len(self._data))
        a._data[:] = self._data
        return a

    def __eq__(self, other):
        if not isinstance(other, array):
            return NotImplemented
        if self.typecode == 'c':
            return buffer(self._data) == buffer(other._data)
        else:
            return self.tolist() == other.tolist()

    def __ne__(self, other):
        if not isinstance(other, array):
            return NotImplemented
        if self.typecode == 'c':
            return buffer(self._data) != buffer(other._data)
        else:
            return self.tolist() != other.tolist()

    def __lt__(self, other):
        if not isinstance(other, array):
            return NotImplemented
        if self.typecode == 'c':
            return buffer(self._data) < buffer(other._data)
        else:
            return self.tolist() < other.tolist()

    def __gt__(self, other):
        if not isinstance(other, array):
            return NotImplemented
        if self.typecode == 'c':
            return buffer(self._data) > buffer(other._data)
        else:
            return self.tolist() > other.tolist()

    def __le__(self, other):
        if not isinstance(other, array):
            return NotImplemented
        if self.typecode == 'c':
            return buffer(self._data) <= buffer(other._data)
        else:
            return self.tolist() <= other.tolist()

    def __ge__(self, other):
        if not isinstance(other, array):
            return NotImplemented
        if self.typecode == 'c':
            return buffer(self._data) >= buffer(other._data)
        else:
            return self.tolist() >= other.tolist()

    def __reduce__(self):
        dict = getattr(self, '__dict__', None)
        data = self.tostring()
        if data:
            initargs = (self.typecode, data)
        else:
            initargs = (self.typecode,)
        return (type(self), initargs, dict)

    ##### list methods
    
    def append(self, x):
        """Append new value x to the end of the array."""
        self._frombuffer(pack(self.typecode, x))

    def count(self, x):
        """Return number of occurences of x in the array."""
        return operator.countOf(self, x)

    def extend(self, iterable):
        """Append items to the end of the array."""
        if isinstance(iterable, array) \
                                    and not self.typecode == iterable.typecode:
            raise TypeError("can only extend with array of same kind")
        self._fromiterable(iterable)

    def index(self, x):
        """Return index of first occurence of x in the array."""
        return operator.indexOf(self, x)
    
    def insert(self, i, x):
        """Insert a new item x into the array before position i."""
        seqlength = len(self)
        if i < 0:
            i += seqlength
            if i < 0:
                i = 0
        elif i > seqlength:
            i = seqlength
        boundary = i * self.itemsize
        data = pack(self.typecode, x)
        newdata = bytebuffer(len(self._data) + len(data))
        newdata[:boundary] = self._data[:boundary]
        newdata[boundary:boundary+self.itemsize] = data
        newdata[boundary+self.itemsize:] = self._data[boundary:]
        self._data = newdata
        
    def pop(self, i=-1):
        """Return the i-th element and delete it from the array. i defaults to
        -1."""
        seqlength = len(self)
        if i < 0:
            i += seqlength
        if not (0 <= i < seqlength):
            raise IndexError(i)
        boundary = i * self.itemsize
        result = unpack_from(self.typecode, self._data, boundary)[0]
        newdata = bytebuffer(len(self._data) - self.itemsize)
        newdata[:boundary] = self._data[:boundary]
        newdata[boundary:] = self._data[boundary+self.itemsize:]
        self._data = newdata
        return result
        
    def remove(self, x):
        """Remove the first occurence of x in the array."""
        self.pop(self.index(x))
        
    def reverse(self):
        """Reverse the order of the items in the array."""
        lst = self.tolist()
        lst.reverse()
        self._clear()
        self.fromlist(lst)

    ##### list protocol
    
    def __len__(self):
        return len(self._data) // self.itemsize
    
    def __add__(self, other):
        if not isinstance(other, array):
            raise TypeError("can only append array to array")
        if self.typecode != other.typecode:
            raise TypeError("bad argument type for built-in operation")
        return array(self.typecode, buffer(self._data) + buffer(other._data))

    def __mul__(self, repeat):
        return array(self.typecode, buffer(self._data) * repeat)

    __rmul__ = __mul__

    def __getitem__(self, i):
        seqlength = len(self)
        if isinstance(i, slice):
            start, stop, step = i.indices(seqlength)
            if step != 1:
                sublist = self.tolist()[i]    # fall-back
                return array(self.typecode, sublist)
            if start < 0:
                start = 0
            if stop < start:
                stop = start
            assert stop <= seqlength
            return array(self.typecode, self._data[start * self.itemsize :
                                                   stop * self.itemsize])
        else:
            if i < 0:
                i += seqlength
            if self.typecode == 'c':  # speed trick
                return self._data[i]
            if not (0 <= i < seqlength):
                raise IndexError(i)
            boundary = i * self.itemsize
            return unpack_from(self.typecode, self._data, boundary)[0]

    def __getslice__(self, i, j):
        return self.__getitem__(slice(i, j))

    def __setitem__(self, i, x):
        if isinstance(i, slice):
            if (not isinstance(x, array)
                or self.typecode != x.typecode):
                raise TypeError("can only assign array of same kind"
                                " to array slice")
            seqlength = len(self)
            start, stop, step = i.indices(seqlength)
            if step != 1:
                sublist = self.tolist()    # fall-back
                sublist[i] = x.tolist()
                self._clear()
                self.fromlist(sublist)
                return
            if start < 0:
                start = 0
            if stop < start:
                stop = start
            assert stop <= seqlength
            boundary1 = start * self.itemsize
            boundary2 = stop * self.itemsize
            boundary2new = boundary1 + len(x._data)
            if boundary2 == boundary2new:
                self._data[boundary1:boundary2] = x._data
            else:
                newdata = bytebuffer(len(self._data) + boundary2new-boundary2)
                newdata[:boundary1] = self._data[:boundary1]
                newdata[boundary1:boundary2new] = x._data
                newdata[boundary2new:] = self._data[boundary2:]
                self._data = newdata
        else:
            seqlength = len(self)
            if i < 0:
                i += seqlength
            if self.typecode == 'c':  # speed trick
                self._data[i] = x
                return
            if not (0 <= i < seqlength):
                raise IndexError(i)
            boundary = i * self.itemsize
            pack_into(self.typecode, self._data, boundary, x)

    def __setslice__(self, i, j, x):
        self.__setitem__(slice(i, j), x)

    def __delitem__(self, i):
        if isinstance(i, slice):
            seqlength = len(self)
            start, stop, step = i.indices(seqlength)
            if start < 0:
                start = 0
            if stop < start:
                stop = start
            assert stop <= seqlength
            if step != 1:
                sublist = self.tolist()    # fall-back
                del sublist[i]
                self._clear()
                self.fromlist(sublist)
                return
            dellength = stop - start
            boundary1 = start * self.itemsize
            boundary2 = stop * self.itemsize
            newdata = bytebuffer(len(self._data) - (boundary2-boundary1))
            newdata[:boundary1] = self._data[:boundary1]
            newdata[boundary1:] = self._data[boundary2:]
            self._data = newdata
        else:            
            seqlength = len(self)
            if i < 0:
                i += seqlength
            if not (0 <= i < seqlength):
                raise IndexError(i)
            boundary = i * self.itemsize
            newdata = bytebuffer(len(self._data) - self.itemsize)
            newdata[:boundary] = self._data[:boundary]
            newdata[boundary:] = self._data[boundary+self.itemsize:]
            self._data = newdata

    def __delslice__(self, i, j):
        self.__delitem__(slice(i, j))

    def __contains__(self, item):
        for x in self:
            if x == item:
                return True
        return False

    def __iadd__(self, other):
        if not isinstance(other, array):
            raise TypeError("can only extend array with array")
        self.extend(other)
        return self

    def __imul__(self, repeat):
        newdata = buffer(self._data) * repeat
        self._data = bytebuffer(len(newdata))
        self._data[:] = newdata
        return self

    def __iter__(self):
        p = 0
        typecode = self.typecode
        itemsize = self.itemsize
        while p < len(self._data):
            yield unpack_from(typecode, self._data, p)[0]
            p += itemsize

    ##### internal methods

    def _fromiterable(self, iterable):
        iterable = tuple(iterable)
        n = len(iterable)
        boundary = len(self._data)
        newdata = bytebuffer(boundary + n * self.itemsize)
        newdata[:boundary] = self._data
        pack_into('%d%s' % (n, self.typecode), newdata, boundary, *iterable)
        self._data = newdata

ArrayType = array
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.