new_contents: # -*- coding: utf-8 -*-
  
  """T2CharString glyph width optimizer."""
  
  from __future__ import print_function, division, absolute_import
  from fontTools.misc.py23 import *
  from fontTools.ttLib import TTFont, getTableClass
  from collections import defaultdict
  from operator import add
  from functools import partial
  
  
  class missingdict(dict):
  	def __init__(self, missing_func):
  		self.missing_func = missing_func
  	def __missing__(self, v):
  		return self.missing_func(v)
  
  def cumSum(f, op=add, start=0, decreasing=False):
  	
  	keys = sorted(f.keys())
  	minx, maxx = keys[0], keys[-1]
  
  	total = reduce(op, f.values(), start)
  
  	if decreasing:
  		missing = lambda x: start if x > maxx else total
  		domain = range(maxx, minx - 1, -1)
  	else:
  		missing = lambda x: start if x < minx else total
  		domain = range(minx, maxx + 1)
  
  	out = missingdict(missing)
  
  	v = start
  	for x in domain:
  		v = op(v, f[x])
  		out[x] = v
  
  	return out
  
  def byteCost(widths, default, nominal):
  
  	if not hasattr(widths, 'items'):
  		d = defaultdict(int)
  		for w in widths:
  			d[w] += 1
  		widths = d
  
  	cost = 0
  	for w,freq in widths.items():
  		if w == default: continue
  		diff = abs(w - nominal)
  		if diff <= 107:
  			cost += freq
  		elif diff <= 1131:
  			cost += freq * 2
  		else:
  			cost += freq * 5
  	return cost
  
  
  def optimizeWidthsBruteforce(widths):
  	"""Bruteforce version.  Veeeeeeeeeeeeeeeeery slow.  Only works for smallests of fonts."""
  
  	d = defaultdict(int)
  	for w in widths:
  		d[w] += 1
  
  	# Maximum number of bytes using default can possibly save
  	maxDefaultAdvantage = 5 * max(d.values())
  
  	minw, maxw = min(widths), max(widths)
  	domain = list(range(minw, maxw+1))
  
  	bestCostWithoutDefault = min(byteCost(widths, None, nominal) for nominal in domain)
  
  	bestCost = len(widths) * 5 + 1
  	for nominal in domain:
  		if byteCost(widths, None, nominal) > bestCost + maxDefaultAdvantage:
  			continue
  		for default in domain:
  			cost = byteCost(widths, default, nominal)
  			if cost < bestCost:
  				bestCost = cost
  				bestDefault = default
  				bestNominal = nominal
  
  	return bestDefault, bestNominal
  
  
  def optimizeWidths(widths):
  	"""Given a list of glyph widths, or dictionary mapping glyph width to number of glyphs having that,
  	returns a tuple of best CFF default and nominal glyph widths."""
  
  	if not hasattr(widths, 'items'):
  		d = defaultdict(int)
  		for w in widths:
  			d[w] += 1
  		widths = d
  	
  	keys = sorted(widths.keys())
  	minw, maxw = keys[0], keys[-1]
  	domain = list(range(minw, maxw+1))
  
  	# Cumulative sum/max forward/backward.
  	cumFrqU = cumSum(widths, op=add)
  	cumMaxU = cumSum(widths, op=max)
  	cumFrqD = cumSum(widths, op=add, decreasing=True)
  	cumMaxD = cumSum(widths, op=max, decreasing=True)
  
  	# Cost per nominal choice, without default consideration.
  	nomnCostU = missingdict(lambda x: cumFrqU[x] + cumFrqU[x-108] + cumFrqU[x-1131]*3)
  	nomnCostD = missingdict(lambda x: cumFrqD[x] + cumFrqD[x+108] + cumFrqD[x+1131]*3)
  	nomnCost  = missingdict(lambda x: nomnCostU[x] + nomnCostD[x])
  
  	# Cost-saving per nominal choice, by best default choice.
  	dfltCostU = missingdict(lambda x: max(cumMaxU[x], cumMaxU[x-108]*2, cumMaxU[x-1131]*5))
  	dfltCostD = missingdict(lambda x: max(cumMaxD[x], cumMaxD[x+108]*2, cumMaxD[x+1131]*5))
  	dfltCost  = missingdict(lambda x: max(dfltCostU[x], dfltCostD[x]))
  
  	# Combined cost per nominal choice.
  	bestCost  = missingdict(lambda x: nomnCost[x] - dfltCost[x])
  
  	# Best nominal.
  	nominal = min(domain, key=lambda x: bestCost[x])
  
  	# Work back the best default.
  	bestC = bestCost[nominal]
  	dfltC = nomnCost[nominal] - bestCost[nominal]
  	ends = []
  	if dfltC == dfltCostU[nominal]:
  		starts = [nominal, nominal-108, nominal-1131]
  		for start in starts:
  			while cumMaxU[start] and cumMaxU[start] == cumMaxU[start-1]:
  				start -= 1
  			ends.append(start)
  	else:
  		starts = [nominal, nominal+108, nominal+1131]
  		for start in starts:
  			while cumMaxD[start] and cumMaxD[start] == cumMaxD[start+1]:
  				start += 1
  			ends.append(start)
  	default = min(ends, key=lambda default: byteCost(widths, default, nominal))
  
  	return default, nominal
  
  
  if __name__ == '__main__':
  	import sys
  	if len(sys.argv) == 1:
  		import doctest
  		sys.exit(doctest.testmod().failed)
  	for fontfile in sys.argv[1:]:
  		font = TTFont(fontfile)
  		hmtx = font['hmtx']
  		widths = [m[0] for m in hmtx.metrics.values()]
  		default, nominal = optimizeWidths(widths)
  		print("glyphs=%d default=%d nominal=%d byteCost=%d" % (len(widths), default, nominal, byteCost(widths, default, nominal)))
  		#default, nominal = optimizeWidthsBruteforce(widths)
  		#print("glyphs=%d default=%d nominal=%d byteCost=%d" % (len(widths), default, nominal, byteCost(widths, default, nominal)))
  
subject: Add module to calculate optimal CFF default and nominal glyph widths