As a sample, I am developing a simple MySortedSet in java which implements SortedSet interface. It is backed up with a simple array which is E[] array.
I have several questions regarding that:
This is the class: (I am not writing entire code, instead of related parts)
public class MySortedSet<E> implements SortedSet<E>, Iterator<E> {
private E[] array;
private Comparator<? super E> _comparator;
private int size = 0;
private int capacity;
@SuppressWarnings("unchecked")
public MySortedSet() {
this.capacity = 10;
this.array = (E[]) new Object[this.capacity];
// this.array = Array.newInstance(Class<E> var,int size);
// We have to get Class<E> from outside caller.
}
}
Question 3: There is a explanation for Constructor since this is a sorted set so it is assumed the elements are sorted:
If this constructor is used to create the sorted set, it is assumed that the elements are ordered using their natural ordering (i.e., E implements Comparable).
It gets two different constructor. One is parameterless and the other one is accepting Comparator<? super E>
.
public MySortedSet() {
this.capacity = 10;
this.array = (E[]) new Object[this.capacity];
// this.array = Array.newInstance(Class<E> var,int size);
// We have to get Class<E> from outside caller.
}
public MySortedSet(Comparator<? super E> comparator) {
this._comparator = comparator;
}
If comparator
is not passed in, natural ordering should be used but I am not really sure how to accomplish it as I need to get Comparator
in some way to access compare
method. Do you guys please recommend me a way to call it so I can call it while comparing in sort
method to sort each element.
For whom they like to see whole code, please refer to this address: http://codepaste.net/4ucvsw it is not perfect but I am working on it.
Question 4: The code guide says :
Because the fastest way to search for a particular item is to use a binary search, you must ensure that the items in the collection are in sorted order at all times. This won't be as hard to achieve as it may seem. When you insert a new item, you can assume the array you are inserting it into is already sorted. So all you need to do is find the position in the array where the new item belongs, shift everything greater than the new item one slot to the right, and insert the new item. This is called insertion sort.
Here is the sort
method logic. I am needed to make binary search to find where a new item belongs to so I can insert the new item in that place and move the other one slot to the right.
But I am not really sure how binary search will work for me here since I am not really sure what I need to find. I am given the item to add not the item to find. Instead what I think is to compare each element with the one I need to add and when I find the last smaller and first greater item, then I will get the first greater item's index, move them to the right and add new item at the index.