/*
        AUTOMATICALLY GENERATED BY jTemp FROM
        /Users/jsh2/Work/openimaj/target/checkout/core/core/src/main/jtemp/org/openimaj/util/array/Sparse#T#Array.jtemp
*/
/**
 * Copyright (c) 2011, The University of Southampton and the individual contributors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without modification,
 * are permitted provided that the following conditions are met:
 *
 *   *  Redistributions of source code must retain the above copyright notice,
 *      this list of conditions and the following disclaimer.
 *
 *   *  Redistributions in binary form must reproduce the above copyright notice,
 *      this list of conditions and the following disclaimer in the documentation
 *      and/or other materials provided with the distribution.
 *
 *   *  Neither the name of the University of Southampton nor the names of its
 *      contributors may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.openimaj.util.array;

import gnu.trove.iterator.TIntIterator;
import gnu.trove.set.hash.TIntHashSet;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

import org.openimaj.io.ReadWriteable;
import org.openimaj.util.concatenate.Concatenatable;

/**
 * A sparse array of short values. Includes some elementary
 * vector operations (add, subtract, scalar multiply, dot product).
 * 
 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
 *
 */
public abstract class SparseShortArray implements ReadWriteable, Concatenatable<SparseShortArray, SparseShortArray> {
        protected static final int DEFAULT_CAPACITY = 10;
        
        /**
         * An entry in a {@link SparseShortArray}, consisting of
         * an index and value.
         * 
         * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
         */
        public static class Entry {
                /**
                 * The index in the array of the value
                 */
                public int index;
                
                /**
                 * The value of the array at the index 
                 */
                public short value;
        }
        
        /**
         * An entry representing the values in two parallel {@link SparseShortArray}s
         * at the same index.
         * 
         * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
         */
        public static class DualEntry extends Entry {           
                /**
                 * The value of the other array at the index 
                 */
                public short otherValue;
        }
        
        /**
         * The length of the array 
         */
        public int length;
        
        /**
         * Increment the value at the given index.
         * 
         * @param index the index
         * @param value the amount to increment by.
         * @return the new value 
         */
        public abstract short increment(int index, short value);

        /**
         * @return the indices of the non-zero valued entries of the array.
         */
        public abstract int[] indices();
        
        /**
         * @return the packed non-zero valued entries of the array.
         */
        public abstract short[] values();

        /**
         * Provide an iterator over the non-zero values.
         * <p>
         * Note: the {@link Entry} returned by the iterator
         * is always the same object. In addition, the iterator
         * cannot affect the value of anything in the array (i.e.
         * changing anything in the {@link Entry} has no effect
         * on the actual array).
         * 
         * @return an iterator over the non-zero values.
         */
        public abstract Iterable<Entry> entries();
        
        /**
         * Provide an iterator over the union of values present in
         * both this array and another array. Values where
         * both arrays are zero are skipped.
         * <p>
         * Note: the {@link DualEntry} returned by the iterator
         * is always the same object. In addition, the iterator
         * cannot affect the value of anything in the array (i.e.
         * changing anything in the {@link DualEntry} has no effect
         * on the actual array).
         * 
         * @param otherArray the second array 
         * 
         * @return an iterator over the non-zero values.
         */
        public Iterable<DualEntry> unionEntries(final SparseShortArray otherArray) {
                //Naive implementation: creates the union of the indices and fetches from
                //them. Subclasses should override for efficiency.
                return new Iterable<DualEntry>() {
                        @Override
                        public Iterator<DualEntry> iterator() {
                                final TIntHashSet keys = new TIntHashSet(SparseShortArray.this.indices());
                                keys.addAll(otherArray.indices());
                                
                                return new Iterator<DualEntry>() {
                                        DualEntry entry = new DualEntry();
                                        TIntIterator iterator = keys.iterator();
                                        
                                        @Override
                                        public boolean hasNext() {
                                                return iterator.hasNext();
                                        }

                                        @Override
                                        public DualEntry next() {
                                                entry.index = iterator.next();
                                                entry.value = SparseShortArray.this.get(entry.index);
                                                entry.otherValue = otherArray.get(entry.index);
                                                return entry;
                                        }

                                        @Override
                                        public void remove() {
                                                throw new UnsupportedOperationException();
                                        }
                                };
                        }
                };
        }
        
