- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers

# Binary search in a TreeMap

Mon, 2010-03-22, 14:56

hello,

i am looking for a growable collection that allows sorted insertion at O(log n) cost and binary search in O(log n) such that it returns the greatest element that is not larger than the query argument, e.g.

query( x ) --> return the element in the collection that is closest to x, (possible equals x), but is no larger than x.

i think scala.collection.immutable.TreeMap would be suitable, but unfortunately doesn't provide public access to tree so that i could walk down from root to the children.... i was thinking to do

scala> class MyTreeMap[ A, B ]()( implicit ordering: Ordering[ A ]) extends scala.collection.immutable.TreeMap[ A, B ]()( ordering ) {

| def root = tree

| }

defined class MyTreeMap

but then as soon as i add elements:

scala> var t = new MyTreeMap[ Int, String ]

t: MyTreeMap[Int,String] = Map()

scala> t += (20 -> "twenty")

:7: error: type mismatch;

found : scala.collection.immutable.TreeMap[Int,String]

required: MyTreeMap[Int,String]

t += (20 -> "twenty")

^

.... i loose my class.

how can i extend TreeMap to gain access to root and so that insertion properly returns my subclass instead of superclass TreeMap?

thanks for help!

best, -sciss-

Mon, 2010-03-22, 16:17

#2
Re: Binary search in a TreeMap

hi,

thank you for the hint with 'to'. i'm trying now to write a class like TreeMap with my added method. but i come across a type problem:

