我如何比较多个时间范围并在 Android Compose 中并排显示它们

要 for each 通用的边缘情况正确地堆叠事件将需要一个复杂的实现，所以这里有一个更简单的实现，它对于没有太多重叠事件的情况足够好地工作.这个简单的实现并不均匀地分配宽度，而只是让最后一个元素在某些边缘中获得一些额外的宽度--在这种情况下，宽度重新分布是可能的.

首先，我创建了一个用于遍历类似图的数据 struct 的帮助器函数，因为下面的代码多次以各种方式使用它.它返回一个Sequence，可以执行广度优先或深度优先的 子图/子树，并按照 node 被访问的顺序生成 node .在实现中，我只使用呼吸优先遍历，但我也在遍历函数中保留了深度优先模式.

/**
 * Traverses the graph-like data structure starting from the receiver.
 * 
 * @param depthFirst if true, the traversal is depth-first, otherwise breadth-first
 * @param nextIterator a function that returns an iterator over the next nodes to visit
 * @return a sequence of nodes in the order they are visited
 */
fun <T> T.traverse(depthFirst: Boolean = false, nextIterator: (T) -> Iterator<T>): Sequence<T> {
    return sequence {
        val current = this@traverse
        if (!depthFirst) yield(current)

        val iterator = nextIterator(current)
        while (iterator.hasNext()) {
            yieldAll(iterator.next().traverse(depthFirst, nextIterator))
        }

        if (depthFirst) yield(current)
    }
}

对于数据 struct ，我使用了一个Node类，它可以容纳一个元素，知道它自己在图中的深度，知道它所属的图的总深度，并且可以容纳对上一个和下一个 node 的引用.

class Node(
        val element: T,
        val currentDepth: Int,
        var totalDepth: Int = currentDepth + 1,
        val prev: MutableList<Node> = mutableListOf(),
        val next: MutableList<Node> = mutableListOf(),
    ) {
        var nextDepth: Node? = null
        var visualDebug = ""
    }

我还在代码中保留了您可以在上面的代码中看到的visualDebug字段.此调试信息显示哪些元素(事件)受算法的不同部分影响.现在，代码只是根据下面描述的情况将visualDebug设置为数字1-4，标记为(1.)-(4.)，但如果您想了解算法是如何工作的，您可以在算法代码内的各个步骤将您自己的调试信息添加到此字段中.您可以简单地通过更改演示代码中的值showVisualDebug来启用或禁用这些额外的调试信息，该值在本文末尾和this UI should show up处可用.

// set to true to see some debug info directly on each event
const val showVisualDebug = true

我实现的简化算法如下:

• 使用比较器对元素进行排序，这进一步简化了已经简化的方法

val sortedElements = elements.sortedWith(comparator)

• 创建一个空列表以保存每个图表最顶部(最左侧)的非重叠结点

val nonOverlappingNodes = mutableListOf<Node>()

• 遍历已排序的元素并将它们添加到类似图的数据 struct 中.从查找到目前为止创建的最后一个图中的第一个重叠 node 开始.

sortedElements.forEach { elementToInsert ->
    val currentOverlappingWith = { node: Node -> areOverlapping(node.element, elementToInsert) }

    val last = nonOverlappingNodes.lastOrNull()

    val firstOverlap = last
        ?.traverse { it.next.iterator() }
        ?.firstOrNull(currentOverlappingWith)
    
    // ...
}

• 如果元素:
  • (1.)未与图形中的任何 node 重叠，请通过使用深度为0的此元素创建新 node 来开始新图形

if (firstOverlap == null) {
    // inserting a new non-overlapping node
    val node = Node(elementToInsert, currentDepth = 0)
    node.visualDebug = "1"
    nonOverlappingNodes.add(node)
}

• (2.)与不在深度0处的结点重叠，在深度0处创建新结点并将其连接到重叠结点

if (firstOverlap == null) { /* ... */ }
else if (firstOverlap.currentDepth > 0) {
    val node = Node(elementToInsert, currentDepth = 0, totalDepth = firstOverlap.totalDepth)
    node.visualDebug = "2"

    firstOverlap.prev.add(node)
    node.next.add(firstOverlap)
    node.nextDepth = firstOverlap

    // inserting a new top node at depth 0 that has an overlap deeper down the hierarchy
    nonOverlappingNodes.add(node)
}

• (3.)与深度为0的 node 重叠，找到此图中的第一个空间隙并在间隙深度创建新 node ，然后找到下一个重叠 node (如果存在)，并将两者连接(4.).