        /**
         * Provide an iterator over the intersection of values present in
         * both this array and another array. Values are only
         * presented for the cases where both arrays are non-zero.
         * <p>
         * Note: the {@link DualEntry} returned by the iterator
         * is always the same object. In addition, the iterator
         * cannot affect the value of anything in the array (i.e.
         * changing anything in the {@link DualEntry} has no effect
         * on the actual array).
         * 
         * @param otherArray the second array
         * 
         * @return an iterator over the non-zero values.
         */
        public Iterable<DualEntry> intersectEntries(final SparseShortArray otherArray) {
                //Naive implementation: creates the intersection of the indices and fetches from
                //them. Subclasses should override for efficiency.
                return new Iterable<DualEntry>() {
                        @Override
                        public Iterator<DualEntry> iterator() {
                                final TIntHashSet keys;
                                
                                if (used() < otherArray.used()) {
                                        keys = new TIntHashSet(SparseShortArray.this.indices());
                                        keys.retainAll(otherArray.indices());
                                } else {
                                        keys = new TIntHashSet(otherArray.indices());
                                        keys.retainAll(SparseShortArray.this.indices());
                                }

                                return new Iterator<DualEntry>() {
                                        DualEntry entry = new DualEntry();
                                        TIntIterator iterator = keys.iterator();

                                        @Override
                                        public boolean hasNext() {
                                                return iterator.hasNext();
                                        }

                                        @Override
                                        public DualEntry next() {
                                                entry.index = iterator.next();
                                                entry.value = SparseShortArray.this.get(entry.index);
                                                entry.otherValue = otherArray.get(entry.index);
                                                return entry;
                                        }

                                        @Override
                                        public void remove() {
                                                throw new UnsupportedOperationException();
                                        }
                                };
                        }
                };
        }
        
        /**
         * Get the value at the given index.
         * @param index the index
         * @return the value at the index.
         */
        public abstract short get(int index);

        /**
         * Check whether the given index is used (i.e. has a non-zero value)
         * @param index the index
         * @return true if not used; false otherwise.
         */
        public abstract boolean isUsed(int index);

        /**
         * Set the value at the given index.
         * 
         * @param index the index.
         * @param value the value to set.
         * @return the value
         */
        public abstract short set(int index, short value);

        /**
         * Set the length of the array. Arrays can only be
         * extended with this method.
         * @param newLength the new array length
         * @throws IllegalArgumentException if the new length is shorter than 
         *              the existing length.
         */
        public void setLength(int newLength) {
                if (newLength < this.length) throw new IllegalArgumentException("can't make sparse array shorter");
                this.length = newLength;
        }

        /**
         * @return the length of the array
         */
        public int size() {
                return length;
        }
        
        /**
         * @return the length of the array
         */
        public int length() {
                return length;
        }

        /**
         * @return the number of non-zero entries in the array
         */
        public abstract int used();
        
        /**
         * @return the density of the array (number of used elements divided
         * by array length)
         */
        public float density() {
                return (float)used() / (float)length; 
        }
        
        /**
         * Compact the space being used by the array if possible.
         */
        public abstract void compact();
        
        /* (non-Javadoc)
         * @see org.openimaj.io.WriteableASCII#writeASCII(java.io.PrintWriter)
         */
        @Override
        public void writeASCII(PrintWriter out) throws IOException {
                out.print(this.length);
                out.print(" ");
                
                for (Entry e : entries()) {
                        out.print(e.index + ":" + e.value + " ");                       
                }
        }

