b.t.MergeSorter(object) : class documentation

Merge-aware topological sorting of a graph.

:param graph: sequence of pairs of node_name->parent_names_list.
              i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
              For this input the output from the sort or
              iter_topo_order routines will be:
              'A', 'B', 'C'
:param branch_tip: the tip of the branch to graph. Revisions not
               reachable from branch_tip are not included in the
               output.
:param mainline_revisions: If not None this forces a mainline to be
                       used rather than synthesised from the graph.
                       This must be a valid path through some part
                       of the graph. If the mainline does not cover all
                       the revisions, output stops at the start of the
                       old revision listed in the mainline revisions
                       list.
                       The order for this parameter is oldest-first.
:param generate_revno: Optional parameter controlling the generation of
    revision number sequences in the output. See the output description
    for more details.

The result is a list sorted so that all parents come before
their children. Each element of the list is a tuple containing:
(sequence_number, node_name, merge_depth, end_of_merge)
 * sequence_number: The sequence of this row in the output. Useful for
   GUIs.
 * node_name: The node name: opaque text to the merge routine.
 * merge_depth: How many levels of merging deep this node has been
   found.
 * revno_sequence: When requested this field provides a sequence of
     revision numbers for all revisions. The format is:
     (REVNO, BRANCHNUM, BRANCHREVNO). BRANCHNUM is the number of the
     branch that the revno is on. From left to right the REVNO numbers
     are the sequence numbers within that branch of the revision.
     For instance, the graph {A:[], B:['A'], C:['A', 'B']} will get
     the following revno_sequences assigned: A:(1,), B:(1,1,1), C:(2,).
     This should be read as 'A is the first commit in the trunk',
     'B is the first commit on the first branch made from A', 'C is the
     second commit in the trunk'.
 * end_of_merge: When True the next node is part of a different merge.


node identifiers can be any hashable object, and are typically strings.

If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
one of the two values for 'a'.

The graph is sorted lazily: until you iterate or sort the input is
not processed other than to create an internal representation.

iteration or sorting may raise GraphCycleError if a cycle is present
in the graph.

Background information on the design:
-------------------------------------
definition: the end of any cluster or 'merge' occurs when:
    1 - the next revision has a lower merge depth than we do.
      i.e.
      A 0
      B  1
      C   2
      D  1
      E 0
      C, D are the ends of clusters, E might be but we need more data.
    2 - or the next revision at our merge depth is not our left most
      ancestor.
      This is required to handle multiple-merges in one commit.
      i.e.
      A 0    [F, B, E]
      B  1   [D, C]
      C   2  [D]
      D  1   [F]
      E  1   [F]
      F 0
      C is the end of a cluster due to rule 1.
      D is not the end of a cluster from rule 1, but is from rule 2: E
        is not its left most ancestor
      E is the end of a cluster due to rule 1
      F might be but we need more data.

we show connecting lines to a parent when:
 - The parent is the start of a merge within this cluster.
   That is, the merge was not done to the mainline before this cluster
   was merged to the mainline.
   This can be detected thus:
    * The parent has a higher merge depth and is the next revision in
      the list.

  The next revision in the list constraint is needed for this case:
  A 0   [D, B]
  B  1  [C, F]   # we do not want to show a line to F which is depth 2
                   but not a merge
  C  1  [H]      # note that this is a long line to show back to the
                   ancestor - see the end of merge rules.
  D 0   [G, E]
  E  1  [G, F]
  F   2 [G]
  G  1  [H]
  H 0
 - Part of this merges 'branch':
  The parent has the same merge depth and is our left most parent and we
   are not the end of the cluster.
  A 0   [C, B] lines: [B, C]
  B  1  [E, C] lines: [C]
  C 0   [D]    lines: [D]
  D 0   [F, E] lines: [E, F]
  E  1  [F]    lines: [F]
  F 0
 - The end of this merge/cluster:
  we can ONLY have multiple parents at the end of a cluster if this
  branch was previously merged into the 'mainline'.
  - if we have one and only one parent, show it
    Note that this may be to a greater merge depth - for instance if
    this branch continued from a deeply nested branch to add something
    to it.
  - if we have more than one parent - show the second oldest (older ==
    further down the list) parent with
    an equal or lower merge depth
     XXXX revisit when awake. ddaa asks about the relevance of each one
     - maybe more than one parent is relevant