1 /*
   2  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package com.sun.glass.ui.monocle.util;
  26 
  27 import java.util.Arrays;
  28 
  29 /**
  30  * Mutable sorted set of int values, optimized for a small number of values. Not
  31  * thread-safe.
  32  */
  33 public class IntSet {
  34     private int[] elements = new int[4];
  35     private int size = 0;
  36 
  37     public void addInt(int value) {
  38         int i = getIndex(value);
  39         if (i < 0) {
  40             int insertionPoint = -1 - i;
  41             if (size == elements.length) {
  42                 elements = Arrays.copyOf(elements, size * 2);
  43             }
  44             if (insertionPoint != size) {
  45                 System.arraycopy(elements, insertionPoint,
  46                                  elements, insertionPoint + 1,
  47                                  size - insertionPoint);
  48             }
  49             elements[insertionPoint] = value;
  50             size ++;
  51         }
  52     }
  53 
  54     public void removeInt(int value) {
  55         int i = getIndex(value);
  56         if (i >= 0) {
  57             if (i < size - 1) {
  58                 System.arraycopy(elements, i + 1, elements, i, size - i - 1);
  59             }
  60             size --;
  61         }
  62     }
  63 
  64     public boolean containsInt(int value) {
  65         return getIndex(value) >= 0;
  66     }
  67 
  68     private int getIndex(int value) {
  69         int i;
  70         for (i = 0; i < size; i++) {
  71             if (elements[i] == value) {
  72                 return i;
  73             } else if (elements[i] > value) {
  74                 return -i - 1;
  75             }
  76         }
  77         return -i - 1;
  78     }
  79 
  80     public int get(int index) {
  81         return elements[index];
  82     }
  83 
  84     /** Adds to the set "dest" values that in this set but are not in the set
  85      * "compared". */
  86     public void difference(IntSet dest, IntSet compared) {
  87         int i = 0;
  88         int j = 0;
  89         while (i < size && j < compared.size) {
  90             int a = elements[i];
  91             int b = compared.elements[j];
  92             if (a < b) {
  93                 // our set has a value that is not in "compared"
  94                 dest.addInt(a);
  95                 i ++;
  96             } else if (a > b) {
  97                 // "compared" has a value that is not in our set.
  98                 j ++;
  99             } else {
 100                 // the sets match at this index.
 101                 i ++;
 102                 j ++;
 103             }
 104         }
 105         // anything left in our set is part of the delta and belongs in "dest".
 106         while (i < size) {
 107             dest.addInt(elements[i]);
 108             i ++;
 109         }
 110     }
 111 
 112     public void clear() {
 113         size = 0;
 114     }
 115 
 116     public int size() {
 117         return size;
 118     }
 119 
 120     public boolean isEmpty() {
 121         return size == 0;
 122     }
 123 
 124     /** Copies the contents of this set to the target set. */
 125     public void copyTo(IntSet target) {
 126         if (target.elements.length < size) {
 127             target.elements = Arrays.copyOf(elements, elements.length);
 128         } else {
 129             System.arraycopy(elements, 0, target.elements, 0, size);
 130         }
 131         target.size = size;
 132     }
 133 
 134     public boolean equals(IntSet set) {
 135         if (set.size == size) {
 136             for (int i = 0; i < size; i++) {
 137                 if (set.elements[i] != elements[i]) {
 138                     return false;
 139                 }
 140             }
 141             return true;
 142         } else {
 143             return false;
 144         }
 145     }
 146 
 147     public boolean equals(Object o) {
 148         if (o instanceof IntSet) {
 149             return equals((IntSet) o);
 150         } else {
 151             return false;
 152         }
 153     }
 154 
 155     public String toString() {
 156         StringBuffer sb = new StringBuffer("IntSet[");
 157         for (int i = 0; i < size; i++) {
 158             sb.append(elements[i]);
 159             if (i < size - 1) {
 160                 sb.append(",");
 161             }
 162         }
 163         sb.append("]");
 164         return sb.toString();
 165     }
 166 
 167 }