Get the union of a set of genomic intervals.

  given a list of genomic intervals with chromosome, start, end and strand
  fields, collapse those intervals with strand in the set <proc_strands>
  into a set of non-overlapping intervals. Other intervals are ignored.
  Intervals must be sorted by chromosome and then start coordinate.

  :note: O(n) time, O(n) space
  :return:  list of intervals that define the collapsed regions. Note that
            these are all new objects, no existing object from s is returned
            or altered. Returned regions will all have name "X" and score 0
  :param s:            list of genomic regions to collapse
  :param proc_strands: set of acceptable strands; ignore input intervals
                       with strand not found in this set.
  :param names:        if True, accumulate region names. If false, all output
                       regions have name "X"
  :param verbose:      if True, output progress message to stderr.
  :raise GenomicIntervalError: if the input regions are not correctly sorted
                               (chromosome then start)

def __collapse_stranded(s, proc_strands, names=False, verbose=False):
  """
  Get the union of a set of genomic intervals.

  given a list of genomic intervals with chromosome, start, end and strand
  fields, collapse those intervals with strand in the set <proc_strands>
  into a set of non-overlapping intervals. Other intervals are ignored.
  Intervals must be sorted by chromosome and then start coordinate.

  :note: O(n) time, O(n) space
  :return:  list of intervals that define the collapsed regions. Note that
            these are all new objects, no existing object from s is returned
            or altered. Returned regions will all have name "X" and score 0
  :param s:            list of genomic regions to collapse
  :param proc_strands: set of acceptable strands; ignore input intervals
                       with strand not found in this set.
  :param names:        if True, accumulate region names. If false, all output
                       regions have name "X"
  :param verbose:      if True, output progress message to stderr.
  :raise GenomicIntervalError: if the input regions are not correctly sorted
                               (chromosome then start)
  """
  def get_first_matching_index(s, proc_strands):
    for i in range(0, len(s)):
      if s[i].strand in proc_strands:
        return i
    return None

  if proc_strands not in [set("+"), set("-"), set(["+", "-"])]:
    raise GenomicIntervalError("failed collapsing intervals on strands '" +
                               ",".join(proc_strands) + "''; unrecognised " +
                               "strand symbols")

  first_index = get_first_matching_index(s, proc_strands)
  if first_index is None:
    return []

  res = []
  current = copy.copy(s[first_index])
  current.strand = '+' if (proc_strands == set("+") or
                           proc_strands == set(["+", "-"])) else '-'
  current.score = 0
  current.name = "X" if not names else set(s[first_index].name)
  for i in range(first_index + 1, len(s)):
    if s[i].strand not in proc_strands:
      continue

    # make sure things are sorted..
    if (s[i].chrom < s[i - 1].chrom) or \
       (s[i].chrom == s[i - 1].chrom and s[i].start < s[i - 1].start):
      raise GenomicIntervalError("collapsing regions failed. saw this " +
                                 "region: " + str(s[i - 1]) + " before this " +
                                 "one: " + str(s[i]))

    # because of sorting order, we know that nothing else exists with
    # start less than s[i] which we haven't already seen.
    if s[i].start > current.end or s[i].chrom != current.chrom:
      if names:
        current.name = ";".join(current.name)
      res.append(current)
      current = copy.copy(s[i])
      current.strand = '+' if (proc_strands == set("+") or
                               proc_strands == set(["+", "-"])) else '-'
      current.score = 0
      current.name = "X" if not names else set(s[i].name)
    else:
      current.end = max(s[i].end, current.end)
      if names:
        current.name.add(s[i].name)

  # don't forget the last one...
  if names:
    current.name = ";".join(current.name)
  res.append(current)

  return res