|
1
25
26 package org.snipsnap.util;
27
28 import org.snipsnap.snip.Snip;
29
30 import java.util.*;
31
32
42
43 public class PartialSearcher implements Map {
44 private Map hash;
45 private String  [] sortedArray;
46
47 public PartialSearcher() {
48 this(HashMap.class);
49 }
50
51 public PartialSearcher(Class klass) {
52 try {
53 hash = (Map) klass.newInstance();
54 } catch (Exception e) {
55 hash = new HashMap();
56 }
57 createSortedArray();
58 }
59
60 public Snip[] match(String s) {
61 return match(s, s + '\uFFFF');
62 }
63
64 public Snip[] match(String start, String end) {
65 int startIdx = binarySearch(sortedArray, start, 0, sortedArray.length - 1);
66 int endIdx = binarySearch(sortedArray, end, 0, sortedArray.length - 1);
67
68 Snip[] objs = new Snip[endIdx - startIdx];
69 for (int i = startIdx; i < endIdx; i++) {
70 objs[i - startIdx] = (Snip) hash.get(sortedArray[i]);
71 }
72 return objs;
73 }
74
75 public void createSortedArray() {
76 sortedArray = new String [hash.size()];
77 Iterator iterator = hash.keySet().iterator();
79 for (int i = 0; iterator.hasNext(); i++) {
80 sortedArray[i] = (String ) iterator.next();
81 }
82 quicksort(sortedArray, 0, sortedArray.length - 1);
83 }
84
85 public static int binarySearch(String [] arr, String elem, int fromIndex, int toIndex) {
86 int mid,cmp;
87 while (fromIndex <= toIndex) {
88 mid = (fromIndex + toIndex) / 2;
89 if ((cmp = arr[mid].compareTo(elem)) < 0) {
90 fromIndex = mid + 1;
91 } else if (cmp > 0) {
92 toIndex = mid - 1;
93 } else {
94 return mid;
95 }
96 }
97 return fromIndex;
98 }
99
100 public void quicksort(String [] arr, int lo, int hi) {
101 if (lo >= hi) {
102 return;
103 }
104
105 int mid = (lo + hi) / 2;
106 String tmp;
107 String middle = arr[mid];
108
109 if (arr[lo].compareTo(middle) > 0) {
110 arr[mid] = arr[lo];
111 arr[lo] = middle;
112 middle = arr[mid];
113 }
114
115 if (middle.compareTo(arr[hi]) > 0) {
116 arr[mid] = arr[hi];
117 arr[hi] = middle;
118 middle = arr[mid];
119
120 if (arr[lo].compareTo(middle) > 0) {
121 arr[mid] = arr[lo];
122 arr[lo] = middle;
123 middle = arr[mid];
124 }
125 }
126
127 int left = lo + 1;
128 int right = hi - 1;
129
130 if (left >= right) {
131 return;
132 }
133
134 for (; ;) {
135 while (arr[right].compareTo(middle) > 0) {
136 right--;
137 }
138
139 while (left < right && arr[left].compareTo(middle) <= 0) {
140 left++;
141 }
142
143 if (left < right) {
144 tmp = arr[left];
145 arr[left] = arr[right];
146 arr[right] = tmp;
147 right--;
148 } else {
149 break;
150 }
151 }
152
153 quicksort(arr, lo, left);
154 quicksort(arr, left + 1, hi);
155 }
156
157 public int size() {
158 return hash.size();
159 }
160
161 public boolean isEmpty() {
162 return hash.isEmpty();
163 }
164
165 public boolean containsKey(Object o) {
166 return hash.containsKey(o);
167 }
168
169 public boolean containsValue(Object o) {
170 return hash.containsValue(o);
171 }
172
173 public Object get(Object o) {
174 return hash.get(o);
175 }
176
177 public Object put(Object o, Object o1) {
178 Object object = hash.put(o,o1);
179 createSortedArray();
180 return object;
181 }
182
183 public Object remove(Object o) {
184 Object object = hash.remove(o);
185 createSortedArray();
186 return object;
187 }
188
189 public void putAll(Map map) {
190 hash.putAll(map);
191 createSortedArray();
192 }
193
194 public void clear() {
195 hash.clear();
196 createSortedArray();
197 }
198
199 public Set keySet() {
200 return hash.keySet();
201 }
202
203 public Collection values() {
204 return hash.values();
205 }
206
207 public Set entrySet() {
208 return hash.entrySet();
209 }
210 }
211 |
Popular Tags |
Java API By Example, From Geeks To Geeks.