# Re: a question for sorting keys in Map

From:
curt@kcwc.com (Curt Welch)
Newsgroups:
comp.lang.java.programmer
Date:
20 Nov 2007 20:25:08 GMT
Message-ID:
www <www@nospam.com> wrote:

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.

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 <curt@kcwc.com>
* 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[i], v2a[i]);
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;
}
}

--
Curt Welch http://CurtWelch.Com/