001    /*
002     * Created on 21.06.2005 Filename: HeapSort.java
003     */
004    package jagafa.util;
005    
006    
007    import java.util.Comparator;
008    import java.util.Iterator;
009    import java.util.List;
010    
011    /**
012     * Sorts a list in descending order (highest first). Names can be associated to
013     * the input list. These names will be sorted simultaneously
014     * 
015     * @param <VAL_TYPE>
016     */
017    public class InsertSort<VAL_TYPE, NAME_TYPE> {
018            private Comparator<VAL_TYPE> comparator = new Comparator<VAL_TYPE>() {
019    
020                    @SuppressWarnings("unchecked")
021                    public int compare(VAL_TYPE o1, VAL_TYPE o2) {
022                            return ((Comparable<VAL_TYPE>) o1).compareTo(o2);
023                    }
024            };
025    
026            private List<VAL_TYPE> list_;
027    
028            private List<NAME_TYPE> names_;
029    
030            private Heap<NAME_TYPE> newNameList_;
031    
032            public InsertSort(List<VAL_TYPE> l, List<NAME_TYPE> names) {
033                    list_ = l;
034    
035                    this.names_ = names;
036                    this.newNameList_ = new Heap<NAME_TYPE>();
037            }
038    
039            public List<VAL_TYPE> sort(List<VAL_TYPE> l) {
040                    this.list_ = l;
041    
042                    Class<? extends Object> type = list_.get(0).getClass();
043                    if (Comparable.class.isAssignableFrom(type)) {
044    
045                    } else {
046                            return null;
047                    }
048    
049                    Heap<NAME_TYPE> newNames = new Heap<NAME_TYPE>();
050                    Heap<VAL_TYPE> newList = new Heap<VAL_TYPE>();
051                    Iterator<VAL_TYPE> iter = list_.iterator();
052                    Iterator<NAME_TYPE> nameIter = names_.iterator();
053    
054                    VAL_TYPE last = iter.next();
055                    newList.insertFirst(last);
056                    newNames.insertFirst(nameIter.next());
057                    while (iter.hasNext()) {
058                            VAL_TYPE next = iter.next();
059    
060                            boolean ok = false;
061                            for (int i = 0; i < newList.size(); i++) {
062                                    VAL_TYPE ss = newList.get(i);
063                                    if (comparator.compare(next, ss) > 0) {
064                                            newList.insert(i, next);
065                                            if (nameIter.hasNext()) {
066                                                    newNames.insert(i, nameIter.next());
067                                            }
068                                            ok = true;
069                                            break;
070                                    }
071                            }
072    
073                            if (!ok) {
074    
075                                    if (comparator.compare(next, last) < 0) {
076                                            newList.insertLast(next);
077                                            if (nameIter.hasNext()) {
078                                                    newNames.insertLast(nameIter.next());
079                                            }
080                                    } else {
081                                            newList.insertFirst(next);
082                                            if (nameIter.hasNext()) {
083                                                    newNames.insertFirst(nameIter.next());
084                                            }
085                                    }
086                            }
087    
088                            last = newList.get(0);
089    
090                    }
091                    
092                    this.newNameList_ = newNames;
093    
094                    return newList;
095            }
096    
097            public List<NAME_TYPE> getNameList() {
098                    return this.newNameList_;
099            }
100    }