# how to write generic extensions for standard collection types in java?

I am a Java beginner and I am looking for an idiomatic way of writing a function that involves generics. I wrote this helper class (below) that pushes items into a sorted generic collection and I wanted to ask for your feedback. Should I perhaps extends some base class of some collection? Or maybe there is some better approach that follows the Java philosophy?

import java.util.Comparator;
import java.util.List;

public abstract class ListExtensions {
public static <T> void addOnCompare(List<T> collection, T item,
Comparator<T> comparator) {
synchronized(collection) {
int i = 0;
int size = collection.size();
if (size == 1) {
int diff = comparator.compare(item, collection.get(0));
switch(diff) {
case 1: i++; break;
default: break;
}
} else {
int range = size - 1;
i = size / 2;
int left = 0;
int right = range;
while(true) {
if (i <= 0) { i = 0; break; }
if (i > range) { i = range; break; }
int diff = comparator.compare(item, collection.get(i));
if (diff == 0) break;
else {
if (diff == -1) right = i;
if (diff == 1) left = i;
int near = i + diff;
if (near < 0) { i = 0; break; }
if (near > range) { i = range + 1; break; }
int diff_near = comparator.compare(item, collection.get(near));
if (diff_near == 0) { i = diff_near; break; }
if (diff_near == diff) {
int step = (right-left)/2;
if (step == 0) step = 1;
switch(diff){
case -1:
right = i;
i = i - step; break;
case 1:
left = i;
i = i + step; break;
}
} else if (diff > diff_near) {
i = near; break;
} else { break; }
}
}
}
}
}
}

-
Have you seen Collections#binarySearch? link to javadoc (Java 6) –  cyroxx Nov 23 '12 at 16:55
A javadoc and/or some comments explaining the method's purpose would be very helpful. –  E-Man Nov 28 '12 at 14:50
Sorry, but that synchronized will only work if all references to the passed-in collection are also locked. Also, it won't stop people from modifying the contents of the collection, if it contains mutable classes. If you really want threadsafety, you have to copy the collections, and the contents (or make things immutable). Otherwise, I'd remove the synchronization, and document that the method isn't threadsafe. –  Clockwork-Muse Dec 28 '12 at 18:48

Parts this question have already been answered on StackOverflow - http://stackoverflow.com/a/13529644/139985 So I'm going to treat this as a simple request for a code review.

1. The method name is opaque ... addOnCompare does not clearly imply a particular action ... and there is no javadoc for the method. This immediately makes code-review hard ... because I have to try and figure out what the code is trying to do before I can comment on whether it is doing that well.

2. The parameter name collection is poor. It is a list, not a collection.

3. The local variable diff_near should be diffNear.

4. This is convoluted:

        switch(diff) {
case 1: i++; break;
default: break;
}


Write it as:

        if (diff == 1) { i = 1; }

5. I don't know what these lines are trying to do, but they are definitely wrong:

        int near = i + diff;
if (near < 0) { i = 0; break; }
if (near > range) { i = range + 1; break; }
int diff_near = comparator.compare(item, collection.get(near));


The value returned by a comparator has no meaning beyond being -ve, zero, or +ve. So adding it to the index i is going to have an unpredictable effect. Indeed, since range never changes, this code makes the behaviour of the entire algorithm too difficult to understand.

6. I'm going to hazard a guess that the method is intended to insert item at the correct position in a previously sorted list. But given the above, I have grave doubts that it will actually work for all possible (valid) comparators and all possible (sorted) input lists.

7. Even if this code did work, the performance for a linked list would be poor. The List.get(int) method for a linked list is O(N), so even an optimal binary search pattern would result in O(Nlog(N)) operations to insert one element into the linked list. A simple traversal of the list followed by an insert would be O(N).

-

Just use java.util.TreeSet. If and only if it needs to be threadsafe, use Collections.synchronizedSortedSet() to get a synchronized wrapper.

-
docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html your version, if it works correctly, has O(n) complexity. (as Stephen C already noted) TreeSet has remove and contains, as well as add, all with O(log n) –  abuzittin gillifirca Dec 28 '12 at 9:08