/* 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.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * KeyList is a generic key-value pair list. The values are inserted and removed based on the key.
 * It differs from the HashMap structure by maintaining it as a list and uses binary search to
 * add and retrieve the objects.
 * 
 * @author Prathab K
 *
 */
public class KeyList<K extends Comparable<K>,V> {
    
    /** List maintains the objects */
    private List<Entry<K,V>> list = new ArrayList<Entry<K,V>>();
    
    /**
     * Adds to the list
     * @param key key that used to add
     * @param value value object
     * @return <tt>true</tt> on success
     */
    public boolean add(K key, V value) {
        Entry<K,V> e = new Entry<K,V>(key,value);
        return list.add(e);
    }
    
    /**
     * Removes from the list
     * @param key key that used to remove the value object
     */
    public boolean remove(K key) {
        int index = Collections.binarySearch(list,new Entry<K,V>(key, null));
        index = - (index + 1);//next index
        
        if(index > 0) {
            if(list.remove(index) != null)
                return true;
            else
                return false;
        }else
            return false;
    }
    
    /**
     * Gets the value object for the specified key, if it matches.
     * If the key does not match, it returns <tt>NULL</tt>.
     * @param key key to retrieve the object
     * @return value object
     */
    public V get(K key) {
        if(list.size() > 0) {
            int index = Collections.binarySearch(list,new Entry<K,V>(key, null));
            if(index < 0) index = - (index + 1);//next index
            
            if(index >= 0 && index < list.size()) {
                Entry<K,V> e = list.get(index);
                return e.value;  
            }else
                return null;
        }else {
            return null;
        }
         
    }
    
    /**
     * Gets the next value object of the specified key for nearest match.
     * If there is not exact key match, the nearest match - the index returned
     * by the binary search on unsuccessful is used as the match.
     * If it matches with last key, then the last value object itself returned. 
     * @param key key to retrieve the object
     * @return value object
     */
    public V getNext(K key) {
        if(list.size() > 0) {
            int index = Collections.binarySearch(list,new Entry<K,V>(key, null));
            if(index < 0) index = - (index + 1);//next index
            
            if(index >= list.size()) {
                index = list.size() - 1;  
            }
             Entry<K,V> e = list.get(index);
             return e.value;
        }else {
            return null;
        }
    }
    
    /**
     * Gets the previous value object of the specified key for nearest match.
     * If there is not exact key match, the nearest match - the index returned
     * by the binary search on unsuccessful is used as the match.
     * If it matches with first key, then the first value object itself returned. 
     * 
     * @param key key to retrieve the object
     * @return value object
     */
    public V getPrev(K key) {
        if(list.size() > 0) {
            int index = Collections.binarySearch(list,new Entry<K,V>(key, null));
            if(index < 0) index = - (index + 2);//previous index
            if(index < 0) {
                index = 0; 
            }
             Entry<K,V> e = list.get(index);
             return e.value;
        }else{
            return null;
        }
    }
    
    /**
     * Sorts the key list
     */
    public void sort(){
        Collections.sort(list);
    }
    
    /**
     * Returns the list size
     * @return list size
     */
    public int size(){
        return list.size();
    }
    
    /**
     * Dumps the contents of the key-list
     */
    private void dump(){
        int i = 1;
        for(Entry<K,V> e : list) {
            System.out.println(i + "-" + e.key + "-" + e.value);
            i++;
        }
    }
    
    /**
     * Generic class for key-value pair data
     * 
     * @author Prathab K
     *
     * @param <K> Key
     * @param <V> Value
     */
    public static class Entry<K extends Comparable<K>, V> implements Comparable<Entry<K,V>>{

        K key;
        V value;
        
        public Entry(){
            
        }
        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
        
        public int compareTo(Entry<K,V> node) {
            return this.key.compareTo(node.key);
        }

    }
}