1 /* 2 * 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.compose.ui.util 18 19 /** 20 * This is a custom implementation that resembles a SortedMap<Int, T> but is based on a simple 21 * ArrayList to avoid the allocation overhead and boxing. 22 * 23 * It can only hold positive keys and 0 and it is only efficient for small keys (0 - ~100), but 24 * therefore provides fast operations for small keys. 25 */ 26 internal class IntIndexedMap<T> { 27 private val arrayList = ArrayList<T?>() 28 private var _size = 0 29 val size 30 get() = _size 31 32 /** Returns the value at [key] or null if the key is not present. */ getnull33 operator fun get(key: Int): T? { 34 if (key < 0 || key >= arrayList.size) return null 35 return arrayList[key] 36 } 37 38 /** 39 * Sets the value at [key] to [value]. If [key] is larger than the current size of the map, this 40 * operation may take up to O(key) time and space. Therefore this data structure is only 41 * efficient for small [key] sizes. 42 */ setnull43 operator fun set(key: Int, value: T?) { 44 if (key < 0) 45 throw UnsupportedOperationException("This map can only hold positive keys and 0.") 46 if (key < arrayList.size) { 47 if (arrayList[key] != null && value == null) _size-- 48 if (arrayList[key] == null && value != null) _size++ 49 arrayList[key] = value 50 } else { 51 if (value == null) return 52 while (key > arrayList.size) { 53 arrayList.add(null) 54 } 55 _size++ 56 arrayList.add(value) 57 } 58 } 59 60 /** Remove value at [key] */ removenull61 fun remove(key: Int) { 62 if (key >= arrayList.size) return 63 this[key] = null 64 } 65 66 /** Get the [value] with the smallest [key] of the map. */ firstnull67 fun first(): T { 68 for (i in 0 until arrayList.size) { 69 return arrayList[i] ?: continue 70 } 71 throw NoSuchElementException("The map is empty.") 72 } 73 } 74