Impl of a list of key/value pairs (and more ?)

[Sébastien de Mapias]

Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:
Object[] obj = struct.get(2)
=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
to make it possible: String[] obj = struct.get(2)).

I found nothing in the standard util API that might help me.
Nobody ever saw something similar somewhere ?

Thanks in advance.
SR

 

[Arved Sandstrom]

Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:
Object[] obj = struct.get(2)
=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
to make it possible: String[] obj = struct.get(2)).

I found nothing in the standard util API that might help me.
Nobody ever saw something similar somewhere ?

Thanks in advance.
SR

This scenario could be satisfied by using a Map, where the keys are your
"abc" or "oiu" strings, and the values are Lists of integers. Write a little
helper function for adding new key-value pairs.

AHS

 

[Donkey Hot]

(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

One can have an array of Objects. Or any other common class.

But a Map could be your friend, as said.

 

[shakah]

(e-mail address removed):

But a Map could be your friend, as said.

Except for the OP's restriction:
"... it may contain duplicates (on either side of the
'pairs')."

 

[Donkey Hot]

Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:
Object[] obj = struct.get(2)
=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
to make it possible: String[] obj = struct.get(2)).

I found nothing in the standard util API that might help me.
Nobody ever saw something similar somewhere ?

Thanks in advance.
SR

public class KeyValuePair
{
private String key ;
private int value ;

public KeyValuePair(String key, int value)
{
this.key = key ;
this.value = value;
}
// getters and setters if needed
}

List struct = new ArrayList();

