12c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown/* 22c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * Copyright (C) 2011 The Android Open Source Project 32c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * 42c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * Licensed under the Apache License, Version 2.0 (the "License"); 52c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * you may not use this file except in compliance with the License. 62c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * You may obtain a copy of the License at 72c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * 82c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * http://www.apache.org/licenses/LICENSE-2.0 92c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * 102c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * Unless required by applicable law or agreed to in writing, software 112c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * distributed under the License is distributed on an "AS IS" BASIS, 122c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 132c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * See the License for the specific language governing permissions and 142c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * limitations under the License. 152c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown */ 162c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 172c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brownpackage android.util; 182c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 192c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brownimport java.util.AbstractSet; 202c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brownimport java.util.Iterator; 212c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 222c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown/** 232c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * A fast immutable set wrapper for an array that is optimized for non-concurrent iteration. 242c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * The same iterator instance is reused each time to avoid creating lots of garbage. 252c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * Iterating over an array in this fashion is 2.5x faster than iterating over a {@link HashSet} 262c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * so it is worth copying the contents of the set to an array when iterating over it 272c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * hundreds of times. 282c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown * @hide 292c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown */ 302c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brownpublic final class FastImmutableArraySet<T> extends AbstractSet<T> { 312c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown FastIterator<T> mIterator; 322c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown T[] mContents; 332c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 342c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public FastImmutableArraySet(T[] contents) { 352c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown mContents = contents; 362c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 372c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 382c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown @Override 392c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public Iterator<T> iterator() { 402c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown FastIterator<T> it = mIterator; 412c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown if (it == null) { 422c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown it = new FastIterator<T>(mContents); 432c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown mIterator = it; 442c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } else { 452c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown it.mIndex = 0; 462c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 472c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown return it; 482c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 492c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 502c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown @Override 512c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public int size() { 522c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown return mContents.length; 532c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 542c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 552c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown private static final class FastIterator<T> implements Iterator<T> { 562c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown private final T[] mContents; 572c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown int mIndex; 582c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 592c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public FastIterator(T[] contents) { 602c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown mContents = contents; 612c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 622c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 632c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown @Override 642c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public boolean hasNext() { 652c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown return mIndex != mContents.length; 662c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 672c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 682c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown @Override 692c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public T next() { 702c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown return mContents[mIndex++]; 712c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 722c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown 732c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown @Override 742c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown public void remove() { 752c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown throw new UnsupportedOperationException(); 762c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 772c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown } 782c376fc46cd01b12e003a7bf83d82f527f6efaf1Jeff Brown} 79