You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Phil Steitz <ph...@steitz.com> on 2003/11/24 03:53:52 UTC
[collections] CaseInsensitiveHashMap
A few weeks back, David Graham submitted code for a
CaseInsensitiveHashMap here:
http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
This looks like a good addition to [collections] to me.
Any objections to my coding up some tests and adding this class to the
map package?
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Janek Bogucki <ya...@studylink.com>.
On Sun, 2003-11-23 at 22:25, Brian S O'Neill wrote:
> This implementation converts the key to lowercase on every get and put,
> which adds a bit of object allocation overhead. Also, simply converting
> to lowercase does not make it fully case-insensitive. There is a comment
> in String.regionMatches that brings up something about the Georgian
> alphabet.
>
> What I always do when I want a case-insensitive map is to construct a
> TreeMap with String.CASE_INSENSITIVE_ORDER.
>
This Georgian issue could be avoided by allowing CaseInsensitiveHashMap
to restrict it's scope to Sql naming standards for columns and leaving
it in DbUtils.
-Janek
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by David Graham <gr...@yahoo.com>.
--- Brian S O'Neill <br...@earthlink.net> wrote:
> This implementation converts the key to lowercase on every get and put,
> which adds a bit of object allocation overhead.
How else would you accomplish the class' goal?
> Also, simply converting
> to lowercase does not make it fully case-insensitive. There is a comment
>
> in String.regionMatches that brings up something about the Georgian
> alphabet.
I couldn't find any such comment in the javadocs
http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#regionMatches(boolean,
int, java.lang.String, int, int)
>
> What I always do when I want a case-insensitive map is to construct a
> TreeMap with String.CASE_INSENSITIVE_ORDER.
We don't want a sorted Map implementation, just an implementation with
case insensitive Strings as keys. Also, TreeMap is known to be much
slower than HashMap.
David
>
> Phil Steitz wrote:
>
> > A few weeks back, David Graham submitted code for a
> > CaseInsensitiveHashMap here:
> >
> > http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
> >
> > This looks like a good addition to [collections] to me.
> >
> > Any objections to my coding up some tests and adding this class to the
>
> > map package?
> >
> > Phil
> >
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
> >
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Brian S O'Neill <br...@earthlink.net>.
This implementation converts the key to lowercase on every get and put,
which adds a bit of object allocation overhead. Also, simply converting
to lowercase does not make it fully case-insensitive. There is a comment
in String.regionMatches that brings up something about the Georgian
alphabet.
What I always do when I want a case-insensitive map is to construct a
TreeMap with String.CASE_INSENSITIVE_ORDER.
Phil Steitz wrote:
> A few weeks back, David Graham submitted code for a
> CaseInsensitiveHashMap here:
>
> http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
>
> This looks like a good addition to [collections] to me.
>
> Any objections to my coding up some tests and adding this class to the
> map package?
>
> Phil
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Phil Steitz <st...@yahoo.com>.
--- Janek Bogucki <ya...@studylink.com> wrote:
> On Tue, 2003-11-25 at 10:37, Phil Steitz wrote:
> > Thinking about this some more, the semantics of keySet() would be
> > difficult with "CompositeMap" approach that I have suggested above. We
>
> > would either have to require that T be idempotent - i.e., T(T(x)) =
> T(x)
> > or have the user supply a (partial) inverse transformer to return *a*
> > pre-image for each transformed key.
> >
> > Phil
>
> Not quite sure if I understood your point entirely but it would not be
> possible to supply an inverse transformation for the lowercase operation
> because it is a many to one function. Perhaps you covered this with the
> word 'partial' but I don't see what you mean by that. What's a partial
> inverse transformer?
>
In the case of toLower(), the identity would work. What I meant was a
function I satisfying T(I(T(x)) = T(x) -- so that the "inverse" would
return something that would, after transformation, map to the same value.
This function needs to select one of the (potentially many) pre-images of
each object in the range of the transformer. An example is the positive
square root as an "inverse" for the squaring function (or the identity as
"inverse" for toLower()).
This is probably not practical, so I guess either keySet() would be broken
(i.e., gets over the interated keySet would not traverse the values in the
Map)if the transformer is not idempotent or it would have to refer to the
underlying Map, which the decorator could expose.
Phil
> -Janek
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Janek Bogucki <ya...@studylink.com>.
On Tue, 2003-11-25 at 10:37, Phil Steitz wrote:
> Thinking about this some more, the semantics of keySet() would be
> difficult with "CompositeMap" approach that I have suggested above. We
> would either have to require that T be idempotent - i.e., T(T(x)) = T(x)
> or have the user supply a (partial) inverse transformer to return *a*
> pre-image for each transformed key.
>
> Phil
Not quite sure if I understood your point entirely but it would not be
possible to supply an inverse transformation for the lowercase operation
because it is a many to one function. Perhaps you covered this with the
word 'partial' but I don't see what you mean by that. What's a partial
inverse transformer?
-Janek
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Phil Steitz <ph...@steitz.com>.
Phil Steitz wrote:
> Stephen Colebourne wrote:
>
>> I would like to propose an alternative solution to the problem that
>> IMO fits
>> well with current [collections] direction.
>>
>> Consider a new Map implementation that acts as a direct replacement for
>> HashMap, call it HashMapA (A for apache ;-). This class contains
>> basically
>> the same code as HashMap, although it must be written without using
>> cut and
>> paste (ie from scratch - Sun licence issues).
>>
>> HashMapA differs from HashMap in that the hashing algorithm and equals
>> comparison methods are dedicated protected methods. It then becomes
>> easy for
>> a subclass to be written that compares keys using case insensitivity
>> (amongst other things). HashMapA would also have a mapIterator()
>> method to
>> access the new map iterator concept.
>>
>> Finally, there would probably need to be a MapA interface to allow
>> access to
>> the map iterator.
>>
>
>
> I see this more like Janek does -- the CaseInsensitiveHashMap
> requirement is really a key transformation requirement, not a hashing
> algorithm overriding requirement. I think that it would be *much
> harder* for users of this class to develop well-performing (and
> reliable) custom hash functions than to supply key transformations. I
> may be misunderstanding your proposal. Please explain more and why in
> particular it would not be better to set up something similar to
> TransformedMap that does key transformations on get -- effectively
> making a composite map, M o T, where T is the tranformer. The value of
> this is when T is not 1-1, as in the case of CaseInsensitiveHashMap.
>
> Phil
>
>
Thinking about this some more, the semantics of keySet() would be
difficult with "CompositeMap" approach that I have suggested above. We
would either have to require that T be idempotent - i.e., T(T(x)) = T(x)
or have the user supply a (partial) inverse transformer to return *a*
pre-image for each transformed key.
Phil
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Phil Steitz <ph...@steitz.com>.
Stephen Colebourne wrote:
> I would like to propose an alternative solution to the problem that IMO fits
> well with current [collections] direction.
>
> Consider a new Map implementation that acts as a direct replacement for
> HashMap, call it HashMapA (A for apache ;-). This class contains basically
> the same code as HashMap, although it must be written without using cut and
> paste (ie from scratch - Sun licence issues).
>
> HashMapA differs from HashMap in that the hashing algorithm and equals
> comparison methods are dedicated protected methods. It then becomes easy for
> a subclass to be written that compares keys using case insensitivity
> (amongst other things). HashMapA would also have a mapIterator() method to
> access the new map iterator concept.
>
> Finally, there would probably need to be a MapA interface to allow access to
> the map iterator.
>
I see this more like Janek does -- the CaseInsensitiveHashMap requirement
is really a key transformation requirement, not a hashing algorithm
overriding requirement. I think that it would be *much harder* for users
of this class to develop well-performing (and reliable) custom hash
functions than to supply key transformations. I may be misunderstanding
your proposal. Please explain more and why in particular it would not be
better to set up something similar to TransformedMap that does key
transformations on get -- effectively making a composite map, M o T, where
T is the tranformer. The value of this is when T is not 1-1, as in the
case of CaseInsensitiveHashMap.
Phil
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Rich Dougherty <ri...@rd.gen.nz>.
Stephen Colebourne wrote:
> I would like to propose an alternative solution to the problem that IMO fits
> well with current [collections] direction.
>
> Consider a new Map implementation that acts as a direct replacement for
> HashMap, call it HashMapA (A for apache ;-). This class contains basically
> the same code as HashMap, although it must be written without using cut and
> paste (ie from scratch - Sun licence issues).
>
> HashMapA differs from HashMap in that the hashing algorithm and equals
> comparison methods are dedicated protected methods. It then becomes easy for
> a subclass to be written that compares keys using case insensitivity
> (amongst other things).
You could also consider having a subclass which delegates these methods
to another object (a Hasher?) to make it possible to override the logic
without subclassing.
public interface Hasher {
/**
* Get the hash code for a key.
*/
public int keyHashCode(Object key);
/**
* Tests if a pair of keys are equal.
*/
public boolean keysEqual(Object key1, Object key2);
}
public class DefaultHasher {
public int keyHashCode(Object key) {
return key.hashCode();
}
public boolean keysEqual(Object key1, Object key2) {
return key1.equals(key2);
}
}
public class ComposableHashMapA extends HashMapA {
private Hasher hasher = new DefaultHasher();
...
protected int keyHashCode(Object key) {
return hasher.keyHashCode(key);
}
protected boolean keysEqual(Object key1, Object key2) {
return hasher.keysEqual(key1, key2);
}
...
}
Rich
--
Rich Dougherty
http://www.rd.gen.nz/
Re: [collections] CaseInsensitiveHashMap
Posted by Stephen Colebourne <sc...@btopenworld.com>.
I would like to propose an alternative solution to the problem that IMO fits
well with current [collections] direction.
Consider a new Map implementation that acts as a direct replacement for
HashMap, call it HashMapA (A for apache ;-). This class contains basically
the same code as HashMap, although it must be written without using cut and
paste (ie from scratch - Sun licence issues).
HashMapA differs from HashMap in that the hashing algorithm and equals
comparison methods are dedicated protected methods. It then becomes easy for
a subclass to be written that compares keys using case insensitivity
(amongst other things). HashMapA would also have a mapIterator() method to
access the new map iterator concept.
Finally, there would probably need to be a MapA interface to allow access to
the map iterator.
Stephen
----- Original Message ----- > >
Umm, I didn't notice #get did not apply the transformation. Perhaps not
> > such a good idea to use TransformedMap after all.
> >
> > This behaviour is certainly different to my expectations (although the
> > documentation is clear enough on this point). I wonder what the original
> > use-case for TransformedMap was.
> >
> > If the database client code restricts itself to using lowercase names
> > (an aspect you are in control of) TransformedMap could still be useful
> > but hardly as convenient as the original case insensitive map.
>
> It's a requirement that DbUtils clients use whatever case they want to
> refer to column names in a Map so TransformedMap as it is now won't work.
>
> Regardless, DbUtils doesn't have a dependency on collections and shouldn't
> add one just for this feature. The implementation of
> CaseInsensitiveHashMap is trivial enough to maintain in DbUtils. I opened
> the enhancement against collections in case anyone else had a need for
> this kind of Map. If TransformedMap doesn't change then I think adding
> CaseInsensitiveMap is the best solution.
>
> >
> > -Janek
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
>
>
> __________________________________
> Do you Yahoo!?
> Free Pop-Up Blocker - Get it now
> http://companion.yahoo.com/
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by David Graham <gr...@yahoo.com>.
--- Janek Bogucki <ya...@studylink.com> wrote:
> On Mon, 2003-11-24 at 10:15, David Graham wrote:
> >
> > --- Janek Bogucki <ya...@studylink.com> wrote:
> > > On Sun, 2003-11-23 at 21:53, Phil Steitz wrote:
> > > > A few weeks back, David Graham submitted code for a
> > > > CaseInsensitiveHashMap here:
> > > >
> > > > http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
> > > >
> > > > This looks like a good addition to [collections] to me.
> > > >
> > > > Any objections to my coding up some tests and adding this class to
> the
> > >
> > > > map package?
> > > >
> > > > Phil
> >
> > >
> > > It might be best to use an instance of
> o.a.c.c.decorators.TransformedMap
> > > with a lower case key transformer and a null value transformer to
> > > implement this class. Even though the posted implementation is
> simple,
> > > using the decorator removes the need to have the 'plumbing' code
> > > currently present -- and illustrates the use of the collections
> library.
> > >
> >
> > That's a good idea. I was not aware of TransformedMap or the
> Transformer
> > interface. It seems like they were designed to avoid writing classes
> like
> > CaseInsensitiveHashMap :-). However, it only transforms objects on
> put()
> > calls and not on get(). That behavior would need to change.
> >
> > David
> >
>
> Umm, I didn't notice #get did not apply the transformation. Perhaps not
> such a good idea to use TransformedMap after all.
>
> This behaviour is certainly different to my expectations (although the
> documentation is clear enough on this point). I wonder what the original
> use-case for TransformedMap was.
>
> If the database client code restricts itself to using lowercase names
> (an aspect you are in control of) TransformedMap could still be useful
> but hardly as convenient as the original case insensitive map.
It's a requirement that DbUtils clients use whatever case they want to
refer to column names in a Map so TransformedMap as it is now won't work.
Regardless, DbUtils doesn't have a dependency on collections and shouldn't
add one just for this feature. The implementation of
CaseInsensitiveHashMap is trivial enough to maintain in DbUtils. I opened
the enhancement against collections in case anyone else had a need for
this kind of Map. If TransformedMap doesn't change then I think adding
CaseInsensitiveMap is the best solution.
>
> -Janek
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Janek Bogucki <ya...@studylink.com>.
On Mon, 2003-11-24 at 10:15, David Graham wrote:
>
> --- Janek Bogucki <ya...@studylink.com> wrote:
> > On Sun, 2003-11-23 at 21:53, Phil Steitz wrote:
> > > A few weeks back, David Graham submitted code for a
> > > CaseInsensitiveHashMap here:
> > >
> > > http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
> > >
> > > This looks like a good addition to [collections] to me.
> > >
> > > Any objections to my coding up some tests and adding this class to the
> >
> > > map package?
> > >
> > > Phil
>
> >
> > It might be best to use an instance of o.a.c.c.decorators.TransformedMap
> > with a lower case key transformer and a null value transformer to
> > implement this class. Even though the posted implementation is simple,
> > using the decorator removes the need to have the 'plumbing' code
> > currently present -- and illustrates the use of the collections library.
> >
>
> That's a good idea. I was not aware of TransformedMap or the Transformer
> interface. It seems like they were designed to avoid writing classes like
> CaseInsensitiveHashMap :-). However, it only transforms objects on put()
> calls and not on get(). That behavior would need to change.
>
> David
>
Umm, I didn't notice #get did not apply the transformation. Perhaps not
such a good idea to use TransformedMap after all.
This behaviour is certainly different to my expectations (although the
documentation is clear enough on this point). I wonder what the original
use-case for TransformedMap was.
If the database client code restricts itself to using lowercase names
(an aspect you are in control of) TransformedMap could still be useful
but hardly as convenient as the original case insensitive map.
-Janek
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by David Graham <gr...@yahoo.com>.
--- Janek Bogucki <ya...@studylink.com> wrote:
> On Sun, 2003-11-23 at 21:53, Phil Steitz wrote:
> > A few weeks back, David Graham submitted code for a
> > CaseInsensitiveHashMap here:
> >
> > http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
> >
> > This looks like a good addition to [collections] to me.
> >
> > Any objections to my coding up some tests and adding this class to the
>
> > map package?
> >
> > Phil
>
> It might be best to use an instance of o.a.c.c.decorators.TransformedMap
> with a lower case key transformer and a null value transformer to
> implement this class. Even though the posted implementation is simple,
> using the decorator removes the need to have the 'plumbing' code
> currently present -- and illustrates the use of the collections library.
>
That's a good idea. I was not aware of TransformedMap or the Transformer
interface. It seems like they were designed to avoid writing classes like
CaseInsensitiveHashMap :-). However, it only transforms objects on put()
calls and not on get(). That behavior would need to change.
David
> -Janek
>
__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] CaseInsensitiveHashMap
Posted by Janek Bogucki <ya...@studylink.com>.
On Sun, 2003-11-23 at 21:53, Phil Steitz wrote:
> A few weeks back, David Graham submitted code for a
> CaseInsensitiveHashMap here:
>
> http://nagoya.apache.org/bugzilla/show_bug.cgi?id=24537
>
> This looks like a good addition to [collections] to me.
>
> Any objections to my coding up some tests and adding this class to the
> map package?
>
> Phil
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>
It might be best to use an instance of o.a.c.c.decorators.TransformedMap
with a lower case key transformer and a null value transformer to
implement this class. Even though the posted implementation is simple,
using the decorator removes the need to have the 'plumbing' code
currently present -- and illustrates the use of the collections library.
-Janek
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org