1 /*
<lambda>null2  * Copyright (C) 2022 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.systemui.statusbar.notification.collection.listbuilder
18 
19 import androidx.annotation.VisibleForTesting
20 import kotlin.math.sign
21 
22 class SemiStableSort {
23     val preallocatedWorkspace by lazy { ArrayList<Any>() }
24     val preallocatedAdditions by lazy { ArrayList<Any>() }
25     val preallocatedMapToIndex by lazy { HashMap<Any, Int>() }
26     val preallocatedMapToIndexComparator: Comparator<Any> by lazy {
27         Comparator.comparingInt { item -> preallocatedMapToIndex[item] ?: -1 }
28     }
29 
30     /**
31      * Sort the given [items] such that items which have a [stableOrder] will all be in that order,
32      * items without a [stableOrder] will be sorted according to the comparator, and the two sets of
33      * items will be combined to have the fewest elements out of order according to the [comparator]
34      * . The result will be placed into the original [items] list.
35      */
36     fun <T : Any> sort(
37         items: MutableList<T>,
38         stableOrder: StableOrder<in T>,
39         comparator: Comparator<in T>,
40     ): Boolean =
41         withWorkspace<T, Boolean> { workspace ->
42             val ordered =
43                 sortTo(
44                     items,
45                     stableOrder,
46                     comparator,
47                     workspace,
48                 )
49             items.clear()
50             items.addAll(workspace)
51             return ordered
52         }
53 
54     /**
55      * Sort the given [items] such that items which have a [stableOrder] will all be in that order,
56      * items without a [stableOrder] will be sorted according to the comparator, and the two sets of
57      * items will be combined to have the fewest elements out of order according to the [comparator]
58      * . The result will be put into [output].
59      */
60     fun <T : Any> sortTo(
61         items: Iterable<T>,
62         stableOrder: StableOrder<in T>,
63         comparator: Comparator<in T>,
64         output: MutableList<T>,
65     ): Boolean {
66         if (DEBUG) println("\n> START from ${items.map { it to stableOrder.getRank(it) }}")
67         // If array already has elements, use subList to ensure we only append
68         val result = output.takeIf { it.isEmpty() } ?: output.subList(output.size, output.size)
69         items.filterTo(result) { stableOrder.getRank(it) != null }
70         result.sortBy { stableOrder.getRank(it)!! }
71         val isOrdered = result.isSorted(comparator)
72         withAdditions<T> { additions ->
73             items.filterTo(additions) { stableOrder.getRank(it) == null }
74             additions.sortWith(comparator)
75             insertPreSortedElementsWithFewestMisOrderings(result, additions, comparator)
76         }
77         return isOrdered
78     }
79 
80     /**
81      * Rearrange the [sortedItems] to enforce that items are in the [stableOrder], and store the
82      * result in [output]. Items with a [stableOrder] will be in that order, items without a
83      * [stableOrder] will remain in same relative order as the input, and the two sets of items will
84      * be combined to have the fewest elements moved from their locations in the original.
85      */
86     fun <T : Any> stabilizeTo(
87         sortedItems: Iterable<T>,
88         stableOrder: StableOrder<in T>,
89         output: MutableList<T>,
90     ): Boolean {
91         // Append to the output array if present
92         val result = output.takeIf { it.isEmpty() } ?: output.subList(output.size, output.size)
93         sortedItems.filterTo(result) { stableOrder.getRank(it) != null }
94         val stableRankComparator = compareBy<T> { stableOrder.getRank(it)!! }
95         val isOrdered = result.isSorted(stableRankComparator)
96         if (!isOrdered) {
97             result.sortWith(stableRankComparator)
98         }
99         if (result.isEmpty()) {
100             sortedItems.filterTo(result) { stableOrder.getRank(it) == null }
101             return isOrdered
102         }
103         withAdditions<T> { additions ->
104             sortedItems.filterTo(additions) { stableOrder.getRank(it) == null }
105             if (additions.isNotEmpty()) {
106                 withIndexOfComparator(sortedItems) { comparator ->
107                     insertPreSortedElementsWithFewestMisOrderings(result, additions, comparator)
108                 }
109             }
110         }
111         return isOrdered
112     }
113 
114     private inline fun <T : Any, R> withWorkspace(block: (ArrayList<T>) -> R): R {
115         preallocatedWorkspace.clear()
116         val result = block(preallocatedWorkspace as ArrayList<T>)
117         preallocatedWorkspace.clear()
118         return result
119     }
120 
121     private inline fun <T : Any> withAdditions(block: (ArrayList<T>) -> Unit) {
122         preallocatedAdditions.clear()
123         block(preallocatedAdditions as ArrayList<T>)
124         preallocatedAdditions.clear()
125     }
126 
127     private inline fun <T : Any> withIndexOfComparator(
128         sortedItems: Iterable<T>,
129         block: (Comparator<in T>) -> Unit
130     ) {
131         preallocatedMapToIndex.clear()
132         sortedItems.forEachIndexed { i, item -> preallocatedMapToIndex[item] = i }
133         block(preallocatedMapToIndexComparator as Comparator<in T>)
134         preallocatedMapToIndex.clear()
135     }
136 
137     companion object {
138 
139         /**
140          * This is the core of the algorithm.
141          *
142          * Insert [preSortedAdditions] (the elements to be inserted) into [existing] without
143          * changing the relative order of any elements already in [existing], even though those
144          * elements may be mis-ordered relative to the [comparator], such that the total number of
145          * elements which are ordered incorrectly according to the [comparator] is fewest.
146          */
147         private fun <T> insertPreSortedElementsWithFewestMisOrderings(
148             existing: MutableList<T>,
149             preSortedAdditions: Iterable<T>,
150             comparator: Comparator<in T>,
151         ) {
152             if (DEBUG) println("  To $existing insert $preSortedAdditions with fewest misordering")
153             var iStart = 0
154             preSortedAdditions.forEach { toAdd ->
155                 if (DEBUG) println("    need to add $toAdd to $existing, starting at $iStart")
156                 var cmpSum = 0
157                 var cmpSumMax = 0
158                 var iCmpSumMax = iStart
159                 if (DEBUG) print("      ")
160                 for (i in iCmpSumMax until existing.size) {
161                     val cmp = comparator.compare(toAdd, existing[i]).sign
162                     cmpSum += cmp
163                     if (cmpSum > cmpSumMax) {
164                         cmpSumMax = cmpSum
165                         iCmpSumMax = i + 1
166                     }
167                     if (DEBUG) print("sum[$i]=$cmpSum, ")
168                 }
169                 if (DEBUG) println("inserting $toAdd at $iCmpSumMax")
170                 existing.add(iCmpSumMax, toAdd)
171                 iStart = iCmpSumMax + 1
172             }
173         }
174 
175         /** Determines if a list is correctly sorted according to the given comparator */
176         @VisibleForTesting
177         fun <T> List<T>.isSorted(comparator: Comparator<T>): Boolean {
178             if (this.size <= 1) {
179                 return true
180             }
181             val iterator = this.iterator()
182             var previous = iterator.next()
183             var current: T?
184             while (iterator.hasNext()) {
185                 current = iterator.next()
186                 if (comparator.compare(previous, current) > 0) {
187                     return false
188                 }
189                 previous = current
190             }
191             return true
192         }
193     }
194 
195     fun interface StableOrder<T> {
196         fun getRank(item: T): Int?
197     }
198 }
199 
200 val DEBUG = false
201