TreeSetGreedy


1   /*
2    *  TreeSetGreedy.java, special container for managing z-Indexes of traces in jchart2d.
3    *  Copyright (C) Achim Westermann, created on 12.05.2005, 20:11:17
4    *
5    *  This library is free software; you can redistribute it and/or
6    *  modify it under the terms of the GNU Lesser General Public
7    *  License as published by the Free Software Foundation; either
8    *  version 2.1 of the License, or (at your option) any later version.
9    * 
10   *  This library is distributed in the hope that it will be useful,
11   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   *  Lesser General Public License for more details.
14   * 
15   *  You should have received a copy of the GNU Lesser General Public
16   *  License along with this library; if not, write to the Free Software
17   *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18   *
19   *  If you modify or optimize the code in a useful way please let me know.
20   *  Achim.Westermann@gmx.de
21   *
22   */
23  package info.monitorenter.util.collections;
24  
25  import java.math.BigDecimal  ;
26  import java.math.BigInteger  ;
27  import java.util.Comparator  ;
28  import java.util.Iterator  ;
29  import java.util.Set  ;
30  import java.util.TreeSet  ;
31  
32  /**
33   * A <code>Set</code> that will always successfully add new instances and
34   * guarantee that all the "<em>Comparable properties</em>" of the contained
35   * {@link info.monitorenter.util.collections.IComparableProperty} instances will build a set
36   * (no duplicates).
37   * <p>
38   * Although the interface of {@link java.util.Set} is preserved and allows
39   * adding any <code>Object</code> <b>only
40   * {@link info.monitorenter.util.collections.IComparableProperty} instances may be added to
41   * <code>TreeSetGreedy</code> </b> because it uses a proprietary
42   * {@link java.util.Comparator}.
43   * <p>
44   * The added <code>IComparableProperty</code> instances with the lowest
45   * {@link java.lang.Number} property (see
46   * {@link info.monitorenter.util.collections.IComparableProperty#getComparableProperty()})
47   * will be returned first from the retrievable <code>Iterator</code>
48   * <p>
49   * <h2>Warning</h2>
50   * If the <code>IComparableProperty</code> (thus meaning the member or
51   * accessed data) is changed from outside, the internal order of this set will
52   * get corrupted and iterations or add/remove calls may fail. Therefore it is
53   * necessary to remove the instance before outside modification and later on add
54   * it again.
55   * <p>
56   * 
57   * @author <a HREF="mailto:Achim.Westermann@gmx.de">Achim Westermann </a>
58   * 
59   */
60  public class TreeSetGreedy extends TreeSet   implements Set   {
61  
62    /**
63     * A <code>Comparator</code> that will compare {@link IComparableProperty}
64     * instances by their {@link IComparableProperty#getComparableProperty()}
65     * number.
66     * <p>
67     * Note that the given <code>Set</code> has to be the instance this
68     * <code>Comparator</code> has to be set to later. This is necessary to
69     * fulfill the contract declared for method {@link #compare(Object, Object)}.
70     * Therefore direct after creation the internal member {@link #m_delegate} has
71     * to be set from outside.
72     * <p>
73     * A {@link java.util.Set} that is sorted by this <code>Comparator</code>
74     * has to be obtained by the call: <br>
75     * 
76     * <pre>
77     * NumberPropertyComparator comparator = new NumberPropertyComparator();
78     * Set set = new TreeSet(comparator);
79     * NumberPropertyComparator.delegate = set;
80     * </pre>
81     * 
82     * <p>
83     * 
84     * @author <a HREF="mailto:Achim.Westermann@gmx.de">Achim Westermann </a>
85     * 
86     */
87    private static final class NumberPropertyComparator implements Comparator   {
88  
89      /**
90       * Reference to an instance that has to be ordered in the
91       * <code>TreeSetGreedy</code> due to modification.
92       */
93      private IComparableProperty m_resort = null;
94  
95      /**
96       * Compares two Objects by casting them to {@link IComparableProperty} and
97       * using their {@link  IComparableProperty#getComparableProperty()}
98       * property.
99       * <p>
100      * This <code>Comparator</code> may only be used in {@link java.util.Set}
101      * instances that only contain <code>IComparableProperty</code> instances.
102      * <p>
103      * For two instances that are judged equal (equal z-index) the first
104      * argument is decided to stay, the second instance gets assigned a higher
105      * {@link IComparableProperty#setComparableProperty(Number)} by one, then is
106      * removed from the <code>Set</code> it is working for and added anew thus
107      * getting the next index order.
108      * <p>
109      * This procedure is expensive (performs <em>O(n!)</em>) but easy to
110      * implement and guarantees that every <code>IComparableProperty</code>
111      * instance is added (never returns 0), all instances have a different
112      * values and the newest added instances definetely get their chosen value.
113      * <p>
114      * 
115      * @param o1
116      *          the first instance for comparison.
117      * 
118      * @param o2
119      *          the second instance for comparison.
120      * 
121      * @throws ClassCastException
122      *           if one of the given arguments does not implement
123      *           {@link IComparableProperty}
124      * 
125      * @return -1 if o1 is first, 0, if both are equal and +1 if o1 comes last.
126      * 
127      * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
128      */
129     public int compare(final Object   o1, final Object   o2) throws ClassCastException   {
130       // Don't take real identical elements (set policy)
131       if (o1 == o2) {
132         return 0;
133       }
134       IComparableProperty prop1 = (IComparableProperty) o1;
135       IComparableProperty prop2 = (IComparableProperty) o2;
136       double i1 = prop1.getComparableProperty().doubleValue();
137       double i2 = prop2.getComparableProperty().doubleValue();
138 
139       // fake and take equal elements.
140       if (i1 < i2) {
141         return -1;
142       } else if (i1 == i2) {
143         // here, we lie
144         // but increase the other
145         prop2.setComparableProperty(createIncreasedNumber(prop2.getComparableProperty()));
146         this.m_resort = prop2;
147         return 1;
148       } else {
149         return 1;
150       }
151 
152     }
153 
154     /**
155      * Creates a new number of the correct type increased by 1.
156      * <p>
157      * 
158      * @param n
159      *          the number to increase.
160      * 
161      * @return a new number of the correct type increased by 1.
162      */
163     private Number   createIncreasedNumber(final Number   n) {
164       Class   c = n.getClass();
165       if (c == Integer  .class) {
166         return new Integer  (n.intValue() - 1);
167       } else if (c == Double  .class) {
168         return new Double  (n.doubleValue() + 1);
169       } else if (c == Float  .class) {
170         return new Float  (n.floatValue() + 1);
171       } else if (c == Short  .class) {
172         return new Short  ((short) (n.shortValue() + 1));
173       } else if (c == Byte  .class) {
174         return new Byte  ((byte) (n.byteValue() + 1));
175       } else if (c == Long  .class) {
176         return new Long  (n.longValue() + 1);
177       } else if (c == BigDecimal  .class) {
178         BigDecimal   bd = new BigDecimal  (n.toString());
179         bd.add(new BigDecimal  (1));
180         return bd;
181       } else {
182         BigInteger   bi = new BigInteger  (n.toString());
183         bi.add(new BigInteger  ("1"));
184         return bi;
185 
186       }
187     }
188   }
189 
190   /**
191    * Generated <code>serialVersionUID</code>.
192    */
193   private static final long serialVersionUID = 3258130237048173623L;
194 
195   /** The comparator to use. */
196   private NumberPropertyComparator m_comparator;
197 
198   /**
199    * Creates an instance with an internal <code>Comparator</code> to fulfill
200    * the contract of this class.
201    */
202   public TreeSetGreedy() {
203     super(new NumberPropertyComparator());
204     this.m_comparator = (NumberPropertyComparator) this.comparator();
205   }
206 
207   /**
208    * @see java.util.Collection#add(java.lang.Object)
209    */
210   public synchronized boolean add(final Object   o) {
211     boolean ret = this.addInternal(o);
212     this.packComparableProperties();
213     return ret;
214   }
215 
216   /**
217    * Internally adds the given instance.
218    * <p>
219    * 
220    * @param o
221    *          the instance to add.
222    * 
223    * @return true if the instance was added.
224    */
225   private boolean addInternal(final Object   o) {
226     boolean ret = super.add(o);
227     boolean success = false;
228     IComparableProperty resort = this.m_comparator.m_resort;
229     this.m_comparator.m_resort = null;
230     if (resort != null) {
231       success = this.remove(resort);
232       if (!success) {
233         System.err.println("Could not remove: " + resort);
234       }
235       // do it after add and see a StackOverflowError.
236       // then puzzle some hours why this happens... ;-)
237       success = this.addInternal(resort);
238     }
239     return ret;
240   }
241 
242   /**
243    * Modifies the values of the comparable properties of the contained elements
244    * to have a continuous order of increasing integer values.
245    * <p>
246    * As the real value of the comparable property is unimportant for this set
247    * but only the relation of the values (order) is of interest this method may
248    * change all values to use only the minimum integer range for expressing the
249    * order.
250    * <p>
251    * An example of the procedure:
252    * 
253    * <pre>
254    *   [0, 10, 11, 22] -&gt; [0,1,2,3]
255    * </pre>
256    * 
257    * <p>
258    * This method allows to avoid exceeding bounds (e.g. between {
259    * {@link info.monitorenter.gui.chart.ITrace2D#Z_INDEX_MIN} and
260    * {@link info.monitorenter.gui.chart.ITrace2D#ZINDEX_MAX}) and allows that changes of the
261    * comparable properties always have an effect. If in the example above the
262    * 2nd instance would increase it's property by one from 10 to 11 nothing
263    * would happen to the order.
264    * <p>
265    * 
266    */
267   private void packComparableProperties() {
268     Iterator   it = this.iterator();
269     IComparableProperty prop;
270     int i = 0;
271     while (it.hasNext()) {
272       prop = (IComparableProperty) it.next();
273       prop.setComparableProperty(new Integer  (i));
274       i++;
275     }
276   }
277 }
278
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags