/**
 * 
         -------- Copyright (C) [2012]  [Kristofer SCHWEIGER & Niklas FLORIAN1]---------

    This program is free software; you can redistribute it and/or modify it under the terms of the
 *  GNU General Public License as published by the Free Software Foundation; either version 2 of the License,
 *  or (at your option) any later version.
    This program 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.
 *  See the GNU General Public License for more details.
 * 
    You should have received a copy of the GNU General Public License along with this program; if not, 
 *  write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA

 * 
 * For any licening issues you can contact us under following adress: Mosaik.Projekt.2012@gmail.com
 */


package dataBase.search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

import mosaik.MosaikConstants;

import dataBase.DataBase;
import dataBase.search.distance.AbstractDistance;
import dataBase.subPicture.SubPicture;

public class SearchList {
	
	//public static final Random rand = new Random(System.nanoTime());
	public static int MinNumberOfPicturesToSearch = MosaikConstants.MinNumberOfPicturesToSearch;
	private ArrayList<SubPicture> list;
	private Comparator<SubPicture> hashComparator;
	public static AbstractDistance searchDistance = DataBase.searchDistance;
	
	/**
	 * Constructor:
	 * Copy list, sort copy, trim copy.
	 * @param db
	 * @param hashComparator
	 */
	public SearchList(DataBase db, Comparator<SubPicture> hashComparator){
		this.list = new ArrayList<SubPicture>(db.list);
		//randomDistribution(this.list);
		Collections.sort(this.list, hashComparator);
		this.list.trimToSize();
		this.hashComparator = hashComparator;
	}
	
//	/**
//	 * Randomize list before stable sorting for more disjunct results in each list.
//	 * @param list
//	 */
//	private void randomDistribution(ArrayList<SubPicture> list){
//		
//		int size = list.size();
//		int step = Math.max(2, size/5000);	// at most 5000 exchanges
//		
//		for(int i1=0; i1<list.size(); i1+=step){
//			
//			int i2 = rand.nextInt(size);
//			if(i2==i1)
//				i2++;
//			
//			SubPicture p1 = list.get(i1);
//			SubPicture p2 = list.get(i2);
//			
//			list.set(i1, p2);
//			list.set(i2, p1);
//		}
//	}
	
	
	public void getBest(SubPicture searchPic, Best1List<SubPicture> results, int threadID){
		//DataList<SubPicture> results = new DataList<SubPicture>(c, NumberOfResults);
		//int i = getStartIndex(searchPic);		// old
		int i = getStartIndexBin(searchPic);	// much faster!
		
		int num = MinNumberOfPicturesToSearch;
		int j        = Math.max(i-num, 0);
		int max      = Math.min(i+num, list.size());
		for(; j<max; j++){
			
			SubPicture pic = list.get(j);
			pic.setDistanceToSearchPic(searchDistance, searchPic, threadID);
			results.add(pic);
		}
		
		//return null;
	}
	
	
	
	/**
	 * Slow?
	 * @param search
	 * @return 0<=index<size, middle of equal hash values
	 */
	private int getStartIndex(SubPicture search){
		
		// --- compare until "0" or "-1" ---
		//
		int i=0;
		for(; i<list.size(); i++){
			SubPicture p2 = list.get(i);
			
			//Out.pl(" >>> Compare result at "+i+": " + hashComparator.compare(search, p2));
			if( hashComparator.compare(search, p2)<=0 ){
				//break;

				break;
			}
		}
		
		// --- compare until "-1" ---
		//
		int x=i;
		for(; x<list.size(); x++){
			SubPicture p2 = list.get(x);
			
			//Out.pl(" >>> Compare result at "+x+": " + hashComparator.compare(search, p2));
			if(hashComparator.compare(search, p2)!=0)
				break;
		}
		i = i + (x-1-i)/2;			// middle index of equal hash values
		
		//Out.pl(" >> Got start index "+i+" of "+list.size());
		return i;
	}
	
	/**
	 * @param search
	 * @return binary search result, even element index or insert point.
	 */
	private int getStartIndexBin(SubPicture search){
		
		int start = 0;
		int end   = list.size();
		int mid   = end/2;
		
		return getStartIndexBin2(search, start, mid, end);
		
	}
	
	/**
	 * Binary search.
	 */
	private int getStartIndexBin2(SubPicture key, int start, int mid, int end){
		
		if(start == mid)
			return mid;		// not found
		
		SubPicture midPic = list.get(mid);
		int c = hashComparator.compare(key, midPic);
		
		if(c < 0){
			return getStartIndexBin2(key, start, start+((mid-start)/2), mid);
		}
		else if(c > 0){
			return getStartIndexBin2(key, mid, mid+((end-mid)/2), end);
		}
		else {
			return mid;		// found
		}
	}
	
	
//	/**
//	 * @param search
//	 * @return binary search result 
//	 */
//	private int getStartIndexBin(SubPicture search){
//		
//		int i = Collections.binarySearch(list, search, hashComparator);
//		
//		if(i<0){
//			// from (-insertionPoint - 1) to insertionPoint
//			i = (i+1)*(-1);
//			
//			if(i==list.size())		// insertionPoint could be list size
//				i = list.size()-1;	//
//		}
//		
//		assert i>0 && i<list.size();		//TODO
//		return i;
//	}
}
