#!/usr/bin/env python3


# Copyright 2016   Vimal Manohar
#           2016   Johns Hopkins University (author: Daniel Povey)
# Apache 2.0

from __future__ import print_function
from __future__ import division
import sys, operator, argparse, os
from collections import defaultdict

# This script reads 'ctm-edits' file format that is produced by get_ctm_edits.py
# and modified by modify_ctm_edits.py and taint_ctm_edits.py Its function is to
# produce a segmentation and text from the ctm-edits input.

# The ctm-edits file format that this script expects is as follows
# <file-id> <channel> <start-time> <duration> <conf> <hyp-word> <ref-word> <edit> ['tainted']
# [note: file-id is really utterance-id at this point].

parser = argparse.ArgumentParser(
    description = "This program produces segmentation and text information "
    "based on reading ctm-edits input format which is produced by "
    "steps/cleanup/internal/get_ctm_edits.py, steps/cleanup/internal/modify_ctm_edits.py and "
    "steps/cleanup/internal/taint_ctm_edits.py.",
 formatter_class=argparse.ArgumentDefaultsHelpFormatter)

parser.add_argument("--min-segment-length", type = float, default = 0.5,
                    help = "Minimum allowed segment length (in seconds) for any "
                    "segment; shorter segments than this will be discarded.")
parser.add_argument("--min-new-segment-length", type = float, default = 1.0,
                    help = "Minimum allowed segment length (in seconds) for newly "
                    "created segments (i.e. not identical to the input utterances). "
                    "Expected to be >= --min-segment-length.")
parser.add_argument("--frame-length", type = float, default = 0.01,
                    help = "This only affects rounding of the output times; they will "
                    "be constrained to multiples of this value.")
parser.add_argument("--max-tainted-length", type = float, default = 0.05,
                    help = "Maximum allowed length of any 'tainted' line.  Note: "
                    "'tainted' lines may only appear at the boundary of a "
                    "segment")
parser.add_argument("--max-edge-silence-length", type = float, default = 0.5,
                    help = "Maximum allowed length of silence if it appears at the "
                    "edge of a segment (will be truncated).  This rule is "
                    "relaxed if such truncation would take a segment below "
                    "the --min-segment-length or --min-new-segment-length.")
parser.add_argument("--max-edge-non-scored-length", type = float, default = 0.5,
                    help = "Maximum allowed length of a non-scored word (noise, cough, etc.) "
                    "if it appears at the edge of a segment (will be truncated). "
                    "This rule is relaxed if such truncation would take a "
                    "segment below the --min-segment-length.")
parser.add_argument("--max-internal-silence-length", type = float, default = 2.0,
                    help = "Maximum allowed length of silence if it appears inside a segment "
                    "(will cause the segment to be split).")
parser.add_argument("--max-internal-non-scored-length", type = float, default = 2.0,
                    help = "Maximum allowed length of a non-scored word (noise, etc.) if "
                    "it appears inside a segment (will cause the segment to be "
                    "split).  Note: reference words which are real words but OOV "
                    "are not included in this category.")
parser.add_argument("--unk-padding", type = float, default = 0.05,
                    help = "Amount of padding with <unk> that we do if a segment boundary is "
                    "next to errors (ins, del, sub).  That is, we add this amount of "
                    "time to the segment and add the <unk> word to cover the acoustics. "
                    "If nonzero, the --oov-symbol-file option must be supplied.")
parser.add_argument("--max-junk-proportion", type = float, default = 0.1,
                    help = "Maximum proportion of the time of the segment that may "
                    "consist of potentially bad data, in which we include 'tainted' lines of "
                    "the ctm-edits input and unk-padding.")
parser.add_argument("--min-split-point-duration", type=float, default=0.1,
                    help="""Minimum duration of silence or non-scored word
                    to be considered a viable split point when
                    truncating based on junk proportion.""")
parser.add_argument("--max-deleted-words-kept-when-merging", type = int, default = 1,
                    help = "When merging segments that are found to be overlapping or "
                    "adjacent after all other processing, keep in the transcript the "
                    "reference words that were deleted between the segments [if any] "
                    "as long as there were no more than this many reference words. "
                    "Setting this to zero will mean that any reference words that "
                    "were deleted between the segments we're about to reattach will "
                    "not appear in the generated transcript (so we'll match the hyp).")
parser.add_argument("--oov-symbol-file", type = str, default = None,
                    help = "Filename of file such as data/lang/oov.txt which contains "
                    "the text form of the OOV word, normally '<unk>'.  Supplied as "
                    "a file to avoid complications with escaping.  Necessary if "
                    "the --unk-padding option has a nonzero value (which it does "
                    "by default.")
parser.add_argument("--ctm-edits-out", type = str,
                    help = "Filename to output an extended version of the ctm-edits format "
                    "with segment start and end points noted.  This file is intended to be "
                    "read by humans; there are currently no scripts that will read it.")
parser.add_argument("--word-stats-out", type = str,
                    help = "Filename for output of word-level stats, of the form "
                    "'<word> <bad-proportion> <total-count-in-ref>', e.g. 'hello 0.12 12408', "
                    "where the <bad-proportion> is the proportion of the time that this "
                    "reference word does not make it into a segment.  It can help reveal words "
                    "that have problematic pronunciations or are associated with "
                    "transcription errors.")


parser.add_argument("non_scored_words_in", metavar = "<non-scored-words-file>",
                    help="Filename of file containing a list of non-scored words, "
                    "one per line. See steps/cleanup/internal/get_nonscored_words.py.")
parser.add_argument("ctm_edits_in", metavar = "<ctm-edits-in>",
                    help = "Filename of input ctm-edits file. "
                    "Use /dev/stdin for standard input.")
parser.add_argument("text_out", metavar = "<text-out>",
                    help = "Filename of output text file (same format as data/train/text, i.e. "
                    "<new-utterance-id> <word1> <word2> ... <wordN>")
