/*
        AUTOMATICALLY GENERATED BY jTemp FROM
        /Users/jsh2/Work/openimaj/target/checkout/core/core/src/main/jtemp/org/openimaj/util/array/SparseBinSearch#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 java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A Sparse array of int values implemented using a pair of 
 * sorted parallel arrays. The first array holds the indexes of
 * the non-zero elements in ascending order; the second holds
 * the corresponding values.
 * <p>
 * Element access has worst-case O(log n) performance. Appends (where
 * the index being added is greater than the existing indices) has O(1)
 * complexity. Random puts have worst case O(n + log n) complexity. 
 * Complexity for getting values by increasing index for iteration 
 * through the non-zero values is O(1).
 * <p>
 * In summary, this implementation has good access performance, and is
 * fast for appending values, but slow for putting at random indices. 
 * It is is optimal for a scenario where you first create the sparse 
 * array and put values in order of increasing indices, and later use 
 * the array mostly for reading.
 *  
 * @see "http://stackoverflow.com/questions/1880804/java-time-efficient-sparse-1d-array-double"
 * 
 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
 *
 */
public class SparseBinSearchIntArray extends SparseIntArray {
        protected int[] keys;
        protected int[] values;
        protected int used;
        
        /**
         * Construct from an existing array of values
         * @param values the values
         */
        public SparseBinSearchIntArray(int[] values) {
                this(values.length);
                
                for (int i=0; i<values.length; i++) {
                        if (values[i] != 0) set(i, values[i]);
                }
        }
        
        /**
         * Generate a new {@link SparseBinSearchIntArray} wrapper which works around
         * an existing array of keys and values
         * @param length
         * @param used
         * @param keys
         * @param values
         */
        public SparseBinSearchIntArray(int length, int used, int[] keys, int[] values){
                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
                if (length < values.length) throw new IllegalArgumentException("length is shorter than number of current values!");
                if (keys.length!=values.length) throw new IllegalArgumentException("Number of keys does not match number of values.");
                this.length = length;
                this.used = used;
                this.keys = keys;
                this.values = values;
        }

        /**
         * Construct the array with the given length
         * @param length the length
         */
        public SparseBinSearchIntArray(int length) {
                this(length, DEFAULT_CAPACITY);
        }

        /**
         * Construct the array with the given length and capacity for non-zero elements
         * @param length the length
         * @param capacity the capacity
         */
        public SparseBinSearchIntArray(int length, int capacity) {
                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
                if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
                
                this.length = length;
                this.keys = new int[capacity];
                this.values = new int[capacity];
        }
        
        /**
         * Construct the array with the given length and expected density
         * @param length the length
         * @param density the density
         */
        public SparseBinSearchIntArray(int length, float density) {
                if (length < 0) throw new IllegalArgumentException("length must be >= 0");
                if (density <= 0 || density > 1) throw new IllegalArgumentException("density must be > 0 and < 1");
                
                this.length = length;
                int capacity = (int) (density * length);
                this.keys = new int[capacity];
                this.values = new int[capacity];
        }
        
        @Override
        public int[] indices() {
                return Arrays.copyOf(keys, used);
        }

        @Override
        public int[] values() {
                return Arrays.copyOf(values, used);
        }

        @Override
        public Iterable<DualEntry> unionEntries(final SparseIntArray otherArray) {
                if (otherArray instanceof SparseBinSearchIntArray) {
                        return unionEntries((SparseBinSearchIntArray) otherArray);
                }
                
                return super.unionEntries(otherArray);
        }
        
