Algorithims/Java - project help

Atomic Pineapple

ok....this might be a bit much to ask but i'll try anyway...

have a project to do for college, but because of family matters and some personal stuff i've dropped way behind, i knew this but we had an assesment of what we done so far today and i have to even start from the start again now so i was wondering if i could get some help....?

The project is to create a program that will read in a text document and count all the words and put them in an array and sort them, then you have to be able to search for a word the user inputs, and you have to allow the user to put in a number and then display the top count of words up to that number so if the user puts in 5 you show the count of the top 5 words.

I have the code to read in the document and put it into an array here :

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

public class DocParser {

public static void main(String [] astrArgs) {
System.out.println("Hello");
String [] astr = new String[200000];
try {
FileInputStream is = new FileInputStream(astrArgs[0]);
Reader r = new BufferedReader(new InputStreamReader(is));
StreamTokenizer st = new StreamTokenizer(r);

int i=0;
for (int val = st.nextToken(); val != st.TT_EOF; val = st.nextToken()) {
if (st.sval == null)
continue;
astr = st.sval;
// System.out.println(st.sval);
i++;
}
String [] astr2 = new String;
for (i = 0; i < astr2.length; i++) {
astr2 = astr;
System.out.println(astr2);
}
} catch (Exception e) {
e.printStackTrace();
}

}
}

but i have to sort it and then impliment the search and other things

so how do you reccomend i go about it? should i create a class to make string objects, so that it takes the string and counts how many times it comes up?

how do you impliment a insertionsort for a string or an object can only get it working for integers?

any general help and pointing in the right direction would be greatly appreciatted, i am normally good at java but for some reason i cant get my head around this...

thanks in advance

D

OfflerCrocGod

I don't think it's a good idea to have the entire program in one class - I would break it up so the main(String[] args) just creates a class instance after you pass the the constructor the file path as an argument. Then you implement all the important parts of the project by calling methods on the class so countWords() returns the number of words mostPopular(int) for the most frequent etc. I'm sure Java has in build methods you can use from Collections to do the sorting for you.

Atomic Pineapple

OfflerCrocGod wrote:

I don't think it's a good idea to have the entire program in one class - I would break it up so the main(String[] args) just creates a class instance after you pass the the constructor the file path as an argument. Then you implement all the important parts of the project by calling methods on the class so countWords() returns the number of words mostPopular(int) for the most frequent etc. I'm sure Java has in build methods you can use from Collections to do the sorting for you.

yeh were not allowed to use the in built sorting methods though, have to create a sorting algorithim ourselves

Hobbes

If your code works for integers then you only need to do a .compareTo() on the string.

instead of...

if (x > y) ...

you do

if (stringX.compareTo(stringY)) ...

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#compareTo

Hobbes

posted too soon, you would actually do..

int x = stringX.compareTo(stringY);

The value of x would denote which string is first.

Civilian_Target

OK, some good tips here. The whole point of the OO model is that you don't put everything in one class. You should have a main that does basic control flow, an IO that reads in the file, a storage object and potentially a class for the sorting.

I don't know whether using a comparator counts as using built in sorting methods, but that's what I'd recommend. If not, you should use that charAt method to extract characters in turn from the string, convert them all to the same case and see whether they're greater than or less than and move them appropriately...

Atomic Pineapple

thanks for all the help lads...

i was wondering would it be a good idea to create an object of type string that will take in the string and put some sort of counter in that object too or would it be best to do this seperately?

EDIT:

Create new arrays of word counting objects. Each object in this array should contain a word from the text file and a number representing the count of times that word occured in the text file. Two different arrays should be produced. The first should be ordered alphabetically by word and the second array should be sorted in descending order of word count, the most frequently occurring words appearing at the beginning.

actually just looking at the project description it appears i have to create a string object, i'm not quite sure what it means by a word counting object?? lecturer is useless and never explains anything correctly

Hobbes

String is an object. Do you mean make a new object that acts like a string?

If you are building an object that you need to sort in an array you are best to build a comparator.

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Comparator.html

Afuera

draffodx wrote:

actually just looking at the project description it appears i have to create a string object, i'm not quite sure what it means by a word counting object?? lecturer is useless and never explains anything correctly

From the description, I'm guessing that a word counting object would look something like this...

public class WordCountObject{

private String sWord;
private int iCount = 0;

public WordCountObject(String s){
  sWord = s;
}

public void increment(){
  iCount++;
}

public int getCount(){
  return iCount;
}

public String getWord(){
  return sWord;
}

}

You'd create one of these whenever you encounter a new word in the text file and add it to the array; incrementing the count every time the word appears.

Once you've read all of the file in you could sort it based on either the sWord or the iCount attribute. The Comparable interface or a Comparator class could be of help in sorting it but maybe your lecturer wants you to do it by hand, rather than using these?

Atomic Pineapple

cheers Afuera, i have something like that already, it has to be an object that will go through the array take in the string in the array and count how many times it has come accross the word and then increment it's count by 1, so that when it's finished i have an array of objects with the string and count in it.

@Hobbes, i have tried to use the compareTo method to change it to accept the use of strings but still cant seem to get it working.