if (firstOverlap == null) { /* ... */ }
else if (firstOverlap.currentDepth > 0) { /* ... */ }
else {
    // insert an overlapping node at a deeper depth into the first overlap-free gap
    val overlap = last
        .traverse { it.next.iterator() }
        .fold(null as Node?) { lastOverlap, next ->
            val adjacent = lastOverlap == null || lastOverlap.currentDepth + 1 == next.currentDepth
            if (adjacent && currentOverlappingWith(next)) next else lastOverlap
        }!!

    // create the new node at the depth of the insertion
    val node = Node(elementToInsert, currentDepth = overlap.currentDepth + 1)
    node.totalDepth = overlap.totalDepth.coerceAtLeast(node.totalDepth)
    node.visualDebug = "3"

    // check if there is an overlap deeper down the hierarchy
    val nextOverlap = overlap
        .traverse { it.next.iterator() }
        .firstOrNull { it !== overlap && currentOverlappingWith(it) }
    if (nextOverlap != null) {
        node.visualDebug = "4"

        // remove the direct connection between overlap and nextOverlap if it exists
        overlap.next.remove(nextOverlap)
        nextOverlap.prev.remove(overlap)

        // add the direct connection between the new node and the next overlap
        nextOverlap.prev.add(node)
        node.next.add(nextOverlap)
        node.nextDepth = nextOverlap
        node.totalDepth = nextOverlap.totalDepth
    }

    // add the connection between overlap and the new node
    node.prev.add(overlap)
    overlap.next.add(node)
    
    // ... (there is a bit more code, see in the full code below)
}

• 当所有元素都添加到图中时，代码将遍历所有图并 for each 图 node 调用factory函数，将元素、开始权重、结束权重和重叠计数传递给调用.函数factory负责创建应该返回的结果，而不是 node .

val visited = mutableSetOf<Node>()
return nonOverlappingNodes.flatMap { node: Node ->
    node.traverse { it.next.iterator() }
        .filter(visited::add) // only process each node once
        .map {
            val startWeight = it.currentDepth / it.totalDepth.toFloat()
            val endWeight = (it.nextDepth?.currentDepth ?: it.totalDepth) / it.totalDepth.toFloat()
            factory(it.element, startWeight, endWeight, it.totalDepth, it.visualDebug)
        }
}

我还定义了一个Booking类和一个EventData类来创建一个小的用法演示.

data class Booking(
    val startTimestamp: LocalDateTime,
    val endTimestamp: LocalDateTime,
) {
    val duration = Duration.between(startTimestamp, endTimestamp)

    companion object {
        fun areOverlapping(a: Booking, b: Booking): Boolean {
            return a.startTimestamp < b.endTimestamp && b.startTimestamp < a.endTimestamp
        }
    }
}

data class EventData(
    val booking: Booking, val startWeight: Float, val endWeight: Float, val overlapCount: Int,
    val visualDebug: String,
) : ParentDataModifier {
    override fun Density.modifyParentData(parentData: Any?) = this@EventData
}

以下是它在调用点的使用方式:

val bookings: List<Booking> // = ...

val events = remember(bookings) {
    bookings.splitHierarchically(
        comparator = compareBy(Booking::startTimestamp).thenByDescending(Booking::duration),
        areOverlapping = Booking::areOverlapping,
        factory = { booking, startWeight, endWeight, overlapCount, visualDebug ->
            EventData(booking, startWeight, endWeight, overlapCount, visualDebug)
        },
    )
}

这就是创建布局时使用事件数据的方式

    // ...
    val eventWidth = ((eventData.endWeight - eventData.startWeight) * availableWidth).roundToInt()
    val placeable = measurable.measure(Constraints.fixed(eventWidth, eventHeight))

    // ...
    val eventX = (eventData.startWeight * availableWidth).roundToInt()
    placeable.place(eventX, eventY)

完整代码

将下面的整个代码复制到一个空的Kotlin文件中，在IDE中打开它，然后判断Compose Pview窗口.This UI should show up.

您还可以从Main Activity调用OverlappingScheduleUI Composable来运行示例代码.

import androidx.compose.foundation.background
import androidx.compose.foundation.layout.Box
import androidx.compose.foundation.layout.Column
import androidx.compose.material3.Text
import androidx.compose.runtime.Composable
import androidx.compose.runtime.remember
import androidx.compose.ui.Modifier
import androidx.compose.ui.graphics.Color
import androidx.compose.ui.layout.Layout
import androidx.compose.ui.layout.ParentDataModifier
import androidx.compose.ui.tooling.preview.Preview
import androidx.compose.ui.unit.Constraints
import androidx.compose.ui.unit.Density
import androidx.compose.ui.unit.dp
import java.time.Duration
import java.time.LocalDateTime
import java.time.LocalTime
import java.time.format.DateTimeFormatter
import java.time.temporal.ChronoUnit
import kotlin.math.roundToInt

// set to true to see some debug info directly on each event
const val showVisualDebug = true

