In: Computer Science
package hw; public class MyArrayForDouble { double[] nums; int numElements; public MyArrayForDouble() { // Constructor. automatically called when creating an instance numElements = 0; nums = new double[5]; } public MyArrayForDouble(int capacity) { // Constructor. automatically called when creating an instance numElements = 0; nums = new double[capacity]; } public MyArrayForDouble(double[] nums1) { nums = new double[nums1.length]; for(int i=0;i<nums1.length;i++) nums[i] = nums1[i]; numElements = nums1.length; } void printArray(){ // cost, times System.out.printf("printArray(%d,%d): ",numElements,nums.length); for(int i=0; i<numElements;i++) System.out.print(nums[i]+" "); System.out.println(); } int linearSearch(double val) { for(int i=0;i<numElements;i++) if(nums[i] == val) return i; return -1; } int binarySearch(double val) { int start = 0; int end = nums.length - 1; int mid; while(start <= end) { mid = (start + end)/2; if(val == nums[mid]) return mid; else if(val < nums[mid]) end = mid-1; else // val > nums[mid] start = mid + 1; } return -1; } private void enlarge() { // double up the size of nums; double[] new_nums = new double[nums.length*2]; for(int i=0;i<numElements;i++) new_nums[i] = nums[i]; nums = new_nums; } void add(double val) { if(isFull()) // if(numElements == nums.length) enlarge(); nums[numElements] = val; numElements++; } public void addOrder(int idx, double[] valArray) { // add all elements of valArray from the specified position of nums. // need to keep order // eg) [10,20,30] --> addOrder(1,{1,2}) makes {10,1,2,20,30} ensureCapacity(numElements + valArray.length); // Here we can safely assume 'nums' has at least 'numElements + valArray.length' spaces for(int i=numElements-1; i>=idx ; i--) nums[i+valArray.length] = nums[i]; for(int i=0;i<valArray.length;i++) nums[i+idx] = valArray[i]; numElements += valArray.length; } private void ensureCapacity(int count) { if(count <= nums.length) return; // need more space double[] new_nums = new double[count]; for(int i=0;i<numElements;i++) new_nums[i] = nums[i]; nums = new_nums; } int remove(double val){ // search for an element that is equal to val. and remove it from 'nums' int idx = linearSearch(val); if(idx < 0) return 0; // fill the location with the last element nums[idx] = nums[numElements-1]; numElements--; return 1; } // void removeAll(int val) { // worst-case: latter half elements are equal to val // // remove(10) in nums = {1, 2, 3, 2, 4, ..., 10, 10, 10, 10} // // O(N) * N = O(N*N) // // search for all the elements equal to val and remove them. // while(remove(val) > 0); // } void removeAll(double val) { // O(N) int j = 0; for(int i=0;i<numElements;i++) if(nums[i] != val) nums[j++] = nums[i]; numElements = j; } double findMin() { // return the minimum value among elements in nums; double minV = nums[0]; for(int i=1;i<numElements;i++) if( nums[i] < minV ) minV = nums[i]; return minV; } void sort() { // There is a bug in this code. Find it. // sort 'nums' in ascending order. eg) 10, 20 , 30 for(int i=0;i<numElements-1;i++) { int minIdx = i; for(int j=i+1;j<numElements;j++) if( nums[j] < nums[minIdx]) minIdx = j; // swap between nums[i] and nums[minIdx] double temp = nums[i]; nums[i] = nums[minIdx]; nums[minIdx] = temp; } } double[] toArray() { // return a copy of the array only with valid elements //return nums; // this is not a right to return a copy. double[] new_nums = new double[numElements]; for(int i=0;i<numElements;i++) new_nums[i] = nums[i]; return new_nums; } public MyArrayForDouble clone(){ // return a copy of this instance/object MyArrayForDouble nums1 = new MyArrayForDouble(this.toArray()); return nums1; } public void clear() { numElements = 0; } // In the above class ‘MyArray’, define a new method ‘getElements(int start, int end)’ // that returns a new array. The new array should have elements // of ‘nums’ from index ‘start’ to ‘end’ inclusively. // For example, suppose nums = {10,20,30,40,50}. Then getElements(2,4) // returns a new array {30,40,50}. Assume that index ‘start’ and ‘end’ are valid // (you don’t need to check their validity). public double[] getElements(int start, int end) { double[] new_nums = new double[end-start+1]; for(int i= start; i <= end ; i++) new_nums[i-start] = nums[i]; return new_nums; } boolean isEmpty() { return numElements == 0; } boolean isFull() { return numElements==nums.length; } }
Second bit of code on a separate file
package hw; public class MyArrayDemo { static void printArray(int[] nums){ for(int i=0; i<nums.length;i++) System.out.print(nums[i]+" "); System.out.println(); } public static void main(String[] args) { // MyArrayForDouble mynums1 = new MyArrayForDouble(); // mynums1.add(10.5); mynums1.add(1.9); mynums1.add(-0.2); mynums1.add(10.5); mynums1.printArray(); // System.out.println(mynums1.linearSearch(1.9)); // mynums1.remove(1.9); mynums1.printArray(); // mynums1.removeAll(10.5); mynums1.printArray(); // Add your code to test MyArrayForString and MyArrayForChar // --> Required. } }
Hi. I have answered the same question before (code for MyArrayForString.java, MyArrayForChar.java and updated MyArrayDemo.java files). Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks
//MyArrayForString.java
public class MyArrayForString {
String[] strings;
int numElements;
public MyArrayForString() { // Constructor. automatically called when
// creating an instance
numElements = 0;
strings = new String[5];
}
public MyArrayForString(int capacity) { // Constructor. automatically called
// when creating an instance
numElements = 0;
strings = new String[capacity];
}
public MyArrayForString(String[] strings1) {
strings = new String[strings1.length];
for (int i = 0; i < strings1.length; i++)
strings[i] = strings1[i];
numElements = strings1.length;
}
void printArray() { // cost, times
System.out.printf("printArray(%d,%d): ", numElements, strings.length);
for (int i = 0; i < numElements; i++)
System.out.print(strings[i] + " ");
System.out.println();
}
int linearSearch(String val) {
for (int i = 0; i < numElements; i++)
if (strings[i].equals(val))
return i;
return -1;
}
int binarySearch(String val) {
int start = 0;
int end = strings.length - 1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (val.equals(strings[mid]))
return mid;
else if (val.compareTo(strings[mid]) < 0)
end = mid - 1;
else
start = mid + 1;
}
return -1;
}
private void enlarge() {
// String up the size of strings;
String[] new_strings = new String[strings.length * 2];
for (int i = 0; i < numElements; i++)
new_strings[i] = strings[i];
strings = new_strings;
}
void add(String val) {
if (isFull())
enlarge();
strings[numElements] = val;
numElements++;
}
public void addOrder(int idx, String[] valArray) {
// add all elements of valArray from the specified position of strings.
// need to keep order
ensureCapacity(numElements + valArray.length);
// Here we can safely assume 'strings' has at least 'numElements +
// valArray.length' spaces
for (int i = numElements - 1; i >= idx; i--)
strings[i + valArray.length] = strings[i];
for (int i = 0; i < valArray.length; i++)
strings[i + idx] = valArray[i];
numElements += valArray.length;
}
private void ensureCapacity(int count) {
if (count <= strings.length)
return;
// need more space
String[] new_strings = new String[count];
for (int i = 0; i < numElements; i++)
new_strings[i] = strings[i];
strings = new_strings;
}
int remove(String val) {
// search for an element that is equal to val. and remove it from 'strings'
int idx = linearSearch(val);
if (idx < 0)
return 0;
// fill the location with the last element
strings[idx] = strings[numElements - 1];
numElements--;
return 1;
}
void removeAll(String val) { // O(N)
int j = 0;
for (int i = 0; i < numElements; i++)
if (strings[i] != val)
strings[j++] = strings[i];
numElements = j;
}
String findMin() {
// return the minimum value among elements in strings;
String minV = strings[0];
for (int i = 1; i < numElements; i++)
if (strings[i].compareTo(minV) < 0)
minV = strings[i];
return minV;
}
void sort() {
for (int i = 0; i < numElements - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < numElements; j++)
if (strings[j].compareTo(strings[minIdx]) < 0)
minIdx = j;
// swap between strings[i] and strings[minIdx]
String temp = strings[i];
strings[i] = strings[minIdx];
strings[minIdx] = temp;
}
}
String[] toArray() {
// return a copy of the array only with valid elements
String[] new_strings = new String[numElements];
for (int i = 0; i < numElements; i++)
new_strings[i] = strings[i];
return new_strings;
}
public MyArrayForString clone() {
// return a copy of this instance/object
MyArrayForString strings1 = new MyArrayForString(this.toArray());
return strings1;
}
public void clear() {
numElements = 0;
}
public String[] getElements(int start, int end) {
String[] new_strings = new String[end - start + 1];
for (int i = start; i <= end; i++)
new_strings[i - start] = strings[i];
return new_strings;
}
boolean isEmpty() {
return numElements == 0;
}
boolean isFull() {
return numElements == strings.length;
}
}
//MyArrayForChar.java
public class MyArrayForChar {
char[] chars;
int numElements;
public MyArrayForChar() {
numElements = 0;
chars = new char[5];
}
public MyArrayForChar(int capacity) {
numElements = 0;
chars = new char[capacity];
}
public MyArrayForChar(char[] chars1) {
chars = new char[chars1.length];
for (int i = 0; i < chars1.length; i++)
chars[i] = chars1[i];
numElements = chars1.length;
}
void printArray() { // cost, times
System.out.printf("printArray(%d,%d): ", numElements, chars.length);
for (int i = 0; i < numElements; i++)
System.out.print(chars[i] + " ");
System.out.println();
}
int linearSearch(char val) {
for (int i = 0; i < numElements; i++)
if (chars[i] == val)
return i;
return -1;
}
int binarySearch(char val) {
int start = 0;
int end = chars.length - 1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (val == chars[mid])
return mid;
else if (val < chars[mid])
end = mid - 1;
else
// val > chars[mid]
start = mid + 1;
}
return -1;
}
private void enlarge() {
// double up the size of chars;
char[] new_chars = new char[chars.length * 2];
for (int i = 0; i < numElements; i++)
new_chars[i] = chars[i];
chars = new_chars;
}
void add(char val) {
if (isFull())
enlarge();
chars[numElements] = val;
numElements++;
}
public void addOrder(int idx, char[] valArray) {
// add all elements of valArray from the specified position of chars.
// need to keep order
// eg) [10,20,30] --> addOrder(1,{1,2}) makes {10,1,2,20,30}
ensureCapacity(numElements + valArray.length);
// Here we can safely assume 'chars' has at least 'numElements +
// valArray.length' spaces
for (int i = numElements - 1; i >= idx; i--)
chars[i + valArray.length] = chars[i];
for (int i = 0; i < valArray.length; i++)
chars[i + idx] = valArray[i];
numElements += valArray.length;
}
private void ensureCapacity(int count) {
if (count <= chars.length)
return;
// need more space
char[] new_chars = new char[count];
for (int i = 0; i < numElements; i++)
new_chars[i] = chars[i];
chars = new_chars;
}
int remove(char val) {
// search for an element that is equal to val. and remove it from 'chars'
int idx = linearSearch(val);
if (idx < 0)
return 0;
// fill the location with the last element
chars[idx] = chars[numElements - 1];
numElements--;
return 1;
}
void removeAll(char val) { // O(N)
int j = 0;
for (int i = 0; i < numElements; i++)
if (chars[i] != val)
chars[j++] = chars[i];
numElements = j;
}
char findMin() {
// return the minimum value among elements in chars;
char minV = chars[0];
for (int i = 1; i < numElements; i++)
if (chars[i] < minV)
minV = chars[i];
return minV;
}
void sort() {
// sort 'chars' in ascending order. eg) 10, 20 , 30
for (int i = 0; i < numElements - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < numElements; j++)
if (chars[j] < chars[minIdx])
minIdx = j;
// swap between chars[i] and chars[minIdx]
char temp = chars[i];
chars[i] = chars[minIdx];
chars[minIdx] = temp;
}
}
char[] toArray() {
// return a copy of the array only with valid elements
// return chars;
char[] new_chars = new char[numElements];
for (int i = 0; i < numElements; i++)
new_chars[i] = chars[i];
return new_chars;
}
public MyArrayForChar clone() {
// return a copy of this instance/object
MyArrayForChar chars1 = new MyArrayForChar(this.toArray());
return chars1;
}
public void clear() {
numElements = 0;
}
public char[] getElements(int start, int end) {
char[] new_chars = new char[end - start + 1];
for (int i = start; i <= end; i++)
new_chars[i - start] = chars[i];
return new_chars;
}
boolean isEmpty() {
return numElements == 0;
}
boolean isFull() {
return numElements == chars.length;
}
}
//MyArrayDemo.java
import java.util.Arrays;
public class MyArrayDemo {
//method to test MyArrayForDouble
static void testMyArrayForDouble() {
MyArrayForDouble mynums1 = new MyArrayForDouble();
mynums1.add(10.5);
mynums1.add(1.9);
mynums1.add(-0.2);
mynums1.add(10.5);
mynums1.add(3.5);
mynums1.add(18.2);
mynums1.printArray();
System.out.println("Min value: " + mynums1.findMin());
mynums1.sort();
System.out.println("sorted");
mynums1.printArray();
System.out.print("get elements between indices 2 and 4: ");
System.out.println(Arrays.toString(mynums1.getElements(2, 4)));
System.out.println("linear search for 1.9: "
+ mynums1.linearSearch(1.9));
System.out.println("binary search for 3.5: "
+ mynums1.binarySearch(3.5));
System.out.println("removing 1.9");
mynums1.remove(1.9);
mynums1.printArray();
System.out.println("removing all occurrences of 10.5");
mynums1.removeAll(10.5);
mynums1.printArray();
}
//method to test MyArrayForString
static void testMyArrayForString() {
MyArrayForString myArray = new MyArrayForString();
myArray.add("david");
myArray.add("john");
myArray.add("adam");
myArray.add("mary");
myArray.add("beric");
myArray.add("kate");
myArray.add("david");
myArray.printArray();
System.out.println("Min value: " + myArray.findMin());
myArray.sort();
System.out.println("sorted");
myArray.printArray();
System.out.print("get elements between indices 2 and 4: ");
System.out.println(Arrays.toString(myArray.getElements(2, 4)));
System.out.println("linear search for mary: "
+ myArray.linearSearch("mary"));
System.out.println("binary search for john: "
+ myArray.binarySearch("john"));
System.out.println("removing mary");
myArray.remove("mary");
myArray.printArray();
System.out.println("removing all occurrences of david");
myArray.removeAll("david");
myArray.printArray();
}
//method to test MyArrayForChar
static void testMyArrayForChar() {
MyArrayForChar myArray = new MyArrayForChar();
myArray.add('d');
myArray.add('j');
myArray.add('a');
myArray.add('m');
myArray.add('b');
myArray.add('k');
myArray.add('d');
myArray.printArray();
System.out.println("Min value: " + myArray.findMin());
myArray.sort();
System.out.println("sorted");
myArray.printArray();
System.out.print("get elements between indices 2 and 4: ");
System.out.println(Arrays.toString(myArray.getElements(2, 4)));
System.out.println("linear search for m: "
+ myArray.linearSearch('m'));
System.out.println("binary search for j: "
+ myArray.binarySearch('j'));
System.out.println("removing m");
myArray.remove('m');
myArray.printArray();
System.out.println("removing all occurrences of d");
myArray.removeAll('d');
myArray.printArray();
}
public static void main(String[] args) {
//calling all three test methods
testMyArrayForDouble();
System.out.println();
testMyArrayForString();
System.out.println();
testMyArrayForChar();
}
}
OUTPUT
printArray(6,10): 10.5 1.9 -0.2 10.5 3.5 18.2
Min value: -0.2
sorted
printArray(6,10): -0.2 1.9 3.5 10.5 10.5 18.2
get elements between indices 2 and 4: [3.5, 10.5, 10.5]
linear search for 1.9: 1
binary search for 3.5: 2
removing 1.9
printArray(5,10): -0.2 18.2 3.5 10.5 10.5
removing all occurrences of 10.5
printArray(3,10): -0.2 18.2 3.5
printArray(7,10): david john adam mary beric kate david
Min value: adam
sorted
printArray(7,10): adam beric david david john kate mary
get elements between indices 2 and 4: [david, david, john]
linear search for mary: 6
binary search for john: 4
removing mary
printArray(6,10): adam beric david david john kate
removing all occurrences of david
printArray(4,10): adam beric john kate
printArray(7,10): d j a m b k d
Min value: a
sorted
printArray(7,10): a b d d j k m
get elements between indices 2 and 4: [d, d, j]
linear search for m: 6
binary search for j: 4
removing m
printArray(6,10): a b d d j k
removing all occurrences of d
printArray(4,10): a b j k