1 Replies - 1784 Views - Last Post: 09 December 2012 - 12:38 AM Rate Topic: -----

#1 lilVaratep  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 27
  • View blog
  • Posts: 241
  • Joined: 09-October 11

Java: Radix sort difficulties

Posted 08 December 2012 - 08:52 PM

Been trying to work on my radix sort implementation for a while now and I'm just completely lost. Looked at algorithms online as well as notes, but still confused on how to get it down to code.


Goals:

Create a le called Location.java which is a simple data item with 3 elds: a String name and 2 longs x
and y. You may have accessors, mutators, and other methods as necessary. You may assume all values
for x and y are positive.
Create a le called ReallySortableVector which has a field ArrayList<Location> thePlaces and at least 4
methods: sortBubble which will sort the items into alphabetical order by their name using bubble sort,
sortQuick which will sort the items by the x coordinate using quick sort, sortRadix which will sort the
items by the y coordinate using radix sort, and ndDistance which will nd the total distance of following
a straight line path between the items in the order they appear in the ArrayList.
Create a le called Driver4 which reads the initial data from a le, performs the sorting and calculating,
and outputs the information as shown in the sample below


Currently getting errors:

java.lang.StringIndexOutOfBoundsException: String index out of range: 2
at java.lang.String.charAt(String.java:658)
at ReallySortableVector.sortRadix(ReallySortableVector.java:61)
at Driver4.main(Driver4.java:32)
java.lang.StringIndexOutOfBoundsException: String index out of range: 1
at java.lang.String.charAt(String.java:658)
at ReallySortableVector.sortRadix(ReallySortableVector.java:61)
at ReallySortableVector.sortRadix(ReallySortableVector.java:77)
at Driver4.main(Driver4.java:32)
java.lang.StringIndexOutOfBoundsException: String index out of range: -1
at java.lang.String.charAt(String.java:658)
at ReallySortableVector.sortRadix(ReallySortableVector.java:61)
at ReallySortableVector.sortRadix(ReallySortableVector.java:77)
at ReallySortableVector.sortRadix(ReallySortableVector.java:77)
at ReallySortableVector.sortRadix(ReallySortableVector.java:77)
at Driver4.main(Driver4.java:32)
8 6 Ddeeffgg Cliff


at runtime

any help is appreciated. thanks!

main:

import java.util.*;
import java.io.*;

