from collections import deque, MutableMapping, ItemsView, ValuesView


class WindowDictItemsView(ItemsView):
    def __contains__(self, item):
        (rev, v) = item
        if self._mapping._past:
            if rev < self._mapping._past[0][0]:
                return False
        elif self._mapping._future:
            if rev < self._mapping._future[0][0]:
                return False
        else:
            return False
        for mrev, mv in self._mapping._past:
            if mrev == rev:
                return mv == v
        for mrev, mv in self._mapping._future:
            if mrev == rev:
                return mv == v
        return False

    def __iter__(self):
        yield from self._mapping._past
        yield from self._mapping._future


class WindowDictValuesView(ValuesView):
    def __contains__(self, value):
        for rev, v in self._mapping._past:
            if v == value:
                return True
        for rev, v in self._mapping._future:
            if v == value:
                return True
        return False

    def __iter__(self):
        for rev, v in self._mapping._past:
            yield v
        for rev, v in self._mapping._future:
            yield v


class WindowDict(MutableMapping):
    """A dict that keeps every value that a variable has had over time.
    
    Look up a revision number in this dict and it will give you the effective value as
    of that revision. Keys should always be revision numbers. Once a key is set, all greater
    keys are considered to be in this dict unless the value is ``None``. Keys after that one
    aren't "set" until one's value is non-``None`` again.
    
    Optimized for the cases where you look up the same revision repeatedly, or its neighbors.
    
    """
    __slots__ = ['_past', '_future']

    def seek(self, rev):
        """Arrange the caches in the optimal way for looking up the given revision."""
        # TODO: binary search? Perhaps only when one or the other deque is very large?
        if self._past and self._past[-1][0] <= rev and (not self._future or self._future[0][0] > rev):
            return
        while self._future and self._future[0][0] <= rev:
            self._past.append(self._future.popleft())
        while self._past and self._past[-1][0] > rev:
            self._future.appendleft(self._past.pop())

    def has_exact_rev(self, rev):
        """Return whether I have a value at this exact revision, not just a previous one."""
        self.seek(rev)
        return self._past and self._past[-1][0] == rev

    def rev_before(self, rev):
        """Return the last rev prior to the given one on which the value changed."""
        self.seek(rev)
        return self._past[-1][0]

    def rev_after(self, rev):
        """Return the next rev after the given one on which the value will change, or None if it never will."""
        self.seek(rev)
        if self._future:
            return self._future[0][0]

    def items(self):
        return WindowDictItemsView(self)

    def values(self):
        return WindowDictValuesView(self)

    def __init__(self, data={}):
        self._past = deque(sorted(data.items()))
        self._future = deque()

    def __iter__(self):
        for (rev, v) in self._past:
            yield rev
        for (rev, v) in self._future:
            yield rev

    def __len__(self):
        return len(self._past) + len(self._future)

    def __getitem__(self, rev):
        self.seek(rev)
        if not self._past:
            raise KeyError("Revision {} is before the start of history".format(rev))
        ret = self._past[-1][1]
        if ret is None:
            raise KeyError("Set, then deleted")
        return ret

    def __setitem__(self, rev, v):
        if not self._past and not self._future:
            self._past.append((rev, v))
        elif rev < self._past[0][0]:
            self._past.appendleft((rev, v))
        elif rev == self._past[0][0]:
            self._past[0] = (rev, v)
        elif rev == self._past[-1][0]:
            self._past[-1] = (rev, v)
        elif rev > self._past[-1][0]:
            if not self._future or rev < self._future[0][0]:
                self._past.append((rev, v))
            elif rev == self._future[0][0]:
                self._future[0] = (rev, v)
            elif rev == self._future[-1][0]:
                self._future[-1] = (rev, v)
            elif rev > self._future[-1][0]:
                self._future.append((rev, v))
            else:
                self.seek(rev)
                self._past.append((rev, v))
        else:
            self.seek(rev)
            self._past.append((rev, v))
    
    def __delitem__(self, rev):
        name = '_past' if rev <= self._rev else '_future'
        stack = getattr(self, name)
        waste = deque()
        setattr(self, name, waste)
        deleted = False
        while stack:
            (r, v) = stack.popleft()
            if r != rev:
                waste.append((r, v))
            else:
                assert not deleted
                deleted = True
        if not deleted:
            raise KeyError("Rev not present: {}".format(rev))

    def __repr__(self):
        return "WindowDict({})".format(repr(dict(self)))


class WindowDefaultDict(WindowDict):
    __slots__ = ['_future', '_past', 'cls', 'args_munger', 'kwargs_munger']

    def __init__(self, cls, args_munger=lambda k: tuple(), kwargs_munger=lambda k: {}, data={}):
        super(WindowDefaultDict, self).__init__(data)
        self.cls = cls
        self.args_munger = args_munger
        self.kwargs_munger = kwargs_munger

    def __getitem__(self, k):
        if k in self:
            return super(WindowDefaultDict, self).__getitem__(k)
        ret = self[k] = self.cls(*self.args_munger(k), **self.kwargs_munger(k))
        return ret


class FuturistWindowDict(WindowDict):
    def __setitem__(self, rev, v):
        if not self._past and not self._future:
            self._past.append((rev, v))
        if self._future:
            self.seek(rev)
        if self._future:
            raise ValueError("Already have some history after {}".format(rev))
        if not self._past or rev > self._past[-1][0]:
            self._past.append(rev, v)
        elif rev == self._past[-1][0]:
            self._past[-1] = (rev, v)
        raise ValueError("Already have some history after {} (and my seek function is broken?)".format(rev))

@@ -5972,32 +5972,51 @@
 ppend((rev, v))%0A
+            return%0A
         if self.
@@ -6239,23 +6239,25 @@
 .append(
+(
 rev, v)
+)
 %0A       
@@ -6318,32 +6318,50 @@
 %5B-1%5D = (rev, v)%0A
+        else:%0A    
         raise Va

Fix FuturistWindowDict.__setitem__