Sorting Objects in an ArrayList

[lalalala]

Hi,
I am working on my inventory program and I have almost completed,
although when I am displaying the summary of my inventory data table,
which is ordered in colums
barcode/Style/Colour/Size. I fetch and store all the data in access,
but now i wanted to group everything by Style, in alphabetical order,
then group colours in a certain Style together, not necessarely in
alphabetical order, then order each style of specefic colour by Size (S
M L XL).
I recall there being an algorithm that could help me sort something
like that from an ArrayList, without having to make a unique algortihm
for the task from scratch.
This is the algorithm I have and "a" is an ArrayList.

for (int i =0;i<a.size();i++){
temp = (String)a.get ;
style = db.getStyle(temp);
size = db.getSize(temp);
colour = db.getColour(temp);

System.out.println((i+1)+".
"+temp+"\t\t"+style+"\t"+colour+"\t"+size);
}

Again Thank you for any help in advance, it is greatly appreciated.
Nadav

 

[Robert Klemme]

Hi,
I am working on my inventory program and I have almost completed,
although when I am displaying the summary of my inventory data table,
which is ordered in colums
barcode/Style/Colour/Size. I fetch and store all the data in access,
but now i wanted to group everything by Style, in alphabetical order,
then group colours in a certain Style together, not necessarely in
alphabetical order, then order each style of specefic colour by Size (S
M L XL).
I recall there being an algorithm that could help me sort something
like that from an ArrayList, without having to make a unique algortihm
for the task from scratch.

You can implement a Comparator and throw the stuff into a TreeSet if you
do not have duplicates. If you do have, then you can still use the
TreeSet by having your Comparator never return 0 for non identical
elements. Alternatively you can use a TreeMap and use instances of some
other collection as values.

Kind regards

robert

 

[lalalala]

Thank you Robert.
I am reading the Comparator method now on java documentation. Although
I have never encountered it. I'm storing all my inventory into an
access database and i'm thinking perhaps this method is a bit to long.
Basically every Style has a specefic colour and size, could't ring up
and order all styles in my table, then once styles are grouped
together, how could i organize the colours, within the styles, and then
the sizes in (s m l xl).
Here's an example

My access datatable is like this, with things in disorder:

Style-----colour-----size

c green s
a yellow m
c blue m
c green m
c blue s
a purple m
a purple s
a yellow s

and i want to reorganize that so it comes up like so:

Style-----colour-----size

c blue s
c blue m
c green s
c green m
a purple s
a purple m
a yellow s
a yellow m

Any ideas on a simple method to organize it, i remember performing a
similar task in school.
Any help is greately appreciated.
Nadav

 

[Oliver Wong]

Thank you Robert.
I am reading the Comparator method now on java documentation. Although
I have never encountered it. I'm storing all my inventory into an
access database and i'm thinking perhaps this method is a bit to long.
Basically every Style has a specefic colour and size, could't ring up
and order all styles in my table, then once styles are grouped
together, how could i organize the colours, within the styles, and then
the sizes in (s m l xl).

Are you using SQL statements to query your Access DB? If so, perhaps you
can use the "ORDER BY" clause to order your results.

- Oliver

 

[jhr]

Think about encapsulating your values with an object. I.E.
StyleInfo {
private char style;
private String colour;
private char size;
}

if your array list is defined as such: ArrayList<StyleInfo> styleList

then use the method, Collections.sort(styleList, sytleComparator)

where styleComparator looks something like:

StyleComparator implements Comparator<Style> {
public in compare(Style s1, Style s2)
{
compare style char
if they are equal compare colour
if colour is equal compare size
}
}

 

[lalalala]

Thank you all you guys are great, that is exactly what i did.
Nadav

 

[Dale King]

You can implement a Comparator and throw the stuff into a TreeSet if you
do not have duplicates. If you do have, then you can still use the
TreeSet by having your Comparator never return 0 for non identical
elements.

Note that only works if you don't want multiple copies of identical
elements. Imagine if you want 2 items in the collection that are not the
same object that have all the same data. There is no valid way to allow
that with any comparator.

In general there is no equivalent to TreeSet for Lists.

 

[Oliver Wong]

Note that only works if you don't want multiple copies of identical
elements. Imagine if you want 2 items in the collection that are not the
same object that have all the same data. There is no valid way to allow
that with any comparator.

In general there is no equivalent to TreeSet for Lists.

If you DON'T want two objects with identical data in the treeset, then
have the comparator return 0 at the appropriate times.

If you DO want two objects with identical data in the treeset, perhaps
you could use System.identityHashCode(Object) as the final criteria to
compare against whenever you would normally return 0. I'm not sure if the
semantics of identityHashCode are well defined enough to ensure that two
distinct objects will *lways* result in two different identityHashCodes
though. In a "typical implementation", I imagine they would (the method
would just return the "address in memory" of the object, though this might
fail on 64 bit architectures), but perhaps there is no requirement of this.
I.e. perhaps an implementation is free to always return 0 on
identityHashCode.

- Oliver

 

[Robert Klemme]

If you DON'T want two objects with identical data in the treeset,
then have the comparator return 0 at the appropriate times.

If you DO want two objects with identical data in the treeset,
perhaps you could use System.identityHashCode(Object) as the final
criteria to compare against whenever you would normally return 0. I'm
not sure if the semantics of identityHashCode are well defined enough to
ensure that two distinct objects will *lways* result in two different
identityHashCodes though. In a "typical implementation", I imagine they
would (the method would just return the "address in memory" of the
object, though this might fail on 64 bit architectures), but perhaps
there is no requirement of this. I.e. perhaps an implementation is free
to always return 0 on identityHashCode.

That's exactly what I meant. Either identityHashCode() or something
else can be used to distinguish non identical but equivalent elements.
Even random() or System.currentTimeMillis() work.

package util;

import java.util.Comparator;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeSet;

public class Duplicates {

public static void main( String[] args ) {
// silly test with strings
SortedSet s = new TreeSet( new Comparator() {
public int compare( Object o1, Object o2 ) {
String s1 = ( String ) o1;
String s2 = ( String ) o2;
int c = s1.compareTo( s2 );
return c == 0 ? System.identityHashCode( s1 ) -
System.identityHashCode( s2 ) : c;
// return c == 0 ? new Random().nextInt() : c;
}
} );

// use new to create different objects
s.add( "foo" );
s.add( "bar" );
s.add( new String( "foo" ) );
s.add( new String( "foo" ) );
s.add( new String( "foo" ) );
s.add( new String( "foo" ) );

System.out.println( s );
}
}


=> [bar, foo, foo, foo, foo, foo]


Kind regards

robert

 

[Oliver Wong]

That's exactly what I meant. Either identityHashCode() or something else
can be used to distinguish non identical but equivalent elements. Even
random() or System.currentTimeMillis() work.

Random and currentTime probably won't satisfy the contract:

<quote>
The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for
all x and y. (This implies that x.compareTo(y) must throw an exception iff
y.compareTo(x) throws an exception.)

The implementor must also ensure that the relation is transitive:
(x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.

Finally, the implementer must ensure that x.compareTo(y)==0 implies that
sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.
</quote>

- Oliver

 

[Patricia Shanahan]

Oliver Wong wrote: ....


That's exactly what I meant. Either identityHashCode() or something
else can be used to distinguish non identical but equivalent elements.
Even random() or System.currentTimeMillis() work.

But does use of random() or System.currentTimeMillis conform to the
Comparator contract?

The Comparator documentation calls for a total order on the objects it
compares. Making random choices could lead to compare(a,b) returning
different answers for the same pair of objects. It could also cause
compare(a,b) and compare(b,c) to both be positive, but compare(a,c) to
be negative.

return c == 0 ? System.identityHashCode( s1 ) -
System.identityHashCode( s2 ) : c;

The use of subtraction here, rather than comparison, can also give
inconsistent results. It is possible to have three integers a, b, and c
such that a-b and b-c are both positive, but a-c is negative due to
overflow.

Patricia

 

[Robert Klemme]

Robert Klemme wrote:

But does use of random() or System.currentTimeMillis conform to the
Comparator contract?

Yeah, probably not. It might still work. This was just a quick hack so
I didn't bother to go too far into details.

The Comparator documentation calls for a total order on the objects it
compares. Making random choices could lead to compare(a,b) returning
different answers for the same pair of objects. It could also cause
compare(a,b) and compare(b,c) to both be positive, but compare(a,c) to
be negative.



The use of subtraction here, rather than comparison, can also give
inconsistent results. It is possible to have three integers a, b, and c
such that a-b and b-c are both positive, but a-c is negative due to
overflow.

return c == 0 ? Math.abs( System.identityHashCode( s1 ) ) -
Math.abs( System.identityHashCode( s2 ) ) : c;

Better?

Kind regards

robert

 

[Thomas Hawtin]

If you DO want two objects with identical data in the treeset,
perhaps you could use System.identityHashCode(Object) as the final
criteria to compare against whenever you would normally return 0. I'm
not sure if the semantics of identityHashCode are well defined enough to
ensure that two distinct objects will *lways* result in two different
identityHashCodes though. In a "typical implementation", I imagine they
would (the method would just return the "address in memory" of the
object, though this might fail on 64 bit architectures), but perhaps
there is no requirement of this. I.e. perhaps an implementation is free
to always return 0 on identityHashCode.

Absolutely not.

On a typical, 32-bit implementation it is easy to find two objects with
the same identityHashCode at the same time. I can't see a particularly
feasible way of ensuring uniqueness.

What I suppose you could do, if you compare two objects with the same
identityHashMap is to keep a note, with WeakReferences, as to which you
decided should come first. Use, say, a
ConcurrentMap<Integer,List<WeakReference<Object>>>.

import java.util.List;
import java.lang.ref.WeakReference;

class ArbitraryComparator
implements java.util.Comparator<Object>
{
public static final java.util.Comparator<Object> INSTANCE =
new ArbitraryComparator();

private static final
java.util.concurrent.ConcurrentMap<

tie = new java.util.concurrent.ConcurrentHashMap<

();

private ArbitraryComparator() {
}
public int compare(Object a, Object b) {
// Check if really are identical.
if (a == b) {
return 0;
}

// Try hash code.
int aHash = System.identityHashCode(a);
int bHash = System.identityHashCode(b);
if (aHash < bHash) {
return -1;
}
if (aHash > bHash) {
return 1;
}

// Last resort - find or make an arbitrary decision.
Integer hash = aHash;
List<WeakReference<Object>> list = tie.get(hash);
if (list == null) {
List<WeakReference<Object>> newList =
new java.util.ArrayList<WeakReference<Object>>();
List<WeakReference<Object>> oldList =
tie.putIfAbsent(hash, newList);
list = oldList==null ? newList : oldList;
}
synchronized (list) {
// Clean list.
for (
java.util.Iterator<WeakReference<Object>> iter =
list.iterator();
iter.hasNext();
) {
WeakReference<Object> ref = iter.next();
if (ref.get() == null) {
iter.remove();
}
}
// Compare on arbitrary index.
int aIndex = index(list, a);
int bIndex = index(list, b);
assert aIndex != bIndex;
return aIndex<bIndex ? -1 : 1;
}
}
// Finds index of object in list, adding to list if necessary.
private static int index(
List<WeakReference<Object>> list, Object obj
) {
int num = list.size();
for (int ct=0; ct<num; ++ct) {
if (list.get(ct) == obj) {
// Found.
return ct;
}
}
// Not found
list.add(new WeakReference<Object>(obj));
return num;
}
}

Disclaimer: Not tested in any way.

Tom Hawtin

 

[Thomas Hawtin]

if (list.get(ct) == obj) {

.get()

Tom Hawtin

 

[Patricia Shanahan]

return c == 0 ? Math.abs( System.identityHashCode( s1 ) ) -
Math.abs( System.identityHashCode( s2 ) ) : c;

Better?

....

Yes and no. The difference of two int absolute values is in the range
[-Integer.MAX_VALUE,Integer.MAX_VALUE], which avoids any overflow
issues. However, it is possible that the absolute values of two distinct
objects' identityHashCode results are equal, especially if the heap is
bigger than 2GB.

This all seems to me to be a bit contorted, because it is trying to
stretch Set to deal with duplicates. The Set interface is designed to
model the mathematical concept of set, which does not allow duplicates.

I would either make sure that distinct objects of the class really do
differ, for example by including a creation order field, or I would
avoid putting them in Sets. The List interface, and implementations such
as ArrayList, are designed to deal with distinct but equal objects.

Patricia

 

[Eric Sosman]

Robert Klemme wrote On 06/02/06 10:26,:

[...]
That's exactly what I meant. Either identityHashCode() or something
else can be used to distinguish non identical but equivalent elements.
Even random() or System.currentTimeMillis() work.

identityHashCode() may work, but using a random number
or the current time or anything else that doesn't lead to a
consistent ordering is unreliable.

The JavaDoc for Comparator specifies a contract that
compare() must fulfill. Among other things, compare() must
define a "total order," which is

- reflexive: compare(x,x) must be zero (unless it
throws an exception)

- anticommutative: compare(x,y) and compare(y,x) must
give "opposite" results (or must both throw exceptions)

- transitive: if compare(x,y)<0 and compare(y,z)<0,
then compare(x,z) must be <0. (And similar rules
for ==0 and >0.)

A "comparison" that's really just a random number cannot
assuredly satisfy these requirements. If you try to sort
a List or array or TreeSet with a Comparator that doesn't
fulfill its contract, the results are unpredictable.

 

[Robert Klemme]

Better?

...

Yes and no. The difference of two int absolute values is in the range
[-Integer.MAX_VALUE,Integer.MAX_VALUE], which avoids any overflow
issues. However, it is possible that the absolute values of two distinct
objects' identityHashCode results are equal, especially if the heap is
bigger than 2GB.

This all seems to me to be a bit contorted, because it is trying to
stretch Set to deal with duplicates. The Set interface is designed to
model the mathematical concept of set, which does not allow duplicates.

I would either make sure that distinct objects of the class really do
differ, for example by including a creation order field, or I would
avoid putting them in Sets. The List interface, and implementations such
as ArrayList, are designed to deal with distinct but equal objects.

Right. The whole thread seems to have gotten a bit out of proportion.
Initially I offered the other alternative (TreeMap with some Collection
as values) which is certainly preferable in terms of robustness. I just
got carried away be my curiousness how far the Comparator can be
stretched.

Last but not least there is another option: there are also various
sort() methods in class Arrays that do not remove duplicates.

Kind regards

robert

 

[Dale King]

If you DON'T want two objects with identical data in the treeset,
then have the comparator return 0 at the appropriate times.

Which does not satisfy the "in general" part of my statement.

If you DO want two objects with identical data in the treeset,
perhaps you could use System.identityHashCode(Object) as the final
criteria to compare against whenever you would normally return 0. I'm
not sure if the semantics of identityHashCode are well defined enough to
ensure that two distinct objects will *lways* result in two different
identityHashCodes though.

Nope it is not guaranteed at all.

In a "typical implementation", I imagine they
would (the method would just return the "address in memory" of the
object, though this might fail on 64 bit architectures), but perhaps
there is no requirement of this. I.e. perhaps an implementation is free
to always return 0 on identityHashCode.

As I remember it really isn't just the address. As I remember they
permute it a little bit as a minor security tweak so that you don't know
the location in memory. As I recall it was like they computed a random
value at the startup of the VM that was used to permute the identity
hash. But I could be remembering totally wrong.

I've had this discussion several times before and in general there is no
way to accomplish a sorted implementation of List using TreeSet.
Actually you need a different abstraction than List because List assumes
you can insert items where you want. Bag is probably the more correct
and widely used term. A bag could be a super interface of List.

By "in general", I mean that:
- It allows multiple copies of objects that have the same contents to be
inserted and guarantees that they sorted in a stable fashion (they don't
suddenly change order).
- It allows multiple instances of the same object to be inserted.
- It works on all VMs and all platforms.
- The contract of Comparator is not violated.

It is possible to satisfy some subset of that using TreeSet and
Comparator, but not all of it.