001 // Copyright (c) 2001 Hursh Jain (http://www.mollypages.org) 002 // The Molly framework is freely distributable under the terms of an 003 // MIT-style license. For details, see the molly pages web site at: 004 // http://www.mollypages.org/. Use, modify, have fun ! 005 006 package fc.util; 007 008 import java.util.*; 009 010 /** 011 Implements a {@link java.util.Collection} that keeps it's elements in 012 Sorted order. This class is internally backed by a LinkedList, therefore 013 iteration is strongly preferred (and much faster) than random access of 014 it's elements. This class has no equivalent in JDK 1.4 and should be 015 replaced by a future JDK equivalent if available. Currently java.util 016 only provides a sorted Set not a sorted Collection (like this one) that 017 allows duplicate elements. 018 <p> 019 <b>Note that this implementation is not synchronized.</b> If multiple 020 threads access a list concurrently, and at least one of the threads 021 modifies the list structurally, it <i>must</i> be synchronized 022 externally. (A structural modification is any operation that adds or 023 deletes one or more elements; merely setting the value of an element is not 024 a structural modification.) This is typically accomplished by 025 synchronizing on some object that naturally encapsulates the list. If no 026 such object exists, the list should be "wrapped" using the 027 Collections.synchronizedList method. This is best done at creation time, 028 to prevent accidental unsynchronized access to the list: 029 <pre> 030 List list = Collections.synchronizedList(new LinkedList(...)); 031 </pre> 032 033 @author hursh jain 034 **/ 035 public class SortedCollection extends AbstractCollection 036 { 037 final boolean dbg = true; 038 List items; //interal storage of contained items 039 Comparator comparator; 040 041 /** 042 Constructs a new, empty SortedCollection, sorted according to the keys' natural 043 order. All keys inserted into the map must implement the Comparable interface. 044 Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must 045 not throw a ClassCastException for any elements k1 and k2 in the map. If the 046 user attempts to put a key into the map that violates this constraint, methods 047 that add elements will throw a <tt>ClassCastException</tt>. 048 **/ 049 public SortedCollection() { 050 this((Comparator)null); 051 } 052 053 /** 054 Constructs a sorted list containing the elements of the specified 055 collection. The elements are sorted according to the elements' natural 056 order 057 058 @param c the collection whose elements are to be placed into this list. 059 @throws NullPointerException if the specified collection is null. 060 **/ 061 public SortedCollection(Collection c) { 062 this((Comparator)null); 063 addAll(c); 064 } 065 066 /** 067 Constructs a new, empty SortedCollection, sorted according to the given comparator. 068 All keys inserted into the map must be mutually comparable by the given 069 comparator: comparator.compare(k1, k2) must not throw a ClassCastException for 070 any keys k1 and k2 in the map. If the user attempts to put a key into the map 071 that violates this constraint, methods that add elements will throw a 072 <tt>ClassCastException</tt>. 073 074 @param c the comparator that will be used to sort this map. A null value 075 indicates that the keys' natural ordering should be used. 076 **/ 077 public SortedCollection(Comparator c) 078 { 079 comparator = c; 080 items = new LinkedList(); 081 } 082 083 084 public boolean add(Object obj) 085 { 086 if (dbg) System.out.println("SortedCollection.add(" + obj + "): ENTER"); 087 boolean result = false; 088 if (items.size() == 0) { 089 //add the initial item 090 items.add(obj); 091 result = true; 092 } 093 else { 094 for (ListIterator it = items.listIterator(); it.hasNext(); /*empty*/) 095 { 096 Object item = it.next(); 097 int c = compare(item, obj); 098 if (c >= 0) { 099 int index = it.previousIndex(); 100 items.add( (index > 0) ? index : 0, obj); 101 result = true; 102 break; 103 } 104 } 105 } 106 if (dbg) System.out.println("SortedCollection.add(" + obj + "): EXIT; result=" + result + "; collection=" + items); 107 return result; 108 } 109 110 public Iterator iterator() { 111 return items.iterator(); 112 } 113 114 public int size() { 115 return items.size(); 116 } 117 118 public String toString() { 119 return items.toString(); 120 } 121 122 /** 123 Compares two keys using the correct comparison method for this SortedCollection. That 124 is to say, if a {@link java.util.Comparator} is set for this class, then it 125 will be used for the comparison, otherwise the specified objects will be 126 compared via a cast to {@link java.lang.Comparable} 127 **/ 128 private int compare(Object k1, Object k2) { 129 int result = (comparator==null ? ((Comparable)k1).compareTo(k2) : 130 comparator.compare(k1, k2)); 131 if (dbg) System.out.println("SortedCollection.compare(" + k1 + "," + k2 + "): result = " + result); 132 return result; 133 } 134 135 136 public static void main(String[] args) throws Exception 137 { 138 //AppMgr.setApp(new UnitTestingApp()); 139 List list = Arrays.asList(new String [] {"x", "c", "d", "a"}); 140 SortedCollection sc = new SortedCollection(list); 141 sc.add("z"); 142 sc.add("x"); 143 sc.add("b"); 144 sc.add("c"); 145 System.out.println(sc); 146 } 147 148 } //~class SortedCollection