#include "IndexMaxHeap.h"
#include "SortHelper.h"
#include <stdlib.h>
#include <assert.h>


typedef struct Index_max_heap_s Index_max_heap;

typedef struct Index_max_heap_s {
    int count;                                      //-> 当前堆内数据的大小
    int capacity;                                   //-> 当前堆的容量
    void (*insert)(Index_max_heap *,int,int);       //-> 插入函数
    int (*extract_max)(Index_max_heap *);           //-> 输出一个最大值
    int (*extract_max_index)(Index_max_heap *);     //-> 输出一个最大值的索引
    int (*get_item_by_index)(Index_max_heap *,int); //-> 返回一个指定的索引值
    void (*change_item_by_index)(Index_max_heap *,int,int); //-> 更改指定索引的值
    int *item;                                      //-> 数组指针
    int *indexs;                                    //-> 数组指针 索引
    int *reverses;                                  //-> 数组指针 反向查找索引
    void (*print_to_dot)(Index_max_heap *);         //-> 生成 dot 语言 函数
} Index_max_heap;


static void index_max_heap_shift_up(Index_max_heap *index_max_heap,int k) {
    while (k > 1 && index_max_heap->item[index_max_heap->indexs[k/2]] < index_max_heap->item[index_max_heap->indexs[k]]) {
        /// 仅交换 index
        swap(&index_max_heap->indexs[k/2], &index_max_heap->indexs[k]);
        index_max_heap->reverses[index_max_heap->indexs[k/2]] = k/2;
        index_max_heap->reverses[index_max_heap->indexs[k]] = k;
        k /= 2;
    }
}

static void index_max_heap_shift_down(Index_max_heap *index_max_heap,int k) {
    while (2*k <= index_max_heap->count) {
        int index = 2*k;
        if (index + 1 <= index_max_heap->count && index_max_heap->item[index_max_heap->indexs[index + 1]] > index_max_heap->item[index_max_heap->indexs[index]]) {
            index += 1;
        }
        if (index_max_heap->item[index_max_heap->indexs[k]] > index_max_heap->item[index_max_heap->indexs[index]]) {
            break;
        }
        
        swap(&index_max_heap->indexs[k], &index_max_heap->indexs[index]);
        index_max_heap->reverses[index_max_heap->indexs[k]] = k;
        index_max_heap->reverses[index_max_heap->indexs[index]] = index;

        k = index;
    }
}

static void insert(Index_max_heap* index_max_heap,int index,int item) {
    if (index_max_heap->count > index_max_heap->capacity) {
        return;
    }
    index_max_heap->count += 1;
    index_max_heap->item[index_max_heap->count] = item;
    index_max_heap->reverses[index] = index_max_heap->count;
    index_max_heap->indexs[index_max_heap->count] = index;
    index_max_heap_shift_up(index_max_heap, index_max_heap->count);
}

static int extract_max(Index_max_heap* index_max_heap) {
    assert(index_max_heap->count > 0);
    int ret = index_max_heap->item[index_max_heap->indexs[1]];
    
    swap(&index_max_heap->indexs[1], &index_max_heap->indexs[index_max_heap->count]);
    index_max_heap->reverses[index_max_heap->indexs[1]] = 1;
    index_max_heap->reverses[index_max_heap->indexs[index_max_heap->count]] = 0;
    
    index_max_heap->count -= 1;
    
    index_max_heap_shift_down(index_max_heap, 1);
    
    return ret;
}

static int extract_max_index(Index_max_heap* index_max_heap) {
    assert(index_max_heap->count > 0);
    int ret = index_max_heap->indexs[1];
    
    swap(&index_max_heap->indexs[1], &index_max_heap->indexs[index_max_heap->count]);
    index_max_heap->reverses[index_max_heap->indexs[1]] = 1;
    index_max_heap->reverses[index_max_heap->indexs[index_max_heap->count]] = 0;

    index_max_heap->count -= 1;
    
    index_max_heap_shift_down(index_max_heap, 1);
    
    return ret;
}

