#include <iostream>

#include "seq_list.hpp"
#include "singly_linked_list.hpp"
#include "doubly_linked_list.hpp"
#include "circular_singly_linked_list.hpp"
#include "circular_doubly_linked_list.hpp"
#include "static_linked_list.hpp"
#include "seq_list_algorithm.hpp"

#include "seq_stack.hpp"
#include "linked_stack.hpp"

#include "linked_queue.hpp"
#include "circular_queue.hpp"
#include "double_ended_queue.hpp"

#include "sparse_matrix.hpp"
#include "simple_gen_list.h"
#include "cyber_dash_string.h"

#include "binary_tree.hpp"
#include "huffman_tree.hpp"
#include "min_heap.hpp"
#include "min_priority_queue.hpp"
#include "max_heap.hpp"
#include "max_priority_queue.hpp"

#include "matrix_graph.hpp"
#include "adjacency_list_graph.hpp"

#include "binary_search_tree.hpp"

#include "util.hpp"
#include "sort_algorithm.hpp"

const int eps = 1e-6;

const int N = 1e3 + 10;

typedef struct num
{
	char a, b, c, temp;	// 0 1 2 3 
	int d;				// 4 5 6 7
	double e;			// 8 9 10 11 12 13 14 15
	long f;				// 16 17 18 19
}Number;

int c = 1;
int e;

void test()
{
	int* a = new int(1);
	int b = 1;
	static int d = 1;
	static int f;

	const char* str = "1";

	cout << "堆区地址：" << (int)a << endl;
	cout << "栈区地址：" << (int)&b << endl;
	cout << "初始化静态区地址：" << (int)&c << endl;
	cout << "初始化静态区地址：" << (int)&d << endl;
	cout << "未初始化静态区地址：" << (int)&e << endl;
	cout << "未初始化静态区地址：" << (int)&f << endl;
	cout << "常量区地址：" << (int)str << endl;

	cout << "============================" << endl;

	/*int aaa = 10;
	int bbb = 20;

	c_swap(&aaa,&bbb,sizeof aaa, sizeof bbb);

	cout << aaa << endl << bbb << endl;*/
}

void testStr()
{
	const char* s = "hhh"; // ==> char s[] = { 'h','h','h','\0'};，但是会被放到只读常量区，里面的内容不可修改

	// 下面两种是一样的
	char ss[] = { 'h','h','h' }; // 后面会默认补‘\0’
	char sss[] = "hhh"; // ==> char ss[] = { 'h','h','h','\0'};，放到的是当前方法的栈区，里面的内容可以修改

	cout << (int) & ss << endl;		// 栈区
	cout << (int) s << endl;		// 常量区
	cout << (int) & sss << endl;	// 栈区
}

void test(int a)
{
	cout << a << endl;
}

void testSeqList()
{
	SeqList<int>* list = new SeqList<int>(100);

	list->insert(0, 12);
	list->insert(1, 22);
	list->insert(2, 4);
	list->insert(3, 100);
	list->insert(4, 8);
	
	cout << "排序前" << endl;
	list->print();

	list->sort();

	cout << "排序后" << endl;
	list->print();
	
	delete list;

	//SeqList<int> list(100);

	//cout << list.capacity() << endl;

	//for (int i = 1; i < 30; i++)
	//{
	//	bool res = list.insert(i - 1, i + 10);
	//	if (!res)
	//		cout << "插入失败" << endl;
	//}

	//list.print();
}

void testSinglyLinkedList()
{
	SinglyLinkedList<int>* list = new SinglyLinkedList<int>();

	for (int i = 1; i < 20; i++)
	{
		list->insert(0,i+10);
	}
	
	list->print();

	delete list;
}

void testStaticLinkedList()
{
	StaticLinkedList<int>* list = new StaticLinkedList<int>();

	list->insert(0, 12);
	list->insert(1, 1212);
	list->insert(2, 121212);
	list->insert(3, 12121212);
	list->insert(4, 1212121212);

	list->print();

	//cout << (*list)[-111].data << endl;

	//cout << (int)list << endl;
	//cout << (int)&(*list)[-111] << endl;
	//
	//cout << (*list)[5].data << endl;
	//cout << (*list)[7].data << endl;
	//cout << (*list)[-7].data << endl;

	StaticLinkedListNode<int> element = (*list)[-1];

	cout << element.data << endl;
	cout << element.data << endl;
	cout << element.data << endl;
	cout << element.data << endl;

	delete list;

}

