001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/core/core/src/main/jtemp/org/openimaj/util/array/SparseBinSearch#T#Array.jtemp
004*/
005/**
006 * Copyright (c) 2011, The University of Southampton and the individual contributors.
007 * All rights reserved.
008 *
009 * Redistribution and use in source and binary forms, with or without modification,
010 * are permitted provided that the following conditions are met:
011 *
012 *   *  Redistributions of source code must retain the above copyright notice,
013 *      this list of conditions and the following disclaimer.
014 *
015 *   *  Redistributions in binary form must reproduce the above copyright notice,
016 *      this list of conditions and the following disclaimer in the documentation
017 *      and/or other materials provided with the distribution.
018 *
019 *   *  Neither the name of the University of Southampton nor the names of its
020 *      contributors may be used to endorse or promote products derived from this
021 *      software without specific prior written permission.
022 *
023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
024 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
025 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
026 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
027 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
028 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
029 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
030 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
031 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
032 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
033 */
034package org.openimaj.util.array;
035
036import java.util.Arrays;
037import java.util.Iterator;
038import java.util.NoSuchElementException;
039
040/**
041 * A Sparse array of short values implemented using a pair of 
042 * sorted parallel arrays. The first array holds the indexes of
043 * the non-zero elements in ascending order; the second holds
044 * the corresponding values.
045 * <p>
046 * Element access has worst-case O(log n) performance. Appends (where
047 * the index being added is greater than the existing indices) has O(1)
048 * complexity. Random puts have worst case O(n + log n) complexity. 
049 * Complexity for getting values by increasing index for iteration 
050 * through the non-zero values is O(1).
051 * <p>
052 * In summary, this implementation has good access performance, and is
053 * fast for appending values, but slow for putting at random indices. 
054 * It is is optimal for a scenario where you first create the sparse 
055 * array and put values in order of increasing indices, and later use 
056 * the array mostly for reading.
057 *  
058 * @see "http://stackoverflow.com/questions/1880804/java-time-efficient-sparse-1d-array-double"
059 * 
060 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
061 *
062 */
063public class SparseBinSearchShortArray extends SparseShortArray {
064        protected int[] keys;
065        protected short[] values;
066        protected int used;
067        
068        /**
069         * Construct from an existing array of values
070         * @param values the values
071         */
072        public SparseBinSearchShortArray(short[] values) {
073                this(values.length);
074                
075                for (int i=0; i<values.length; i++) {
076                        if (values[i] != 0) set(i, values[i]);
077                }
078        }
079        
080        /**
081         * Generate a new {@link SparseBinSearchShortArray} wrapper which works around
082         * an existing array of keys and values
083         * @param length
084         * @param used
085         * @param keys
086         * @param values
087         */
088        public SparseBinSearchShortArray(int length, int used, int[] keys, short[] values){
089                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
090                if (length < values.length) throw new IllegalArgumentException("length is shorter than number of current values!");
091                if (keys.length!=values.length) throw new IllegalArgumentException("Number of keys does not match number of values.");
092                this.length = length;
093                this.used = used;
094                this.keys = keys;
095                this.values = values;
096        }
097
098        /**
099         * Construct the array with the given length
100         * @param length the length
101         */
102        public SparseBinSearchShortArray(int length) {
103                this(length, DEFAULT_CAPACITY);
104        }
105
106        /**
107         * Construct the array with the given length and capacity for non-zero elements
108         * @param length the length
109         * @param capacity the capacity
110         */
111        public SparseBinSearchShortArray(int length, int capacity) {
112                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
113                if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
114                
115                this.length = length;
116                this.keys = new int[capacity];
117                this.values = new short[capacity];
118        }
119        
120        /**
121         * Construct the array with the given length and expected density
122         * @param length the length
123         * @param density the density
124         */
125        public SparseBinSearchShortArray(int length, float density) {
126                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
127                if (density <= 0 || density > 1) throw new IllegalArgumentException("density must be > 0 and < 1");
128                
129                this.length = length;
130                int capacity = (int) (density * length);
131                this.keys = new int[capacity];
132                this.values = new short[capacity];
133        }
134        
135        @Override
136        public int[] indices() {
137                return Arrays.copyOf(keys, used);
138        }
139
140        @Override
141        public short[] values() {
142                return Arrays.copyOf(values, used);
143        }
144
145        @Override
146        public Iterable<DualEntry> unionEntries(final SparseShortArray otherArray) {
147                if (otherArray instanceof SparseBinSearchShortArray) {
148                        return unionEntries((SparseBinSearchShortArray) otherArray);
149                }
150                
151                return super.unionEntries(otherArray);
152        }
153        
154        /**
155         * Provide an iterator over the union of values present in
156         * both this array and another array. Values where
157         * both arrays are zero are skipped.
158         * <p>
159         * Note: the {@link SparseShortArray.DualEntry} returned by the iterator
160         * is always the same object. In addition, the iterator
161         * cannot affect the value of anything in the array (i.e.
162         * changing anything in the {@link SparseShortArray.DualEntry} has no effect
163         * on the actual array).
164         * 
165         * @param otherArray the second array 
166         * 
167         * @return an iterator over the non-zero values.
168         */
169        public Iterable<DualEntry> unionEntries(final SparseBinSearchShortArray otherArray) {
170                return new Iterable<DualEntry>() {
171                        @Override
172                        public Iterator<DualEntry> iterator() {
173                                return new Iterator<DualEntry>() {
174                                        private DualEntry entry = new DualEntry();
175                                        private int innerIndex = 0;
176                                        private int otherInnerIndex = 0;
177
178                                        @Override
179                                        public boolean hasNext() {
180                                                return innerIndex < used || otherInnerIndex < otherArray.used;
181                                        }
182
183                                        @Override
184                                        public DualEntry next() {
185                                                if (!hasNext()) throw new NoSuchElementException();
186
187                                                if (innerIndex < used && (otherInnerIndex >= otherArray.used || keys[innerIndex] < otherArray.keys[otherInnerIndex])) {
188                                                        entry.index = keys[innerIndex];
189                                                        entry.value = values[innerIndex];
190                                                        entry.otherValue = 0;
191                                                        innerIndex++;
192                                                } else if (otherInnerIndex < otherArray.used && (innerIndex >= used || keys[innerIndex] > otherArray.keys[otherInnerIndex])) {
193                                                        entry.index = otherArray.keys[otherInnerIndex];
194                                                        entry.value = 0;
195                                                        entry.otherValue = otherArray.values[otherInnerIndex];
196                                                        otherInnerIndex++;
197                                                } else {
198                                                        entry.index = keys[innerIndex];
199                                                        entry.value = values[innerIndex];
200                                                        entry.otherValue = otherArray.values[otherInnerIndex];
201                                                        innerIndex++;
202                                                        otherInnerIndex++;
203                                                }
204
205                                                return entry;
206                                        }
207
208                                        @Override
209                                        public void remove() {
210                                                throw new UnsupportedOperationException();
211                                        }
212                                };
213                        }
214                };
215        }
216
217        @Override
218        public Iterable<Entry> entries() {
219                return new Iterable<Entry>() {
220                        @Override
221                        public Iterator<Entry> iterator() {
222                                return new Iterator<Entry>() {
223                                        private Entry entry = new Entry();
224                                        private int innerIndex = 0;
225
226                                        @Override
227                                        public boolean hasNext() {
228                                                return innerIndex < used;
229                                        }
230
231                                        @Override
232                                        public Entry next() {
233                                                if (!hasNext()) throw new NoSuchElementException();
234                                                
235                                                entry.index = keys[innerIndex];
236                                                entry.value = values[innerIndex];
237                                                innerIndex++;
238                                                
239                                                return entry;
240                                        }
241
242                                        @Override
243                                        public void remove() {
244                                                throw new UnsupportedOperationException();
245                                        }
246                                };
247                        }
248                };
249        }
250
251        @Override
252        public boolean equals(Object obj) {
253                if (!(obj instanceof SparseBinSearchShortArray)) return false;
254                
255                return length == ((SparseBinSearchShortArray)obj).length &&
256                                used == ((SparseBinSearchShortArray)obj).used && 
257                                Arrays.equals(keys, ((SparseBinSearchShortArray)obj).keys) &&
258                                Arrays.equals(values, values);
259        }
260
261        @Override
262        public short get(int key) {
263                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key));
264                int spot = Arrays.binarySearch(keys, 0, used, key);
265                return spot < 0 ? 0 : values[spot];
266        }
267
268        @Override
269        public int hashCode() {
270                return length ^ Arrays.hashCode(keys) ^ Arrays.hashCode(values);
271        }
272
273        @Override
274        public boolean isUsed(int key) {
275                return 0 <= Arrays.binarySearch(keys, 0, used, key);
276        }
277
278        @Override
279        public short set(int key, short value) {
280                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key));
281                int spot = Arrays.binarySearch(keys, 0, used, key);
282                if (spot >= 0) return values[spot] = value;
283                else return update(-1 - spot, key, value);
284        }
285
286        @Override
287        public short increment(int key, short value) {
288                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key));
289                int spot = Arrays.binarySearch(keys, 0, used, key);
290                if (spot >= 0) return values[spot] += value;
291                return update(-1 - spot, key, value);
292        }
293        
294        private short update(int spot, int key, short value) {
295                // grow if reaching end of capacity
296                if (used == keys.length) {
297                        int capacity = (keys.length * 3) / 2 + 1;
298                        keys = Arrays.copyOf(keys, capacity);
299                        values = Arrays.copyOf(values, capacity);
300                }
301                
302                // shift values if not appending
303                if (spot < used) {
304                        System.arraycopy(keys, spot, keys, spot + 1, used - spot);
305                        System.arraycopy(values, spot, values, spot + 1, used - spot);
306                }
307                
308                used++;
309                keys[spot] = key;
310                return values[spot] = value;
311        }
312
313        @Override
314        public int used() {
315                return used;
316        }
317
318        @Override
319        public void compact() {
320                keys = Arrays.copyOf(keys, used);
321                values = Arrays.copyOf(values, used);
322        }
323        
324        /* (non-Javadoc)
325         * @see org.openimaj.util.array.SparseDoubleArray#copy()
326         */
327        @Override
328        public SparseShortArray copy() {
329                SparseBinSearchShortArray copy = new SparseBinSearchShortArray(length);
330                copy.used = used;
331                copy.keys = Arrays.copyOf(keys, keys.length);
332                copy.values = Arrays.copyOf(values, values.length);
333                return copy;
334        }
335
336        /* (non-Javadoc)
337         * @see org.openimaj.util.array.SparseDoubleArray#reverse()
338         */
339        @Override
340        public SparseShortArray reverse() {
341                final int len = used;
342                final int hlen = len / 2;
343                
344                for(int i = 0; i < hlen; i++) {
345                        short tmpVal = values[i];
346                        values[i] = values[len - i - 1];
347                        values[len - i - 1] = tmpVal;
348                        
349                        int tmpKey = keys[i];
350                        keys[i] = length - keys[len - i - 1];
351                        keys[len - i - 1] = length - tmpKey;
352                }
353                
354                return this;
355        }
356}