package sort;
import java.awt.*;
import java.awt.BorderLayout;
import java.awt.event.*;
import java.io.*;
import javax.swing.*;
import javax.swing.JProgressBar;

public class SortFrame extends JFrame {
	private JComboBox fileNumber;// 數(shù)據(jù)分組個(gè)數(shù)選擇欄，選擇數(shù)據(jù)分組個(gè)數(shù)

	private JComboBox Sort;// 排序選擇欄，選擇進(jìn)行排序的方法

	private JTextField fileaddress;// 用于輸入待排序文件的地址

	private JTextArea printResult;// 顯示結(jié)果的文本域
	final JProgressBar progressBar = new JProgressBar();

	// 窗口的構(gòu)造方法
	public SortFrame() {
		super();
		setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

		final JScrollPane scrollPane = new JScrollPane();
		getContentPane().add(scrollPane, BorderLayout.CENTER);

		printResult = new JTextArea();
		printResult.setText("");
		printResult.setEditable(false);
		scrollPane.setViewportView(printResult);

		final JPanel panel = new JPanel();
		panel.setLayout(new BorderLayout(5, 5));
		getContentPane().add(panel, BorderLayout.NORTH);

		final JPanel panel_1 = new JPanel();
		panel_1.setLayout(new GridLayout(2, 0, 5, 5));
		panel.add(panel_1);

		final JLabel label = new JLabel();
		label.setText("在此輸入需排序的文件所在的位置(包括文件名)");
		panel_1.add(label);

		fileaddress = new JTextField();
		fileaddress.setText("data_src.txt");
		panel_1.add(fileaddress);

		final JPanel panel_2 = new JPanel();
		panel_2.setLayout(new GridLayout(0, 2, 5, 5));
		panel.add(panel_2, BorderLayout.EAST);

		final String sortItem[] = { "請(qǐng)選擇排序類(lèi)型", "插入排序", "堆排序", "歸并排序", "快速排序" };
		Sort = new JComboBox(sortItem);
		panel_2.add(Sort);

		final String numberOfFile[] = { "選擇數(shù)據(jù)分組個(gè)數(shù)", "400", "200", "100", "50",
				"25" };
		fileNumber = new JComboBox(numberOfFile);
		panel_2.add(fileNumber);

		final JButton sort = new JButton();
		panel_2.add(sort);

		// 向排序按鈕添加監(jiān)聽(tīng)器，點(diǎn)擊之后，對(duì)fileaddress中顯示的文件進(jìn)行排序
		sort.addActionListener(new ActionListener() {
			public void actionPerformed(final ActionEvent e) {

				// 新建排序線程SortThread，以防用戶(hù)界面線程阻塞
				Thread SortThread = new Thread() {
					int number = Integer.parseInt(numberOfFile[fileNumber
							.getSelectedIndex()]);// 得到數(shù)據(jù)分組個(gè)數(shù)

					int whichSort = Sort.getSelectedIndex();// 得到排序方法的下標(biāo)

					File files[] = new File[number];// 創(chuàng)建分組文件類(lèi)數(shù)組

					final int ManyNumber = 1000000;// 設(shè)置整數(shù)的總數(shù)

					// run()方法，當(dāng)調(diào)用此線程的start()方法時(shí)執(zhí)行此方法
					public void run() {
						try {
							// 使點(diǎn)擊后的排序按鈕不可用，以防多次點(diǎn)擊造成錯(cuò)誤
							sort.setEnabled(false);
							sort.setText("LOADING....");

							long spendTime = System.currentTimeMillis();// 用于記錄總時(shí)間
							String sortFile = fileaddress.getText();// 獲取源文件的地址
							File toSort = new File(sortFile);
							IntegerReader inputSortFile = new IntegerReader(
									new BufferedReader(new FileReader(toSort)));// 創(chuàng)建整數(shù)讀取對(duì)象
							String path = toSort.getParent() + "\\";// 獲取源文件的父目錄

							// 初始化創(chuàng)建分組文件數(shù)組，文件名為data_src_i.txt，i從0到number-1，目錄與源文件的目錄相同
							for (int i = 0; i < number; i++)
								files[i] = new File(path + "data_src_" + i
										+ ".txt");

							// 判斷是否選擇了排序方法和數(shù)據(jù)分組個(gè)數(shù)，否則拋出NumberFormatException
							if (fileNumber.getSelectedIndex() == 0
									|| Sort.getSelectedIndex() == 0)
								throw new NumberFormatException();

							long Sorttime = 0;// 用于記錄排序的總時(shí)間
							double pro=0;
							// 分塊讀取整數(shù)到IntList a，再對(duì)a調(diào)用排序方法，排好序后寫(xiě)入到BufferedWriter
							// partSortFile中
							for (int i = 0; i < number; i++) {
								BufferedWriter partSortFile = new BufferedWriter(
										new FileWriter(files[i]));
								IntList a = new IntList();
								for (int j = 0; j < ManyNumber / number; j++) {
									a.appond(inputSortFile.readerInt());
								}
								switch (whichSort) {
								case 1:
									Sorttime += insertSort(a, partSortFile);
									break;
								case 2:
									Sorttime += heapSort(a, partSortFile);
									break;
								case 3:
									Sorttime += mergeSort(a, partSortFile);
									break;
								case 4:
									Sorttime += quickSort(a, partSortFile);
									break;
								}
								pro+=99/number;
								progressBar.setValue((int)pro);
								panel.add(progressBar, BorderLayout.SOUTH);
							}
							inputSortFile.close();

							/*
							 * 每次分別從每個(gè)分組文件中讀取一個(gè)整數(shù)到數(shù)組num中，將最小的放寫(xiě)道 BufferedWriter
							 * outputSortFile中，
							 * 并將擁有此次寫(xiě)入的最小整數(shù)的文件的下一個(gè)整數(shù)放到num的同一位置上 再重復(fù)直到所有整數(shù)都已讀入
							 */
							IntegerReader filesreader[] = new IntegerReader[number];// 分組文件整數(shù)讀取的數(shù)組
							int num[] = new int[number];// 用于保存每個(gè)分組文件的一個(gè)整數(shù)的數(shù)組

							// 將每個(gè)文件的第一個(gè)整數(shù)讀取到num中
							for (int i = 0; i < number; i++) {
								filesreader[i] = new IntegerReader(
										new BufferedReader(new FileReader(
												files[i])));
								num[i] = filesreader[i].readerInt();
							}

							BufferedWriter outputSortFile = new BufferedWriter(
									new FileWriter(path + "data_dst.txt"));// 目標(biāo)文件的寫(xiě)入器

							// 進(jìn)行比較并寫(xiě)入
							for (int i = 0; i < ManyNumber; i++) {
								int minindex = Min(num);// 求出num中最小數(shù)的下標(biāo)
								outputSortFile.write(num[minindex] + " ");
								num[minindex] = filesreader[minindex]
										.readerInt();

								// 如果num[minindex]==-1為true，則表示filesreader[minindex]中的所有整數(shù)都已讀取了，則關(guān)閉輸入流，否則無(wú)法刪除文件
								if (num[minindex] == -1)
									filesreader[minindex].close();
							}
							outputSortFile.close();

							// 刪除分組文件
							for (int i = 0; i < number; i++)
								files[i].delete();

							// 將按鈕復(fù)原
							sort.setText("排序");
							sort.setEnabled(true);

							spendTime = System.currentTimeMillis() - spendTime;// 計(jì)算時(shí)間差

							// 顯示結(jié)果
							String output = "排序成功啦！！\n" + "排序方法名稱(chēng)" + "\t數(shù)據(jù)分組個(gè)數(shù)"
									+ "\t總用時(shí)(毫秒)" + "\t排序用時(shí)(毫秒)" + "\n"
									+ sortItem[whichSort] + "\t" + number
									+ "\t" + spendTime + "\t" + Sorttime
									+ "\n\n";
							printResult.append(output);
						}

						catch (NumberFormatException ex) {
							JOptionPane.showMessageDialog(null, "請(qǐng)選擇方法和數(shù)據(jù)分組數(shù)",
									"錯(cuò)誤", JOptionPane.ERROR_MESSAGE);
						} catch (FileNotFoundException ex) {
							JOptionPane.showMessageDialog(null, "初始文件不存在",
									"錯(cuò)誤", JOptionPane.ERROR_MESSAGE);
						} catch (IOException ex) {
							JOptionPane.showMessageDialog(null, "文件輸出錯(cuò)誤", "錯(cuò)誤",
									JOptionPane.ERROR_MESSAGE);
						} catch (Exception ex) {
							JOptionPane.showMessageDialog(null, "排序錯(cuò)誤"
									+ ex.getMessage(), "錯(cuò)誤",
									JOptionPane.ERROR_MESSAGE);
						}

						// 不管怎樣，反正就是要把多余文件刪了
						finally {
							for (int i = 0; i < number; i++)
								files[i].delete();
						}
					}
				};
				// 調(diào)用start()執(zhí)行run()方法
				SortThread.start();
			}
		});
		sort.setText("排序");

		final JButton reset = new JButton();
		panel_2.add(reset);

		// 向清空按鈕添加監(jiān)聽(tīng)器，點(diǎn)擊之后，將printResult中的文本清空
		reset.addActionListener(new ActionListener() {
			public void actionPerformed(final ActionEvent e) {
				printResult.setText("");
			}
		});
		reset.setText("清空");

		
		progressBar.setStringPainted(true);
		progressBar.setInheritsPopupMenu(true);
		progressBar.setIndeterminate(false);
		panel.add(progressBar, BorderLayout.SOUTH);
	}