@Preview(showBackground = true)
@Composable
fun OverlappingScheduleUI() {
    val bookings: List<Booking> = LocalDateTime.parse("2023-04-28T08:00:00").let { base ->
        listOf(
            Booking(base.plusMinutes(  0), base.plusMinutes(  0 + 60)),
            Booking(base.plusMinutes( 10), base.plusMinutes( 10 + 60)),
            Booking(base.plusMinutes( 20), base.plusMinutes( 20 + 60)),
            Booking(base.plusMinutes( 30), base.plusMinutes( 30 + 90)),
            Booking(base.plusMinutes( 50), base.plusMinutes( 90 + 120)),

            Booking(base.plusMinutes( 90), base.plusMinutes( 90 + 60)),
            Booking(base.plusMinutes(100), base.plusMinutes(100 + 60)),

            Booking(base.plusMinutes(160), base.plusMinutes(160 + 90)),
            Booking(base.plusMinutes(170), base.plusMinutes(170 + 45)),
            Booking(base.plusMinutes(230), base.plusMinutes(230 + 60)),
            Booking(base.plusMinutes(230), base.plusMinutes(230 + 60)),
            Booking(base.plusMinutes(230), base.plusMinutes(230 + 60)),

            Booking(base.plusMinutes(300), base.plusMinutes(300 + 60)),
            Booking(base.plusMinutes(320), base.plusMinutes(320 + 60)),
        )
    }

    val events = remember(bookings) {
        bookings.splitHierarchically(
            comparator = compareBy(Booking::startTimestamp).thenByDescending(Booking::duration),
            areOverlapping = Booking::areOverlapping,
            factory = { booking, startWeight, endWeight, overlapCount, visualDebug ->
                EventData(booking, startWeight, endWeight, overlapCount, visualDebug)
            },
        )
    }

    Layout(content = {
        val dateTimeFormatter = DateTimeFormatter.ofPattern("HH:mm")
        events.forEach { event ->
            Box(modifier = Modifier
                .then(event)
                .background(color = Color(0f, 0.5f, 1f - event.startWeight * 0.6f))) {
                Column {
                    if (showVisualDebug) Text(event.visualDebug, color = Color.White)
                    Text(event.booking.startTimestamp.format(dateTimeFormatter), color = Color.White)
                }
            }
        }
    }) { measureables, constraints ->
        val hourHeight = 64.dp
        val availableWidth = constraints.maxWidth

        val placeablesWithEvents = measureables.map { measurable ->
            val eventData = measurable.parentData as EventData
            val booking = eventData.booking
            val eventDurationMinutes = ChronoUnit.MINUTES.between(
                booking.startTimestamp,
                booking.endTimestamp
            )
            val eventHeight = ((eventDurationMinutes / 60f) * hourHeight.toPx()).roundToInt()
            val eventWidth = ((eventData.endWeight - eventData.startWeight) * availableWidth).roundToInt()
            val placeable = measurable.measure(Constraints.fixed(eventWidth, eventHeight))

            Pair(placeable, eventData)
        }

        layout(availableWidth, hourHeight.roundToPx() * 24) {
            placeablesWithEvents.forEach { (placeable, eventData) ->
                val booking = eventData.booking
                val eventOffsetMinutes = ChronoUnit.MINUTES.between(
                    LocalTime.MIN, booking.startTimestamp
                )
                val eventY = ((eventOffsetMinutes / 60f) * hourHeight.toPx()).roundToInt()
                val eventX = (eventData.startWeight * availableWidth).roundToInt()

                placeable.place(eventX, eventY, eventData.startWeight)
            }
        }
    }
}

data class Booking(
    val startTimestamp: LocalDateTime,
    val endTimestamp: LocalDateTime,
) {
    val duration = Duration.between(startTimestamp, endTimestamp)

    companion object {
        fun areOverlapping(a: Booking, b: Booking): Boolean {
            return a.startTimestamp < b.endTimestamp && b.startTimestamp < a.endTimestamp
        }
    }
}

data class EventData(
    val booking: Booking, val startWeight: Float, val endWeight: Float, val overlapCount: Int,
    val visualDebug: String,
) : ParentDataModifier {
    override fun Density.modifyParentData(parentData: Any?) = this@EventData
}

/**
 * Traverses the graph-like data structure starting from the receiver.
 *
 * @param depthFirst if true, the traversal is depth-first, otherwise breadth-first
 * @param nextIterator a function that returns an iterator over the next nodes to visit
 * @return a sequence of nodes in the order they are visited
 */
fun <T> T.traverse(depthFirst: Boolean = false, nextIterator: (T) -> Iterator<T>): Sequence<T> {
    return sequence {
        val current = this@traverse
        if (!depthFirst) yield(current)

        val next = nextIterator(current)
        while (next.hasNext()) {
            yieldAll(next.next().traverse(depthFirst, nextIterator))
        }

        if (depthFirst) yield(current)
    }
}