        /* (non-Javadoc)
         * @see org.openimaj.io.ReadableASCII#readASCII(java.util.Scanner)
         */
        @Override
        public void readASCII(Scanner in) throws IOException {
                this.length = in.nextInt();
                
                String[] parts = in.nextLine().split(" ");
                for (String part : parts) {
                        String[] bits = part.split(":");
                        
                        set(Integer.parseInt(bits[0]), Short.parseShort(bits[1]));
                }
        }

        /* (non-Javadoc)
         * @see org.openimaj.io.ReadableASCII#asciiHeader()
         */
        @Override
        public String asciiHeader() {
                return "SpShortA";
        }

        /* (non-Javadoc)
         * @see org.openimaj.io.WriteableBinary#writeBinary(java.io.DataOutput)
         */
        @Override
        public void writeBinary(DataOutput out) throws IOException {
                out.writeInt(this.length);
                out.writeInt(this.used());
                for (Entry e : entries()) {
                        out.writeInt(e.index);
                        out.writeShort(e.value);                        
                }
        }

        /* (non-Javadoc)
         * @see org.openimaj.io.ReadableBinary#readBinary(java.io.DataInput)
         */
        @Override
        public void readBinary(DataInput in) throws IOException {
                this.length = in.readInt();
                int used = in.readInt();
                for (int i=0; i<used; i++) {
                        set(in.readInt(), in.readShort());
                }
        }

        /* (non-Javadoc)
         * @see org.openimaj.io.ReadableBinary#binaryHeader()
         */
        @Override
        public byte[] binaryHeader() {
                return "SpShortA".getBytes();
        }
        
        /**
         * Deep copy the array.
         * @return a deep copy of the array
         */
        public abstract SparseShortArray copy();

        /**
         * Add the values in the given vector to a copy of
         * this array and return the result
         * @param vector the vector to add
         * @return the resultant vector
         */
        public SparseShortArray add(SparseShortArray vector) {
                return copy().addInplace(vector);
        }

        /**
         * Add the values in the given vector to
         * this vector and return this
         * @param vector the vector to add
         * @return this
         */
        public SparseShortArray addInplace(SparseShortArray vector) {
                for (Entry e : vector.entries()) {
                        increment(e.index, e.value);
                }

                return this;
        }

        /**
         * Subtract the values in the given vector from a copy of
         * this vector and return the result
         * @param vector the array to add
         * @return the resultant vector
         */
        public SparseShortArray subtract(SparseShortArray vector) {
                return copy().subtractInplace(vector);
        }

        /**
         * Subtract the values in the given vector from
         * this array and return this
         * @param vector the vector to add
         * @return this
         */
        public SparseShortArray subtractInplace(SparseShortArray vector) {
                for (Entry e : vector.entries()) {
                        increment(e.index, (short)(-e.value));
                }

                return this;
        }

        /**
         * Copy this vector and multiply its values by a 
         * scalar
         * @param value scalar multiplier
         * @return the multiplied vector 
         */
        public SparseShortArray multiply(double value) {
                return copy().multiplyInplace(value);
        }

        /**
         * Multiply the values inplace by a scalar and return this
         * @param value scalar multiplier
         * @return this
         */
        public SparseShortArray multiplyInplace(double value) {
                for (Entry e : entries()) {
                        if (this.isUsed(e.index))
                                set(e.index, (short)(value * e.value));
                }

                return this;
        }

        /**
         * Compute the dot product with another vector
         * @param vector the other vector
         * @return the dot product
         */
        public double dotProduct(SparseShortArray vector) {
                double sum = 0;

                int tused = this.used();
                int vused = vector.used();

                SparseShortArray smaller = (tused < vused ? this : vector);
                SparseShortArray larger = (tused < vused ? vector : this);

                for (Entry e : smaller.entries()) {
                        sum += e.value * larger.get(e.index);
                }

                return sum;
        }
        
        /**
         * @return the largest value in the array
         */
        public short maxValue() {
                short max = -Short.MAX_VALUE;

                for (Entry e : entries()) {
                        if (e.value > max) max = e.value;
                }

                return max;
        }