parser.add_argument("segments_out", metavar = "<segments-out>",
                    help = "Filename of output segments.  This has the same format as data/train/segments, "
                    "but instead of <recording-id>, the second field is the old utterance-id, i.e "
                    "<new-utterance-id> <old-utterance-id> <start-time> <end-time>")

args = parser.parse_args()




def IsTainted(split_line_of_utt):
    return len(split_line_of_utt) > 8 and split_line_of_utt[8] == 'tainted'

# This function returns a list of pairs (start-index, end-index) representing
# the cores of segments (so if a pair is (s, e), then the core of a segment
# would span (s, s+1, ... e-1).
#
# By the 'core of a segment', we mean a sequence of ctm-edits lines including at
# least one 'cor' line and a contiguous sequence of other lines of the type
# 'cor', 'fix' and 'sil' that must be not tainted.  The segment core excludes
# any tainted lines at the edge of a segment, which will be added later.
#
# We only initiate segments when it contains something correct and not realized
# as unk (i.e. ref==hyp); and we extend it with anything that is 'sil' or 'fix'
# or 'cor' that is not tainted.  Contiguous regions of 'true' in the resulting
# boolean array will then become the cores of prototype segments, and we'll add
# any adjacent tainted words (or parts of them).
def ComputeSegmentCores(split_lines_of_utt):
    num_lines = len(split_lines_of_utt)
    line_is_in_segment_core = [ False] * num_lines
    for i in range(num_lines):
        if split_lines_of_utt[i][7] == 'cor' and \
            split_lines_of_utt[i][4] == split_lines_of_utt[i][6]:
            line_is_in_segment_core[i] = True

    # extend each proto-segment forwards as far as we can:
    for i in range(1, num_lines):
        if line_is_in_segment_core[i-1] and not line_is_in_segment_core[i]:
            edit_type = split_lines_of_utt[i][7]
            if not IsTainted(split_lines_of_utt[i]) and \
                (edit_type == 'cor' or edit_type == 'sil' or edit_type == 'fix'):
                line_is_in_segment_core[i] = True

    # extend each proto-segment backwards as far as we can:
    for i in reversed(range(0, num_lines - 1)):
        if line_is_in_segment_core[i+1] and not line_is_in_segment_core[i]:
            edit_type = split_lines_of_utt[i][7]
            if not IsTainted(split_lines_of_utt[i]) and \
               (edit_type == 'cor' or edit_type == 'sil' or edit_type == 'fix'):
                line_is_in_segment_core[i] = True


    segment_ranges = []
    cur_segment_start = None
    for i in range(0, num_lines):
        if line_is_in_segment_core[i]:
            if cur_segment_start == None:
                cur_segment_start = i
        else:
            if cur_segment_start != None:
                segment_ranges.append( (cur_segment_start, i) )
                cur_segment_start = None
    if cur_segment_start != None:
        segment_ranges.append( (cur_segment_start, num_lines) )

    return segment_ranges

