Skip to content

Instantly share code, notes, and snippets.

@fancellu
Created August 30, 2015 15:03
Embed
What would you like to do?
Simple insertion into an ordered List
val li=List(1,2,10,20,30) //> li : List[Int] = List(1, 2, 10, 20, 30)
def insert[T](li:List[T],x:T)(implicit cmp:Ordering[T])={
val (first,last)=li.partition {cmp.lteq(_, x) }
first:::x::last
} //> insert: [T](li: List[T], x: T)(implicit cmp: Ordering[T])List[T]
insert(li,11) //> res0: List[Int] = List(1, 2, 10, 11, 20, 30)
insert(li,10) //> res1: List[Int] = List(1, 2, 10, 10, 20, 30)
insert(li,9) //> res2: List[Int] = List(1, 2, 9, 10, 20, 30)
insert(li,0) //> res3: List[Int] = List(0, 1, 2, 10, 20, 30)
insert(li,999) //> res4: List[Int] = List(1, 2, 10, 20, 30, 999)
insert(List('a','b','m','z'),'l') //> res5: List[Char] = List(a, b, l, m, z)
@fancellu
Copy link
Author

You can of course use the mutable PriorityQueue

http://www.scala-lang.org/api/current/index.html#scala.collection.mutable.PriorityQueue

e.g.

val pq=collection.mutable.PriorityQueue(1,2,10,20,30).reverse
pq+=11
pq.clone.dequeueAll // to print emit in priority order

@fancellu
Copy link
Author

Also can use collection.immutable.SortedSet if you don't need repeated values.

e.g.

val ss=collection.immutable.SortedSet(1,2,10,20,30)
ss+11 //> res0: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 10, 11, 20,
//| 30)
ss+9 //> res1: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 9, 10, 20, 3
//| 0)
ss+10 //> res2: scala.collection.immutable.SortedSet[Int] = TreeSet(1, 2, 10, 20, 30)

@abbas-taher
Copy link

very nice.
I was writing an imperative version and it looked ugly.
Thanks

@mayonesa
Copy link

unfortunately, partition will not exploit the fact that it is sorted and it can binary-searched into

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment