Project import generated by Copybara.
GitOrigin-RevId: d9e9e3fb4e31372ec1fb43b178994ca78fa8fe70
diff --git a/tracker/rerank_helpers.py b/tracker/rerank_helpers.py
new file mode 100644
index 0000000..f27582c
--- /dev/null
+++ b/tracker/rerank_helpers.py
@@ -0,0 +1,133 @@
+# 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]])