在很多的实际应用中，经常会遇过这种情况。就是要求排序(升序或降序)只保存N个对象信息，如我发表的其中一篇文件
(原创)设计一个Tomcat访问日志分析工具 这个工具需要解析非常多的数据，再排出前10位流量最大的页面信息。我们知道 Java中 有Collections.sort方法可以对list进行排序，但在数据量很大的情况，每次要取时进行一次排序，效率就比较的低，所以我实现下面这个SortedBag工具类，供大家参考学习。有什么问题和建议也希望大家回复给我，Thx!
SortedBag工具类实现以下功能：
* 自动排序
* 可以设置SortedBag的最大size，超过该size后，SortedBag会根据排序的类型(升序去掉最大的或降序去掉最小的)保证SortedBag的size不超过最大设置
* 可以对元素进行设置唯一设置
* 注意事项：
SortedBag支持泛型，所以需要使用jdb5.0或以版本编译运行。
SortedBag是非线程安全的，如果是多线程的情况，请加上安全锁
下面是一个使用的例子：
1 //size is 5. element is unique. use ascending order
2 SortedBag<String> list = new SortedBag<String>(5, true, true);
3
4 list.add("r");
5 list.add("a");
6 list.add("c");
7 list.add("b");
8 list.add("e");
9 list.add("g");
10 list.add("a");
11
12 System.out.println(list);
打印出来的结果：
util.SortedBag@69b332[1=a,2=b,3=c,4=e,5=g]
源代码如下：
1
2 import java.util.Collection;
3 import java.util.LinkedList;
4 import java.util.ListIterator;
5
6 import org.apache.commons.lang.builder.ToStringBuilder;
7
8 /**
9 * <p>
10 * Sorted linked list.
11 * </p>
12 * <p>
13 * <pre>
14 * it could provide a sorted list by certain size. default szie is -1(size is not limit).
15 * it also support unique item sort by setUnique method. default is not unique element sort.
16 * if szie is great than certain count,we have two choices.
17 * if desc then the smallest one will be removed,
18 * if asc then the biggest one will be removed.
19 *
20 * Notice: the element in the list must implement Comparable interface.
21 * </per>
22 * <p>
23 *
24 * @author Matthew Xie
25 * @version 2006-6-2
26 */
27 public class SortedBag<T extends Comparable<T>> extends LinkedList<T> {
28
29 public static final int DEFAULT_LIST_SIZE = -1;
30
31 /**
32 * serial version uid
33 */
34 private static final long serialVersionUID = -9019444166911394396L;
35
36 private int item_num;
37
38 private boolean isUnique = false;
39 private boolean isAsc = true;
40
41 /**
42 * get the ordered item number
43 * @return item number
44 */
45 public int getItem_num() {
46 return item_num;
47 }
48
49 /**
50 * set the ordered item number.
51 * @param item_num item number.
52 */
53 public void setItem_num(int item_num) {
54 this.item_num = item_num;
55 }
56
57
58 /**
59 * @param item_num
60 */
61 public SortedBag(int item_num) {
62 this(item_num, false, true);
63
64 }
65
66 /**
67 * @param item_num
68 * @param isUnique
69 * @param isAsc
70 */
71 public SortedBag(int item_num, boolean isUnique, boolean isAsc) {
72 super();
73 this.item_num = item_num;
74 this.isUnique = isUnique;
75 this.isAsc = isAsc;
76 }
77
78 /**
79 * default construct method
80 */
81 public SortedBag() {
82 this(DEFAULT_LIST_SIZE);
83 }
84
85 private void binaryInsert(int beginPos, int endPos, T t) {
86 if (beginPos > endPos) {
87 return;
88 }
89 if (beginPos == endPos) {
90 add(beginPos, t);
91 return;
92 }
93
94 int cComparePos = (endPos + beginPos) / 2;
95 T temp = get(cComparePos);
96
97 int compareResult = t.compareTo(temp);
98 if (!isAsc()) {
99 compareResult = compareResult * -1;
100 }
101
102 if (compareResult > 0) {
103 if (cComparePos+1 == endPos) {
104 addElement(endPos, t);
105 return;
106 }
107 binaryInsert(cComparePos, endPos-1, t);
108 } else if (compareResult < 0) {
109 if (beginPos+1 == cComparePos) {
110 addElement(cComparePos, t);
111 return;
112 }
113 binaryInsert(beginPos, cComparePos, t);
114 } else if (!isUnique) {
115 add(cComparePos, t);
116 return;
117 }
118 }
119
120 private void addElement(int pos, T t) {
121 if (isAsc()) {
122 if (pos > 0) {
123 T ctemp = get(pos-1);
124 if (isUnique && t.compareTo(ctemp) == 0) {
125 return;
126 }
127 }
128 } else {
129 T ctemp;
130 if (pos < size()) {
131 ctemp = get(pos);
132 } else {
133 ctemp = get(pos-1);
134 }
135 if (isUnique && t.compareTo(ctemp) == 0) {
136 return;
137 }
138 }
139 add(pos, t);
140 }
141
142 /**
143 * <p>
144 * add to the list, and then ordered the item.</p>
145 * @param t object
146 */
147 private void addToItemList(T t) {
148 int len = size();
149
150 if (len == 0) {
151 super.add(t);
152 return;
153 }
154
155 T tTemp;
156 if (item_num > 0) {
157 tTemp = getLast();
158 if (!compareTo(t, tTemp) && len >= item_num) {
159 return;
160 }
161 }
162
163 binaryInsert(0, len, t);
164
165 if (item_num > 0) {
166 if (size() > item_num) {
167 removeLast();
168 }
169 }
170 }
171
172 /**
173 * Appends all of the elements in the specified collection to the end of
174 * this list, in the order that they are returned by the specified
175 * collection's iterator. The behavior of this operation is undefined if
176 * the specified collection is modified while the operation is in
177 * progress. (This implies that the behavior of this call is undefined if
178 * the specified Collection is this list, and this list is nonempty.)
179 *
180 * @param list the elements to be inserted into this list.
181 * @return <tt>true</tt> if this list changed as a result of the call.
182 * @throws NullPointerException if the specified collection is null.
183 */
184 public void addAll(Collection<T> list) {
185 if (list == null) {
186 return;
187 }
188 for (T t : list) {
189 addToItemList(t);
190 }
191 }
192
193 /**
194 * Appends the specified element to the this list.
195 * <p>
196 * notice: that after added to the list. the current object added to list<br>
197 * will be ordered. <br>
198 * if the ordered list biggest lenght is n, and the current object is bigger or<br>
199 * smaller than any one of the n objects, it will insert into his right order position.<br>
200 * if the thest n objects if bigger ot smaller than current object, it won't be added to the list.<br>
201 * </p>
202 *
203 * @param t element to be appended to this list.
204 * @return <tt>true</tt> (as per the general contract of
205 * <tt>Collection.add</tt>).
206 */
207 @Override
208 public boolean add(T t) {
209 addToItemList(t);
210 return true;
211 }
212
213
214
215 /**
216 * get the object toString method's return result
217 * @param t object
218 * @return toString value
219 */
220 public String getString(T t) {
221 return t.toString();
222 }
223
224
225 /**
226 * Override the toString method.
227 * @return the item info from the list.
228 */
229 @Override
230 public String toString() {
231 ToStringBuilder toStringBuilder = new ToStringBuilder(this);
232
233 ListIterator<T> listIter = listIterator();
234 T tTemp;
235 Integer i = 1;
236 while (listIter.hasNext()) {
237 tTemp = listIter.next();
238 toStringBuilder.append(i.toString(), getString(tTemp));
239 i++;
240 }
241 return toStringBuilder.toString();
242 }
243
244 /**
245 * <p>
246 * compare method.
247 * </p>
248 * <p>
249 * <pre>
250 * t1 is the object you add.
251 * t2 is the object get from list
252 * </pre>
253 * </p>
254 * @param t1 item1
255 * @param t2 item2
256 * @return true or false to compare between t1 and t2
257 */
258 protected Boolean compareTo(T t1, T t2) {
259 boolean bRet;
260 if (t1 == null) {
261 bRet = false;
262 } else {
263 if (t2 == null) {
264 bRet = true;
265 }
266 bRet = t1.compareTo(t2) > 0 ? true : false;
267 }
268 if (isAsc()) {
269 bRet = !bRet;
270 }
271
272 return bRet;
273 }
274
275 /**
276 * @param isUnique The isUnique to set.
277 */
278 public void setUnique(boolean isUnique) {
279 this.isUnique = isUnique;
280 }
281
282 /**
283 * equal the object t1 with t2. true means t1 and t2 are equal.
284 *
285 * @param t1 object
286 * @param t2 object
287 * @return t1 is equal to t2 or not.
288 */
289 protected Boolean equalItem(T t1, T t2) {
290 if (t1 == null) {
291 if (t2 == null) {return true;}
292 } else {
293 if (t2 != null) {
294 return t1.compareTo(t2) == 0 ? true : false;
295 }
296 }
297 return false;
298 }
299
300 public boolean isAsc() {
301 return isAsc;
302 }
303
304 public void setAsc(boolean isAsc) {
305 this.isAsc = isAsc;
306 }
307
308 public static void main(String[] args) {
309
310 //size is 5. element is unique. use ascending order
311 SortedBag<String> list = new SortedBag<String>(8, false, true);
312
313 list.add("r");
314 list.add("a");
315 list.add("c");
316 list.add("b");
317 list.add("e");
318 list.add("g");
319 list.add("a");
320
321 System.out.println(list);
322 }
323 }
Yours Matthew！
posted on 2008-04-16 09:00
x.matthew 阅读(1032)
评论(16) 编辑 收藏