class BinaryTreeMap[ A, +B ]( override val size: Int, t: RedBlack[ A ]#Tree[ B ] )( implicit val ordering: Ordering[ A ])

extends RedBlack[ A ]

with SortedMap[ A, B ]

with SortedMapLike[ A, B, BinaryTreeMap[ A, B ]]

with MapLike[ A, B, BinaryTreeMap[ A, B ]] {

[...]

def getClosestLessOrEqualTo( key: A ) : Option[ B ] =

getClosestLessOrEqualTo( key, tree )

@tailrec

private def getClosestLessOrEqualTo( key: A, t: RedBlack[ A ]#Tree[ B ],

best: Option[ RedBlack[ A ]#NonEmpty[ B ]]) : Option[ B ] = {

val (next, nextBest) = t match {

case leaf: RedBlack[ A ]#NonEmpty[ B ] => {

val cmp = ordering.compare( key, leaf.key )

if( cmp == 0 ) return Some( leaf.value )

if( cmp < 0 ) {

(leaf.left, best)

} else {

val better = best.map( bestLeaf => {

if( ordering.gt( leaf.key, bestLeaf.key )) leaf else bestLeaf

}) orElse Some( leaf )

(leaf.right, better)

}

}

case _ => return best.map( _.value )

}

getClosestLessOrEqualTo( key, next, nextBest )

}

[...]

}

this gives me:

error: type mismatch;

found : scala.collection.immutable.RedBlack[A]#Tree[Any]

required: scala.collection.immutable.RedBlack[A]#Tree[B]

getClosestLessOrEqualTo( key, next )

but if change to

case leaf: RedBlack[ A ]#NonEmpty[ B ] => {

i get instead

warning: non variable type-argument B in type pattern scala.collection.immutable.RedBlack[A]#NonEmpty[B] is unchecked since it is eliminated by erasure

error: covariant type B occurs in contravariant position in type scala.collection.immutable.RedBlack[A]#Tree[B] of value t

private def getClosestLessOrEqualTo( key: A, t: RedBlack[ A ]#Tree[ B ],

error: covariant type B occurs in contravariant position in type Option[scala.collection.immutable.RedBlack[A]#NonEmpty[B]] of value best

best: Option[ RedBlack[ A ]#NonEmpty[ B ]]) : Option[ B ] = {

... so how to solve this pattern match properly?

thanks, -sciss-

Am 22.03.2010 um 14:16 schrieb Randall R Schulz:

> On Monday March 22 2010, Sciss wrote:

>> hello,

>>

>> I am looking for a growable collection that allows sorted insertion

>> at O(log n) cost and binary search in O(log n) such that it returns

>> the greatest element that is not larger than the query argument, e.g.

>

> You can use the "from" (or "to") method to create sub-range bounded by a

> value you specify.

>

> Considering the fact that Java's sorted collections have the operation

> you want, I think it should exist in the pertinent Scala collections,

> too.

>

>

>> ...

>>

>> How can i extend TreeMap to gain access to root and so that insertion

>> properly returns my subclass instead of superclass TreeMap?

>

> Extending the 2.8 collection classes is not always trivial, depending on

> the signature of the methods you want to add or override.

>

> I was going to suggest you look at how TreeHashMap is implemented, but I

> see it's not (implemented, that is; it's a placeholder with a few

> hundred lines of code, all commented out). Is it going to be reinstated

> before the final release of Scala 2.8?

>

>

>> Thanks for help!

>>

>> best, -sciss-

>

>

> Randall Schulz

Mon, 2010-03-22, 16:27

#3
Re: Binary search in a TreeMap

p.s. if i change

class BinaryTreeMap[ A, +B ]

to

class BinaryTreeMap[ A, B ]

and

case leaf: RedBlack[ A ]#NonEmpty[ B ] => {

to

case leaf_bla: RedBlack[ _ ]#NonEmpty[ _ ] => {

val leaf = leaf_bla.asInstanceOf[ RedBlack[ A ]#NonEmpty[ B ]]

it compiles without warnings and errors. this is obivously ugly, and i wonder why the type system always needs to get into your way when you do something that is slightly non simple.

shrug,

- sciss -

Am 22.03.2010 um 15:15 schrieb Sciss:

> hi,

>

> thank you for the hint with 'to'. i'm trying now to write a class like TreeMap with my added method. but i come across a type problem:

>

> class BinaryTreeMap[ A, +B ]( override val size: Int, t: RedBlack[ A ]#Tree[ B ] )( implicit val ordering: Ordering[ A ])

> extends RedBlack[ A ]

> with SortedMap[ A, B ]

> with SortedMapLike[ A, B, BinaryTreeMap[ A, B ]]

> with MapLike[ A, B, BinaryTreeMap[ A, B ]] {

>

> [...]

>

> def getClosestLessOrEqualTo( key: A ) : Option[ B ] =

> getClosestLessOrEqualTo( key, tree )

>

> @tailrec

> private def getClosestLessOrEqualTo( key: A, t: RedBlack[ A ]#Tree[ B ],

> best: Option[ RedBlack[ A ]#NonEmpty[ B ]]) : Option[ B ] = {

> val (next, nextBest) = t match {

> case leaf: RedBlack[ A ]#NonEmpty[ B ] => {

> val cmp = ordering.compare( key, leaf.key )

> if( cmp == 0 ) return Some( leaf.value )

> if( cmp < 0 ) {

> (leaf.left, best)

> } else {

> val better = best.map( bestLeaf => {

> if( ordering.gt( leaf.key, bestLeaf.key )) leaf else bestLeaf

> }) orElse Some( leaf )

> (leaf.right, better)

> }

> }

> case _ => return best.map( _.value )

> }

> getClosestLessOrEqualTo( key, next, nextBest )

> }

>

> [...]

> }

>

> this gives me:

>

> error: type mismatch;

> found : scala.collection.immutable.RedBlack[A]#Tree[Any]

> required: scala.collection.immutable.RedBlack[A]#Tree[B]

> getClosestLessOrEqualTo( key, next )

>

> but if change to

>

> case leaf: RedBlack[ A ]#NonEmpty[ B ] => {

>

> i get instead

>

> warning: non variable type-argument B in type pattern scala.collection.immutable.RedBlack[A]#NonEmpty[B] is unchecked since it is eliminated by erasure

> error: covariant type B occurs in contravariant position in type scala.collection.immutable.RedBlack[A]#Tree[B] of value t

> private def getClosestLessOrEqualTo( key: A, t: RedBlack[ A ]#Tree[ B ],

> error: covariant type B occurs in contravariant position in type Option[scala.collection.immutable.RedBlack[A]#NonEmpty[B]] of value best

> best: Option[ RedBlack[ A ]#NonEmpty[ B ]]) : Option[ B ] = {

>

> ... so how to solve this pattern match properly?

>

> thanks, -sciss-

>

>

> Am 22.03.2010 um 14:16 schrieb Randall R Schulz:

>

>> On Monday March 22 2010, Sciss wrote:

>>> hello,

>>>

>>> I am looking for a growable collection that allows sorted insertion

>>> at O(log n) cost and binary search in O(log n) such that it returns

>>> the greatest element that is not larger than the query argument, e.g.

>>

>> You can use the "from" (or "to") method to create sub-range bounded by a

>> value you specify.

>>

>> Considering the fact that Java's sorted collections have the operation

>> you want, I think it should exist in the pertinent Scala collections,

>> too.

>>

>>

>>> ...

>>>

>>> How can i extend TreeMap to gain access to root and so that insertion

>>> properly returns my subclass instead of superclass TreeMap?

>>

>> Extending the 2.8 collection classes is not always trivial, depending on

>> the signature of the methods you want to add or override.

>>

>> I was going to suggest you look at how TreeHashMap is implemented, but I

>> see it's not (implemented, that is; it's a placeholder with a few

>> hundred lines of code, all commented out). Is it going to be reinstated

>> before the final release of Scala 2.8?

>>

>>

>>> Thanks for help!

>>>

>>> best, -sciss-

>>

>>

>> Randall Schulz

>

Wed, 2010-03-24, 01:37

#4
Re: Binary search in a TreeMap

On Mon, Mar 22, 2010 at 3:16 PM, Randall R Schulz <rschulz [at] sonic [dot] net> wrote:

On Monday March 22 2010, Sciss wrote:I think it will be eliminated. immutable.HashMap now uses hash tries which should be more efficient than TreeHashMap in most cases.

> hello,

>

> I am looking for a growable collection that allows sorted insertion

> at O(log n) cost and binary search in O(log n) such that it returns

> the greatest element that is not larger than the query argument, e.g.

You can use the "from" (or "to") method to create sub-range bounded by a

value you specify.

Considering the fact that Java's sorted collections have the operation

you want, I think it should exist in the pertinent Scala collections,

too.

> ...

>

> How can i extend TreeMap to gain access to root and so that insertion

> properly returns my subclass instead of superclass TreeMap?

Extending the 2.8 collection classes is not always trivial, depending on

the signature of the methods you want to add or override.

I was going to suggest you look at how TreeHashMap is implemented, but I

see it's not (implemented, that is; it's a placeholder with a few

hundred lines of code, all commented out). Is it going to be reinstated

before the final release of Scala 2.8?

Cheers

-- Martin

Wed, 2010-03-24, 01:57

#5
Re: Binary search in a TreeMap

On Tuesday March 23 2010, martin odersky wrote:

> On Mon, Mar 22, 2010 at 3:16 PM, wrote:

> > ...

> >

> > I was going to suggest you look at how TreeHashMap is implemented,

> > but I see it's not (implemented, that is; it's a placeholder with a

> > few hundred lines of code, all commented out). Is it going to be

> > reinstated before the final release of Scala 2.8?

> >

>

> I think it will be eliminated. immutable.HashMap now uses hash

> tries which should be more efficient than TreeHashMap in most cases.

Will this hash map also maintain key order? That is the whole point of

Tree(Hash)Map, right?

Wed, 2010-03-24, 18:17

#6
Re: Binary search in a TreeMap

On Mar 24, 2010, at 1:41 AM, Randall R Schulz wrote:

> On Tuesday March 23 2010, martin odersky wrote:

>> On Mon, Mar 22, 2010 at 3:16 PM, wrote:

>>> ...

>>>

>>> I was going to suggest you look at how TreeHashMap is implemented,

>>> but I see it's not (implemented, that is; it's a placeholder with a

>>> few hundred lines of code, all commented out). Is it going to be

>>> reinstated before the final release of Scala 2.8?

>>>

>>

>> I think it will be eliminated. immutable.HashMap now uses hash

>> tries which should be more efficient than TreeHashMap in most cases.

>

> Will this hash map also maintain key order? That is the whole point of

> Tree(Hash)Map, right?

TreeMap != TreeHashMap

TreeMap, which will be kept, is sorted while TreeHashMap isn't.

- Tiark

Wed, 2010-03-24, 23:37

#7
Re: Binary search in a TreeMap

On Wednesday March 24 2010, Tiark Rompf wrote:

> On Mar 24, 2010, at 1:41 AM, Randall R Schulz wrote:

> > ...

> >

> > Will this hash map also maintain key order? That is the whole point

> > of Tree(Hash)Map, right?

>

> TreeMap != TreeHashMap

>

> TreeMap, which will be kept, is sorted while TreeHashMap isn't.

What is tree-like about TreeHashMap?

> - Tiark

Randall Schulz

On Monday March 22 2010, Sciss wrote:

> hello,

>

> I am looking for a growable collection that allows sorted insertion

> at O(log n) cost and binary search in O(log n) such that it returns

> the greatest element that is not larger than the query argument, e.g.

You can use the "from" (or "to") method to create sub-range bounded by a

value you specify.

Considering the fact that Java's sorted collections have the operation

you want, I think it should exist in the pertinent Scala collections,

too.

> ...

>

> How can i extend TreeMap to gain access to root and so that insertion

> properly returns my subclass instead of superclass TreeMap?

Extending the 2.8 collection classes is not always trivial, depending on

the signature of the methods you want to add or override.

I was going to suggest you look at how TreeHashMap is implemented, but I

see it's not (implemented, that is; it's a placeholder with a few

hundred lines of code, all commented out). Is it going to be reinstated

before the final release of Scala 2.8?

> Thanks for help!

>

> best, -sciss-

Randall Schulz