class Segment(object):
    def __init__(self, split_lines_of_utt, start_index, end_index, debug_str = None):
        self.split_lines_of_utt = split_lines_of_utt
        # start_index is the index of the first line that appears in this
        # segment, and end_index is one past the last line.  This does not
        # include unk-padding.
        self.start_index = start_index
        self.end_index = end_index
        # If the following values are nonzero, then when we create the segment
        # we will add <unk> at the start and end of the segment [representing
        # partial words], with this amount of additional audio.
        self.start_unk_padding = 0.0
        self.end_unk_padding = 0.0

        # debug_str keeps track of the 'core' of the segment.
        if debug_str == None:
            debug_str = 'core-start={0},core-end={1}'.format(start_index,end_index)
        self.debug_str = debug_str

        # This gives the proportion of the time of the first line in the segment
        # that we keep.  Usually 1.0 but may be less if we've trimmed away some
        # proportion of the time.
        self.start_keep_proportion = 1.0
        # This gives the proportion of the time of the last line in the segment
        # that we keep.  Usually 1.0 but may be less if we've trimmed away some
        # proportion of the time.
        self.end_keep_proportion = 1.0

    # This is stage 1 of segment processing (after creating the boundaries of the
    # core of the segment, which is done outside of this class).a
    #
    # This function may reduce start_index and/or increase end_index by
    # including a single adjacent 'tainted' line from the ctm-edits file.  This
    # is only done if the lines at the boundaries of the segment are currently
    # real non-silence words and not non-scored words.  The idea is that we
    # probably don't want to start or end the segment right at the boundary of a
    # real word, we want to add some kind of padding.
    def PossiblyAddTaintedLines(self):
        global non_scored_words
        split_lines_of_utt = self.split_lines_of_utt
        # we're iterating over the segment (start, end)
        for b in [False, True]:
            if b:
                boundary_index = self.end_index - 1
                adjacent_index = self.end_index
            else:
                boundary_index = self.start_index
                adjacent_index = self.start_index - 1
            if adjacent_index >= 0 and adjacent_index < len(split_lines_of_utt):
                # only consider merging the adjacent word into the segment if we're not
                # at a segment boundary.
                adjacent_line_is_tainted = IsTainted(split_lines_of_utt[adjacent_index])
                # if the adjacent line wasn't tainted, then there must have been
                # another stronger reason why we didn't include it in the core
                # of the segment (probably that it was an ins, del or sub), so
                # there is no point considering it.
                if adjacent_line_is_tainted:
                    boundary_edit_type = split_lines_of_utt[boundary_index][7]
                    boundary_hyp_word = split_lines_of_utt[boundary_index][7]
                    # we only add the tainted line to the segment if the word at
                    # the boundary was a non-silence word that was correctly
                    # decoded and not fixed [see modify_ctm_edits.py.]
                    if boundary_edit_type == 'cor' and \
                       not boundary_hyp_word in non_scored_words:
                        # Add the adjacent tainted line to the segment.
                        if b:
                            self.end_index += 1
                        else:
                            self.start_index -= 1

    # This is stage 2 of segment processing.
    # This function will split a segment into multiple pieces if any of the
    # internal [non-boundary] silences or non-scored words are longer
    # than the allowed values --max-internal-silence-length and
    # --max-internal-non-scored-length.  This function returns a
    # list of segments.  In the normal case (where there is no splitting)
    # it just returns an array with a single element 'self'.
    def PossiblySplitSegment(self):
        global non_scored_words, args
        # make sure the segment hasn't been processed more than we expect.
        assert self.start_unk_padding == 0.0 and self.end_unk_padding == 0.0 and \
              self.start_keep_proportion == 1.0 and self.end_keep_proportion == 1.0
        segments = []  # the answer
        cur_start_index = self.start_index
        cur_start_is_split = False
        # only consider splitting at non-boundary lines.  [we'd just truncate
        # the boundary lines.]
        for index_to_split_at in range(cur_start_index + 1, self.end_index - 1):
            this_split_line = self.split_lines_of_utt[index_to_split_at]
            this_duration = float(this_split_line[3])
            this_edit_type = this_split_line[7]
            this_ref_word = this_split_line[6]
            if (this_edit_type == 'sil' and this_duration > args.max_internal_silence_length) or \
               (this_ref_word in non_scored_words and this_duration > args.max_internal_non_scored_length):
                # We split this segment at this index, dividing the word in two
                # [later on, in PossiblyTruncateBoundaries, it may be further
                # truncated.]
                # Note: we use 'index_to_split_at + 1' because the Segment constructor
                # takes an 'end-index' which is interpreted as one past the end.
                new_segment = Segment(self.split_lines_of_utt, cur_start_index,
                                      index_to_split_at + 1, self.debug_str)
                if cur_start_is_split:
                    new_segment.start_keep_proportion = 0.5
                new_segment.end_keep_proportion = 0.5
                cur_start_is_split = True
                cur_start_index = index_to_split_at
                segments.append(new_segment)
        if len(segments) == 0:  # We did not split.
            segments.append(self)
        else:
            # We did split.  Add the very last segment.
            new_segment = Segment(self.split_lines_of_utt, cur_start_index,
                                  self.end_index, self.debug_str)
            assert cur_start_is_split
            new_segment.start_keep_proportion = 0.5
            segments.append(new_segment)
        return segments


    # This is stage 3 of segment processing.  It will truncate the silences and
    # non-scored words at the segment boundaries if they are longer than the
    # --max-edge-silence-length and --max-edge-non-scored-length respectively
    # (and to the extent that this wouldn't take us below the
    # --min-segment-length or --min-new-segment-length).
    def PossiblyTruncateBoundaries(self):
        for b in [True, False]:
            if b:
                this_index = self.start_index
            else:
                this_index = self.end_index - 1
            this_split_line = self.split_lines_of_utt[this_index]
            truncated_duration = None
            this_duration = float(this_split_line[3])
            this_edit = this_split_line[7]
            this_ref_word = this_split_line[6]
            if this_edit == 'sil' and \
               this_duration > args.max_edge_silence_length:
                truncated_duration = args.max_edge_silence_length
            elif this_ref_word in non_scored_words and \
                 this_duration > args.max_edge_non_scored_length:
                truncated_duration = args.max_edge_non_scored_length
            if truncated_duration != None:
                keep_proportion = truncated_duration / this_duration
                if b:
                    self.start_keep_proportion = keep_proportion
                else:
                    self.end_keep_proportion = keep_proportion

    # This relaxes the segment-boundary truncation of
    # PossiblyTruncateBoundaries(), if it would take us below
    # min-new-segment-length or min-segment-length.  Note: this does not relax
    # the boundary truncation for a particular boundary (start or end) if that
    # boundary corresponds to a 'tainted' line of the ctm (because it's
    # dangerous to include too much 'tainted' audio).
    def RelaxBoundaryTruncation(self):
        # this should be called before adding unk padding.
        assert self.start_unk_padding == self.end_unk_padding == 0.0
        if self.start_keep_proportion == self.end_keep_proportion == 1.0:
            return  # nothing to do there was no truncation.
        length_cutoff = max(args.min_new_segment_length, args.min_segment_length)
        length_with_truncation = self.Length()
        if length_with_truncation >= length_cutoff:
            return  # Nothing to do.
        orig_start_keep_proportion = self.start_keep_proportion
        orig_end_keep_proportion = self.end_keep_proportion
        if not IsTainted(self.split_lines_of_utt[self.start_index]):
            self.start_keep_proportion = 1.0
        if not IsTainted(self.split_lines_of_utt[self.end_index - 1]):
            self.end_keep_proportion = 1.0
        length_with_relaxed_boundaries = self.Length()
        if length_with_relaxed_boundaries <= length_cutoff:
            # Completely undo the truncation [to the extent allowed by the
            # presence of tainted lines at the start/end] if, even without
            # truncation, we'd be below the length cutoff.  This segment may be
            # removed later on (but it may not, if removing truncation makes us
            # identical to the input utterance, and the length is between
            # min_segment_length min_new_segment_length).
            return
        # Next, compute an interpolation constant a such that the
        # {start,end}_keep_proportion values will equal a *
        # [values-computed-by-PossiblyTruncateBoundaries()] + (1-a) * [completely-relaxed-values].
        # we're solving the equation:
        # length_cutoff = a * length_with_truncation + (1-a) * length_with_relaxed_boundaries
        # -> length_cutoff - length_with_relaxed_boundaries =
        #        a * (length_with_truncation - length_with_relaxed_boundaries)
        # -> a = (length_cutoff - length_with_relaxed_boundaries) / (length_with_truncation - length_with_relaxed_boundaries)
        a = (length_cutoff - length_with_relaxed_boundaries) / \
            (length_with_truncation - length_with_relaxed_boundaries)
        if a < 0.0 or a > 1.0:
            print("segment_ctm_edits.py: bad 'a' value = {0}".format(a), file = sys.stderr)
            return
        self.start_keep_proportion = \
           a * orig_start_keep_proportion + (1-a) * self.start_keep_proportion
        self.end_keep_proportion = \
           a * orig_end_keep_proportion + (1-a) * self.end_keep_proportion
        if not abs(self.Length() - length_cutoff) < 0.01:
            print("segment_ctm_edits.py: possible problem relaxing boundary "
                  "truncation, length is {0} vs {1}".format(self.Length(), length_cutoff),
                  file = sys.stderr)


    # This is stage 4 of segment processing.
    # This function may set start_unk_padding and end_unk_padding to nonzero
    # values.  This is done if the current boundary words are real, scored
    # words and we're not next to the beginning or end of the utterance.
    def PossiblyAddUnkPadding(self):
        for b in [True, False]:
            if b:
                this_index = self.start_index
            else:
                this_index = self.end_index - 1
            this_split_line = self.split_lines_of_utt[this_index]
            this_start_time = float(this_split_line[2])
            this_ref_word = this_split_line[6]
            this_edit = this_split_line[7]
            if this_edit == 'cor' and not this_ref_word in non_scored_words:
                # we can consider adding unk-padding.
                if b: # start of utterance.
                    unk_padding = args.unk_padding
                    if unk_padding > this_start_time:  # close to beginning of file
                        unk_padding = this_start_time
                    # If we could add less than half of the specified
                    # unk-padding, don't add any (because when we add
                    # unk-padding we add the unknown-word symbol '<unk>', and if
                    # there isn't enough space to traverse the HMM we don't want
                    # to do it at all.
                    if unk_padding < 0.5 * args.unk_padding:
                        unk_padding = 0.0
                    self.start_unk_padding = unk_padding
                else: # end of utterance.
                    this_end_time = this_start_time + float(this_split_line[3])
                    last_line = self.split_lines_of_utt[-1]
                    utterance_end_time = float(last_line[2]) + float(last_line[3])
                    max_allowable_padding = utterance_end_time - this_end_time
                    assert max_allowable_padding > -0.01
                    unk_padding = args.unk_padding
                    if unk_padding > max_allowable_padding:
                        unk_padding = max_allowable_padding
                    # If we could add less than half of the specified
                    # unk-padding, don't add any (because when we add
                    # unk-padding we add the unknown-word symbol '<unk>', and if
                    # there isn't enough space to traverse the HMM we don't want
                    # to do it at all.
                    if unk_padding < 0.5 * args.unk_padding:
                        unk_padding = 0.0
                    self.end_unk_padding = unk_padding

    # This function will merge the segment in 'other' with the segment
    # in 'self'.  It is only to be called when 'self' and 'other' are from
    # the same utterance, 'other' is after 'self' in time order (based on
    # the original segment cores), and self.EndTime() >= other.StartTime().
    # Note: in this situation there will normally be deleted words
    # between the two segments.  What this program does with the deleted
    # words depends on '--max-deleted-words-kept-when-merging'.  If there
    # were any inserted words in the transcript (less likely), this
    # program will keep the reference.
    def MergeWithSegment(self, other):
        assert self.EndTime() >= other.StartTime() and \
               self.StartTime() < other.EndTime() and \
               self.split_lines_of_utt is other.split_lines_of_utt
        orig_self_end_index = self.end_index
        self.debug_str = "({0}/merged-with/{1})".format(self.debug_str, other.debug_str)
        # everything that relates to the end of this segment gets copied
        # from 'other'.
        self.end_index = other.end_index
        self.end_unk_padding = other.end_unk_padding
        self.end_keep_proportion = other.end_keep_proportion
        # The next thing we have to do is to go over any lines of the ctm that
        # appear between 'self' and 'other', or are shared between both (this
        # would only happen for tainted silence or non-scored-word segments),
        # and decide what to do with them.  We'll keep the reference for any
        # substitutions or insertions (which anyway are unlikely to appear
        # in these merged segments).  Note: most of this happens in self.Text(),
        # but at this point we need to decide whether to mark any deletions
        # as 'discard-this-word'.
        first_index_of_overlap = min(orig_self_end_index - 1, other.start_index)
        last_index_of_overlap = max(orig_self_end_index - 1, other.start_index)
        num_deleted_words = 0
        for i in range(first_index_of_overlap, last_index_of_overlap + 1):
            edit_type = self.split_lines_of_utt[i][7]
            if edit_type == 'del':
                num_deleted_words += 1
        if num_deleted_words > args.max_deleted_words_kept_when_merging:
            for i in range(first_index_of_overlap, last_index_of_overlap + 1):
                if self.split_lines_of_utt[i][7] == 'del':
                    self.split_lines_of_utt[i].append('do-not-include-in-text')

    # Returns the start time of the utterance (within the enclosing utterance)
    # This is before any rounding.
    def StartTime(self):
        first_line = self.split_lines_of_utt[self.start_index]
        first_line_start = float(first_line[2])
        first_line_duration = float(first_line[3])
        first_line_end = first_line_start + first_line_duration
        return first_line_end - self.start_unk_padding \
              - (first_line_duration * self.start_keep_proportion)

    # Returns some string-valued information about 'this' that is useful for debugging.
    def DebugInfo(self):
        return 'start=%d,end=%d,unk-padding=%.2f,%.2f,keep-proportion=%.2f,%.2f,' % \
            (self.start_index, self.end_index, self.start_unk_padding,
             self.end_unk_padding, self.start_keep_proportion, self.end_keep_proportion) + \
         self.debug_str

    # Returns the start time of the utterance (within the enclosing utterance)
    def EndTime(self):
        last_line = self.split_lines_of_utt[self.end_index - 1]
        last_line_start = float(last_line[2])
        last_line_duration = float(last_line[3])
        return last_line_start + (last_line_duration * self.end_keep_proportion) \
             + self.end_unk_padding

    # Returns the segment length in seconds.
    def Length(self):
        return self.EndTime() - self.StartTime()

    def IsWholeUtterance(self):
        # returns true if this segment corresponds to the whole utterance that
        # it's a part of (i.e. its start/end time are zero and the end-time of
        # the last segment.
        last_line_of_utt = self.split_lines_of_utt[-1]
        last_line_end_time = float(last_line_of_utt[2]) + float(last_line_of_utt[3])
        return abs(self.StartTime() - 0.0) < 0.001 and \
               abs(self.EndTime() - last_line_end_time) < 0.001

    # Returns the proportion of the duration of this segment that consists of
    # unk-padding and tainted lines of input (will be between 0.0 and 1.0).
    def JunkProportion(self):
        # Note: only the first and last lines could possibly be tainted as
        # that's how we create the segments; and if either or both are tainted
        # the utterance must contain other lines, so double-counting is not a
        # problem.
        junk_duration = self.start_unk_padding + self.end_unk_padding
        first_split_line = self.split_lines_of_utt[self.start_index]
        if IsTainted(first_split_line):
            first_duration = float(first_split_line[3])
            junk_duration += first_duration * self.start_keep_proportion
        last_split_line = self.split_lines_of_utt[self.end_index - 1]
        if IsTainted(last_split_line):
            last_duration = float(last_split_line[3])
            junk_duration += last_duration * self.end_keep_proportion
        return junk_duration / self.Length()

    # This function will remove something from the beginning of the
    # segment if it's possible to cleanly lop off a bit that contains
    # more junk, as a proportion of its length, than 'args.junk_proportion'.
    # Junk is defined as unk-padding and/or tainted segments.
    # It considers as a potential split point, the first silence
    # segment or non-tainted non-scored-word segment in the
    # utterance.  See also TruncateEndForJunkProportion
    def PossiblyTruncateStartForJunkProportion(self):
        begin_junk_duration = self.start_unk_padding
        first_split_line = self.split_lines_of_utt[self.start_index]
        if IsTainted(first_split_line):
            first_duration = float(first_split_line[3])
            begin_junk_duration += first_duration * self.start_keep_proportion
        if begin_junk_duration == 0.0:
            # nothing to do.
            return

        candidate_start_index = None
        # the following iterates over all lines internal to the utterance.
        for i in range(self.start_index + 1, self.end_index - 1):
            this_split_line = self.split_lines_of_utt[i]
            this_edit_type = this_split_line[7]
            this_ref_word = this_split_line[6]
            # We'll consider splitting on silence and on non-scored words.
            # (i.e. making the silence or non-scored word the left boundary of
            # the new utterance and discarding the piece to the left of that).
            if ((this_edit_type == 'sil'
                 or (this_edit_type == 'cor'
                     and this_ref_word in non_scored_words))
                and (float(this_split_line[3])
                     > args.min_split_point_duration)):
                candidate_start_index = i
                candidate_start_time = float(this_split_line[2])
                break  # Consider only the first potential truncation.
        if candidate_start_index is None:
            return  # Nothing to do as there is no place to split.
        candidate_removed_piece_duration = candidate_start_time - self.StartTime()
        if float(begin_junk_duration) / candidate_removed_piece_duration < args.max_junk_proportion:
            return  # Nothing to do as the candidate piece to remove has too
                    # little junk.
        # OK, remove the piece.
        self.start_index = candidate_start_index
        self.start_unk_padding = 0.0
        self.start_keep_proportion = 1.0
        self.debug_str += ',truncated-start-for-junk'

    # This is like PossiblyTruncateStartForJunkProportion(), but
    # acts on the end of the segment; see comments there.
    def PossiblyTruncateEndForJunkProportion(self):
        end_junk_duration = self.end_unk_padding
        last_split_line = self.split_lines_of_utt[self.end_index - 1]
        if IsTainted(last_split_line):
            last_duration = float(last_split_line[3])
            end_junk_duration += last_duration * self.end_keep_proportion
        if end_junk_duration == 0.0:
            # nothing to do.
            return

        candidate_end_index = None
        # the following iterates over all lines internal to the utterance
        # (starting from the end).
        for i in reversed(range(self.start_index + 1, self.end_index - 1)):
            this_split_line = self.split_lines_of_utt[i]
            this_edit_type = this_split_line[7]
            this_ref_word = this_split_line[6]
            # We'll consider splitting on silence and on non-scored words.
            # (i.e. making the silence or non-scored word the right boundary of
            # the new utterance and discarding the piece to the right of that).
            if ((this_edit_type == 'sil'
                 or (this_edit_type == 'cor'
                     and this_ref_word in non_scored_words))
                and (float(this_split_line[3])
                     > args.min_split_point_duration)):
                candidate_end_index = i + 1  # note: end-indexes are one past the last.
                candidate_end_time = float(this_split_line[2]) + float(this_split_line[3])
                break  # Consider only the latest potential truncation.
        if candidate_end_index is None:
            return  # Nothing to do as there is no place to split.
        candidate_removed_piece_duration = self.EndTime() - candidate_end_time
        if float(end_junk_duration) / candidate_removed_piece_duration < args.max_junk_proportion:
            return  # Nothing to do as the candidate piece to remove has too
                    # little junk.
        # OK, remove the piece.
        self.end_index = candidate_end_index
        self.end_unk_padding = 0.0
        self.end_keep_proportion = 1.0
        self.debug_str += ',truncated-end-for-junk'


    # this will return true if there is at least one word in the utterance
    # that's a scored word (not a non-scored word) and not an OOV word that's
    # realized as unk.  This becomes a filter on keeping segments.
    def ContainsAtLeastOneScoredNonOovWord(self):
        global non_scored_words
        for i in range(self.start_index, self.end_index):
            this_split_line = self.split_lines_of_utt[i]
            this_hyp_word = this_split_line[4]
            this_ref_word = this_split_line[6]
            this_edit = this_split_line[7]
            if this_edit == 'cor' and not this_ref_word in non_scored_words \
               and this_ref_word == this_hyp_word:
                return True
        return False

    # Returns the text corresponding to this utterance, as a string.
    def Text(self):
        global oov_symbol
        text_array = []
        if self.start_unk_padding != 0.0:
            text_array.append(oov_symbol)
        for i in range(self.start_index, self.end_index):
            this_split_line = self.split_lines_of_utt[i]
            this_edit = this_split_line[7]
            this_ref_word = this_split_line[6]
            if this_ref_word != '<eps>' and this_split_line[-1] != 'do-not-include-in-text':
                text_array.append(this_ref_word)
        if self.end_unk_padding != 0.0:
            text_array.append(oov_symbol)
        return ' '.join(text_array)