        /**
         * @return the smallest value in the array
         */
        public short minValue() {
                short min = Short.MAX_VALUE;

                for (Entry e : entries()) {
                        if (e.value < min) min = e.value;
                }

                return min;
        }

        /**
         * @return the index of the largest value in the array
         */
        public int maxIndex() {
                short max = -Short.MAX_VALUE;
                int index = 0;

                for (Entry e : entries()) {
                        if (e.value > max) { 
                                max = e.value;
                                index = e.index;
                        }
                }

                return index;
        }

        /**
         * @return the index of the smallest value in the array
         */
        public int minIndex() {
                short min = Short.MAX_VALUE;
                int index = 0;

                for (Entry e : entries()) {
                        if (e.value < min) {
                                min = e.value;
                                index = e.index;
                        }
                }

                return index;
        }

        /**
         * Reverse the elements, returning this.
         * 
         * @return this array
         */
        public abstract SparseShortArray reverse();

        /**
         * Concatenate multiple arrays into a single new array.
         * 
         * @param arrays the arrays to concatenate.
         * @return the new concatenated array
         */
        public static SparseShortArray concatenateArrays(SparseShortArray... arrays) {
                SparseShortArray concat = arrays[0].copy();

                for (int i=1; i<arrays.length; i++) {
                        if (arrays[i] != null) {
                                int oldLength = concat.length;
                                concat.setLength(oldLength + arrays[i].length);

                                for (Entry e : arrays[i].entries())
                                        concat.set(e.index + oldLength, e.value);
                        }
                }

        return concat;
        }

        /**
         * Compute the sum of values
         * @return the sum of all values
         */
        public short sumValues() {
                short sum = 0;

                for (Entry e : entries()) sum += e.value;

                return sum;
        }

        /**
         * Compute the sum of values squared
         * @return the sum of all values
         */
        public short sumValuesSquared() {
                short sum = 0;

                for (Entry e : entries()) sum += e.value * e.value;

                return sum;
        }
        
        /**
         * Convert this sparse array to a dense array.
         * <p>
         * Be aware that calling this method results in an array of {@link #length}
         * being created. This could be very bad for performance.
         * 
         * @return the dense array representation of this feature.
         */
        public short[] toArray() {
                final short[] array = new short[length];

                for (final Entry e : entries()) {
                        array[e.index] = e.value;
                }

                return array;
        }

        /**
         * Convert this sparse array to a dense array. If the input array is longer
         * than {@link #length}, then it will be cleared and populated with the data
         * held in this sparse array. If the input array is <code>null</code> or is
         * smaller than {@link #length}, then a new array will be allocated, filled
         * and returned.
         * <p>
         * Be aware that calling this method may result in an array of
         * {@link #length} being created. This could be very bad for performance.
         * 
         * @param array
         *            The array to fill or null.
         * 
         * @return the dense array representation of this feature.
         */
        public short[] toArray(short[] array) {
                if (array == null || array.length < length)
                        array = new short[length];
                else
                        Arrays.fill(array, (short) 0);

                for (final Entry e : entries()) {
                        array[e.index] = e.value;
                }

                return array;
        }
        
        @Override
        public SparseShortArray concatenate(SparseShortArray... ins) {
                final SparseShortArray result = copy();
                
                for (int i=0; i<ins.length; i++) {
                        final int oldLength = result.length;
                        result.setLength(oldLength + ins[i].length);
                        
                        for (Entry e : ins[i].entries()) {
                                result.set(e.index + oldLength, e.value);
                        }
                }
                
                return result;
        }
        
        @Override
        public SparseShortArray concatenate(List<SparseShortArray> ins) {
                final SparseShortArray result = copy();
                
                for (int i=0; i<ins.size(); i++) {
                        final int oldLength = result.length;
                        result.setLength(oldLength + ins.get(i).length);
                        
                        for (Entry e : ins.get(i).entries()) {
                                result.set(e.index + oldLength, e.value);
                        }
                }
                
                return result;
        }
}