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 }