Add algorithm functions (swaps/sorting/partioning/heaps)

1 files changed, 154 insertions, 0 deletions

diff --git a/include/bh/algo.h b/include/bh/algo.h
new file mode 100644
index 0000000..9beae6f
--- /dev/null
+++ b/include/bh/algo.h
@@ -0,0 +1,154 @@
+#ifndef BHLIB_ALGO_H
+#define BHLIB_ALGO_H
+
+#include "bh.h"
+
+/**
+ * @brief   Swap two elements.
+ *
+ * @param   lhs     Pointer to the first element
+ * @param   rhs     Pointer to the second element
+ * @param   size    Element size
+ */
+void bh_swap(void *lhs,
+             void *rhs,
+             size_t size);
+
+/**
+ * @brief   Partition the array.
+ *
+ * @param   pivot   Pointer to the pivot element
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ *
+ * @return  Pointer to the first element that are greater-or-equal to pivot
+ *          element.
+ *
+ * @warning Pivot element can be an element of the partitioned array itself.
+ */
+void *bh_partition(void *pivot,
+                   void *array,
+                   size_t size,
+                   size_t element,
+                   bh_equal_cb_t equal);
+
+/**
+ * @brief   Sort the array.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ */
+void bh_sort(void *array,
+             size_t size,
+             size_t element,
+             bh_equal_cb_t equal);
+
+/**
+ * @brief   Sort the array using insert sort.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ */
+void bh_sort_insert(void *array,
+                    size_t size,
+                    size_t element,
+                    bh_equal_cb_t equal);
+
+/**
+ * @brief   Sort the array using shell sort.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ */
+void bh_sort_shell(void *array,
+                   size_t size,
+                   size_t element,
+                   bh_equal_cb_t equal);
+
+/**
+ * @brief   Sort the array using intro sort.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ */
+void bh_sort_intro(void *array,
+                   size_t size,
+                   size_t element,
+                   bh_equal_cb_t equal);
+
+/**
+ * @brief   Sort the array using heap sort.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ */
+void bh_sort_heap(void *array,
+                  size_t size,
+                  size_t element,
+                  bh_equal_cb_t equal);
+
+/**
+ * @brief   Make heap from the array.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ *
+ * @sa bh_heap_remove, bh_heap_insert
+ */
+void bh_heap_make(void *array,
+                  size_t size,
+                  size_t element,
+                  bh_equal_cb_t equal);
+
+/**
+ * @brief   Remove element from the heap.
+ *
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ *
+ * @warning Removed element is placed at the end of the array
+ *
+ * @sa bh_heap_make, bh_heap_remove
+ */
+void bh_heap_remove(void *array,
+                    size_t size,
+                    size_t element,
+                    bh_equal_cb_t equal);
+
+/**
+ * @brief   Insert element to the heap.
+ *
+ * @param   value   Pointer to the inserted value (optional)
+ * @param   array   Pointer to the array
+ * @param   size    Array size
+ * @param   element Element size
+ * @param   equal   Equal/compare function
+ *
+ * @warning If value is not passed, function assumes inserted element
+ *          is already placed at the end of the array.
+ *
+ * @sa bh_heap_make, bh_heap_remove
+ */
+void bh_heap_insert(void *value,
+                    void *array,
+                    size_t size,
+                    size_t element,
+                    bh_equal_cb_t equal);
+
+#endif /* BHLIB_ALGO_H */