1"""Persistent Data Types
2
3"""
4
5import operator as op
6import sys
7
8from collections import OrderedDict
9from contextlib import contextmanager
10from shutil import rmtree
11
12from .core import BytesType, Cache, ENOVAL, TextType
13
14############################################################################
15# BEGIN Python 2/3 Shims
16############################################################################
17
18try:
19    from collections.abc import MutableMapping, Sequence
20    from collections.abc import KeysView, ValuesView, ItemsView
21except ImportError:
22    from collections import MutableMapping, Sequence
23    from collections import KeysView, ValuesView, ItemsView
24
25if sys.hexversion < 0x03000000:
26    from itertools import izip as zip  # pylint: disable=redefined-builtin,no-name-in-module,ungrouped-imports
27    range = xrange  # pylint: disable=redefined-builtin,invalid-name,undefined-variable
28
29############################################################################
30# END Python 2/3 Shims
31############################################################################
32
33
34def _make_compare(seq_op, doc):
35    "Make compare method with Sequence semantics."
36    def compare(self, that):
37        "Compare method for deque and sequence."
38        if not isinstance(that, Sequence):
39            return NotImplemented
40
41        len_self = len(self)
42        len_that = len(that)
43
44        if len_self != len_that:
45            if seq_op is op.eq:
46                return False
47            if seq_op is op.ne:
48                return True
49
50        for alpha, beta in zip(self, that):
51            if alpha != beta:
52                return seq_op(alpha, beta)
53
54        return seq_op(len_self, len_that)
55
56    compare.__name__ = '__{0}__'.format(seq_op.__name__)
57    doc_str = 'Return True if and only if deque is {0} `that`.'
58    compare.__doc__ = doc_str.format(doc)
59
60    return compare
61
62
63class Deque(Sequence):
64    """Persistent sequence with double-ended queue semantics.
65
66    Double-ended queue is an ordered collection with optimized access at its
67    endpoints.
68
69    Items are serialized to disk. Deque may be initialized from directory path
70    where items are stored.
71
72    >>> deque = Deque()
73    >>> deque += range(5)
74    >>> list(deque)
75    [0, 1, 2, 3, 4]
76    >>> for value in range(5):
77    ...     deque.appendleft(-value)
78    >>> len(deque)
79    10
80    >>> list(deque)
81    [-4, -3, -2, -1, 0, 0, 1, 2, 3, 4]
82    >>> deque.pop()
83    4
84    >>> deque.popleft()
85    -4
86    >>> deque.reverse()
87    >>> list(deque)
88    [3, 2, 1, 0, 0, -1, -2, -3]
89
90    """
91    def __init__(self, iterable=(), directory=None):
92        """Initialize deque instance.
93
94        If directory is None then temporary directory created. The directory
95        will *not* be automatically removed.
96
97        :param iterable: iterable of items to append to deque
98        :param directory: deque directory (default None)
99
100        """
101        self._cache = Cache(directory, eviction_policy='none')
102        with self.transact():
103            self.extend(iterable)
104
105
106    @classmethod
107    def fromcache(cls, cache, iterable=()):
108        """Initialize deque using `cache`.
109
110        >>> cache = Cache()
111        >>> deque = Deque.fromcache(cache, [5, 6, 7, 8])
112        >>> deque.cache is cache
113        True
114        >>> len(deque)
115        4
116        >>> 7 in deque
117        True
118        >>> deque.popleft()
119        5
120
121        :param Cache cache: cache to use
122        :param iterable: iterable of items
123        :return: initialized Deque
124
125        """
126        # pylint: disable=no-member,protected-access
127        self = cls.__new__(cls)
128        self._cache = cache
129        self.extend(iterable)
130        return self
131
132
133    @property
134    def cache(self):
135        "Cache used by deque."
136        return self._cache
137
138
139    @property
140    def directory(self):
141        "Directory path where deque is stored."
142        return self._cache.directory
143
144
145    def _index(self, index, func):
146        len_self = len(self)
147
148        if index >= 0:
149            if index >= len_self:
150                raise IndexError('deque index out of range')
151
152            for key in self._cache.iterkeys():
153                if index == 0:
154                    try:
155                        return func(key)
156                    except KeyError:
157                        continue
158                index -= 1
159        else:
160            if index < -len_self:
161                raise IndexError('deque index out of range')
162
163            index += 1
164
165            for key in self._cache.iterkeys(reverse=True):
166                if index == 0:
167                    try:
168                        return func(key)
169                    except KeyError:
170                        continue
171                index += 1
172
173        raise IndexError('deque index out of range')
174
175
176    def __getitem__(self, index):
177        """deque.__getitem__(index) <==> deque[index]
178
179        Return corresponding item for `index` in deque.
180
181        See also `Deque.peekleft` and `Deque.peek` for indexing deque at index
182        ``0`` or ``-1``.
183
184        >>> deque = Deque()
185        >>> deque.extend('abcde')
186        >>> deque[1]
187        'b'
188        >>> deque[-2]
189        'd'
190
191        :param int index: index of item
192        :return: corresponding item
193        :raises IndexError: if index out of range
194
195        """
196        return self._index(index, self._cache.__getitem__)
197
198
199    def __setitem__(self, index, value):
200        """deque.__setitem__(index, value) <==> deque[index] = value
201
202        Store `value` in deque at `index`.
203
204        >>> deque = Deque()
205        >>> deque.extend([None] * 3)
206        >>> deque[0] = 'a'
207        >>> deque[1] = 'b'
208        >>> deque[-1] = 'c'
209        >>> ''.join(deque)
210        'abc'
211
212        :param int index: index of value
213        :param value: value to store
214        :raises IndexError: if index out of range
215
216        """
217        set_value = lambda key: self._cache.__setitem__(key, value)
218        self._index(index, set_value)
219
220
221    def __delitem__(self, index):
222        """deque.__delitem__(index) <==> del deque[index]
223
224        Delete item in deque at `index`.
225
226        >>> deque = Deque()
227        >>> deque.extend([None] * 3)
228        >>> del deque[0]
229        >>> del deque[1]
230        >>> del deque[-1]
231        >>> len(deque)
232        0
233
234        :param int index: index of item
235        :raises IndexError: if index out of range
236
237        """
238        self._index(index, self._cache.__delitem__)
239
240
241    def __repr__(self):
242        """deque.__repr__() <==> repr(deque)
243
244        Return string with printable representation of deque.
245
246        """
247        name = type(self).__name__
248        return '{0}(directory={1!r})'.format(name, self.directory)
249
250
251    __eq__ = _make_compare(op.eq, 'equal to')
252    __ne__ = _make_compare(op.ne, 'not equal to')
253    __lt__ = _make_compare(op.lt, 'less than')
254    __gt__ = _make_compare(op.gt, 'greater than')
255    __le__ = _make_compare(op.le, 'less than or equal to')
256    __ge__ = _make_compare(op.ge, 'greater than or equal to')
257
258
259    def __iadd__(self, iterable):
260        """deque.__iadd__(iterable) <==> deque += iterable
261
262        Extend back side of deque with items from iterable.
263
264        :param iterable: iterable of items to append to deque
265        :return: deque with added items
266
267        """
268        self.extend(iterable)
269        return self
270
271
272    def __iter__(self):
273        """deque.__iter__() <==> iter(deque)
274
275        Return iterator of deque from front to back.
276
277        """
278        _cache = self._cache
279
280        for key in _cache.iterkeys():
281            try:
282                yield _cache[key]
283            except KeyError:
284                pass
285
286
287    def __len__(self):
288        """deque.__len__() <==> len(deque)
289
290        Return length of deque.
291
292        """
293        return len(self._cache)
294
295
296    def __reversed__(self):
297        """deque.__reversed__() <==> reversed(deque)
298
299        Return iterator of deque from back to front.
300
301        >>> deque = Deque()
302        >>> deque.extend('abcd')
303        >>> iterator = reversed(deque)
304        >>> next(iterator)
305        'd'
306        >>> list(iterator)
307        ['c', 'b', 'a']
308
309        """
310        _cache = self._cache
311
312        for key in _cache.iterkeys(reverse=True):
313            try:
314                yield _cache[key]
315            except KeyError:
316                pass
317
318
319    def __getstate__(self):
320        return self.directory
321
322
323    def __setstate__(self, state):
324        self.__init__(directory=state)
325
326
327    def append(self, value):
328        """Add `value` to back of deque.
329
330        >>> deque = Deque()
331        >>> deque.append('a')
332        >>> deque.append('b')
333        >>> deque.append('c')
334        >>> list(deque)
335        ['a', 'b', 'c']
336
337        :param value: value to add to back of deque
338
339        """
340        self._cache.push(value, retry=True)
341
342
343    def appendleft(self, value):
344        """Add `value` to front of deque.
345
346        >>> deque = Deque()
347        >>> deque.appendleft('a')
348        >>> deque.appendleft('b')
349        >>> deque.appendleft('c')
350        >>> list(deque)
351        ['c', 'b', 'a']
352
353        :param value: value to add to front of deque
354
355        """
356        self._cache.push(value, side='front', retry=True)
357
358
359    def clear(self):
360        """Remove all elements from deque.
361
362        >>> deque = Deque('abc')
363        >>> len(deque)
364        3
365        >>> deque.clear()
366        >>> list(deque)
367        []
368
369        """
370        self._cache.clear(retry=True)
371
372
373    def count(self, value):
374        """Return number of occurrences of `value` in deque.
375
376        >>> deque = Deque()
377        >>> deque += [num for num in range(1, 5) for _ in range(num)]
378        >>> deque.count(0)
379        0
380        >>> deque.count(1)
381        1
382        >>> deque.count(4)
383        4
384
385        :param value: value to count in deque
386        :return: count of items equal to value in deque
387
388        """
389        return sum(1 for item in self if value == item)
390
391
392    def extend(self, iterable):
393        """Extend back side of deque with values from `iterable`.
394
395        :param iterable: iterable of values
396
397        """
398        for value in iterable:
399            self.append(value)
400
401
402    def extendleft(self, iterable):
403        """Extend front side of deque with value from `iterable`.
404
405        >>> deque = Deque()
406        >>> deque.extendleft('abc')
407        >>> list(deque)
408        ['c', 'b', 'a']
409
410        :param iterable: iterable of values
411
412        """
413        for value in iterable:
414            self.appendleft(value)
415
416
417    def peek(self):
418        """Peek at value at back of deque.
419
420        Faster than indexing deque at -1.
421
422        If deque is empty then raise IndexError.
423
424        >>> deque = Deque()
425        >>> deque.peek()
426        Traceback (most recent call last):
427            ...
428        IndexError: peek from an empty deque
429        >>> deque += 'abc'
430        >>> deque.peek()
431        'c'
432
433        :return: value at back of deque
434        :raises IndexError: if deque is empty
435
436        """
437        default = None, ENOVAL
438        _, value = self._cache.peek(default=default, side='back', retry=True)
439        if value is ENOVAL:
440            raise IndexError('peek from an empty deque')
441        return value
442
443
444    def peekleft(self):
445        """Peek at value at back of deque.
446
447        Faster than indexing deque at 0.
448
449        If deque is empty then raise IndexError.
450
451        >>> deque = Deque()
452        >>> deque.peekleft()
453        Traceback (most recent call last):
454            ...
455        IndexError: peek from an empty deque
456        >>> deque += 'abc'
457        >>> deque.peekleft()
458        'a'
459
460        :return: value at front of deque
461        :raises IndexError: if deque is empty
462
463        """
464        default = None, ENOVAL
465        _, value = self._cache.peek(default=default, side='front', retry=True)
466        if value is ENOVAL:
467            raise IndexError('peek from an empty deque')
468        return value
469
470
471    def pop(self):
472        """Remove and return value at back of deque.
473
474        If deque is empty then raise IndexError.
475
476        >>> deque = Deque()
477        >>> deque += 'ab'
478        >>> deque.pop()
479        'b'
480        >>> deque.pop()
481        'a'
482        >>> deque.pop()
483        Traceback (most recent call last):
484            ...
485        IndexError: pop from an empty deque
486
487        :return: value at back of deque
488        :raises IndexError: if deque is empty
489
490        """
491        default = None, ENOVAL
492        _, value = self._cache.pull(default=default, side='back', retry=True)
493        if value is ENOVAL:
494            raise IndexError('pop from an empty deque')
495        return value
496
497
498    def popleft(self):
499        """Remove and return value at front of deque.
500
501        >>> deque = Deque()
502        >>> deque += 'ab'
503        >>> deque.popleft()
504        'a'
505        >>> deque.popleft()
506        'b'
507        >>> deque.popleft()
508        Traceback (most recent call last):
509            ...
510        IndexError: pop from an empty deque
511
512        :return: value at front of deque
513        :raises IndexError: if deque is empty
514
515        """
516        default = None, ENOVAL
517        _, value = self._cache.pull(default=default, retry=True)
518        if value is ENOVAL:
519            raise IndexError('pop from an empty deque')
520        return value
521
522
523    def remove(self, value):
524        """Remove first occurrence of `value` in deque.
525
526        >>> deque = Deque()
527        >>> deque += 'aab'
528        >>> deque.remove('a')
529        >>> list(deque)
530        ['a', 'b']
531        >>> deque.remove('b')
532        >>> list(deque)
533        ['a']
534        >>> deque.remove('c')
535        Traceback (most recent call last):
536            ...
537        ValueError: deque.remove(value): value not in deque
538
539        :param value: value to remove
540        :raises ValueError: if value not in deque
541
542        """
543        _cache = self._cache
544
545        for key in _cache.iterkeys():
546            try:
547                item = _cache[key]
548            except KeyError:
549                continue
550            else:
551                if value == item:
552                    try:
553                        del _cache[key]
554                    except KeyError:
555                        continue
556                    return
557
558        raise ValueError('deque.remove(value): value not in deque')
559
560
561    def reverse(self):
562        """Reverse deque in place.
563
564        >>> deque = Deque()
565        >>> deque += 'abc'
566        >>> deque.reverse()
567        >>> list(deque)
568        ['c', 'b', 'a']
569
570        """
571        # GrantJ 2019-03-22 Consider using an algorithm that swaps the values
572        # at two keys. Like self._cache.swap(key1, key2, retry=True) The swap
573        # method would exchange the values at two given keys. Then, using a
574        # forward iterator and a reverse iterator, the reversis method could
575        # avoid making copies of the values.
576        temp = Deque(iterable=reversed(self))
577        self.clear()
578        self.extend(temp)
579        directory = temp.directory
580        del temp
581        rmtree(directory)
582
583
584    def rotate(self, steps=1):
585        """Rotate deque right by `steps`.
586
587        If steps is negative then rotate left.
588
589        >>> deque = Deque()
590        >>> deque += range(5)
591        >>> deque.rotate(2)
592        >>> list(deque)
593        [3, 4, 0, 1, 2]
594        >>> deque.rotate(-1)
595        >>> list(deque)
596        [4, 0, 1, 2, 3]
597
598        :param int steps: number of steps to rotate (default 1)
599
600        """
601        if not isinstance(steps, int):
602            type_name = type(steps).__name__
603            raise TypeError('integer argument expected, got %s' % type_name)
604
605        len_self = len(self)
606
607        if not len_self:
608            return
609
610        if steps >= 0:
611            steps %= len_self
612
613            for _ in range(steps):
614                try:
615                    value = self.pop()
616                except IndexError:
617                    return
618                else:
619                    self.appendleft(value)
620        else:
621            steps *= -1
622            steps %= len_self
623
624            for _ in range(steps):
625                try:
626                    value = self.popleft()
627                except IndexError:
628                    return
629                else:
630                    self.append(value)
631
632
633    __hash__ = None
634
635
636    @contextmanager
637    def transact(self):
638        """Context manager to perform a transaction by locking the deque.
639
640        While the deque is locked, no other write operation is permitted.
641        Transactions should therefore be as short as possible. Read and write
642        operations performed in a transaction are atomic. Read operations may
643        occur concurrent to a transaction.
644
645        Transactions may be nested and may not be shared between threads.
646
647        >>> from diskcache import Deque
648        >>> deque = Deque()
649        >>> deque += range(5)
650        >>> with deque.transact():  # Atomically rotate elements.
651        ...     value = deque.pop()
652        ...     deque.appendleft(value)
653        >>> list(deque)
654        [4, 0, 1, 2, 3]
655
656        :return: context manager for use in `with` statement
657
658        """
659        with self._cache.transact(retry=True):
660            yield
661
662
663class Index(MutableMapping):
664    """Persistent mutable mapping with insertion order iteration.
665
666    Items are serialized to disk. Index may be initialized from directory path
667    where items are stored.
668
669    Hashing protocol is not used. Keys are looked up by their serialized
670    format. See ``diskcache.Disk`` for details.
671
672    >>> index = Index()
673    >>> index.update([('a', 1), ('b', 2), ('c', 3)])
674    >>> index['a']
675    1
676    >>> list(index)
677    ['a', 'b', 'c']
678    >>> len(index)
679    3
680    >>> del index['b']
681    >>> index.popitem()
682    ('c', 3)
683
684    """
685    def __init__(self, *args, **kwargs):
686        """Initialize index in directory and update items.
687
688        Optional first argument may be string specifying directory where items
689        are stored. When None or not given, temporary directory is created.
690
691        >>> index = Index({'a': 1, 'b': 2, 'c': 3})
692        >>> len(index)
693        3
694        >>> directory = index.directory
695        >>> inventory = Index(directory, d=4)
696        >>> inventory['b']
697        2
698        >>> len(inventory)
699        4
700
701        """
702        if args and isinstance(args[0], (BytesType, TextType)):
703            directory = args[0]
704            args = args[1:]
705        else:
706            if args and args[0] is None:
707                args = args[1:]
708            directory = None
709        self._cache = Cache(directory, eviction_policy='none')
710        self.update(*args, **kwargs)
711
712
713    @classmethod
714    def fromcache(cls, cache, *args, **kwargs):
715        """Initialize index using `cache` and update items.
716
717        >>> cache = Cache()
718        >>> index = Index.fromcache(cache, {'a': 1, 'b': 2, 'c': 3})
719        >>> index.cache is cache
720        True
721        >>> len(index)
722        3
723        >>> 'b' in index
724        True
725        >>> index['c']
726        3
727
728        :param Cache cache: cache to use
729        :param args: mapping or sequence of items
730        :param kwargs: mapping of items
731        :return: initialized Index
732
733        """
734        # pylint: disable=no-member,protected-access
735        self = cls.__new__(cls)
736        self._cache = cache
737        self.update(*args, **kwargs)
738        return self
739
740
741    @property
742    def cache(self):
743        "Cache used by index."
744        return self._cache
745
746
747    @property
748    def directory(self):
749        "Directory path where items are stored."
750        return self._cache.directory
751
752
753    def __getitem__(self, key):
754        """index.__getitem__(key) <==> index[key]
755
756        Return corresponding value for `key` in index.
757
758        >>> index = Index()
759        >>> index.update({'a': 1, 'b': 2})
760        >>> index['a']
761        1
762        >>> index['b']
763        2
764        >>> index['c']
765        Traceback (most recent call last):
766            ...
767        KeyError: 'c'
768
769        :param key: key for item
770        :return: value for item in index with given key
771        :raises KeyError: if key is not found
772
773        """
774        return self._cache[key]
775
776
777    def __setitem__(self, key, value):
778        """index.__setitem__(key, value) <==> index[key] = value
779
780        Set `key` and `value` item in index.
781
782        >>> index = Index()
783        >>> index['a'] = 1
784        >>> index[0] = None
785        >>> len(index)
786        2
787
788        :param key: key for item
789        :param value: value for item
790
791        """
792        self._cache[key] = value
793
794
795    def __delitem__(self, key):
796        """index.__delitem__(key) <==> del index[key]
797
798        Delete corresponding item for `key` from index.
799
800        >>> index = Index()
801        >>> index.update({'a': 1, 'b': 2})
802        >>> del index['a']
803        >>> del index['b']
804        >>> len(index)
805        0
806        >>> del index['c']
807        Traceback (most recent call last):
808            ...
809        KeyError: 'c'
810
811        :param key: key for item
812        :raises KeyError: if key is not found
813
814        """
815        del self._cache[key]
816
817
818    def setdefault(self, key, default=None):
819        """Set and get value for `key` in index using `default`.
820
821        If `key` is not in index then set corresponding value to `default`. If
822        `key` is in index then ignore `default` and return existing value.
823
824        >>> index = Index()
825        >>> index.setdefault('a', 0)
826        0
827        >>> index.setdefault('a', 1)
828        0
829
830        :param key: key for item
831        :param default: value if key is missing (default None)
832        :return: value for item in index with given key
833
834        """
835        _cache = self._cache
836        while True:
837            try:
838                return _cache[key]
839            except KeyError:
840                _cache.add(key, default, retry=True)
841
842
843    def peekitem(self, last=True):
844        """Peek at key and value item pair in index based on iteration order.
845
846        >>> index = Index()
847        >>> for num, letter in enumerate('xyz'):
848        ...     index[letter] = num
849        >>> index.peekitem()
850        ('z', 2)
851        >>> index.peekitem(last=False)
852        ('x', 0)
853
854        :param bool last: last item in iteration order (default True)
855        :return: key and value item pair
856        :raises KeyError: if cache is empty
857
858        """
859        return self._cache.peekitem(last, retry=True)
860
861
862    def pop(self, key, default=ENOVAL):
863        """Remove corresponding item for `key` from index and return value.
864
865        If `key` is missing then return `default`. If `default` is `ENOVAL`
866        then raise KeyError.
867
868        >>> index = Index({'a': 1, 'b': 2})
869        >>> index.pop('a')
870        1
871        >>> index.pop('b')
872        2
873        >>> index.pop('c', default=3)
874        3
875        >>> index.pop('d')
876        Traceback (most recent call last):
877            ...
878        KeyError: 'd'
879
880        :param key: key for item
881        :param default: return value if key is missing (default ENOVAL)
882        :return: value for item if key is found else default
883        :raises KeyError: if key is not found and default is ENOVAL
884
885        """
886        _cache = self._cache
887        value = _cache.pop(key, default=default, retry=True)
888        if value is ENOVAL:
889            raise KeyError(key)
890        return value
891
892
893    def popitem(self, last=True):
894        """Remove and return item pair.
895
896        Item pairs are returned in last-in-first-out (LIFO) order if last is
897        True else first-in-first-out (FIFO) order. LIFO order imitates a stack
898        and FIFO order imitates a queue.
899
900        >>> index = Index()
901        >>> index.update([('a', 1), ('b', 2), ('c', 3)])
902        >>> index.popitem()
903        ('c', 3)
904        >>> index.popitem(last=False)
905        ('a', 1)
906        >>> index.popitem()
907        ('b', 2)
908        >>> index.popitem()
909        Traceback (most recent call last):
910          ...
911        KeyError: 'dictionary is empty'
912
913        :param bool last: pop last item pair (default True)
914        :return: key and value item pair
915        :raises KeyError: if index is empty
916
917        """
918        # pylint: disable=arguments-differ
919        _cache = self._cache
920
921        with _cache.transact(retry=True):
922            key, value = _cache.peekitem(last=last)
923            del _cache[key]
924
925        return key, value
926
927
928    def push(self, value, prefix=None, side='back'):
929        """Push `value` onto `side` of queue in index identified by `prefix`.
930
931        When prefix is None, integer keys are used. Otherwise, string keys are
932        used in the format "prefix-integer". Integer starts at 500 trillion.
933
934        Defaults to pushing value on back of queue. Set side to 'front' to push
935        value on front of queue. Side must be one of 'back' or 'front'.
936
937        See also `Index.pull`.
938
939        >>> index = Index()
940        >>> print(index.push('apples'))
941        500000000000000
942        >>> print(index.push('beans'))
943        500000000000001
944        >>> print(index.push('cherries', side='front'))
945        499999999999999
946        >>> index[500000000000001]
947        'beans'
948        >>> index.push('dates', prefix='fruit')
949        'fruit-500000000000000'
950
951        :param value: value for item
952        :param str prefix: key prefix (default None, key is integer)
953        :param str side: either 'back' or 'front' (default 'back')
954        :return: key for item in cache
955
956        """
957        return self._cache.push(value, prefix, side, retry=True)
958
959
960    def pull(self, prefix=None, default=(None, None), side='front'):
961        """Pull key and value item pair from `side` of queue in index.
962
963        When prefix is None, integer keys are used. Otherwise, string keys are
964        used in the format "prefix-integer". Integer starts at 500 trillion.
965
966        If queue is empty, return default.
967
968        Defaults to pulling key and value item pairs from front of queue. Set
969        side to 'back' to pull from back of queue. Side must be one of 'front'
970        or 'back'.
971
972        See also `Index.push`.
973
974        >>> index = Index()
975        >>> for letter in 'abc':
976        ...     print(index.push(letter))
977        500000000000000
978        500000000000001
979        500000000000002
980        >>> key, value = index.pull()
981        >>> print(key)
982        500000000000000
983        >>> value
984        'a'
985        >>> _, value = index.pull(side='back')
986        >>> value
987        'c'
988        >>> index.pull(prefix='fruit')
989        (None, None)
990
991        :param str prefix: key prefix (default None, key is integer)
992        :param default: value to return if key is missing
993            (default (None, None))
994        :param str side: either 'front' or 'back' (default 'front')
995        :return: key and value item pair or default if queue is empty
996
997        """
998        return self._cache.pull(prefix, default, side, retry=True)
999
1000
1001    def clear(self):
1002        """Remove all items from index.
1003
1004        >>> index = Index({'a': 0, 'b': 1, 'c': 2})
1005        >>> len(index)
1006        3
1007        >>> index.clear()
1008        >>> dict(index)
1009        {}
1010
1011        """
1012        self._cache.clear(retry=True)
1013
1014
1015    def __iter__(self):
1016        """index.__iter__() <==> iter(index)
1017
1018        Return iterator of index keys in insertion order.
1019
1020        """
1021        return iter(self._cache)
1022
1023
1024    def __reversed__(self):
1025        """index.__reversed__() <==> reversed(index)
1026
1027        Return iterator of index keys in reversed insertion order.
1028
1029        >>> index = Index()
1030        >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1031        >>> iterator = reversed(index)
1032        >>> next(iterator)
1033        'c'
1034        >>> list(iterator)
1035        ['b', 'a']
1036
1037        """
1038        return reversed(self._cache)
1039
1040
1041    def __len__(self):
1042        """index.__len__() <==> len(index)
1043
1044        Return length of index.
1045
1046        """
1047        return len(self._cache)
1048
1049
1050    if sys.hexversion < 0x03000000:
1051        def keys(self):
1052            """List of index keys.
1053
1054            >>> index = Index()
1055            >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1056            >>> index.keys()
1057            ['a', 'b', 'c']
1058
1059            :return: list of keys
1060
1061            """
1062            return list(self._cache)
1063
1064
1065        def values(self):
1066            """List of index values.
1067
1068            >>> index = Index()
1069            >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1070            >>> index.values()
1071            [1, 2, 3]
1072
1073            :return: list of values
1074
1075            """
1076            return list(self.itervalues())
1077
1078
1079        def items(self):
1080            """List of index items.
1081
1082            >>> index = Index()
1083            >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1084            >>> index.items()
1085            [('a', 1), ('b', 2), ('c', 3)]
1086
1087            :return: list of items
1088
1089            """
1090            return list(self.iteritems())
1091
1092
1093        def iterkeys(self):
1094            """Iterator of index keys.
1095
1096            >>> index = Index()
1097            >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1098            >>> list(index.iterkeys())
1099            ['a', 'b', 'c']
1100
1101            :return: iterator of keys
1102
1103            """
1104            return iter(self._cache)
1105
1106
1107        def itervalues(self):
1108            """Iterator of index values.
1109
1110            >>> index = Index()
1111            >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1112            >>> list(index.itervalues())
1113            [1, 2, 3]
1114
1115            :return: iterator of values
1116
1117            """
1118            _cache = self._cache
1119
1120            for key in _cache:
1121                while True:
1122                    try:
1123                        yield _cache[key]
1124                    except KeyError:
1125                        pass
1126                    break
1127
1128
1129        def iteritems(self):
1130            """Iterator of index items.
1131
1132            >>> index = Index()
1133            >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1134            >>> list(index.iteritems())
1135            [('a', 1), ('b', 2), ('c', 3)]
1136
1137            :return: iterator of items
1138
1139            """
1140            _cache = self._cache
1141
1142            for key in _cache:
1143                while True:
1144                    try:
1145                        yield key, _cache[key]
1146                    except KeyError:
1147                        pass
1148                    break
1149
1150
1151        def viewkeys(self):
1152            """Set-like object providing a view of index keys.
1153
1154            >>> index = Index()
1155            >>> index.update({'a': 1, 'b': 2, 'c': 3})
1156            >>> keys_view = index.viewkeys()
1157            >>> 'b' in keys_view
1158            True
1159
1160            :return: keys view
1161
1162            """
1163            return KeysView(self)
1164
1165
1166        def viewvalues(self):
1167            """Set-like object providing a view of index values.
1168
1169            >>> index = Index()
1170            >>> index.update({'a': 1, 'b': 2, 'c': 3})
1171            >>> values_view = index.viewvalues()
1172            >>> 2 in values_view
1173            True
1174
1175            :return: values view
1176
1177            """
1178            return ValuesView(self)
1179
1180
1181        def viewitems(self):
1182            """Set-like object providing a view of index items.
1183
1184            >>> index = Index()
1185            >>> index.update({'a': 1, 'b': 2, 'c': 3})
1186            >>> items_view = index.viewitems()
1187            >>> ('b', 2) in items_view
1188            True
1189
1190            :return: items view
1191
1192            """
1193            return ItemsView(self)
1194
1195
1196    else:
1197        def keys(self):
1198            """Set-like object providing a view of index keys.
1199
1200            >>> index = Index()
1201            >>> index.update({'a': 1, 'b': 2, 'c': 3})
1202            >>> keys_view = index.keys()
1203            >>> 'b' in keys_view
1204            True
1205
1206            :return: keys view
1207
1208            """
1209            return KeysView(self)
1210
1211
1212        def values(self):
1213            """Set-like object providing a view of index values.
1214
1215            >>> index = Index()
1216            >>> index.update({'a': 1, 'b': 2, 'c': 3})
1217            >>> values_view = index.values()
1218            >>> 2 in values_view
1219            True
1220
1221            :return: values view
1222
1223            """
1224            return ValuesView(self)
1225
1226
1227        def items(self):
1228            """Set-like object providing a view of index items.
1229
1230            >>> index = Index()
1231            >>> index.update({'a': 1, 'b': 2, 'c': 3})
1232            >>> items_view = index.items()
1233            >>> ('b', 2) in items_view
1234            True
1235
1236            :return: items view
1237
1238            """
1239            return ItemsView(self)
1240
1241
1242    __hash__ = None
1243
1244
1245    def __getstate__(self):
1246        return self.directory
1247
1248
1249    def __setstate__(self, state):
1250        self.__init__(state)
1251
1252
1253    def __eq__(self, other):
1254        """index.__eq__(other) <==> index == other
1255
1256        Compare equality for index and `other`.
1257
1258        Comparison to another index or ordered dictionary is
1259        order-sensitive. Comparison to all other mappings is order-insensitive.
1260
1261        >>> index = Index()
1262        >>> pairs = [('a', 1), ('b', 2), ('c', 3)]
1263        >>> index.update(pairs)
1264        >>> from collections import OrderedDict
1265        >>> od = OrderedDict(pairs)
1266        >>> index == od
1267        True
1268        >>> index == {'c': 3, 'b': 2, 'a': 1}
1269        True
1270
1271        :param other: other mapping in equality comparison
1272        :return: True if index equals other
1273
1274        """
1275        if len(self) != len(other):
1276            return False
1277
1278        if isinstance(other, (Index, OrderedDict)):
1279            alpha = ((key, self[key]) for key in self)
1280            beta = ((key, other[key]) for key in other)
1281            pairs = zip(alpha, beta)
1282            return not any(a != x or b != y for (a, b), (x, y) in pairs)
1283        else:
1284            return all(self[key] == other.get(key, ENOVAL) for key in self)
1285
1286
1287    def __ne__(self, other):
1288        """index.__ne__(other) <==> index != other
1289
1290        Compare inequality for index and `other`.
1291
1292        Comparison to another index or ordered dictionary is
1293        order-sensitive. Comparison to all other mappings is order-insensitive.
1294
1295        >>> index = Index()
1296        >>> index.update([('a', 1), ('b', 2), ('c', 3)])
1297        >>> from collections import OrderedDict
1298        >>> od = OrderedDict([('c', 3), ('b', 2), ('a', 1)])
1299        >>> index != od
1300        True
1301        >>> index != {'a': 1, 'b': 2}
1302        True
1303
1304        :param other: other mapping in inequality comparison
1305        :return: True if index does not equal other
1306
1307        """
1308        return not self == other
1309
1310
1311    def memoize(self, name=None, typed=False):
1312        """Memoizing cache decorator.
1313
1314        Decorator to wrap callable with memoizing function using cache.
1315        Repeated calls with the same arguments will lookup result in cache and
1316        avoid function evaluation.
1317
1318        If name is set to None (default), the callable name will be determined
1319        automatically.
1320
1321        If typed is set to True, function arguments of different types will be
1322        cached separately. For example, f(3) and f(3.0) will be treated as
1323        distinct calls with distinct results.
1324
1325        The original underlying function is accessible through the __wrapped__
1326        attribute. This is useful for introspection, for bypassing the cache,
1327        or for rewrapping the function with a different cache.
1328
1329        >>> from diskcache import Index
1330        >>> mapping = Index()
1331        >>> @mapping.memoize()
1332        ... def fibonacci(number):
1333        ...     if number == 0:
1334        ...         return 0
1335        ...     elif number == 1:
1336        ...         return 1
1337        ...     else:
1338        ...         return fibonacci(number - 1) + fibonacci(number - 2)
1339        >>> print(fibonacci(100))
1340        354224848179261915075
1341
1342        An additional `__cache_key__` attribute can be used to generate the
1343        cache key used for the given arguments.
1344
1345        >>> key = fibonacci.__cache_key__(100)
1346        >>> print(mapping[key])
1347        354224848179261915075
1348
1349        Remember to call memoize when decorating a callable. If you forget,
1350        then a TypeError will occur. Note the lack of parenthenses after
1351        memoize below:
1352
1353        >>> @mapping.memoize
1354        ... def test():
1355        ...     pass
1356        Traceback (most recent call last):
1357            ...
1358        TypeError: name cannot be callable
1359
1360        :param str name: name given for callable (default None, automatic)
1361        :param bool typed: cache different types separately (default False)
1362        :return: callable decorator
1363
1364        """
1365        return self._cache.memoize(name, typed)
1366
1367
1368    @contextmanager
1369    def transact(self):
1370        """Context manager to perform a transaction by locking the index.
1371
1372        While the index is locked, no other write operation is permitted.
1373        Transactions should therefore be as short as possible. Read and write
1374        operations performed in a transaction are atomic. Read operations may
1375        occur concurrent to a transaction.
1376
1377        Transactions may be nested and may not be shared between threads.
1378
1379        >>> from diskcache import Index
1380        >>> mapping = Index()
1381        >>> with mapping.transact():  # Atomically increment two keys.
1382        ...     mapping['total'] = mapping.get('total', 0) + 123.4
1383        ...     mapping['count'] = mapping.get('count', 0) + 1
1384        >>> with mapping.transact():  # Atomically calculate average.
1385        ...     average = mapping['total'] / mapping['count']
1386        >>> average
1387        123.4
1388
1389        :return: context manager for use in `with` statement
1390
1391        """
1392        with self._cache.transact(retry=True):
1393            yield
1394
1395
1396    def __repr__(self):
1397        """index.__repr__() <==> repr(index)
1398
1399        Return string with printable representation of index.
1400
1401        """
1402        name = type(self).__name__
1403        return '{0}({1!r})'.format(name, self.directory)
1404