how:sorted list with getIndexOf(Object obj)

[DrChaos]

This should be very trivial and is in C++ Ahhh pointers.
but here i am in java.

All i want to do is:
Dynamically add to an array/list, objects (implemented with
Comparable()) and when i add an object that "compares" is equal to
another object in the array it allows access to that object (through
returning the index or reference) so i can modify it, in a way that does
not effect the "Comparable" function result.

so:
I am adding strings dynamically to a list but if the string is already
in there i want to say that the string now has an increased occurrence count

Comparable myObject:
String s
int count

public int compareTo(Object obj){
return s.compareTo(((myObject)obj).s);
}


If the string 's' matches one in the array, increase its count.

Thats it. simple right?

since this list will be added to dynamically, and could get to about
5000 items long I don't want to do something slow like Use a treeSet and
convert to array at every addition to the set and seek the array :S


I have started to look into TreeMap but i have not seen a good
solution yet.

Ideas?

-Jim aka DrChaos.

 

[Eric Sosman]

DrChaos wrote On 10/06/05 13:13,:

This should be very trivial and is in C++ Ahhh pointers.
but here i am in java.

All i want to do is:
Dynamically add to an array/list, objects (implemented with
Comparable()) and when i add an object that "compares" is equal to
another object in the array it allows access to that object (through
returning the index or reference) so i can modify it, in a way that does
not effect the "Comparable" function result.

so:
I am adding strings dynamically to a list but if the string is already
in there i want to say that the string now has an increased occurrence count

Comparable myObject:
String s
int count

public int compareTo(Object obj){
return s.compareTo(((myObject)obj).s);
}


If the string 's' matches one in the array, increase its count.

Thats it. simple right?

since this list will be added to dynamically, and could get to about
5000 items long I don't want to do something slow like Use a treeSet and
convert to array at every addition to the set and seek the array :S

This is probably the root cause of Java's reputation for
slowness: People who do silly things and then blame the language.

I have started to look into TreeMap but i have not seen a good
solution yet.

Ideas?

First idea: It's a good thing you provided an example,
because your problem description verges on the baffling.

Second idea: Is there some special reason you want to
use a collection that's based on compareTo() rather than
on equals()? TreeMap does so, but unless you actually
need "sortedness" a HashMap is probably preferable.

 

[Roedy Green]

All i want to do is:
Dynamically add to an array/list, objects (implemented with
Comparable()) and when i add an object that "compares" is equal to
another object in the array it allows access to that object (through
returning the index or reference) so i can modify it, in a way that does
not effect the "Comparable" function result.

In Java the typical idiom for maintaining the same collection in
several orders is just to have several arrayLists or arrays
or Collections with a list of pointers to the objects. there is no
master collection.


You get your sorts in the first place with Collections.sort and then
an toArray export.

If you want to keep adding elements, you can maintain several
arraylists each using a different comparator. You can then insert an
elt, or tack it on the end and resort. I wrote a class called
SortedArrayList that does lazy sorting to make this easier.

See http://mindprod.com/products1.html#SORTED

 

[DrChaos]

Thanks for your suggestions and comments.
I built, using TreeMap and a comparable item (with a static sorting
switch) an easily sortable via 2 indexes, a dynamic String array, with
counts. I no longer need the index back because my
"indexedStrCompareClass.add(...)" function takes care of the count and
duplicated string issues using the TreeMap. My only other route was to
go with Tables, and as i understand they are very slow in java.

I have not done any performance testing on this yet, but it's
simple,reusable as a basic string counting list and will likely do the job.

The conversion between TreeMap to array should be quick just resetting a
new pointer...

public class treeTerms implements Comparable{
String term;
int count;
static boolean sortOnString;
/** Creates a new instance of treeTerms */
public treeTerms() {
}

public int compareTo(Object obj){
if (sortOnString)
return (term.compareTo(((treeTerms)obj).term));
else{
if (count == ((treeTerms)obj).count)
return 0;
else if (count < ((treeTerms)obj).count)
return 1;
else return -1;
}
}

}

--------------------------------------------

import java.io.*;
import java.util.*;

/**
*
* @author root
*/
public class indexedStrCompareClass {
TreeMap t;

public indexedStrCompareClass(){
t= new TreeMap();
}

public void add(treeTerms tSet){
treeTerms setObj = (treeTerms)t.get(tSet.term);
if (setObj == null)
t.put(tSet.term, tSet);
else
setObj.count +=1;
}
public Object remove(treeTerms tSet){
return t.remove(tSet.term);
}
public Object[] getTermSortedArray(){
TreeSet ts = new TreeSet();
treeTerms.sortOnString = true;
ts.addAll(t.values());
return ts.toArray();
}

public Object[] getCountSortedArray(){
TreeSet ts = new TreeSet();
treeTerms.sortOnString = false;
ts.addAll(t.values());
return ts.toArray();
}
}

 