        /**
         * 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 SparseIntArray.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 SparseIntArray.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 SparseBinSearchIntArray otherArray) {
                return new Iterable<DualEntry>() {
                        @Override
                        public Iterator<DualEntry> iterator() {
                                return new Iterator<DualEntry>() {
                                        private DualEntry entry = new DualEntry();
                                        private int innerIndex = 0;
                                        private int otherInnerIndex = 0;

                                        @Override
                                        public boolean hasNext() {
                                                return innerIndex < used || otherInnerIndex < otherArray.used;
                                        }

                                        @Override
                                        public DualEntry next() {
                                                if (!hasNext()) throw new NoSuchElementException();

                                                if (innerIndex < used && (otherInnerIndex >= otherArray.used || keys[innerIndex] < otherArray.keys[otherInnerIndex])) {
                                                        entry.index = keys[innerIndex];
                                                        entry.value = values[innerIndex];
                                                        entry.otherValue = 0;
                                                        innerIndex++;
                                                } else if (otherInnerIndex < otherArray.used && (innerIndex >= used || keys[innerIndex] > otherArray.keys[otherInnerIndex])) {
                                                        entry.index = otherArray.keys[otherInnerIndex];
                                                        entry.value = 0;
                                                        entry.otherValue = otherArray.values[otherInnerIndex];
                                                        otherInnerIndex++;
                                                } else {
                                                        entry.index = keys[innerIndex];
                                                        entry.value = values[innerIndex];
                                                        entry.otherValue = otherArray.values[otherInnerIndex];
                                                        innerIndex++;
                                                        otherInnerIndex++;
                                                }

                                                return entry;
                                        }

                                        @Override
                                        public void remove() {
                                                throw new UnsupportedOperationException();
                                        }
                                };
                        }
                };
        }

        @Override
        public Iterable<Entry> entries() {
                return new Iterable<Entry>() {
                        @Override
                        public Iterator<Entry> iterator() {
                                return new Iterator<Entry>() {
                                        private Entry entry = new Entry();
                                        private int innerIndex = 0;

                                        @Override
                                        public boolean hasNext() {
                                                return innerIndex < used;
                                        }

                                        @Override
                                        public Entry next() {
                                                if (!hasNext()) throw new NoSuchElementException();
                                                
                                                entry.index = keys[innerIndex];
                                                entry.value = values[innerIndex];
                                                innerIndex++;
                                                
                                                return entry;
                                        }

                                        @Override
                                        public void remove() {
                                                throw new UnsupportedOperationException();
                                        }
                                };
                        }
                };
        }

        @Override
        public boolean equals(Object obj) {
                if (!(obj instanceof SparseBinSearchIntArray)) return false;
                
                return length == ((SparseBinSearchIntArray)obj).length &&
                                used == ((SparseBinSearchIntArray)obj).used && 
                                Arrays.equals(keys, ((SparseBinSearchIntArray)obj).keys) &&
                                Arrays.equals(values, values);
        }

        @Override
        public int get(int key) {
                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key));
                int spot = Arrays.binarySearch(keys, 0, used, key);
                return spot < 0 ? 0 : values[spot];
        }

        @Override
        public int hashCode() {
                return length ^ Arrays.hashCode(keys) ^ Arrays.hashCode(values);
        }

        @Override
        public boolean isUsed(int key) {
                return 0 <= Arrays.binarySearch(keys, 0, used, key);
        }

        @Override
        public int set(int key, int value) {
                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key));
                int spot = Arrays.binarySearch(keys, 0, used, key);
                if (spot >= 0) return values[spot] = value;
                else return update(-1 - spot, key, value);
        }

        @Override
        public int increment(int key, int value) {
                if (key < 0 || key >= length) throw new IndexOutOfBoundsException(Integer.toString(key));
                int spot = Arrays.binarySearch(keys, 0, used, key);
                if (spot >= 0) return values[spot] += value;
                return update(-1 - spot, key, value);
        }
        
        private int update(int spot, int key, int value) {
                // grow if reaching end of capacity
                if (used == keys.length) {
                        int capacity = (keys.length * 3) / 2 + 1;
                        keys = Arrays.copyOf(keys, capacity);
                        values = Arrays.copyOf(values, capacity);
                }
                
                // shift values if not appending
                if (spot < used) {
                        System.arraycopy(keys, spot, keys, spot + 1, used - spot);
                        System.arraycopy(values, spot, values, spot + 1, used - spot);
                }
                
                used++;
                keys[spot] = key;
                return values[spot] = value;
        }

        @Override
        public int used() {
                return used;
        }

        @Override
        public void compact() {
                keys = Arrays.copyOf(keys, used);
                values = Arrays.copyOf(values, used);
        }
        
        /* (non-Javadoc)
         * @see org.openimaj.util.array.SparseDoubleArray#copy()
         */
        @Override
        public SparseIntArray copy() {
                SparseBinSearchIntArray copy = new SparseBinSearchIntArray(length);
                copy.used = used;
                copy.keys = Arrays.copyOf(keys, keys.length);
                copy.values = Arrays.copyOf(values, values.length);
                return copy;
        }

        /* (non-Javadoc)
         * @see org.openimaj.util.array.SparseDoubleArray#reverse()
         */
        @Override
        public SparseIntArray reverse() {
                final int len = used;
                final int hlen = len / 2;
                
                for(int i = 0; i < hlen; i++) {
                        int tmpVal = values[i];
                        values[i] = values[len - i - 1];
                        values[len - i - 1] = tmpVal;
                        
                        int tmpKey = keys[i];
                        keys[i] = length - keys[len - i - 1];
                        keys[len - i - 1] = length - tmpKey;
                }
                
                return this;
        }
}