doc/todo/sort_parameter_for_map_plugin_and_directive/python_algorithms.py

   1 testdata = "c/3 a b d b/1 c/1 c/2/x c/2 c".split(" ")
   2
   3 def strategy_byearlychild(sequence):
   4     """Sort by earliest child
   5
   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.
   8
   9     >>> strategy_byearlychild(testdata)
  10     ['c', 'c/3', 'c/1', 'c/2', 'c/2/x', 'a', 'b', 'b/1', 'd']
  11     """
  12
  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
  17         if childindices:
  18             return min(sequence.index(item), *childindices)
  19         else:
  20             return sequence.index(item)
  21     sequence = sorted(sequence, key=firstchildindex)
  22
  23     # second step: pull other children to the start too
  24     return strategy_byparents(sequence)
  25
  26 def strategy_byparents(sequence):
  27     """Sort by parents only
  28
  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.
  32
  33     >>> strategy_byparents(testdata)
  34     ['a', 'b', 'b/1', 'd', 'c', 'c/3', 'c/1', 'c/2', 'c/2/x']
  35     """
  36
  37     def partindices(item):
  38         """Convert an entry a tuple of the indices of the entry's parts.
  39
  40         >>> sequence = testsequence
  41         >>> assert partindices("c/2/x") == (sequence.index("c"), sequence.index("c/2"), sequence.index("c/2/x"))
  42         fnord
  43         """
  44         return tuple(sequence.index(item.rsplit('/', i)[0]) for i in range(item.count('/'), -1, -1))
  45
  46     return sorted(sequence, key=partindices)
  47
  48 def strategy_forcedsequence(sequence):
  49     """Forced Sequence Mode
  50
  51     Using this strategy, all entries will be shown in the sequence; this can
  52     cause parents to show up multiple times.
  53
  54     The only reason why this is not the identical function is that parents that
  55     are sorted between their children are bubbled up to the top of their
  56     contiguous children to avoid being repeated in the output.
  57
  58     >>> strategy_forcedsequence(testdata)
  59     ['c/3', 'a', 'b', 'd', 'b/1', 'c', 'c/1', 'c/2', 'c/2/x']
  60     """
  61
  62     # this is a classical bubblesort. other algorithms wouldn't work because
  63     # they'd compare non-adjacent entries and move the parents before remote
  64     # children. python's timsort seems to work too...
  65
  66     for i in range(len(sequence), 1, -1):
  67         for j in range(1, i):
  68             if sequence[j-1].startswith(sequence[j] + '/'):
  69                 sequence[j-1:j+1] = [sequence[j], sequence[j-1]]
  70
  71     return sequence
  72
  73 def strategy_forcedsequence_timsort(sequence):
  74     sequence.sort(lambda x,y: -1 if y.startswith(x) else 1)
  75     return sequence
  76
  77 if __name__ == "__main__":
  78     import doctest
  79     doctest.testmod()
  80
  81     import itertools
  82
  83     for perm in itertools.permutations(testdata):
  84         if strategy_forcedsequence(testdata[:]) != strategy_forcedsequence_timsort(testdata[:]):
  85             print "difference for testdata", testdata
  86             print "normal", strategy_forcedsequence(testdata[:])
  87             print "timsort", strategy_forcedsequence_timsort(testdata[:])