[4/14]
class Group:
def counts (self, c, Slist, counts, incs):
pass
def increments (self, c, Slist, counts, incs):
pass
class LayeredGroups:
class Group1 (Group):
def __init__ (self, layer1):
self.layer1 = layer1
def counts (self, c, Slist, counts, incs):
self.layer1.count (c, Slist, counts, incs)
def increments (self, c, Slist, counts, incs):
self.layer1.increment (c, Slist, counts, incs)
class GroupN (Group):
def __init__ (self, order, layers):
self.order = order
self.layers = layers
self.cache_coufun = [l.count for l in layers [:order]]
self.cache_incfun = layers [order - 1].increment
def counts (self, c, Slist, counts, incs):
for fun in self.cache_coufun:
fun (c, Slist, counts, incs)
def increments (self, c, Slist, counts, incs):
self.cache_incfun (c, Slist, counts, incs)
def work_layers_partial (c, Slist, counts, incs, nleft, countfun, order):
order -= 1
countfun (1, Slist, counts, incs)
want = counts [order]
if want > nleft:
return 0
low, high = 1, c
diff = high - low
savec = counts [:]
savei = incs [:]
while diff > 1:
now = (low + high) // 2
countfun (now, Slist, counts, incs)
want = counts [order]
if want <= nleft:
low = now
savec [:] = counts
savei [:] = incs
else:
high = now
diff = high - low
counts [:] = savec
incs [:] = savei
return low
def work_layers_loop (n, groups):
glen = len (groups)
gm1 = glen - 1
R = 3
Slist = [ 4] * glen
counts = [None] * glen
incs = [None] * glen
levels = []
s, c = 4, 3
done = 2
next = seq2_next
g = groups [-1]
gcounts = g.counts
increments = g.increments
slistrange = range (gm1)
gcounts (c, Slist, counts, incs)
advance = counts [gm1]
done += advance
while done <= n:
increments (c, Slist, counts, incs)
R += incs [gm1]
for k in slistrange:
Slist [k + 1] += incs [k]
s, c = next (levels, 0)
Slist [0] = s
gcounts (c, Slist, counts, incs)
advance = counts [gm1]
done += advance
done -= advance
print ("levels:", len (levels))
for gorder in range (glen, 1, -1):
g = groups [gorder - 1]
used = work_layers_partial (
c, Slist, counts, incs,
n - done, g.counts, gorder)
if used > 0:
advance = counts [gorder - 1]
g.increments (used, Slist, counts, incs)
R += incs [gorder - 1]
for k in range (gorder - 1):
Slist [k + 1] += incs [k]
done += advance
levels = [[s, c, used, Slist [1]]]
s, c = next (levels, 0)
Slist [0] = s
del Slist [1]
if done < n:
g = groups [0]
c = n - done
g.counts (c, Slist, counts, incs)
g.increments (c, Slist, counts, incs)
R += incs [0]
return R
def work_layers (n):
layers = [
ChainedLayers.Layer1,
ChainedLayers.Layer2,
ChainedLayers.Layer3,
ChainedLayers.Layer4,
]
groups = [
LayeredGroups.Group1 (layers [0]),
LayeredGroups.GroupN (2, layers),
LayeredGroups.GroupN (3, layers),
LayeredGroups.GroupN (4, layers),
]
return work_layers_loop (n, groups)