public class Driver4 {
    public static void main(String[] args) {
        System.out.println("Welcome to Project 4.");
        System.out.println("Reading data from locations.txt");
        ReallySortableVector rsv = readFile();
        
        System.out.println("Anna's Path");
        rsv.sortBubble();
        for (int i = 0; i < rsv.thePlaces.size(); i++) {
            System.out.println(rsv.thePlaces.get(i).getX() + " "
                + rsv.thePlaces.get(i).getY() + " "
                + rsv.thePlaces.get(i).getName());
        }
        
        System.out.println("Carlos' Path");
        rsv.sortQuick(0, rsv.thePlaces.size()-1);
        for (int i = 0; i < rsv.thePlaces.size(); i++) {
            System.out.println(rsv.thePlaces.get(i).getX() + " "
                + rsv.thePlaces.get(i).getY() + " "
                + rsv.thePlaces.get(i).getName());
        }
        
        System.out.println("Bob's Path");
        rsv.sortRadix(rsv.checkBits());
        for (int i = 0; i < rsv.thePlaces.size(); i++) {
            System.out.println(rsv.thePlaces.get(i).getX() + " "
                + rsv.thePlaces.get(i).getY() + " "
                + rsv.thePlaces.get(i).getName());
        }
    }
    public static ReallySortableVector readFile() {
        ReallySortableVector rsv = new ReallySortableVector();
        Location info;
        try {
            Scanner file = new Scanner(new File("locations.txt"));
            rsv = new ReallySortableVector();
            while (file.hasNext()) {
                String tempD = file.nextLine();
                String delims = " ";
                String[] tokens = tempD.split(delims);
                if (tokens.length > 3)
                    for (int i = 2; i < tokens.length-1; i++) {
                        tokens[2] = tokens[2] + " " + tokens[i+1];
                    }
               info = new Location(tokens[2], Long.parseLong(tokens[0]),
                Long.parseLong(tokens[1]));
               rsv.addToList(info);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return rsv;
    }
}


arraylist/vector:

   import java.util.*;

   public class ReallySortableVector {
      ArrayList<Location> thePlaces = new ArrayList<Location>();
      
      public ReallySortableVector() {
        
      }
    
      public void addToList(Location lc) {
         thePlaces.add(lc);
      }
    
      public void sortQuick(int low, int high) {
         Location[] tmp = new Location[high-low+1];
         int from = low, to = high;
         if (high-low > 0) {
            for (int i = low+1; i <= high; i++) {
               if (thePlaces.get(low).getX() < thePlaces.get(i).getX())
                  tmp[-low+to--] = thePlaces.get(i);
               else
                  tmp[-low+from++] = thePlaces.get(i);
            }
            tmp[from-low] = thePlaces.get(low);
            for (int i = low; i <= high; i++)
               thePlaces.set(i, tmp[i-low]);
            sortQuick(low, from-1);
            sortQuick(from+1, high);
         }
      }
    
      public void sortBubble() {
         int i = 1;
         Location tmp;
         boolean done = false;
         while (!done) {
            done = true;
            for (int j = 0; j < thePlaces.size()-i; j++)
               if (thePlaces.get(j).getName().compareTo(thePlaces.get(j+1).getName())>0)
               {
                  tmp = thePlaces.get(j);
                  thePlaces.set(j, thePlaces.get(j+1));
                  thePlaces.set(j+1, tmp);
                  done = false;
               }
            i++;
         }
      }
          public void sortRadix(int bitLocation) {
         Location tmp;
         ArrayList<Location> tmpA = new ArrayList<Location>();
         String conversion;
         try {
             for (int i = 0; i < thePlaces.size(); i++) {
                if (longToBinary(thePlaces.get(i).getY()).charAt(bitLocation-1) == '0') {
                   tmpA.add(thePlaces.get(i));
                   thePlaces.remove(i);
                }
             }
             for (int i = 0; i < thePlaces.size(); i++) {
                if (longToBinary(thePlaces.get(i).getY()).charAt(bitLocation-1) == '1') {
                   tmpA.add(thePlaces.get(i));
                   thePlaces.remove(i);
                }
             }
         } catch (Exception e) {
            e.printStackTrace();
         }
        
         if (bitLocation-1 >= 0)
            sortRadix(bitLocation-1);
      }
      
    
      private String longToBinary(long n) {
         return Long.toBinaryString(n);
      }
    
      public int checkBits() {
         int max = 0;
         String strLong;
         for (int i = 0; i < thePlaces.size(); i++) {
            strLong = Long.toBinaryString(thePlaces.get(i).getY());
            if (strLong.length() > max)
               max = strLong.length();
         }
         return max;
      }
    
    
      private Location[] generateArray(int size) {
         Location[] pass = new Location[size];
         return pass;
      }
   }



location:


public class Location {
    String name;
    long x;
    long y;
    public Location() {
        name = "";
        x = 0;
        y = 0;
    }
    public Location(String n, long a, long B)/> {
        name = n;
        x = a;
        y = b;
    }
    public String getName() {
        return name;
    }
    public void setName(String n) {
        name = n;
    }
    public long getX() {
        return x;
    }
    public void setX(Long a) {
        x = a;
    }
    public long getY() {
        return y;
    }
    public void setY(Long B)/> {
        y = b;
    }
}



locations.txt:

0 0 Aabbccdd Hill
4 3 Ssttuuvv Escape
0 6 Hhiijjkk Falls
8 0 Nnooppqq Trail Head
8 6 Ddeeffgg Cliff


Is This A Good Question/Topic? 0
  • +

Replies To: Java: Radix sort difficulties

#2 Martyr2  Icon User is online

  • Programming Theoretician
  • member icon

Reputation: 4424
  • View blog
  • Posts: 12,293
  • Joined: 18-April 07

Re: Java: Radix sort difficulties

Posted 09 December 2012 - 12:38 AM

Well the errors are telling you that whatever bitlocation is that you are sending to your sortRadix there is out of range when you subtract 1 from it. So for example lets assume that I pass the bitlocation of 0 to the function. When it subtracts 1 it will come out as -1 which charAt is going to choke on. Or lets say the string you are calling charAt on is only 3 characters long but you pass a bit location of 4 to the function. Subtract 1 and you get index 3, but the highest index (because it starts at zero) is 2. There is no character at the 3 index. Again, the index is out of range.

It seems to be whatever line 658 is on. So check that line and see what bitlocation (subtract 1) might be out of range and you will have the source of your errors.

:)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1