void testSeqListAlgorithm()
{
	SeqList<int> a(100);
	SeqList<int> b(100);

	a.insert(0,1);
	a.insert(1,11);
	a.insert(2,111);
	a.insert(3,1111);
	a.insert(4,11111);

	b.insert(0, 2);
	b.insert(1, 11);
	b.insert(2, 111);
	b.insert(3, 1111);
	b.insert(4, 11111);

	//seqListUnion(a, b);
	seqListInterSection(a, b);

	a.print();

}

void testSeqStack()
{
	SeqStack<int> seq_stack;

	seq_stack.push(1);
	seq_stack.push(11);
	seq_stack.push(111);
	seq_stack.push(1111);

	cout << seq_stack << endl;
	//int num;
	//seq_stack.top(num);
	//cout << num << endl;
}

void testLinkedStack()
{
	LinkedStack<int>* stack_ = new LinkedStack<int>{};

	stack_->push(1);
	stack_->push(11);
	stack_->push(111);
	stack_->push(1111);
	stack_->push(11111);

	cout << *stack_;

	delete stack_;
}

void testLinkedQueue()
{
	LinkedQueue<double> queue{}; // 等价于LinkedQueue<double> queue; 即调用空参构造

	queue.enQueue(1.12);
	queue.enQueue(11);
	queue.enQueue(111);
	queue.enQueue(1111);

	cout << queue << endl;
}

void testCircularQueue()
{
	CircularQueue<long>* queue = new CircularQueue<long>();

	queue->enQueue(1);
	queue->enQueue(11);
	queue->enQueue(111);
	queue->enQueue(1111);

	cout << *queue << endl;

	delete queue;
}

void testDoubleEndedQueue()
{
	DoubleEndedQueue<long long> queue;

	queue.pushBack(1);
	queue.pushBack(11);
	queue.pushBack(111);
	queue.pushBack(1111);

	cout << queue << endl;

	long long temp;

	queue.popFront(temp);

	cout << "从队头弹出的元素是：" << temp << endl;

	queue.popBack(temp);

	cout << "从队尾弹出的元素是：" << temp << endl;

	temp = 2;

	queue.pushFront(temp);

	cout << "向队头插入一个元素：" << temp << endl << endl;

	cout << queue << endl;
}

void testSparseMatrix()
{
	SparseMatrix<int>* matrix = new SparseMatrix<int>(100);
	cin >> *matrix;

	//matrix = matrix->fastTranspose();

	//cout << "转置后的" << endl << *matrix << endl;
	SparseMatrix<int>* matrix_temp = new SparseMatrix<int>(100);
	cin >> *matrix_temp;

	*matrix = matrix->add(*matrix_temp);

	cout << "加法操作后" << endl << *matrix;

	delete matrix;
	delete matrix_temp;
}

void testCyberDashString()
{
	string s = "ababababeababf";

	//cout << s.c_str() << endl;

	String str(s.c_str());
	
	String pattern_str((new string("ababf"))->c_str());

	cout << "暴力匹配：" << str.bruteForceMatch(pattern_str, 1) << endl;
	cout << "简单构造的next数组执行的KMP匹配：" << str.kmpMatch(pattern_str, 1) << endl;
	cout << "CyberDash构造的next数组执行的KMP匹配：" << str.kmpMatchByCyberDash(pattern_str, 1) << endl;

}

template <typename TData>
void visit(binary_tree::BinaryTreeNode<TData>* node)
{
	cout << node->data << "，";
}

void testBinaryTree()
{
	BinaryTree<char>* b_tree1 = new BinaryTree<char>();

	b_tree1->createByPreOrderAndInOrderList("ABDECFG","DBEAFCG",7);

	cout << "前序遍历的结果：";
	b_tree1->preOrderTraversal(visit);
	cout << endl;

	cout << "中序遍历的结果：";
	b_tree1->inOrderTraversal(visit);
	cout << endl;

	cout << "后序遍历的结果：";
	b_tree1->postOrderTraversal(visit);
	cout << endl;

	cout << "层序遍历的结果：";
	b_tree1->levelOrderTraversal(visit);
	cout << endl;

	BinaryTree<char>* b_tree2 = new BinaryTree<char>();
	b_tree2->createByPreOrderAndInOrderList("ABDECFG", "DBEAFCG", 7);


	if (*b_tree1 == *b_tree2)
		cout << "ok" << endl;

	cout << *b_tree1 << endl;

	delete b_tree1;
	delete b_tree2;
}

