Adding or moving an element in a list already sorted

user_14305770 0
Viewed 48

I'm looking for a way to add an element in a list already sorted or move an existing element.

data class House(
    val id: Int,
    val sold: Boolean,
    val creationDate: LocalDate,
    ...
)

My list is already sorted on 2 parameters (sold and creationDate).

Example of a list already sorted :
[
    House(123, false, 2015-03-23, ...),
    House(456, false, 2015-01-11, ...),
    House(789, false, 2014-08-30, ...), // <- I'm looking for move this one
    House(147, false, 2014-02-15, ...),
    House(258, true, 2016-06-02, ...),
    House(369, true, 2015-04-20, ...),
    House(321, true, 2015-01-28, ...),
    House(654, true, 2011-11-01, ...)
]

Now if an house is sold, (House with id 789) how can I move an item from the first part of the list to the other part without reordering all the list. (for a performance concern) This new position have to consider the key "creationDate".

List updated :
[
    House(123, false, 2015-03-23, ...),
    House(456, false, 2015-01-11, ...),
    House(147, false, 2014-02-15, ...),
    House(258, true, 2016-06-02, ...),
    House(369, true, 2015-04-20, ...),
    House(321, true, 2015-01-28, ...),
    House(789, true, 2014-08-30, ...), // <- Result expected
    House(654, true, 2011-11-01, ...)
]

Thank's for your help.

kotlin list sorting
2 Answers

Suppose you have:

val list = mutableListOf<House>(
    ...
)
val indexToMove = 2

You can remove the element first, then use a binary search to find where it should be inserted. binarySearch would return (-insertion point - 1) if the element is not found. And if the same element happens to be in the list, we'll just use the index of that element as the insertion point.

val removed = list.removeAt(indexToMove)
removed.sold = true // shouldn't "sold" be a var if a house can be sold?

// this should be the same comparator you used for sorting the list
val comparator: Comparator<House> = 
    compareBy(House::sold)
    .thenByDescending(House::creationDate)
val searchResult = list.binarySearch(removed, comparator)
val insertionPoint =
    if (searchResult < 0) {
        -(searchResult + 1)
    } else {
        searchResult
    }
list.add(insertionPoint, removed)
user_51335850

Based on the assumption that your list is already sorted, you can remove the house from the list, and re-insert it in the right place. The sold house has to be inserted at the index of the first house that has to come after the house you want to insert.

In this case, you're looking for the first house that is sold and has a creation date that is earlier than the house you just sold:

val index = houseList.indexOfFirst { 
    it.sold && it.creationDate < soldHouse.creationDate 
}

With removing the house from the list and converting it to a sold house, this gives

val houseList = mutableListOf(
    House(123, false, LocalDate.of(2015, 3, 23)),
    House(456, false, LocalDate.of(2015, 1, 11)),
    House(789, false, LocalDate.of(2014, 8, 30)),
    House(147, false, LocalDate.of(2014, 2, 15)),
    House(258, true, LocalDate.of(2016, 6, 2)),
    House(369, true, LocalDate.of(2015, 4, 20)),
    House(321, true, LocalDate.of(2015, 1, 28)),
    House(654, true, LocalDate.of(2011, 11, 1))
)

println("old house list:")
println(houseList.joinToString(", ") {it.id.toString()})

val houseToSell = houseList.firstOrNull { it.id == 789 } ?: return
houseList.remove(houseToSell)
val soldHouse = houseToSell.copy(sold = true)

val index = houseList.indexOfFirst { it.sold && it.creationDate < soldHouse.creationDate }
if (index == -1) houseList.add(0, soldHouse)
else houseList.add(index, soldHouse)

println("new house list:")
println(houseList.joinToString(", ") {it.id.toString()})

which prints

old house list:
123, 456, 789, 147, 258, 369, 321, 654
new house list:
123, 456, 147, 258, 369, 321, 789, 654
user_66295690
Related