New Topic/Question
Reply
public class OrderedStringList {
int max = 100;
String strArray[] = new String[max];
int count = 0;
public static void main(String[] args) {
OrderedStringList test = new OrderedStringList();
// does nothing really with out driver class
}
public void add(String str) {
if (count == 0) {
strArray[0] = str;
count++;
} else {
int result = binarySearch(str);
if (result == -999) {
String temp = strArray[0];
strArray[0] = str;
reorderArray(1, temp);
count++;
} else {
System.out.println(result);
if (result > 0) {
String temp = strArray[result];
strArray[result] = str;
reorderArray(result + 1, temp);
count++;
} else {
String temp = strArray[Math.abs(result)];
strArray[Math.abs(result)] = str;
reorderArray(Math.abs(result) + 1, temp);
count++;
}
}
}
}
public boolean remove(int badIndex) {
if (badIndex < count - 1 && badIndex > 0) {
for (int i = badIndex; i < count - 2; i++) // reorderes items in
// array to keep in
// order
{
strArray[i] = strArray[i + 1];
}
strArray[count - 1] = null;
count--;
return true; // returns true since operation sucessful
} else {
return false;// remove failed
}
}
public void removeAll() {
strArray = new String[max];
count = 0;
}
public String returnStr(int index) {
return strArray[index];
}
public int returnSize() {
return count;
}
public int binarySearch(String searchItem) {
int first = 0;
int last = count - 1;
int mid = 0;
boolean found = false;
// Loop until found or end of list.
if (count == 0) {
System.out.println("No items in list");
return -1;
} else {
while (first <= last && !found) {
// Find the middle.
mid = (first + last) / 2;
// Compare the middle item to the search item.
if (strArray[mid].compareTo(searchItem) == 0)
found = true;
else { // Not found, readjust search parameters, halving the
// size &
// start over.
if (strArray[mid].compareTo(searchItem) > 0) {
last = mid - 1;
} else {
first = mid + 1;
}
}
}
if (found)
return mid;
else {
if (mid == 0) {
return -999; // value isnt in array but should be
// inserted to index 0
} else {
return mid * -1;
}
}
}
}
public String toString() {
if (count == 0) {
return "No items in list";
} else {
String response = "";
for (int i = 0; i <= count - 1; i++) {
response = response + " " + strArray[i];
}
return response;
}
}
private void reorderArray(int begin, String newStr) {
for (int i = begin; i < count; i++) {
strArray[i] = newStr;
newStr = strArray[i + 1];
}
strArray[count] = newStr;
}
}
import java.io.*;
public class Driver {
OrderedStringList runner = new OrderedStringList();
public static void main(String[] args) throws IOException {
Driver test = new Driver();
test.menuPrompt();
}
public void menuPrompt() throws IOException {
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
int response = 100; // just a dummy initial value
while (response != 898) {
System.out.println("Please input a number for the following options");
System.out.println("Press 1 to insert item to list");
System.out.println("Press 2 to delete a item from list");
System.out.println("Press 3 to get item from list");
System.out.println("Press 4 to search for a specified item in the list.");
System.out.println("Press 5 to clear list");
System.out.println("Press 6 to print size and content of list");
System.out.println("Press 7 to exit program");
System.out.println("Please input your selection: ");
String answer = stdin.readLine();
response = Integer.parseInt(answer);
switch (response) {
case 1:
System.out.println("Selection 1 was made.");
System.out.println("Enter item : ");
String tName = stdin.readLine();
runner.add(tName);
// System.out.println("Item: "+tName+" inserted in position"+
// inputIndex+" in the list");
break;
case 2:
System.out.println("Selection 2 was made.");
System.out.println("Index of item to be deleted: ");
String t2Index = stdin.readLine();
int input2Index = Integer.parseInt(t2Index);
boolean result = runner.remove(input2Index);
if (result == true) {
System.out.println("Remove was successful");
} else {
System.out.println("Remove was unsuccessful");
}
break;
case 3:
System.out.println("Selection 3 was made");
System.out.println("Please insert a index for item, assume index starts at 0: ");
String t3Index = stdin.readLine();
int input3Index = Integer.parseInt(t3Index);
if (runner.returnStr(input3Index) != null) {
System.out.println(runner.returnStr(input3Index));
} else {
System.out.println("invalid item at specified index");
}
break;
case 4:
System.out.println("Selection 4 was made.");
System.out.println("Enter item to search for: ");
String searchResponse = stdin.readLine();
int ii = runner.binarySearch(searchResponse);
if (ii == -999) { //-999 is dummy value so i know it belongs in0 but isnt there yet
System.out.println("Item belongs at beginning of list");
} else {
if (ii > 0) {
System.out.println(searchResponse+ " was found at index: " + ii);
} else {
System.out.println(searchResponse+ " belongs in index: " + Math.abs(ii));
}
}
break;
case 5:
runner.removeAll();
System.out.println("Selection 5 was made.");
break;
case 6:
System.out.println("List contains :" + runner.returnSize()
+ " strings");
System.out.println(runner.toString());
break;
case 7:
System.out.println("Selection 7 was made, GOODBYE!!");
System.exit(1);
break;
}
}
}
}
sorry for the long post of code but i figured be the only way any one could help me by showing what im trying to do. This implemention uses a string array base and attempts a binary search by comparing two strings. This program also attempts to add the items in ascending order in lexographic terms as needed by binary searching. The possible return values are as follows for binary search,
if the response is = to a positive int then that means it is allready in the array and is located at that position. if it returns a negative value it means that the item is not in the array but should be inserted in the index when taking the absolute value of the returned index from binary search. the last return value can be -999 which means the item belongs at 0 index but is not currently in the array.
im having multiple problems.. for one it doesnt seem that my program is adding the strings to the array in the correct order, also my shifting seems to be off as even my tostring method shows null entries in the array. few other problems that when i remember ill post back =P any help would be appreciated
ill post back after school
MultiQuote
| 