Solved

Reading from input, storing to output

Posted on 2004-09-06
67
306 Views
Last Modified: 2010-08-05
Hello again,

I did some testing with this code, and found it did not work if the integers on my input.txt were separated by tabs instead of spaces.  Is there a way I can have the output print the same format as the input?

Example:

  input: 1 <tab> 2 <tab> <tab> 3
output: 1 <tab> 2 <tab> <tab> 3

  input: 1 _ 2 _ _ 3
output: 1 _ 2 _ _ 3

Note: <tab> represents tab spaces, and "_" represents regular spaces.
0
Comment
Question by:luna621
  • 42
  • 16
  • 4
  • +2
67 Comments
 

Author Comment

by:luna621
Comment Utility
import java.io.*;
 import java.util.*;

 public class ReadInputArray {

      public static void main (String[] arg) throws Exception {
        // Read input array

        BufferedReader readFile = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String input = "";

        File output = new File("output.txt"); // writes to output.txt
        FileOutputStream outFromFile = new FileOutputStream(output);
        PrintStream ps = new PrintStream(outFromFile);

        try {

            while((input = readFile.readLine())!=null) { // reads until there are no characters left

                ArrayList resultList = new ArrayList(); // create new ArrayList for result
                ArrayList digitsList = new ArrayList(); // create new ArrayList for ints

                int len = input.length(); // length of input
                StringBuffer sbDigits = new StringBuffer(); // create new string

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ') { // if the character is a space
                        resultList.add("_" + c);
                        if(sbDigits.length()>0) { // join the two together
                            digitsList.add(new Integer(sbDigits.toString()));
                            resultList.add(new Integer(sbDigits.toString()));
                            sbDigits = new StringBuffer();
                        } // END if
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

                if(sbDigits.length()>0){
                    digitsList.add(new Integer(sbDigits.toString()));
                    resultList.add(new Integer(sbDigits.toString()));
                    sbDigits = new StringBuffer();
                } // END if

                for(int i=1; i<resultList.size(); i++){
                    //System.out.print(resultList.get(i));
                    ps.print(resultList.get(i)); // writes what was read to outout.txt
                } // END for
            } // END while
            System.out.println("Process complete.  Please check your output.txt.\n");
        } // END try

        catch(NumberFormatException notInt) {
             System.out.println("Input not in correct format.  Integers only please.");
             System.out.println("Program will now exit.\n");
        } // END catch
      } // END main()

 } // END class ReadInputArray
0
 

Author Comment

by:luna621
Comment Utility
After more testing, I found that these lines:

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    ...
                } // END for

                if(sbDigits.length()>0){
                    digitsList.add(new Integer(sbDigits.toString()));
                    resultList.add(new Integer(sbDigits.toString()));
                    sbDigits = new StringBuffer();
                } // END if

miss the last space from the input.txt file.

Example:

  input: 1 _ 2 _ _ 3
output: 1 _ 2 _ 3

Perhaps instead of a StringBuffer(), I should use StringTokenizer()??
0
 

Author Comment

by:luna621
Comment Utility
And what would happen if my input.txt had a combination of tabs and spaces separating the integers?

Example:                    input: 1 _ 2 _ <tab> 3
0
 
LVL 92

Assisted Solution

