Sort algorithm problems on java comparable

Question

I want to do a specific sort. I am using java's comparable interface which means the return of my compare method must return -1 +1 or 0 depending on the equality of the two compared, then I am sorting using Collections. My trouble comes from how I wish to compare.

I have a key that is made up of either of the following

[keyName]  
[siteName].[keyName]  
[siteName].[pageName].[keyName]  

so as an example "mysite.alampshade.color"

the tricky part is the sites must be sorted first, followed by keyname, followed by pageName. but firstly by the keynames, then site name, in the order of the number of sections to the property. Sorry. its a little complicated, an example may help. here is the order they must be:

alpha  
beta  
charlie  
sitea.alpha  
sitea.charlie  
sitea.pagea.beta  
sitea.pageb.beta  
sitea.pagea.charlie  
siteb.alpha  
siteb.delta  
siteb.pagef.alpha  
siteb.pageb.echo  
siteb.pageb.golf  
siteb.pagea.hotel  
siteb.pageb.hotel  
siteb.pagec.hotel  

I have tried many different ways and have thrown away code a few times but still cant get it perfect. some pseudocode would be of great help if not some java.

EDIT: to add another possibly simplier to understand example the following is sorted how I need it

a  
b  
c  
z  
a.b  
a.c  
a.d  
a.z  
a.b.a  
a.c.a  
a.b.b  
a.b.c  
a.c.c  
a.a.d  
b.a  
b.b  
b.z  
b.a.a  
b.b.a  
b.a.b  
c.c.f  

Answer 1

Should be good now.

public int compare(String a, String b) {
String[] partsA = a.split("\\.");
String[] partsB = b.split("\\.");

// If first term is different, we exit.
if (partsA[0].compareTo(partsB[0]) != 0) return partsA[0].compareTo(partsB[0]);

// Else, first term is identical.
else {
    // Same number of parts
    if (partsA.length == partsB.length) {
        // 2 parts, we compare the 2nd part.
        if (partsA.length == 2) {
            return partsA[1].compareTo(partsB[1]);
        // 3 parts, we compare the 3rd part first, then the 2nd part        
        } else {
            if (partsA[2].compareTo(partsB[2]) != 0) return partsA[2].compareTo(partsB[2]);
            return partsA[1].compareTo(partsB[1]);
        }

    // Different number of parts
    } else {
        // If A has only 1 part, it's first
        if (partsA.length == 1) return -1;
        // If B has only 1 part, it's first
        if (partsB.length == 1) return 1;

        // Case 2 vs 3 parts, we compare the 3rd part with the 2nd part of the other. If it's equal, the shorter is first.
        if (partsA.length == 3) {
            if (partsA[2].compareTo(partsB[1]) != 0) return partsA[2].compareTo(partsB[1]);
            else return 1;
        } else {
            if (partsA[1].compareTo(partsB[2]) != 0) return partsA[1].compareTo(partsB[2]);
            else return -1;
        }           
    }
}
}

Answer 2

Another option, making it recursive you avoid the problem if there is ever more entries.

import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List;

public class SortTest {
    public static void main(String[] args) {
        String[] test = new String[]{
            "a",
            "b",
            "b.a",
            "b.a.a",
            "a.a.a",
            "a.b.a",
            "a.a",
            "a.b",
            "b.a.b",
            "b.b.a"
        };

        Arrays.sort(test, new Comparator<String>() {

        int compareComplexList(List<String> a, List<String> b, List<int[]> positions, int order ) {

          int minimum = a.size() < b.size() ? a.size() - 1 : b.size() - 1;   

          if (a.get(positions.get(minimum)[order]).compareTo(b.get(positions.get(minimum)[order])) != 0)
                return a.get(positions.get(minimum)[order]).compareTo(b.get(positions.get(minimum)[order]));
          else if (order < minimum - 1) return compareComplexList(a,b, positions, ++order);
          else return Double.compare(a.size(),b.size());
        }

        public int compare(String a, String b) {
          List<String> partsA = Arrays.asList(a.split("\\."));
          List<String> partsB = Arrays.asList(b.split("\\."));
          List<int[]>  orders = new ArrayList<int[]>();

          orders.add(new int[] {0});
          orders.add(new int[] {0,1});
          orders.add(new int[] {0,2,1});

          return compareComplexList(partsA, partsB, orders,0);
        }
        });
        System.out.println("Sorted: "+Arrays.toString(test));
    }

}

Answer 3

My other answer started getting too gnarly. Here's a better, more natural solution:

public class StrangeComparator {
  private static class Entry implements Comparable<Entry> {
    // What to split with.
    static final String dot = Pattern.quote(".");
    // The parts.
    final String key;
    final String page;
    final String site;

    public Entry(String s) {
      String [] parts = s.split(dot);
      switch (parts.length) {
        case 1:
          key = parts[0];
          page = "";
          site = "";
          break;

        case 2:
          key = parts[1];
          page = "";
          site = parts[0];
          break;

        case 3:
          key = parts[2];
          page = parts[1];
          site = parts[0];
          break;

        default:
          throw new IllegalArgumentException("There must be at least one part to an entry.");
      }
    }

