code: def _concordance_summary_statistics(
      event_times, predicted_event_times, event_observed
  ):  # pylint: disable=too-many-locals
      """Find the concordance index in n * log(n) time.
  
      Assumes the data has been verified by lifelines.utils.concordance_index first.
      """
      # Here's how this works.
      #
      # It would be pretty easy to do if we had no censored data and no ties. There, the basic idea
      # would be to iterate over the cases in order of their true event time (from least to greatest),
      # while keeping track of a pool of *predicted* event times for all cases previously seen (= all
      # cases that we know should be ranked lower than the case we're looking at currently).
      #
      # If the pool has O(log n) insert and O(log n) RANK (i.e., "how many things in the pool have
      # value less than x"), then the following algorithm is n log n:
      #
      # Sort the times and predictions by time, increasing
      # n_pairs, n_correct := 0
      # pool := {}
      # for each prediction p:
      #     n_pairs += len(pool)
      #     n_correct += rank(pool, p)
      #     add p to pool
      #
      # There are three complications: tied ground truth values, tied predictions, and censored
      # observations.
      #
      # - To handle tied true event times, we modify the inner loop to work in *batches* of observations
      # p_1, ..., p_n whose true event times are tied, and then add them all to the pool
      # simultaneously at the end.
      #
      # - To handle tied predictions, which should each count for 0.5, we switch to
      #     n_correct += min_rank(pool, p)
      #     n_tied += count(pool, p)
      #
      # - To handle censored observations, we handle each batch of tied, censored observations just
      # after the batch of observations that died at the same time (since those censored observations
      # are comparable all the observations that died at the same time or previously). However, we do
      # NOT add them to the pool at the end, because they are NOT comparable with any observations
      # that leave the study afterward--whether or not those observations get censored.
      if np.logical_not(event_observed).all():
          return (0, 0, 0)
  
      died_mask = event_observed.astype(bool)
      # TODO: is event_times already sorted? That would be nice...
      died_truth = event_times[died_mask]
      ix = np.argsort(died_truth)
      died_truth = died_truth[ix]
      died_pred = predicted_event_times[died_mask][ix]
  
      censored_truth = event_times[~died_mask]
      ix = np.argsort(censored_truth)
      censored_truth = censored_truth[ix]
      censored_pred = predicted_event_times[~died_mask][ix]
  
      censored_ix = 0
      died_ix = 0
      times_to_compare = _BTree(np.unique(died_pred))
      num_pairs = np.int64(0)
      num_correct = np.int64(0)
      num_tied = np.int64(0)
  
      # we iterate through cases sorted by exit time:
      # - First, all cases that died at time t0. We add these to the sortedlist of died times.
      # - Then, all cases that were censored at time t0. We DON'T add these since they are NOT
      #   comparable to subsequent elements.
      while True:
          has_more_censored = censored_ix < len(censored_truth)
          has_more_died = died_ix < len(died_truth)
          # Should we look at some censored indices next, or died indices?
          if has_more_censored and (
              not has_more_died
              or died_truth[died_ix] > censored_truth[censored_ix]
          ):
              pairs, correct, tied, next_ix = _handle_pairs(
                  censored_truth,
                  censored_pred,
                  censored_ix,
                  times_to_compare,
              )
              censored_ix = next_ix
          elif has_more_died and (
              not has_more_censored
              or died_truth[died_ix] <= censored_truth[censored_ix]
          ):
              pairs, correct, tied, next_ix = _handle_pairs(
                  died_truth, died_pred, died_ix, times_to_compare
              )
              for pred in died_pred[died_ix:next_ix]:
                  times_to_compare.insert(pred)
              died_ix = next_ix
          else:
              assert not (has_more_died or has_more_censored)
              break
  
          num_pairs += pairs
          num_correct += correct
          num_tied += tied
  
      return (num_correct, num_tied, num_pairs)
  
file_path: lifelines/lifelines/utils/concordance.py
imports: import numpy
  from lifelines.utils.btree import _BTree
label_desc: Use image node_id 4 for calling a global function with example usage: _concordance_summary_statistics(event_times, predicted_event_times, event_observed) and returns: num_correct,  num_tied,  num_pairs, int,  int,  int