# Here, 'text' will be something that indicates the stage of processing,
# e.g. 'Stage 0: segment cores', 'Stage 1: add tainted lines',
#, etc.
def AccumulateSegmentStats(segment_list, text):
    global segment_total_length, num_segments
    for segment in segment_list:
        num_segments[text] += 1
        segment_total_length[text] += segment.Length()

def PrintSegmentStats():
    global segment_total_length, num_segments, \
       num_utterances, num_utterances_without_segments, \
       total_length_of_utterances

    print('Number of utterances is %d, of which %.2f%% had no segments after '
          'all processing; total length of data in original utterances (in seconds) '
          'was %d' % (num_utterances,
                      num_utterances_without_segments * 100.0 / num_utterances,
                      total_length_of_utterances),
          file = sys.stderr)


    keys = sorted(segment_total_length.keys())
    for i in range(len(keys)):
        key = keys[i]
        if i > 0:
            delta_percentage = '[%+.2f%%]' % ((segment_total_length[key] - segment_total_length[keys[i-1]])
                                              * 100.0 / total_length_of_utterances)
        print('At %s, num-segments is %d, total length %.2f%% of original total %s' % (
                key, num_segments[key],
                segment_total_length[key] * 100.0 / total_length_of_utterances,
                delta_percentage if i > 0 else ''),
              file = sys.stderr)