	// 插入排序方法，將IntList a中的數(shù)升序排序，排好之后寫(xiě)入到BufferedWriter partSortFile中，并返回單次排序的時(shí)間
	public long insertSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		int i, j, temp;
		int n;
		long time = System.currentTimeMillis();// 用于記錄排序的時(shí)間
		n = a.size();
		for (i = 0; i < n - 1; i++) {
			temp = a.getData(i + 1);
			j = i;
			while (j > -1 && temp <= a.getData(j)) {
				a.setData(j + 1, a.getData(j));
				j--;
			}
			a.setData(j + 1, temp);
		}
		time = System.currentTimeMillis() - time;
		// 將a寫(xiě)入partSortFile中
		for (int k = 0; k < a.size(); k++)
			partSortFile.write(a.getData(k) + " ");
		partSortFile.close();
		return time;
	}

	// 堆排序方法，將IntList a中的數(shù)升序排序，排好之后寫(xiě)入到BufferedWriter partSortFile中，并返回單次排序的時(shí)間
	public long heapSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		int temp;
		int n = a.size();
		long time = System.currentTimeMillis();
		// 創(chuàng)建最大堆
		for (int i = (n - 1) / 2; i >= 0; i--)
			createHeap(a, n, i);

		for (int i = n - 1; i > 0; i--) {
			temp = a.getData(0);
			a.setData(0, a.getData(i));
			a.setData(i, temp);
			createHeap(a, i, 0);
		}
		time = System.currentTimeMillis() - time;
		for (int k = 0; k < a.size(); k++)
			partSortFile.write(a.getData(k) + " ");
		partSortFile.close();
		return time;
	}

	// 創(chuàng)建堆的方法
	public void createHeap(IntList a, int n, int h) throws Exception {
		int i, j, flag;
		int temp;
		i = h;
		j = 2 * i + 1;
		temp = a.getData(i);
		flag = 0;
		while (j < n && flag != 1) {
			if (j < n - 1 && a.getData(j) < a.getData(j + 1))
				j++;
			if (temp > a.getData(j))
				flag = 1;
			else {
				a.setData(i, a.getData(j));
				i = j;
				j = 2 * i + 1;
			}
		}
		a.setData(i, temp);
	}

	// 快速排序
	public long quickSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		long time = System.currentTimeMillis();
		quick(a, 0, a.size() - 1);
		time = System.currentTimeMillis() - time;
		for (int k = 0; k < a.size(); k++)
			partSortFile.write(a.getData(k) + " ");
		partSortFile.close();
		return time;
	}

	public void quick(IntList a, int low, int high) throws Exception {
		int i, j;
		int temp;
		i = low;
		j = high;
		temp = a.getData(low);

		while (i < j) {
			while (i < j && temp <= a.getData(j))
				j--;
			if (i < j) {
				a.setData(i, a.getData(j));
				i++;
			}

			while (i < j && a.getData(i) < temp)
				i++;
			if (i < j) {
				a.setData(j, a.getData(i));
				j--;
			}
		}
		a.setData(i, temp);

		if (low < i)
			quick(a, low, i - 1);
		if (i < high)
			quick(a, i + 1, high);
	}

	// 歸并排序
	public long mergeSort(IntList a, BufferedWriter partSortFile)
			throws Exception {
		int i;
		int n = a.size();
		int k = 1;
		int[] swap = new int[n];
		long time = System.currentTimeMillis();
		while (k < n) {
			merge(a, swap, k);
			for (i = 0; i < n; i++)
				a.setData(i, swap[i]);
			k = 2 * k;
		}
		time = System.currentTimeMillis() - time;
		for (int l = 0; l < a.size(); l++)
			partSortFile.write(a.getData(l) + " ");
		partSortFile.close();
		return time;
	}

	public static void merge(IntList a, int[] swap, int k) throws Exception {
		int temp1, temp2, x = 0, i;
		// 每次循環(huán)將相鄰的兩個(gè)分塊和到一起
		for (i = 2 * k; i < swap.length && x < swap.length; i += 2 * k) {
			int j, l;
			for (j = i - k, l = i - 2 * k; j < i && l < i - k;) {
				temp1 = a.getData(l);
				temp2 = a.getData(j);
				if (temp1 <= temp2) {
					swap[x++] = temp1;
					l++;
				} else {
					swap[x++] = temp2;
					j++;
				}
			}
			// 將剩下的數(shù)全部放入swap中
			while (j < i)
				swap[x++] = a.getData(j++);
			while (l < i - k)
				swap[x++] = a.getData(l++);
		}
		// 當(dāng)剩下的數(shù)不足一個(gè)分塊的時(shí)候全部加入到swap中
		if (swap.length - x <= k && swap.length != x)
			for (; x < swap.length; x++)
				swap[x] = a.getData(x);
		// 當(dāng)剩下的數(shù)多于一個(gè)分塊 但少于兩個(gè)分塊時(shí),將他們看作是兩個(gè)長(zhǎng)度不同的分塊合并
		else if (swap.length - x > k && swap.length != x) {
			int m = x + k;
			int j, l;
			for (j = m, l = x; j < swap.length && l < m;) {
				temp1 = a.getData(l);
				temp2 = a.getData(j);
				if (temp1 <= temp2) {
					swap[x++] = temp1;
					l++;
				} else {
					swap[x++] = temp2;
					j++;
				}
			}
			while (j < swap.length)
				swap[x++] = a.getData(j++);
			while (l < m)
				swap[x++] = a.getData(l++);
		}
	}

	// 求數(shù)組中除-1外的最小整數(shù)的下標(biāo)
	public int Min(int[] a) {
		int index = 0;
		for (int i = 0; i < a.length; i++)
			if ((a[index] == -1 || a[index] > a[i]) && a[i] != -1)
				index = i;
		return index;
	}
}

