Sorting array's

[Peter Shipway]

Hey yo,

I am sort of new to array's, i know how to use them and such but I have not had much like sorting them, I have a custom object of Reverse which is an array containg a String and an Int, e.g

Key Value
a 1
b 2
c 4
d 3

The way I wish to sort them is in decesding order of the Value's e.g

Key Value
c 4
d 3
b 2
a 1

I am completely unsure of how to do it, to i compare each number to the one before and/or after it? wouldnt that be rather slow? isnt there a faster accurate way to do it?

Any help would be greatly appericated

[Chengwei Lee]

Hi Peter,

I don't quite understand your problem. Are you saying that you've a Reverse class that has an instance variable which is a 2D array? The first column holding String values & the second columns holding Integer object values?

Or the 2D array is not contained in the object?

[Peter Shipway]

Hey yo,

It is a 1d array of a class Object (code below);

  
/*
 ** This class acts as a custom array
 ** to store both a key and a value
 ** @author Peter Shipway, September 2004
 */
class Reverse{
    // The key of the array
    String n = "";
    // The value of the array
    int    d = 0;
    /*
     ** Constructer method for Reverse class
     ** @param an a string to act as 'key'
     ** @param ad a int to act as 'value'
     ** preconditions: none
     ** postconditions: update variables with new array
     ** entrie
     */
    public Reverse(String an, int ad){
        n = an;
        d = ad;
    }
    /*
     ** Returns the String key
     ** preconditions: none
     ** postconditions: return n
     */
    public String getN(){
        return n;
    }
    /*
     ** Returns the Int value
     ** preconditions: none
     ** postconditions: return d
     */
    public int getD(){
        return d;
    }
}

I am trying to sort the array by the Value(d) in decesinding order. Sorry if I am not using correct terms, I have gown very acustom to map's and lists.

[Peter Shipway]

Ok i have been checking out the java API and have found this;

sort(Object[] a)
Sorts the specified array of objects into ascending order, according to the natural ordering of its elements

is there a way I can use this method in my case? if so how?

[Nigel Browne]

you should look at the Collections framework.

import java.util.*;
 
public class Reverse {
   public static void main (String args[]){
      List l = Arrays.asList(args);
      Collections.reverse(l);
      System.out.println(l);
   }
}
 

run the program:
java Reverse 9 8 7 6 5 4 3 2 1

the answer being
[1, 2, 3, 4, 5, 6, 7, 8, 9]

[Neil Laurance]

Implement the Comparable interface:
http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html

import java.util.*;
public class Reverse implements Comparable {
    String n = "";
    int    d = 0;
    public Reverse(String an, int ad){
        n = an;
        d = ad;
    }
    public String getN(){ return n; }
    public int getD(){ return d; }
 
    public int compareTo(Object o) {
        return this.d - ((Reverse)o).d;
    }
    public String toString() {
        return "["+n+", "+d+"]";
    }
 
    public static void main(String[] args) {
        Reverse[] r = {
            new Reverse("c", 4),
            new Reverse("b", 2),
            new Reverse("a", 1),
            new Reverse("d", 3)
        };
        System.out.println("Unsorted:");
        printArray(r);
 
        Arrays.sort(r);
        System.out.println("Sorted:");
        printArray(r);
 
        Arrays.sort(r, Collections.reverseOrder());
        System.out.println("Reverse Sorted:");
        printArray(r);
    }
    public static void printArray(Object[] o) {
        for (int i = 0; i < o.length; i++) {
            System.out.println(o[i]);
        }
    }
}

Cheers, Neil

[Nigel Browne]

Also have you considered using one of the classes that implement the Map interface which are designed to hold key/value collections?

Learn the default librarys and you will find that alot of work has been already done by the experts, tested and used by the millions of java programmers worldwide. Don't reinvent the wheel !

[Peter Shipway]

Hey yo,

