Solved

data structure design

Posted on 2007-08-06
336 Views
This question is 1/2 design, 1/2 java.

Suppose i have some variables, like this:

stooge (MOE, LARRY, CURLY)
height (TALL, MEDIUM, SHORT)
hair  (BALD, HIRSUTE)
wealth (POOR, AVERAGE, RICH)

This indicates, for example, that the variable stooge can be of value MOE, LARRY or CURLY
(doesn't matter what type of data it is, just any primitive)

I have many many data records which might look like this:

dataRecord:
int i1;
int i2;
boolean b;
String s;
float f;

I would then write some code like so:

if (i1 / i2+ < 100)
stooge = MOE;
else if (i1 / i2 == 100)
stooge = LARRY
else
stooge = CURLY

if (b == true) && (f < 10.0)
height = tall
else (b == true && (f == 10.0)
height = medium
else
height = short

The point is that, with each record I can determine a value for each of stooge, height, hair and wealth.

I need to count the number of occurrences of each possible combinations, e.g. I need to count how many
(MOE, TALL, BALD, POOR) occurences there are.

What is the best way to create a data structure for this?

0
Question by:allelopath

LVL 3

Expert Comment

A loop? Let see you have a stack, queue, tree, graph...
0

LVL 1

Author Comment

My first thought is a multidimensional array
int numberOfOccurences [3][3][2][3]
0

LVL 5

Assisted Solution

A class to describe the stooge. A static method to generate a key based on the attributes and a hash map used to map the key to the count of instances.
0

LVL 1

Author Comment

mkatmonkey:
When you say 'a class to describe the stooge', does Class Stooge contain height, hair and wealth?
0

LVL 5

Expert Comment

That's the idea.
0

LVL 86

Expert Comment

enum Stooge {
MOE,
LARRY,
CURLY
}

etc.

Keep a Set of each variable that you can query
0

LVL 5

Expert Comment

You initial thought would work too, but the problem is two weeks later when stooges can have a dozen new attributes, you'd have a very large multidimensional array for counting the occurrences. Referencing them is error prone.

With the approach I suggested, you could just alter how you generate the key which is less error prone. Other benefits of this approach is just increased flexibility. For example, you can maintain multiple ways of counting and grouping your stooges.
0

LVL 1

Author Comment

CEHJ:
I've never used a Set before. Could you provide a little more detail. I understand the enum part.
0

LVL 92

Accepted Solution

Expanding on what mkatmonkey mentioned earlier you would define a hashCode() and equals() method in your data record class and then stor4e all instances in a Map keyed on the object itself.

public class DataRecord {

public int hashCode() {
....
}

public boolean equals(Object o) {
...
}
...

DataRecord record = new DataRecord(stooge, height, ...

Integer count = map.get(record);
if (count==null) {
// new combo
count = new Integer(0);
}
// incremement counter for this combo
map.put(record, new Integer(count.intValue()+1));
0

LVL 1

Author Comment

objects:
thanks for the response. Something doesn't make sense to me, though.
You say:

DataRecord record = new DataRecord(stooge, height, hair,wealth);

but mkatmonkey suggested a new class (call it Stooge) with stooge, height, hair,wealth that is separate from the data record with members i1, i1, b,s,f. Do you mean, then to do this:

Stooge stooge = new Stooge(stooge, height, hair,wealth);

and have the hashcode() and equals() method in the Stooge class?

I think it is best to keep i1, i2, b,s,f separate from stooge, height, hair,wealth
0

LVL 1

Author Comment

also, I am not clear on what hashCode() and equal() would contain.
0

LVL 92

Expert Comment

> Stooge stooge = new Stooge(stooge, height, hair,wealth);
> and have the hashcode() and equals() method in the Stooge class?

sorry, yes thats what I meant.  Just got the naming mixed up
0

LVL 92

Expert Comment

equals() would return true if all the properties are equal.
See the javadoc for hashCode() contract
http://mindprod.com/jgloss/hashcode.html

0

LVL 1

Author Comment

Also, I don't understand where 'map' is coming from in your example.
Is this java.util.Map interface?
If so is it implemented by Stooge?

Something like this for equals() and hashcode(): --------------

public boolean equals(Object o)
{
if ( o == null )
{
return false;
}
if ( (o.stooge == this.stooge) &&
( o.height == this.height) &&
( o.hair == this.hair) &&
( o.wealth == this.wealth) )
{
return true;
}
else
{
return false;
}

public int hashCode() {
return this.hashCode();
}
0

LVL 92

Expert Comment

> Is this java.util.Map interface?

yes

> If so is it implemented by Stooge?

No, you can use HashMap

Map map = new HashMap();

or using Java 5+

Map<Stooge, Integer> map = new HashMap<Stooge, Integer>();

It maps the number of instances of each stooge type.
0

LVL 1

Author Comment

Ok, bear with me. I getting there.
I now have a class called StoogeHash which has the Map declared as you describe. Using the data records, it determines the values of stooge hair, height, wealth and then creates a new object:

StoogeEntry stoogeEntry = new StoogeEntry( stooge, hair, height, wealth );

Then, as you specify, it increments the count:

// see if this combination is already an entry is hashmap
Integer count = map.get( stoogeEntry );

// if not then we have a new entry, so start with zero count
if ( count == null ) {
// new combination
count = new Integer( 0 );
}

// increment counter for this combination
map.put( stoogeEntry, new Integer( count.intValue() + 1 ) );

The 'elemental' class is called StoogeEntry. It has the members stooge, hair, height, wealth with their getters/setters. It also has these 2 methods:

public int hashCode()
{
result *= stooge.hashCode();
result *= hair.hashCode();
result *= height.hashCode();
result *= wealth.hashCode();

return result;
}

public boolean equals(StoogeEntry stoogeEntry)
{
if ( ( this.getStooge() == stoogeEntry).getStooge() ) && ( this.getHair() == stoogeEntry.getHair() )
&& ( this.getHeight() == stoogeEntry).getHeight() )
&& ( this.getWealth() == stoogeEntry).getWealth() ) ) ) {
return true;
}
else {
return false;
}
}

So after processing all data records, I will have a map with entries for each 'kind' of StoogeEntry.

How do I get the count for a specific combination?
0

LVL 92

Expert Comment

Thats basiocally what u do in the first step.
You create a a StoogeEntry for the combo u require and call the maps get() method to get the count
0

LVL 1

Author Comment

Ok, its working. I'm going to keep this question open for another week or so, in case I come across anything.
0

Featured Post

Suggested Solutions

Problem to setup 18 66
factory design pattern vs abstract factoy design pattern 2 61
array220 challenge 8 29
wordcount challenge 11 46
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectioâ€¦
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to aâ€¦
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define â€¦
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importingâ€¦