CODEWITHSUNDEEP
scalasortingscala-collections
davidrpugh
davidrpugh

Reputation: 4573

Sorted collection of orders in Scala

I need to maintain a sorted collection of orders of the form...

Order(id: Long, price: Long, quantity: Long)

...where order.price is the variable on which the order of the collection is defined. I also need to look up an order by order.id and remove it from the collection.

I initially tried mutable.PriorityQueue, but could not figure out how to look up and remove orders. I then moved to immutable.TreeSet, but TreeSet considers orders with the same price duplicates and drops one of them. I had thought about using immutable.TreeMap but that collection sorts keys and the natural keys for my orders is id not price.

What collection should I use? The ideal collection would seem to be a Map where the sort order is defined over keys. As far as I can tell, this doesn't exist.

Upvotes: 1

Views: 1418

Answers (1)

Daniel Langdon
Daniel Langdon

Reputation: 5999

I believe there is no collection that does exactly what you mention.

You might be able to inherit from java's LinkedHashMap. It keeps items accessible by key but keep a linked list of the internal nodes to have a stable ordering. That implementation uses insertion order (most efficient since you just append to the underlying linked list), but you could customize it to do insertions on the liked list based on a custom Comparator (so insertion would be O(n)). Hope it helps!

Upvotes: 0

Related Questions