blob: cc23521a4cb295548bd6dd898735195560df9d96 [file] [log] [blame]
# Copyright 2016 The Chromium Authors
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""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.maxsize
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]])