by:objects
objects earned 250 total points
Comment Utility
>  if(c == ' ') { // if the character is a space

try changing that to:

 if(c == ' ' || c == '\t' ) { // if the character is a space or a tab
0
 

Author Comment

by:luna621
Comment Utility
Ok, that fixed the tab problem.  Thank you!

But, it's still not counting the last space/tab.
0
 

Author Comment

by:luna621
Comment Utility
Hmm... it's also adding a space before the tab.

Example:

  input: 1 <tab> 2 <tab> <tab> 3
output: 1 _ <tab> 2 _ <tab> 3   <------ still missing last tab
0
 

Author Comment

by:luna621
Comment Utility
Oh, nevermind about the space before the tab.  I fixed it :)
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
So do you still have any problems with it?
0
 

Author Comment

by:luna621
Comment Utility
Well, it's still not reading the last space/tab.  I got rid of the other problem (space before the tab).

Example:

  input: 1 _ 2 _ _ 3
output: 1 _ 2 _ 3 <----- what happened to the last space??
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
can u post the current code
0
 

Author Comment

by:luna621
Comment Utility
import java.io.*;
 import java.util.*;

 public class ReadInputArray {

      public static void main (String[] arg) throws Exception {
        // Read input array

        BufferedReader readFile = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String input = "";

        File output = new File("output.txt"); // writes to output.txt
        FileOutputStream outFromFile = new FileOutputStream(output);
        PrintStream ps = new PrintStream(outFromFile);

        try {

            while((input = readFile.readLine())!=null) { // reads until there are no characters left

                ArrayList resultList = new ArrayList(); // create new ArrayList for result
                ArrayList digitsList = new ArrayList(); // create new ArrayList for ints

                int len = input.length(); // length of input
                StringBuffer sbDigits = new StringBuffer(); // create new string

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ' || c == '\t') { // if the character is a space or tab
                        resultList.add("" + c);
                        if(sbDigits.length()>0) { // join the two together
                            digitsList.add(new Integer(sbDigits.toString()));
                            resultList.add(new Integer(sbDigits.toString()));
                            sbDigits = new StringBuffer();
                        } // END if
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

                if(sbDigits.length()>0){
                    digitsList.add(new Integer(sbDigits.toString()));
                    resultList.add(new Integer(sbDigits.toString()));
                    sbDigits = new StringBuffer();
                } // END if

                for(int i=1; i<resultList.size(); i++){
                    ps.print(resultList.get(i)); // writes what was read to outout.txt
                } // END for
            } // END while
            System.out.println("Process complete.  Please check your output.txt.\n");
        } // END try

        catch(NumberFormatException notInt) {
             System.out.println("Input not in correct format.  Integers only please.");
             System.out.println("Program will now exit.\n");
        } // END catch

      } // END main()


 } // END class ReadInputArray
0
 
LVL 16

Accepted Solution

by:
gnoon earned 250 total points
Comment Utility
It should be

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ' || c == '\t') { // if the character is a space
                        if(sbDigits.length()>0) { // join the two together
                            resultList.add(new Integer(sbDigits.toString()));
                            sbDigits = new StringBuffer();
                        } // END if
                        String space = c == ' ' ? "_" : "\t" ;
                        resultList.add(space);
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

                if(sbDigits.length()>0){
                    resultList.add(new Integer(sbDigits.toString()));
                    sbDigits = new StringBuffer();
                } // END if
0
 

Author Comment

by:luna621
Comment Utility
Hmm... it doesn't print the first integer.
0
 
LVL 16

Expert Comment

by:gnoon
Comment Utility
And this

                for(int i=0; i<resultList.size(); i++){   //<---------- i=1 should be i=0
                    System.out.println(">>"+resultList.get(i));
                    ps.print(resultList.get(i)); // writes what was read to outout.txt
                } // END for
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
> Hmm... it doesn't print the first integer.

It was printing it before wasn't it?
0
 

Author Comment

by:luna621
Comment Utility
:)  thank you gnoon!!

Okay, I have another question.  Suppose I want to sort the integers using this quicksort code:

import java.util.Vector;

public class QuickSort
{
    // Sorts entire array
    public static void sort(Vector array)
    {
        sort(array, 0, array.size() - 1);
    }

    // Sorts partial array
    public static void sort(Vector array, int start, int end)
    {
        int p;
        if (end > start)
        {
            p = partition(array, start, end);
            sort(array, start, p-1);
            sort(array, p+1, end);
        }
    }

    protected static int compare(Sortable a, Sortable b)
    {
       return a.compare(b);
    }

    protected static int partition(Vector array, int start, int end)
    {
        int left, right;
        Sortable partitionElement;

        // Arbitrary partition start...there are better ways...
        partitionElement = (Sortable)array.elementAt(end);

        left = start - 1;
        right = end;
        for (;;)
        {
            while (compare(partitionElement, (Sortable)array.elementAt(++left)) == 1)
            {
                if (left == end) break;
            }
            while (compare(partitionElement, (Sortable)array.elementAt(--right)) == -1)
            {
                if (right == start) break;
            }
            if (left >= right) break;
            swap(array, left, right);
        }
        swap(array, left, end);

        return left;
    }

    protected static void swap(Vector array, int i, int j)
    {
        Object temp;

        temp = array.elementAt(i);
        array.setElementAt(array.elementAt(j), i);
        array.setElementAt(temp, j);
    }
}

How would I call on it from the main method?
0
 

Author Comment

by:luna621
Comment Utility
or is there a better code for the quicksort?  That's the one I learned...
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
You'll need to either change your QuickSort class to use List instead of Vector, or change your resultList to be a Vector (I'd suggest the former)

Then to call it use:

QuickSort.sort(resultList);
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
> or is there a better code for the quicksort?

Collections.sort(resultList);
0
 

Author Comment