struct.add(new KeyValuePair("abc", 987);
struct.add(new KeyValuePair("oiu", 567);
struct.add(new KeyValuePair("zye", 124);

KeyValuePair pair = struct.get(2) ;

 

[Donkey Hot]

public class KeyValuePair
{
private String key ;
private int value ;

public KeyValuePair(String key, int value)
{
this.key = key ;
this.value = value;
}
// getters and setters if needed
}

List struct = new ArrayList();

struct.add(new KeyValuePair("abc", 987);
struct.add(new KeyValuePair("oiu", 567);
struct.add(new KeyValuePair("zye", 124);

KeyValuePair pair = struct.get(2) ;

And before someone notices that my code does not compile, I must tell that
it is not Java, but some pseudo code to illustrate the idea

It converts to Java with

List<KeyValuePair> struct = new ArrayList<KeyValuePair>();

 

[Arved Sandstrom]

Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:
Object[] obj = struct.get(2)
=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
to make it possible: String[] obj = struct.get(2)).

I found nothing in the standard util API that might help me.
Nobody ever saw something similar somewhere ?

Thanks in advance.
SR

This scenario could be satisfied by using a Map, where the keys are your
"abc" or "oiu" strings, and the values are Lists of integers. Write a
little helper function for adding new key-value pairs.

You seem to have overlooked the "may contain duplicates"
part of the problem description.

I think my suggestion works. Duplicate keys (e.g. "abc" and "abc") are
handled by having Lists of integers as the values in the first place. Lists
themselves allow duplicate elements.

My first code example does just this:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class ArrayValue {

public static void main(String[] args) {
Map<String, ArrayList<Integer>> test = new HashMap<String,
ArrayList<Integer>>();

insert(test, "abc", 10);
insert(test, "abc", 15);
insert(test, "oiu", -2);
insert(test, "abc", 10);
insert(test, "xyz", 55);
insert(test, "oiu", -2);

System.out.println(test.toString());
}

private static void insert(Map<String, ArrayList<Integer>> m, String
key, Integer value) {
ArrayList<Integer> list = null;
if (m.get(key) == null) {
list = new ArrayList<Integer>();
} else {
list = m.get(key);
}
list.add(value);
m.put(key, list);
}
}

with an output of

{abc=[10, 15, 10], oiu=[-2, -2], xyz=[55]}

This could be finetuned yet further, in case large numbers of duplicate
values (for given keys) are expected, but the core code already satisfies
the requirement.

AHS

 

[Tegiri Nenashi]

Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:
Object[] obj = struct.get(2)
=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
to make it possible: String[] obj = struct.get(2)).

I found nothing in the standard util API that might help me.
Nobody ever saw something similar somewhere ?

Thanks in advance.
SR

Duplicates on value sude is not a problem. For duplicate keys you'll
have to do some hack, like concatenating each key with unique postfix,
which can be for example a generated sequencwe number. Then you do a
range search on keys, to extract the value.

 

[Mark Space]

Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

One can't?

What does "Object [][] struct;" do?

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:

An array like above would work, but Lists are better, as they expand as
needed, and the Collection API is quite versatile. It's kind of a
bummer that Java doesn't have any kind of "Pair" object in the standard
API. But making your own is utterly trivial, which is I'm sure why the
language designers skipped adding one.

See Donkey Hot's List example, it seems to be exactly what you need. I
think folks got confused because your request was so simple. A Map is
overkill if you just need index look-up.

 

[Stefan Ram]

You seem to want a Map that allows duplicate keys.

Duplicate keys are also supported by Junotal:

System.out.println( room( "< a=b a=c >" ).getValues( "a" ));

[b, c]

http://www.purl.org/stefan_ram/pub/junotal_tutorial

Junotal even accepts duplicate values for duplicate keys:

System.out.println( room( "< a=b a=b >" ).getValues( "a" ));



Since the values of a key are deemed to be a set, here the set
of values for the key »"a"« only has one element, even though
it was given twice.

(However, I am not sure whether this is what the OP wanted.)

 

[Stefan Ram]

simultaneously ... Maybe it would be a Good Thing if the O.P.
were to describe the larger problem he wants to solve instead
of the data structure he's dreamed up to solve it with.

Or else, - if he still wants to described the object he's
dreamed up - the best thing would be that he provides

- the interface (including JavaDoc) to be implemented and
- a unit test for this interface.

Then, one could write an implementation against this without
the additional need to interpret an natural language question.

 

[Tom Anderson]

[...]

This scenario could be satisfied by using a Map, where the keys are your
"abc" or "oiu" strings, and the values are Lists of integers. Write a
little helper function for adding new key-value pairs.

You seem to have overlooked the "may contain duplicates"
part of the problem description.

It seems to me that Arved's suggestion to use "Lists of integers" as the
value for each key would address that.

Sets of integers would probably be even better.

Although i think we all misunderstood just what it was the OP wanted.

tom

 

[Arved Sandstrom]

Arved Sandstrom wrote:
Hello,
I'd like to be able to play with the following structure:
struct { ("abc", 987), ("oiu", 567), ("abc", 123), ("zye", 234), ...}
i.e. some kind of 2-dimensional array of keys/values or objects...
(or struct { ("abc", "987"), ("oiu", "567") etc. as one can't have
arrays of data of different types)

As you can see it may contain duplicates (on either side of the
'pairs').

And it would be nice too to retrieve a pair through the means of
an index:
Object[] obj = struct.get(2)
=> obj[0] would be "oiu", while obj[1] would equal 567 (or "567",
to make it possible: String[] obj = struct.get(2)).

I found nothing in the standard util API that might help me.
Nobody ever saw something similar somewhere ?

Thanks in advance.
SR
This scenario could be satisfied by using a Map, where the keys are
your "abc" or "oiu" strings, and the values are Lists of integers.
Write a little helper function for adding new key-value pairs.
You seem to have overlooked the "may contain duplicates"
part of the problem description.

I think my suggestion works. Duplicate keys (e.g. "abc" and "abc") are
handled by having Lists of integers as the values in the first place.
Lists themselves allow duplicate elements.

*I* seem to have overlooked a few things. Sorry for my
over-hasty (mis)reading of your post.

There's still the "access by index" requirement to worry
about, though. LinkedHashMap is all well and good, but I don't
see how it could associate the key "abc" with indices 0 and 2
simultaneously ... Maybe it would be a Good Thing if the O.P.
were to describe the larger problem he wants to solve instead
of the data structure he's dreamed up to solve it with.

I tend to agree. I mean, most of us can figure out one way or another of
creating a "collection" and faking out any access mechanism asked for, but
without a perspective on the original problem what's the point? Is it that
access would be required using both the key (e.g "abc") *and* an index
(presumably by order of addition)? You could do it, but is it the best
solution for the problem?

AHS

 

[Tegiri Nenashi]

I
think folks got confused because your request was so simple.  A Map is
overkill if you just need index look-up.

You do realize that Map, e.g. TreeMap gives you logarithmic access
time?

 

[conrad]

You do realize that Map, e.g. TreeMap gives you logarithmic access
time?

Not true. HashMap gives O(1) access time. You are correct about
TreeMap, but not to generalize that to all Maps.

 

[conrad]

The points others have made about the vagueness of the requirement are
valuable. Based on what we do know, I'd generalize Arved's suggestion
to Map <String, Collection<Integer>>.

 

[Mark Space]

You do realize that Map, e.g. TreeMap gives you logarithmic access
time?

And do you realize that a List, like ArraryList, gives k * O(1) for
lookup, with a very small k value to multiply that? (Unlike HashMap,
where the kO(1) will have a somewhat larger k.)

Inserts into an ArrayList I think are O(n) because the whole list might
need to be copied. OTOH, if the problem allows you to predict the total
array size needed, then insertion into an ArrayList is O(1) also.

I didn't see where the OP asked for ordered retrieval (which is what
TreeMap gives you). Just indexed retrieval.

 

[Tegiri Nenashi]

And do you realize that a List, like ArraryList, gives k * O(1) for
lookup, with a very small k value to multiply that?  (Unlike HashMap,
where the kO(1) will have a somewhat larger k.)

Array is indexed by non-negative integers, and there supposed to be no
gaps (try putting two pairs (1, "a") and (10000000,"b") into an
array). Therefore, "array as a map" works in a very-very narrow
scope.

Inserts into an ArrayList I think are O(n) because the whole list might
need to be copied.  OTOH, if the problem allows you to predict the total
array size needed, then insertion into an ArrayList is O(1) also.

I didn't see where the OP asked for ordered retrieval (which is what
TreeMap gives you).  Just indexed retrieval.

Tree map allows index range scan lookup. Suppose you have two
pairs("a", 10) and ("a", 20) and want to extract both by the key "a".
It is impossible to have these pairs in any kind of map, but one can
store something like ("a1", 10) and ("a2", 20) instead. Then, you
lookup the set of values between "a" and "az"(inclusive), where z is
the last symbol in the ASCII range, or between "a" and "b"(exclusive).
I assume that off-the-shelf classes that were mentioned elsewhere in
the thread shield these details from the user.

 

[Tegiri Nenashi]

Not true.  HashMap gives O(1) access time.  You are correct about
TreeMap, but not to generalize that to all Maps.

I suggest the O notation doesn't really work for HashMap. Consider
HashMap with lookup table size k. Then for an input n < k we indeed
have constant access time. For large input n >> k the access time
becomes linear. And the O notation is an approximation of the
complexity function when input is assumed to grow infinitely large.
Therefore, the HashMap gives you O(n) access time.

Any programmatic solution that includes arbitrary constant doesn't
scale. HashMaps don't scale, while red-black trees do. In database
field, hash indexes are gone forever. I suggest we deprecate HashMaps
as well.

 

[Stefan Ram]

Array is indexed by non-negative integers, and there supposed
to be no gaps (try putting two pairs (1, "a") and
(10000000,"b") into an array).

This holds for the Java language concept of an »array«.

The general term »array« includes sparse arrays.

http://en.wikipedia.org/wiki/Sparse_array

One can see an array as an interface or as an implementation.

A sparse array (interface) might be implemented with a hash
map (implementation).