Now i am getting some really weird errors when I try and call the Arrays.sort(rev) method,
including a NullPointerException

    public void driverDistance() throws IOException{
        for (int r = 0; r < i; r++){
            String name = cars[r].getName();
            int    k    = cars[r].getK();
            if (!tm.containsKey(name)){
                tm.put(name, new Integer(k));
            }else{
                cars[r].setK(k);
                k = cars[r].getK();
                tm.remove(name);
                tm.put(name, new Integer(k));
            }
        }
        for (Iterator i = tm.entrySet().iterator(); i.hasNext(); ){
            Map.Entry entry = (Map.Entry)i.next();
            String key = entry.getKey().toString();
            int value  = Integer.parseInt(entry.getValue().toString());
            rev[a] = new Reverse(key, value);
            a++;
        }
        Arrays.sort(rev);
    }

What am i doing wrong? the error is occuring on the line of the Arrays.sort(rev)

[Peter Shipway]

I am so lost I fell like my head is going to explode, This is a really complicated program, I aplogize to the admin's but I fell like I will need to post all of it to make any sense what-so-ever;

  
/*
 ** Car class to be used as array and
 ** return methods, used with Travel.java
 ** @author Peter Shipway, August 2004
 */
class Car{
    // The Drivers Name
    String name  = "";
    // The Cars Rego
    String rego  = "";
    // The starting Place
    String start = "";
    // The ending Place
    String end   = "";
    // The Distance travled
    int k        = 0;
    /*
     ** Constructer for Car Class, updates values with variables passed
     ** @param thename The name of the driver.
     ** @param therego The registation number of the car.
     ** @param thestart The staring place of the dirver.
     ** @param thend The ending place of the driver.
     ** @param tk The distance the driver travled.
     ** postconditions: a instance of the car class has been created.
     ** preconditions: Variables updated with new values
     */
    public Car(String thename, String therego, String thestart, String theend, int tk){
        name  = thename;
        rego  = therego;
        start = thestart;
        end   = theend;
        k     = tk;
    }
    /*
     ** K is updated with the new value passed
     ** @param a The value to add to k
     ** precondtions: none
     ** postconditions: k is returned
     */
    public void setK(int a){
        k += a;
    }
    /*
     ** Returns the name of the driver
     ** preconditions: none
     ** postconditions: the name is returned
     */
    public String getName(){
        return name;
    }
    /*
     ** Returns the rego of the driver
     ** preconditions: none
     ** postconditions: the rego is retuned
     */
    public String getRego(){
        return rego;
    }
    /*
     ** Returns the starting place of the driver
     ** preconditions: none
     ** postconditions: the start is returned
     */
    public String getStart(){
        return start;
    }
     /*
      ** Returns the ending place of the driver
      ** preconditions: none
      ** postconditions: the end is returned
      */
    public String getEnd(){
        return end;
    }
    /*
     ** Returns the travel of the driver
     ** preconditions: none
     ** postconditions: the travel distance is returned
     */
    public int getK(){
        return k;
    }
}

I am using this class as an array to store infomation about the trips of the vehicles.

  
import java.util.*;
public class Reverse implements Comparable{
    String n = "";
    int    d = 0;
    
    public Reverse(String an, int ad){
        n = an;
        d = ad;
    }
    public String getN(){ return n; }
    public int getD(){ return d; }
    
    public int compareTo(Object o) {
        return this.d - ((Reverse)o).d;
    }
    
    public String toString() {return "["+n+", "+d+"]";}
}

This is the class that is suppose to store the array to be sorted and reversed (using it as an array)

  
import java.io.*;
import java.util.*;
/*
 ** Travel class to accept input
 ** from user then print out the
 ** total distance travled by each
 ** driver and the total of all drivers
 ** @author Peter Shipway, August 2004
 */
