Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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; }           
                    }
                }
            }
            collection.add(i, item);
        }
    }
}
share|improve this question
1  
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

2 Answers 2

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).

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.