static int contain(Index_max_heap* index_max_heap,int i) {
    assert(i + 1 >= 1 && i + 1 <= index_max_heap->capacity );
    return index_max_heap->reverses[i + 1] != 0;
}

static int get_item_by_index(Index_max_heap* index_max_heap,int index) {
    assert(contain(index_max_heap,index));
    return index_max_heap->item[index + 1];
}

static void change_item_by_index(Index_max_heap* index_max_heap,int index,int item) {
    assert(contain(index_max_heap,index));
    index += 1;
    index_max_heap->item[index] = item;
    
//    for (int i = 1; i <= index_max_heap->count; i++) {
//        if (index_max_heap->indexs[i] == index) {
//            index_max_heap_shift_up(index_max_heap, i);
//            index_max_heap_shift_down(index_max_heap, i);
//            return;
//        }
//    }
    
    int i = index_max_heap->reverses[index];
    index_max_heap_shift_up(index_max_heap, i);
    index_max_heap_shift_down(index_max_heap, i);
}

static void print_to_dot(Index_max_heap *index_max_heap) {
    printf("\n<---------- dot start ---------->\n\n");
    printf("digraph heap {\nnode[shape=circle];\nnodesep=0.3;\n");
    int count = index_max_heap->count;
    for (int i = 1; i <= count; i++) {
        int leftIndex = 2 * i;
        int rightIndex = 2 * i + 1;
        if (leftIndex <= count) {
            printf("\t%d -> %d;\n",index_max_heap->item[index_max_heap->indexs[i]],index_max_heap->item[index_max_heap->indexs[leftIndex]]);
        }
        if (rightIndex <= count) {
            printf("\t%d -> %d;\n",index_max_heap->item[index_max_heap->indexs[i]],index_max_heap->item[index_max_heap->indexs[rightIndex]]);
        }
    }
    printf("}\n");
    printf("\n\n<---------- dot end ---------->\n");
}


static Index_max_heap create_index_max_heap(int capacity) {
    
    int *item = (int *)malloc(sizeof(int) * (capacity + 1));
    int *indexs = (int *)malloc(sizeof(int) * (capacity + 1));
    int *reverses = (int *)malloc(sizeof(int) * (capacity + 1));
    for (int i = 0; i < capacity; i++) {
        item[i] = 0;
        indexs[i] = 0;
        reverses[i] = 0;
    }
    Index_max_heap index_max_heap = {
        .count = 0,
        .capacity = capacity,
        .insert = insert,
        .extract_max = extract_max,
        .extract_max_index = extract_max_index,
        .get_item_by_index = get_item_by_index,
        .change_item_by_index = change_item_by_index,
        .item = item,
        .indexs = indexs,
        .reverses = reverses,
        .print_to_dot = print_to_dot
    };
    return index_max_heap;
}


#pragma mark - test
void test_index_max_heap() {
    
//    int *a = generateNoRepeatRandomArray(20,0,100);
    
    int arr[] = { 31,2, 1,45,73, 69, 60, 59,91, 49,  43, 32,  29, 18,88, 17, 9,76, 6,  0};
    
    Index_max_heap index_max_heap = create_index_max_heap(50);
    
    for (int i = 0; i < 20; i++) {
        index_max_heap.insert(&index_max_heap,i,arr[i]);
    }
    
    void (*change_item_by_index)(Index_max_heap *index_max_heap,int,int) = index_max_heap.change_item_by_index;
    change_item_by_index(&index_max_heap,8,22);
    
    void (*print_to_dot)(Index_max_heap *index_max_heap) = index_max_heap.print_to_dot;
    print_to_dot(&index_max_heap);
    
    int (*extract_max)(Index_max_heap *index_max_heap) = index_max_heap.extract_max;
    for (int i = 1; i <= 20; i ++) {
        printf("%d, ",extract_max(&index_max_heap));
    }
}

typedef struct Heap_sort_max_s Heap_sort_max;

typedef struct Heap_sort_max_s {
    int count;                              //-> 当前堆内数据的大小
    int capacity;                           //-> 当前堆的容量
    void (*insert)(Heap_sort_max *,int);    //-> 插入函数
    int (*extract_max)(Heap_sort_max *);    //-> 输出一个最大值
    int *item;                              //-> 数组指针
    void (*print_to_dot)(Heap_sort_max *);  //-> 生成 dot 语言 函数
} Heap_sort_max;

