blob: 3eee741ed64bd24600b210628a6e2b7e0ad5520e [file] [log] [blame]
"""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.longOffset 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