Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2020 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 androidx.ui.core |
| 18 | |
Nikolay Igotti | 9ea0c1f | 2020-06-30 12:27:21 +0300 | [diff] [blame] | 19 | import androidx.ui.util.identityHashCode |
| 20 | import androidx.ui.util.TreeSet |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 21 | |
| 22 | /** |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 23 | * The set of [LayoutNode]s which orders items by their [LayoutNode.depth] and |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 24 | * allows modifications(additions and removals) while we iterate through it via [popEach]. |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 25 | * While [LayoutNode] is added to the set it should always be: |
| 26 | * 1) attached [LayoutNode.isAttached] == true |
| 27 | * 2) maintaining the same [LayoutNode.depth] |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 28 | * as any of this modifications can break the comparator's contract which can cause |
| 29 | * to not find the item in the tree set, which we previously added. |
| 30 | */ |
George Mount | 5469e25 | 2020-06-17 10:01:42 -0700 | [diff] [blame] | 31 | @OptIn(ExperimentalLayoutNodeApi::class) |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 32 | internal class DepthSortedSet( |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 33 | private val extraAssertions: Boolean = true |
| 34 | ) { |
| 35 | // stores the depth used when the node was added into the set so we can assert it wasn't |
| 36 | // changed since then. we need to enforce this as changing the depth can break the contract |
| 37 | // used in comparator for building the tree in TreeSet. |
| 38 | // Created and used only when extraAssertions == true |
| 39 | private val mapOfOriginalDepth by lazy(LazyThreadSafetyMode.NONE) { |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 40 | mutableMapOf<LayoutNode, Int>() |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 41 | } |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 42 | private val DepthComparator: Comparator<LayoutNode> = object : Comparator<LayoutNode> { |
| 43 | override fun compare(l1: LayoutNode, l2: LayoutNode): Int { |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 44 | val depthDiff = l1.depth.compareTo(l2.depth) |
| 45 | if (depthDiff != 0) { |
| 46 | return depthDiff |
| 47 | } |
Nikolay Igotti | 9ea0c1f | 2020-06-30 12:27:21 +0300 | [diff] [blame] | 48 | return l1.identityHashCode().compareTo(l2.identityHashCode()) |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 49 | } |
| 50 | } |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 51 | private val set = TreeSet<LayoutNode>(DepthComparator) |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 52 | |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 53 | fun contains(node: LayoutNode): Boolean { |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 54 | val contains = set.contains(node) |
| 55 | if (extraAssertions) { |
| 56 | check(contains == mapOfOriginalDepth.containsKey(node)) |
| 57 | } |
| 58 | return contains |
| 59 | } |
| 60 | |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 61 | fun add(node: LayoutNode) { |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 62 | check(node.isAttached()) |
| 63 | if (extraAssertions) { |
| 64 | val usedDepth = mapOfOriginalDepth[node] |
| 65 | if (usedDepth == null) { |
| 66 | mapOfOriginalDepth[node] = node.depth |
| 67 | } else { |
| 68 | check(usedDepth == node.depth) |
| 69 | } |
| 70 | } |
| 71 | set.add(node) |
| 72 | } |
| 73 | |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 74 | fun remove(node: LayoutNode) { |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 75 | check(node.isAttached()) |
| 76 | val contains = set.remove(node) |
| 77 | if (extraAssertions) { |
| 78 | val usedDepth = mapOfOriginalDepth.remove(node) |
| 79 | if (contains) { |
| 80 | check(usedDepth == node.depth) |
| 81 | } else { |
| 82 | check(usedDepth == null) |
| 83 | } |
| 84 | } |
| 85 | } |
| 86 | |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 87 | fun pop(): LayoutNode { |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 88 | val node = set.first() |
| 89 | remove(node) |
| 90 | return node |
| 91 | } |
| 92 | |
George Mount | 17d6fe5 | 2020-05-15 08:08:23 -0700 | [diff] [blame] | 93 | inline fun popEach(crossinline block: (LayoutNode) -> Unit) { |
Andrey Kulikov | 8f43a95 | 2020-02-12 16:01:29 +0000 | [diff] [blame] | 94 | while (isNotEmpty()) { |
| 95 | val node = pop() |
| 96 | block(node) |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | fun isEmpty(): Boolean = set.isEmpty() |
| 101 | |
| 102 | @Suppress("NOTHING_TO_INLINE") |
| 103 | inline fun isNotEmpty(): Boolean = !isEmpty() |
| 104 | |
| 105 | override fun toString(): String { |
| 106 | return set.toString() |
| 107 | } |
| 108 | } |