1 testdata = "c/3 a b d b/1 c/1 c/2/x c/2 c".split(" ")
3 def strategy_byearlychild(sequence):
4 """Sort by earliest child
6 When this strategy is used, a parent is displayed with all its children as
7 soon as the first child is supposed to be shown.
9 >>> strategy_byearlychild(testdata)
10 ['c', 'c/3', 'c/1', 'c/2', 'c/2/x', 'a', 'b', 'b/1', 'd']
13 # first step: pull parents to top
14 def firstchildindex(item):
15 childindices = [i for (i,text) in enumerate(sequence) if text.startswith(item + "/")]
16 # distinction required as min(foo, *[]) tries to iterate over foo
18 return min(sequence.index(item), *childindices)
20 return sequence.index(item)
21 sequence = sorted(sequence, key=firstchildindex)
23 # second step: pull other children to the start too
24 return strategy_byparents(sequence)
26 def strategy_byparents(sequence):
27 """Sort by parents only
29 With this strategy, children are sorted *under* their parents regardless of
30 their own position, and the parents' positions are determined only by
31 comparing the parents themselves.
33 >>> strategy_byparents(testdata)
34 ['a', 'b', 'b/1', 'd', 'c', 'c/3', 'c/1', 'c/2', 'c/2/x']
37 def partindices(item):
38 return tuple(sequence.index(item.rsplit('/', i)[0]) for i in range(item.count('/'), -1, -1))
40 return sorted(sequence, key=partindices)
42 def strategy_forcedsequence(sequence):
43 """Forced Sequence Mode
45 Using this strategy, all entries will be shown in the sequence; this can
46 cause parents to show up multiple times.
48 The only reason why this is not the identical function is that parents that
49 are sorted between their children are bubbled up to the top of their
50 contiguous children to avoid being repeated in the output.
52 >>> strategy_forcedsequence(testdata)
53 ['c/3', 'a', 'b', 'd', 'b/1', 'c', 'c/1', 'c/2', 'c/2/x']
56 # this is a classical bubblesort. other algorithms wouldn't work because
57 # they'd compare non-adjacent entries and move the parents before remote
58 # children. python's timsort seems to work too...
60 for i in range(len(sequence), 1, -1):
62 if sequence[j-1].startswith(sequence[j] + '/'):
63 sequence[j-1:j+1] = [sequence[j], sequence[j-1]]
67 def strategy_forcedsequence_timsort(sequence):
68 sequence.sort(lambda x,y: -1 if y.startswith(x) else 1)
71 if __name__ == "__main__":
77 for perm in itertools.permutations(testdata):
78 if strategy_forcedsequence(testdata[:]) != strategy_forcedsequence_timsort(testdata[:]):
79 print "difference for testdata", testdata
80 print "normal", strategy_forcedsequence(testdata[:])
81 print "timsort", strategy_forcedsequence_timsort(testdata[:])