- 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