[go: nahoru, domu]
Google Git
Sign in
android / platform / frameworks / support / 205da9b3b7868614d701d29f57dade9facf8b5cd / . / ui / ui-core / src / commonMain / kotlin / androidx / ui / core / DepthSortedSet.kt
blob: 05871dd30c7d71049e17abd20d789d168a606c4a [file] [log] [blame]
Andrey Kulikov8f43a952020-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
17package androidx.ui.core
18
Nikolay Igotti9ea0c1f2020-06-30 12:27:21 +0300[diff] [blame]19import androidx.ui.util.identityHashCode
20import androidx.ui.util.TreeSet
Andrey Kulikov8f43a952020-02-12 16:01:29 +0000[diff] [blame]21
22/**
George Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]23 * The set of [LayoutNode]s which orders items by their [LayoutNode.depth] and
Andrey Kulikov8f43a952020-02-12 16:01:29 +0000[diff] [blame]24 * allows modifications(additions and removals) while we iterate through it via [popEach].
George Mount17d6fe52020-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 Kulikov8f43a952020-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 Mount5469e252020-06-17 10:01:42 -0700[diff] [blame]31@OptIn(ExperimentalLayoutNodeApi::class)
George Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]32internal class DepthSortedSet(
Andrey Kulikov8f43a952020-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 Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]40 mutableMapOf<LayoutNode, Int>()
Andrey Kulikov8f43a952020-02-12 16:01:29 +0000[diff] [blame]41 }
George Mount17d6fe52020-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 Kulikov8f43a952020-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 Igotti9ea0c1f2020-06-30 12:27:21 +0300[diff] [blame]48 return l1.identityHashCode().compareTo(l2.identityHashCode())
Andrey Kulikov8f43a952020-02-12 16:01:29 +0000[diff] [blame]49 }
50 }
George Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]51 private val set = TreeSet<LayoutNode>(DepthComparator)
Andrey Kulikov8f43a952020-02-12 16:01:29 +0000[diff] [blame]52
George Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]53 fun contains(node: LayoutNode): Boolean {
Andrey Kulikov8f43a952020-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 Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]61 fun add(node: LayoutNode) {
Andrey Kulikov8f43a952020-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 Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]74 fun remove(node: LayoutNode) {
Andrey Kulikov8f43a952020-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 Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]87 fun pop(): LayoutNode {
Andrey Kulikov8f43a952020-02-12 16:01:29 +0000[diff] [blame]88 val node = set.first()
89 remove(node)
90 return node
91 }
92
George Mount17d6fe52020-05-15 08:08:23 -0700[diff] [blame]93 inline fun popEach(crossinline block: (LayoutNode) -> Unit) {
Andrey Kulikov8f43a952020-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}