1 files changed, 49 insertions, 1 deletions
diff --git a/rdiff-backup/rdiff_backup/rorpiter.py b/rdiff-backup/rdiff_backup/rorpiter.py
index f75d8e8..3849fdc 100644
--- a/rdiff-backup/rdiff_backup/rorpiter.py
+++ b/rdiff-backup/rdiff_backup/rorpiter.py
@@ -440,5 +440,53 @@ class CacheIndexable:
 	def get(self, index):
 		"""Return element with index index from cache"""
 		try: return self.cache_dict[index]
-		except KeyError: return None
+		except KeyError:
+			assert index > self.cache_indicies[0], index
+			return None
 
+
+class CachedIndexableProcessor:
+	"""Reorder indicies, then feed into some function in order
+
+	Use this class when you want to run some function on a stream of
+	objects in index order.  However, the objects may be slightly out
+	of index order.  This class will cache a certain number, and then
+	reorder them.
+
+	An error is signaled if the indicies arrive too out of order.
+
+	"""
+	def __init__(self, function, cache_size):
+		"""CIP initializer.  function is called on every elem."""
+		self.function = function
+		self.cache_size = cache_size
+		self.cache_indicies = []
+		self.cache_dict = {}
+
+	def process(self, elem):
+		"""Call CIP (and underlying self.function) on indexed elem"""
+		index = elem.index
+		self.cache_dict[index] = elem
+		if self.cache_indicies and index <= self.cache_indicies[-1]:
+			assert index > self.cache_indicies[0]
+			self.cache_indicies.append(index)
+			self.cache_indicies.sort() # Ack, n log n, should be log n!!!
+		else: self.cache_indicies.append(index)
+		
+		if len(self.cache_indicies) > self.cache_size:
+			first_index = self.cache_indicies[0]
+			first_elem = self.cache_dict[first_index]
+			del self.cache_indicies[0]
+			del self.cache_dict[first_index]
+			self.function(first_elem)
+
+	__call__ = process
+
+	def close(self):
+		"""Flush cache by running function on remaining elems"""
+		while self.cache_indicies:
+			index = self.cache_indicies[0]
+			elem = self.cache_dict[index]
+			del self.cache_indicies[0]
+			del self.cache_dict[index]
+			self.function(elem)