# This function creates the segments for an utterance as a list
# of class Segment.
# It returns a 2-tuple (list-of-segments, list-of-deleted-segments)
# where the deleted segments are only useful for diagnostic printing.
# Note: split_lines_of_utt is a list of lists, one per line, each containing the
# sequence of fields.
def GetSegmentsForUtterance(split_lines_of_utt):
    global num_utterances, num_utterances_without_segments, total_length_of_utterances

    num_utterances += 1

    segment_ranges = ComputeSegmentCores(split_lines_of_utt)

    utterance_end_time = float(split_lines_of_utt[-1][2]) + float(split_lines_of_utt[-1][3])
    total_length_of_utterances += utterance_end_time

    segments = [ Segment(split_lines_of_utt, x[0], x[1])
                 for x in segment_ranges ]

    AccumulateSegmentStats(segments, 'stage  0 [segment cores]')
    for segment in segments:
        segment.PossiblyAddTaintedLines()
    AccumulateSegmentStats(segments, 'stage  1 [add tainted lines]')
    new_segments = []
    for s in segments:
        new_segments += s.PossiblySplitSegment()
    segments = new_segments
    AccumulateSegmentStats(segments, 'stage  2 [split segments]')
    for s in segments:
        s.PossiblyTruncateBoundaries()
    AccumulateSegmentStats(segments, 'stage  3 [truncate boundaries]')
    for s in segments:
        s.RelaxBoundaryTruncation()
    AccumulateSegmentStats(segments, 'stage  4 [relax boundary truncation]')
    for s in segments:
        s.PossiblyAddUnkPadding()
    AccumulateSegmentStats(segments, 'stage  5 [unk-padding]')

    deleted_segments = []
    new_segments = []
    for s in segments:
        # the 0.999 allows for roundoff error.
        if (not s.IsWholeUtterance() and s.Length() < 0.999 * args.min_new_segment_length):
            s.debug_str += '[deleted-because-of--min-new-segment-length]'
            deleted_segments.append(s)
        else:
            new_segments.append(s)
    segments = new_segments
    AccumulateSegmentStats(segments, 'stage  6 [remove new segments under --min-new-segment-length')

    new_segments = []
    for s in segments:
        # the 0.999 allows for roundoff error.
        if s.Length() < 0.999 * args.min_segment_length:
            s.debug_str += '[deleted-because-of--min-segment-length]'
            deleted_segments.append(s)
        else:
            new_segments.append(s)
    segments = new_segments
    AccumulateSegmentStats(segments, 'stage  7 [remove segments under --min-segment-length')

    for s in segments:
        s.PossiblyTruncateStartForJunkProportion()
    AccumulateSegmentStats(segments, 'stage  8 [truncate segment-starts for --max-junk-proportion')

    for s in segments:
        s.PossiblyTruncateEndForJunkProportion()
    AccumulateSegmentStats(segments, 'stage  9 [truncate segment-ends for --max-junk-proportion')

    new_segments = []
    for s in segments:
        if s.ContainsAtLeastOneScoredNonOovWord():
            new_segments.append(s)
        else:
            s.debug_str += '[deleted-because-no-scored-non-oov-words]'
            deleted_segments.append(s)

    segments = new_segments
    AccumulateSegmentStats(segments, 'stage 10 [remove segments without scored,non-OOV words]')

    new_segments = []
    for s in segments:
        j = s.JunkProportion()
        if j <= args.max_junk_proportion:
            new_segments.append(s)
        else:
            s.debug_str += '[deleted-because-junk-proportion={0}]'.format(j)
            deleted_segments.append(s)

    segments = new_segments
    AccumulateSegmentStats(segments, 'stage 11 [remove segments with junk exceeding --max-junk-proportion]')

    new_segments = []
    if len(segments) > 0:
        new_segments.append(segments[0])
        for i in range(1, len(segments)):
            if new_segments[-1].EndTime() >= segments[i].StartTime():
                new_segments[-1].MergeWithSegment(segments[i])
            else:
                new_segments.append(segments[i])
    segments = new_segments
    AccumulateSegmentStats(segments, 'stage 12 [merge overlapping or touching segments]')

    for i in range(len(segments) - 1):
        if segments[i].EndTime() > segments[i+1].StartTime():
            # this just adds something to --ctm-edits-out output
            segments[i+1].debug_str += ",overlaps-previous-segment"

    if len(segments) == 0:
        num_utterances_without_segments += 1

    return (segments, deleted_segments)

