001 /*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License"). You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at
010 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
011 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
012 * See the License for the specific language governing permissions
013 * and limitations under the License.
014 *
015 * When distributing Covered Code, include this CDDL HEADER in each
016 * file and include the License file at
017 * trunk/opends/resource/legal-notices/OpenDS.LICENSE. If applicable,
018 * add the following below this CDDL HEADER, with the fields enclosed
019 * by brackets "[]" replaced with your own identifying information:
020 * Portions Copyright [yyyy] [name of copyright owner]
021 *
022 * CDDL HEADER END
023 *
024 *
025 * Copyright 2006-2008 Sun Microsystems, Inc.
026 */
027 package org.opends.server.backends.jeb;
028
029 import java.io.DataInputStream;
030 import java.io.IOException;
031
032
033 /**
034 * This class represents a sorted set of longs. Internally it uses an array
035 * that can grow when necessary. A goal of this class is to avoid memory
036 * allocations where possible.
037 */
038 public class Longs
039 {
040 /**
041 * The internal array where elements are stored.
042 */
043 private long[] array = null;
044
045
046 /**
047 * The number of valid elements in the array.
048 */
049 private int count = 0;
050
051
052
053 /**
054 * Construct a new empty set.
055 */
056 public Longs()
057 {
058 }
059
060
061
062 /**
063 * Decodes a set from a byte array.
064 * @param bytes The encoded value.
065 */
066 void decode(byte[] bytes)
067 {
068 if (bytes == null)
069 {
070 count = 0;
071 return;
072 }
073
074 int count = bytes.length / 8;
075 resize(count);
076
077 for (int pos = 0, i = 0; i < count; i++)
078 {
079 long v = 0;
080 v |= (bytes[pos++] & 0xFFL) << 56;
081 v |= (bytes[pos++] & 0xFFL) << 48;
082 v |= (bytes[pos++] & 0xFFL) << 40;
083 v |= (bytes[pos++] & 0xFFL) << 32;
084 v |= (bytes[pos++] & 0xFFL) << 24;
085 v |= (bytes[pos++] & 0xFFL) << 16;
086 v |= (bytes[pos++] & 0xFFL) << 8;
087 v |= (bytes[pos++] & 0xFFL);
088 array[i] = v;
089 }
090 this.count = count;
091 }
092
093
094
095 /**
096 * Get the number of bytes needed to encode this value into a byte array.
097 * @return The number of bytes needed to encode this value into a byte array.
098 */
099 public int encodedSize()
100 {
101 return count*8;
102 }
103
104
105
106 /**
107 * Encode this value into a byte array.
108 * @param bytes The array into which the value will be encoded. If the
109 * provided array is null, or is not big enough, a new array will be
110 * allocated.
111 * @return The encoded array. If the provided array was bigger than needed
112 * to encode the value then the provided array is returned and the number
113 * of bytes of useful data is given by the encodedSize method.
114 */
115 byte[] encode(byte[] bytes)
116 {
117 int encodedSize = encodedSize();
118 if (bytes == null || bytes.length < encodedSize)
119 {
120 bytes = new byte[encodedSize];
121 }
122
123 for (int pos = 0, i = 0; i < count; i++)
124 {
125 long v = array[i];
126 bytes[pos++] = (byte) ((v >>> 56) & 0xFF);
127 bytes[pos++] = (byte) ((v >>> 48) & 0xFF);
128 bytes[pos++] = (byte) ((v >>> 40) & 0xFF);
129 bytes[pos++] = (byte) ((v >>> 32) & 0xFF);
130 bytes[pos++] = (byte) ((v >>> 24) & 0xFF);
131 bytes[pos++] = (byte) ((v >>> 16) & 0xFF);
132 bytes[pos++] = (byte) ((v >>> 8) & 0xFF);
133 bytes[pos++] = (byte) (v & 0xFF);
134 }
135
136 return bytes;
137 }
138
139
140
141 /**
142 * This is very much like Arrays.binarySearch except that it searches only
143 * an initial portion of the provided array.
144 * @param a The array to be searched.
145 * @param count The number of initial elements in the array to be searched.
146 * @param key The element to search for.
147 * @return See Arrays.binarySearch.
148 */
149 private static int binarySearch(long[] a, int count, long key)
150 {
151 int low = 0;
152 int high = count-1;
153
154 while (low <= high)
155 {
156 int mid = (low + high) >> 1;
157 long midVal = a[mid];
158
159 if (midVal < key)
160 low = mid + 1;
161 else if (midVal > key)
162 high = mid - 1;
163 else
164 return mid; // key found
165 }
166 return -(low + 1); // key not found.
167 }
168
169
170
171 /**
172 * Add a new value to the set.
173 * @param v The value to be added.
174 * @return true if the value was added, false if it was already present
175 * in the set.
176 */
177 public boolean add(long v)
178 {
179 resize(count+1);
180
181 if (count == 0 || v > array[count-1])
182 {
183 array[count++] = v;
184 return true;
185 }
186
187 int pos = binarySearch(array, count, v);
188 if (pos >=0)
189 {
190 return false;
191 }
192
193 // For a negative return value r, the index -(r+1) gives the array
194 // index at which the specified value can be inserted to maintain
195 // the sorted order of the array.
196 pos = -(pos+1);
197
198 System.arraycopy(array, pos, array, pos+1, count-pos);
199 array[pos] = v;
200 count++;
201 return true;
202 }
203
204 /**
205 * Adds all the elements of a provided set to this set if they are not
206 * already present.
207 * @param that The set of elements to be added.
208 */
209 public void addAll(Longs that)
210 {
211 resize(this.count+that.count);
212
213 if (that.count == 0)
214 {
215 return;
216 }
217
218 // Optimize for the case where the two sets are sure to have no overlap.
219 if (this.count == 0 || that.array[0] > this.array[this.count-1])
220 {
221 System.arraycopy(that.array, 0, this.array, this.count, that.count);
222 count += that.count;
223 return;
224 }
225
226 if (this.array[0] > that.array[that.count-1])
227 {
228 System.arraycopy(this.array, 0, this.array, that.count, this.count);
229 System.arraycopy(that.array, 0, this.array, 0, that.count);
230 count += that.count;
231 return;
232 }
233
234 int destPos = binarySearch(this.array, this.count, that.array[0]);
235 if (destPos < 0)
236 {
237 destPos = -(destPos+1);
238 }
239
240 // Make space for the copy.
241 int aCount = this.count - destPos;
242 int aPos = destPos + that.count;
243 int aEnd = aPos + aCount;
244 System.arraycopy(this.array, destPos, this.array, aPos, aCount);
245
246 // Optimize for the case where there is no overlap.
247 if (this.array[aPos] > that.array[that.count-1])
248 {
249 System.arraycopy(that.array, 0, this.array, destPos, that.count);
250 count += that.count;
251 return;
252 }
253
254 int bPos;
255 for ( bPos = 0; aPos < aEnd && bPos < that.count; )
256 {
257 if ( this.array[aPos] < that.array[bPos] )
258 {
259 this.array[destPos++] = this.array[aPos++];
260 }
261 else if ( this.array[aPos] > that.array[bPos] )
262 {
263 this.array[destPos++] = that.array[bPos++];
264 }
265 else
266 {
267 this.array[destPos++] = this.array[aPos++];
268 bPos++;
269 }
270 }
271
272 // Copy any remainder.
273 int aRemain = aEnd - aPos;
274 if (aRemain > 0)
275 {
276 System.arraycopy(this.array, aPos, this.array, destPos, aRemain);
277 destPos += aRemain;
278 }
279
280 int bRemain = that.count - bPos;
281 if (bRemain > 0)
282 {
283 System.arraycopy(that.array, bPos, this.array, destPos, bRemain);
284 destPos += bRemain;
285 }
286
287 count = destPos;
288 }
289
290
291 /**
292 * Deletes all the elements of a provided set from this set if they are
293 * present.
294 * @param that The set of elements to be deleted.
295 */
296 public void deleteAll(Longs that)
297 {
298 int thisPos, thatPos, destPos;
299 for ( destPos = 0, thisPos = 0, thatPos = 0;
300 thisPos < count && thatPos < that.count; )
301 {
302 if ( array[thisPos] < that.array[thatPos] )
303 {
304 array[destPos++] = array[thisPos++];
305 }
306 else if ( array[thisPos] > that.array[thatPos] )
307 {
308 thatPos++;
309 }
310 else
311 {
312 thisPos++;
313 thatPos++;
314 }
315 }
316
317 System.arraycopy(array, thisPos, array, destPos, count - thisPos);
318 destPos += count - thisPos;
319
320 count = destPos;
321 }
322
323
324 /**
325 * Return the number of elements in the set.
326 * @return The number of elements in the set.
327 */
328 public int size()
329 {
330 return count;
331 }
332
333
334 /**
335 * Decode a value from a data input stream.
336 * @param dataInputStream The data input stream to read the value from.
337 * @throws IOException If an I/O error occurs while reading the value.
338 */
339 public void decode(DataInputStream dataInputStream)
340 throws IOException
341 {
342 int len = dataInputStream.readInt();
343 int count = len/8;
344 resize(count);
345 for (int i = 0; i < count; i++)
346 {
347 array[i] = dataInputStream.readLong();
348 }
349 this.count = count;
350 }
351
352
353 /**
354 * Ensures capacity of the internal array for a given number of elements.
355 * @param size The internal array will be guaranteed to be at least this
356 * size.
357 */
358 private void resize(int size)
359 {
360 if (array == null)
361 {
362 array = new long[size];
363 }
364 else if (array.length < size)
365 {
366 // Expand the size of the array in powers of two.
367 int newSize = array.length == 0 ? 1 : array.length;
368 do
369 {
370 newSize *= 2;
371 } while (newSize < size);
372
373 long[] newBytes = new long[newSize];
374 System.arraycopy(array, 0, newBytes, 0, count);
375 array = newBytes;
376 }
377 }
378
379
380 /**
381 * Clears the set leaving it empty.
382 */
383 public void clear()
384 {
385 count = 0;
386 }
387
388
389
390 /**
391 * Convert the set to a new array of longs.
392 * @return An array of longs.
393 */
394 public long[] toArray()
395 {
396 long[] dst = new long[count];
397
398 System.arraycopy(array, 0, dst, 0, count);
399 return dst;
400 }
401
402
403 /**
404 * {@inheritDoc}
405 */
406 @Override
407 public String toString()
408 {
409 StringBuilder b = new StringBuilder();
410 b.append(count);
411 if (count > 0)
412 {
413 b.append('[');
414 b.append(array[0]);
415 if (count > 1)
416 {
417 b.append(':');
418 b.append(array[count-1]);
419 }
420 b.append(']');
421 }
422 return b.toString();
423 }
424
425 }