I want to create a list using Kotlin that contains items of another list, based on endDate equals to startDate and .. etc

Example:

listOf( 
{id1, startDate=1, endDate=3},
{id3, startDate=5, endDate=6},
{id2, startDate=3, endDate=5},
{id4, startDate=10, endDate=12},
{id5, startDate=12, endDate=13},
{id6, startDate=13, endDate=16})


result listOf[{id1}, {id2}, {id3}], [{id4}, {id5}, {id6}] // these are two items

CodePudding user response：

With the given dataset, this problem looks innocent at a first glance, but may grow to a more complex problem quickly. Imagine a dataset that has the potential of multiple, possible results. Should longest possible chains be preferred, or a result with balanced chain size?

A naive implementation may be like this (written inside a Kotest).

data class ListItem(
    val id: String,
    val startDate: Int,
    val endDate: Int
)

given("another StackOverflow issue") {

    val coll = listOf(
        ListItem("id1", startDate = 1, endDate = 3),
        ListItem("id3", startDate = 5, endDate = 6),
        ListItem("id2", startDate = 3, endDate = 5),
        ListItem("id4", startDate = 10, endDate = 12),
        ListItem("id5", startDate = 12, endDate = 13),
        ListItem("id6", startDate = 13, endDate = 16)
    )

    `when`("linking chain") {

        /** final result ends up here */
        val chains: MutableList<MutableList<ListItem>> = mutableListOf()

        /** populate dequeue with items ordered by startDate */
        val arrayDeque = ArrayDeque(coll.sortedBy { it.startDate })

        /** loop is iterated at least once, hence do/while */
        do {
            /** add a new chain */
            chains.add(mutableListOf())

            /** get first element for chain */
            var currentItem: ListItem = arrayDeque.removeFirst()

            /** add first element to current chain */
            chains.last().add(currentItem)

            /** add items to current chain until chain is broken */
            while (arrayDeque.any { it.startDate == currentItem.endDate }) {
                /** get next element to add to chain and remove it from dequeue */
                currentItem = arrayDeque
                    .first { it.startDate == currentItem.endDate }
                    .also { arrayDeque.remove(it) }
                chains.last().add(currentItem)
            }
        } while (arrayDeque.any())

        then("result should be as expected") {

            chains.size shouldBe 2
            chains.first().size shouldBe 3
            chains.last().size shouldBe 3

            chains.flatMap { it.map { innerItem -> innerItem.id } } shouldBe listOf(
                "id1",
                "id2",
                "id3",
                "id4",
                "id5",
                "id6",
            )
        }
    }
}