[DrChaos]

Woops..... something here does not seem right.
In both " public Object[] getCountSortedArray()" and
"...getTermSortedArray()"

ts.addAll(t.values());
return ts.toArray();

Are not working... more research into TreeMap i guess...

Thanks for your suggestions and comments.
I built, using TreeMap and a comparable item (with a static sorting
switch) an easily sortable via 2 indexes, a dynamic String array, with
counts. I no longer need the index back because my
"indexedStrCompareClass.add(...)" function takes care of the count and
duplicated string issues using the TreeMap. My only other route was to
go with Tables, and as i understand they are very slow in java.

I have not done any performance testing on this yet, but it's
simple,reusable as a basic string counting list and will likely do the job.

The conversion between TreeMap to array should be quick just resetting a
new pointer...

public class treeTerms implements Comparable{
String term;
int count;
static boolean sortOnString;
/** Creates a new instance of treeTerms */
public treeTerms() {
}

public int compareTo(Object obj){
if (sortOnString)
return (term.compareTo(((treeTerms)obj).term));
else{
if (count == ((treeTerms)obj).count)
return 0;
else if (count < ((treeTerms)obj).count)
return 1;
else return -1;
}
}

}

--------------------------------------------

import java.io.*;
import java.util.*;

/**
*
* @author root
*/
public class indexedStrCompareClass {
TreeMap t;

public indexedStrCompareClass(){
t= new TreeMap();
}

public void add(treeTerms tSet){
treeTerms setObj = (treeTerms)t.get(tSet.term);
if (setObj == null)
t.put(tSet.term, tSet);
else
setObj.count +=1;
}
public Object remove(treeTerms tSet){
return t.remove(tSet.term);
}
public Object[] getTermSortedArray(){
TreeSet ts = new TreeSet();
treeTerms.sortOnString = true;
ts.addAll(t.values());
return ts.toArray();
}

public Object[] getCountSortedArray(){
TreeSet ts = new TreeSet();
treeTerms.sortOnString = false;
ts.addAll(t.values());
return ts.toArray();
}
}


----------------------------

This should be very trivial and is in C++ Ahhh pointers.
but here i am in java.

All i want to do is:
Dynamically add to an array/list, objects (implemented with
Comparable()) and when i add an object that "compares" is equal to
another object in the array it allows access to that object (through
returning the index or reference) so i can modify it, in a way that
does not effect the "Comparable" function result.

so:
I am adding strings dynamically to a list but if the string is already
in there i want to say that the string now has an increased occurrence
count

Comparable myObject:
String s
int count

public int compareTo(Object obj){
return s.compareTo(((myObject)obj).s);
}


If the string 's' matches one in the array, increase its count.

Thats it. simple right?

since this list will be added to dynamically, and could get to about
5000 items long I don't want to do something slow like Use a treeSet
and convert to array at every addition to the set and seek the array :S


I have started to look into TreeMap but i have not seen a good
solution yet.

Ideas?

-Jim aka DrChaos.

 

[John C. Bollinger]

I built, using TreeMap and a comparable item (with a static sorting
switch)

Ow. That's very broken. It means that you can never rely on the result
of a natural-order comparison past the point of its evaluation, for the
very next thing that happens could be toggling the switch. Moreover,
toggling the switch affects all instances, everywhere, which is unlikely
to be what you want (no matter how much you may think it is). Among
other things, flipping the switch will likely cause any existing TreeMap
or TreeSet of these objects to instantly fail, as the contents are
suddenly and horribly jumbled.

The correct way to implement multiple distinct orderings is to use
different Comparators for the different orders, or one natural order and
Comparators for the other orders.

an easily sortable via 2 indexes, a dynamic String array

Please use a different term than "array", as "array" has a specific
meaning in Java (and in most other computer languages) that is different
from what you are describing. Calling your thing an "array" really
muddies the waters.

, with
counts. I no longer need the index back because my
"indexedStrCompareClass.add(...)" function takes care of the count and
duplicated string issues using the TreeMap. My only other route was to
go with Tables, and as i understand they are very slow in java.

What in the world are you talking about? Regarding "Tables", that is?
I have no clue what you're talking about, but you are probably misinformed.

I have not done any performance testing on this yet, but it's
simple,reusable as a basic string counting list and will likely do the job.

The conversion between TreeMap to array should be quick just resetting a
new pointer...

public class treeTerms implements Comparable{
String term;
int count;
static boolean sortOnString;
/** Creates a new instance of treeTerms */
public treeTerms() {
}

public int compareTo(Object obj){
if (sortOnString)
return (term.compareTo(((treeTerms)obj).term));
else{
if (count == ((treeTerms)obj).count)
return 0;
else if (count < ((treeTerms)obj).count)
return 1;
else return -1;
}
}

As I wrote above, do not implement your natural order in this switchable
way -- unless you really mean it when you call yourself Dr*Chaos*.

}

