Source code

001/* An object of this class is a totally ordered set.
002
003 Copyright (c) 2006-2014 The Regents of the University of California.
004 All rights reserved.
005 Permission is hereby granted, without written agreement and without
006 license or royalty fees, to use, copy, modify, and distribute this
007 software and its documentation for any purpose, provided that the above
008 copyright notice and the following two paragraphs appear in all copies
009 of this software.
010
011 IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
012 FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
013 ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
014 THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
015 SUCH DAMAGE.
016
017 THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
018 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
019 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
020 PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
021 CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
022 ENHANCEMENTS, OR MODIFICATIONS.
023
024 PT_COPYRIGHT_VERSION_2
025 COPYRIGHTENDKEY
026
027 */
028package ptolemy.actor.util;
029
030import java.util.Collections;
031import java.util.Comparator;
032import java.util.Enumeration;
033import java.util.Iterator;
034import java.util.LinkedList;
035import java.util.List;
036
037///////////////////////////////////////////////////////////////////
038//// TotallyOrderedSet
039
040/**
041 An object of this class is a totally ordered set with an increasing order.
042 The order between any two elements in the set can be checked by calling the
043 compare() method of a comparator associated with this object. An element, a,
044 in this set is said to precede another one, b, if compare(a, b) returns -1.
045 <p>
046 The set does not contain repeated elements, which means comparing any two
047 elements in this set never returns 0.
048
049 @author  Jie Liu, Haiyang Zheng
050 @version $Id$
051 @since Ptolemy II 5.2
052 @Pt.ProposedRating Green (hyzheng)
053 @Pt.AcceptedRating Green (hyzheng)
054 */
055public class TotallyOrderedSet {
056    /** Construct a set with the given comparator.
057     *  @param comparator The Comparator with which to compare elements.
058     *  Note that the comparator cannot be changed after this TotallyOrderedSet
059     *  object is constructed.
060     *  @see java.util.Comparator
061     */
062    public TotallyOrderedSet(Comparator comparator) {
063        _comparator = comparator;
064        _set = new LinkedList();
065    }
066
067    ///////////////////////////////////////////////////////////////////
068    ////                         public methods                    ////
069
070    /** Return the element with the given index. The index starts with 0.
071     *  @param index The index of the element to return.
072     *  @return The requested element.
073     */
074    public Object at(int index) {
075        return _set.get(index);
076    }
077
078    /** Clear the set by removing all elements.
079     */
080    public void clear() {
081        _set.clear();
082    }
083
084    /** Return true if the given element is contained in this set.
085     *  The equivalence relation is defined by the comparator.
086     *  If the type of given element is not comparable by the comparator,
087     *  then a ClassCastException will be thrown.
088     *  @param object The object to check for containment.
089     *  @return True If the element is contained in this set.
090     */
091    public boolean contains(Object object) {
092        boolean result = false;
093        Iterator elements = _set.iterator();
094
095        while (elements.hasNext()) {
096            Object next = elements.next();
097            int comparator = _comparator.compare(object, next);
098
099            if (comparator == 0) {
100                result = true;
101                break;
102            }
103
104            if (comparator < 0) {
105                break;
106            }
107        }
108
109        return result;
110    }
111
112    /** Return a list of all the elements.
113     *  @return The list of all the elements.
114     */
115    public List elementList() {
116        return _set;
117    }
118
119    /** Return an enumeration of all the elements.
120     *  @return The enumeration of all the elements.
121     *  @deprecated Use elementList() instead.
122     */
123    @Deprecated
124    public Enumeration elements() {
125        return Collections.enumeration(_set);
126    }
127
128    /** Return the first element, ie. the <i>smallest</i> element.
129     *  If the set is empty, then return null.
130     *  @return The smallest element.
131     */
132    public Object first() {
133        if (isEmpty()) {
134            return null;
135        }
136
137        return _set.getFirst();
138    }
139
140    /** Return the comparator.
141     *  @return The comparator.
142     */
143    public Comparator getComparator() {
144        return _comparator;
145    }
146
147    /** Return the index of the given object. Return -1 if the object
148     *  is not in the set.
149     *  @param obj The object to get index for.
150     *  @return The index.
151     */
152    public int indexOf(Object obj) {
153        return _set.indexOf(obj);
154    }
155
156    /** Insert the given element while keeping the set sorted. If the set
157     *  contains an element "equal to" the given element, then do nothing.
158     *  The equivalence relation is defined by the comparator.
159     *  If the type of the given element is not comparable, then a
160     *  ClassCastException will be thrown.
161     *  @param obj The element to be inserted.
162     */
163    public void insert(Object obj) {
164        int count = 0;
165        Iterator elements = _set.iterator();
166
167        while (elements.hasNext()) {
168            Object next = elements.next();
169            int comparisonResult = _comparator.compare(obj, next);
170
171            if (comparisonResult == 0) {
172                return;
173            } else if (comparisonResult < 0) {
174                _set.add(count, obj);
175                return;
176            }
177
178            count++;
179        }
180
181        _set.addLast(obj);
182    }
183
184    /** Return true if the set is empty.
185     *  @return True if the set is empty.
186     */
187    public boolean isEmpty() {
188        return _set.isEmpty();
189    }
190
191    /** Remove all the elements that are (strictly) less than the argument.
192     *  If the set is empty or all the elements are greater than
193     *  the argument, then do nothing.
194     *
195     *  @param obj The argument.
196     */
197    public void removeAllLessThan(Object obj) {
198        while (!isEmpty()) {
199            Object first = first();
200            int com = _comparator.compare(obj, first);
201
202            if (com <= 0) {
203                return;
204            } else {
205                removeFirst();
206            }
207        }
208    }
209
210    /** Remove and return the element with the given index.
211     *  @param index The index of the element.
212     *  @return The removed element.
213     */
214    public Object removeAt(int index) {
215        return _set.remove(index);
216    }
217
218    /** Remove and return the first element, ie. the <i>smallest</i>
219     *  element in the set.
220     *  @return The removed element.
221     */
222    public Object removeFirst() {
223        return _set.removeFirst();
224    }
225
226    /** Return the size of the set.
227     *  @return The size of the set.
228     */
229    public int size() {
230        return _set.size();
231    }
232
233    /** Return the first element, ie. the <i>smallest</i> element and
234     *  remove it from the set.
235     *  @return The smallest element.
236     *  @deprecated Use removeFirst() instead.
237     */
238    @Deprecated
239    public Object take() {
240        return _set.removeFirst();
241    }
242
243    /** Return a string that consists of the contents of the elements
244     *  in the set. The elements are represented by there toString()
245     *  value. This method is for test purpose.
246     *  @return The string description of the set.
247     */
248    @Override
249    public String toString() {
250        StringBuffer result = new StringBuffer();
251        Iterator elements = elementList().iterator();
252
253        while (elements.hasNext()) {
254            result.append(elements.next().toString() + " ");
255        }
256
257        return result.toString();
258    }
259
260    ///////////////////////////////////////////////////////////////////
261    ////                         private variables                 ////
262
263    /** The comparator for the order.  The comparator is a blank final
264     *  field that can't be changed after creation.
265     */
266    private final Comparator _comparator;
267
268    /** The set. */
269    private LinkedList _set;
270}