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