# this prints a number with a certain number of digits after
# the point, while removing trailing zeros.
def FloatToString(f):
    num_digits = 6 # we want to print 6 digits after the zero
    g = f
    while abs(g) > 1.0:
        g *= 0.1
        num_digits += 1
    format_str = '%.{0}g'.format(num_digits)
    return format_str % f

# Gives time in string form as an exact multiple of the frame-length, e.g. 0.01
# (after rounding).
def TimeToString(time, frame_length):
    n = round(time / frame_length)
    assert n >= 0
    # The next function call will remove trailing zeros while printing it, so
    # that e.g. 0.01 will be printed as 0.01 and not 0.0099999999999999.  It
    # seems that doing this in a simple way is not really possible (at least,
    # not without assuming that frame_length is of the form 10^-n, which we
    # don't really want to do).
    return FloatToString(n * frame_length)

def WriteSegmentsForUtterance(text_output_handle, segments_output_handle,
                              old_utterance_name, segments):
    num_digits = len('{}'.format(len(segments)))
    for n in range(len(segments)):
        segment = segments[n]
        # split utterances will be named foo-bar-1 foo-bar-2, etc.
        new_utterance_name = "{old}-{index:0{width}}".format(
                                 old=old_utterance_name, index=n+1,
                                 width=num_digits)
        # print a line to the text output of the form like
        # <new-utterance-id> <text>
        # like:
        # foo-bar-1 hello this is dan
        print(new_utterance_name, segment.Text(), file = text_output_handle)
        # print a line to the segments output of the form
        # <new-utterance-id> <old-utterance-id> <start-time> <end-time>
        # like:
        # foo-bar-1 foo-bar 5.1 7.2
        print(new_utterance_name, old_utterance_name,
              TimeToString(segment.StartTime(), args.frame_length),
              TimeToString(segment.EndTime(), args.frame_length),
              file = segments_output_handle)



