Sort


1   /**
2    * 
3    */
4   package prefuse.data.util;
5   
6   import java.util.Arrays  ;
7   import java.util.Comparator  ;
8   
9   import prefuse.data.Schema;
10  import prefuse.data.Table;
11  import prefuse.data.Tuple;
12  import prefuse.data.expression.Predicate;
13  import prefuse.data.tuple.TupleSet;
14  import prefuse.util.collections.CompositeComparator;
15  import prefuse.util.collections.NullComparator;
16  
17  /**
18   * <p>Utility class representing sorting criteria, this can be given as
19   * input to the {@link TupleSet#tuples(Predicate, Sort)} method to
20   * get a sorted iteration of tuples.</p>
21   * 
22   * <p>Sort criteria consists of an ordered list of data field names to
23   * sort by, along with an indication to sort tuples in either ascending
24   * or descending order. These criteria can be passed in to the
25   * constructor or added incrementally using the
26   * {@link #add(String, boolean)} method.</p>
27   * 
28   * <p>Alternatively, one can also specify the sorting criteria using a
29   * single string, which is parsed using the {@link #parse(String)} method.
30   * This string should consist
31   * of a comma-delimited list of field names, which optional "ASC" or
32   * "DESC" modifiers to specify ascending or descending sorts. If no
33   * modifier is given, ascending order is assumed. Field
34   * names which include spaces or other non-standard characters should
35   * be written in brackets ([]), just as is done in 
36   * {@link prefuse.data.expression.parser.ExpressionParser expression
37   * language statements}. For example, the
38   * following string</p>
39   * 
40   * <pre>"Profit DESC, [Product Type]"</pre>   
41   * 
42   * <p>sorts first by the data field "Profit" in descending order,
43   * additionally sorting in ascending order by the data field
44   * "Product Type" for tuples which have identical values in the
45   * "Profit" field.</p>
46   * 
47   * @author <a HREF="http://jheer.org">jeffrey heer</a>
48   */
49  public class Sort {
50  
51      private static final String   ASC  = " ASC";
52      private static final String   DESC = " DESC";
53      private static final String   asc  = ASC.toLowerCase();
54      private static final String   desc = DESC.toLowerCase();
55      
56      private String  []  m_fields;
57      private boolean[] m_ascend;
58      
59      /**
60       * Creates a new, empty Sort specification.
61       */
62      public Sort() {
63          this(new String  [0], new boolean[0]);
64      }
65      
66      /**
67       * Creates a new Sort specification that sorts on the
68       * given fields, all in ascending order.
69       * @param fields the fields to sort on, in order of precedence
70       */
71      public Sort(String  [] fields) {
72          this(fields, new boolean[fields.length]);
73          Arrays.fill(m_ascend, true);
74      }
75      
76      /**
77       * Creates a new Sort specification that sorts on the
78       * given fields in the given orders.
79       * @param fields the fields to sort on, in order of precedence
80       * @param ascend for each field, indicates if the field should
81       * be sorted in ascending (true) or descending (false) order
82       */
83      public Sort(String  [] fields, boolean[] ascend) {
84          m_fields = fields;
85          m_ascend = ascend;
86      }
87      
88      /**
89       * Adds a new field to this Sort specification.
90       * @param field the additional field to sort on
91       * @param ascend indicates if the field should
92       * be sorted in ascending (true) or descending (false) order
93       */
94      public void add(String   field, boolean ascend) {
95          String  [] f = new String  [m_fields.length+1];
96          System.arraycopy(m_fields, 0, f, 0, m_fields.length);
97          f[m_fields.length] = field;
98          m_fields = f;
99          
100         boolean[] b = new boolean[m_fields.length+1];
101         System.arraycopy(m_ascend, 0, b, 0, m_ascend.length);
102         b[m_ascend.length] = ascend;
103         m_ascend = b;
104     }
105     
106     /**
107      * Returns the number of fields in this Sort specification.
108      * @return the number of fields to sort on
109      */
110     public int size() {
111         return m_fields.length;
112     }
113     
114     /**
115      * Returns the sort field at the given index.
116      * @param i the index to look up
117      * @return the sort field at the given index
118      */
119     public String   getField(int i) {
120         return m_fields[i];
121     }
122     
123     /**
124      * Returns the ascending modifier as the given index.
125      * @param i the index to look up
126      * @return true if the field at the given index is to be sorted
127      * in ascending order, false for descending order
128      */
129     public boolean isAscending(int i) {
130         return m_ascend[i];
131     }
132     
133     /**
134      * Generates a Comparator to be used for sorting tuples drawn from
135      * the given tuple set.
136      * @param ts the TupleSet whose Tuples are to be sorted
137      * @return a Comparator instance for sorting tuples from the given
138      * set using the sorting criteria given in this specification
139      */
140     public Comparator   getComparator(TupleSet ts) {
141         // get the schema, so we can lookup column value types        
142         Schema s = null;
143         if ( ts instanceof Table ) {
144             // for Tables, we can get this directly
145             s = ((Table)ts).getSchema();
146         } else {
147             // if non-table tuple set is empty, we punt
148             if ( ts.getTupleCount() == 0 )
149                 return new NullComparator();
150             // otherwise, use the schema of the first tuple in the set
151             s = ((Tuple)ts.tuples().next()).getSchema();
152         }
153         // create the comparator
154         CompositeComparator cc = new CompositeComparator(m_fields.length);
155         for ( int i=0; i<m_fields.length; ++i ) {
156             cc.add(new TupleComparator(m_fields[i],
157                        s.getColumnType(m_fields[i]), m_ascend[i]));
158         }
159         return cc;
160     }
161     
162     // ------------------------------------------------------------------------
163     
164     private static void subparse(String   s, Object  [] res) {
165         s = s.trim();
166         
167         // extract ascending modifier first
168         res[1] = Boolean.TRUE;
169         if ( s.endsWith(DESC) || s.endsWith(desc) ) {
170             res[1] = Boolean.FALSE;
171             s = s.substring(0, s.length()-DESC.length()).trim();
172         } else if ( s.endsWith(ASC) || s.endsWith(asc) ) {
173             s = s.substring(0, s.length()-ASC.length()).trim();
174         }
175         
176         if ( s.startsWith("[") ) {
177             if ( s.lastIndexOf("[") == 0 && 
178                  s.endsWith("]") && s.indexOf("]") == s.length() ) {
179                 res[0] = s.substring(1, s.length()-1);
180             } else {
181                 throw new RuntimeException  ();
182             }
183         } else {
184             if ( s.indexOf(" ") < 0 && s.indexOf("\t") < 0 ) {
185                 res[0] = s;
186             } else {
187                 throw new RuntimeException  ();
188             }
189         }
190     }
191     
192     /**
193      * Parse a comma-delimited String of data fields to sort on, along
194      * with optional ASC or DESC modifiers, to generate a new Sort
195      * specification. This string should consist
196      * of a comma-delimited list of field names, which optional "ASC" or
197      * "DESC" modifiers to specify ascending or descending sorts. If no
198      * modifier is given, ascending order is assumed. Field
199      * names which include spaces or other non-standard characters should
200      * be written in brackets ([]), just as is done in 
201      * {@link prefuse.data.expression.parser.ExpressionParser expression
202      * language statements}. For example, the
203      * following string</p>
204      * 
205      * <pre>"Profit DESC, [Product Type]"</pre>   
206      * 
207      * <p>sorts first by the data field "Profit" in descending order,
208      * additionally sorting in ascending order by the data field
209      * "Product Type" for tuples which have identical values in the
210      * "Profit" field.</p>
211      * @param s the sort specification String
212      * @return a new Sort specification
213      */
214     public static Sort parse(String   s) {
215         Sort sort = new Sort();
216         Object  [] res = new Object  [2];
217         int idx = 0, len = s.length();
218         int comma = s.indexOf(',');
219         int quote = s.indexOf('[');
220         while ( idx < len ) {
221             if ( comma < 0 ) {
222                 subparse(s.substring(idx), res);
223                 sort.add((String  )res[0], ((Boolean  )res[1]).booleanValue());
224                 break;
225             } else if ( quote < 0 || comma < quote ) {
226                 subparse(s.substring(idx, comma), res);
227                 sort.add((String  )res[0], ((Boolean  )res[1]).booleanValue());
228                 idx = comma + 1;
229                 comma = s.indexOf(idx, ',');
230             } else {
231                 int q2 = s.indexOf(quote, ']');
232                 if ( q2 < 0 ) {
233                     throw new RuntimeException  ();
234                 } else {
235                     comma = s.indexOf(q2, ',');
236                     subparse(s.substring(idx, comma), res);
237                     sort.add((String  )res[0], ((Boolean  )res[1]).booleanValue());
238                     idx = comma + 1;
239                     comma = s.indexOf(idx, ',');
240                 }
241             }
242         }
243         return sort;
244     }
245     
246     /**
247      * @see java.lang.Object#toString()
248      */
249     public String   toString() {
250         StringBuffer   sbuf = new StringBuffer  ();
251         for ( int i=0; i<m_fields.length; ++i ) {
252             if ( i > 0 ) sbuf.append(", ");
253             sbuf.append('[').append(m_fields[i]).append(']');
254             sbuf.append((m_ascend[i]) ? ASC : DESC);
255         }
256         return sbuf.toString();
257     }
258     
259 } // end of class Sort
260
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags