/**
 *  "插入排序 "，对少量元素进行排序的有效算法。
 *  《算法导论》原文摘要：
 * Insertion sort works the way many people sort a hand
 * of playing cards. We start with an empty left hand and the cards face down on
 * the table. We then remove one card at a time from the table and insert it
 * into the correct position in the left hand. To find the correct position for
 * a card, we compare it with each of the cards already in the hand, from right
 * to left, as illustrated in Figure 2.1. At all times, the cards held in the
 * left hand are sorted, and these cards were originally the top cards of the
 * pile on the table. 
 * 伪代码如下： 
 * for j<- 2 to length[A] 
 * 	do key <- A[j] 
 * 		>Insert A[j] into the sorted sequence A[1..j-1] （>符号代表后面的部分是注释）
 * 		i <- j-1 
 * 		while i>0 and A[i]>key 
 * 			do A[i+1] <- A[i] 
 * 			i <- i-1 
 * 		A[i+1] <- key 
 * 算法复杂度：n^2
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class InsertionSort {

	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };

	public static void main(String[] args) {
		//从数组第二个元素开始排序，因为第一个元素本身肯定是已经排好序的
		for (int j = 1; j < input.length; j++) {// 复杂度 n
			int key = input[j];
			int i = j - 1;
			//依次跟之前的元素进行比较，如果发现比前面的原素小，则交换位置，最终完成排序。
			while (i >= 0 && input[i] > key) {//复杂度：1+2+...+(n-1)=&Theta;(n^2)
				input[i + 1] = input[i];
				input[i] = key;
				i--;
			}
		}
		/*
		 * 所以最终复杂度为n*n=n^2。最优情况下（即都已经排列好的情况下），第二个n=1， 所以在最优情况下，复杂度为n。
		 */
		// 打印数组
		printArray();
	}

	private static void printArray() {
		for (int i : input) {
			System.out.print(i + " ");
		}
	}
}

/**
 * 《算法导论》习题6.5-8: Give an θ(nlgk)-time algorithm to merge k sorted lists into
 * one sorted list, where n is the total number of elements in all the input
 * lists. (Hint: Use a min-heap for k-way merging.) 
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class Exercice658 {

	// 给定3（k=3）个已排好序的数组，这里考虑简单情况，
	// 即所有数组包含的元素个数一致。
	// 注：因为已实现MaxHeapify算法，所以此处用最大到小排好序的数组举例
	private static int[] arrayOne = new int[] { 7, 4, 3, 1 };
	private static int[] arrayTwo = new int[] { 10, 9, 5, 2 };
	private static int[] arrayThree = new int[] { 12, 11, 8, 6 };
	
	// 已排好序中的数组中，元素的个数
	private static int length = arrayOne.length;
	// 已排好序的数组的个数
	private static int k = 3;
	// 所有数组中元素的总个数
	private static int n = length * k;
	// 合并后输出数组
	private static int[] output = new int[n];
	
	public static void main(String[] args) {
		mergeSortedArrays();
		// 打印数组
		printArray();
	}

	/**
	 * 合并已排序的数组，利用<code>;PriorityQueue</code>;中 的insert和extractMax算法实现
	 * 复杂度分析：
	 * 根据当前实现，复杂度应该为：θ(nk)，并不满足题意。
	 * 但是所用思路，与习题参考中的思路一致，参考原文如下：
	 * Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insert
	 * all k elements a position 1 from each list into a heap. Use EXTRACT-MAX to obtain the rst element
	 * of the merged list. Insert element at position 2 from the list where the largest element originally
	 * came from into the heap. Continuing in this fashion yields the desired algorithm. Clearly the
	 * running time is θ(n lg k).
	 * 差异之处在于，当从堆中取出一个元素之后，需要知道这个元素原来所属数组，这里也需要去判断，这里耗时K。另外，在插入的时候，
	 * 也需要判断
	 */
	private static void mergeSortedArrays() {
		
		// 利用前面实现的优先级队列中的方法，构造一个容量为k=3的堆
		PriorityQueue priQueue = new PriorityQueue(k);
		int count = 0;
		//用于保存各数组当前插入元素索引位的数组
		int[] indexArray = new int[k];
		int arrayChoice = 0;
		//初始情况，向堆中插入各数组首位元素
		//复杂度：θ(klgk)
		priQueue.insert(arrayOne[0]);
		priQueue.insert(arrayTwo[0]);
		priQueue.insert(arrayThree[0]);
		for (int i = 0; i < n; i++) {// 该循环复杂度：θ(n)
			// 取出当前最大值，复杂度θ(lgk)
			int value = priQueue.extractMax();
			count++;
			// 赋值
			output[n-count] = value;
			// 判断当前取出的最大元素所在数组，硬编码：(疑惑：复杂度θ(k),因为最差会进行k次比较，此处如何优化)
			if (value == arrayOne[indexArray[0]]) {
				arrayChoice = 0;
			} else if (value == arrayTwo[indexArray[1]]) {
				arrayChoice = 1;
			} else {
				arrayChoice = 2;
			}
			// 相应的索引位+1
			indexArray[arrayChoice]++;
			// 向堆中插入元素,如果备选数组中还有元素，则继续从该数组选取(疑惑：采用switch语句，复杂度是否降到θ(lgk)以下)
			// 根据:http://hi.baidu.com/software_one/blog/item/254990dfd96aee205982ddcb.html 中介绍，似乎可以。
			// 望高手指导！
			switch (arrayChoice) {
			case 0 :
				if (indexArray[0] < length) {
					priQueue.insert(arrayOne[indexArray[0]]);
				}
				break;
			case 1 :
				if (indexArray[1] < length) {
					priQueue.insert(arrayTwo[indexArray[1]]);
				}
				break;
			case 2 :
				if (indexArray[2] < length) {
					priQueue.insert(arrayThree[indexArray[2]]);
				} 
				break;
			}
		}
	}

	private static void printArray() {
		for (int i : output) {
			System.out.print(i + " ");
		}
	}
}

