.table updates, .dup & .equal

8 files changed, 163 insertions, 252 deletions

diff --git a/library/lullaby/table.lua b/library/lullaby/table.lua
index 51414f7..f0f11ec 100644
--- a/library/lullaby/table.lua
+++ b/library/lullaby/table.lua
@@ -1,6 +1,6 @@
 ---@meta
 
----to be rewritten
+---to be mostly rewritten
 ---@class lullaby.table
 local table = {}
 
@@ -15,6 +15,23 @@ local table = {}
 ---@return string[]
 function table.split(haystack, search, skip) end
 
+---compares 2 tables recursivley
+---@param A any[]
+---@param B any[]
+---@param depth integer? max depth to search, defaults to -1
+---@return boolean
+function table.equal(A, B, depth) end
+
+---clones table recursivley
+---@param table any[]
+---@return value[]
+function table.dup(table) end
+
+---gets table len, useful for key,value tables
+---@param table any[]
+---@return integer
+function table.len(table) end
+
 ---greatest, least
 ---@deprecated
 ---@param array number[]
@@ -40,33 +57,4 @@ function table.bubblesort(array) end
 ---@param array number[]
 function table.heapsort(array) end
 
----least, greatest
----@deprecated
----@param array integer[]
-function table.countintsort(array) end
-
----dont use this lol
----@deprecated
----greatest, least
----@param array number[]
-function table.miraclesort(array) end
-
----dont use this lol
----@deprecated
----greatest, least
----@param array number[]
-function table.stalinsort(array) end
-
----dont use this lol
----@deprecated
----greatest, least
----@param array number[]
-function table.slowsort(array) end
-
----dont use this lol
----@deprecated
----greatest, least
----@param array number[]
-function table.bogosort(array) end
-
 return table
diff --git a/src/lua.c b/src/lua.c
index 3accdb4..f60fba5 100644
--- a/src/lua.c
+++ b/src/lua.c
@@ -13,18 +13,6 @@ int luaI_nothing(lua_State* L){
   return 0;

 }

 

-void* __malloc_(size_t N){

-  printf("hi");

-  malloc_count++;

-  return (malloc)(N);

-}

-

-void __free_(void* p){

-  malloc_count--;

-  printf("%i\n",malloc_count);

-  return (free)(p);

-}