static void heap_sort_max_shift_up(Heap_sort_max *heap_sort_max,int k) {
    while (k > 1 && heap_sort_max->item[k/2] < heap_sort_max->item[k]) {
        swap(&heap_sort_max->item[k/2], &heap_sort_max->item[k]);
        k /= 2;
    }
}

static void print_to_dot(Heap_sort_max *heap_sort_max) {
    printf("\n<---------- dot start ---------->\n\n");
    printf("digraph heap {\nnode[shape=circle];\nnodesep=0.3;\n");
    int count = heap_sort_max->count;
    for (int i = 1; i <= count; i++) {
        int leftIndex = 2 * i;
        int rightIndex = 2 * i + 1;
        if (leftIndex <= count) {
            printf("\t%d -> %d;\n",heap_sort_max->item[i],heap_sort_max->item[leftIndex]);
        }
        if (rightIndex <= count) {
            printf("\t%d -> %d;\n",heap_sort_max->item[i],heap_sort_max->item[rightIndex]);
        }
    }
    printf("}\n");
    printf("\n\n<---------- dot end ---------->\n");
}

static Heap_sort_max create_heap_sort_max(int capacity) {
    
    int *p = (int *)malloc(sizeof(int) * capacity);
    for (int i = 0; i < capacity; i++) {
        p[i] = 0;
    }
    Heap_sort_max heap_sort_max = {
        .count = 0,
        .capacity = capacity,
        .insert = insert,
        .extract_max = extract_max,
        .item = p,
        .print_to_dot = print_to_dot
    };
    return heap_sort_max;
}

static void free_heap_sort_max(Heap_sort_max *heap_sort_max) {
    free(heap_sort_max->item);
}

void test_heap_sort_max() {
    
    int *a = generateNoRepeatRandomArray(20,0,100);
    
    Heap_sort_max heap_sort_max = create_heap_sort_max(50);
    
    for (int i = 0; i < 20; i++) {
        heap_sort_max.insert(&heap_sort_max,a[i]);
    }
    
    void (*print_to_dot)(Heap_sort_max *heap_sort_max) = heap_sort_max.print_to_dot;
    print_to_dot(&heap_sort_max);
    
    free_heap_sort_max(&heap_sort_max);
}

static int extract_max(Heap_sort_max* heap_sort_max) {
    assert(heap_sort_max->count > 0);
    int ret = heap_sort_max->item[1];
    
    swap(&heap_sort_max->item[1], &heap_sort_max->item[heap_sort_max->count]);
    heap_sort_max->count -= 1;
    
    heap_sort_max_shift_down(heap_sort_max, 1);
    
    return ret;
}

void heap_sort(int arr[],int n) {
    Heap_sort_max heap_sort_max = create_heap_sort_max(n + 1);
    
    for (int i = 0; i < n; i++) {
        heap_sort_max.insert(&heap_sort_max,arr[i]);
    }
    
    for (int i = n-1; i >=0; i--) {
        arr[i] = ((int (*)(Heap_sort_max *heap_sort_max))heap_sort_max.extract_max)(&heap_sort_max);
    }
}

void heapify_sort(int arr[],int n) {
    Heap_sort_max heap_sort_max = create_heap_sort_max(n + 1);
    for (int i = 0; i < n; i ++) {
        heap_sort_max.item[i+1] = arr[i];
    }
    heap_sort_max.count = n;
    
    for (int i = n/2; i >= 1; i--) {
        heap_sort_max_shift_down(&heap_sort_max, i);/// O(n)
    }
    
    for (int i = n-1; i >=0; i--) {
        arr[i] = ((int (*)(Heap_sort_max *heap_sort_max))heap_sort_max.extract_max)(&heap_sort_max);
    }
}

