nodes: 0, module; 1, function_definition; 2, function_name:regionsIntersection; 3, parameters; 4, block; 5, identifier:s1; 6, identifier:s2; 7, default_parameter; 8, expression_statement; 9, expression_statement; 10, comment:# we don't need to explicitly check for sorting because sorted order is; 11, comment:# a post-condition of the collapsing function; 12, expression_statement; 13, expression_statement; 14, if_statement; 15, expression_statement; 16, expression_statement; 17, for_statement; 18, return_statement; 19, identifier:collapse; 20, True; 21, comment:"""
    given two lists of genomic regions with chromosome, start and end
    coordinates, return a new list of regions which is the intersection of those
    two sets. Lists must be sorted by chromosome and start index
  
    :return: new list that represents the intersection of the two input lists.
             output regions will all have name "X", be on strand "+" and have
             score 0
    :param s1: first list of genomic regions
    :param s2: second list of genomic regions
    :raise GenomicIntervalError: if the input regions are not sorted correctly
                                 (by chromosome and start index)
    :note: O(n) time, O(n) space; informally, might use up to 3x space of input
    """; 22, assignment; 23, assignment; 24, assignment; 25, boolean_operator; 26, block; 27, assignment; 28, assignment; 29, identifier:i; 30, call; 31, block; 32, identifier:res; 33, identifier:debug; 34, False; 35, identifier:s1_c; 36, call; 37, identifier:s2_c; 38, call; 39, comparison_operator:len(s1_c) == 0; 40, comparison_operator:len(s2_c) == 0; 41, return_statement; 42, identifier:res; 43, list; 44, identifier:j; 45, integer:0; 46, identifier:range; 47, argument_list; 48, if_statement; 49, comment:# find first thing in s2_c with end in or after s1_c[i]; 50, if_statement; 51, while_statement; 52, comment:# nothing intersects if we hit the end of s2, or the end of the chrom,; 53, comment:# or we're still on the same chrom but start after the end of s2_c[i]; 54, if_statement; 55, comment:# now everything at or after j in s2_c that starts before; 56, comment:# the end of s1_c must overlap with it; 57, while_statement; 58, comment:# it's possible the last intersecting element runs on to the; 59, comment:# next element from s1_c, so...; 60, expression_statement; 61, if_statement; 62, identifier:collapseRegions; 63, argument_list; 64, identifier:collapseRegions; 65, argument_list; 66, call; 67, integer:0; 68, call; 69, integer:0; 70, list; 71, integer:0; 72, call; 73, identifier:debug; 74, block; 75, identifier:debug; 76, block; 77, parenthesized_expression; 78, block; 79, boolean_operator; 80, block; 81, comparison_operator:s2_c[j].start < s1_c[i].end; 82, block; 83, augmented_assignment; 84, identifier:debug; 85, block; 86, identifier:s1; 87, identifier:s2; 88, identifier:len; 89, argument_list; 90, identifier:len; 91, argument_list; 92, identifier:len; 93, argument_list; 94, expression_statement; 95, expression_statement; 96, boolean_operator; 97, expression_statement; 98, boolean_operator; 99, line_continuation:\; 100, parenthesized_expression; 101, continue_statement; 102, attribute; 103, attribute; 104, expression_statement; 105, expression_statement; 106, expression_statement; 107, if_statement; 108, expression_statement; 109, expression_statement; 110, if_statement; 111, identifier:j; 112, integer:1; 113, expression_statement; 114, identifier:s1_c; 115, identifier:s2_c; 116, identifier:s1_c; 117, call; 118, call; 119, comparison_operator:j < len(s2_c); 120, parenthesized_expression; 121, augmented_assignment; 122, comparison_operator:j >= len(s2_c); 123, comparison_operator:s2_c[j].chrom > s1_c[i].chrom; 124, boolean_operator; 125, subscript; 126, identifier:start; 127, subscript; 128, identifier:end; 129, assignment; 130, assignment; 131, assignment; 132, identifier:debug; 133, block; 134, call; 135, augmented_assignment; 136, boolean_operator; 137, block; 138, call; 139, attribute; 140, argument_list; 141, attribute; 142, argument_list; 143, identifier:j; 144, call; 145, boolean_operator; 146, identifier:j; 147, integer:1; 148, identifier:j; 149, call; 150, attribute; 151, attribute; 152, comparison_operator:s2_c[j].chrom == s1_c[i].chrom; 153, comparison_operator:s2_c[j].start >= s1_c[i].end; 154, identifier:s2_c; 155, identifier:j; 156, identifier:s1_c; 157, identifier:i; 158, identifier:s; 159, call; 160, identifier:e; 161, call; 162, identifier:overlap; 163, call; 164, expression_statement; 165, attribute; 166, argument_list; 167, identifier:j; 168, integer:1; 169, comparison_operator:j >= len(s2_c); 170, comparison_operator:s2_c[j].chrom != s1_c[i].chrom; 171, break_statement; 172, attribute; 173, argument_list; 174, attribute; 175, identifier:write; 176, binary_operator:"processing from s1_c : " + str(s1_c[i]) + "\n"; 177, attribute; 178, identifier:write; 179, binary_operator:"i = " + str(i) + " and j = " + str(j) + "\n"; 180, identifier:len; 181, argument_list; 182, comparison_operator:s2_c[j].chrom < s1_c[i].chrom; 183, parenthesized_expression; 184, identifier:len; 185, argument_list; 186, subscript; 187, identifier:chrom; 188, subscript; 189, identifier:chrom; 190, attribute; 191, attribute; 192, attribute; 193, attribute; 194, identifier:max; 195, argument_list; 196, identifier:min; 197, argument_list; 198, identifier:GenomicInterval; 199, argument_list; 200, call; 201, identifier:res; 202, identifier:append; 203, identifier:overlap; 204, identifier:j; 205, call; 206, attribute; 207, attribute; 208, attribute; 209, identifier:write; 210, binary_operator:"\tmoving s2_c index back to " + str(s2_c[j]) + "\n"; 211, identifier:sys; 212, identifier:stderr; 213, binary_operator:"processing from s1_c : " + str(s1_c[i]); 214, string:"\n"; 215, identifier:sys; 216, identifier:stderr; 217, binary_operator:"i = " + str(i) + " and j = " + str(j); 218, string:"\n"; 219, identifier:s2_c; 220, attribute; 221, attribute; 222, boolean_operator; 223, identifier:s2_c; 224, identifier:s2_c; 225, identifier:j; 226, identifier:s1_c; 227, identifier:i; 228, subscript; 229, identifier:chrom; 230, subscript; 231, identifier:chrom; 232, subscript; 233, identifier:start; 234, subscript; 235, identifier:end; 236, attribute; 237, attribute; 238, attribute; 239, attribute; 240, attribute; 241, identifier:s; 242, identifier:e; 243, string:"X"; 244, integer:0; 245, string:"+"; 246, attribute; 247, argument_list; 248, identifier:len; 249, argument_list; 250, subscript; 251, identifier:chrom; 252, subscript; 253, identifier:chrom; 254, identifier:sys; 255, identifier:stderr; 256, binary_operator:"\tmoving s2_c index back to " + str(s2_c[j]); 257, string:"\n"; 258, string:"processing from s1_c : "; 259, call; 260, binary_operator:"i = " + str(i) + " and j = "; 261, call; 262, subscript; 263, identifier:chrom; 264, subscript; 265, identifier:chrom; 266, comparison_operator:s2_c[j].chrom == s1_c[i].chrom; 267, comparison_operator:s2_c[j].end <= s1_c[i].start; 268, identifier:s2_c; 269, identifier:j; 270, identifier:s1_c; 271, identifier:i; 272, identifier:s2_c; 273, identifier:j; 274, identifier:s1_c; 275, identifier:i; 276, subscript; 277, identifier:start; 278, subscript; 279, identifier:start; 280, subscript; 281, identifier:end; 282, subscript; 283, identifier:end; 284, subscript; 285, identifier:chrom; 286, attribute; 287, identifier:write; 288, binary_operator:"\tadding to overlaps: " + str(overlap) + "\n"; 289, identifier:s2_c; 290, identifier:s2_c; 291, identifier:j; 292, identifier:s1_c; 293, identifier:i; 294, string:"\tmoving s2_c index back to "; 295, call; 296, identifier:str; 297, argument_list; 298, binary_operator:"i = " + str(i); 299, string:" and j = "; 300, identifier:str; 301, argument_list; 302, identifier:s2_c; 303, identifier:j; 304, identifier:s1_c; 305, identifier:i; 306, attribute; 307, attribute; 308, attribute; 309, attribute; 310, identifier:s1_c; 311, identifier:i; 312, identifier:s2_c; 313, identifier:j; 314, identifier:s1_c; 315, identifier:i; 316, identifier:s2_c; 317, identifier:j; 318, identifier:s1_c; 319, identifier:i; 320, identifier:sys; 321, identifier:stderr; 322, binary_operator:"\tadding to overlaps: " + str(overlap); 323, string:"\n"; 324, identifier:str; 325, argument_list; 326, subscript; 327, string:"i = "; 328, call; 329, identifier:j; 330, subscript; 331, identifier:chrom; 332, subscript; 333, identifier:chrom; 334, subscript; 335, identifier:end; 336, subscript; 337, identifier:start; 338, string:"\tadding to overlaps: "; 339, call; 340, subscript; 341, identifier:s1_c; 342, identifier:i; 343, identifier:str; 344, argument_list; 345, identifier:s2_c; 346, identifier:j; 347, identifier:s1_c; 348, identifier:i; 349, identifier:s2_c; 350, identifier:j; 351, identifier:s1_c; 352, identifier:i; 353, identifier:str; 354, argument_list; 355, identifier:s2_c; 356, identifier:j; 357, identifier:i; 358, identifier:overlap
code: def regionsIntersection(s1, s2, collapse=True):
    """
    given two lists of genomic regions with chromosome, start and end
    coordinates, return a new list of regions which is the intersection of those
    two sets. Lists must be sorted by chromosome and start index
  
    :return: new list that represents the intersection of the two input lists.
             output regions will all have name "X", be on strand "+" and have
             score 0
    :param s1: first list of genomic regions
    :param s2: second list of genomic regions
    :raise GenomicIntervalError: if the input regions are not sorted correctly
                                 (by chromosome and start index)
    :note: O(n) time, O(n) space; informally, might use up to 3x space of input
    """
    debug = False
  
    # we don't need to explicitly check for sorting because sorted order is
    # a post-condition of the collapsing function
    s1_c = collapseRegions(s1)
    s2_c = collapseRegions(s2)
  
    if len(s1_c) == 0 or len(s2_c) == 0:
      return []
  
    res = []
    j = 0
    for i in range(0, len(s1_c)):
      if debug:
        sys.stderr.write("processing from s1_c : " + str(s1_c[i]) + "\n")
  
      # find first thing in s2_c with end in or after s1_c[i]
      if debug:
        sys.stderr.write("i = " + str(i) + " and j = " + str(j) + "\n")
      while (j < len(s2_c) and
             (s2_c[j].chrom < s1_c[i].chrom or
             (s2_c[j].chrom == s1_c[i].chrom and s2_c[j].end <= s1_c[i].start))):
        j += 1
      # nothing intersects if we hit the end of s2, or the end of the chrom,
      # or we're still on the same chrom but start after the end of s2_c[i]
      if j >= len(s2_c) or s2_c[j].chrom > s1_c[i].chrom or \
         (s2_c[j].chrom == s1_c[i].chrom and s2_c[j].start >= s1_c[i].end):
        continue
  
      # now everything at or after j in s2_c that starts before
      # the end of s1_c must overlap with it
      while s2_c[j].start < s1_c[i].end:
        s = max(s1_c[i].start, s2_c[j].start)
        e = min(s1_c[i].end, s2_c[j].end)
        overlap = GenomicInterval(s1_c[i].chrom, s, e, "X", 0, "+")
        if debug:
          sys.stderr.write("\tadding to overlaps: " + str(overlap) + "\n")
        res.append(overlap)
        j += 1
        if j >= len(s2_c) or s2_c[j].chrom != s1_c[i].chrom:
          break
  
      # it's possible the last intersecting element runs on to the
      # next element from s1_c, so...
      j -= 1
      if debug:
        sys.stderr.write("\tmoving s2_c index back to " + str(s2_c[j]) + "\n")
  
    return res