-

 int luaI_iserror(lua_State* L){

   if(lua_gettop(L) < 3) return 0;

   return lua_type(L, -3) == LUA_TNIL &&

@@ -172,10 +160,6 @@ int writer(lua_State *L, const void* p, size_t sz, void* ud){
   return 0;

 }

 

-enum table_cache {

-  CACHE_HIT, CACHE_MISS

-};

-

 enum table_cache table_cache(lua_State* L, char* key, int index){

   lua_getfield(L, LUA_REGISTRYINDEX, key);

   if(lua_type(L, -1) == LUA_TNIL){

diff --git a/src/lua.h b/src/lua.h
index 1e45242..da65101 100644
--- a/src/lua.h
+++ b/src/lua.h
@@ -17,14 +17,17 @@ enum deep_copy_flags {
   STRIP_GC = (1 << 5),

   IS_UPVALUE = (1 << 6),

 };

+

+enum table_cache {

+  CACHE_HIT, CACHE_MISS

+};

 #endif 

 

 #ifndef GIT_COMMIT

 #define GIT_COMMIT "unknown"

 #endif

 

-void* __malloc_(size_t);

-void __free_(void*);

+enum table_cache table_cache(lua_State* L, char* key, int index);

 

 void luaI_deepcopy(lua_State* src, lua_State* dest, enum deep_copy_flags);

 void luaI_deepcopy2(lua_State* src, lua_State* dest);

@@ -108,6 +111,10 @@ extern int _print_errors;
 

 int writer(lua_State*, const void*, size_t, void*);

 

+#if LUA_VERSION_NUM != 501

+  #define lua_equal(L, A, B) lua_compare(L, A, B, LUA_OPEQ)

+#endif

+

 #if LUA_VERSION_NUM == 504

     #define lua_objlen lua_rawlen

 

diff --git a/src/sort.c b/src/sort.c
index 4462160..83fd0da 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -245,182 +245,8 @@ int l_bubblesort(lua_State* L) {
   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;
-}
diff --git a/src/sort.h b/src/sort.h
index e59cd4e..2b2efee 100644
--- a/src/sort.h
+++ b/src/sort.h
@@ -7,13 +7,3 @@ int l_mergesort(lua_State*);    //[double+int] -> arr[N] (greatest -> least)
 int l_shellsort(lua_State*);    //[double+int] -> arr[N] (greatest -> least)
 int l_bubblesort(lua_State*);   //[double+int] -> arr[N] (greatest -> least)
 int l_heapsort(lua_State*);     //[double+int] -> arr[N] (greatest -> least)
-
-//non-comparison sorts
-//good for large arrays filled with small values
-int l_countingsort(lua_State*); //[int] (arr[N] >= 0) -> arr[N] (least -> greatest)
-
-//esoteric sorts
-int l_miraclesort(lua_State*);  //[double+int] -> arr[-∞<=N<=∞] (greatest -> least)
-int l_stalinsort(lua_State*);   //[double+int] -> arr[?<=N] (greatest -> least)
-int l_slowsort(lua_State*);     //[double+int] -> arr[N] (greatest -> least)
-int l_bogosort(lua_State*);     //[double+int] -> arr[N] (greatest -> least)
diff --git a/src/table.c b/src/table.c
index bf14892..f5bdd5d 100644
--- a/src/table.c
+++ b/src/table.c
@@ -3,6 +3,99 @@
 #include <string.h>
 #include <stdint.h>
 
+void value_clone_req(lua_State* L){
+  int idx = lua_gettop(L);
+
+  if(lua_type(L, idx) == LUA_TTABLE){
+    char* key = calloc(sizeof* key, 50);
+    sprintf(key, "clone-%p", lua_topointer(L, idx));
+    lua_newtable(L);
+    int nidx = lua_gettop(L);
+
+    if(table_cache(L, key, nidx) == CACHE_HIT){
+      free(key);
+      return;
+    }
+    free(key);
+
+    lua_pushnil(L);
+    for(;lua_next(L, idx);){
+      value_clone_req(L);
+      lua_pushvalue(L, -3);
+      lua_pushvalue(L, -2);
+      lua_settable(L, nidx);
+      lua_pop(L, 2);
+    }
+  } else {
+    lua_pushvalue(L, idx);
+  }
+}
+
+int l_dup(lua_State* L){
+  if(lua_gettop(L) != 1) return 0;
+
+  value_clone_req(L);
+  lua_pushvalue(L, 2);
+  return 1;
+}
+
+int req_equal(lua_State* L, int maxdepth, int currentdepth, parray_t* req_table){
+  if(maxdepth < currentdepth && maxdepth != -1)
+    return 1;
+
+  int t1 = lua_gettop(L);
+  int t2 = lua_gettop(L) - 1;
+  if(i_len(L, t1) != i_len(L, t2))
+    return 0;
+  lua_pushnil(L);
+  for(;lua_next(L, t1) != 0;){ //-3 = key, -2 = t1[key], -1 = t2[key]
+    lua_pushvalue(L, -2);
+    lua_gettable(L, t2);
+
+    if(lua_type(L, -1) != lua_type(L, -2))
+      return 0;
+
+    if(lua_type(L, -1) == LUA_TTABLE){
+      const void* p = lua_topointer(L, -2);
+      char* str = calloc(sizeof* str, 50);
+      sprintf(str, "%p", p);
+      if(parray_geti(req_table, str) == -1){
+        parray_set(req_table, str, req_table);
+        if(!req_equal(L, maxdepth, currentdepth + 1, req_table)){
+          free(str);
+          return 0;
+        }
+      }
+      free(str);
+    } else {
+      if(!lua_equal(L, -2, -1))
+        return 0;
+    }
+
+    lua_pop(L, 2);
+  }
+  return 1;
+}
+
+int l_equal(lua_State* L){
+  if(lua_gettop(L) <= 1){
+    lua_pushboolean(L, 1);
+    return 1;
+  }
+
+  luaL_checktype(L, 1, LUA_TTABLE);
+  luaL_checktype(L, 2, LUA_TTABLE);
+  int64_t depth = -1;
+  if(lua_gettop(L) >= 3) depth = luaL_checknumber(L, 3);
+  lua_settop(L, 2);
+
+  parray_t* p = parray_init();
+  lua_pushboolean(L, req_equal(L, depth, 0, p));
+  parray_lclear(p);
+
+  return 1;
+}
+
 int l_split(lua_State* L){
   size_t str_len = 0;
   size_t search_len = 0;
@@ -59,6 +152,7 @@ uint64_t i_len(lua_State* L, int pos){
   }
   return i;
 }
+
 int l_len(lua_State* L) {
   luaL_checktype(L, 1, LUA_TTABLE);    
   lua_pushnumber(L,i_len(L,1));
@@ -84,7 +178,7 @@ int l_reverse(lua_State* L) {
   return 1;
 }
 
-int l_greatest(lua_State* L) {
+int l_max(lua_State* L) {
   luaL_checktype(L, 1, LUA_TTABLE);
   size_t len = lua_objlen(L,1);
   int touched = 0;
@@ -104,7 +198,7 @@ int l_greatest(lua_State* L) {
   return 1;
 }
 
-int l_least(lua_State* L) {
+int l_min(lua_State* L) {
   luaL_checktype(L, 1, LUA_TTABLE);
   size_t len = lua_objlen(L,1);
   int touched = 0;
diff --git a/src/table.h b/src/table.h
index 6d872c3..b114cd2 100644
--- a/src/table.h
+++ b/src/table.h
@@ -9,8 +9,8 @@ uint64_t i_len(lua_State*,int);
 
 int l_len(lua_State*);          //[double+int] -> i
 int l_reverse(lua_State*);      //[double+int] -> arr[N]
-int l_greatest(lua_State*);     //[double+int] -> i
-int l_least(lua_State*);        //[double+int] -> i
+int l_max(lua_State*);     //[double+int] -> i
+int l_min(lua_State*);        //[double+int] -> i
 int l_shuffle(lua_State*);      //[double+int] -> arr[N]
 int l_sum(lua_State*);      //[double+int] -> i
 
@@ -21,35 +21,35 @@ int l_to_char_array(lua_State*);
 
 int l_unpack(lua_State*);
 int l_split(lua_State*);
+int l_equal(lua_State*);
+int l_dup(lua_State*);
 
 #define clean_lullaby_table luaI_nothing
+
+#warning "docs needed here"
 static const luaL_Reg table_function_list [] = {
   {"len",l_len},
-  {"reverse",l_reverse},
-  {"greatest",l_greatest},
-  {"least",l_least},
-  {"shuffle",l_shuffle},
-  {"sum",l_sum},
+  {"reverse",l_reverse}, //no docs
+  {"max",l_max}, //no docs
+  {"min",l_min}, //no docs
+  {"shuffle",l_shuffle}, //no docs
+  {"sum",l_sum}, //no docs
   {"split",l_split},
-  {"to_char_array", l_to_char_array},
+  {"to_char_array", l_to_char_array}, //no docs
 
-  {"index",l_indexof},
-  {"sindex",l_sindexof},
+  {"index",l_indexof}, //no docs
+  {"sindex",l_sindexof}, //no docs
 
+  //updates these and the functions
   {"quicksort",l_quicksort},
   {"mergesort",l_mergesort},
   {"shellsort",l_shellsort},
   {"bubblesort",l_bubblesort},
   {"heapsort",l_heapsort},
 
-  {"countingsort",l_countingsort},
-
-  {"miraclesort",l_miraclesort},
-  {"stalinsort",l_stalinsort},
-  {"slowsort",l_slowsort},
-  {"bogosort",l_bogosort},
-
-  {"unpack", l_unpack},
+  {"unpack", l_unpack}, //no docs
+  {"equal", l_equal},
+  {"dup", l_dup},
 
   {NULL,NULL}
 };
diff --git a/tests/units/sort.lua b/tests/units/sort.lua
new file mode 100644
index 0000000..343f65e
--- /dev/null
+++ b/tests/units/sort.lua
@@ -0,0 +1,22 @@
+local input = {}
+local len = 500
+local max = 9999
+
+for i=1,len do
+  table.insert(input, math.random(-max, max))
+end
+
+local a = llby.table.dup(input)
+local b = llby.table.dup(input)
+local c = llby.table.dup(input)
+local d = llby.table.dup(input)
+local e = llby.table.dup(input)
+
+llby.table.quicksort(a)
+llby.table.bubblesort(b)
+llby.table.heapsort(c)
+llby.table.shellsort(d)
+llby.table.mergesort(e)
+
+return llby.table.equal(a, b) and llby.table.equal(b, c) and
+  llby.table.equal(c, d) and llby.table.equal(d, e)