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    }