/* Copyright (C) 2009  CSE,IIT Bombay  http://www.cse.iitb.ac.in

This file is part of the ConStore open source storage facility for concept-nets.

ConStore is free software and distributed under the 
Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License;
you can copy, distribute and transmit the work
with the work attribution in the manner specified by the author or licensor.
You may not use this work for commercial purposes and may not alter, 
transform, or build upon this work.

Please refer the legal code of the license, available at
http://creativecommons.org/licenses/by-nc-nd/3.0/legalcode

ConStore is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  */

package iitb.con.util;

import java.nio.ByteBuffer;
import java.util.Random;

/**
 * Sorted 2D Integer Array consists of two columns (key-value) 
 * and the values are maintained in sorted order according to the key.
 * It is an unbound array and handles duplicate values.
 * 
 * @author Prathab K
 *
 */
public class Sorted2DIntArray {
    
    /** Number of column */
    private static final int COL_NUM = 2;
    
    /**
     * The number of values currently present in the array.
     */
    protected int currentIndex;
    
    private static final int INT_SIZE = 4;

    /**
     * The underlying array used for storing the data.
     */
    protected int[][] a;

    /**
     * Constructor with full specification.
     * 
     * @param size number of int values initially allowed in array
     */
    
    public Sorted2DIntArray(int size) {
        a = new int[size][COL_NUM];
        for(int i = 0 ; i < size; i++)
            a[i][0] = Integer.MAX_VALUE;
        a[0][0] = -1; a[0][1] = -1;
        currentIndex = 1;
    }

    public Sorted2DIntArray(ByteBuffer buffer) {
        buffer.flip();
        int size = buffer.capacity() / (INT_SIZE * COL_NUM);
        if(size == 0) {
            a = new int[1][COL_NUM];
            a[0][0] = -1; a[0][1] = -1;
            currentIndex = 1;
        }
        else {
            a = new int[size][COL_NUM];
            for(int i = 0 ; i < size; i++)
                for(int j = 0 ; j < COL_NUM ;j++)
                    a[i][j] = buffer.getInt();
            currentIndex = size;
        }
        
    }

    /**
     * Increase the size of the array to at least a specified size. The array
     * will normally be at least doubled in size, but if a maximum size
     * increment was specified in the constructor and the value is less than
     * the current size of the array, the maximum increment will be used
     * instead. If the requested size requires more than the default growth, 
     * the requested size overrides the normal growth and determines the size
     * of the replacement array.
     * 
     * @param required new minimum size required
     */
    
    protected void growArray(int oldCapacity) {
        int size = Math.max((oldCapacity * 3)/2 + 1, 150);
        int[][] grown = new int[size][COL_NUM];
        for(int i = a.length ; i < size; i++)
            grown[i][0] = Integer.MAX_VALUE;
        System.arraycopy(a, 0, grown, 0, a.length);
        a = grown;
    }

    /**
     * Add a value to the array, appending it after the current values.
     * 
     * @param value1 value to be added
     * @param value2 value to be added
     * @return index number of added element
     */
    
    public final int add(int value1, int value2) {
        int index = -1;
        
        if(isValuePairExist(value1,value2))
            return -1;
        try {
            if(currentIndex == 0 || value1 > a[currentIndex - 1][0]) {
                 index = currentIndex++;
                if (currentIndex > a.length) {
                    growArray(currentIndex);
                }
                a[index][0] = value1;
                a[index][1] = value2;
            } else {
                index = Int2DBinarySearch.locate(a, value1, 0);
                if(index > 0)
                    index++;
                else
                    index = -index;
                add(index, value1, value2);
            }
        }catch(ArrayIndexOutOfBoundsException e) {
            e.printStackTrace();
        }
        return index;
    }
    

    /**
     * Add a value at a specified index in the array.
     * 
     * @param index index position at which to insert element
     * @param value value to be inserted into array
     */
    
    private void add(int index, int value1, int value2) {
        if (index >= 0 && index <= currentIndex) {
            if (++currentIndex > a.length) {
                growArray(currentIndex);
            }
            if (index < currentIndex) {
                System.arraycopy(a, index, a, index + 1,
                    currentIndex - index - 1);
            }
            int[][] n = new int[1][2];
            n[0][0] = value1;
            n[0][1] = value2;
            a[index] = n[0];
        } else {
            System.err.println("Index: " + index + ", Current Index " + currentIndex);
            throw new ArrayIndexOutOfBoundsException("Invalid index value");
        }
    }

    /**
     * Remove a value from the array. All values above the index removed
     * are moved down one index position.
     * 
     * @param value1 index of value1 to be removed
     */
    
    public void remove(int value1) {
        int index = Int2DBinarySearch.locate(a, value1, 0);
        if (index >= 0 && index < currentIndex) {
            if (index < --currentIndex){
                System.arraycopy(a, index + 1, a, index,
                    currentIndex - index);
                a[currentIndex][0] = 0;
                a[currentIndex][1] = 0;
            }
        } else {
            throw new ArrayIndexOutOfBoundsException("Invalid index value");
        }
    }

