scala - Binary search on an indexed collection (a sorted, indexed sequence) -

scala - Binary search on an indexed collection (a sorted, indexed sequence) -

i have indexed collection (it must indexed) of type a:

var coll: indexedseq[a]

i wish maintain coll sorted according ordering[a] adding/removing items to/from it. obvious mechanism like:

def binarysearch[a : ordering](a: indexedseq[a], elem: a): int def add(a: a) { val idx = binarysearch(coll, a) coll = (coll take idx) :+ +: (coll drop idx) }

but there neither binarysearch in standard library (odd, seeing there scala.util.sorting.quicksort) , there no datatype can find both indexed , sorted (i guess inefficient structure).

i think slice on treeset reasonably efficient (and can utilize one-element range), you're right--it's unusual there no indexed sorted info structure. , it's efficient enough; sorted tree can used way if number of children tracked. think it's oversight it's missing.

you can utilize set repeated elements if wrap them tag allows reference equality, , can create sure they're ordered:

class tag[a](val value: a)(implicit ord: ordering[a]) extends ordered[tag[a]] { def compare(ta: tag[a]) = { val c = ord.compare(value,ta.value) if (c != 0) c else if (this eq ta) 0 else system.identityhashcode(this) compare system.identityhashcode(ta) } override def tostring = value.tostring+"'" override def hashcode = value.hashcode override def equals(a: any) = a.asinstanceof[anyref] eq } scala> collection.immutable.treeset[tag[int]]() ++ list(1,2,3,2,1).map(i => new tag(i)) res1: scala.collection.immutable.treeset[tag[int]] = treeset(1', 1', 2', 2', 3') scala> res1.slice(2,3).head res2: tag[int] = 2'

this add together lot of overhead comparatively simple task, however.

scala indexing binary-search