public class SelectionSort {
  private String[] a;

  private int nElems;

  public SelectionSort(int max) {
    a = new String[max];
    nElems = 0;
  }

  public void insert(String value) {
    a[nElems] = value;
    nElems++;
  }

  public void display() {
    for (int j = 0; j < nElems; j++)
      System.out.print(a[j] + " ");
    System.out.println("");
  }

  public void selectionSort() {
    int out, in, min;

    for (out = 0; out < nElems - 1; out++) // outer loop
    {
      min = out; // minimum
      for (in = out + 1; in < nElems; in++)
        // inner loop

	int x = a[in].compareTo(a[min]);

        if (x < 0) // if min greater,
          min = in; // a new min
      swap(out, min); // swap them
    }
  }

  private void swap(int one, int two) {
    String temp = a[one];
    a[one] = a[two];
    a[two] = temp;
  }

  public static void main(String[] args) {
    int maxSize = 100;
    SelectionSort arr; // reference to array
    arr = new SelectionSort(maxSize); // create the array

    arr.insert("Hello"); // insert 10 items
    arr.insert("uello");
    arr.insert("fgello");
    arr.insert("jello");
    arr.insert("erello");
    arr.insert("fello");
    arr.insert("mello");
    arr.insert("jello");
    arr.insert("jello");
    arr.insert("jello");

    arr.display();

    arr.selectionSort();

    arr.display();
  }

}

And here's the errors...

G:\Algo\project\SelectionSort.java:34: '.class' expected
	int x = a[in].compareTo(a[min]);
            ^
G:\Algo\project\SelectionSort.java:34: not a statement
	int x = a[in].compareTo(a[min]);
        ^
G:\Algo\project\SelectionSort.java:36: cannot resolve symbol
symbol  : variable x  
location: class SelectionSort
        if (x < 0) // if min greater,
            ^
3 errors

Tool completed with exit code 1

i've tried to impliment it several ways but just keeps giving the same errors??

Civilian_Target

You can't declare a variable in a loop. You need to say

int x;
for(i=0....){
      x = ...

Atomic Pineapple

cheers yep i got it to work anyway, and the sorting works properly, just need to get a binary search working for strings and set up an object to read the sorted array and take in the words and count its occurrences :eek:

pH

You can indeed declare a variable within a for loop (as long as you only need to use it within that context). In the above case the declaration of x seems OK where it is.

In the posted code there he seems to have struck a weird compiler bug or there's something quite deep going on beyond my knowledge of java.

The for loop on line 29 has no braces so just should operate on the next line (which contains the definition of x). If I put braces around this line {int x = a[in].compareTo(a[min]);} then the compiler gives me an expected error (line 34 cannot find variable x), but with the braces omitted we get this weird '.class expected error - anyone understand what's happening?

Hobbes

You really should be putting that into a comparator. The reason for that is that you can use the calls to do a sort on your array easier for anyone else who plans to use your code.

http://www.javaworld.com/javaworld/jw-12-2002/jw-1227-sort.html?page=3

Atomic Pineapple

spot on pH that was the flaw, the loop was only looking at the one line, just put in brackets and it was fine so it was, yes hobbes i have used a comparetor, i doubt anyone else will want to use my code anyway, :rolleyes:

Hobbes

draffodx wrote:

i have used a comparetor, i doubt anyone else will want to use my code anyway, :rolleyes:

True, but most coding is maintaining someone elses work. So if it looks maintainable/upgradeable you should at least get a point for that.

Atomic Pineapple

ok i have a class that reads in the file and puts all the words into an array,

a class to do a selection sort to sort out the array in order,

i need a class to do a binary search for a word input by a user, again this seems to be easy to do for a integer but hard to do for a string? can anyone point me in the right direction?

Mutant_Fruit

Think of a string as a load of integers one after the other. Each individual char in a string can be cast to an integer...

Hobbes

Would you get away with Arrays.binarysearch ?

Atomic Pineapple

Hobbes wrote:

Would you get away with Arrays.binarysearch ?

nope, lecterurer appears to be of the opinion that anything thats easy is bad and evil and not good

Atomic Pineapple

public static boolean bsearch(Array v, String s) {
    int  left, right;
    // If the String is anywhere, it is in positions left through right-1.
    // The String is not in a position before left.
    // The String is not in a position after right-1.
    if (v.size() == 0) return false; 
    left = 0;
    right = v.size();
    while  (left != right - 1)  {
      int  m  =  (right+left)/2;
      String sm  =  (String)  v.indexOf(m);
      if (sm.compareTo(s)<0) {
          left  =  m;        // Move left to the middle.
      }  
      else if (sm.compareTo(s)>0) {
          right  =  m;       // Move right to the middle.
      }
      else  {
          left  =  m;
          right  =  m+1;
      }
    }
    return s.equals((String) v.indexOf(left));
  }

Thats what i've come up with for the binary search but it still doesnt work with the array, "public static boolean bsearch(Array v, String s)" is this the correct way to do it? it seems to have a problem with the array v.

pH

No - pass an array (of Strings) as follows:

public static boolean bsearch(String[] v, String s) {
 ...
}