--------------------------------------------

import java.io.*;
import java.util.*;

/**
*
* @author root

Naughty you. You shouldn't be logging in as root for non-administrative
purposes. Certainly not for developing software.

*/
public class indexedStrCompareClass {
TreeMap t;

public indexedStrCompareClass(){
t= new TreeMap();
}

public void add(treeTerms tSet){
treeTerms setObj = (treeTerms)t.get(tSet.term);
if (setObj == null)
t.put(tSet.term, tSet);
else
setObj.count +=1;
}
public Object remove(treeTerms tSet){
return t.remove(tSet.term);
}

This remove() method is probably not what you want. I would have
expected you to decrement the count if it was greater than one, and only
remove the treeTerms when the count reached zero. Otherwise, remove()
is not symmetric with add().

public Object[] getTermSortedArray(){
TreeSet ts = new TreeSet();
treeTerms.sortOnString = true;

Instead of flipping the switch here you ought to supply a suitable
Comparator to your TreeSet.

ts.addAll(t.values());
return ts.toArray();
}

public Object[] getCountSortedArray(){
TreeSet ts = new TreeSet();
treeTerms.sortOnString = false;

As above, instead of flipping the switch here you ought to supply a
suitable Comparator to your TreeSet.

ts.addAll(t.values());
return ts.toArray();
}

Why not output treeTerms[] instances instead of Object[]? Your class
only works with treeTerms objects, so there is no loss of generality,
and you gain some specificity.

So why are you using a TreeMap for your main storage, then? You are not
relying on entries being maintained in order, so you are not getting any
benefit from it. HashMap is a better general-purpose choice.

}

Also note: it is widespread Java convention to name classes and
interfaces with an initial capital letter. We will have a slightly
easier time reading your code if you conform to this convention.

 

[Roedy Green]

My only other route was to
go with Tables, and as i understand they are very slow in java.

Tables are for displaying data not storing it. They use a DataModel
which you create yourself with any logical structure you want, in the
simplest case with an Array.

 

[Roedy Green]

public int compareTo(Object obj){
if (sortOnString)
return (term.compareTo(((treeTerms)obj).term));
else{
if (count == ((treeTerms)obj).count)
return 0;
else if (count < ((treeTerms)obj).count)
return 1;
else return -1;
}

Read the contract for compareTo. I am pretty sure that is illegal. You
must give the same result every time All manner of code trusts
compareTo to behave transitively .

The idiom is when you create a collection, you feed it a Comparator --
the official ordering for this Collection. If you want a second
ordering you feed the collection as a whole to a second collection
with a different Comparator. There is one set of objects, two
collections. From then on you can add and delete keeping them in sync
or not as you please.

When to sort and when to use a SortedSet or SortedMap? If all you
want to do is sort the collection once then just put your elts into an
ArrayList and sort. If you want to MAINTAIN a sorted list adding and
deleting elements, then usually a TreeMap is faster than resorting.

Sorts are very fast compared with tree structures. So if you only need
the elements in order every once in a while for some batch process, it
is usually much easier, faster and ram-effective to spin off an array
and sort it rather than maintaining a sorted collection.

 

[DrChaos]

Read the contract for compareTo. I am pretty sure that is illegal. You
must give the same result every time All manner of code trusts
compareTo to behave transitively .

The idiom is when you create a collection, you feed it a Comparator --
the official ordering for this Collection. If you want a second
ordering you feed the collection as a whole to a second collection
with a different Comparator. There is one set of objects, two
collections. From then on you can add and delete keeping them in sync
or not as you please.

When to sort and when to use a SortedSet or SortedMap? If all you
want to do is sort the collection once then just put your elts into an
ArrayList and sort. If you want to MAINTAIN a sorted list adding and
deleting elements, then usually a TreeMap is faster than resorting.

Sorts are very fast compared with tree structures. So if you only need
the elements in order every once in a while for some batch process, it
is usually much easier, faster and ram-effective to spin off an array
and sort it rather than maintaining a sorted collection.

When i mentioned "Tables" i meant use a tabled approach via database
driver etc.....

fixed,
thanks for the tips, i'm new to java (can you guess?)
i changed the compare to function and got rid of the switch. all better
now.

public int compareTo(Object obj){
int dd = term.compareTo( ((TreeTerms)obj).term);
if (dd == 0){
return 0;
}
else if (count == ((TreeTerms)obj).count)
return term.compareTo(((TreeTerms)obj).term);
else if (count < ((TreeTerms)obj).count)
return 1;
else return -1;
}