jaraco/itertools.py
def collate_revs(old, new, key=lambda x: x, merge=lambda old, new: new):
	"""
	Given revision sets old and new, each containing a series
	of revisions of some set of objects, collate them based on
	these rules:

	- all items from each set are yielded in stable order
	- items in old are yielded first
	- items in new are yielded last
	- items that match are yielded in the order in which they
	appear, giving preference to new

	Items match based on the 'key' parameter (identity by default).

	Items are merged using the 'merge' function, which accepts the old
	and new items to be merged (returning new by default).

	This algorithm requires fully materializing both old and new in memory.

	>>> rev1 = ['a', 'b', 'c']
	>>> rev2 = ['a', 'd', 'c']
	>>> result = list(collate_revs(rev1, rev2))

	'd' must appear before 'c'
	>>> result.index('d') < result.index('c')
	True

	'b' must appear before 'd' because it came chronologically
	first.
	>>> result.index('b') < result.index('d')
	True

	>>> result
	['a', 'b', 'd', 'c']

	>>> list(collate_revs(['a', 'b', 'c'], ['d']))
	['a', 'b', 'c', 'd']

	>>> list(collate_revs(['b', 'a'], ['a', 'b']))
	['a', 'b']

	>>> list(collate_revs(['a', 'c'], ['a', 'b', 'c']))
	['a', 'b', 'c']

	Given two sequences of things out of order, regardless
	of which order in which the items are merged, all
	keys should always be merged.

	>>> from more_itertools import consume
	>>> left_items = ['a', 'b', 'c']
	>>> right_items = ['a', 'c', 'b']
	>>> consume(collate_revs(left_items, right_items, merge=print))
	a a
	c c
	b b
	>>> consume(collate_revs(right_items, left_items, merge=print))
	a a
	b b
	c c

	The merge should not suppress non-True items:

	>>> consume(collate_revs([0, 1, 2, None, ''], [0, None, ''], merge=print))
	None None
	<BLANKLINE>
	0 0

	"""
	missing = object()

	def maybe_merge(*items):
		"""
		Merge any non-null items
		"""
		def not_missing(ob):
			return ob is not missing

		return functools.reduce(merge, filter(not_missing, items))

	new_items = collections.OrderedDict(
		(key(el), el)
		for el in new
	)
	old_items = collections.OrderedDict(
		(key(el), el)
		for el in old
	)

	# use the old_items as a reference
	for old_key, old_item in _mutable_iter(old_items):
		if old_key not in new_items:
			yield old_item
			continue

		# yield all new items that appear before the matching key
		before, match_new, new_items = _swap_on_miss(
			partition_dict(new_items, old_key))
		for new_key, new_item in before.items():
			# ensure any new keys are merged with previous items if
			# they exist
			yield maybe_merge(new_item, old_items.pop(new_key, missing))
		yield merge(old_item, match_new)

	# finally, yield whatever is leftover
	# yield from new_items.values()
	for item in new_items.values():
		yield item