/**
 * 快速排序，《算法导论》第七章
 * @author lihzh(OneCoder)
 * @OneCoder-Blog http://www.coderli.com
 */
public class QuickSort {
	
	//待排数组
	private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 };

	public static void main(String[] args) {
		//快速排序
		quickSort(input, 0, input.length - 1);
		//打印数组
		printArray();
	}
	
	/**
	 * 快速排序，伪代码：
	 * QUICKSORT(A, p, r)
	 * 1 if p < r
	 * 2 	then q → PARTITION(A, p, r)
	 * 3 		QUICKSORT(A, p, q - 1)
	 * 4 		QUICKSORT(A, q + 1, r)
	 * 
	 * PARTITION(A, p, r)
	 * 1 x → A[r]
	 * 2 i → p - 1
	 * 3 for j → p to r - 1
	 * 4 	do if A[j] <= x
	 * 5 		then i → i + 1
	 * 6 			exchange A[i] ⟷ A[j]
	 * 7 exchange A[i + 1] ⟷ A[r]
	 * 8 return i + 1
	 * 复杂度，最坏情况下：θ(n^2)
	 * 一般平衡情况：θ(nlgn)
	 * @param array 待排数组
	 * @param from 起始位置
	 * @param to 终止位置
	 */
	private static void quickSort(int[] array, int from, int to) {
		if (from < to) {
			int temp = array[to];
			int i = from - 1;
			for (int j = from; j < to; j++) {
				if (array[j] <= temp) {
					i++;
					int tempValue = array[j];
					array[j] = array[i];
					array[i] = tempValue;
				}
			}
			array[to] = array[i+1];
			array[i+1] = temp;
			quickSort(array, from, i);
			quickSort(array, i + 1, to);
		}
	}

	private static void printArray() {
		for (int i : input) {
			System.out.print(i + &quot; &quot;);
		}
	}
}

/**
 * @author lihzh
 * @date 2012-4-21 下午10:18:46
 */
public class ForReadClass {

	final int init = 110;
	private final Integer intField = 120;
	public final String stringField = "Public Final Strng Value";
	public static String commStr = "Common String value";
	String str = "Just a string value";
	final double d = 1.1;
	final Double D = 1.2;
	
	public ForReadClass() {
	}
	
