Clover Coverage Report - contrib
Coverage timestamp: Fri Apr 27 2012 21:25:11 UTC
../../../../../../../img/srcFileCovDistChart9.png 31% of files have more coverage
51   209   32   4.25
32   110   0.63   4
12     2.67  
3    
 
  UDAFExampleMaxMinNUtil       Line # 32 27 18 81.6% 0.81632656
  UDAFExampleMaxMinNUtil.State       Line # 40 0 0 - -1.0
  UDAFExampleMaxMinNUtil.Evaluator       Line # 49 24 14 93.5% 0.9347826
 
No Tests
 
1    /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements. See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership. The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License. You may obtain a copy of the License at
9    *
10    * http://www.apache.org/licenses/LICENSE-2.0
11    *
12    * Unless required by applicable law or agreed to in writing, software
13    * distributed under the License is distributed on an "AS IS" BASIS,
14    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15    * See the License for the specific language governing permissions and
16    * limitations under the License.
17    */
18   
19   
20    package org.apache.hadoop.hive.contrib.udaf.example;
21   
22    import java.util.ArrayList;
23    import java.util.Collections;
24    import java.util.Comparator;
25    import java.util.List;
26   
27    import org.apache.hadoop.hive.ql.exec.UDAFEvaluator;
28   
29    /**
30    * The utility class for UDAFMaxN and UDAFMinN.
31    */
 
32    public final class UDAFExampleMaxMinNUtil {
33   
34    /**
35    * This class stores the information during an aggregation.
36    *
37    * Note that this class has to have a public constructor, so that Hive can
38    * serialize/deserialize this class using reflection.
39    */
 
40    public static class State {
41    ArrayList<Double> a; // This ArrayList holds the max/min N
42    int n; // This is the N
43    }
44   
45    /**
46    * The base class of the UDAFEvaluator for UDAFMaxN and UDAFMinN.
47    * We just need to override the getAscending function to make it work.
48    */
 
49    public abstract static class Evaluator implements UDAFEvaluator {
50   
51    private State state;
52   
 
53  16 toggle public Evaluator() {
54  16 state = new State();
55  16 init();
56    }
57   
58    /**
59    * Reset the state.
60    */
 
61  20 toggle public void init() {
62  20 state.a = new ArrayList<Double>();
63  20 state.n = 0;
64    }
65   
66    /**
67    * Returns true in UDAFMaxN, and false in UDAFMinN.
68    */
69    protected abstract boolean getAscending();
70   
71    /**
72    * Iterate through one row of original data.
73    * This function will update the internal max/min buffer if the internal buffer is not full,
74    * or the new row is larger/smaller than the current max/min n.
75    */
 
76  2000 toggle public boolean iterate(Double o, int n) {
77  2000 boolean ascending = getAscending();
78  2000 state.n = n;
79  2000 if (o != null) {
80  1500 boolean doInsert = state.a.size() < n;
81  1500 if (!doInsert) {
82  1460 Double last = state.a.get(state.a.size()-1);
83  1460 if (ascending) {
84  734 doInsert = o < last;
85    } else {
86  726 doInsert = o > last;
87    }
88    }
89  1500 if (doInsert) {
90  180 binaryInsert(state.a, o, ascending);
91  180 if (state.a.size() > n) {
92  140 state.a.remove(state.a.size()-1);
93    }
94    }
95    }
96  2000 return true;
97    }
98   
99    /**
100    * Get partial aggregation results.
101    */
 
102  4 toggle public State terminatePartial() {
103    // This is SQL standard - max_n of zero items should be null.
104  4 return state.a.size() == 0 ? null : state;
105    }
106   
107    /** Two pointers are created to track the maximal elements in both o and MaxNArray.
108    * The smallest element is added into tempArrayList
109    * Consider the sizes of o and MaxNArray may be different.
110    */
 
111  4 toggle public boolean merge(State o) {
112  4 if (o != null) {
113  4 state.n = o.n;
114  4 state.a = sortedMerge(o.a, state.a, getAscending(), o.n);
115    }
116  4 return true;
117    }
118   
119    /**
120    * Terminates the max N lookup and return the final result.
121    */
 
122  4 toggle public ArrayList<Double> terminate() {
123    // This is SQL standard - return state.MaxNArray, or null if the size is zero.
124  4 return state.a.size() == 0 ? null : state.a;
125    }
126    }
127   
128   
129    /**
130    * Returns a comparator based on whether the order is ascending or not.
131    * Has a dummy parameter to make sure generics can infer the type correctly.
132    */
 
133  184 toggle static <T extends Comparable<T>> Comparator<T> getComparator(boolean ascending, T dummy) {
134  184 Comparator<T> comp;
135  184 if (ascending) {
136  88 comp = new Comparator<T>() {
 
137  276 toggle public int compare(T o1, T o2) {
138  276 return o1.compareTo(o2);
139    }
140    };
141    } else {
142  96 comp = new Comparator<T>() {
 
143  285 toggle public int compare(T o1, T o2) {
144  285 return o2.compareTo(o1);
145    }
146    };
147    }
148  184 return comp;
149    }
150   
151    /**
152    * Insert an element into an ascending/descending array, and keep the order.
153    * @param ascending
154    * if true, the array is sorted in ascending order,
155    * otherwise it is in descending order.
156    *
157    */
 
158  180 toggle static <T extends Comparable<T>> void binaryInsert(List<T> list, T value, boolean ascending) {
159   
160  180 int position = Collections.binarySearch(list, value, getComparator(ascending, (T)null));
161  180 if (position < 0) {
162  154 position = (-position) - 1;
163    }
164  180 list.add(position, value);
165    }
166   
167    /**
168    * Merge two ascending/descending array and keep the first n elements.
169    * @param ascending
170    * if true, the array is sorted in ascending order,
171    * otherwise it is in descending order.
172    */
 
173  4 toggle static <T extends Comparable<T>> ArrayList<T> sortedMerge(List<T> a1, List<T> a2,
174    boolean ascending, int n) {
175   
176  4 Comparator<T> comparator = getComparator(ascending, (T)null);
177   
178  4 int n1 = a1.size();
179  4 int n2 = a2.size();
180  4 int p1 = 0; // The current element in a1
181  4 int p2 = 0; // The current element in a2
182   
183  4 ArrayList<T> output = new ArrayList<T>(n);
184   
185  40 while (output.size() < n && (p1 < n1 || p2 < n2)) {
186  40 if (p1 < n1) {
187  40 if (p2 == n2 || comparator.compare(a1.get(p1), a2.get(p2)) < 0) {
188  40 output.add(a1.get(p1++));
189    }
190    }
191  40 if (output.size() == n) {
192  4 break;
193    }
194  36 if (p2 < n2) {
195  0 if (p1 == n1 || comparator.compare(a2.get(p2), a1.get(p1)) < 0) {
196  0 output.add(a2.get(p2++));
197    }
198    }
199    }
200   
201  4 return output;
202    }
203   
204    // No instantiation.
 
205  0 toggle private UDAFExampleMaxMinNUtil() {
206    }
207   
208    }
209