# Note, this is destrutive of 'segments_for_utterance', but it won't matter.
def PrintDebugInfoForUtterance(ctm_edits_out_handle,
                               split_lines_of_cur_utterance,
                               segments_for_utterance,
                               deleted_segments_for_utterance):
    # info_to_print will be list of 2-tuples (time, 'start-segment-n'|'end-segment-n')
    # representing the start or end times of segments.
    info_to_print = []
    for n in range(len(segments_for_utterance)):
        segment = segments_for_utterance[n]
        start_string = 'start-segment-{0}[{1}]'.format(n+1, segment.DebugInfo())
        info_to_print.append( (segment.StartTime(), start_string) )
        end_string = 'end-segment-{}'.format(n+1)
        info_to_print.append( (segment.EndTime(), end_string) )
    # for segments that were deleted we print info like start-deleted-segment-1, and
    # otherwise similar info to segments that were retained.
    for n in range(len(deleted_segments_for_utterance)):
        segment = deleted_segments_for_utterance[n]
        start_string = 'start-deleted-segment-{0}[{1}]'.format(n+1, segment.DebugInfo())
        info_to_print.append( (segment.StartTime(), start_string) )
        end_string = 'end-deleted-segment-{}'.format(n+1)
        info_to_print.append( (segment.EndTime(), end_string) )

    info_to_print = sorted(info_to_print)

    for i in range(len(split_lines_of_cur_utterance)):
        split_line=split_lines_of_cur_utterance[i]
        split_line[0] += '[{}]'.format(i)    # add an index like [0], [1], to
                                             # the utterance-id so we can easily
                                             # look up segment indexes.
        start_time = float(split_line[2])
        end_time = start_time + float(split_line[3])
        split_line_copy = list(split_line)
        while len(info_to_print) > 0 and info_to_print[0][0] <= end_time:
            (segment_start, string) = info_to_print[0]
            # shift the first element off of info_to_print.
            info_to_print = info_to_print[1:]
            # add a field like 'start-segment1[...]=3.21' to what we're about to print.
            split_line_copy.append(string + "=" + TimeToString(segment_start, args.frame_length))
        print(' '.join(split_line_copy), file = ctm_edits_out_handle)

# This accumulates word-level stats about, for each reference word, with what
# probability it will end up in the core of a segment.  Words with low
# probabilities of being in segments will generally be associated with some kind
# of error (there is a higher probability of having a wrong lexicon entry).
def AccWordStatsForUtterance(split_lines_of_utt,
                             segments_for_utterance):
    # word_count_pair is a map from a string (the word) to
    # a list [total-count, count-not-within-segments]
    global word_count_pair
    line_is_in_segment = [ False ] * len(split_lines_of_utt)
    for segment in segments_for_utterance:
        for i in range(segment.start_index, segment.end_index):
            line_is_in_segment[i] = True
    for i in range(len(split_lines_of_utt)):
        this_ref_word = split_lines_of_utt[i][6]
        if this_ref_word != '<eps>':
            word_count_pair[this_ref_word][0] += 1
            if not line_is_in_segment[i]:
                word_count_pair[this_ref_word][1] += 1