    /**
     * Ensure that the array has the capacity for at least the specified
     * number of values.
     * 
     * @param min minimum capacity to be guaranteed
     */
    
    public final void ensureCapacity(int min) {
        if (min > a.length) {
            growArray(min);
        }
    }

    /**
     * Set the array to the empty state.
     */
    
    public final void clear() {
        currentIndex = 0;
    }

    /**
     * Get the number of values currently present in the array.
     * 
     * @return count of values present
     */
    
    public final int size() {
        return currentIndex;
    }

    /**
     * Sets the number of values currently present in the array. If the new
     * size is greater than the current size, the added values are initialized
     * to 0.
     * 
     * @param count number of values to be set
     */
    
    public void setSize(int count) {
        if (count > a.length) {
            growArray(count);
        } else if (count < currentIndex) {
            for (int i = count; i < currentIndex; i++) {
                a[i][0] = 0;
                a[i][1] = 0;
            }
        }
        currentIndex = count;
    }

    /**
     * Retrieve the value present at an index position in the array.
     * 
     * @param value1 rows to be retrieved using value1
     * @return the rows based on the match of value1, 
     * returns <tt>NULL</tt> if there is no match
     */
    
    public final int[][] get(int value1) {
        int[][] r = null;
        int i = 0;
        int index = Int2DBinarySearch.locate(a, value1, 0);
        try {
            if (index > 0) {
                while(((index + i) < currentIndex) && a[index + i][0] == value1)
                    i++;
                int[][] r1 = new int[i][1];
                for(int j = 0; j < i ; j++)
                    r1[j] = a[index + j];
                
                i = 1;
                while(((index - i) > 0) && a[index - i][0] == value1)
                    i++;
                int[][] r2 = new int[i - 1][1];
                for(int j = 0; j < i - 1 ; j++)
                    r2[j] = a[index - j -1];
                
                return mergeArray(r1,r2);
            }
        }catch(ArrayIndexOutOfBoundsException e) {
            e.printStackTrace();
        }
        return r;
    }

    /**
     * Merges two given 2d arrays
     * @param r1 first array
     * @param r2 second array
     * @return merged array
     */
    private int[][] mergeArray(int[][] r1, int[][] r2) {
        int[][] r = new int[r1.length + r2.length][0];
        for(int i = 0; i < r1.length; i++)
            r[i] = r1[i];
        for(int j=0,i = r1.length; j < r2.length; j++,i++)
            r[i] = r2[j];
        return r;
    }
    
    /**
     * Checks if given value pair exists in the array
     * @param value1 first column value (key)
     * @param value2 second column value
     * @return <tt>true</tt> if exists, else <tt>false</tt>
     */
    public final boolean isValuePairExist(int value1, int value2) {
        int[][] r = get(value1);
        if(r == null)
            return false;
        else {
            for(int i = 0; i < r.length; i++)
                if(r[i][1] == value2)
                    return true;
        }
        return false; 
        
    }
    /**
     * Sets the values based on the index match of value1 in the array.
     * 
     * @param value1 value used to located the index in the array
     * @param value2 value to be set
     */
    
    public final void set(int value1, int value2) {
        int index = Int2DBinarySearch.locate(a, value1, 0);
        if (index < currentIndex) {
            a[index][0] = value1;
            a[index][1] = value2;
        } else {
            throw new ArrayIndexOutOfBoundsException("Invalid index value");
        }
    }

    
    //For Test
    public static void main(String[] args) {
        Sorted2DIntArray grid = new Sorted2DIntArray(10);
        Random r = new Random();
        
        /*for(int i = 0; i < 100; i++) {
            grid.add(Math.abs(r.nextInt()), r.nextInt());
        }*/
        
        grid.add(-1, -1);
        grid.add(13887, 52);
        grid.add(13887, 1040);
        grid.add(13887, 1011);
        grid.add(13887, 322);
        grid.add(13887, 738);
        grid.add(13887, 1011);
        grid.dump();
    }
    
    /**
     * Returns the array contents as bytes in the form of <tt>ByteBuffer</tt>
     * @return contents as {@link ByteBuffer}
     */
    public ByteBuffer toBuffer() {
        ByteBuffer buffer = ByteBuffer.allocate((currentIndex - 1) * INT_SIZE * COL_NUM);
        
        for(int i = 0; i < currentIndex - 1; i++)
            for(int j = 0 ; j < COL_NUM ;j++)
                buffer.putInt(a[i][j]);
        
        return buffer;
    }
    
    /**
     * Prints the contents of the array
     */
    public void dump() {
        for(int i = 0; i < a.length; i++) {
            System.out.print("[ ");
            for(int j = 0; j < a[i].length; j++)
                System.out.print( a[i][j] + ",");
            System.out.print(" ]\n");
        }
    }
}