by:luna621
Comment Utility
So, for these:

    public static void sort(Vector array) {
    ...
    public static void sort(Vector array, int start, int end)...

change it to

    public static void sort(List array) {
    ...
    public static void sort(List array, int start, int end)...
0
 

Author Comment

by:luna621
Comment Utility
Uh oh!  Comes up with a bunch of errors.  I think because the code was dependent on the Vector thing:

C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:20: cannot resolve symbol
symbol  : class Sortable
location: class QuickSort
    protected static int compare(Sortable a, Sortable b) {
                                 ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:20: cannot resolve symbol
symbol  : class Sortable
location: class QuickSort
    protected static int compare(Sortable a, Sortable b) {
                                             ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:26: cannot resolve symbol
symbol  : class Sortable
location: class QuickSort
        Sortable partitionElement;
        ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:29: cannot resolve symbol
symbol  : class Sortable
location: class QuickSort
        partitionElement = (Sortable)array.elementAt(end);
                            ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:29: cannot resolve symbol
symbol  : method elementAt (int)
location: interface java.util.List
        partitionElement = (Sortable)array.elementAt(end);
                                          ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:34: cannot resolve symbol
symbol  : class Sortable
location: class QuickSort
            while (compare(partitionElement, (Sortable)array.elementAt(++left)) == 1) {
                                              ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:34: cannot resolve symbol
symbol  : method elementAt (int)
location: interface java.util.List
            while (compare(partitionElement, (Sortable)array.elementAt(++left)) == 1) {
                                                            ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:37: cannot resolve symbol
symbol  : class Sortable
location: class QuickSort
            while (compare(partitionElement, (Sortable)array.elementAt(--right)) == -1) {
                                              ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:37: cannot resolve symbol
symbol  : method elementAt (int)
location: interface java.util.List
            while (compare(partitionElement, (Sortable)array.elementAt(--right)) == -1) {
                                                            ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:41: swap(java.util.Vector,int,int) in QuickSort cannot be applied to (java.util.List,int,int)
            swap(array, left, right);
            ^
C:\Documents and Settings\luna621\My Documents\Codes\QuickSort.java:43: swap(java.util.Vector,int,int) in QuickSort cannot be applied to (java.util.List,int,int)
        swap(array, left, end);
        ^
11 errors
0
 

Author Comment

by:luna621
Comment Utility
Here's the Quicksort code:

import java.util.*;

public class QuickSort {

    // Sorts entire array
    public static void sort(List array) {
        sort(array, 0, array.size() - 1);
    } // END sort

    // Sorts partial array
    public static void sort(List array, int start, int end) {
        int p;
        if (end > start) {
            p = partition(array, start, end);
            sort(array, start, p-1);
            sort(array, p+1, end);
        } // END if
    } // END sort

    protected static int compare(Sortable a, Sortable b) {
       return a.compare(b);
    } // END compare

    protected static int partition(List array, int start, int end) {
        int left, right;
        Sortable partitionElement;

        // Arbitrary partition start...
        partitionElement = (Sortable)array.elementAt(end);

        left = start - 1;
        right = end;
        for (;;) {
            while (compare(partitionElement, (Sortable)array.elementAt(++left)) == 1) {
                if (left == end) break;
            } // END while
            while (compare(partitionElement, (Sortable)array.elementAt(--right)) == -1) {
                if (right == start) break;
            } // END while
            if (left >= right) break;
            swap(array, left, right);
        } // END for
        swap(array, left, end);

        return left;
    } // END partition

    protected static void swap(Vector array, int i, int j) {
        Object temp;

        temp = array.elementAt(i);
        array.setElementAt(array.elementAt(j), i);
        array.setElementAt(temp, j);
    } // END swap
} // END Quicksort
0
 

Author Comment

by:luna621
Comment Utility
Oops!!

    protected static void swap(Vector array, int i, int j) {
        Object temp;


Suppose to be:

    protected static void swap(List array, int i, int j) {
        Object temp;

0
 
LVL 92

Expert Comment

by:objects
Comment Utility
Your Sortable class/interface seems to be missing
0
 

Author Comment

by:luna621
Comment Utility
Oh, okay wait.  That was the wrong code :)

Let me try my other one.
0
 

Author Comment

by:luna621
Comment Utility
Aiyaya!  I can't figure out what I'm suppose to do with my choosePivot method:

public class QuickSort {

// ---------------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray[first..last] is an array.
// Postcondition: theArray[first..last] is sorted.
// Calls: partition.
// ---------------------------------------------------------

    public static void quickSort(Comparable[] theArray, int first, int last) {

        int pivotIndex;

        if (first < last) {
            // create the partition: S1, Pivot, S2
            pivotIndex = partition(theArray, first, last);
            // sort regions S1 and S2
            quickSort(theArray, first, pivotIndex-1);
            quickSort(theArray, pivotIndex+1, last);
        }  // END if

    }  // END quickSort

// ---------------------------------------------------------
// Partitions an array for quicksort.
// Precondition: theArray[first..last] is an array;
// first <= last.
// Postcondition: Returns the index of the pivot element of
// theArray[first..last]. Upon completion of the method,
// this will be the index value lastS1 such that
//    S1 = theArray[first..lastS1-1] <  pivot
//         theArray[lastS1]          == pivot
//    S2 = theArray[lastS1+1..last]  >= pivot
// Calls: choosePivot.
// ---------------------------------------------------------

    private static int partition(Comparable[] theArray, int first, int last) {

        // tempItem is used to swap elements in the array
        Comparable tempItem;
        // place pivot in theArray[first]
        choosePivot(theArray, first, last);
        Comparable pivot = theArray[first];   // reference pivot

        // initially, everything but pivot is in unknown
        int lastS1 = first;          // index of last item in S1

        // move one item at a time until unknown region is empty

        for (int firstUnknown = first + 1; firstUnknown <= last; ++firstUnknown) {
        // Invariant: theArray[first+1..lastS1] < pivot
        //            theArray[lastS1+1..firstUnknown-1] >= pivot
        // move item from unknown to proper region
            if (theArray[firstUnknown].compareTo(pivot) < 0) {
                // item from unknown belongs in S1
                ++lastS1;
                tempItem = theArray[firstUnknown];
                theArray[firstUnknown] = theArray[lastS1];
                theArray[lastS1] = tempItem;
            }  // end if
            // else item from unknown belongs in S2
        }  // end for

        // place pivot in proper position and mark its location
        tempItem = theArray[first];
        theArray[first] = theArray[lastS1];
        theArray[lastS1] = tempItem;
        return lastS1;
    }  // end partition

// ---------------------------------------------------------
// Chooses a pivot for quicksort's partition algorithm and
// swaps it with the first item in an array.
// Precondition: theArray[first..last] is an array;
// first <= last.
// Postcondition: theArray[first] is the pivot.
// ---------------------------------------------------------

    private static void choosePivot(Comparable[] theArray, int first, int last) {
        // ???
        // need to swap pivot w/ first
    }  // end choosePivot

} // END QuickSort
0
 

Author Comment

by:luna621
Comment Utility
Okay, how's this?

private static void choosePivot(Comparable[] theArray, int first, int last) {

     int pivotIndex;
     int mid = (first + last)/2;
         if (theArray[first].compareTo(theArray[mid])<=0) {
               if (theArray[mid] <= theArray[last]) {
                    pivotIndex = mid;
               }
               else {
                    pivotIndex = (theArray[first].compareTo(theArray[last])<=0 ? last : first);
               }
          }
          else if(theArray[last] <= theArray[mid]) {
               pivotIndex = mid;
          }
          else {
               pivotIndex = (theArray[first] <= theArray[last] ? first:last);
               swap(theArray, first pivotIndex);
          }

}  // end choosePivot


public void swap(int[] theArray, int left, int right) {

         Comparable temp = theArray[left];
         theArray[left] = theArray[right];
         theArray[right] = temp;

 } // end swap()
0
 

Author Comment

by:luna621
Comment Utility
Oh, darn:

C:\Documents and Settings\luna621\Codes\QuickSort.java:84: operator <= cannot be applied to java.lang.Comparable,java.lang.Comparable
               if (theArray[mid] <= theArray[last]) {
                                 ^
C:\Documents and Settings\luna621\Codes\QuickSort.java:91: operator <= cannot be applied to java.lang.Comparable,java.lang.Comparable
          else if(theArray[last] <= theArray[mid]) {
                                 ^
C:\Documents and Settings\luna621\Codes\QuickSort.java:95: operator <= cannot be applied to java.lang.Comparable,java.lang.Comparable
               pivotIndex = (theArray[first] <= theArray[last] ? first:last);
                                             ^
C:\Documents and Settings\luna621\Codes\QuickSort.java:96: swap(int[],int,int) in QuickSort cannot be applied to (java.lang.Comparable[],int,int)
               swap(theArray, first, pivotIndex);
               ^
C:\Documents and Settings\luna621\Codes\QuickSort.java:104: incompatible types
found   : int
required: java.lang.Comparable
         Comparable temp = theArray[left];
                                   ^
C:\Documents and Settings\luna621\Codes\QuickSort.java:106: incompatible types
found   : java.lang.Comparable
required: int
         theArray[right] = temp;
                           ^
6 errors
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
>  if (theArray[mid] <= theArray[last]) {

should be:

 if (theArray[mid].compareTo(theArray[last])<=0) {

similar for the others
0
 

Author Comment

by:luna621
Comment Utility
C:\Documents and Settings\luna621\My Documents\Codes\ReadInputArray.java:55: quickSort(java.lang.Comparable[],int,int) in QuickSort cannot be applied to (java.util.ArrayList)
                QuickSort.quickSort(resultList);
                         ^
1 error


I know I need the first and last elements of the list.  How do I get that?

input.charAt(0) & input.charAt(len)??
0
 

Author Comment

by:luna621
Comment Utility
import java.io.*;
 import java.util.*;

 public class ReadInputArray {

      public static void main (String[] arg) throws Exception {
        // Read input array

        BufferedReader readFile = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String input = "";

        File output = new File("output.txt"); // writes to output.txt
        FileOutputStream outFromFile = new FileOutputStream(output);
        PrintStream ps = new PrintStream(outFromFile);

        try {

            while((input = readFile.readLine())!=null) { // reads until there are no characters left

                ArrayList resultList = new ArrayList(); // create new ArrayList for result
                ArrayList digitsList = new ArrayList(); // create new ArrayList for ints

                int len = input.length(); // length of input
                StringBuffer sbDigits = new StringBuffer(); // create new string

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ' || c == '\t') { // if the character is a space
                        if(sbDigits.length()>0) { // join the two together
                            resultList.add(new Integer(sbDigits.toString()));
                            sbDigits = new StringBuffer();
                        } // END if
                        String space = c == ' ' ? " " : "\t" ;
                        resultList.add(space);
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

                if(sbDigits.length()>0){
                    resultList.add(new Integer(sbDigits.toString()));
                    sbDigits = new StringBuffer();
                } // END if

                QuickSort.quickSort(resultList);

                for(int i=0; i<resultList.size(); i++){
                    System.out.print(resultList.get(i));
                    ps.print(resultList.get(i)); // writes what was read to outout.txt
                } // END for
            } // END while
            System.out.println("\n\nProcess complete.  Please check your output.txt.\n");
        } // END try

        catch(NumberFormatException notInt) {
             System.out.println("Input not in correct format.  Integers only please.");
             System.out.println("Program will now exit.\n");
        } // END catch

      } // END main()


 } // END class ReadInputArray
0
 
LVL 19

Expert Comment

by:ramazanyich
Comment Utility
If you are using JDK1.3 it is possible to use RMI over HTTP using special HTTP tunneling.
see http://java.sun.com/j2se/1.3/docs/guide/rmi/faq.html#firewall for details.
Hope that can help.
0
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 19

Expert Comment

by:ramazanyich
Comment Utility
Sorry, I had a lot of windows open. That reply mentioned to be in another topic.
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
you need to convert your List to an array, using it toArray() method and sort that array.

0
 

Author Comment

by:luna621
Comment Utility
What do you mean?

public static void quickSort(Comparable[] theArray, int first, int last) {
    theArray = (ArrayList)theArray;
...
}
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
No when you calling it, you have a List, but the QuickSort class expects an array.
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
QuickSort.quickSort((Comparable[])resultList.toArray(new Comparable[0], 0, resultList.size()-1);
0
 

Author Comment

by:luna621
Comment Utility
java:55: cannot resolve symbol
symbol  : method toArray (java.lang.Comparable[],int,int)
location: class java.util.ArrayList
                QuickSort.quickSort((Comparable[])resultList.toArray(new Comparable[0], 0, resultList.size()-1));
                                                            ^
java:55: quickSort(java.lang.Comparable[],int,int) in QuickSort cannot be applied to (java.lang.Comparable[])
                QuickSort.quickSort((Comparable[])resultList.toArray(new Comparable[0], 0, resultList.size()-1));
                         ^
2 errors

Is this because I can't make the resultList a Comparable[]??
0
 
LVL 12

Expert Comment

by:Giant2
Comment Utility
>Is this because I can't make the resultList a Comparable[]??

No.
Because the method quickSort give 3 parameters and you have specified only one.

Bye, Giant.
0
 
LVL 12

Expert Comment

by:Giant2
Comment Utility
I believe your calling must be like following:
QuickSort.quickSort((Comparable[])resultList.toArray(), 0, resultList.size()-1));
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
woops, I missed a ). Also will need to keep a reference to the array:

Comparable[] array = (Comparable[])resultList.toArray(new Comparable[0]);
QuickSort.quickSort(array, 0, array.length-1);
0
 

Author Comment

by:luna621
Comment Utility
Exception in thread "main" java.lang.ClassCastException
        at java.lang.Integer.compareTo(Integer.java:955
        at QuickSort.choosePivot(QuickSort.java:83)
        at QuickSort.partition(QuickSort.java:42)
        at QuickSort.quickSort(QuickSort.java:16)
        at ReadInputArray.main(ReadInputArray.java:57)

-----------------------------------------------------------------------
QuickSort.choosePivot(QuickSort.java:83)
     >> if (theArray[first].compareTo(theArray[mid])<=0) {

QuickSort.partition(QuickSort.java:42)
     >> choosePivot(theArray, first, last);

QuickSort.quickSort(QuickSort.java:16)
     >> pivotIndex = partition(theArray, first, last);

ReadInputArray.main(ReadInputArray.java:57)
    >> QuickSort.quickSort(array, 0, array.length-1);
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
Thats cause you are adding String's and Integer's to your list, and you cannot compare them to sort.
0
 

Author Comment

by:luna621
Comment Utility
Okay.  Should I sort the integers first, then put them back into my digitsList?  Then, combine it with the spaces after?  Looks like I'll have to work on this tomorrow.  I'll be back.  Thank you for helping me so far!!
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
Depends how did you want them sorted
0
 
LVL 12

Expert Comment

by:Giant2
Comment Utility
With the following code you can sort Integer and String.
from b c 3 a c 28 e c 5
to 3 5 28 a b c c c e
To put the String before the Integer you must only change the line:
else if (a[i] instanceof String && pivot instanceof Integer)//String must follows Integer
with:
else if (a[i] instanceof Integer && pivot instanceof String)//Integer must follows String

Hope this could help you.
Bye, Giant.

public class QuickSort {

      public static void main(String[] args) {
            Comparable[] aa = { "b", "c", new Integer(3), "a", "c", new Integer(28), "e", "c", new Integer(5)};
            QuickSort qs = new QuickSort();
            System.out.print("FROM:");
            for (int i = 0; i < aa.length; i++)
                  System.out.print(" " + aa[i]);
            System.out.println();
            qs.quicksort(aa, 0, aa.length - 1);
            System.out.print("TO:");
            for (int i = 0; i < aa.length; i++)
                  System.out.print(" " + aa[i]);
            System.out.println();
      }

      public void quicksort(Comparable[] a, int low, int high) {
            int pivot;
            /* Termination condition! */
            if (high > low) {
                  pivot = partition(a, low, high);
                  quicksort(a, low, pivot - 1);
                  quicksort(a, pivot + 1, high);
            }
      }

      private void swap(Comparable[] a, int posx, int posy) {
            Comparable el = a[posx];
            a[posx] = a[posy];
            a[posy] = el;
      }

      public int partition(Comparable[] a, int low, int high) {
            int piv = ((high - low) / 2) + low;
            Comparable pivot = a[piv];
            int last = high;
            int i = low;
            while (i < last) {
                  boolean invert = false;
                  if (a[i].getClass().getName().equals(pivot.getClass().getName()) && a[i].compareTo(pivot) >= 0)
                        invert = true;
                  else if (a[i] instanceof String && pivot instanceof Integer)//String must follows Integer
                        invert = true;
                  if (invert) {
                        if (piv == i) {
                              swap(a, piv, piv + 1);
                              piv = piv + 1;
                        } else {
                              swap(a, i, last);
                              if (piv == last) {
                                    piv = i;
                              }
                              last--;
                        } //end if else piv==i
                  } else
                        i++;
            } //end while i
            return piv;
      }

}
0
 

Author Comment

by:luna621
Comment Utility
cannot resolve symbol
symbol  : method quicksort (java.lang.Comparable[],int,int)
location: class QuickSort
          qs.quicksort(aa, 0, aa.length - 1);
            ^
1 error


I'm gonna try sorting the integers first.  Then putting the sorted ints into the resultList.  I'll probably have a lot of errors, so I'll be posting soon.
0
 

Author Comment

by:luna621
Comment Utility
Darn!  It compiles, but it doesn't sort it:

                ArrayList resultList = new ArrayList(); // create new ArrayList for result
                ArrayList digitsList = new ArrayList(); // create new ArrayList for ints

                int len = input.length(); // length of input
                StringBuffer sbDigits = new StringBuffer(); // create new string

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ' || c == '\t') { // if the character is a space
                        if(sbDigits.length()>0) { // join the two together
                            Comparable[] array = (Comparable[])digitsList.toArray(new Comparable[0]);   <<<<<<
                            QuickSort.quickSort(array, 0, array.length-1);  <<<<<<
                            sbDigits = (StringBuffer) sbDigits; <<<<<<
                            resultList.add(new Integer(sbDigits.toString()));
                            sbDigits = new StringBuffer();
                        } // END if
                        String space = c == ' ' ? " " : "\t" ;
                        resultList.add(space);
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for
0
 

Author Comment

by:luna621
Comment Utility
Comment from Giant2
Date: 09/07/2004 05:17AM HST

With the following code you can sort Integer and String.
from b c 3 a c 28 e c 5
to 3 5 28 a b c c c e
----------------------------------------------------------------------------------
Thank you, I understand what you're saying.  Sorry, I should have clarified.  My program only excepts integers, spaces, and tabs.  So, you can throw the String idea out :)

Basically, I just need my QuickSort to sort like how this did:

            Collections.sort(digitsList);

            int num=0;
            for (int i=0; i<resultList.size(); i++){
                if (resultList.get(i) instanceof Integer){
                    resultList.set(i,digitsList.get(num));
                    num++;
                }// END if
            }// END for


Example:

  input: 11 _ 2 _ _ 53 <tab> 0 _ _ _ 28
output: 0 _ 2 _ _ 11 <tab> 28 _ _ _ 53


The code already takes care of the spaces and tabs.  It's just the quicksort is not working.
 
0
 

Author Comment

by:luna621
Comment Utility
Comment from objects  feedback
Date: 09/06/2004 11:16PM HST

Depends how did you want them sorted
-------------------------------------------------------------------------

Like how I have in my example above.  Okay, changed the code a little, but it still doesn't work:

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ' || c == '\t') { // if the character is a space
                        if(sbDigits.length()>0) { // join the two together

                            // Sort input array in increasing order
                            Comparable[] array = (Comparable[])digitsList.toArray(new Comparable[0]);
                            QuickSort.quickSort(array, 0, array.length-1);
                            resultList.add(new Integer(sbDigits.toString()));
                            sbDigits = new StringBuffer();
                        } // END if
                        String space = c == ' ' ? " " : "\t" ;
                        resultList.add(space);
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

How do I add the Comparable[] array to the resultList?  Or, is that not possible?
0
 

Author Comment

by:luna621
Comment Utility
Okay, how about if I forget about the spacing for now.  So as long as the integers are separated by spaces or tabs, that line is an acceptable input.  Then, have the quicksort sort it.

Example:

  input: 8 _ _ 3 _ 24 _ _ _ 2 <tab> 66 _ 14
output: 2 _ 3 _ 8 _ 24 _ 66
0
 
LVL 92

Expert Comment

by:objects
Comment Utility
you need to sort *after* you have added all the numbers to the list, no point sorting every time you add a number.
And then use the contents of the array *not* the contents of resultList (which remains in original order)
0
 

Author Comment

by:luna621
Comment Utility
Yeah, found that out the hard way :)

Anyways, I started over - tried to simplify it.  Is this approach better?:

      public static void main (String[] arg) throws Exception {

        try {

// 1. Read a string from the file
            BufferedReader in = new BufferedReader(new FileReader("input.txt"));
            String input = "";

            while ((input = in.readLine()) != null) {

                try {
                // process(input) - make sure input in correct format

// 2. Tokenize 'str' using a StringTokenizer and store all tokens into an array
            StringTokenizer parser = new StringTokenizer(aString);

            while (parser.hasMoreTokens()) {
                //processWord(parser.nextToken()) - store into array
            } // END while

// stop tokenizing

//3. Apply quicksort
// stop quicksort

//4. Write the string 'input' to the output.txt file.
// stop output

                } // END try

                catch(NumberFormatException notInt) {
                    System.out.println("Input not in correct format.  Integers, spaces, or tabs only please.");
                    System.out.println("Program will now exit.\n");
                    System.exit(0);
                } // end catch

            } // END while

            in.close();

// stop read from file

        } // END try

        catch (IOException e) {
            System.out.println("Could not read from input.txt.");
            System.out.println("Program will now exit.\n");
            System.exit(0);
        } // END catch
0
 

Author Comment

by:luna621
Comment Utility
>>     // 2. Tokenize 'str' using a StringTokenizer and store all tokens into an array

Should read:  // 2. Tokenize 'input' using a StringTokenizer and store all tokens into an array
0
 
LVL 16

Expert Comment

by:gnoon
Comment Utility
I would suggest using Collections.sort() (mergesort nlog(n) performance) for easier programing.

            ArrayList resultList = new ArrayList(); // create new ArrayList for result
            ArrayList digitsList = new ArrayList(); // create new ArrayList for ints

            while((input = readFile.readLine())!=null) { // reads until there are no characters left

                int len = input.length(); // length of input
                StringBuffer sbDigits = new StringBuffer(); // create new string

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                    char c = input.charAt(i);
                    if(c == ' ' || c == '\t') { // if the character is a space
                        if(sbDigits.length()>0) { // join the two together
                            Integer num = new Integer(sbDigits.toString());
                            digitsList.add(num);
                            resultList.add(num);
                            sbDigits = new StringBuffer();
                        } // END if
                        String space = c == ' ' ? "_" : "\t" ;
                        resultList.add(space);
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

                if(sbDigits.length()>0){
                    Integer num = new Integer(sbDigits.toString());
                    digitsList.add(num);
                    resultList.add(num);
                    sbDigits = new StringBuffer();
                } // END if

                resultList.add("\n"); // new line
            } // END while

            int numIndex = 0;
            Collections.sort(digitsList); // sort them
            Iterator it = digitsList.iterator();
            for(int i=0; i<resultList.size(); i++){
                Object o = resultList.get(i);
                if(o instanceof Integer)
                {
                    o = it.hasNext() ? it.next() : "" ;
                }
                System.out.print(o);
                ps.print(o); // writes what was read to outout.txt
            } // END for
0
 

Author Comment

by:luna621
Comment Utility
> Comment from gnoon
> Date: 09/07/2004 05:05PM HST
>
> I would suggest using Collections.sort() (mergesort nlog(n) performance) for easier programing.
------------------------------------------------------------------------------------------------------------------------------------

Yes, someone previously suggested that (think it was in another post).  But, I wanted my code to call on my QuickSort code (located in another class).  That's why I decided to scrap the idea I started with.  Forget about the spacing and the tabs in the right places.  I just need to:

1. Check if input is correct: only integers, spaces, and tabs; no letters, special characters, etc.
    Example of correct input:  10 _ 3 _ _ 4 <tab> 7
                  incorrect input:  1 _ abc _ * <tab> e4

2. Tokenize the string, and store into array.
         array =>    |10 | 3 | 4 | 7 |

3. Quicksort array =>  | 3 | 4 | 7 |10 |

4. Pretty print array: 3 _ 4 _ 7 _ 10

0
 

Author Comment

by:luna621
Comment Utility
So, would I basically do the same thing:

            ArrayList digitsList = new ArrayList(); // create new ArrayList for ints

            while((input = readFile.readLine())!=null) { // reads until there are no characters left

                int len = input.length(); // length of input
                StringBuffer sbDigits = new StringBuffer(); // create new string

                // reads through input to finds ints and spaces
                for(int i=0; i<len; i++) {
                        if(sbDigits.length()>0) { // join the two together
                            Integer num = new Integer(sbDigits.toString());
                            digitsList.add(num);
                            sbDigits = new StringBuffer();
                        } // END if
                    } // END if
                    else {
                        sbDigits.append(c);
                    } // END else
                } // END for

                if(sbDigits.length()>0){
                    Integer num = new Integer(sbDigits.toString());
                    digitsList.add(num);
                    sbDigits = new StringBuffer();
                } // END if
            } // END while
0
 

Author Comment

by:luna621
Comment Utility
Whoops!  Take this out:

                    else {
                        sbDigits.append(c);
                    } // END else
0
 

Author Comment

by:luna621
Comment Utility
Hmm... okay.  I think it's not storing into the array.  Ah!  I need to Tokenize the string, then store it right?  How would I do that?

            while (input.hasMoreTokens()) {
                digitsList.add(input.nextToken()); <<-------------  ?????
            } // END while
0
 

Author Comment

by:luna621
Comment Utility
           StringTokenizer ints = new StringTokenizer(input);

            while (ints.hasMoreTokens()) {
                digitsList.add(ints.nextToken()); //<<-------------  ?????
            } // END while
0
 

Author Comment

by:luna621
Comment Utility
Okay, got it to Tokenize... but it's still not sorting...


        while((input = readFile.readLine())!=null) { // reads until there are no characters left

            StringTokenizer ints = new StringTokenizer(input);

            while (ints.hasMoreTokens()) {
                digitsList.add(ints.nextToken() + " ");
            } // END while

            Comparable[] array = (Comparable[])digitsList.toArray(new Comparable[0]);
            QuickSort.quickSort(array, 0, array.length-1);

            // Output the resulting array
            for(int i=0; i<digitsList.size(); i++){
                System.out.print(digitsList.get(i));
                ps.print(digitsList.get(i)); // writes what was read to output.txt
            } // END for
            System.out.println("\n\nProcess complete.  Please check your output.txt.\n");
        } // END while
0
 

Author Comment

by:luna621
Comment Utility
Aiyaya!  It's also accepting letters and special characters.  How do I make it accept integers only?
0
 

Author Comment

by:luna621
Comment Utility
Okay, does this Tokenizer look better?

        try {
            // Read input from input.txt
            while((input = readFile.readLine())!=null) { // reads until there are no characters left

                // separates the ints from the spaces

                StringBuffer sbDigits = new StringBuffer(); // create new string

                StringTokenizer st = new StringTokenizer(input);
                int numElements = 0;
                if ((numElements = st.countTokens()) > 0) {
                    String[] tempString = input.split(" ");
                    int index = 0;
                    while (st.hasMoreTokens()) {
                        tempString[index++] = st.nextToken();
                    } // END while
                } // END if

// need to sort...


                // Output the resulting array
                for(int i=0; i<digitsList.size(); i++){
                    System.out.print(digitsList.get(i));
                    ps.print(digitsList.get(i)); // writes what was read to output.txt
                } // END for
                System.out.println("\n\nProcess complete.  Please check your output.txt.\n");
            } // END while
        } // END try

        // checks for data in correct format - integers, spaces, and tabs only
        catch(NumberFormatException notInt) {
             System.out.println("Input not in correct format.  Integers, spaces, or tabs only please.");
             System.out.println("Program will now exit.\n");
        } // END catch
0
 

Author Comment

by:luna621
Comment Utility
How do I make it an integer array instead of a String array.  I tried changing it to int[], but it wouldn't let me use the .split()...

                    String[] intArray = input.split(" ");
                    int index = 0;
                    while (st.hasMoreTokens()) {
                        intArray[index++] = st.nextToken();
                       
                    } // END while
0
 

Author Comment

by:luna621
Comment Utility
Okay, this page is starting to get too long.  I'll post another question to continue this one.  Thank you for all who helped  :)
0
 
LVL 16

Expert Comment

by:gnoon
Comment Utility
>Forget about the spacing and the tabs in the right places.
>I just need to:
>    1. Check if input is correct: only integers, spaces, and tabs; no letters, special characters, etc.
>    2. ...

There's a class, named StreamTokenizer, which can get only numbers from a string(read from file) and can check for non-digit character. It's easy to use. :)

Thank for acceptation.
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now