/**
 * Splits the collection into non-overlapping groups.
 * 
 * @param comparator a comparator that orders the elements in the collection supplied through the receiver
 * @param areOverlapping a function that returns `true` if the two elements are overlapping
 * @param factory a function that creates the result from the element, start weight, end weight and overlap count
 * @return a list of results that the [factory] creates over the collection of the input elements
 */
fun <T, R> Collection<T>.splitHierarchically(
    comparator: Comparator<T>,
    areOverlapping: (a: T, b: T) -> Boolean,
    factory: (element: T, startWeight: Float, endWeight: Float, overlapCount: Int, visualDebug: String) -> R,
): List<R> {
    val elements = this

    if (elements.isEmpty()) return emptyList()

    class Node(
        val element: T,
        val currentDepth: Int,
        var totalDepth: Int = currentDepth + 1,
        val prev: MutableList<Node> = mutableListOf(),
        val next: MutableList<Node> = mutableListOf(),
    ) {
        var nextDepth: Node? = null
        var visualDebug = ""
    }

    // Sorting the items with their comparator
    // ensures a deterministic insertion order chosen by the caller
    val sortedElements = elements.sortedWith(comparator)

    val nonOverlappingNodes = mutableListOf<Node>()
    
    // Iterate through the sorted items and add them to one of the graphs.
    // If two items are overlapping they are connected in the same graph
    sortedElements.forEach { elementToInsert ->
        val currentOverlappingWith = { e: Node -> areOverlapping(e.element, elementToInsert) }
        
        val last = nonOverlappingNodes.lastOrNull()

        val firstOverlap = last
            ?.traverse { it.next.iterator() }
            ?.firstOrNull(currentOverlappingWith)

        if (firstOverlap == null) {
            // inserting a new non-overlapping node
            val node = Node(elementToInsert, currentDepth = 0)
            node.visualDebug = "1"
            nonOverlappingNodes.add(node)
        } else if (firstOverlap.currentDepth > 0) {
            val node = Node(elementToInsert, currentDepth = 0, totalDepth = firstOverlap.totalDepth)
            node.visualDebug = "2"

            firstOverlap.prev.add(node)
            node.next.add(firstOverlap)
            node.nextDepth = firstOverlap

            // inserting a new top node at depth 0 that has an overlap deeper down the hierarchy
            nonOverlappingNodes.add(node)
        }
        else {
            // insert an overlapping node at a deeper depth into the first overlap-free gap
            val overlap = last
                .traverse { it.next.iterator() }
                .fold(null as Node?) { lastOverlap, next ->
                    val adjacent = lastOverlap == null || lastOverlap.currentDepth + 1 == next.currentDepth
                    if (adjacent && currentOverlappingWith(next)) next else lastOverlap
                }!!

            // create the new node at the depth of the insertion
            val node = Node(elementToInsert, currentDepth = overlap.currentDepth + 1)
            node.totalDepth = overlap.totalDepth.coerceAtLeast(node.totalDepth)
            node.visualDebug = "3"

            val nextOverlap = overlap
                .traverse { it.next.iterator() }
                .firstOrNull { it !== overlap && currentOverlappingWith(it) }
            if (nextOverlap != null) {
                node.visualDebug = "4"

                // remove the direct connection between overlap and nextOverlap if it exists
                overlap.next.remove(nextOverlap)
                nextOverlap.prev.remove(overlap)

                // add the direct connection between the new node and the next overlap
                nextOverlap.prev.add(node)
                node.next.add(nextOverlap)
                node.nextDepth = nextOverlap
                node.totalDepth = nextOverlap.totalDepth
            }

            // add the connection between overlap and the new node
            node.prev.add(overlap)
            overlap.next.add(node)

            // updating the nextDepth of the overlap if the new node is closer
            if (node.currentDepth < (overlap.nextDepth?.currentDepth ?: Int.MAX_VALUE)) {
                overlap.nextDepth = node
            }

            // propagate the total depth inside the current graph only
            val totalDepth = node.totalDepth           

            val visited = mutableSetOf(node)
            node.traverse {
                iterator {
                    yieldAll(it.prev.filter(visited::add))
                    yieldAll(it.next.filter(visited::add))
                }
            }.forEach {
                it.totalDepth = totalDepth
            }
        }
    }

    val visited = mutableSetOf<Node>()
    return nonOverlappingNodes.flatMap { node: Node ->
        node.traverse { it.next.iterator() }
            .filter(visited::add) // only process each node once
            .map {
                val startWeight = it.currentDepth / it.totalDepth.toFloat()
                val endWeight = (it.nextDepth?.currentDepth ?: it.totalDepth) / it.totalDepth.toFloat()
                factory(it.element, startWeight, endWeight, it.totalDepth, it.visualDebug)
            }
    }
}