a question for sorting keys in Map

W

www

Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g:
VARIABLE0, VARIABLE1, VARIABLE2, etc.

If the total number of entries < 10, then the sorted order is ok:

VARIABLE0
VARIABLE1
VARIABLE2


But, if the total number of entries > 10, the sorted order is not what I
want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
...
VARIABLE2
VARIABLE20
VARIABLE21
...
VARIABLE3
VARIABLE30
VARIABLE31
...

I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
...
VARIABLE9
VARIABLE10
VARIABLE11
....

Can you help me to achieve this? Thank you very much.
 
P

Patricia Shanahan

www said:
Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g: ....
I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
..
VARIABLE9
VARIABLE10
VARIABLE11
...

Can you help me to achieve this? Thank you very much.
Click to expand...

Write a class, possibly an anonymous inner class, that implements
Comparator<String> and whose compare method returns the order you want.
Pass an instance of your Comparator to the appropriate TreeMap constructor.

An alternative approach would be to wrap your TreeMap in a Map class you
write. On insertion, change the key to remove the "VARIABLE" part of the
string, and convert the remainder to an Integer. The order you want is
the natural sort order for Integer. When returning keys as results,
concatenate with "VARIABLE" to recover the original key.

Patricia
 
C

Curt Welch

www said:
Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g:
VARIABLE0, VARIABLE1, VARIABLE2, etc.

If the total number of entries < 10, then the sorted order is ok:

VARIABLE0
VARIABLE1
VARIABLE2

But, if the total number of entries > 10, the sorted order is not what I
want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
..
VARIABLE2
VARIABLE20
VARIABLE21
..
VARIABLE3
VARIABLE30
VARIABLE31
..

I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
..
VARIABLE9
VARIABLE10
VARIABLE11
...

Can you help me to achieve this? Thank you very much.
Click to expand...

I don't know of any simple Java built in function to help you. You have to
write some code to do that.

You have a few options on how to do that.

You can write your own Comparator object which implements the Compare
function for Strings, and then write the code yourself to compare two
strings so that X10 comes after X2 instead of before it. When you create
your TreeMap you pass your Comparator object in the constructor so it will
use your logic for sorting the entries.

I wrote one of these back in the 70's (in C of course not Java) to make the
Unix ls command sort file names the way you want your strings to sort. It
broke the names into logical sets of letters and numbers, and then sorted
the letter substrings using normal dictionary sort and sorted the number
substrings using numeric sort.

The other option to change the sort order is to create a new object for the
keys instead of using strings. If every one of your keys follows the
specific format you mention above (name + number), this approach can work
well. Create the key object which keeps the name and number as separate
instance variables. Create a toString() method which produces the string
version of the key. Create a compare method that does the type of compare
of two of these objects like you want. That is, compare the strings, and
if they are equal, compare the numbers.

Oh, what the hey, here's the code for the custom key solution:

import java.util.Map;
import java.util.TreeMap;
import java.util.Random;

public class SortKey
{
public static void main(String args[])
{
Map<MyKey,Integer> m = new TreeMap<MyKey,Integer>();

Random rand = new Random();

m.put(new MyKey("A", 1), rand.nextInt(99));
m.put(new MyKey("A", 10), rand.nextInt(99));
m.put(new MyKey("B", 1), rand.nextInt(99));
m.put(new MyKey("B", 10), rand.nextInt(99));
m.put(new MyKey("B", 2), rand.nextInt(99));
m.put(new MyKey("B", 20), rand.nextInt(99));
m.put(new MyKey("B", 3), rand.nextInt(99));
m.put(new MyKey("B", 30), rand.nextInt(99));

System.out.println("Map is: " + m);
}
}

class MyKey implements Comparable<MyKey>
{
String var;
int num;

MyKey(String v, int n)
{
var = v;
num = n;
}

public String getVar()
{
return var;
}

public int getNum()
{
return num;
}

public String toString()
{
return String.format("%s%d", var, num);
}

public int compareTo(MyKey k)
{
int r = getVar().compareTo(k.getVar());

if (r == 0)
return ((Integer)getNum()).compareTo(k.getNum());

return r;
}
}

Which produces the output:

Map is: {A1=82, A10=86, B1=86, B2=24, B3=7, B10=18, B20=81, B30=86}
 
Y

ynseo

Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g:
VARIABLE0, VARIABLE1, VARIABLE2, etc.

If the total number of entries < 10, then the sorted order is ok:

VARIABLE0
VARIABLE1
VARIABLE2

But, if the total number of entries > 10, the sorted order is not what I
want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
..
VARIABLE2
VARIABLE20
VARIABLE21
..
VARIABLE3
VARIABLE30
VARIABLE31
..

I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
..
VARIABLE9
VARIABLE10
VARIABLE11
...

Can you help me to achieve this? Thank you very much.
Click to expand...

A possible way is to make each string value end with a double-digit
figure ; VARIABLE8 => VARIABLE08( or VARIABLE008 ).