def collate_revs(old, new, key=lambda x: x, merge=lambda old, new: new):
	"""
	Given revision sets old and new, each containing a series
	of revisions of some set of objects, collate them based on
	these rules:

	- all items from each set are yielded in stable order
	- items in old are yielded first
	- items in new are yielded last
	- items that match are yielded in the order in which they
	appear, giving preference to new

	Items match based on the 'key' parameter (identity by default).

	Items are merged using the 'merge' function, which accepts the old
	and new items to be merged (returning new by default).

	This algorithm requires fully materializing both old and new in memory.

	>>> rev1 = ['a', 'b', 'c']
	>>> rev2 = ['a', 'd', 'c']
	>>> result = list(collate_revs(rev1, rev2))

	'd' must appear before 'c'
	>>> result.index('d') < result.index('c')
	True

	'b' must appear before 'd' because it came chronologically
	first.
	>>> result.index('b') < result.index('d')
	True

	>>> result
	['a', 'b', 'd', 'c']

	>>> list(collate_revs(['a', 'b', 'c'], ['d']))
	['a', 'b', 'c', 'd']

	>>> list(collate_revs(['b', 'a'], ['a', 'b']))
	['a', 'b']

	>>> list(collate_revs(['a', 'c'], ['a', 'b', 'c']))
	['a', 'b', 'c']

	Given two sequences of things out of order, regardless
	of which order in which the items are merged, all
	keys should always be merged.

	>>> from more_itertools import consume
	>>> left_items = ['a', 'b', 'c']
	>>> right_items = ['a', 'c', 'b']
	>>> consume(collate_revs(left_items, right_items, merge=print))
	a a
	c c
	b b
	>>> consume(collate_revs(right_items, left_items, merge=print))
	a a
	b b
	c c

	The merge should not suppress non-True items:

	>>> consume(collate_revs([0, 1, 2, None, ''], [0, None, ''], merge=print))
	None None
	<BLANKLINE>
	0 0

	"""
	missing = object()

	def maybe_merge(*items):
		"""
		Merge any non-null items
		"""
		def not_missing(ob):
			return ob is not missing

		return functools.reduce(merge, filter(not_missing, items))

	new_items = collections.OrderedDict(
		(key(el), el)
		for el in new
	)
	old_items = collections.OrderedDict(
		(key(el), el)
		for el in old
	)

	# use the old_items as a reference
	for old_key, old_item in _mutable_iter(old_items):
		if old_key not in new_items:
			yield old_item
			continue

		# yield all new items that appear before the matching key
		before, match_new, new_items = _swap_on_miss(
			partition_dict(new_items, old_key))
		for new_key, new_item in before.items():
			# ensure any new keys are merged with previous items if
			# they exist
			yield maybe_merge(new_item, old_items.pop(new_key, missing))
		yield merge(old_item, match_new)

	# finally, yield whatever is leftover
	# yield from new_items.values()
	for item in new_items.values():
		yield item
Given revision sets old and new, each containing a series
	of revisions of some set of objects, collate them based on
	these rules:

	- all items from each set are yielded in stable order
	- items in old are yielded first
	- items in new are yielded last
	- items that match are yielded in the order in which they
	appear, giving preference to new

	Items match based on the 'key' parameter (identity by default).

	Items are merged using the 'merge' function, which accepts the old
	and new items to be merged (returning new by default).

	This algorithm requires fully materializing both old and new in memory.

	>>> rev1 = ['a', 'b', 'c']
	>>> rev2 = ['a', 'd', 'c']
	>>> result = list(collate_revs(rev1, rev2))

	'd' must appear before 'c'
	>>> result.index('d') < result.index('c')
	True

	'b' must appear before 'd' because it came chronologically
	first.
	>>> result.index('b') < result.index('d')
	True

	>>> result
	['a', 'b', 'd', 'c']

	>>> list(collate_revs(['a', 'b', 'c'], ['d']))
	['a', 'b', 'c', 'd']

	>>> list(collate_revs(['b', 'a'], ['a', 'b']))
	['a', 'b']

	>>> list(collate_revs(['a', 'c'], ['a', 'b', 'c']))
	['a', 'b', 'c']

	Given two sequences of things out of order, regardless
	of which order in which the items are merged, all
	keys should always be merged.

	>>> from more_itertools import consume
	>>> left_items = ['a', 'b', 'c']
	>>> right_items = ['a', 'c', 'b']
	>>> consume(collate_revs(left_items, right_items, merge=print))
	a a
	c c
	b b
	>>> consume(collate_revs(right_items, left_items, merge=print))
	a a
	b b
	c c

	The merge should not suppress non-True items:

	>>> consume(collate_revs([0, 1, 2, None, ''], [0, None, ''], merge=print))
	None None
	<BLANKLINE>
	0 0