albin.severinson
BAN USER@LinkSausage What do you think about bounding the font sizes you need to consider and then doing binary search?
In other, words find a font that will for sure fit and one that will for sure not fit. Then do binary search on the remaining fonts. You could maybe even improve the speed by using the average font size somehow.
You might want to take a different approach if you're dealing with sparse matrices. This runs in O(n log n), where n is the number of non-zero entries. This assumes zig-zag means going bottom-left to top right for each diagonal. If you want to alternate direction you need to sort each diagonal separately, I think.
# Matrix element
class Element(object):
def __init__(self, row, col, val):
self.row = row
self.col = col
self.val = val
return
# Coordinate list matrix class
class Matrix(object):
def __init__(self):
self.rows = 0
self.cols = 0
self.elements = list()
return
def add(self, e):
assert type(e) is Element
self.elements.append(e)
if e.row > self.rows:
self.rows = e.row
if e.col > self.cols:
self.cols = e.col
return
class ZZIter(object):
def __init__(self, matrix):
assert type(matrix) is Matrix
elements = sorted(matrix.elements, key=lambda x: x.row)
elements = sorted(elements, key=lambda x: x.row + x.col)
self.elements = elements
self.index = 0
return
def __iter__(self):
return self
def __next__(self):
if self.index == len(self.elements):
raise StopIteration
e = self.elements[self.index]
self.index += 1
return e
Don't think we have a python solution yet. This is a bit clunky, but it does the job. Forgetting to take negative numbers into account is probably a common mistake.
- albin.severinson January 05, 2017