youngtableau.java

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

/*
 * 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.
 */
package cn.edu.whu.iss.algorithm.unit06;

import mypackage.tools.print.P;
public class YoungTableau {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] k = { 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5,1,2,3,6,5,4,3,7,8,9,111,43,2,5,6 };
		k = YoungTableau.youngSort(k);
		for (int i = 0; i < k.length; i++) {
			P.rint(k[i] + " ");
		}P.rintln();
		int[] a = { 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5,1,2,3,6,5,4,3,7,8,9,111,43,2,5,6 };
		YoungTableau y = new YoungTableau(a);
		P.rintln(y);
		
		P.rintln(y.searchYoung(1));
		P.rintln(y.searchYoung(2));
		P.rintln(y.searchYoung(1123));
		P.rintln(y.searchYoung(3));
		P.rintln(y.searchYoung(11));
		P.rintln(y.searchYoung(12));
		P.rintln(y.searchYoung(13));
		P.rintln(y.searchYoung(10));
		P.rintln(y.searchYoung(111111));
		P.rintln(y.searchYoung(1010101));
	}

	/**
	 * Sort a array by young tableau data structure
	 * @param k the array
	 * @return array of being sorted
	 */
	public static int[] youngSort(int[] k) {
		int s = (int)Math.sqrt(k.length);
		if(s*s<k.length)s++;
		YoungTableau y = new YoungTableau(s,s);

		for (int i = 0; i < k.length; i++) {
			y.minYoungInsert(k[i]);
		}

		for (int i = 0; i < k.length; i++) {
			k[i] = y.extractMinYoung();
		}

		return k;
	}
	
	private int m;

	private int n;

	private int e;

	private int[][] y;
	
	public YoungTableau(int n, int m) {
		this.n = n - 1;
		this.m = m - 1;
		e=0;
		y = new int[n][m];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				y[i][j] = Integer.MAX_VALUE;
	}

	public YoungTableau(int[] tmpy){
		int s = (int)Math.sqrt(tmpy.length);
		if(s*s!=e)s++;
		y=new int[s][s];
		m=s-1;
		n=s-1;
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= m; j++)
				y[i][j] = Integer.MAX_VALUE;
		e=0;
		for(int i=0;i<tmpy.length;i++){
			minYoungInsert(tmpy[i]);
		}
	}

	public YoungTableau(int[][] tmpy) {
		n = tmpy.length - 1;
		m = tmpy[0].length - 1;
		e=m*n;
		y = tmpy.clone();
	}

	/**
	 * Get the min element in the tableau.And delete it.
	 * 
	 * @return min element
	 */

	public int extractMinYoung() {
		int min = y[0][0];
		e--;
		minYoungReset(0, 0);
		return min;
	}

	/**
	 * Insert a key to the tableau.
	 * @param key number
	 * @return true Insert successfully
	 */
	public boolean minYoungInsert(int key) {
		if (y[n][m] < Integer.MAX_VALUE){
			return false;
		}
		e++;
		return minYoungInsert(key, 0, 0);
	}
	
	/**
	 * Insert a number to the tableau.
	 * 
	 * @param key
	 *            inserting number
	 * @param l
	 *            the place
	 * @param r
	 *            the place
	 * @return true Insert successfully
	 */
	private boolean minYoungInsert(int key, int l, int r) {
		if (key >= Integer.MAX_VALUE) {
			return true;
		}
		int e=scale()-2;
		
		if (key < y[r][l]) {
			int temp = y[r][l];
			y[r][l] = key;
			if (temp < Integer.MAX_VALUE) {
				if(r<e){
					l=0;
					return minYoungInsert(temp,l,r+1);
				}else{
					return minYoungInsert(temp,l+1,r);
				}
			} else {
				return true;
			}
		} else {
			if (l<e) {
				return minYoungInsert(key, l + 1, r);
			} else {
				l=0;
				return minYoungInsert(key, l, r + 1);
			}
		}
	}

	/**
	 * Replace the y[r+1][l+1] and reset the tableau.
	 * 
	 * @param r
	 *            the row of the tableau.
	 * @param l
	 *            the column of the tableau.
	 * @return true Reset completely.
	 */
	public boolean minYoungReset(int r, int l) {
		try {
			if (l == m) {
				for (int i = r; i < n; i++) {
					y[i][l] = y[i + 1][l];
				}
				y[n][l] = Integer.MAX_VALUE;
				return true;
			} else if (r == n) {
				for (int i = l; i < m; i++) {
					y[r][i] = y[r][i + 1];
				}
				y[r][m] = Integer.MAX_VALUE;
				return true;
			} else if (y[r + 1][l] < y[r][l + 1]) {
				y[r][l] = y[r + 1][l];
				return minYoungReset(r + 1, l);
			} else {
				y[r][l] = y[r][l + 1];
				return minYoungReset(r, l + 1);
			}
		} catch (Exception e) {
			e.printStackTrace();
			return false;
		}
	}
	/**
	 * Get the scale of the tableau
	 * @return scale.
	 */
	private int scale(){
		int s = (int)Math.sqrt(e);
		if(s*s==e)return s;
		else return s+1;
	}

	public boolean searchYoung(int key){
		return searchYoung(key,0,0);
	}

	private boolean searchYoung(int key,int l,int r){
		if(l>m||r>n)return false;
		if (key == y[r][l]) {
			return true;
		}
		int e=scale()-2;
		
		if (key < y[r][l]) {
				if(r<e){
					l=0;
					return searchYoung(key,l,r+1);
				}else{
					return searchYoung(key,l+1,r);
				}

		} else {
			if (l<e) {
				return searchYoung(key, l + 1, r);
			} else {
				l=0;
				return searchYoung(key, l, r + 1);
			}
		}
	}

	public String toString() {
		String s = "";
		for (int i = 0; i <= n; i++) {
			s += "[";
			for (int j = 0; j < m; j++) {
				s += y[i][j] + ",";
			}
			s += y[i][m] + "]";
			s += "\n";
		}
		return s;
	}

}