class Travel{
    Maps map = new Maps();
    static String param1 = "";
    static String param2 = "";
    /* 
     ** Creates a new instance of Travel then
     ** calls the read method followed by the
     ** print method
     ** @param args The command line arugments
     ** preconditions: none
     ** postconditions: summary of driver and distances 
     ** printed
     */
    public static void main(String[]args) throws IOException{
        Travel app = new Travel();
        app.commands(args); // calls commands to read in users commands
        app.read();         // read's the users input
        app.construct();    // constructs the map/array
    }
    /*
     ** Checks through array and places
     ** commands into two separte static strings
     ** @param args the command line arugments
     ** preconditions: a array is passed
     ** postconditions: String's updated with information
     */
    public void commands(String[] args){
        // Increaments through the array of arugments
        for (int a = 0; a < args.length; a++){
            if (a == 0){
                // Set the first String to the first array entry
                param1 = args[a];
            } else if (a == 1){
                // Set the second String to the second array entry
                param2 = args[a];
            }
        }
    }
    /*
     ** Accepts the users input line by
     ** line, calls the check method for
     ** error handling, if true is returned
     ** then information is taken out and a new
     ** car array entry is created.
     ** preconditions: user enters something
     ** postconditions: cars array updated with information
     */
    public void read() throws IOException{
        // Create a new reader to expect user input
        BufferedReader in = new BufferedReader(
            new InputStreamReader(System.in));
        String line   = in.readLine(); // read in the line
        String rego   = "";            // cars rego
        String name   = "";            // drivers name
        String startp = "";            // starting place
        String endp   = "";            // ending place
        int startk    = 0;             // starting k's
        int endk      = 0;             // ending k's
        int distance  = 0;             // distance travled
        while (line != null){
            // creates a new tokenizer from the line entered
            StringTokenizer st = new StringTokenizer(line);
            if (check(line) == true){
                // sets the variables to the values passed
                rego     = st.nextToken();
                name     = st.nextToken();
                startp   = st.nextToken();
                endp     = st.nextToken();
                startk   = Integer.parseInt(st.nextToken());
                endk     = Integer.parseInt(st.nextToken());
                distance = endk - startk;
                map.newCar(rego,name,startp,endp,distance);
            }
            // read a new line in
            line = in.readLine();
        }
    }
 
    /*
     ** Checks that the Line passed has 6 tokens, that
     ** the start and ending place are not the same,
     ** and that the final kilometres is not less then
     ** the begining 
     ** @param line the line with information to be checked
     ** preconditions: a line is passed
     ** postconditions: returns true if the line is valid
     */
     public boolean check(String line) throws IOException{
        StringTokenizer st = new StringTokenizer(line);
        if (st.countTokens() != 6){
            return false;
        }
        st.nextToken(); // rego
        st.nextToken(); // driver
        // If start location is equal to end location
        if (st.nextToken().equals(st.nextToken())){
            return false;
        }
        String s = st.nextToken(); // Starting k
        String e = st.nextToken(); // Ending k
        if (!isInt(s) || !isInt(e)){
            return false;
        }
        if (Integer.parseInt(e) < Integer.parseInt(s)){
            return false;
        }
        return true;
    }
    /*
     ** Accepts a String then returns if It can
     ** be changed to an Integer or not
     ** @param a the string to be checked
     ** preconditions none
     ** postconditions: true or false is returned
     */
    public boolean isInt(String a) throws IOException{
        try{
            Integer b = new Integer(a);
            return true;
        }
        catch (NumberFormatException E){
            return false;
        }
    }
    /*
     ** Creates the map depending upon the users entred
     ** command line arugments, uses a treemap to sort
     ** by the keys, and a hashmap to store the pre-sorted
     ** entries for values
     ** @param args the command line arugments
     ** preconditions: user has entered a valid command line
     ** arugment
     ** postconditions: maps updated with information
     */
    public void construct() throws IOException{
        if (param1.equalsIgnoreCase("-driver")){
            if (param2.equalsIgnoreCase("-distance")){
                map.driverDistance();
                printa();
            }else{
               map.driver();
               print();
            }
        }
        if (param1.equalsIgnoreCase("-vehicle")){
            if (param2.equalsIgnoreCase("-distance")){
                map.vehicleDistance();
                printa();
            }else{
               map.vehicle();
               print();
            }
        }
        if (param1.equalsIgnoreCase("-route")){
            map.route();
            printa();
        }
    }
    /*
     ** Iterates through the treemap printing the key
     ** then the value of the Map.
     ** precondtions: the treemap has been created
     ** postconditions: the results are printed to screen
     */
    public void print() throws IOException{
        Tools tool = new Tools();
        Map tm = map.getMap();
        // Create an Iterator to iterate through the Map
        for (Iterator i = tm.entrySet().iterator(); i.hasNext(); ){
            // Get the next map entry
            Map.Entry entry = (Map.Entry)i.next();
            // Get the Key and the Value and pass as strings
            String text = entry.getKey().toString();
            String num = entry.getValue().toString();
            // Print the key and value, justifyec
            System.out.println(tool.leftJustify(text,16) + tool.rightJustify(num,5));
        }
    }
    /*
     ** Iterates through the array printing the
     ** summrized information of the users inputS
     ** preconditions: the array is created
     ** postconditions: the information is printed to screen
     */
    public void printa() throws IOException{
        Tools tool = new Tools();
        for (int r = 0; r < map.getA(); r++){
            String key   = map.getKey(r);
            String value = map.getValue(r);
            System.out.println(tool.leftJustify(value,16) + tool.rightJustify(key,5));
        }
    }
}

