nodes: 0, module; 1, function_definition; 2, function_name:bucketIterator; 3, parameters; 4, block; 5, identifier:elements; 6, identifier:buckets; 7, expression_statement; 8, function_definition; 9, function_definition; 10, expression_statement; 11, expression_statement; 12, expression_statement; 13, for_statement; 14, comment:"""
    For each bucket in buckets, yield it and any elements that overlap it.
  
    :param elements: the genomic intervals to place into the buckets. Must be
                     sorted by chromosome and start index. This could be a
                     list, or an iterator.
    :param buckets: the buckets into which genomic intervals should be binned.
                    Must be sorted by chromosome and start index. This could be
                    a list, or an iterator
    :return: iterator that will yeild a tuple of 1 bucket and 1 list of elements
             in the bucket for each call to __next__().
    """; 15, function_name:check_sorted; 16, parameters; 17, block; 18, function_name:updateOpen; 19, parameters; 20, block; 21, assignment; 22, assignment; 23, assignment; 24, identifier:bucket; 25, identifier:buckets; 26, comment:# make sure the buckets are sorted by start index; 27, block; 28, identifier:current; 29, identifier:previous; 30, if_statement; 31, identifier:openHeap; 32, identifier:elementIterator; 33, identifier:bucketChrom; 34, identifier:bucketStart; 35, identifier:bucketEnd; 36, expression_statement; 37, comment:# first, we're going to pop elements from the heap which can no longer; 38, comment:# overalp this or any future buckets. Buckets are sorted by start, so; 39, comment:# we'll never see another bucket that starts earlier than this one --; 40, comment:# hence any elements that end before the start of this bucket will never be; 41, comment:# used again and can be dropped. Elements in the heap are ordered by end; 42, comment:# index, so once we reach an element in the heap that does not end before; 43, comment:# the start of this bucket, we are sure that no others will come after it; 44, comment:# which do end before the start of this bucket. So we can stop dropping.; 45, while_statement; 46, comment:# now we're going to add new elements from the iterator to the heap. As; 47, comment:# we know that elements in the iterator are sorted by start index, we know; 48, comment:# that once we see an element that has a start index greater than the end; 49, comment:# of this bucket, we can stop -- everything else after it will also start; 50, comment:# after the end of this bucket.; 51, while_statement; 52, identifier:openElems; 53, list; 54, identifier:prevBucket; 55, None; 56, identifier:elementIter; 57, call; 58, if_statement; 59, expression_statement; 60, comment:# be careful here not to leak a reference to the heap; if the caller; 61, comment:# decides to mess with that list, it'll screw us up. Anyway, we need a; 62, comment:# final check here to make sure we trim off any elements that exceed the; 63, comment:# end of this bucket.; 64, expression_statement; 65, expression_statement; 66, boolean_operator; 67, block; 68, comment:"""
      Drop elements from heap which start earlier than current bucket.
  
      Update the open heap so that it contains only elements that end after the
      start of the current bucket. Note that the heap may already contain some
      elements that start after the end of the current bucket, if a previous
      bucket ended after the end of this one and brought them into the set.
  
      :param openHeap: a min heap of elements; uses the default sorting order
                       for the genomic intervals, which is by end index. This
                       is what we're updating.
      :param elementIterator: an iterator from which we will pull new elements.
                              Elements yielded by this iterator must be sorted
                              by start index. Must be 'peakable'
      :param bucketChrom: the chromosome of the current bucket.
      :param bucketStart: the start index of the current bucket.
      :param bucketEnd: the end index of the current bucket.
      """; 69, boolean_operator; 70, block; 71, boolean_operator; 72, block; 73, identifier:AutoApplyIterator; 74, argument_list; 75, boolean_operator; 76, block; 77, call; 78, yield; 79, assignment; 80, parenthesized_expression; 81, line_continuation:\; 82, parenthesized_expression; 83, raise_statement; 84, comparison_operator:len(openHeap) > 0; 85, parenthesized_expression; 86, expression_statement; 87, parenthesized_expression; 88, line_continuation:\; 89, parenthesized_expression; 90, expression_statement; 91, comment:# if e falls before this bucket, we can skip it; buckets are sorted by; 92, comment:# start, so no other buckets start earlier than this one and so it; 93, comment:# cannot intersect any others.; 94, if_statement; 95, comment:# now we know e intersects this bucket..; 96, expression_statement; 97, identifier:elements; 98, identifier:check_sorted; 99, comparison_operator:prevBucket is not None; 100, parenthesized_expression; 101, raise_statement; 102, identifier:updateOpen; 103, argument_list; 104, expression_list; 105, identifier:prevBucket; 106, identifier:bucket; 107, comparison_operator:previous is not None; 108, boolean_operator; 109, call; 110, call; 111, integer:0; 112, boolean_operator; 113, call; 114, comparison_operator:elementIterator.peek() is not None; 115, boolean_operator; 116, assignment; 117, boolean_operator; 118, block; 119, call; 120, identifier:prevBucket; 121, None; 122, boolean_operator; 123, call; 124, identifier:openElems; 125, identifier:elementIter; 126, attribute; 127, attribute; 128, attribute; 129, identifier:bucket; 130, list_comprehension; 131, identifier:previous; 132, None; 133, parenthesized_expression; 134, parenthesized_expression; 135, identifier:GenomicIntervalError; 136, argument_list; 137, identifier:len; 138, argument_list; 139, parenthesized_expression; 140, parenthesized_expression; 141, identifier:heappop; 142, argument_list; 143, call; 144, None; 145, parenthesized_expression; 146, parenthesized_expression; 147, identifier:e; 148, call; 149, parenthesized_expression; 150, line_continuation:\; 151, parenthesized_expression; 152, continue_statement; 153, identifier:heappush; 154, argument_list; 155, parenthesized_expression; 156, parenthesized_expression; 157, identifier:GenomicIntervalError; 158, argument_list; 159, identifier:bucket; 160, identifier:chrom; 161, identifier:bucket; 162, identifier:start; 163, identifier:bucket; 164, identifier:end; 165, identifier:x; 166, for_in_clause; 167, if_clause; 168, comparison_operator:previous.chrom > current.chrom; 169, boolean_operator; 170, binary_operator:"elements not sorted. Saw " +
                                   str(previous) + " before " + str(current); 171, identifier:openHeap; 172, comparison_operator:openHeap[0].chrom < bucketChrom; 173, boolean_operator; 174, identifier:openHeap; 175, attribute; 176, argument_list; 177, comparison_operator:elementIterator.peek().chrom < bucketChrom; 178, boolean_operator; 179, attribute; 180, argument_list; 181, comparison_operator:e.chrom < bucketChrom; 182, boolean_operator; 183, identifier:openHeap; 184, identifier:e; 185, comparison_operator:bucket.chrom < prevBucket.chrom; 186, boolean_operator; 187, binary_operator:"regions-of-interest are not sorted. Saw " +
                                   str(prevBucket) + " before " + str(bucket); 188, identifier:x; 189, identifier:openElems; 190, comparison_operator:x.start < bucket.end; 191, attribute; 192, attribute; 193, parenthesized_expression; 194, parenthesized_expression; 195, binary_operator:"elements not sorted. Saw " +
                                   str(previous) + " before "; 196, call; 197, attribute; 198, identifier:bucketChrom; 199, parenthesized_expression; 200, parenthesized_expression; 201, identifier:elementIterator; 202, identifier:peek; 203, attribute; 204, identifier:bucketChrom; 205, parenthesized_expression; 206, parenthesized_expression; 207, identifier:elementIterator; 208, identifier:__next__; 209, attribute; 210, identifier:bucketChrom; 211, comparison_operator:e.chrom == bucketChrom; 212, comparison_operator:e.end <= bucketStart; 213, attribute; 214, attribute; 215, comparison_operator:bucket.chrom == prevBucket.chrom; 216, comparison_operator:bucket.start < prevBucket.start; 217, binary_operator:"regions-of-interest are not sorted. Saw " +
                                   str(prevBucket) + " before "; 218, call; 219, attribute; 220, attribute; 221, identifier:previous; 222, identifier:chrom; 223, identifier:current; 224, identifier:chrom; 225, comparison_operator:previous.chrom == current.chrom; 226, comparison_operator:previous.start > current.start; 227, binary_operator:"elements not sorted. Saw " +
                                   str(previous); 228, string:" before "; 229, identifier:str; 230, argument_list; 231, subscript; 232, identifier:chrom; 233, comparison_operator:openHeap[0].chrom == bucketChrom; 234, comparison_operator:openHeap[0].end <= bucketStart; 235, call; 236, identifier:chrom; 237, comparison_operator:elementIterator.peek().chrom == bucketChrom; 238, comparison_operator:elementIterator.peek().start < bucketEnd; 239, identifier:e; 240, identifier:chrom; 241, attribute; 242, identifier:bucketChrom; 243, attribute; 244, identifier:bucketStart; 245, identifier:bucket; 246, identifier:chrom; 247, identifier:prevBucket; 248, identifier:chrom; 249, attribute; 250, attribute; 251, attribute; 252, attribute; 253, binary_operator:"regions-of-interest are not sorted. Saw " +
                                   str(prevBucket); 254, string:" before "; 255, identifier:str; 256, argument_list; 257, identifier:x; 258, identifier:start; 259, identifier:bucket; 260, identifier:end; 261, attribute; 262, attribute; 263, attribute; 264, attribute; 265, string:"elements not sorted. Saw "; 266, call; 267, identifier:current; 268, identifier:openHeap; 269, integer:0; 270, attribute; 271, identifier:bucketChrom; 272, attribute; 273, identifier:bucketStart; 274, attribute; 275, argument_list; 276, attribute; 277, identifier:bucketChrom; 278, attribute; 279, identifier:bucketEnd; 280, identifier:e; 281, identifier:chrom; 282, identifier:e; 283, identifier:end; 284, identifier:bucket; 285, identifier:chrom; 286, identifier:prevBucket; 287, identifier:chrom; 288, identifier:bucket; 289, identifier:start; 290, identifier:prevBucket; 291, identifier:start; 292, string:"regions-of-interest are not sorted. Saw "; 293, call; 294, identifier:bucket; 295, identifier:previous; 296, identifier:chrom; 297, identifier:current; 298, identifier:chrom; 299, identifier:previous; 300, identifier:start; 301, identifier:current; 302, identifier:start; 303, identifier:str; 304, argument_list; 305, subscript; 306, identifier:chrom; 307, subscript; 308, identifier:end; 309, identifier:elementIterator; 310, identifier:peek; 311, call; 312, identifier:chrom; 313, call; 314, identifier:start; 315, identifier:str; 316, argument_list; 317, identifier:previous; 318, identifier:openHeap; 319, integer:0; 320, identifier:openHeap; 321, integer:0; 322, attribute; 323, argument_list; 324, attribute; 325, argument_list; 326, identifier:prevBucket; 327, identifier:elementIterator; 328, identifier:peek; 329, identifier:elementIterator; 330, identifier:peek
code: def bucketIterator(elements, buckets):
    """
    For each bucket in buckets, yield it and any elements that overlap it.
  
    :param elements: the genomic intervals to place into the buckets. Must be
                     sorted by chromosome and start index. This could be a
                     list, or an iterator.
    :param buckets: the buckets into which genomic intervals should be binned.
                    Must be sorted by chromosome and start index. This could be
                    a list, or an iterator
    :return: iterator that will yeild a tuple of 1 bucket and 1 list of elements
             in the bucket for each call to __next__().
    """
    def check_sorted(current, previous):
      if (previous is not None) and \
         ((previous.chrom > current.chrom) or
          ((previous.chrom == current.chrom) and
           (previous.start > current.start))):
        raise GenomicIntervalError("elements not sorted. Saw " +
                                   str(previous) + " before " + str(current))
  
    def updateOpen(openHeap, elementIterator, bucketChrom,
                   bucketStart, bucketEnd):
      """
      Drop elements from heap which start earlier than current bucket.
  
      Update the open heap so that it contains only elements that end after the
      start of the current bucket. Note that the heap may already contain some
      elements that start after the end of the current bucket, if a previous
      bucket ended after the end of this one and brought them into the set.
  
      :param openHeap: a min heap of elements; uses the default sorting order
                       for the genomic intervals, which is by end index. This
                       is what we're updating.
      :param elementIterator: an iterator from which we will pull new elements.
                              Elements yielded by this iterator must be sorted
                              by start index. Must be 'peakable'
      :param bucketChrom: the chromosome of the current bucket.
      :param bucketStart: the start index of the current bucket.
      :param bucketEnd: the end index of the current bucket.
      """
      # first, we're going to pop elements from the heap which can no longer
      # overalp this or any future buckets. Buckets are sorted by start, so
      # we'll never see another bucket that starts earlier than this one --
      # hence any elements that end before the start of this bucket will never be
      # used again and can be dropped. Elements in the heap are ordered by end
      # index, so once we reach an element in the heap that does not end before
      # the start of this bucket, we are sure that no others will come after it
      # which do end before the start of this bucket. So we can stop dropping.
      while len(openHeap) > 0 and ((openHeap[0].chrom < bucketChrom) or
                                   ((openHeap[0].chrom == bucketChrom) and
                                   (openHeap[0].end <= bucketStart))):
        heappop(openHeap)
  
      # now we're going to add new elements from the iterator to the heap. As
      # we know that elements in the iterator are sorted by start index, we know
      # that once we see an element that has a start index greater than the end
      # of this bucket, we can stop -- everything else after it will also start
      # after the end of this bucket.
      while (elementIterator.peek() is not None) and \
            ((elementIterator.peek().chrom < bucketChrom) or
             ((elementIterator.peek().chrom == bucketChrom) and
              (elementIterator.peek().start < bucketEnd))):
        e = elementIterator.__next__()
        # if e falls before this bucket, we can skip it; buckets are sorted by
        # start, so no other buckets start earlier than this one and so it
        # cannot intersect any others.
        if (e.chrom < bucketChrom) or \
           (e.chrom == bucketChrom and e.end <= bucketStart):
           continue
        # now we know e intersects this bucket..
        heappush(openHeap, e)
  
    openElems = []
    prevBucket = None
    elementIter = AutoApplyIterator(elements, check_sorted)
    for bucket in buckets:
      # make sure the buckets are sorted by start index
      if prevBucket is not None and ((bucket.chrom < prevBucket.chrom) or
                                     (bucket.chrom == prevBucket.chrom and
                                      bucket.start < prevBucket.start)):
        raise GenomicIntervalError("regions-of-interest are not sorted. Saw " +
                                   str(prevBucket) + " before " + str(bucket))
      updateOpen(openElems, elementIter, bucket.chrom, bucket. start, bucket.end)
  
      # be careful here not to leak a reference to the heap; if the caller
      # decides to mess with that list, it'll screw us up. Anyway, we need a
      # final check here to make sure we trim off any elements that exceed the
      # end of this bucket.
      yield bucket, [x for x in openElems if x.start < bucket.end]
      prevBucket = bucket