// 顶结点的索引从 0 开始
static void heap_autochthonous_sort_shift_down(int arr[],int n,int k) {
    while ((2*k + 1) < n) {
        int index = 2*k + 1; // 取左孩子索引
        if (index + 1 < n && arr[index + 1] > arr[index]) { index++; }
        if (arr[k] > arr[index]) { break; }
        swap(&arr[k], &arr[index]);
        k = index;
    }
}

/// 原地堆排序 空间O(1)
void heap_autochthonous_sort(int arr[],int n) {
    /// heapify
    for (int i = (n-1)/2; i >= 0; i--) {
        heap_autochthonous_sort_shift_down(arr, n, i);
    }
    
    for (int i = n-1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heap_autochthonous_sort_shift_down(arr, i, 0);
    }
}

void __quickSort(int arr[],int l,int r) {
    if (l >= r) {
        return;
    }

    int p = __partition(arr,l,r);
    
    __quickSort(arr, l, p-1);
    __quickSort(arr, p+1, r);
}

void quickSort(int arr[],int n) {
    __quickSort(arr,0,n-1);
}

int __partition_00(int arr[],int l,int r) {
    swap(&arr[l], &arr[rand()%(r-l+1) + l]);
    int v = arr[l];
    int j = l;
    for (int i = l+1; i <= r; i++) {
        if (arr[i] < v) {
            swap(&arr[j +1], &arr[i]);
            j ++;
        }
    }
    swap(&arr[l], &arr[j]);
    return j;
}

5, 6, 5, 5, 5, 5, 8, 3, 5, 5

int __partition_twoWays(int arr[],int l,int r) {
    swap(&arr[l], &arr[rand()%(r-l+1) + l]);
    int v = arr[l];
    int i = l + 1;
    int j = r;
    while (1) {
        while (i <= r && arr[i] < v) { i ++; }
        while (j >= l+1 && arr[j] > v) { j --; }
        if (j <= i) { break; }
        swap(&arr[i], &arr[j]);
        i++;
        j--;
    }
    swap(&arr[l], &arr[j]);
    return j;
}

void mergeSort(int arr[],int n) {
    __mergeSort(arr, 0, n-1);
}

void __mergeSort(int arr[],int l,int r) {
    
    int mid = l + (r - l)/2;
    
    if (l >= r) {
        return;
    }
    
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    
    _merge(arr, l, mid, r);
}

int mid = (l + r)/2;

void shellsort2(int a[], int n) {

    int j, gap;
    
    for (gap = n / 2; gap > 0; gap /= 2)
        for (j = gap; j < n; j++)//从数组第gap个元素开始
            if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
            {
                int temp = a[j];
                int k = j - gap;
                while (k >= 0 && a[k] > temp)
                {
                    a[k + gap] = a[k];
                    k -= gap;
                }
                a[k + gap] = temp;
            }
}

int n  = 100000;
// 有序
int *a = generateSequenceArray(n);
// 近乎有序
int *b = generateRandomSequenceArray(n, 100);
// 随机
int *c = generateRandomArray(n,0,n);
// 倒叙
int *d = generateReverseArray(n);

int *a1 = copyGenerateRandomArray(a, n);
int *a2 = copyGenerateRandomArray(a, n);
int *a3 = copyGenerateRandomArray(a, n);

int *b1 = copyGenerateRandomArray(b, n);
int *b2 = copyGenerateRandomArray(b, n);
int *b3 = copyGenerateRandomArray(b, n);

int *c1 = copyGenerateRandomArray(c, n);
int *c2 = copyGenerateRandomArray(c, n);
int *c3 = copyGenerateRandomArray(c, n);

int *d1 = copyGenerateRandomArray(d, n);
int *d2 = copyGenerateRandomArray(d, n);
int *d3 = copyGenerateRandomArray(d, n);

printf("**************有序*************\n");
testSort("插入排序　　", insertSort,a1, n);
testSort("插入排序优化", insertSort2,a2, n);
testSort("希尔排序　　", shellsort2,a3, n);
printf("\n**************近乎有序*************\n");
testSort("插入排序　　", insertSort,b1, n);
testSort("插入排序优化", insertSort2,b2, n);
testSort("希尔排序　　", shellsort2,b3, n);
printf("\n**************随机*************\n");
testSort("插入排序　　", insertSort,c1, n);
testSort("插入排序优化", insertSort2,c2, n);
testSort("希尔排序　　", shellsort2,c3, n);
printf("\n**************倒叙*************\n");
testSort("插入排序　　", insertSort,d1, n);
testSort("插入排序优化", insertSort2,d2, n);
testSort("希尔排序　　", shellsort2,d3, n);