	public void methodA() {
		System.out.println(intField);
	}
}

   /**
	 * @param args
	 * @author lihzh
	 * @date 2012-4-21 下午10:17:22
	 */
	public static void main(String[] args) {
		try {
			ClassReader reader = new ClassReader("cn.home.practice.bean.ForReadClass");
			ClassNode cn = new ClassNode();
			reader.accept(cn, 0);
			System.out.println(cn.name);
			List<FieldNode> fieldList = cn.fields;
			for (FieldNode fieldNode : fieldList) {
				System.out.println("Field name: " + fieldNode.name);
				System.out.println("Field desc: " + fieldNode.desc);
				System.out.println("Filed value: " + fieldNode.value);
				System.out.println("Filed access: " + fieldNode.access);
        		}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

   /**
	 * @param args
	 * @author lihzh
	 * @date 2012-4-21 下午10:17:22
	 */
	public static void main(String[] args) {
		try {
			ClassReader reader = new ClassReader(
					"cn.home.practice.bean.ForReadClass");
			ClassNode cn = new ClassNode();
			reader.accept(cn, 0);
			List<MethodNode> methodList = cn.methods;
			for (MethodNode md : methodList) {
				System.out.println(md.name);
				System.out.println(md.access);
				System.out.println(md.desc);
				System.out.println(md.signature);
				List<LocalVariableNode> lvNodeList = md.localVariables;
				for (LocalVariableNode lvn : lvNodeList) {
					System.out.println("Local name: " + lvn.name);
					System.out.println("Local name: " + lvn.start.getLabel());
					System.out.println("Local name: " + lvn.desc);
					System.out.println("Local name: " + lvn.signature);
				}
				Iterator<AbstractInsnNode> instraIter = md.instructions.iterator();
				while (instraIter.hasNext()) {
					AbstractInsnNode abi = instraIter.next();
					if (abi instanceof LdcInsnNode) {
						LdcInsnNode ldcI = (LdcInsnNode) abi;
						System.out.println("LDC node value: " + ldcI.cst);
					}
				}
			}
			MethodVisitor mv = cn.visitMethod(Opcodes.AALOAD, "<init>", Type
					.getType(String.class).toString(), null, null);
			mv.visitFieldInsn(Opcodes.GETFIELD, Type.getInternalName(String.class), "str", Type
					.getType(String.class).toString());
			System.out.println(cn.name);
			List<FieldNode> fieldList = cn.fields;
			for (FieldNode fieldNode : fieldList) {
				System.out.println("Field name: " + fieldNode.name);
				System.out.println("Field desc: " + fieldNode.desc);
				System.out.println("Filed value: " + fieldNode.value);
				System.out.println("Filed access: " + fieldNode.access);
				if (fieldNode.visibleAnnotations != null) {
					for (AnnotationNode anNode : fieldNode.visibleAnnotations) {
						System.out.println(anNode.desc);
					}
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		} catch (SecurityException e) {
			e.printStackTrace();
		} catch (IllegalArgumentException e) {
			e.printStackTrace();
		}
	}

	/**
	 * 从绝对路径读取文件，最基本的文件读取方式
	 * 
	 * @author lihzh
	 * @data 2012-4-11 下午9:33:44
	 */
	@Test
	public void testGetFileFromAbsolutePath() {
		String dirPathNotUnderClasspath = "D:\\workspace-home\\JavaDemo\\conf";
		File dirFile = new File(dirPathNotUnderClasspath);
		AssertDirFile(dirFile);
	}

   /**
	 * 对文件夹类型文件的断言
	 * 
	 * @param dirFile
	 * @author lihzh
	 * @data 2012-4-11 下午9:49:14
	 */
	private void AssertDirFile(File dirFile) {
		// 文件存在
		Assert.assertTrue(dirFile.exists());
		// 是绝对路径
		Assert.assertTrue(dirFile.isAbsolute());
		// 是个文件夹
		Assert.assertTrue(dirFile.isDirectory());
		// 获取文件夹下所有文件
		File[] files = dirFile.listFiles();
		// 下面有文件
		Assert.assertNotNull(files);
		// 且只有一个
		Assert.assertEquals(1, files.length);
		// 文件名匹配
		Assert.assertEquals("test.properties", files[0].getName());
	}

	/**
	 * 从相对路径读取文件，相对于编译路径，在Eclipse中即为工程所在根目录。 本质还是绝对路径读取。
	 * 
	 * @author lihzh
	 * @data 2012-4-11 下午9:51:10
	 */
	@Test
	public void testGetFileFromRelativePath() {
		String dirPath = System.getProperty("user.dir") + "\\conf";
		File dirFile = new File(dirPath);
		AssertDirFile(dirFile);
	}

   /**
	 * 构造URI/URL格式的文件路径，读取本地文件
	 * 
	 * @author lihzh
	 * @throws URISyntaxException
	 * @throws MalformedURLException
	 * @data 2012-4-11 下午10:25:00
	 */
	@Test
	public void testGetFileFromURIPath() throws URISyntaxException,
			MalformedURLException {
		// 直接用URI构造, 由于URI和URL可以互转，所以如果为URL直接用URL.toURI转换成URI即可
		URI uri = new URI("file:/D:/workspace-home/JavaDemo/conf/");
		File dirFile = new File(uri);
		AssertDirFile(dirFile);
	}

   /**
	 * 从依赖的Jar包中读取文件, Jar包内的文件是无法用File读取的，只能用Stream的方式读取。
	 * 
	 * @author lihzh
	 * @throws URISyntaxException
	 * @throws IOException
	 * @data 2012-4-11 下午11:07:58
	 */
	@Test
	public void testGetFileFromJarInClassPath() throws URISyntaxException,
			IOException {
		Enumeration<URL> urls = this.getClass().getClassLoader().getResources("conf/test.properties");
		URL url = this.getClass().getClassLoader().getResource("conf/test.properties");
		Assert.assertTrue(urls.hasMoreElements());
		Assert.assertNotNull(url);
		// 注意两种不同调用方式的路径的区别，此处如果不以'/' 开头，会被当作相对于当前类所在的包类处理,自然无法找到。
		// 因为在Class的getResource方法的开头，有一个resolveName方法，处理了传入的路径格式问题。而ClassLoader类里的
		// getResource和getResources均无此处理。使用时候需要用心。
		URL clzURL = this.getClass().getResource("/conf/test.properties");
		URL nullURL = this.getClass().getResource("conf/test.properties");
		Assert.assertNotNull(clzURL);
		Assert.assertNull(nullURL);
		URL thisClzURL = this.getClass().getResource("");
		Assert.assertNotNull(thisClzURL);
		// 开始读取文件内容
		InputStream is = this.getClass().getResourceAsStream("/conf/test.properties");
		Properties props = new Properties();
		props.load(is);
		Assert.assertTrue(props.containsKey("test.key"));
		Assert.assertEquals("thisIsValue", props.getProperty("test.key"));
	}

	/**
	 * 从ClassPath中的Jar包读取某文件夹下的所有文件
	 * 
	 * @author lihzh
	 * @throws IOException 
	 * @data 2012-4-13 下午10:22:24
	 */
	@Test
	public void testGetFilesFromJarInClassPathWithDirPath() throws IOException {
		String dirPath = "conf/";
		URL url = this.getClass().getClassLoader().getResource(dirPath);
		Assert.assertNotNull(url);
		String urlStr = url.toString();
		// 找到!/ 截断之前的字符串
		String jarPath = urlStr.substring(0, urlStr.indexOf("!/") + 2);
		URL jarURL = new URL(jarPath);
		JarURLConnection jarCon = (JarURLConnection) jarURL.openConnection();
		JarFile jarFile = jarCon.getJarFile();
		Enumeration<JarEntry> jarEntrys = jarFile.entries();
		Assert.assertTrue(jarEntrys.hasMoreElements());
		Properties props = new Properties();
		while (jarEntrys.hasMoreElements()) {
			JarEntry entry = jarEntrys.nextElement();
			// 简单的判断路径，如果想做到像Spring，Ant-Style格式的路径匹配需要用到正则。
			String name = entry.getName();
			if (name.startsWith(dirPath) && !entry.isDirectory()) {
				// 开始读取文件内容
				InputStream is = this.getClass().getClassLoader().getResourceAsStream(name);
				Assert.assertNotNull(is);
				props.load(is);
			}
		}
		Assert.assertTrue(props.containsKey("test.key"));
		Assert.assertEquals("thisIsValue", props.getProperty("test.key"));
		Assert.assertTrue(props.containsKey("test.key.two"));
		Assert.assertEquals("thisIsAnotherValue", props.getProperty("test.key.two"));
	}