void testHuffmanTree()
{
	const char keys[] = "abcdefgh";

	const int weights[] = {2,4,1,7,5,6,3,1};

	int len = sizeof(weights) / sizeof(int);

	HuffmanTree<char, int>* huffmanTree = new HuffmanTree<char, int>(keys,weights,len);

	huffmanTree->printTree();

	delete huffmanTree;
}

void testMinHeap()
{
	// 一维数组
	int arr[] = { 1,23,-45,2,6,9,4,-5,10 };

	MinHeap<int>* m_heap = new MinHeap<int>(arr,sizeof arr / sizeof(int),N);

	int element;

	for (int i = 0; i < sizeof arr / sizeof(int); i++)
	{
		m_heap->pop(element);
		cout << element << endl;
	}

	delete m_heap;
}

void testMinPriorityQueue()
{
	// 一维数组
	int arr[] = { 1,23,-45,2,6,9,4,-5,10 };

	MinPriorityQueue<int> min_queue(arr,sizeof arr / sizeof(int));

	int data;
	for (int i = 0; i < sizeof arr / sizeof(int); i++)
	{
		min_queue.deQueue(data);
		cout << data << endl;
	}
}

void testMaxHeap()
{
	// 一维数组
	int arr[] = { 1,23,-45,2,6,9,4,-5,10 };

	MaxHeap<int>* m_heap = new MaxHeap<int>(arr, sizeof arr / sizeof(int), N);

	int element;

	for (int i = 0; i < sizeof arr / sizeof(int); i++)
	{
		m_heap->pop(element);
		cout << element << endl;
	}

	delete m_heap;
}

void testMaxPriorityQueue()
{
	// 一维数组
	int arr[] = { 1,23,-45,2,6,9,4,-5,10 };

	MaxPriorityQueue<int> max_queue(arr, sizeof arr / sizeof(int));

	int data;
	for (int i = 0; i < sizeof arr / sizeof(int); i++)
	{
		max_queue.deQueue(data);
		cout << data << endl;
	}
}

template <typename TKey,typename TValue>
void nodePrint(BstNode<TKey, TValue>* node)
{
	cout << "[key:" << node->key() << ", value:" << node->value() << "]";
}

void testBinarySearchTree()
{
	BinarySearchTree<int, int>* bst = new BinarySearchTree<int, int>();

	for (int i = 0; i < 10; i++)
	{
		bst->insertRecursive(i,i*100);
	}

	bst->print(nodePrint);

	delete bst;
}

void testSortAlgorithm()
{
	int data_list[] = {1,23,2,456,33,12,100,999};
	int length = sizeof data_list / sizeof(int);

	cout << "排序前:" << endl;
	printArray(data_list,sizeof data_list / sizeof(int));

	//bubbleSort(data_list, length);
	//selectionSort(data_list, length);
	//insertionSort(data_list, length);
	//int gaps[N];
	//int gaps_count = 0,temp = length;
	//while (temp)
	//{
	//	gaps[gaps_count] = temp / 2;
	//	gaps_count++;
	//	temp /= 2;
	//}
	//shellSort(data_list,gaps,length,gaps_count);

	//mergeSortRecursive(data_list,length);
	//mergeSort(data_list,length);
	//quickSort(data_list,length);
	heapSort(data_list,length);

	cout << "排序后:" << endl;
	printArray(data_list, sizeof data_list / sizeof(int));
}

int main()
{
	test();
	//testStr();

	//test(12);
	//testSeqList();
	//testSinglyLinkedList();
	//testStaticLinkedList();
	//testSeqListAlgorithm();
	//testSeqStack();
	//testLinkedStack();
	//testLinkedQueue();
	//testCircularQueue();
	//testDoubleEndedQueue();
	//testSparseMatrix();
	//testCyberDashString();
	//testBinaryTree();
	//testHuffmanTree();
	//testMinHeap();
	//testMinPriorityQueue();
	//testMaxHeap();
	//testMaxPriorityQueue();
	//testBinarySearchTree();
	testSortAlgorithm();

	system("pause");

	return 0;
}