    @Override
    public int compareTo(Entry t) {
      int diff = site.compareTo(t.site);
      if ( diff == 0 ) {
        diff = page.compareTo(t.page);
      }
      if ( diff == 0 ) {
        diff = key.compareTo(t.key);
      }
      return diff;
    }

    @Override
    public String toString () {
      return (site.length() > 0 ? site + "." : "")
              + (page.length() > 0 ? page + "." : "")
              + key;
    }
  }

  public void test() {
    String[] test = new String[]{
      "alpha",
      "beta",
      "charlie",
      "zeta", // Added to demonstrate correctness.
      "sitea.alpha",
      "sitea.charlie",
      "sitea.pagea.beta",
      "sitea.pageb.beta",
      "sitea.pagea.charlie",
      "siteb.alpha",
      "siteb.delta",
      "siteb.pagef.alpha",
      "siteb.pageb.echo",
      "siteb.pageb.golf",
      "siteb.pagea.hotel",
      "siteb.pageb.hotel",
      "siteb.pagec.hotel"
    };
    Arrays.sort(test);
    System.out.println("Normal sort: " + Separator.separate("\n", "\n", test));
    Entry[] entries = new Entry[test.length];
    for ( int i = 0; i < test.length; i++ ) {
      entries[i] = new Entry(test[i]);
    }
    Arrays.sort(entries);
    System.out.println("Special sort: " + Separator.separate("\n", "\n", entries));
  }

  public static void main(String args[]) {
    new StrangeComparator().test();
  }
}

Output order is:

alpha
beta
charlie
zeta
sitea.alpha
sitea.charlie
sitea.pagea.beta
sitea.pagea.charlie
sitea.pageb.beta
siteb.alpha
siteb.delta
siteb.pagea.hotel
siteb.pageb.echo
siteb.pageb.golf
siteb.pageb.hotel
siteb.pagec.hotel
siteb.pagef.alpha

Which kinda does what you say but doesn't match your example.

Answer 4

Here's an alternative - if a component is found to contain less that 3 parts then parts are added at the start to take up the slack. It then uses a sort order array to define which columns should be compared next:

  public void test() {
    String[] test = new String[]{
      "alpha",
      "beta",
      "charlie",
      "zeta", // Added to demonstrate correctness.
      "sitea.alpha",
      "sitea.charlie",
      "sitea.pagea.beta",
      "sitea.pageb.beta",
      "sitea.pagea.charlie",
      "siteb.alpha",
      "siteb.delta",
      "siteb.pagef.alpha",
      "siteb.pageb.echo",
      "siteb.pageb.golf",
      "siteb.pagea.hotel",
      "siteb.pageb.hotel",
      "siteb.pagec.hotel"
    };
    Arrays.sort(test);
    System.out.println("Normal sort: "+Arrays.toString(test));
    Arrays.sort(test, new Comparator<String>() {
      // How many columns to pad to.
      final int padTo = 3;
      // What to pad with.
      final String padWith = "";
      // What order to compare the resultant columns in.
      final int[] order = {0, 2, 1};

      @Override
      public int compare(String s1, String s2) {
        String[] s1parts = padArray(s1.split(Pattern.quote(".")), padTo, padWith);
        String[] s2parts = padArray(s2.split(Pattern.quote(".")), padTo, padWith);
        int diff = 0;
        for ( int i = 0; diff == 0 && i < order.length; i++ ) {
          diff = s1parts[order[i]].compareTo(s2parts[order[i]]);
        }
        return diff;
      }

      String [] padArray(String[] array, int padTo, String padWith) {
        String [] padded = new String[padTo];
        for ( int i = 0; i < padded.length; i++ ) {
          padded[padded.length - i - 1] = i < array.length ? array[i]: padWith;
        }
        return padded;
      }
    });
    System.out.println("Special sort: "+Arrays.toString(test));
  }

prints (more or less):

Normal sort: [alpha,
 beta,
 charlie,
 sitea.alpha,
 sitea.charlie,
 sitea.pagea.beta,
 sitea.pagea.charlie,
 sitea.pageb.beta,
 siteb.alpha,
 siteb.delta,
 siteb.pagea.hotel,
 siteb.pageb.echo,
 siteb.pageb.golf,
 siteb.pageb.hotel,
 siteb.pagec.hotel,
 siteb.pagef.alpha,
 zeta]
Special sort: [alpha,
 beta,
 charlie,
 sitea.alpha,
 sitea.charlie,
 siteb.alpha,
 siteb.delta,
 zeta,
 siteb.pagef.alpha,
 sitea.pagea.beta,
 sitea.pageb.beta,
 sitea.pagea.charlie,
 siteb.pageb.echo,
 siteb.pageb.golf,
 siteb.pagea.hotel,
 siteb.pageb.hotel,
 siteb.pagec.hotel]

There does seem to be some ambiguity in your requirements but this code is structured so you can, with trivial tweaks, achieve most interpretations of your comparison quite simply.