001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/core/core/src/main/jtemp/org/openimaj/util/array/SparseHashed#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 gnu.trove.iterator.TIntShortIterator;
037import gnu.trove.map.hash.TIntShortHashMap;
038
039import java.util.Iterator;
040import java.util.NoSuchElementException;
041
042/**
043 * A {@link SparseShortArray} implementation based on a
044 * {@link TIntShortHashMap}. Unlike the {@link SparseBinSearchShortArray}
045 * implementation, this class should be good for the case
046 * where random insertion is used frequently (O(1) insert complexity).
047 * In the worst-case search is O(n), although in practice it should be better.
048 * <p>
049 * Note that the {@link #entries()} method will in general not return
050 * the entries in index order. 
051 * 
052 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
053 *
054 */
055public class SparseHashedShortArray extends SparseShortArray {
056        TIntShortHashMap data;
057        
058        /**
059         * @param values
060         */
061        public SparseHashedShortArray(short[] values) {
062                this(values.length);
063                
064                for (int i=0; i<values.length; i++) {
065                        if (values[i] != 0) set(i, values[i]);
066                }
067        }
068
069        /**
070         * Construct the array with the given length
071         * @param length the length
072         */
073        public SparseHashedShortArray(int length) {
074                this(length, DEFAULT_CAPACITY);
075        }
076
077        /**
078         * Construct the array with the given length and capacity for non-zero elements
079         * @param length the length
080         * @param capacity the capacity
081         */
082        public SparseHashedShortArray(int length, int capacity) {
083                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
084                if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
085        
086                this.length = length;
087                this.data = new TIntShortHashMap(capacity);
088        }
089
090        /**
091         * Construct the array with the given length and expected density
092         * @param length the length
093         * @param density the density
094         */
095        public SparseHashedShortArray(int length, float density) {
096                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
097                if (density <= 0 || density > 1) throw new IllegalArgumentException("density must be > 0 and < 1");
098                
099                this.length = length;
100                int capacity = (int) (density * length);
101                this.data = new TIntShortHashMap(capacity);
102        }
103        
104        @Override
105        public short increment(int key, short value) {
106                return data.adjustOrPutValue(key, value, value);
107        }
108
109        @Override
110        public int[] indices() {
111                return data.keys();
112        }
113
114        @Override
115        public short[] values() {
116                return data.values();
117        }
118
119        /* (non-Javadoc)
120         * @see org.openimaj.util.array.SparseShortArray#entries()
121         */
122        @Override
123        public Iterable<Entry> entries() {
124                return new Iterable<Entry>() {
125                        @Override
126                        public Iterator<Entry> iterator() {
127                                return new Iterator<Entry>() {
128                                        private Entry entry = new Entry();
129                                        private TIntShortIterator iterator = data.iterator();
130
131                                        @Override
132                                        public boolean hasNext() {
133                                                return iterator.hasNext();
134                                        }
135
136                                        @Override
137                                        public Entry next() {
138                                                if (!hasNext()) throw new NoSuchElementException();
139                                                iterator.advance();
140                                                entry.index = iterator.key();
141                                                entry.value = iterator.value();
142                                                
143                                                return entry;
144                                        }
145
146                                        @Override
147                                        public void remove() {
148                                                throw new UnsupportedOperationException();
149                                        }
150                                };
151                        }
152                };
153        }
154
155        @Override
156        public boolean equals(Object obj) {
157                if (!(obj instanceof SparseHashedShortArray)) return false;
158                
159                return length == ((SparseHashedShortArray)obj).length &&
160                                data.equals(((SparseHashedShortArray)obj).data);
161        }
162
163        @Override
164        public short get(int key) {
165                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key)); 
166                return data.get(key);
167        }
168
169        @Override
170        public int hashCode() {
171                return length ^ data.hashCode();
172        }
173
174        @Override
175        public boolean isUsed(int key) {
176                return data.contains(key);
177        }
178
179        @Override
180        public short set(int key, short value) {
181                return data.put(key, value);
182        }
183
184        @Override
185        public int used() {
186                return data.size();
187        }
188
189        @Override
190        public void compact() {
191                data.compact();
192        }
193        
194        /* (non-Javadoc)
195         * @see org.openimaj.util.array.SparseDoubleArray#copy()
196         */
197        @Override
198        public SparseShortArray copy() {
199                SparseHashedShortArray copy = new SparseHashedShortArray(length);
200                
201                copy.data = new TIntShortHashMap(data);
202                
203                return copy;
204        }
205
206        /* (non-Javadoc)
207         * @see org.openimaj.util.array.SparseDoubleArray#reverse()
208         */
209        @Override
210        public SparseShortArray reverse() {
211                //TODO: this could be more efficient and avoid the copy
212                TIntShortHashMap tmp = new TIntShortHashMap(data.size());
213
214                for (Entry e : entries())
215                        tmp.put(length - e.index, e.value);
216                
217                this.data = tmp;
218                
219                return this;
220        }
221}