// 整數(shù)讀取類(lèi)，在一個(gè)BufferedReader中讀取兩個(gè)空格之間的字符組成字符串輸出，因?yàn)檫@是我們data_src.txt文件中整數(shù)保存的格式
class IntegerReader {
	BufferedReader reader;

	IntegerReader(BufferedReader read) {
		reader = read;
	}

	// 返回下一個(gè)整數(shù)，當(dāng)沒(méi)有整數(shù)時(shí)就返回-1
	int readerInt() throws IOException {
		String number = "";
		int temp = reader.read();
		while ((char) temp != ' ' && temp != -1) {
			number += (char) temp;
			temp = reader.read();
		}
		if (temp == -1)
			return -1;
		else
			return Integer.parseInt(number);
	}

	// 關(guān)閉流
	void close() throws IOException {
		reader.close();
	}
}

// 順序表類(lèi)，用來(lái)儲(chǔ)存整數(shù)
class IntList {
	private int size = 0;

	private int[] shu;

	public IntList() {
		shu = new int[10];
		size = 0;
	}

	public void appond(int intobj) {
		// 如果數(shù)組空間不夠就將其長(zhǎng)度擴(kuò)大一倍
		if (size + 1 > shu.length) {
			int[] sh = shu;
			shu = new int[sh.length * 2];
			for (int j = 0; j < size; j++)
				shu[j] = sh[j];
			shu[size] = intobj;
			size++;
		} else {
			shu[size] = intobj;
			size++;
		}
	}

	public int getData(int i) throws Exception {
		if (i < 0 || i >= size)
			throw new Exception();
		return shu[i];
	}

	public void setData(int i, int intobj) {
		shu[i] = intobj;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}
}