0

I'm new to Scala, does Scala support a fixed length SortedMap?

What I have in mind is a map that does the following:

  • Takes a max_size parameter upon creation
  • Upon an add, checks if there are already max_size elements
    • If there is, remove the smallest key and its value first (key's gonna be an Int)
    • Then adds the key and value to the map.

Strictly speaking, I don't need the map to be sorted, but it seems necessary/available if we're removing the smallest key

I wanted to ask before I started rolling my own. Also I will be running this under Samza, which I believe is single threaded and so concurrency won't be a concern.

I'm on scala 2.10

benhsu
  • 5,346
  • 8
  • 39
  • 47
  • Possible duplicate of [Java time-based map/cache with expiring keys](http://stackoverflow.com/questions/3802370/java-time-based-map-cache-with-expiring-keys) – LaloInDublin Apr 12 '16 at 22:58
  • there's not a default collection for that. but in scala you should use immutable objects, so a Map shouldn't change its size (an add would return a different Map). Still, maybe there's some collection for that – pedrorijo91 Apr 12 '16 at 23:18
  • note: scala 2.12 is almost out (already out?), you should be already migrated into 2.11 :) – pedrorijo91 Apr 12 '16 at 23:18
  • Possible duplicate of [Maximum Length for scala queue](http://stackoverflow.com/questions/6918731/maximum-length-for-scala-queue) – nmat Apr 12 '16 at 23:51

2 Answers2

2

You can do something simple like this based on TreeMap which guarantees order of elements by key:

import scala.collection.immutable.TreeMap

def add[K,V](map: TreeMap[K,V], elem: (K,V), maxSize: Int): TreeMap[K,V] = {
  map.takeRight(maxSize - 1) + elem
}

Here is how to use it:

scala> val m = TreeMap(1 -> "one", 2 -> "two", 3 -> "three")
m: scala.collection.immutable.TreeMap[Int,String] = 
Map(1 -> one, 2 -> two, 3 -> three)

scala> val m1 = add(m, 0 -> "zero", 4)
m1: scala.collection.immutable.TreeMap[Int,String] = 
Map(0 -> zero, 1 -> one, 2 -> two, 3 -> three)

scala> val m2 = add(m1, 4 -> "four", 4)
m2: scala.collection.immutable.TreeMap[Int,String] = 
Map(1 -> one, 2 -> two, 3 -> three, 4 -> four)

scala> val m3 = add(m2, 5 -> "five", 4)
m3: scala.collection.immutable.TreeMap[Int,String] = 
Map(2 -> two, 3 -> three, 4 -> four, 5 -> five)

scala> val m4 = add(m3, 0 -> "zero", 4)
m4: scala.collection.immutable.TreeMap[Int,String] = 
Map(0 -> zero, 3 -> three, 4 -> four, 5 -> five)

You can obviously try to make it more convenient to suit your needs.

yǝsʞǝla
  • 16,272
  • 2
  • 44
  • 65
  • Thank you! This is very helpful. I found a small bug where if you keep adding elements smaller than the minimum element in the set (say if the smallest key is 2 and you're adding 0) the result won't be quite correct. – benhsu Apr 13 '16 at 15:22
  • I wanted to write it the way you did, but I followed your requirements - remove smallest, then add. Both are valid for different circumstances. – yǝsʞǝla Apr 13 '16 at 23:10
0

Aleksey's answer was very helpful. I made a small fix to it

import scala.collection.immutable.TreeMap

def add[K,V](map: TreeMap[K,V], elem: (K,V), maxSize: Int): TreeMap[K,V] = {
  (map + elem).takeRight(maxSize - 1)
}


 val m = TreeMap(1 -> "one", 2 -> "two", 3 -> "three")

 val m1 = add(m, 0 -> "zero", 4)

 val m2 = add(m1, 4 -> "four", 4)

 val m3 = add(m2, 0 -> "zero", 4)

 val m4 = add(m3, 1 -> "one", 4)

 val m5 = add(m4, 0 -> "zero", 4)

 val m6 = add(m5, 1 -> "one", 4)
benhsu
  • 5,346
  • 8
  • 39
  • 47
  • I wanted to write it the way you did, but I followed your requirements - remove smallest, then add. Both are valid for different circumstances. – yǝsʞǝla Apr 13 '16 at 23:03