--- /dev/null
+#!/usr/bin/python
+
+# Copyright(c)2008-2010 Internet Archive. Software license AGPL version 3.
+#
+# This file is part of BookReader.
+#
+# BookReader is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Affero General Public License as published by
+# the Free Software Foundation, either version 3 of the License, or
+# (at your option) any later version.
+#
+# BookReader is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU Affero General Public License for more details.
+#
+# You should have received a copy of the GNU Affero General Public License
+# along with BookReader. If not, see <http://www.gnu.org/licenses/>.
+#
+# The BookReader source is hosted at http://github.com/openlibrary/bookreader/
+
+from collections import deque
+import itertools
+
+class windowed_iterator:
+ """ Wrap an iterator s.t. we can see [window] neighbors
+ in either direction from the current item.
+
+ Items are stored in a deque of size 2*window + 1, where the latest
+ item is always in the middle position.
+
+ The supplied clear_callback() is called for items more than
+ [window] steps in the past.
+
+ """
+
+ # Todo? remove use of None as sentinel, to be able to represent
+ # iterators returning None.
+
+ def __init__(self, iterator, window, clear_callback=None):
+ self.iterator = iterator
+ # initialize deque with sentinel values
+ self.items = deque((None for i in range(window + 1)),
+ window * 2 + 1)
+ self.window = window
+ self.clear_callback = clear_callback
+ def __iter__(self):
+ return self
+ def __repr__(self):
+ return str(self.items) + ' window: ' + str(self.window)
+ def clear(self):
+ for item in self.items:
+ if item and self.clear_callback is not None:
+ self.clear_callback(item)
+ self.items.clear()
+ def neighbor(self, delta):
+ if abs(delta) > self.window:
+ raise IndexError('Requested delta outside window')
+ while self.window + delta + 1 > len(self.items):
+ try:
+ self.items.append(self.iterator.next())
+ except StopIteration:
+ return None
+ return self.items[self.window + delta]
+ def neighbors(self, window=None, modtwo=False):
+ if window is None:
+ window = self.window
+ if window > self.window:
+ raise IndexError('Requested delta outside window')
+ for i in itertools.chain(range(-window, 0),
+ range(1, window + 1)):
+ if modtwo and i % 2 == 1:
+ continue
+ n = self.neighbor(i)
+ if n is not None:
+ yield n
+ def next(self):
+ nextitem = None
+ if len(self.items) == self.window + 1:
+ # elicit potential StopIteration before clearing/popping
+ nextitem = self.iterator.next()
+ if self.items[0] is not None and self.clear_callback is not None:
+ self.clear_callback(self.items[0])
+ self.items.popleft()
+ if nextitem is not None:
+ self.items.append(nextitem)
+ return self.items[self.window]
+
+
+if __name__ == '__main__':
+ def sample_gen():
+ for i in range(0, 10):
+ yield { 'num': i*i }
+
+ g = sample_gen()
+ c = windowed_iterator(g, 3)
+
+ for i, item in enumerate(c):
+ print 'item %s: %s' % (i, item)
+ # print c
+ if i in (1, 4, 6, 9):
+ print 'neighbors of item %s: %s' % (i, [n for n in c.neighbors(2)])