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.util.Iterator;
030    import java.util.ArrayList;
031    import java.util.Arrays;
032    
033    /**
034     * Represents a set of Entry IDs.  It can represent a set where the IDs are
035     * not defined, for example when the index entry limit has been exceeded.
036     */
037    public class EntryIDSet implements Iterable<EntryID>
038    {
039    
040    
041      /**
042       * The IDs are stored here in an array in ascending order.
043       * A null array implies not defined, rather than zero IDs.
044       */
045      private long[] values = null;
046    
047      /**
048       * The size of the set when it is not defined. This value is only maintained
049       * when the set is undefined.
050       */
051      private long undefinedSize = Long.MAX_VALUE;
052    
053      /**
054       * The database key containing this set, if the set was constructed
055       * directly from the database.
056       */
057      private byte[] keyBytes = null;
058    
059      /**
060       * Create a new undefined set.
061       */
062      public EntryIDSet()
063      {
064        values = null;
065        undefinedSize = Long.MAX_VALUE;
066      }
067    
068      /**
069       * Create a new undefined set with a initial size.
070       *
071       * @param size The undefined size for this set.
072       */
073      public EntryIDSet(long size)
074      {
075        values = null;
076        undefinedSize = size;
077      }
078    
079      /**
080       * Create a new entry ID set from the raw database value.
081       *
082       * @param keyBytes The database key that contains this value.
083       * @param bytes The database value, or null if there are no entry IDs.
084       */
085      public EntryIDSet(byte[] keyBytes, byte[] bytes)
086      {
087        this.keyBytes = keyBytes;
088    
089        if (bytes == null)
090        {
091          values = new long[0];
092          return;
093        }
094    
095        if (bytes.length == 0)
096        {
097          // Entry limit has exceeded and there is no encoded undefined set size.
098          values = null;
099          undefinedSize = Long.MAX_VALUE;
100        }
101        else if ((bytes[0] & 0x80) == 0x80)
102        {
103          // Entry limit has exceeded and there is an encoded undefined set size.
104          values = null;
105          undefinedSize = JebFormat.entryIDUndefinedSizeFromDatabase(bytes);
106        }
107        else
108        {
109          // Seems like entry limit has not been exceeded and the bytes is a
110          // list of entry IDs.
111          values = JebFormat.entryIDListFromDatabase(bytes);
112        }
113    
114      }
115    
116      /**
117       * Construct an EntryIDSet from an array of longs.
118       *
119       * @param values The array of IDs represented as longs.
120       * @param pos The position of the first ID to take from the array.
121       * @param len the number of IDs to take from the array.
122       */
123      EntryIDSet(long[] values, int pos, int len)
124      {
125        this.values = new long[len];
126        System.arraycopy(values, pos, this.values, 0, len);
127      }
128    
129      /**
130       * Create a new set of entry IDs that is the union of several entry ID sets.
131       *
132       * @param sets A list of entry ID sets.
133       * @param allowDuplicates true if duplicate IDs are allowed in the resulting
134       * set, or if the provided sets are sure not to overlap; false if
135       * duplicates should be eliminated.
136       * @return The union of the provided entry ID sets.
137       */
138      public static EntryIDSet unionOfSets(ArrayList<EntryIDSet> sets,
139                                             boolean allowDuplicates)
140      {
141        boolean needSort = false;
142        int count = 0;
143    
144        boolean undefined = false;
145        for (EntryIDSet l : sets)
146        {
147          if (!l.isDefined())
148          {
149            if(l.undefinedSize == Long.MAX_VALUE)
150            {
151              return new EntryIDSet();
152            }
153            else
154            {
155              undefined = true;
156            }
157          }
158          count += l.size();
159        }
160    
161        if(undefined)
162        {
163          return new EntryIDSet(count);
164        }
165    
166        long[] n = new long[count];
167        int pos = 0;
168        for (EntryIDSet l : sets)
169        {
170          if (l.values.length != 0)
171          {
172            if (!needSort && pos > 0 && l.values[0] < n[pos-1])
173            {
174              needSort = true;
175            }
176            System.arraycopy(l.values, 0, n, pos, l.values.length);
177            pos += l.values.length;
178          }
179        }
180        if (needSort)
181        {
182          Arrays.sort(n);
183        }
184        if (allowDuplicates)
185        {
186          EntryIDSet ret = new EntryIDSet();
187          ret.values = n;
188          return ret;
189        }
190        long[] n1 = new long[n.length];
191        long last = -1;
192        int j = 0;
193        for (int i = 0; i < n.length; i++)
194        {
195          if (n[i] != last)
196          {
197            last = n1[j++] = n[i];
198          }
199        }
200        if (j == n1.length)
201        {
202          EntryIDSet ret = new EntryIDSet();
203          ret.values = n1;
204          return ret;
205        }
206        else
207        {
208          return new EntryIDSet(n1, 0, j);
209        }
210      }
211    
212      /**
213       * Get the size of this entry ID set.
214       *
215       * @return The number of IDs in the set.
216       */
217      public long size()
218      {
219        if (values == null)
220        {
221          return undefinedSize;
222        }
223        else
224        {
225          return values.length;
226        }
227      }
228    
229      /**
230       * Get a string representation of this object.
231       * @return A string representation of this object.
232       */
233      public String toString()
234      {
235        StringBuilder buffer = new StringBuilder(16);
236        toString(buffer);
237        return buffer.toString();
238      }
239    
240      /**
241       * Convert to a short string to aid with debugging.
242       *
243       * @param buffer The string is appended to this string builder.
244       */
245      public void toString(StringBuilder buffer)
246      {
247        if (!isDefined())
248        {
249          if (keyBytes != null)
250          {
251            // The index entry limit was exceeded
252            if(undefinedSize == Long.MAX_VALUE)
253            {
254              buffer.append("[LIMIT-EXCEEDED]");
255            }
256            else
257            {
258              buffer.append("[LIMIT-EXCEEDED:");
259              buffer.append(undefinedSize);
260              buffer.append("]");
261            }
262          }
263          else
264          {
265            // Not indexed
266            buffer.append("[NOT-INDEXED]");
267          }
268        }
269        else
270        {
271          buffer.append("[COUNT:");
272          buffer.append(size());
273          buffer.append("]");
274        }
275      }
276    
277      /**
278       * Determine whether this set of IDs is defined.
279       *
280       * @return true if the set of IDs is defined.
281       */
282      public boolean isDefined()
283      {
284        return values != null;
285      }
286    
287      /**
288       * Get a database representation of this object.
289       * @return A database representation of this object as a byte array.
290       */
291      public byte[] toDatabase()
292      {
293        if(isDefined())
294        {
295          return JebFormat.entryIDListToDatabase(values);
296        }
297        else
298        {
299          return JebFormat.entryIDUndefinedSizeToDatabase(undefinedSize);
300        }
301      }
302    
303      /**
304       * Insert an ID into this set.
305       *
306       * @param entryID The ID to be inserted.
307       * @return true if the set was changed, false if it was not changed,
308       *         for example if the set is undefined or the ID was already present.
309       */
310      public boolean add(EntryID entryID)
311      {
312        if (values == null)
313        {
314          if(undefinedSize != Long.MAX_VALUE)
315          {
316            undefinedSize++;
317          }
318          return true;
319        }
320    
321        long id = entryID.longValue();
322        if (values.length == 0)
323        {
324          values = new long[1];
325          values[0] = id;
326          return true;
327        }
328    
329        if (id > values[values.length-1])
330        {
331          long[] updatedValues = new long[values.length+1];
332          System.arraycopy(values, 0, updatedValues, 0, values.length);
333          updatedValues[values.length] = id;
334          values = updatedValues;
335        }
336        else
337        {
338          int pos = Arrays.binarySearch(values, id);
339          if (pos >= 0)
340          {
341            // The ID is already present.
342            return false;
343          }
344    
345          // For a negative return value r, the index -(r+1) gives the array
346          // index at which the specified value can be inserted to maintain
347          // the sorted order of the array.
348          pos = -(pos+1);
349    
350          long[] updatedValues = new long[values.length+1];
351          System.arraycopy(values, 0, updatedValues, 0, pos);
352          System.arraycopy(values, pos, updatedValues, pos+1, values.length-pos);
353          updatedValues[pos] = id;
354          values = updatedValues;
355        }
356    
357        return true;
358      }
359    
360      /**
361       * Remove an ID from this set.
362       *
363       * @param entryID The ID to be removed
364       * @return true if the set was changed, false if it was not changed,
365       *         for example if the set was undefined or the ID was not present.
366       */
367      public boolean remove(EntryID entryID)
368      {
369        if (values == null)
370        {
371          if(undefinedSize != Long.MAX_VALUE)
372          {
373            undefinedSize--;
374          }
375          return true;
376        }
377    
378        if (values.length == 0)
379        {
380          return false;
381        }
382    
383        long id = entryID.longValue();
384    
385        // Binary search to locate the ID.
386        int pos = Arrays.binarySearch(values, id);
387        if (pos < 0)
388        {
389          // Not found.
390          return false;
391        }
392        else
393        {
394          // Found it.
395          long[] updatedValues = new long[values.length-1];
396          System.arraycopy(values, 0, updatedValues, 0, pos);
397          System.arraycopy(values, pos+1, updatedValues, pos, values.length-pos-1);
398          values = updatedValues;
399          return true;
400        }
401      }
402    
403      /**
404       * Check whether this set of entry IDs contains a given ID.
405       *
406       * @param entryID The ID to be checked.
407       * @return true if this set contains the given ID,
408       *         or if the set is undefined.
409       */
410      public boolean contains(EntryID entryID)
411      {
412        if (values == null)
413        {
414          return true;
415        }
416    
417        long id = entryID.longValue();
418        if (values.length == 0)
419        {
420          return false;
421        }
422    
423        if (id > values[values.length-1])
424        {
425          return false;
426        }
427        else
428        {
429          int pos = Arrays.binarySearch(values, id);
430          if (pos >= 0)
431          {
432            return true;
433          }
434          else
435          {
436            return false;
437          }
438        }
439      }
440    
441      /**
442       * Takes the intersection of this set with another.
443       * Retain those IDs that appear in the given set.
444       *
445       * @param that The set of IDs that are to be retained from this object.
446       */
447      public void retainAll(EntryIDSet that)
448      {
449        if (!this.isDefined())
450        {
451          this.values = that.values;
452          this.undefinedSize = that.undefinedSize;
453          return;
454        }
455    
456        if (!that.isDefined())
457        {
458          return;
459        }
460    
461        // TODO Perhaps Arrays.asList and retainAll list method are more efficient?
462    
463        long[] a = this.values;
464        long[] b = that.values;
465    
466        int ai = 0, bi = 0, ci = 0;
467        long[] c = new long[Math.min(a.length,b.length)];
468        while (ai < a.length && bi < b.length)
469        {
470          if (a[ai] == b[bi])
471          {
472            c[ci] = a[ai];
473            ai++;
474            bi++;
475            ci++;
476          }
477          else if (a[ai] > b[bi])
478          {
479            bi++;
480          }
481          else
482          {
483            ai++;
484          }
485        }
486        if (ci < c.length)
487        {
488          long[] results = new long[ci];
489          System.arraycopy(c, 0, results, 0, ci);
490          values = results;
491        }
492        else
493        {
494          values = c;
495        }
496      }
497    
498      /**
499       * Add all the IDs from a given set that are not already present.
500       *
501       * @param that The set of IDs to be added. It MUST be defined
502       */
503      public void addAll(EntryIDSet that)
504      {
505        if(!that.isDefined())
506        {
507          return;
508        }
509    
510        if (!this.isDefined())
511        {
512          // Assume there are no overlap between IDs in that set with this set
513          if(undefinedSize != Long.MAX_VALUE && that.size() > 0)
514          {
515            undefinedSize += that.size();
516          }
517          return;
518        }
519    
520        long[] a = this.values;
521        long[] b = that.values;
522    
523        if (a.length == 0)
524        {
525          values = b;
526          return;
527        }
528    
529        if (b.length == 0)
530        {
531          return;
532        }
533    
534        // Optimize for case where the two sets are sure to have no overlap.
535        if (b[0] > a[a.length-1])
536        {
537          // All IDs in 'b' are greater than those in 'a'.
538          long[] n = new long[a.length + b.length];
539          System.arraycopy(a, 0, n, 0, a.length);
540          System.arraycopy(b, 0, n, a.length, b.length);
541          values = n;
542          return;
543        }
544    
545        if (a[0] > b[b.length-1])
546        {
547          // All IDs in 'a' are greater than those in 'b'.
548          long[] n = new long[a.length + b.length];
549          System.arraycopy(b, 0, n, 0, b.length);
550          System.arraycopy(a, 0, n, b.length, a.length);
551          values = n;
552          return;
553        }
554    
555        long[] n;
556        if ( b.length < a.length ) {
557          n = a;
558          a = b;
559          b = n;
560        }
561    
562        n = new long[a.length + b.length];
563    
564        int ai, bi, ni;
565        for ( ni = 0, ai = 0, bi = 0; ai < a.length && bi < b.length; ) {
566          if ( a[ai] < b[bi] ) {
567            n[ni++] = a[ai++];
568          } else if ( b[bi] < a[ai] ) {
569            n[ni++] = b[bi++];
570          } else {
571            n[ni++] = a[ai];
572            ai++;
573            bi++;
574          }
575        }
576    
577        // Copy any remainder from the first array.
578        int aRemain = a.length - ai;
579        if (aRemain > 0)
580        {
581          System.arraycopy(a, ai, n, ni, aRemain);
582          ni += aRemain;
583        }
584    
585        // Copy any remainder from the second array.
586        int bRemain = b.length - bi;
587        if (bRemain > 0)
588        {
589          System.arraycopy(b, bi, n, ni, bRemain);
590          ni += bRemain;
591        }
592    
593        if (ni < n.length)
594        {
595          long[] results = new long[ni];
596          System.arraycopy(n, 0, results, 0, ni);
597          values = results;
598        }
599        else
600        {
601          values = n;
602        }
603      }
604    
605      /**
606       * Delete all IDs in this set that are in a given set.
607       *
608       * @param that The set of IDs to be deleted. It MUST be defined.
609       */
610      public void deleteAll(EntryIDSet that)
611      {
612        if(!that.isDefined())
613        {
614          return;
615        }
616    
617        if (!this.isDefined())
618        {
619          // Can't simply subtract the undefined size of this set to that set since
620          // we don't know if there are any duplicates. In this case, we can't
621          // maintain the undefined size anymore.
622          if(undefinedSize != Long.MAX_VALUE && that.size() > 0)
623          {
624            undefinedSize = Long.MAX_VALUE;
625          }
626          return;
627        }
628    
629        long[] a = this.values;
630        long[] b = that.values;
631    
632        if (a.length == 0 || b.length == 0)
633        {
634          return;
635        }
636    
637        // Optimize for case where the two sets are sure to have no overlap.
638        if (b[0] > a[a.length-1])
639        {
640          return;
641        }
642    
643        if (a[0] > b[b.length-1])
644        {
645          return;
646        }
647    
648        long[] n;
649    
650        n = new long[a.length];
651    
652        int ai, bi, ni;
653        for ( ni = 0, ai = 0, bi = 0; ai < a.length && bi < b.length; ) {
654          if ( a[ai] < b[bi] ) {
655            n[ni++] = a[ai++];
656          } else if ( b[bi] < a[ai] ) {
657            bi++;
658          } else {
659            ai++;
660            bi++;
661          }
662        }
663    
664        System.arraycopy(a, ai, n, ni, a.length - ai);
665        ni += a.length - ai;
666    
667        if (ni < a.length)
668        {
669          long[] results = new long[ni];
670          System.arraycopy(n, 0, results, 0, ni);
671          values = results;
672        }
673        else
674        {
675          values = n;
676        }
677      }
678    
679      /**
680       * Create an iterator over the set or an empty iterator
681       * if the set is not defined.
682       *
683       * @return An EntryID iterator.
684       */
685      public Iterator<EntryID> iterator()
686      {
687        if (values == null)
688        {
689          // The set is not defined.
690          return new IDSetIterator(new long[0]);
691        }
692        else
693        {
694          // The set is defined.
695          return new IDSetIterator(values);
696        }
697      }
698    
699      /**
700       * Create an iterator over the set or an empty iterator
701       * if the set is not defined.
702       *
703       * @param  begin  The entry ID of the first entry to return in the list.
704       *
705       * @return An EntryID iterator.
706       */
707      public Iterator<EntryID> iterator(EntryID begin)
708      {
709        if (values == null)
710        {
711          // The set is not defined.
712          return new IDSetIterator(new long[0]);
713        }
714        else
715        {
716          // The set is defined.
717          return new IDSetIterator(values, begin);
718        }
719      }
720    
721    }