001/*
002        AUTOMATICALLY GENERATED BY jTemp FROM
003        /Users/jsh2/Work/openimaj/target/checkout/core/core/src/main/jtemp/org/openimaj/util/array/Sparse#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.TIntIterator;
037import gnu.trove.set.hash.TIntHashSet;
038
039import java.io.DataInput;
040import java.io.DataOutput;
041import java.io.IOException;
042import java.io.PrintWriter;
043import java.util.Arrays;
044import java.util.Iterator;
045import java.util.List;
046import java.util.Scanner;
047
048import org.openimaj.io.ReadWriteable;
049import org.openimaj.util.concatenate.Concatenatable;
050
051/**
052 * A sparse array of int values. Includes some elementary
053 * vector operations (add, subtract, scalar multiply, dot product).
054 * 
055 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
056 *
057 */
058public abstract class SparseIntArray implements ReadWriteable, Concatenatable<SparseIntArray, SparseIntArray> {
059        protected static final int DEFAULT_CAPACITY = 10;
060        
061        /**
062         * An entry in a {@link SparseIntArray}, consisting of
063         * an index and value.
064         * 
065         * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
066         */
067        public static class Entry {
068                /**
069                 * The index in the array of the value
070                 */
071                public int index;
072                
073                /**
074                 * The value of the array at the index 
075                 */
076                public int value;
077        }
078        
079        /**
080         * An entry representing the values in two parallel {@link SparseIntArray}s
081         * at the same index.
082         * 
083         * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
084         */
085        public static class DualEntry extends Entry {           
086                /**
087                 * The value of the other array at the index 
088                 */
089                public int otherValue;
090        }
091        
092        /**
093         * The length of the array 
094         */
095        public int length;
096        
097        /**
098         * Increment the value at the given index.
099         * 
100         * @param index the index
101         * @param value the amount to increment by.
102         * @return the new value 
103         */
104        public abstract int increment(int index, int value);
105
106        /**
107         * @return the indices of the non-zero valued entries of the array.
108         */
109        public abstract int[] indices();
110        
111        /**
112         * @return the packed non-zero valued entries of the array.
113         */
114        public abstract int[] values();
115
116        /**
117         * Provide an iterator over the non-zero values.
118         * <p>
119         * Note: the {@link Entry} returned by the iterator
120         * is always the same object. In addition, the iterator
121         * cannot affect the value of anything in the array (i.e.
122         * changing anything in the {@link Entry} has no effect
123         * on the actual array).
124         * 
125         * @return an iterator over the non-zero values.
126         */
127        public abstract Iterable<Entry> entries();
128        
129        /**
130         * Provide an iterator over the union of values present in
131         * both this array and another array. Values where
132         * both arrays are zero are skipped.
133         * <p>
134         * Note: the {@link DualEntry} returned by the iterator
135         * is always the same object. In addition, the iterator
136         * cannot affect the value of anything in the array (i.e.
137         * changing anything in the {@link DualEntry} has no effect
138         * on the actual array).
139         * 
140         * @param otherArray the second array 
141         * 
142         * @return an iterator over the non-zero values.
143         */
144        public Iterable<DualEntry> unionEntries(final SparseIntArray otherArray) {
145                //Naive implementation: creates the union of the indices and fetches from
146                //them. Subclasses should override for efficiency.
147                return new Iterable<DualEntry>() {
148                        @Override
149                        public Iterator<DualEntry> iterator() {
150                                final TIntHashSet keys = new TIntHashSet(SparseIntArray.this.indices());
151                                keys.addAll(otherArray.indices());
152                                
153                                return new Iterator<DualEntry>() {
154                                        DualEntry entry = new DualEntry();
155                                        TIntIterator iterator = keys.iterator();
156                                        
157                                        @Override
158                                        public boolean hasNext() {
159                                                return iterator.hasNext();
160                                        }
161
162                                        @Override
163                                        public DualEntry next() {
164                                                entry.index = iterator.next();
165                                                entry.value = SparseIntArray.this.get(entry.index);
166                                                entry.otherValue = otherArray.get(entry.index);
167                                                return entry;
168                                        }
169
170                                        @Override
171                                        public void remove() {
172                                                throw new UnsupportedOperationException();
173                                        }
174                                };
175                        }
176                };
177        }
178        
179        /**
180         * Provide an iterator over the intersection of values present in
181         * both this array and another array. Values are only
182         * presented for the cases where both arrays are non-zero.
183         * <p>
184         * Note: the {@link DualEntry} returned by the iterator
185         * is always the same object. In addition, the iterator
186         * cannot affect the value of anything in the array (i.e.
187         * changing anything in the {@link DualEntry} has no effect
188         * on the actual array).
189         * 
190         * @param otherArray the second array
191         * 
192         * @return an iterator over the non-zero values.
193         */
194        public Iterable<DualEntry> intersectEntries(final SparseIntArray otherArray) {
195                //Naive implementation: creates the intersection of the indices and fetches from
196                //them. Subclasses should override for efficiency.
197                return new Iterable<DualEntry>() {
198                        @Override
199                        public Iterator<DualEntry> iterator() {
200                                final TIntHashSet keys;
201                                
202                                if (used() < otherArray.used()) {
203                                        keys = new TIntHashSet(SparseIntArray.this.indices());
204                                        keys.retainAll(otherArray.indices());
205                                } else {
206                                        keys = new TIntHashSet(otherArray.indices());
207                                        keys.retainAll(SparseIntArray.this.indices());
208                                }
209
210                                return new Iterator<DualEntry>() {
211                                        DualEntry entry = new DualEntry();
212                                        TIntIterator iterator = keys.iterator();
213
214                                        @Override
215                                        public boolean hasNext() {
216                                                return iterator.hasNext();
217                                        }
218
219                                        @Override
220                                        public DualEntry next() {
221                                                entry.index = iterator.next();
222                                                entry.value = SparseIntArray.this.get(entry.index);
223                                                entry.otherValue = otherArray.get(entry.index);
224                                                return entry;
225                                        }
226
227                                        @Override
228                                        public void remove() {
229                                                throw new UnsupportedOperationException();
230                                        }
231                                };
232                        }
233                };
234        }
235        
236        /**
237         * Get the value at the given index.
238         * @param index the index
239         * @return the value at the index.
240         */
241        public abstract int get(int index);
242
243        /**
244         * Check whether the given index is used (i.e. has a non-zero value)
245         * @param index the index
246         * @return true if not used; false otherwise.
247         */
248        public abstract boolean isUsed(int index);
249
250        /**
251         * Set the value at the given index.
252         * 
253         * @param index the index.
254         * @param value the value to set.
255         * @return the value
256         */
257        public abstract int set(int index, int value);
258
259        /**
260         * Set the length of the array. Arrays can only be
261         * extended with this method.
262         * @param newLength the new array length
263         * @throws IllegalArgumentException if the new length is shorter than 
264         *              the existing length.
265         */
266        public void setLength(int newLength) {
267                if (newLength < this.length) throw new IllegalArgumentException("can't make sparse array shorter");
268                this.length = newLength;
269        }
270
271        /**
272         * @return the length of the array
273         */
274        public int size() {
275                return length;
276        }
277        
278        /**
279         * @return the length of the array
280         */
281        public int length() {
282                return length;
283        }
284
285        /**
286         * @return the number of non-zero entries in the array
287         */
288        public abstract int used();
289        
290        /**
291         * @return the density of the array (number of used elements divided
292         * by array length)
293         */
294        public float density() {
295                return (float)used() / (float)length; 
296        }
297        
298        /**
299         * Compact the space being used by the array if possible.
300         */
301        public abstract void compact();
302        
303        /* (non-Javadoc)
304         * @see org.openimaj.io.WriteableASCII#writeASCII(java.io.PrintWriter)
305         */
306        @Override
307        public void writeASCII(PrintWriter out) throws IOException {
308                out.print(this.length);
309                out.print(" ");
310                
311                for (Entry e : entries()) {
312                        out.print(e.index + ":" + e.value + " ");                       
313                }
314        }
315
316        /* (non-Javadoc)
317         * @see org.openimaj.io.ReadableASCII#readASCII(java.util.Scanner)
318         */
319        @Override
320        public void readASCII(Scanner in) throws IOException {
321                this.length = in.nextInt();
322                
323                String[] parts = in.nextLine().split(" ");
324                for (String part : parts) {
325                        String[] bits = part.split(":");
326                        
327                        set(Integer.parseInt(bits[0]), Integer.parseInt(bits[1]));
328                }
329        }
330
331        /* (non-Javadoc)
332         * @see org.openimaj.io.ReadableASCII#asciiHeader()
333         */
334        @Override
335        public String asciiHeader() {
336                return "SpIntA";
337        }
338
339        /* (non-Javadoc)
340         * @see org.openimaj.io.WriteableBinary#writeBinary(java.io.DataOutput)
341         */
342        @Override
343        public void writeBinary(DataOutput out) throws IOException {
344                out.writeInt(this.length);
345                out.writeInt(this.used());
346                for (Entry e : entries()) {
347                        out.writeInt(e.index);
348                        out.writeInt(e.value);                  
349                }
350        }
351
352        /* (non-Javadoc)
353         * @see org.openimaj.io.ReadableBinary#readBinary(java.io.DataInput)
354         */
355        @Override
356        public void readBinary(DataInput in) throws IOException {
357                this.length = in.readInt();
358                int used = in.readInt();
359                for (int i=0; i<used; i++) {
360                        set(in.readInt(), in.readInt());
361                }
362        }
363
364        /* (non-Javadoc)
365         * @see org.openimaj.io.ReadableBinary#binaryHeader()
366         */
367        @Override
368        public byte[] binaryHeader() {
369                return "SpIntA".getBytes();
370        }
371        
372        /**
373         * Deep copy the array.
374         * @return a deep copy of the array
375         */
376        public abstract SparseIntArray copy();
377
378        /**
379         * Add the values in the given vector to a copy of
380         * this array and return the result
381         * @param vector the vector to add
382         * @return the resultant vector
383         */
384        public SparseIntArray add(SparseIntArray vector) {
385                return copy().addInplace(vector);
386        }
387
388        /**
389         * Add the values in the given vector to
390         * this vector and return this
391         * @param vector the vector to add
392         * @return this
393         */
394        public SparseIntArray addInplace(SparseIntArray vector) {
395                for (Entry e : vector.entries()) {
396                        increment(e.index, e.value);
397                }
398
399                return this;
400        }
401
402        /**
403         * Subtract the values in the given vector from a copy of
404         * this vector and return the result
405         * @param vector the array to add
406         * @return the resultant vector
407         */
408        public SparseIntArray subtract(SparseIntArray vector) {
409                return copy().subtractInplace(vector);
410        }
411
412        /**
413         * Subtract the values in the given vector from
414         * this array and return this
415         * @param vector the vector to add
416         * @return this
417         */
418        public SparseIntArray subtractInplace(SparseIntArray vector) {
419                for (Entry e : vector.entries()) {
420                        increment(e.index, (int)(-e.value));
421                }
422
423                return this;
424        }
425
426        /**
427         * Copy this vector and multiply its values by a 
428         * scalar
429         * @param value scalar multiplier
430         * @return the multiplied vector 
431         */
432        public SparseIntArray multiply(double value) {
433                return copy().multiplyInplace(value);
434        }
435
436        /**
437         * Multiply the values inplace by a scalar and return this
438         * @param value scalar multiplier
439         * @return this
440         */
441        public SparseIntArray multiplyInplace(double value) {
442                for (Entry e : entries()) {
443                        if (this.isUsed(e.index))
444                                set(e.index, (int)(value * e.value));
445                }
446
447                return this;
448        }
449
450        /**
451         * Compute the dot product with another vector
452         * @param vector the other vector
453         * @return the dot product
454         */
455        public double dotProduct(SparseIntArray vector) {
456                double sum = 0;
457
458                int tused = this.used();
459                int vused = vector.used();
460
461                SparseIntArray smaller = (tused < vused ? this : vector);
462                SparseIntArray larger = (tused < vused ? vector : this);
463
464                for (Entry e : smaller.entries()) {
465                        sum += e.value * larger.get(e.index);
466                }
467
468                return sum;
469        }
470        
471        /**
472         * @return the largest value in the array
473         */
474        public int maxValue() {
475                int max = -Integer.MAX_VALUE;
476
477                for (Entry e : entries()) {
478                        if (e.value > max) max = e.value;
479                }
480
481                return max;
482        }
483
484        /**
485         * @return the smallest value in the array
486         */
487        public int minValue() {
488                int min = Integer.MAX_VALUE;
489
490                for (Entry e : entries()) {
491                        if (e.value < min) min = e.value;
492                }
493
494                return min;
495        }
496
497        /**
498         * @return the index of the largest value in the array
499         */
500        public int maxIndex() {
501                int max = -Integer.MAX_VALUE;
502                int index = 0;
503
504                for (Entry e : entries()) {
505                        if (e.value > max) { 
506                                max = e.value;
507                                index = e.index;
508                        }
509                }
510
511                return index;
512        }
513
514        /**
515         * @return the index of the smallest value in the array
516         */
517        public int minIndex() {
518                int min = Integer.MAX_VALUE;
519                int index = 0;
520
521                for (Entry e : entries()) {
522                        if (e.value < min) {
523                                min = e.value;
524                                index = e.index;
525                        }
526                }
527
528                return index;
529        }
530
531        /**
532         * Reverse the elements, returning this.
533         * 
534         * @return this array
535         */
536        public abstract SparseIntArray reverse();
537
538        /**
539         * Concatenate multiple arrays into a single new array.
540         * 
541         * @param arrays the arrays to concatenate.
542         * @return the new concatenated array
543         */
544        public static SparseIntArray concatenateArrays(SparseIntArray... arrays) {
545                SparseIntArray concat = arrays[0].copy();
546
547                for (int i=1; i<arrays.length; i++) {
548                        if (arrays[i] != null) {
549                                int oldLength = concat.length;
550                                concat.setLength(oldLength + arrays[i].length);
551
552                                for (Entry e : arrays[i].entries())
553                                        concat.set(e.index + oldLength, e.value);
554                        }
555                }
556
557        return concat;
558        }
559
560        /**
561         * Compute the sum of values
562         * @return the sum of all values
563         */
564        public int sumValues() {
565                int sum = 0;
566
567                for (Entry e : entries()) sum += e.value;
568
569                return sum;
570        }
571
572        /**
573         * Compute the sum of values squared
574         * @return the sum of all values
575         */
576        public int sumValuesSquared() {
577                int sum = 0;
578
579                for (Entry e : entries()) sum += e.value * e.value;
580
581                return sum;
582        }
583        
584        /**
585         * Convert this sparse array to a dense array.
586         * <p>
587         * Be aware that calling this method results in an array of {@link #length}
588         * being created. This could be very bad for performance.
589         * 
590         * @return the dense array representation of this feature.
591         */
592        public int[] toArray() {
593                final int[] array = new int[length];
594
595                for (final Entry e : entries()) {
596                        array[e.index] = e.value;
597                }
598
599                return array;
600        }
601
602        /**
603         * Convert this sparse array to a dense array. If the input array is longer
604         * than {@link #length}, then it will be cleared and populated with the data
605         * held in this sparse array. If the input array is <code>null</code> or is
606         * smaller than {@link #length}, then a new array will be allocated, filled
607         * and returned.
608         * <p>
609         * Be aware that calling this method may result in an array of
610         * {@link #length} being created. This could be very bad for performance.
611         * 
612         * @param array
613         *            The array to fill or null.
614         * 
615         * @return the dense array representation of this feature.
616         */
617        public int[] toArray(int[] array) {
618                if (array == null || array.length < length)
619                        array = new int[length];
620                else
621                        Arrays.fill(array, (int) 0);
622
623                for (final Entry e : entries()) {
624                        array[e.index] = e.value;
625                }
626
627                return array;
628        }
629        
630        @Override
631        public SparseIntArray concatenate(SparseIntArray... ins) {
632                final SparseIntArray result = copy();
633                
634                for (int i=0; i<ins.length; i++) {
635                        final int oldLength = result.length;
636                        result.setLength(oldLength + ins[i].length);
637                        
638                        for (Entry e : ins[i].entries()) {
639                                result.set(e.index + oldLength, e.value);
640                        }
641                }
642                
643                return result;
644        }
645        
646        @Override
647        public SparseIntArray concatenate(List<SparseIntArray> ins) {
648                final SparseIntArray result = copy();
649                
650                for (int i=0; i<ins.size(); i++) {
651                        final int oldLength = result.length;
652                        result.setLength(oldLength + ins.get(i).length);
653                        
654                        for (Entry e : ins.get(i).entries()) {
655                                result.set(e.index + oldLength, e.value);
656                        }
657                }
658                
659                return result;
660        }
661}