That is the main class that handles everything, input, output and error handling.

  
import java.io.*;
import java.util.*;
class Maps{
    
    Map     tm   = new TreeMap();
    Car[]   cars = new Car[100];
    Reverse[] rev = new Reverse[100];
    int i = 0;
    int a = 0;
    
    public void newCar(String rego, String name, String startp, String endp, int distance){
        cars[i] = new Car(name,rego,startp,endp,distance);
        i++;
    }
 
    public void driverDistance() throws IOException{
        for (int r = 0; r < i; r++){
            String name = cars[r].getName();
            int    k    = cars[r].getK();
            if (!tm.containsKey(name)){
                tm.put(name, new Integer(k));
            }else{
                cars[r].setK(k);
                k = cars[r].getK();
                tm.remove(name);
                tm.put(name, new Integer(k));
            }
        }
        for (Iterator i = tm.entrySet().iterator(); i.hasNext(); ){
            Map.Entry entry = (Map.Entry)i.next();
            String key = entry.getKey().toString();
            int value  = Integer.parseInt(entry.getValue().toString());
            rev[a] = new Reverse(key, value);
            a++;
        }
        Arrays.sort(rev);
    }
 
    public void driver() throws IOException{
        for (int r = 0; r < i; r++){
            String name = cars[r].getName();
            int    k    = cars[r].getK();
            if (!tm.containsKey(name)){
                tm.put(name, new Integer(k));
            }else{
                cars[r].setK(k);
                k = cars[r].getK();
                tm.remove(name);
                tm.put(name, new Integer(k));
            }
        }
    }
 
    public void vehicleDistance() throws IOException{
        for (int r = 0; r < i; r++){
            String rego = cars[r].getRego();
            int    k    = cars[r].getK();
            if (!tm.containsKey(rego)){
                tm.put(rego, new Integer(k));
            }else{
                cars[r].setK(k);
                k = cars[r].getK();
                tm.remove(rego);
                tm.put(rego, new Integer(k)); 
            }
        }
        for (Iterator i = tm.entrySet().iterator(); i.hasNext(); ){
            Map.Entry entry = (Map.Entry)i.next();
            String key = entry.getKey().toString();
            int value  = Integer.parseInt(entry.getValue().toString());
            rev[a] = new Reverse(key, value);
            a++;
        }
        Arrays.sort(rev);
    }
 
