Reputation: 379
Sorted Vector - AddItem
I have written a sorted vector which works fully. However my Add method is very long and I feel like there is a lot of redundant code.
I have a binary search function written and I would like to use this in my Add method instead of doing comparisons in the Add function also.
Below is my code:
public class SortedVector
{
private int maxcap = 10, noOfItems = 0, grow = 10;
private String[] data = new String[maxcap];
// Default Constructor
public SortedVector()
{
}
public void SetGrowBy(int growby)
{
grow = growby;
}
public int GetCapacity()
{
return maxcap;
}
public int GetNoOfItems()
{
return noOfItems;
}
public String GetItemByIndex(int index)
{
if (index > noOfItems+1 || index < 0)
{
return null;
}
else
{
String item = data[index];
return item;
}
}
public int FindItem(String search)
{
int low=0;
int high = noOfItems - 1;
return binarySearch(search, low, high);
}
public int binarySearch(String search, int low, int high)
{
if(low>high)
return -1;
int mid = (low + high)/2;
if (data[mid] == search)
return mid;
else
if (data[mid].compareToIgnoreCase(search)<0)
return binarySearch(search, mid+1, high);
else
return binarySearch(search, low, mid-1);
}
public void AddItem(String value)
{
int thirdCounter = 0;
int fourthCounter = 0;
int place3= 0;
int place4 =0;
if(maxcap > noOfItems)
{
if(noOfItems == 0)
{
data[0] = value;
noOfItems++;
}
else
{
int firstCounter = noOfItems;
for (int i=0; i < firstCounter; i++)
{
String[]temp = new String[maxcap];
if(thirdCounter == 0)
{
if (data[i].compareToIgnoreCase(value)>0)
{
for (int j=0; j < noOfItems; j++)
{
temp[j+1] = data[j];
}
data=temp;
data[0] = value;
noOfItems++;
thirdCounter++;
}
else
{
if(data[i].compareToIgnoreCase(value)<0)
{
for (int j=0; j < noOfItems; j++)
{
if (data[j].compareToIgnoreCase(value)>0)
{
if(fourthCounter ==0)
{
temp[j+1] = data[j];
place3 = j;
fourthCounter++;
}
else
{
temp[j+1] = data[j];
}
}
else
{
temp[j]=data[j];
place4 = j;
}
}
if (place3 == 0)
{
if(place4 == 0)
{
data=temp;
data[1] = value;
noOfItems++;
firstCounter++;
}
else
{
data=temp;
data[place4+1] = value;
noOfItems++;
thirdCounter++;
}
}
else
{
data=temp;
data[place3] = value;
noOfItems++;
thirdCounter++;
}
}
}
}
}
}
}
else
{
int firstCounter = 0;
maxcap = grow +maxcap;
String[]temp3 = new String[maxcap];
for (int i=0; i < noOfItems; i++)
{
if(firstCounter == 0)
{
if (data[i].compareToIgnoreCase(value)>0)
{
for (int j=0; j < noOfItems; j++)
{
temp3[j+1] = data[j];
}
data=temp3;
data[0] = value;
noOfItems++;
firstCounter++;
}
else
{
int place1 = 0;
int place2 = 0;
int secondCounter = 0;
if(data[i].compareToIgnoreCase(value)<0)
{
for (int j=0; j < noOfItems; j++)
{
if (data[j].compareToIgnoreCase(value)>0)
{
if(j/2!=0 && secondCounter ==0)
{
temp3[j+1] = data[j];
place1 = j;
secondCounter++;
}
else
{
temp3[j+1] = data[j];
}
}
else
{
temp3[j]=data[j];
place2 = j;
}
}
if (place1 == 0)
{
if(place2 == 0)
{
data=temp3;
data[1] = value;
noOfItems++;
firstCounter++;
}
else
{
data=temp3;
data[place2+1] = value;
noOfItems++;
firstCounter++;
}
}
else
{
data=temp3;
data[place1] = value;
noOfItems++;
firstCounter++;
}
}
}
}
}
}
System.out.println("adding: "+value);
}
public void DeleteItem(int index)
{
if (index < noOfItems && index >= 0)
{
data[index] = null;
if (data[index+1] != null)
{
int j = index;
for(int i = (index+1); i<noOfItems; i++)
{
data[j] = data[i];
j++;
}
}
noOfItems--;
}
System.out.println("deleted: "+index);
}
public String toString()
{
return super.toString();
}
}
Any tips on how I could do that much appreciated.
Kind Regards, Ben.
Upvotes: 0
Views: 64
Answers (3)
Reputation: 3992
The easiest way is make the binarySearch return the insertion position if the element is not found. Very much like Arrays.binarySearch does:
returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1)
So, if the return of the ret=binarySearch is negative, you only need to take -ret-1 to get the insert position.
You can even take a look to the code, its open source anyway (i.e. not only it runs, but you can use it to learn from it)
(no, I won't copy/paste that piece of code; link-only answer - take it or leave it).
Upvotes: 0
Reputation: 3206
Here it is
DEMO: https://repl.it/Eqak/0
public void AddItem(String value)
{
// Check if cursor at last
if(noOfItems + 1 == maxcap){
// Resize data
maxcap *= 2;
String[] newData = new String[maxcap];
System.arraycopy(data, 0, newData, 0, noOfItems);
data = newData;
}
// find the last element according to value
int idx = 0;
for(; idx<noOfItems; idx++){
if(data[idx].compareToIgnoreCase(value) >= 0) {
break;
}
}
// move elements if required
if(idx < noOfItems){
System.arraycopy(data, idx, data, idx+1, noOfItems-idx);
}
// set element on index
data[idx] = value;
noOfItems++;
System.out.println("adding: "+value);
}
Upvotes: 0
Reputation: 17454
Implementing the add, (binaryAdd) is almost identical to how you implemented the binary search. The code will be 99% similar.
Let say you have the following data:
+--------------------------+
|10|20|30|40|50|60|70|80|90|
+--------------------------+
You want to add 35 into it and keep the data in ascending order.
The mid value is 50, and since 35 is < 50, we are interested in 10 to 50:
+--------------+
|10|20|30|40|50|
+--------------+
The mid value is 30, and since 35 is > 30, we are interested in 30 to 50:
+--------+
|30|40|50|
+--------+
The mid value is 40, and since 35 is < 40, we are interested in 30 to 40:
+-----+
|30|40|
+-----+
When you left with 2 elements, choose either left or the right for comparison:
if you choose left, 35 > 30, so 35 should be added after 30.
if you choose right, 35 < 40, so 35 should be before after 40.
The process is similar to binary search, but instead of returning the position of the target value, you return the position to insert the value.
Upvotes: 1
Related Questions
- How to sort items on entry in Java
- How to sort a Vector from a spesific index
- What function can be used to sort a Vector?
- How to insert vector element inside vector in java
- custom sorting order for a vector
- Vector Sort JAVA
- How to sort a Vector of Vectors?
- Sort and optimize Java Vector with custom objects
- Sort a Vector of custom objects
- Sorting vector in java