string stuff & closed file from reading

1 files changed, 426 insertions, 0 deletions

diff --git a/src/sort.c b/src/sort.c
new file mode 100644
index 0000000..ee9a40b
--- /dev/null
+++ b/src/sort.c
@@ -0,0 +1,426 @@
+#include "table.h"
+#include <stdlib.h>
+
+int i_hoarepartition(double* arr, int low, int high){
+    double pivot = arr[((int)((high - low) / 2)) + low];
+    int i = low - 1;
+    int j = high + 1;
+
+    for(;;){
+      i++; j--;
+      
+      while(arr[i] > pivot) i++;
+      while(arr[j] < pivot) j--;
+      if(i >= j) return j;
+
+      i_swap(arr[i],arr[j]);
+    }
+}
+
+void i_quicksort(double* arr, int low, int high){
+    if(low >= 0 && high >= 0 && low < high){
+      int p = i_hoarepartition(arr, low, high);
+      i_quicksort(arr, low, p);
+      i_quicksort(arr, p + 1, high);
+    }
+}
+
+int l_quicksort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1); 
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+       
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+    
+    i_quicksort(nums, 0, len - 1);
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+
+    free(nums);
+    return 1;
+}
+
+void i_merge(double* arr, int b, int m, int e){
+    int n1 = m - b + 1;
+    int n2 = e - m;
+
+    double* left = malloc(sizeof * left * n1);
+    double* right = malloc(sizeof * right * n2);
+
+    for(int i = 0; i < n1; i++) left[i] = arr[b + i];
+    for(int i = 0; i < n2; i++) right[i] = arr[m + 1 + i];
+
+    int l_ind = 0;
+    int r_ind = 0;
+    int k = b;
+
+    for(; l_ind < n1 && r_ind < n2; k++){
+      if(left[l_ind] >= right[r_ind]){
+        arr[k] = left[l_ind];
+        l_ind++;
+      } else {
+        arr[k] = right[r_ind];
+        r_ind++;
+      }
+    }
+
+    for(; l_ind < n1; k++){
+      arr[k] = left[l_ind];
+      l_ind++;
+    }
+    for(; r_ind < n2; k++){
+      arr[k] = right[r_ind];
+      r_ind++;
+    }
+
+    free(left);
+    free(right);
+}
+
+void i_mergesort(double* arr, int b, int e){
+    if(b < e){
+      int mid = (b + e) /2;
+      i_mergesort(arr, b, mid);
+      i_mergesort(arr, mid + 1, e);
+      i_merge(arr, b, mid, e);
+    } 
+}
+
+int l_mergesort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1); 
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+       
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+   
+    i_mergesort(nums, 0, len - 1);
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+
+    free(nums);
+    return 1;
+}
+
+void i_heapify(double* arr, int n, int i){
+  int largest = i;
+  int left = 2 * i + 1;
+  int right = 2 * i + 2;
+
+  if(left < n && arr[left] < arr[largest])
+    largest = left;
+
+  if(right < n && arr[right] < arr[largest])
+    largest = right;
+
+  if(largest != i){
+    i_swap(arr[i],arr[largest]);
+    i_heapify(arr,n,largest);
+  }
+}
+
+int l_heapsort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1); 
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+       
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+    for(int i = len / 2 - 1; i >= 0; i--) 
+      i_heapify(nums,len,i);
+
+    for(int i = len - 1; i >= 0; i--){
+      i_swap(nums[i],nums[0]);
+      i_heapify(nums, i, 0);
+    }
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+    free(nums);
+    return 1;
+}
+
+int l_shellsort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+
+    for(int interval = len/2; interval > 0; interval /=2){
+      for(int i = interval; i < len; i++){
+        double temp = nums[i];
+        int j;
+        for(j = i; j >= interval && nums[j - interval] < temp; j -= interval){
+          nums[j] = nums[j - interval];
+        }
+        nums[j] = temp;
+      }
+    }
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+
+    free(nums);
+    return 1;
+}
+
+int l_bubblesort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+
+    int n = len;
+    for(;n > 0;){
+      int new = 0;
+      
+      for(int i = 0; i != n-1; i++){
+        if(nums[i+1]>nums[i]){
+          double temp = nums[i];
+          nums[i] = nums[i+1];
+          nums[i+1] = temp;
+
+          new = i+1;
+        } 
+      }
+      
+      n = new;
+    }
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+    
+    free(nums);
+    return 1;
+}
+
+int l_countingsort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    int* nums = malloc(sizeof * nums * len);
+    int* out = malloc(sizeof * nums * len);
+    int max = 0;
+    for(int i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      nums[i] = luaL_checknumber(L, -1);
+      out[i] = 0;
+      
+      if(nums[i]<0) p_fatal("array.countingsort(<table>) requires all indices to be >= 0");
+      max = max < nums[i] ? nums[i] : max;
+
+      lua_pop(L,1);
+    }
+   
+    int* count = calloc(max + 1, sizeof * count);
+
+    for(size_t i = 0; i < len; i++){
+      count[nums[i]]++;
+    } 
+    
+    for(size_t i = 1; i <= max; i++){
+      count[i] += count[i - 1];
+    }
+
+    for(int i = len - 1; i >= 0; i--){
+      out[count[nums[i]] - 1] = nums[i];
+      count[nums[i]]--;
+    }
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,out[i]);
+      lua_settable(L, -3);
+    }
+    
+    free(count);
+    free(nums);
+    free(out);
+    return 1;
+}
+
+int i_sorted(double* arr, size_t len){
+    for(size_t i = 0; i != len - 1; i++)
+      if(arr[i] > arr[i+1]) return 0;
+    return 1;
+}
+
+int l_miraclesort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+
+    for(;!i_sorted(nums,len););
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+    
+    free(nums);
+    return 1;
+}
+
+int l_stalinsort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    size_t rlen = 0;
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      double n = luaL_checknumber(L, -1);
+      if(rlen == 0 || nums[rlen - 1] <= n){
+        nums[rlen] = n;
+        rlen++;
+      }
+      
+      lua_pop(L,1);
+    }
+
+
+    lua_newtable(L);
+    for(size_t i = 0; i != rlen; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+
+    free(nums);
+    return 1;
+}
+
+void i_slowsort(double* arr, int i, int j){
+    if(i >= j) return;
+
+    int m = (i + j) /2;
+
+    i_slowsort(arr, i, m);
+    i_slowsort(arr, m + 1, j);
+
+    if(arr[j] < arr[m]){
+      i_swap(arr[j], arr[m]);
+    }
+
+    i_slowsort(arr, i, j - 1);
+}
+
+int l_slowsort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    double* nums = malloc(sizeof * nums * len);
+    for(int i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+
+    i_slowsort(nums, 0, len - 1);
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+
+    free(nums);
+    return 1;
+}
+
+int l_bogosort(lua_State* L) {
+    luaL_checktype(L, 1, LUA_TTABLE);
+    size_t len = lua_objlen(L,1);
+    double* nums = malloc(sizeof * nums * len);
+    for(size_t i = 0; i <= len-1; i++){
+
+      lua_pushinteger(L,i+1);
+      lua_gettable(L,1);
+
+      nums[i] = luaL_checknumber(L, -1);
+      lua_pop(L,1);
+    }
+
+    for(;!i_sorted(nums, len);){
+      i_shuffle(nums, len);
+    }
+
+    lua_newtable(L);
+    for(size_t i = 0; i != len; i++){
+      lua_pushnumber(L,i+1);
+      lua_pushnumber(L,nums[i]);
+      lua_settable(L, -3);
+    }
+
+    free(nums);
+    return 1;
+}