def PrintWordStats(word_stats_out):
    try:
        f = open(word_stats_out, 'w', encoding='utf-8')
    except:
        sys.exit("segment_ctm_edits.py: error opening word-stats file --word-stats-out={0} "
                 "for writing".format(word_stats_out))
    global word_count_pair
    # Sort from most to least problematic.  We want to give more prominence to
    # words that are most frequently not in segments, but also to high-count
    # words.  Define badness = pair[1] / pair[0], and total_count = pair[0],
    # where 'pair' is a value of word_count_pair.  We'll reverse sort on
    # badness^3 * total_count = pair[1]^3 / pair[0]^2.
    for key, pair in sorted(word_count_pair.items(),
                      key = lambda item: (item[1][1] ** 3) * 1.0 / (item[1][0] ** 2),
                      reverse = True):
        badness = pair[1] * 1.0 / pair[0]
        total_count = pair[0]
        print(key, badness, total_count, file = f)
    try:
        f.close()
    except:
        sys.exit("segment_ctm_edits.py: error closing file --word-stats-out={0} "
                 "(full disk?)".format(word_stats_out))
    print("segment_ctm_edits.py: please see the file {0} for word-level statistics "
          "saying how frequently each word was excluded for a segment; format is "
          "<word> <proportion-of-time-excluded> <total-count>.  Particularly "
          "problematic words appear near the top of the file.".format(word_stats_out),
          file = sys.stderr)


def ProcessData():
    try:
        f_in = open(args.ctm_edits_in, encoding='utf-8')
    except:
        sys.exit("segment_ctm_edits.py: error opening ctm-edits input "
                 "file {0}".format(args.ctm_edits_in))
    try:
        text_output_handle = open(args.text_out, 'w', encoding='utf-8')
    except:
        sys.exit("segment_ctm_edits.py: error opening text output "
                 "file {0}".format(args.text_out))
    try:
        segments_output_handle = open(args.segments_out, 'w', encoding='utf-8')
    except:
        sys.exit("segment_ctm_edits.py: error opening segments output "
                 "file {0}".format(args.text_out))
    if args.ctm_edits_out != None:
        try:
            ctm_edits_output_handle = open(args.ctm_edits_out, 'w', encoding='utf-8')
        except:
            sys.exit("segment_ctm_edits.py: error opening ctm-edits output "
                     "file {0}".format(args.ctm_edits_out))

    # Most of what we're doing in the lines below is splitting the input lines
    # and grouping them per utterance, before giving them to ProcessUtterance()
    # and then printing the modified lines.
    first_line = f_in.readline()
    if first_line == '':
        sys.exit("segment_ctm_edits.py: empty input")
    split_pending_line = first_line.split()
    if len(split_pending_line) == 0:
        sys.exit("segment_ctm_edits.py: bad input line " + first_line)
    cur_utterance = split_pending_line[0]
    split_lines_of_cur_utterance = []

    while True:
        if len(split_pending_line) == 0 or split_pending_line[0] != cur_utterance:
            (segments_for_utterance,
             deleted_segments_for_utterance) = GetSegmentsForUtterance(split_lines_of_cur_utterance)
            AccWordStatsForUtterance(split_lines_of_cur_utterance, segments_for_utterance)
            WriteSegmentsForUtterance(text_output_handle, segments_output_handle,
                                      cur_utterance, segments_for_utterance)
            if args.ctm_edits_out != None:
                PrintDebugInfoForUtterance(ctm_edits_output_handle,
                                           split_lines_of_cur_utterance,
                                           segments_for_utterance,
                                           deleted_segments_for_utterance)
            split_lines_of_cur_utterance = []
            if len(split_pending_line) == 0:
                break
            else:
                cur_utterance = split_pending_line[0]

        split_lines_of_cur_utterance.append(split_pending_line)
        next_line = f_in.readline()
        split_pending_line = next_line.split()
        if len(split_pending_line) == 0:
            if next_line != '':
                sys.exit("segment_ctm_edits.py: got an empty or whitespace input line")
    try:
        text_output_handle.close()
        segments_output_handle.close()
        if args.ctm_edits_out != None:
            ctm_edits_output_handle.close()
    except:
        sys.exit("segment_ctm_edits.py: error closing one or more outputs "
                 "(broken pipe or full disk?)")


def ReadNonScoredWords(non_scored_words_file):
    global non_scored_words
    try:
        f = open(non_scored_words_file, encoding='utf-8')
    except:
        sys.exit("segment_ctm_edits.py: error opening file: "
                 "--non-scored-words=" + non_scored_words_file)
    for line in f.readlines():
        a = line.split()
        if not len(line.split()) == 1:
            sys.exit("segment_ctm_edits.py: bad line in non-scored-words "
                     "file {0}: {1}".format(non_scored_words_file, line))
        non_scored_words.add(a[0])
    f.close()




non_scored_words = set()
ReadNonScoredWords(args.non_scored_words_in)

oov_symbol = None
if args.oov_symbol_file != None:
    try:
        with open(args.oov_symbol_file, encoding='utf-8') as f:
            line = f.readline()
            assert len(line.split()) == 1
            oov_symbol = line.split()[0]
            assert f.readline() == ''
    except Exception as e:
        sys.exit("segment_ctm_edits.py: error reading file --oov-symbol-file=" +
                 args.oov_symbol_file + ", error is: " + str(e))
elif args.unk_padding != 0.0:
    sys.exit("segment_ctm_edits.py: if the --unk-padding option is nonzero (which "
             "it is by default, the --oov-symbol-file option must be supplied.")

# segment_total_length and num_segments are maps from
# 'stage' strings; see AccumulateSegmentStats for details.
segment_total_length = defaultdict(int)
num_segments = defaultdict(int)
# the lambda expression below is an anonymous function that takes no arguments
# and returns the new list [0, 0].
word_count_pair = defaultdict(lambda: [0, 0])
num_utterances = 0
num_utterances_without_segments = 0
total_length_of_utterances = 0


ProcessData()
PrintSegmentStats()
if args.word_stats_out != None:
    PrintWordStats(args.word_stats_out)
if args.ctm_edits_out != None:
    print("segment_ctm_edits.py: detailed utterance-level debug information "
          "is in " + args.ctm_edits_out, file = sys.stderr)