Lib/fontTools/ttLib/tables/distillery/__init__.py

"""This module helps with distilling a set of objects (aka tables) linked together through
a set of object references (represented eventually by offsets) into a bytestream in a compact
and efficient manner.  This is useful for compiling tables like GSUB/GPOS/GDEF and other
tables represented in the otData.py module."""

from __future__ import print_function, division, absolute_import
from fontTools.misc.py23 import *

from fibonacci_heap_mod import Fibonacci_heap


def sortMeOut(table):
	distillery = Distillery()
	return distillery.distill(table)

class ObjectSet(object):

	def __init__(self):
		self._s = set()
		self._d = dict()

	def add(self, obj):
		self._s.add(id(obj))
		self._d[id(obj)] = obj

	def remove(self, obj):
		self._s.remove(id(obj))
		del self._d[id(obj)]

	def issubset(self, other):
		assert type(other) == ObjectSet
		return self._s.issubset(other._s)

	def __iter__(self):
		return iter(self._d.values())

	def __contains__(self, obj):
		return id(obj) in self._s

	def __bool__(self):
		return bool(self._s)

	__nonzero__ = __bool__

	def __len__(self):
		return len(self._s)

	def __repr__(self):
		return repr(self._s)

class Distillery(object):

	def __init__(self):
		self.packedS = ObjectSet()
		self.readyQ = Fibonacci_heap()
		self.readyS = ObjectSet()
		#self.awaitQ = Fibonacci_heap()
		#self.awaitS = ObjectSet()

	def _itemPriority(self, item):
		leashLen = (65536)**2 if item.offsetSize == 4 else 65536
		packedParentsPos = [p.pos for p in item.parents if p in self.packedS]
		leashStart = min(packedParentsPos) if packedParentsPos else (65536)**2 * 2
		itemLen = len(item)
		return (leashStart + leashLen + itemLen)# / 4

	def _itemIsReady(self, item):
		return item.parents.issubset(self.packedS)

	def _readyEnqueue(self, item):
		item.node = self.readyQ.enqueue(item, self._itemPriority(item))
		self.readyS.add(item)

	#def _awaitEnqueue(self, item):
	#	item.node = self.awaitQ.enqueue(item, self._itemPriority(item))
	#	self.awaitS.add(item)

	#def _awaitDelete(self, item):
	#	assert item in self.awaitS
	#	self.awaitS.remove(item)
	#	self.awaitQ.delete(item.node)
	#	del item.node

	def _setParents(self, root, done):
		done.add(root)
		root.parents = ObjectSet()
		for item in root.items:
			if not hasattr(item, 'getData'):
				continue
			if item not in done:
				self._setParents(item, done)
			item.parents.add(root)

	def distill(self, root):
		self._setParents(root, ObjectSet())

		out = []

		self._readyEnqueue(root)

		pos = 0
		while self.readyQ:
			entry = self.readyQ.dequeue_min()
			obj = entry.get_value()
			self.readyS.remove(obj)
			prio = entry.get_priority()
			del entry
			del obj.node

			out.append(obj)
			obj.pos = pos
			self.packedS.add(obj)

			for item in obj.items:
				if not hasattr(item, "getData"):
					continue

				assert item not in self.packedS
				if item in self.readyS:
					continue

				if self._itemIsReady(item):
					#if hasattr(item, 'node'):
					#	self._awaitDelete(item)

					self._readyEnqueue(item)
				else:
					pass
					#if hasattr(item, 'node'):
					#	self.awaitQ.decrease_key(item.node, self._itemPriority(item))
					#else:
					#	self._awaitEnqueue(item)

			pos += len(obj)

		#assert not self.awaitS, self.awaitS
		#assert not self.awaitQ, self.awaitQ
		assert not self.readyS, self.readyS
		assert not self.readyQ, self.readyQ

		return out