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);
		//TODO: test
		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){
		
		// TODO: Random Unsort
		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);
		
		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 
//	 */
//	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;
//	}
}
