quantiledata.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 150 行

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//16 Nov 2007
package cn.edu.whu.iss.algorithm.unit09;

import java.util.Arrays;

/**
 * Use for getting k quantiles numbers.
 * It contains the KQuantiles' location and the Result
 * @author wpc
 *
 */
public class QuantileData{
	//Location
	private int[] KQuantile ;
	//The result
	private int[] KResult;
	//The elements' length
	private int eLength;
	//The K quantile
	private int k;
	//The block
	private int m;
	//The stack point of the result
	private int p;
	
	/**
	 * Constructor
	 * @param elementLength The elements' length
	 * @param kQuantile the K quantile
	 */
	public QuantileData(int elementLength,int kQuantile){
		this.eLength = elementLength;
		this.k = kQuantile;
		
		init();
	}
	
	/**
	 * Initialize the data
	 */
	private void init(){
		KQuantile = new int[k-1];
		KResult = new int[k-1];
		p=0;
		m = (int)Math.round((float)eLength/ (float)k );
		
		KQuantile[0] = m-1;
		Arrays.fill(KResult, 0);
		for(int i=1;i<k-1;i++){
			KQuantile[i] = KQuantile[i-1]+m;
		}
	}
	
	/**
	 * Check the location whether is in the quantiles
	 * @param i location
	 * @return true in
	 */
	public boolean contains(int i){
		/**
		 * It use the binary search
		 */
 		int l	=	0;
 		int r	=	k-2;
 		int mid	=	0;
 		while(l<=r){
 			mid	=	(l+r)>>1;//(l+r)/2
 			if(i<KQuantile[mid]){
 				r	=	mid-1;
 			}else if(i>KQuantile[mid]){
 				l	=	mid+1;
 			}else{
 				return true;
 			}
 		}
 		return false;
	}
	
	/**
	 * Add a location to the result
	 * @param i location
	 */
	public void add(int i){
		if(!isFull()){
			KResult[p] = i;
			p++;
		}
	}
	
	/**
	 * Whether the result is full
	 * @return true result is full
 	 */
	public boolean isFull(){
		if(p==KResult.length){
			return true;
		}else{
			return false;
		}
	}
	
	/**
	 * Whether the block has results
	 * @param p the begin of the block
	 * @param r the end of the block
	 * @return
	 */
	public boolean checkHave(int p,int r){
		p++;r++;
		if( (p/m)<(r/m) ){
			return true;
		}else{
			if( (r%m==0)||(p%m==0) ){
				return true;
			}
			if( (r-p)/m>0){
				return true;
			}else{
				return false;
			}
		}
	}
	
	/**
	 * Get the list of the results
	 * @return
	 */
	public int[] getKResult() {
		return KResult;
	}

}