tracker/rerank_helpers.py

# Copyright 2016 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style
# license that can be found in the LICENSE file or at
# https://developers.google.com/open-source/licenses/bsd

"""Functions to help rerank issues in a lit.

This file contains methods that implement a reranking algorithm for
issues in a list.
"""

from __future__ import division
from __future__ import print_function
from __future__ import absolute_import

import sys

from framework import exceptions

MAX_RANKING = sys.maxint
MIN_RANKING = 0

def GetHotlistRerankChanges(hotlist_items, moved_issue_ids, target_position):
  # type: (int, Sequence[int], int) -> Collection[Tuple[int, int]]
  """Computes the new ranks from reranking and or inserting of HotlistItems.

  Args:
    hotlist_items: The current list of HotlistItems in the Hotlist.
    moved_issue_ids: A list of issue IDs to be moved/inserted together,
      in the order
      they should have the reranking.
    target_position: The index, starting at 0, of the new position the
      first issue in moved_issue_ids should occupy in the updated ordering.
      Therefore this value cannot be greater than
      (len(hotlist.items) - len(moved_issue_ids)).

  Returns:
    A list of [(issue_id, rank), ...] of HotlistItems that need to be updated.

  Raises:
    InputException: If the target_position is not valid.
  """
  # Sort hotlist items by rank.
  sorted_hotlist_items = sorted(hotlist_items, key=lambda item: item.rank)
  unmoved_hotlist_items = [
      item for item in sorted_hotlist_items
      if item.issue_id not in moved_issue_ids]
  if target_position < 0:
    raise exceptions.InputException(
        'given `target_position`: %d, must be non-negative')
  if target_position > len(unmoved_hotlist_items):
    raise exceptions.InputException(
        '`target_position` %d is higher than maximum allowed (%d) for'
        'moving %d items in a hotlist with %d items total.' % (
            target_position, len(unmoved_hotlist_items),
            len(moved_issue_ids), len(sorted_hotlist_items)))
  lower, higher = [], []
  for i, item in enumerate(unmoved_hotlist_items):
    item_tuple = (item.issue_id, item.rank)
    if i < target_position:
      lower.append(item_tuple)
    else:
      higher.append(item_tuple)

  return GetInsertRankings(lower, higher, moved_issue_ids)

def GetInsertRankings(lower, higher, moved_ids):
  """Compute rankings for moved_ids to insert between the
  lower and higher rankings

  Args:
    lower: a list of [(id, rank),...] of blockers that should have
      a lower rank than the moved issues. Should be sorted from highest
      to lowest rank.
    higher: a list of [(id, rank),...] of blockers that should have
      a higher rank than the moved issues. Should be sorted from highest
      to lowest rank.
    moved_ids: a list of global IDs for issues to re-rank.

  Returns:
    a list of [(id, rank),...] of blockers that need to be updated. rank
    is the new rank of the issue with the specified id.
  """
  if lower:
    lower_rank = lower[-1][1]
  else:
    lower_rank = MIN_RANKING

  if higher:
    higher_rank = higher[0][1]
  else:
    higher_rank = MAX_RANKING

  slot_count = higher_rank - lower_rank - 1
  if slot_count >= len(moved_ids):
    new_ranks = _DistributeRanks(lower_rank, higher_rank, len(moved_ids))
    return list(zip(moved_ids, new_ranks))
  else:
    new_lower, new_higher, new_moved_ids = _ResplitRanks(
        lower, higher, moved_ids)
    if not new_moved_ids:
      return None
    else:
      return GetInsertRankings(new_lower, new_higher, new_moved_ids)


def _DistributeRanks(low, high, rank_count):
  """Compute evenly distributed ranks in a range"""
  bucket_size = (high - low) // rank_count
  first_rank = low + (bucket_size + 1) // 2
  return list(range(first_rank, high, bucket_size))


def _ResplitRanks(lower, higher, moved_ids):
  if not (lower or higher):
    return None, None, None

  if not lower:
    take_from = 'higher'
  elif not higher:
    take_from = 'lower'
  else:
    next_lower = lower[-2][1] if len(lower) >= 2 else MIN_RANKING
    next_higher = higher[1][1] if len(higher) >= 2 else MAX_RANKING
    if (lower[-1][1] - next_lower) > (next_higher - higher[0][1]):
      take_from = 'lower'
    else:
      take_from = 'higher'

  if take_from == 'lower':
    return (lower[:-1], higher, [lower[-1][0]] + moved_ids)
  else:
    return (lower, higher[1:], moved_ids + [higher[0][0]])