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
006package fc.util;
007
008import java.util.*;
009
010/** 
011Implements a {@link java.util.Collection} that keeps it's elements in
012Sorted order. This class is internally backed by a LinkedList, therefore
013iteration is strongly preferred (and much faster) than random access of
014it's elements. This class has no equivalent in JDK 1.4 and should be
015replaced by a future JDK equivalent if available. Currently java.util
016only provides a sorted Set not a sorted Collection (like this one) that
017allows duplicate elements.
018<p>
019<b>Note that this implementation is not synchronized.</b> If multiple
020threads access a list concurrently, and at least one of the threads
021modifies the list structurally, it <i>must</i> be synchronized
022externally.  (A structural modification is any operation that adds or
023deletes one or more elements; merely setting the value of an element is not
024a structural modification.)  This is typically accomplished by
025synchronizing on some object that naturally encapsulates the list.  If no
026such object exists, the list should be "wrapped" using the
027Collections.synchronizedList method.  This is best done at creation time,
028to prevent accidental unsynchronized access to the list: 
029 <pre>
030    List list = Collections.synchronizedList(new LinkedList(...));
031 </pre>
032
033@author hursh jain
034**/
035public class SortedCollection extends AbstractCollection
036{
037final boolean dbg = true;
038List items;       //interal storage of contained items
039Comparator comparator;
040
041/**
042Constructs a new, empty SortedCollection, sorted according to the keys' natural
043order. All keys inserted into the map must implement the Comparable interface.
044Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must
045not throw a ClassCastException for any elements k1 and k2 in the map. If the
046user attempts to put a key into the map that violates this constraint, methods
047that add elements will throw a <tt>ClassCastException</tt>.
048**/
049public SortedCollection() {
050  this((Comparator)null);
051  }
052
053/**
054Constructs a sorted list containing the elements of the specified
055collection. The elements are sorted according to the elements' natural 
056order
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**/
061public SortedCollection(Collection c) {
062  this((Comparator)null);
063  addAll(c);
064  }
065
066/**
067Constructs a new, empty SortedCollection, sorted according to the given comparator.
068All keys inserted into the map must be mutually comparable by the given
069comparator: comparator.compare(k1, k2) must not throw a ClassCastException for
070any keys k1 and k2 in the map. If the user attempts to put a key into the map
071that 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**/
077public SortedCollection(Comparator c) 
078  {
079  comparator = c;
080  items = new LinkedList();
081  }
082
083
084public 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
110public Iterator iterator() {
111  return items.iterator();
112  }
113  
114public int size() {
115  return items.size();
116  } 
117
118public String toString()  {
119  return items.toString();
120  }
121
122/**
123Compares two keys using the correct comparison method for this SortedCollection. That
124is to say, if a {@link java.util.Comparator} is set for this class, then it
125will be used for the comparison, otherwise the specified objects will be
126compared via a cast to {@link java.lang.Comparable}
127**/
128private 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  
136public 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