    public void vehicle() throws IOException{
        for (int r = 0; r < i; r++){
            String rego = cars[r].getRego();
            int    k    = cars[r].getK();
            if (!tm.containsKey(rego)){
                tm.put(rego, new Integer(k));
            }else{
                cars[r].setK(k);
                k = cars[r].getK();
                tm.remove(rego);
                tm.put(rego, new Integer(k));
            }
        }
    }
 
    public void route() throws IOException{
        for (int r = 0; r < i; r++){
            String se = cars[r].getStart() + " " + cars[r].getEnd();
            if (!tm.containsKey(se)){
                tm.put(se, new Integer(1));
            }else{
                int e = Integer.parseInt(tm.get(se).toString());
                e++;
                tm.remove(se);
                tm.put(se, new Integer(e));
            }
        }
        for (Iterator i = tm.entrySet().iterator(); i.hasNext(); ){
            Map.Entry entry = (Map.Entry)i.next();
            String key = entry.getKey().toString();
            int value  = Integer.parseInt(entry.getValue().toString());
            rev[a] = new Reverse(key, value);
            a++;
        }
        Arrays.sort(rev);
    }
 
    public Map getMap(){
        return tm;
    }
    
    public int getA(){
        return a;
    }
 
    public String getValue(int c){
        return rev[c].getN();
    }
 
    public String getKey(int c){
        int z = rev[c].getD();;
        Integer x = new Integer(z);
        String y = x.toString();
        return y;
    }
}

The class that will probbaly cause me to loose 10 years of my life, this is the problem class (i think) it handles the maps, arrays and how to create and store them.

[Chengwei Lee]

Hi Peter,

Neil had already given you the solution to your woes. Take a look at it.

Cheers!

[Peter Shipway]

Hey yo,

I relize that and I am very thankfull, but I get errors when trying to do it that way. e.g I cannot use the Arrays.sort() method

[Peter Shipway]

Sorry I will be more clear;

I am using the idea of a class that extends the Comparison class, I am using this as an array, I am attempting to sort it from another class, I am getting a NullPointerException on the following method;

  
    public int compareTo(Object o) {
        return this.d - ((Reverse)o).d;
    }

Which is located in the reverse class, you have helped me out beyond what I could have hoped for guy's, if I can just get past the last road-block I will be extermly greatful and happy for your help.

[Layne Lund]

Your above method has a possible source for the NullPointerException that you get. What happens if the parameter o is not actually an object of type Reverse, for some reason? The cast (Reverse)o will return null and attempting to call a method on this null reference will cause a NullPointerException! Of course, if this happens, there's probably a problem somewhere else in your program. Perhaps you can do something like

public int compareTo(Object o)
{
  Reverse r = (Reverse) o;
  if (r == null) {
    throw new InvalidArgumentException("Object of type Reverse expected.");
  }
  return this.d - r.d;
}

I'm not saying this will fix all of your problems. However, it will eliminate this particular source of an error, and even alert you later if you modify something that causes this.

HTH

Layne

[Chengwei Lee]

My apologise, I didn't read the posts carefully enough.

My suggestion would be to use Collections.sort(List l, Comparator c). If you're using an Object[] to store your Reverse objects, you need to know the size before hand. But using List, you can have dynamic sizes.

Then by implementing the Comparator class, you can specify the sort order you need.

HTH.

[Neil Laurance]

You have created an array of Reverse items using:

Reverse rev = new Reverse[100];

This array is initialised with 100 null Reverse references.
You cannot use Arrays.sort when part of this array contains nulls.
Better to use a dynamically growing list, and use Collections.sort:

List rev = new ArrayList;
...
Reverse foo = ...
...
rev.add(foo);
...
Collections.sort(rev);

This should hopefully solve your problems.
Cheers, Neil