You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@directory.apache.org by Alex Karasulu <ak...@apache.org> on 2009/04/01 17:58:59 UTC
[ApacheDS][AvlTreeMap] insert() fails to replace old value
Hi Kiran,
I have a problem you might be able to help me with. It seems the AvlTreeMap
does not replace old values when someone inserts a K/V pair using the same
key. I've created a simple test case which is now being ignored in
AvlTreeMap on my branch. Here's the commit for the test:
http://svn.apache.org/viewvc?view=rev&revision=760939
If you can look at this and fix fast great but if not I can fix as well.
Just have not ventured into the AVL tree code just yet.
Thanks,
Alex
Re: [ApacheDS][AvlTreeMap] insert() fails to replace old value
Posted by Alex Karasulu <ak...@gmail.com>.
On Thu, Apr 2, 2009 at 9:34 AM, David Jencks <da...@yahoo.com> wrote:
>
> On Apr 1, 2009, at 10:28 PM, Kiran Ayyagari wrote:
>
>
>>
>> David Jencks wrote:
>>
>>> Why isn't it V insert(K, V)? AvlTreeMap doesn't appear to extend
>>> anything.... I don't see how returning the supplied key is very useful
>>> whereas returning the previous value if any is quite useful.
>>>
>>
>> that makes sense, cause its a map, but one issue is this map supports
>> duplicates
>> also, in this case the 'value' defined as V will not be of the same type
>> as the one given during instantiation.
>> e.x given the declaration as AvlTreeMap<Integer,Integer> treeMap = new
>> AvlTreeMap<Integer,Integer>()
>> in case duplicates are enabled the 'value' will hold a AvlTree type.
>>
>> This can easily lead to CCE without some extra checks.
>>
>
> I don't quite see your point of view. I figured that "put" methods only
> return a value when they replace a previous value. If duplicates are
> allowed, then put will never replace a value and always return null. If
> duplicates are not allowed, then there will be 0 (null) or 1 (V) objects to
> return.
>
+1
>
>
>
>>
>> Alex, wdyt? is there any use case that requires the value, if yes, should
>> the same semantic be applied to remove(K,V) also?
>>
>
> I don't see how a return from this can be useful unless something like
> remove(K, null) removes all the values associated with K. In that case
> returning AvlTree<V> might be more appropriate. On the other hand my naive
> expectations would be that remove(K, null) would only remove something is
> insert(K, null) had been called. If I wanted to remove all the values
> associated with a K I'd want a method remove(K) and having this return an
> AvlTree(V) seems more appropriate (this could be a singleton if there is
> only one value).
>
+1
These were my thoughts exactly. I think the problem was we copied the
AvlTree<V> as a starting point for AvlTreeMap<K,V>.
Thanks for the clarification David.
Alex
Re: [ApacheDS][AvlTreeMap] insert() fails to replace old value
Posted by ayyagarikiran <ay...@gmail.com>.
David Jencks wrote:
>
> On Apr 1, 2009, at 10:28 PM, Kiran Ayyagari wrote:
>
>> This can easily lead to CCE without some extra checks.
>
> I don't quite see your point of view. I figured that "put" methods only
> return a value when they replace a previous value. If duplicates are
> allowed, then put will never replace a value and always return null. If
> duplicates are not allowed, then there will be 0 (null) or 1 (V) objects
> to return.
>
ah, right, I was mixing both the value passed and the actual 'value' present in node.
> I don't see how a return from this can be useful unless something like
> remove(K, null) removes all the values associated with K. In that case
> returning AvlTree<V> might be more appropriate. On the other hand my
> naive expectations would be that remove(K, null) would only remove
> something is insert(K, null) had been called. If I wanted to remove all
> the values associated with a K I'd want a method remove(K) and having
> this return an AvlTree(V) seems more appropriate (this could be a
> singleton if there is only one value).
the current impl removes the all the values associated with a key if remove(K,null) is called
assuming that we don't allow null to be inserted by checking at a higher level (ex. the XXXTable implementations)
But, yes this is certainly possible to have null values, provided the comparators handle them properly.
Returning a singleton AvlTree<V> would be a overhead, but if this is something really required will add it
thanks David.
Kiran Ayyagari
Re: [ApacheDS][AvlTreeMap] insert() fails to replace old value
Posted by David Jencks <da...@yahoo.com>.
On Apr 1, 2009, at 10:28 PM, Kiran Ayyagari wrote:
>
>
> David Jencks wrote:
>> Why isn't it V insert(K, V)? AvlTreeMap doesn't appear to extend
>> anything.... I don't see how returning the supplied key is very
>> useful whereas returning the previous value if any is quite useful.
>
> that makes sense, cause its a map, but one issue is this map
> supports duplicates
> also, in this case the 'value' defined as V will not be of the same
> type as the one given during instantiation.
> e.x given the declaration as AvlTreeMap<Integer,Integer> treeMap =
> new AvlTreeMap<Integer,Integer>()
> in case duplicates are enabled the 'value' will hold a AvlTree type.
>
> This can easily lead to CCE without some extra checks.
I don't quite see your point of view. I figured that "put" methods
only return a value when they replace a previous value. If duplicates
are allowed, then put will never replace a value and always return
null. If duplicates are not allowed, then there will be 0 (null) or 1
(V) objects to return.
>
>
> Alex, wdyt? is there any use case that requires the value, if yes,
> should the same semantic be applied to remove(K,V) also?
I don't see how a return from this can be useful unless something like
remove(K, null) removes all the values associated with K. In that
case returning AvlTree<V> might be more appropriate. On the other
hand my naive expectations would be that remove(K, null) would only
remove something is insert(K, null) had been called. If I wanted to
remove all the values associated with a K I'd want a method remove(K)
and having this return an AvlTree(V) seems more appropriate (this
could be a singleton if there is only one value).
thanks
david jencks
>
>
> thanks David
>
> Kiran Ayyagari
Re: [ApacheDS][AvlTreeMap] insert() fails to replace old value
Posted by Kiran Ayyagari <ay...@gmail.com>.
David Jencks wrote:
>
>
> Why isn't it V insert(K, V)? AvlTreeMap doesn't appear to extend
> anything.... I don't see how returning the supplied key is very useful
> whereas returning the previous value if any is quite useful.
that makes sense, cause its a map, but one issue is this map supports duplicates
also, in this case the 'value' defined as V will not be of the same type as the one given during instantiation.
e.x given the declaration as AvlTreeMap<Integer,Integer> treeMap = new AvlTreeMap<Integer,Integer>()
in case duplicates are enabled the 'value' will hold a AvlTree type.
This can easily lead to CCE without some extra checks.
Alex, wdyt? is there any use case that requires the value, if yes, should the same semantic be applied to remove(K,V) also?
thanks David
Kiran Ayyagari
Re: [ApacheDS][AvlTreeMap] insert() fails to replace old value
Posted by David Jencks <da...@yahoo.com>.
On Apr 1, 2009, at 11:49 AM, Kiran Ayyagari wrote:
> hi Alex,
>
> Thanks for reporting this, have fixed at revision [1].
>
> I think there is no way with generics that we can return the
> replaced value V
> cause the signature of insert is - *K* insert( K, V )
Why isn't it V insert(K, V)? AvlTreeMap doesn't appear to extend
anything.... I don't see how returning the supplied key is very useful
whereas returning the previous value if any is quite useful.
thanks
david jencks
>
>
> [1] http://svn.apache.org/viewvc?view=rev&revision=761007
>
> Kiran Ayyagari
>
> Alex Karasulu wrote:
>> Hi Kiran,
>> I have a problem you might be able to help me with. It seems the
>> AvlTreeMap does not replace old values when someone inserts a K/V
>> pair using the same key. I've created a simple test case which is
>> now being ignored in AvlTreeMap on my branch. Here's the commit
>> for the test:
>> http://svn.apache.org/viewvc?view=rev&revision=760939 <http://svn.apache.org/viewvc?view=rev&revision=760939
>> >
>> If you can look at this and fix fast great but if not I can fix as
>> well. Just have not ventured into the AVL tree code just yet.
>> Thanks,
>> Alex
Re: [ApacheDS][AvlTreeMap] insert() fails to replace old value
Posted by Kiran Ayyagari <ay...@gmail.com>.
hi Alex,
Thanks for reporting this, have fixed at revision [1].
I think there is no way with generics that we can return the replaced value V
cause the signature of insert is - *K* insert( K, V )
[1] http://svn.apache.org/viewvc?view=rev&revision=761007
Kiran Ayyagari
Alex Karasulu wrote:
> Hi Kiran,
>
> I have a problem you might be able to help me with. It seems the
> AvlTreeMap does not replace old values when someone inserts a K/V pair
> using the same key. I've created a simple test case which is now being
> ignored in AvlTreeMap on my branch. Here's the commit for the test:
>
> http://svn.apache.org/viewvc?view=rev&revision=760939
> <http://svn.apache.org/viewvc?view=rev&revision=760939>
>
> If you can look at this and fix fast great but if not I can fix as
> well. Just have not ventured into the AVL tree code just yet.
>
> Thanks,
> Alex