free(a);free(a1);free(a2);free(a3);

free(b);free(b1);free(b2);free(b3);

free(c);free(c1);free(c2);free(c3);

free(d);free(d1);free(d2);free(d3);

for (int j = i; j > 0; j--) {
    if (arr[j] < arr[j - 1]) {
        swap(&arr[j], &arr[j-1]);
    } else {
        break;
    }
}

for (int i = 1; i < n; i++) {
    for (int j = i; j > 0; j--) {
        if (arr[j] < arr[j - 1]) {
            swap(&arr[j], &arr[j-1]);
        } else {
            break;
        }
    }
}

void insertSort(int arr[],int n) {
    
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && (arr[j] < arr[j - 1]); j--) {
            swap(&arr[j], &arr[j-1]);
            
        }
    }
}

int n  = 100000;
// 有序
int *a = generateSequenceArray(n);
// 近乎有序
int *b = generateRandomSequenceArray(n, 100);
// 随机
int *c = generateRandomArray(n,0,n);
// 倒叙
int *d = generateReverseArray(n);

int *a1 = copyGenerateRandomArray(a, n);

int *b1 = copyGenerateRandomArray(b, n);

int *c1 = copyGenerateRandomArray(c, n);

int *d1 = copyGenerateRandomArray(d, n);

printf("**************有序*************\n");
testSort("插入排序　　", insertSort,a1, n);
printf("\n**************近乎有序*************\n");
testSort("插入排序　　", insertSort,b1, n);
printf("\n**************随机*************\n");
testSort("插入排序　　", insertSort,c1, n);
printf("\n**************倒叙*************\n");
testSort("插入排序　　", insertSort,d1, n);

free(a);free(a1);

free(b);free(b1);

free(c);free(c1);

free(d);free(d1);

for (int i = 1; i < n; i++) {
   
   int e = arr[i];//将该元素记录下来
   int j;
   for (j = i; j > 0 && arr[j - 1] > e; j--) {
       arr[j] = arr[j - 1];
   }
   arr[j] = e;
}

{6, 2, 4, 1, 5, 9 }

void bubbleSort(int arr[],int n) {
    for (int i = 0; i < n ; i ++) {
        for (int j = 1; j < n-i; j ++) {
            if (arr[j] < arr[j-1]) {
                swap(&arr[j], &arr[j-1]);
            }
        }
    }
}

第一次：2 4 1 5 6 9 
第二次：2 1 4 5 6 9 
第三次：1 2 4 5 6 9 
第四次：1 2 4 5 6 9 
第五次：1 2 4 5 6 9 
第六次：1 2 4 5 6 9

void bubbleSort2(int arr[],int n) {
    int flag = 1;
    for (int i = 0; i < n && flag ; i ++) {
        flag = 0;
        for (int j = 1; j < n - i; j ++) {
            
            if (arr[j] < arr[j-1]) {
                flag = 1;
                swap(&arr[j], &arr[j-1]);
            }
        }
    }
}

void selectSort(int arr[],int n) {
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(&arr[i], &arr[minIndex]);
    }
}

- (void)start NS_AVAILABLE(10_5, 2_0);

@property NSQualityOfService qualityOfService NS_AVAILABLE(10_10, 8_0);

@property (readonly, getter=isCancelled) BOOL cancelled NS_AVAILABLE(10_5, 2_0);
- (void)cancel NS_AVAILABLE(10_5, 2_0);

+ (void)exit;

@property (readonly) BOOL isMainThread NS_AVAILABLE(10_5, 2_0);
+ (BOOL)isMainThread NS_AVAILABLE(10_5, 2_0); // reports whether current thread is main
+ (NSThread *)mainThread NS_AVAILABLE(10_5, 2_0);