001package org.jadira.reflection.cloning.collection;
002
003import java.util.Arrays;
004import java.util.Collection;
005import java.util.IdentityHashMap;
006import java.util.Iterator;
007import java.util.Set;
008
009/**
010 * A wrapper for IdentityHashMap that resolves object matches quickly for
011 * small sets using binary search
012 * @param <E> The type of entries within the set 
013 */
014public class FastIdentityHashSet<E> implements Set<E> {
015
016        private int[] entryKeys = new int[0];
017        private static final int ARRAY_SIZE = 12;
018        
019        private IdentityHashMap<E, Boolean> hashMap = new IdentityHashMap<E, Boolean>(12);
020        
021        @Override
022        public int size() {
023                if (entryKeys != null) {
024                        return entryKeys.length;
025                } else {
026                        return hashMap.size();
027                }
028        }
029        
030        @Override
031        public boolean isEmpty() {
032                if (entryKeys != null) {
033                        return entryKeys.length == 0;
034                } else {
035                        return hashMap.isEmpty();
036                }               
037        }
038        
039        @Override
040        public boolean contains(Object key) {
041                if (entryKeys != null) {
042                        return Arrays.binarySearch(entryKeys, System.identityHashCode(key)) >= 0;
043                } else {
044                        return hashMap.containsKey(System.identityHashCode(key));
045                }
046        }
047        
048        @Override
049        public Iterator<E> iterator() {
050                return hashMap.keySet().iterator();
051        }
052        
053        @Override
054        public Object[] toArray() {
055                return hashMap.keySet().toArray();
056        }
057        
058        @SuppressWarnings("unchecked")
059        @Override
060        public <T> T[] toArray(T[] a) {
061                return (T[]) hashMap.keySet().toArray();
062        }
063        
064        @Override
065        public boolean add(E e) {
066                boolean res = hashMap.put(e, Boolean.TRUE);
067                if (res) {
068                        if (entryKeys == null || (entryKeys.length + 1 <= ARRAY_SIZE)) {
069                                Object[] keys = hashMap.keySet().toArray(new Object[]{});
070                                entryKeys = new int[keys.length];
071                                for (int i = 0; i < keys.length; i++) {
072                                        entryKeys[i] = System.identityHashCode(keys[i]);
073                                }
074                                Arrays.sort(entryKeys);
075                        } else {
076                                entryKeys = null;
077                        }
078                }
079                return res;
080        }
081        
082        @Override
083        public boolean remove(Object o) {
084                boolean res = hashMap.remove(o);
085                if (res) {
086                        if (hashMap.size() <= ARRAY_SIZE) {
087                                Object[] keys = hashMap.keySet().toArray(new Object[]{});
088                
089                                entryKeys = new int[keys.length];
090                                for (int i = 0; i < keys.length; i++) {
091                                        entryKeys[i] = System.identityHashCode(keys[i]);
092                                }
093                                Arrays.sort(entryKeys);
094                        } else {
095                                entryKeys = null;
096                        }
097                }
098                return res;     
099        }
100        
101        @Override
102        public boolean containsAll(Collection<?> c) {
103                for (Object next : c) {
104                        if(!contains(next)) {
105                                return false;
106                        }
107                }
108                return true;
109        }
110        
111        @Override
112        public boolean addAll(Collection<? extends E> c) {
113                
114                boolean res = false;
115                for (E next : c) {
116                        boolean nextRes = add(next);
117                        if (nextRes) { res = nextRes; }
118                }
119                return res;
120        }
121        
122        @Override
123        public void clear() {
124                hashMap.clear();
125                entryKeys = new int[]{};
126        }
127
128        @Override
129        public boolean retainAll(Collection<?> c) {
130                
131                Set<E> keySet = hashMap.keySet();
132                boolean res = keySet.retainAll(c);
133                
134                hashMap.clear();
135                
136                for (E next : keySet) {
137                        hashMap.put(next, Boolean.TRUE);
138                }
139                
140                if (res) {
141                        Object[] keys = hashMap.keySet().toArray(new Object[]{});
142                        entryKeys = new int[keys.length];
143                        for (int i = 0; i < keys.length; i++) {
144                                entryKeys[i] = System.identityHashCode(keys[i]);
145                        }
146                        Arrays.sort(entryKeys);
147                }
148                return res;
149        }
150
151        @Override
152        public boolean removeAll(Collection<?> c) {
153                boolean res = false;
154                for (Object next : c) {
155                        boolean nextRes = remove(next);
156                        if (nextRes) { res = nextRes; }
157                }
158                return res;
159        }
160}