@@ -0,0 +1,2798 @@
+import itertools%0Aimport random%0Aimport six%0A%0A%0Aclass RandomAccessQueue(object):%0A    %22%22%22FIFO queue with fast indexing%0A%0A    Operations getitem, setitem, append, popleft, and len%0A    are amortized O(1)-time, if this data structure is used ephemerally.%0A    %22%22%22%0A%0A    def __init__(self, *args, **kwargs):%0A        self._queue_front = %5B%5D%0A        self._queue_back = list(*args, **kwargs)%0A%0A    def __iter__(self):%0A        return itertools.chain(reversed(self._queue_front),%0A                               iter(self._queue_back))%0A%0A    def __repr__(self):%0A        return %22RandomAccessQueue(%7B%7D)%22.format(str(list(iter(self))))%0A%0A    def __len__(self):%0A        return len(self._queue_front) + len(self._queue_back)%0A%0A    def __getitem__(self, i):%0A        if i %3E= 0:%0A            nf = len(self._queue_front)%0A            if i %3C nf:%0A                return self._queue_front%5B~i%5D%0A            else:%0A                i -= nf%0A                if i %3C len(self._queue_back):%0A                    return self._queue_back%5Bi%5D%0A                else:%0A                    raise IndexError(%22RandomAccessQueue index out of range%22)%0A%0A        else:%0A            nb = len(self._queue_back)%0A            if i %3E= -nb:%0A                return self._queue_back%5Bi%5D%0A            else:%0A                i += nb%0A                if i %3E= -len(self._queue_front):%0A                    return self._queue_front%5B~i%5D%0A                else:%0A                    raise IndexError(%22RandomAccessQueue index out of range%22)%0A%0A    def __setitem__(self, i, x):%0A        if i %3E= 0:%0A            nf = len(self._queue_front)%0A            if i %3C nf:%0A                self._queue_front%5B~i%5D = x%0A            else:%0A                i -= nf%0A                if i %3C len(self._queue_back):%0A                    self._queue_back%5Bi%5D = x%0A                else:%0A                    raise IndexError(%22RandomAccessQueue index out of range%22)%0A%0A        else:%0A            nb = len(self._queue_back)%0A            if i %3E= -nb:%0A                self._queue_back%5Bi%5D = x%0A            else:%0A                i += nb%0A                if i %3E= -len(self._queue_front):%0A                    self._queue_front%5B~i%5D = x%0A                else:%0A                    raise IndexError(%22RandomAccessQueue index out of range%22)%0A%0A    def append(self, x):%0A        self._queue_back.append(x)%0A%0A    def popleft(self):%0A        if not self._queue_front:%0A            if not self._queue_back:%0A                raise IndexError(%22pop from empty RandomAccessQueue%22)%0A%0A            self._queue_front = self._queue_back%0A            self._queue_back = %5B%5D%0A            self._queue_front.reverse()%0A%0A        return self._queue_front.pop()%0A%0A    def _sample(self, k):%0A        n = len(self)%0A        if k %3E n:%0A            raise ValueError(%22Sample larger than population or is negative%22)%0A%0A        return %5Bself%5Bi%5D for i in random.sample(six.moves.range(n), k)%5D%0A

Add RandomAccessQueue