Another one is to implement java.util.Comparator specific to your
value strings and create TreeMap instance with it.

I think the first way is easier :)
 
M

Matt Humphrey

www said:
Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g: VARIABLE0,
VARIABLE1, VARIABLE2, etc.

If the total number of entries < 10, then the sorted order is ok:

VARIABLE0
VARIABLE1
VARIABLE2


But, if the total number of entries > 10, the sorted order is not what I
want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
Click to expand...

Yes, this is this natural order for strings. You might try to change the
keys to be more nicely formatted (e.g. VARIABLE0001 vs. VARIABLE1).
Alternatively, you could replace the string with a more meaningful object,
as in
class VariableId extends Comparable <VariableId> {
String name; int id
public boolean equals (Object o1) {
// override equals to return true when both match
}
public int hashcode () { // compute hashcode based on name and id }
public int compareTo (VariableId x) {
// Compare it to itself--you set the natural order
}
}

But if you can't do those you can always supply the TreeMap with a custom
Comparator that sets the sort order.

new Comparator () <String> {
public int compare (String s1, String s2) {
// Parse the two strings to separate the variable from the suffix
digits
// compare the string portions. If not zero, answer that
// otherwise compare the numeric portions. If not zero answer that
// otherwise nswer zero--they're the same
}
}

This comparator is inefficient, however, because it parses both keys all
over again on every comparison. I haven't validated this code--it's just to
explain the concepts.

Matt Humphrey http://www.iviz.com/
 
D

Daniel Pitts

www said:
Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g:
VARIABLE0, VARIABLE1, VARIABLE2, etc.

If the total number of entries < 10, then the sorted order is ok:

VARIABLE0
VARIABLE1
VARIABLE2


But, if the total number of entries > 10, the sorted order is not what I
want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
...
VARIABLE2
VARIABLE20
VARIABLE21
...
VARIABLE3
VARIABLE30
VARIABLE31
...

I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
...
VARIABLE9
VARIABLE10
VARIABLE11
....

Can you help me to achieve this? Thank you very much.
Click to expand...
I suggest not using a map of Strings in this case:

SortedMap<Integer, Something>;

Or, using a List
List<Something>

If you absolutely must using Strings, then tell me this:
Which order would these strings be in? A1B10, B2A9

Regardless of your answer there, you'll need to write a
Comparator<String> implementation that will give the correct ordering.

Hope this helps,
Daniel.
 
C

Curt Welch

www said:
Hi,

I have a Map, actually a TreeMap, which will automatically sort the keys
alphabetically. The keys are Strings, like "VARIABLE" + i, e.g:
VARIABLE0, VARIABLE1, VARIABLE2, etc.

If the total number of entries < 10, then the sorted order is ok:

VARIABLE0
VARIABLE1
VARIABLE2

But, if the total number of entries > 10, the sorted order is not what I
want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
..
VARIABLE2
VARIABLE20
VARIABLE21
..
VARIABLE3
VARIABLE30
VARIABLE31
..

I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
..
VARIABLE9
VARIABLE10
VARIABLE11
...

Can you help me to achieve this? Thank you very much.
Click to expand...

Thanks for exercise. Here's some code I wrote as examples of how to do it.

import java.util.Map;
import java.util.TreeMap;
import java.util.Random;
import java.util.Comparator;
import java.util.Arrays;

public class SortKey
{
public static void main(String args[])
{
comparatorSolution();
}

static void comparatorSolution()
{
Map<String,Integer> m = new TreeMap<String,Integer>(new
VarNameSorter());

Random rand = new Random();

m.put("", rand.nextInt(99));
m.put("1", rand.nextInt(99));
m.put("2", rand.nextInt(99));
m.put("10", rand.nextInt(99));
m.put("20", rand.nextInt(99));
m.put("A", rand.nextInt(99));
m.put("B", rand.nextInt(99));
m.put("A1", rand.nextInt(99));
m.put("A10", rand.nextInt(99));
m.put("A2", rand.nextInt(99));
m.put("A20", rand.nextInt(99));
m.put("A1.1", rand.nextInt(99));
m.put("A1.2", rand.nextInt(99));
m.put("A1.10", rand.nextInt(99));
m.put("A1X", rand.nextInt(99));
m.put("A1Y", rand.nextInt(99));

System.out.println("Map is:");

for (String var : m.keySet())
System.out.printf("\"%s\"=%d\n", var, m.get(var));
}

static void myKeySolution()
{
Map<MyKey,Integer> m = new TreeMap<MyKey,Integer>();

Random rand = new Random();

m.put(new MyKey("A", 1), rand.nextInt(99));
m.put(new MyKey("A", 10), rand.nextInt(99));
m.put(new MyKey("B", 1), rand.nextInt(99));
m.put(new MyKey("B", 10), rand.nextInt(99));
m.put(new MyKey("B", 2), rand.nextInt(99));
m.put(new MyKey("B", 20), rand.nextInt(99));
m.put(new MyKey("B", 3), rand.nextInt(99));
m.put(new MyKey("B", 30), rand.nextInt(99));

System.out.println("Map is: " + m);
}
}

class MyKey implements Comparable<MyKey>
{
String var;
int num;

MyKey(String v, int n)
{
var = v;
num = n;
}

public String getVar()
{
return var;
}

public int getNum()
{
return num;
}

public String toString()
{
return String.format("%s%d", var, num);
}

public int compareTo(MyKey k)
{
int r = getVar().compareTo(k.getVar());

if (r == 0)
return ((Integer)getNum()).compareTo(k.getNum());

return r;
}
}

/**
* Sort variable names with mixed strings and numbers.
*
* Curt Welch <[email protected]>
* 11-20-2007
*/

class VarNameSorter implements Comparator<String>
{
public int compare(String v1, String v2)
{
// Split var names into digit and non digit substrings

String[] v1a = splitVarName(v1);
String[] v2a = splitVarName(v2);

for (int i = 0; i < v1a.length; i++) {
if (i >= v2a.length)
return +1; // v2 is shorter - it comes first
int r = compareChunk(v1a, v2a);
if (r != 0)
return r;
}

if (v1a.length < v2a.length)
return -1; // v1 is shorter - it comes first

return 0; // they are the same
}

// split into digit and non digit substrings

private String[] splitVarName(String name)
{
String[] a = new String[0];

for (int i = 0; i < name.length();) {
int start = i;
boolean isDigit = Character.isDigit(name.charAt(i));
while (i < name.length() && (isDigit ==
Character.isDigit(name.charAt(i))))
i++;
a = Arrays.copyOf(a, a.length + 1);
a[a.length-1] = name.substring(start, i);
}

return a;
}

// compare digits strings by int value, other strings by natural order.

private int compareChunk(String s1, String s2)
{
if (isNum(s1) && isNum(s2))
return valueOf(s1) - valueOf(s2);

return s1.compareTo(s2);
}

// Is the first character a digit?

private boolean isNum(String s)
{
return s.length() > 0 && Character.isDigit(s.charAt(0));
}

private int valueOf(String s)
{
try {
return Integer.parseInt(s);
} catch (NumberFormatException e) {}

return 0;
}
}
 
L

Lasse Reichstein Nielsen

www said:
I have a Map, actually a TreeMap, which will automatically sort the
keys alphabetically.
True.

The keys are Strings, like "VARIABLE" + i, e.g:
VARIABLE0, VARIABLE1, VARIABLE2, etc. ....
But, if the total number of entries > 10, the sorted order is not what
I want:

VARIABLE0
VARIABLE1
VARIABLE10
VARIABLE11
VARIABLE12
..
VARIABLE2
VARIABLE20 ....
I want the order be:
VARIABLE0
VARIABLE1
VARIABLE2
..
VARIABLE9
VARIABLE10
VARIABLE11
...
Click to expand...

As you said, the default order of comparison on strings is lexical, so
that is what you get.

You need to make a different comparison, and provide it to the TreeSet
as a Comparator.
Try, e.g.,

public static class VariableComparator implements Comparator<String> {
public int compare(String a, String b) {
int res = a.length() - b.length();
if (res == 0) {
res = a.substring(8).compareTo(b.substring(8));
}
return res;
}
}

It assumes that the strings do in fact start with "VARIABLE" and are
followed by the number.
Can you help me to achieve this? Thank you very much.
Click to expand...

You might want to reconsider the approach. All you seem to need is a
set of numbers. You can always prefix with "VARIABLE" later.
A BitSet would perhaps suffice.

/L
 
L

Lasse Reichstein Nielsen

......long snip.....
You might want to reconsider the approach. All you seem to need is a
set of numbers. You can always prefix with "VARIABLE" later.
A BitSet would perhaps suffice.
Click to expand...

Uhm, no. It was a Map, not a Set. Forget the last part.

/L
 
R

Roedy Green

Can you help me to achieve this? Thank you very much.
Click to expand...

You need to write a Comparable or Comparator. See
http://mindprod.com/jgloss/comparator.html
http://mindprod.com/jgloss/comparable.html
http://mindprod.com/jgloss/sort.html

There is one that will do what you want, but it perhaps overly
complicated part of http://mindprod.com/products1.html#INI

Roughly you must either split the field on every compare or spit it
when you construct the object and compare on the text part and if you
get a tie compare on the numeric part.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Sorting an STL map 1
Wrapping statements in Python in SPSS 10
How do you type test in C++... Newb question :) 2
Parallel sorting algorithms... 0
sorting map value based 6
sorting by prior value in a deeply nested hash 1
Sort Map on Value 42
Retrieve data 'live' from spinner within a RecyclerView 1

Members online

No members online now.
Total: 31 (members: 0, guests: 31)
Robots: 347

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,070
Latest member
BiogenixGummies

Latest Threads

Top