nodes: 0, module; 1, function_definition; 2, function_name:group_files_by_size_fast; 3, parameters; 4, comment:# pragma: no cover; 5, block; 6, identifier:fileslist; 7, identifier:nbgroups; 8, default_parameter; 9, expression_statement; 10, expression_statement; 11, expression_statement; 12, expression_statement; 13, comment:# [] or {}; 14, expression_statement; 15, expression_statement; 16, while_statement; 17, return_statement; 18, identifier:mode; 19, integer:1; 20, string; 21, assignment; 22, assignment; 23, assignment; 24, assignment; 25, assignment; 26, identifier:ford; 27, block; 28, identifier:fgrouped; 29, string_content:Given a files list with sizes, output a list where the files are grouped in nbgroups per cluster.
  
      Pseudo-code for algorithm in O(n log(g)) (thank's to insertion sort or binary search trees)
      See for more infos: http://cs.stackexchange.com/questions/44406/fast-algorithm-for-clustering-groups-of-elements-given-their-size-time/44614#44614
      For each file:
          - If to-fill list is empty or file.size > first-key(to-fill):
            * Create cluster c with file in first group g1
            * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
          - Else:
            * ksize = first-key(to-fill)
            * c, g = to-fill[ksize].popitem(0)
            * Add file to cluster c in group g
            * nsize = ksize - file.size
            * if nsize > 0:
              . to-fill[nsize].append([c, g])
              . sort to-fill if not an automatic ordering structure; 30, identifier:ftofill; 31, call; 32, identifier:ftofill_pointer; 33, dictionary; 34, identifier:fgrouped; 35, list; 36, identifier:ford; 37, call; 38, identifier:last_cid; 39, unary_operator; 40, expression_statement; 41, comment:#print "----\n"+fname, fsize; 42, comment:#if ftofill: print "beforebranch", fsize, ftofill[-1]; 43, comment:#print ftofill; 44, if_statement; 45, identifier:SortedList; 46, argument_list; 47, identifier:sorted; 48, argument_list; 49, integer:1; 50, assignment; 51, boolean_operator; 52, block; 53, else_clause; 54, call; 55, keyword_argument; 56, pattern_list; 57, call; 58, not_operator; 59, comparison_operator:fsize > ftofill[-1]; 60, expression_statement; 61, comment:#print "Branch A: create cluster %i" % last_cid; 62, expression_statement; 63, comment:#fgrouped[last_cid] = []; 64, expression_statement; 65, if_statement; 66, comment:#print "Branch B"; 67, block; 68, attribute; 69, argument_list; 70, identifier:key; 71, lambda; 72, identifier:fname; 73, identifier:fsize; 74, attribute; 75, argument_list; 76, identifier:ftofill; 77, identifier:fsize; 78, subscript; 79, augmented_assignment; 80, call; 81, call; 82, comparison_operator:mode==0; 83, block; 84, else_clause; 85, expression_statement; 86, expression_statement; 87, comment:#print "Assign to cluster %i group %i" % (c, g); 88, expression_statement; 89, expression_statement; 90, if_statement; 91, identifier:fileslist; 92, identifier:iteritems; 93, lambda_parameters; 94, subscript; 95, identifier:ford; 96, identifier:pop; 97, identifier:ftofill; 98, unary_operator; 99, identifier:last_cid; 100, integer:1; 101, attribute; 102, argument_list; 103, attribute; 104, argument_list; 105, identifier:mode; 106, integer:0; 107, for_statement; 108, block; 109, assignment; 110, assignment; 111, call; 112, assignment; 113, comparison_operator:nsize > 0; 114, block; 115, identifier:x; 116, identifier:x; 117, integer:1; 118, integer:1; 119, identifier:fgrouped; 120, identifier:append; 121, list; 122, subscript; 123, identifier:append; 124, list; 125, identifier:g; 126, call; 127, block; 128, for_statement; 129, identifier:ksize; 130, call; 131, pattern_list; 132, call; 133, attribute; 134, argument_list; 135, identifier:nsize; 136, binary_operator:ksize - fsize; 137, identifier:nsize; 138, integer:0; 139, if_statement; 140, expression_statement; 141, expression_statement; 142, identifier:fgrouped; 143, identifier:last_cid; 144, identifier:fname; 145, identifier:xrange; 146, argument_list; 147, expression_statement; 148, if_statement; 149, expression_statement; 150, expression_statement; 151, identifier:g; 152, call; 153, block; 154, attribute; 155, argument_list; 156, identifier:c; 157, identifier:g; 158, attribute; 159, argument_list; 160, subscript; 161, identifier:append; 162, identifier:fname; 163, identifier:ksize; 164, identifier:fsize; 165, not_operator; 166, block; 167, call; 168, call; 169, binary_operator:nbgroups-1; 170, integer:0; 171, unary_operator; 172, call; 173, not_operator; 174, block; 175, call; 176, call; 177, identifier:xrange; 178, argument_list; 179, try_statement; 180, expression_statement; 181, expression_statement; 182, if_statement; 183, identifier:ftofill; 184, identifier:pop; 185, subscript; 186, identifier:pop; 187, subscript; 188, identifier:g; 189, comparison_operator:nsize in ftofill_pointer; 190, expression_statement; 191, attribute; 192, argument_list; 193, attribute; 194, argument_list; 195, identifier:nbgroups; 196, integer:1; 197, integer:1; 198, attribute; 199, argument_list; 200, comparison_operator:fsize in ftofill_pointer; 201, expression_statement; 202, attribute; 203, argument_list; 204, attribute; 205, argument_list; 206, integer:1; 207, identifier:nbgroups; 208, block; 209, except_clause; 210, call; 211, assignment; 212, comparison_operator:diff_size > 0; 213, block; 214, identifier:ftofill_pointer; 215, identifier:ksize; 216, identifier:fgrouped; 217, identifier:c; 218, identifier:nsize; 219, identifier:ftofill_pointer; 220, assignment; 221, subscript; 222, identifier:append; 223, tuple; 224, identifier:ftofill; 225, identifier:add; 226, identifier:nsize; 227, subscript; 228, identifier:append; 229, list; 230, identifier:fsize; 231, identifier:ftofill_pointer; 232, assignment; 233, subscript; 234, identifier:append; 235, tuple; 236, identifier:ftofill; 237, identifier:add; 238, identifier:fsize; 239, expression_statement; 240, comment:#print "Added to group %i: %s %i" % (g, fgname, fgsize); 241, identifier:IndexError; 242, block; 243, attribute; 244, argument_list; 245, identifier:diff_size; 246, binary_operator:fsize - fgsize; 247, identifier:diff_size; 248, integer:0; 249, if_statement; 250, expression_statement; 251, expression_statement; 252, subscript; 253, list; 254, identifier:ftofill_pointer; 255, identifier:nsize; 256, identifier:c; 257, identifier:g; 258, identifier:fgrouped; 259, identifier:last_cid; 260, subscript; 261, list; 262, identifier:ftofill_pointer; 263, identifier:fsize; 264, identifier:last_cid; 265, identifier:g; 266, assignment; 267, break_statement; 268, subscript; 269, identifier:append; 270, list; 271, identifier:fsize; 272, identifier:fgsize; 273, not_operator; 274, block; 275, call; 276, call; 277, identifier:ftofill_pointer; 278, identifier:nsize; 279, identifier:ftofill_pointer; 280, identifier:fsize; 281, pattern_list; 282, call; 283, identifier:fgrouped; 284, identifier:last_cid; 285, identifier:fgname; 286, comparison_operator:diff_size in ftofill_pointer; 287, expression_statement; 288, attribute; 289, argument_list; 290, attribute; 291, argument_list; 292, identifier:fgname; 293, identifier:fgsize; 294, attribute; 295, argument_list; 296, identifier:diff_size; 297, identifier:ftofill_pointer; 298, assignment; 299, subscript; 300, identifier:append; 301, tuple; 302, identifier:ftofill; 303, identifier:add; 304, identifier:diff_size; 305, identifier:ford; 306, identifier:pop; 307, subscript; 308, list; 309, identifier:ftofill_pointer; 310, identifier:diff_size; 311, identifier:last_cid; 312, identifier:g; 313, identifier:ftofill_pointer; 314, identifier:diff_size
code: def group_files_by_size_fast(fileslist, nbgroups, mode=1):  # pragma: no cover
      '''Given a files list with sizes, output a list where the files are grouped in nbgroups per cluster.
  
      Pseudo-code for algorithm in O(n log(g)) (thank's to insertion sort or binary search trees)
      See for more infos: http://cs.stackexchange.com/questions/44406/fast-algorithm-for-clustering-groups-of-elements-given-their-size-time/44614#44614
      For each file:
          - If to-fill list is empty or file.size > first-key(to-fill):
            * Create cluster c with file in first group g1
            * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
          - Else:
            * ksize = first-key(to-fill)
            * c, g = to-fill[ksize].popitem(0)
            * Add file to cluster c in group g
            * nsize = ksize - file.size
            * if nsize > 0:
              . to-fill[nsize].append([c, g])
              . sort to-fill if not an automatic ordering structure
          '''
      ftofill = SortedList()
      ftofill_pointer = {}
      fgrouped = [] # [] or {}
      ford = sorted(fileslist.iteritems(), key=lambda x: x[1])
      last_cid = -1
      while ford:
          fname, fsize = ford.pop()
          #print "----\n"+fname, fsize
          #if ftofill: print "beforebranch", fsize, ftofill[-1]
          #print ftofill
          if not ftofill or fsize > ftofill[-1]:
              last_cid += 1
              #print "Branch A: create cluster %i" % last_cid
              fgrouped.append([])
              #fgrouped[last_cid] = []
              fgrouped[last_cid].append([fname])
              if mode==0:
                  for g in xrange(nbgroups-1, 0, -1):
                      fgrouped[last_cid].append([])
                      if not fsize in ftofill_pointer:
                          ftofill_pointer[fsize] = []
                      ftofill_pointer[fsize].append((last_cid, g))
                      ftofill.add(fsize)
              else:
                  for g in xrange(1, nbgroups):
                      try:
                          fgname, fgsize = ford.pop()
                          #print "Added to group %i: %s %i" % (g, fgname, fgsize)
                      except IndexError:
                          break
                      fgrouped[last_cid].append([fgname])
                      diff_size = fsize - fgsize
                      if diff_size > 0:
                          if not diff_size in ftofill_pointer:
                              ftofill_pointer[diff_size] = []
                          ftofill_pointer[diff_size].append((last_cid, g))
                          ftofill.add(diff_size)
          else:
              #print "Branch B"
              ksize = ftofill.pop()
              c, g = ftofill_pointer[ksize].pop()
              #print "Assign to cluster %i group %i" % (c, g)
              fgrouped[c][g].append(fname)
              nsize = ksize - fsize
              if nsize > 0:
                  if not nsize in ftofill_pointer:
                      ftofill_pointer[nsize] = []
                  ftofill_pointer[nsize].append((c, g))
                  ftofill.add(nsize)
      return fgrouped