1 /* <lambda>null2 * Copyright (C) 2024 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.settingslib.metadata 18 19 import java.util.function.Consumer 20 21 /** 22 * A compact and immutable data structure provides [get] and for-each operations on ordered 23 * key-value entries. 24 * 25 * The implementation uses fixed-size array and no API is offered to modify entries. Actually, 26 * elements are provided in sorted order during constructor to simplify data management. As a 27 * result, this class is more lightweight compared with `ArrayMap`. 28 */ 29 @Suppress("UNCHECKED_CAST") 30 class FixedArrayMap<K : Comparable<K>, V> { 31 private val array: Array<Any?> 32 33 /** Constructors with empty element. */ 34 constructor() { 35 array = emptyArray() 36 } 37 38 /** 39 * Constructors. 40 * 41 * @param size the number of elements 42 * @param consumer initializer to provide exactly [size] elements *in sorted order* 43 */ 44 constructor(size: Int, consumer: Consumer<OrderedInitializer<K, V>>) { 45 array = arrayOfNulls(size * 2) 46 val orderedInitializer = OrderedInitializer<K, V>(array) 47 consumer.accept(orderedInitializer) 48 orderedInitializer.verify() 49 } 50 51 /** Returns the number of elements. */ 52 val size: Int 53 get() = array.size / 2 54 55 /** 56 * Returns a new [FixedArrayMap] that merged from current and given [FixedArrayMap] instance. 57 * 58 * [other] takes precedence for identical keys. 59 */ 60 fun merge(other: FixedArrayMap<K, V>): FixedArrayMap<K, V> { 61 var newKeys = 0 62 other.forEachKey { if (get(it) == null) newKeys++ } 63 return FixedArrayMap(size + newKeys) { initializer -> 64 var index1 = 0 65 var index2 = 0 66 while (!initializer.isDone()) { 67 val key1 = if (index1 < array.size) array[index1] as K else null 68 val key2 = if (index2 < other.array.size) other.array[index2] as K else null 69 val diff = 70 when { 71 key1 == null -> 1 72 key2 == null -> -1 73 else -> key1.compareTo(key2) 74 } 75 if (diff < 0) { 76 initializer.put(key1!!, array[index1 + 1] as V) 77 index1 += 2 78 } else { 79 initializer.put(key2!!, other.array[index2 + 1] as V) 80 index2 += 2 81 if (diff == 0) index1 += 2 82 } 83 } 84 } 85 } 86 87 /** Traversals keys *in sorted order* and applies given action. */ 88 fun forEachKey(action: (key: K) -> Unit) { 89 for (index in array.indices step 2) { 90 action(array[index] as K) 91 } 92 } 93 94 /** Traversals keys *in sorted order* and applies given action. */ 95 suspend fun forEachKeyAsync(action: suspend (key: K) -> Unit) { 96 for (index in array.indices step 2) { 97 action(array[index] as K) 98 } 99 } 100 101 /** Traversals key-value entries *in sorted order* and applies given action. */ 102 fun forEach(action: (key: K, value: V) -> Unit) { 103 for (index in array.indices step 2) { 104 action(array[index] as K, array[index + 1] as V) 105 } 106 } 107 108 /** Traversals key-value entries in sorted order and applies given action. */ 109 suspend fun forEachAsync(action: suspend (key: K, value: V) -> Unit) { 110 for (index in array.indices step 2) { 111 action(array[index] as K, array[index + 1] as V) 112 } 113 } 114 115 /** 116 * Returns the value associated with given key. 117 * 118 * Binary-search algorithm is applied, so this operation takes O(log2(N)) at worst case. 119 */ 120 operator fun get(key: K): V? { 121 var low = 0 122 var high = array.size / 2 123 while (low < high) { 124 val mid = (low + high).ushr(1) // safe from overflows 125 val diff = (array[mid * 2] as K).compareTo(key) 126 when { 127 diff < 0 -> low = mid + 1 128 diff > 0 -> high = mid 129 else -> return array[mid * 2 + 1] as V 130 } 131 } 132 return null 133 } 134 135 /** Initializer to provide key-value pairs *in sorted order*. */ 136 class OrderedInitializer<K : Comparable<K>, V> 137 internal constructor(private val array: Array<Any?>) { 138 private var index = 0 139 140 internal val size: Int 141 get() = array.size 142 143 /** Returns whether all elements are added. */ 144 fun isDone() = index == array.size 145 146 /** Adds a new key-value entry. The key must be provided in sorted order. */ 147 fun put(key: K, value: V) { 148 array[index++] = key 149 array[index++] = value 150 } 151 152 internal fun verify() { 153 if (!isDone()) throw IllegalStateException("Missing items: ${index / 2} / ${size / 2}") 154 for (index in 2 until size step 2) { 155 if ((array[index - 2] as K) >= (array[index] as K)) { 156 throw IllegalStateException("${array[index - 2]} >= ${array[index]}") 157 } 158 } 159 } 160 } 161 } 162