<commit_before>"""C3 algorithm by <NAME> (with readability enhanced by me)."""

from collections import defaultdict


class LinearizeError(ValueError):
    pass
    
def merge(seqs):
    # Make sure we don't actually mutate anything we are getting as input.
    seqs = [x[:] for x in seqs]
    # print 'merge', seqs
    res = [];
    i=0
    while 1:
      nonemptyseqs = [seq for seq in seqs if seq]
      if not nonemptyseqs:
          return res
      i += 1
      # print '\n',i,'round: candidates...',
      
      for seq in nonemptyseqs: # find merge candidates among seq heads
          cand = seq[0]
          # print ' ',cand,
          nothead=[s for s in nonemptyseqs if cand in s[1:]]
          if nothead:
              cand=None #reject candidate
          else:
              break
      if not cand:
          raise LinearizeError("inconsistent hierarchy")
      res.append(cand)
      for seq in nonemptyseqs: # remove cand
          if seq[0] == cand: del seq[0]

def linearize(graph, order=True):
    "Compute the class precedence list (MRO or method resolution order) according to C3"
    # I have removed adding [C.get_deps()] on the end to remove the requirement that they are in order.
    results = {}
    graph = defaultdict(list, dict(
        (k, list(v)) for k, v in graph.iteritems()
    ))
    for head in sorted(graph, key=lambda k: len(graph[k])):
        _linearize(head, graph, order, results)
    return results
    
def _linearize(head, graph, order, results):
    if head in results:
        return results[head]
    res = merge(
        [[head]] +
        [_linearize(x, graph, order, results) for x in graph[head]] +
        ([graph[head]] if order else [])
    )
    results[head] = res
    return res


if __name__ == '__main__':
    
    A, B, C, D, E, F, G, O = 'ABCDEFGO'
    
    assert merge([[O]]) == [O]
    assert merge([[D], [D, O]]) == [D, O]
    assert merge([[E], [E, O]]) == [E, O]
    assert merge([[F], [F, O]]) == [F, O]<commit_msg>Clean up the merge function.<commit_after>"""C3 algorithm by <NAME> (with readability enhanced by me)."""

from collections import defaultdict


class LinearizeError(ValueError):
    pass


def merge(sequences):
    
    # Make sure we don't actually mutate anything we are getting as input.
    sequences = [list(x) for x in sequences]
    
    result = []
    
    while True:
        
        # Clear out blank sequences.
        sequences = [x for x in sequences if x]
        if not sequences:
            return result

        # Find the first clean head.
        for seq in sequences:
            head = seq[0]
            # If this is not a bad head (ie. not in any other sequence)...
            if not any(head in s[1:] for s in sequences):
                break
        else:
            raise LinearizeError("inconsistent hierarchy")
        
        # Move the head from the front of all sequences to the end of results.
        result.append(head)
        for seq in sequences:
            if seq[0] == head:
                del seq[0]


def linearize(graph, order=True):
    "Compute the class precedence list (MRO or method resolution order) according to C3"
    results = {}
    graph = defaultdict(list, graph)
    for head in sorted(graph, key=lambda k: len(graph[k])):
        _linearize(head, graph, order, results)
    return results
    
def _linearize(head, graph, order, results):
    if head in results:
        return results[head]
    res = merge(
        [[head]] +
        [_linearize(x, graph, order, results) for x in graph[head]] +
        ([graph[head]] if order else [])
    )
    results[head] = res
    return res


if __name__ == '__main__':
    
    A, B, C, D, E, F, G, O = 'ABCDEFGO'
    
    assert merge([[O]]) == [O]
    assert merge([[D], [D, O]]) == [D, O]
    assert merge([[E], [E, O]]) == [E, O]
    assert merge([[F], [F, O]]) == [F, O]
{'fraction_non_alphanumeric': 0.12045395924684034, 'fraction_numerical': 0.003868970853752902, 'mean_word_length': 2.2023121387283235, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7398349', 'n_tokens_mistral': 1213, 'n_tokens_neox': 1195, 'n_words': 446}