blob: f27582cca196812b389f2b35d8afae2d993e0c81 [file] [log] [blame]
Copybara854996b2021-09-07 19:36:02 +00001# Copyright 2016 The Chromium Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style
3# license that can be found in the LICENSE file or at
4# https://developers.google.com/open-source/licenses/bsd
5
6"""Functions to help rerank issues in a lit.
7
8This file contains methods that implement a reranking algorithm for
9issues in a list.
10"""
11
12from __future__ import division
13from __future__ import print_function
14from __future__ import absolute_import
15
16import sys
17
18from framework import exceptions
19
20MAX_RANKING = sys.maxint
21MIN_RANKING = 0
22
23def GetHotlistRerankChanges(hotlist_items, moved_issue_ids, target_position):
24 # type: (int, Sequence[int], int) -> Collection[Tuple[int, int]]
25 """Computes the new ranks from reranking and or inserting of HotlistItems.
26
27 Args:
28 hotlist_items: The current list of HotlistItems in the Hotlist.
29 moved_issue_ids: A list of issue IDs to be moved/inserted together,
30 in the order
31 they should have the reranking.
32 target_position: The index, starting at 0, of the new position the
33 first issue in moved_issue_ids should occupy in the updated ordering.
34 Therefore this value cannot be greater than
35 (len(hotlist.items) - len(moved_issue_ids)).
36
37 Returns:
38 A list of [(issue_id, rank), ...] of HotlistItems that need to be updated.
39
40 Raises:
41 InputException: If the target_position is not valid.
42 """
43 # Sort hotlist items by rank.
44 sorted_hotlist_items = sorted(hotlist_items, key=lambda item: item.rank)
45 unmoved_hotlist_items = [
46 item for item in sorted_hotlist_items
47 if item.issue_id not in moved_issue_ids]
48 if target_position < 0:
49 raise exceptions.InputException(
50 'given `target_position`: %d, must be non-negative')
51 if target_position > len(unmoved_hotlist_items):
52 raise exceptions.InputException(
53 '`target_position` %d is higher than maximum allowed (%d) for'
54 'moving %d items in a hotlist with %d items total.' % (
55 target_position, len(unmoved_hotlist_items),
56 len(moved_issue_ids), len(sorted_hotlist_items)))
57 lower, higher = [], []
58 for i, item in enumerate(unmoved_hotlist_items):
59 item_tuple = (item.issue_id, item.rank)
60 if i < target_position:
61 lower.append(item_tuple)
62 else:
63 higher.append(item_tuple)
64
65 return GetInsertRankings(lower, higher, moved_issue_ids)
66
67def GetInsertRankings(lower, higher, moved_ids):
68 """Compute rankings for moved_ids to insert between the
69 lower and higher rankings
70
71 Args:
72 lower: a list of [(id, rank),...] of blockers that should have
73 a lower rank than the moved issues. Should be sorted from highest
74 to lowest rank.
75 higher: a list of [(id, rank),...] of blockers that should have
76 a higher rank than the moved issues. Should be sorted from highest
77 to lowest rank.
78 moved_ids: a list of global IDs for issues to re-rank.
79
80 Returns:
81 a list of [(id, rank),...] of blockers that need to be updated. rank
82 is the new rank of the issue with the specified id.
83 """
84 if lower:
85 lower_rank = lower[-1][1]
86 else:
87 lower_rank = MIN_RANKING
88
89 if higher:
90 higher_rank = higher[0][1]
91 else:
92 higher_rank = MAX_RANKING
93
94 slot_count = higher_rank - lower_rank - 1
95 if slot_count >= len(moved_ids):
96 new_ranks = _DistributeRanks(lower_rank, higher_rank, len(moved_ids))
97 return list(zip(moved_ids, new_ranks))
98 else:
99 new_lower, new_higher, new_moved_ids = _ResplitRanks(
100 lower, higher, moved_ids)
101 if not new_moved_ids:
102 return None
103 else:
104 return GetInsertRankings(new_lower, new_higher, new_moved_ids)
105
106
107def _DistributeRanks(low, high, rank_count):
108 """Compute evenly distributed ranks in a range"""
109 bucket_size = (high - low) // rank_count
110 first_rank = low + (bucket_size + 1) // 2
111 return list(range(first_rank, high, bucket_size))
112
113
114def _ResplitRanks(lower, higher, moved_ids):
115 if not (lower or higher):
116 return None, None, None
117
118 if not lower:
119 take_from = 'higher'
120 elif not higher:
121 take_from = 'lower'
122 else:
123 next_lower = lower[-2][1] if len(lower) >= 2 else MIN_RANKING
124 next_higher = higher[1][1] if len(higher) >= 2 else MAX_RANKING
125 if (lower[-1][1] - next_lower) > (next_higher - higher[0][1]):
126 take_from = 'lower'
127 else:
128 take_from = 'higher'
129
130 if take_from == 'lower':
131 return (lower[:-1], higher, [lower[-1][0]] + moved_ids)
132 else:
133 return (lower, higher[1:], moved_ids + [higher[0][0]])