ronantakizawa/codereview-bench huggingface dataset:
Repository: TheAlgorithms/C-Plus-Plus
File: sorting/quick_sort_iterative.cpp (C++)

Code before:
/**
 * @file
 * @brief Quick Sort without recursion. This method uses the stack instead.
 * Both recursive and iterative implementations have O(n log n) best case
 * and O(n^2) worst case.
 * @details
 * https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
 * https://en.wikipedia.org/wiki/Quicksort
 * https://www.geeksforgeeks.org/iterative-quick-sort/
 * @author [Sebe324](https://github.com/sebe324)
 */

#include <iostream> /// for std::cout
#include <vector> /// for std::vector
#include <stack> /// for std::stack
#include <algorithm> ///for std::is_sorted
#include <cassert> /// for assert

/**
 * @brief The partition function sorts the array from
 * start to end and uses the last element as the pivot.
 * @param arr the array to be sorted
 * @param start starting index
 * @param end ending index
 * @return int next index of the pivot
 */
int partition(std::vector<int> &arr, int start, int end)
{
    int pivot = arr[end];
    int index = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            std::swap(arr[++index], arr[j]);
        }
    }

    std::swap(arr[index + 1], arr[end]);
    return index + 1;
}


Review comment (suggestion):
```suggestion
#include <algorithm> /// for std::is_sorted
```

Code after:
/**
 * @file
 * @brief Quick Sort without recursion. This method uses the stack instead.
 * Both recursive and iterative implementations have O(n log n) best case
 * and O(n^2) worst case.
 * @details
 * https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
 * https://en.wikipedia.org/wiki/Quicksort
 * https://www.geeksforgeeks.org/iterative-quick-sort/
 * @author [Sebe324](https://github.com/sebe324)
 */

#include <iostream> /// for std::cout
#include <vector> /// for std::vector
#include <stack> /// for std::stack
#include <algorithm> /// for std::is_sorted
#include <cassert> /// for assert


/**
 * @namespace sorting
 * @brief Sorting algorithms
 */
namespace sorting {
/**
 * @brief The partition function sorts the array from
 * start to end and uses the last element as the pivot.
 * @param arr the array to be sorted
 * @param start starting index
 * @param end ending index
 * @return int next index of the pivot
 */
int partition(std::vector<int> &arr, int start, int end)
{
    int pivot = arr[end];
    int index = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            std::swap(arr[++index], arr[j]);
        }
Repository: TheAlgorithms/C-Plus-Plus
File: sorting/quick_sort_iterative.cpp (C++)

Code before:
/**
 * @file
 * @brief Quick Sort without recursion. This method uses the stack instead.
 * Both recursive and iterative implementations have O(n log n) best case
 * and O(n^2) worst case.
 * @details
 * https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
 * https://en.wikipedia.org/wiki/Quicksort
 * https://www.geeksforgeeks.org/iterative-quick-sort/
 * @author [Sebe324](https://github.com/sebe324)
 */

#include <iostream> /// for std::cout
#include <vector> /// for std::vector
#include <stack> /// for std::stack
#include <algorithm> /// for std::is_sorted
#include <cassert> /// for assert

/**
 * @brief The partition function sorts the array from
 * start to end and uses the last element as the pivot.
 * @param arr the array to be sorted
 * @param start starting index
 * @param end ending index
 * @return int next index of the pivot
 */
int partition(std::vector<int> &arr, int start, int end)
{
    int pivot = arr[end];
    int index = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            std::swap(arr[++index], arr[j]);
        }
    }

    std::swap(arr[index + 1], arr[end]);
    return index + 1;
}

/**
 * @brief The main sorting function

Review comment (suggestion):
```suggestion


/**
 * @namespace sorting
 * @brief Sorting algorithms
 */
namespace sorting {
```
should be inside sorting namespace

Code after:
/**
 * @file
 * @brief Quick Sort without recursion. This method uses the stack instead.
 * Both recursive and iterative implementations have O(n log n) best case
 * and O(n^2) worst case.
 * @details
 * https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive
 * https://en.wikipedia.org/wiki/Quicksort
 * https://www.geeksforgeeks.org/iterative-quick-sort/
 * @author [Sebe324](https://github.com/sebe324)
 */

#include <iostream> /// for std::cout
#include <vector> /// for std::vector
#include <stack> /// for std::stack
#include <algorithm> /// for std::is_sorted
#include <cassert> /// for assert


/**
 * @namespace sorting
 * @brief Sorting algorithms
 */
namespace sorting {
/**
 * @brief The partition function sorts the array from
 * start to end and uses the last element as the pivot.
 * @param arr the array to be sorted
 * @param start starting index
 * @param end ending index
 * @return int next index of the pivot
 */
int partition(std::vector<int> &arr, int start, int end)
{
    int pivot = arr[end];
    int index = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            std::swap(arr[++index], arr[j]);
        }
    }
Repository: TheAlgorithms/C-Plus-Plus
File: sorting/tim_sort.cpp (C++)

Code before:
// utility function to print the Array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d  ", arr[i]);
    std::cout << std::endl;
}

/**
 * @brief self-test implementation 
 * @returns void
 */
void tests() {
    // Case: array of length 65
    constexpr int N = 65;
    int arr[N];

    std::iota(arr, arr + N, 0);
    std::reverse(arr, arr + N);
    assert(!std::is_sorted(arr, arr + N));

    timSort(arr, N);
    assert(std::is_sorted(arr, arr + N));
}

// Driver program to test above function
int main() {
    tests();

    int arr[] = {5, 21, 7, 23, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Given Array is\n");
    printArray(arr, n);

    timSort(arr, n);

    printf("After Sorting Array is\n");
    printArray(arr, n);
    return 0;
}


Review comment (suggestion):
```suggestion
    tests(); // run self test implementations
```


Code after:
// utility function to print the Array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d  ", arr[i]);
    std::cout << std::endl;
}

/**
 * @brief self-test implementation 
 * @returns void
 */
void tests() {
    // Case: array of length 65
    constexpr int N = 65;
    int arr[N];

    std::iota(arr, arr + N, 0);
    std::reverse(arr, arr + N);
    assert(!std::is_sorted(arr, arr + N));

    timSort(arr, N);
    assert(std::is_sorted(arr, arr + N));
}

// Driver program to test above function
int main() {
    tests(); // run self test implementations

    int arr[] = {5, 21, 7, 23, 19};
    const int n = sizeof(arr) / sizeof(arr[0]);
    printf("Given Array is\n");
    printArray(arr, n);

    timSort(arr, n);

    printf("After Sorting Array is\n");
    printArray(arr, n);
    return 0;
}
Repository: TheAlgorithms/C-Plus-Plus
File: sorting/tim_sort.cpp (C++)

Code before:
    for (int i = 0; i < n; i++) printf("%d  ", arr[i]);
    std::cout << std::endl;
}

/**
 * @brief self-test implementation 
 * @returns void
 */
void tests() {
    // Case: array of length 65
    constexpr int N = 65;
    int arr[N];

    std::iota(arr, arr + N, 0);
    std::reverse(arr, arr + N);
    assert(!std::is_sorted(arr, arr + N));

    timSort(arr, N);
    assert(std::is_sorted(arr, arr + N));
}

// Driver program to test above function
int main() {
    tests(); // run self test implementations

    int arr[] = {5, 21, 7, 23, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Given Array is\n");
    printArray(arr, n);

    timSort(arr, n);

    printf("After Sorting Array is\n");
    printArray(arr, n);
    return 0;
}


Review comment (suggestion):
you could remove the rest of main so only what remains is
```cpp
int main() {
   tests(); // run self test implementations
   return 0;
}
```

Code after:
    for (int i = 0; i < n; i++) printf("%d  ", arr[i]);
    std::cout << std::endl;
}

/**
 * @brief self-test implementation 
 * @returns void
 */
void tests() {
    // Case: array of length 65
    constexpr int N = 65;
    int arr[N];

    std::iota(arr, arr + N, 0);
    std::reverse(arr, arr + N);
    assert(!std::is_sorted(arr, arr + N));

    timSort(arr, N);
    assert(std::is_sorted(arr, arr + N));
}

// Driver program to test above function
int main() {
    tests(); // run self test implementations

    int arr[] = {5, 21, 7, 23, 19};
    const int n = sizeof(arr) / sizeof(arr[0]);
    printf("Given Array is\n");
    printArray(arr, n);

    timSort(arr, n);

    printf("After Sorting Array is\n");
    printArray(arr, n);
    return 0;
}
Repository: TheAlgorithms/C-Plus-Plus
File: strings/knuth_morris_pratt.cpp (C++)

Code before:
 * @returns `std::string::npos` if not found
 */
size_t kmp(const std::string &pattern, const std::string &text) {
    if (pattern.empty()) {
        return 0;
    }
    std::vector<size_t> failure = getFailureArray(pattern);
    size_t text_length = text.size();
    size_t pattern_length = pattern.size();
    size_t k = 0;
    for (size_t j = 0; j < text_length; j++) {
        while (k != std::string::npos && pattern[k] != text[j]) {
            k = failure[k];
        }
        if (++k == pattern_length) {
            return j - k + 1;
        }
    }
    return std::string::npos;
}
}  // namespace string_search

using string_search::kmp;

/**
 * @brief test KMP algorithm
 * @returns void
 */
static void tests() {
    assert(kmp("abc1abc12l", "alskfjaldsabc1abc1abc12k2") == std::string::npos);
    assert(kmp("bca", "abcabc") == 1);
    assert(kmp("World", "helloWorld") == 5);
    assert(kmp("c++", "his_is_c++") == 7);
    assert(kmp("happy", "happy_coding") == 0);
    assert(kmp("", "pattern is empty") == 0);

    // this lets the user know that the tests have passed
    std::cout << "All KMP algorithm tests have successfully passed!\n";
}

/*
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    tests();
    return 0;
}


Review comment (suggestion):
```suggestion
 * @brief self-test implementations
```
doxygen reasons

Code after:
    if (pattern.empty()) {
        return 0;
    }
    std::vector<size_t> failure = getFailureArray(pattern);
    size_t text_length = text.size();
    size_t pattern_length = pattern.size();
    size_t k = 0;
    for (size_t j = 0; j < text_length; j++) {
        while (k != std::string::npos && pattern[k] != text[j]) {
            k = failure[k];
        }
        if (++k == pattern_length) {
            return j - k + 1;
        }
    }
    return std::string::npos;
}
}  // namespace string_search

using string_search::kmp;

/**
 * @brief self-test implementations
 * @returns void
 */
static void tests() {
    assert(kmp("abc1abc12l", "alskfjaldsabc1abc1abc12k2") == std::string::npos);
    assert(kmp("bca", "abcabc") == 1);
    assert(kmp("World", "helloWorld") == 5);
    assert(kmp("c++", "his_is_c++") == 7);
    assert(kmp("happy", "happy_coding") == 0);
    assert(kmp("", "pattern is empty") == 0);

    // this lets the user know that the tests have passed
    std::cout << "All KMP algorithm tests have successfully passed!\n";
}

/*
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    tests();
    return 0;
}
Repository: TheAlgorithms/C-Plus-Plus
File: dynamic_programming/trapped_rainwater.cpp (C++)

Code before:
/**
 * @file
 * @brief Implementation of the [Trapped Rainwater
 * Problem](https://www.geeksforgeeks.org/trapping-rain-water/)
 * @details
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <vector>     /// For vector container

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
int trappedRainwater(const std::vector<int>& heights) {
    int n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<int> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];

Review comment (security):
```suggestion
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
```

Code after:
/**
 * @file
 * @brief Implementation of the [Trapped Rainwater
 * Problem](https://www.geeksforgeeks.org/trapping-rain-water/)
 * @details
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <cstdint>    /// For integral typedefs
#include <vector>     /// For std::vector

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
uint32_t trappedRainwater(const std::vector<uint32_t>& heights) {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<uint32_t> leftMax(n), rightMax(n);
Repository: TheAlgorithms/C-Plus-Plus
File: dynamic_programming/trapped_rainwater.cpp (C++)

Code before:
/**
 * @file
 * @brief Implementation of the [Trapped Rainwater
 * Problem](https://www.geeksforgeeks.org/trapping-rain-water/)
 * @details
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <vector>     /// For vector container

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
int trappedRainwater(const std::vector<int>& heights) {
    int n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<int> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (int i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
    }

    // Calculate the maximum height of wall to the right of each wall

Review comment (suggestion):
```suggestion
#include <vector>     /// For std::vector
```

Code after:
/**
 * @file
 * @brief Implementation of the [Trapped Rainwater
 * Problem](https://www.geeksforgeeks.org/trapping-rain-water/)
 * @details
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <cstdint>    /// For integral typedefs
#include <vector>     /// For std::vector

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
uint32_t trappedRainwater(const std::vector<uint32_t>& heights) {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<uint32_t> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (std::size_t i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
Repository: TheAlgorithms/C-Plus-Plus
File: dynamic_programming/trapped_rainwater.cpp (C++)

Code before:
/**
 * @file
 * @brief Implementation of the [Trapped Rainwater
 * Problem](https://www.geeksforgeeks.org/trapping-rain-water/)
 * @details
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <vector>     /// For std::vector

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
unsigned int trappedRainwater(const std::vector<unsigned int>& heights) {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<unsigned int> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (std::size_t i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
    }

    // Calculate the maximum height of wall to the right of each wall

Review comment (suggestion):
```suggestion
#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <vector>     /// For std::vector
#include <cstdint>    /// For integral typedefs
```

Code after:
/**
 * @file
 * @brief Implementation of the [Trapped Rainwater
 * Problem](https://www.geeksforgeeks.org/trapping-rain-water/)
 * @details
 * This implementation calculates the amount of rainwater that can be trapped
 * between walls represented by an array of heights.
 * @author [SOZEL](https://github.com/TruongNhanNguyen)
 */

#include <algorithm>  /// For std::min and std::max
#include <cassert>    /// For assert
#include <cstddef>    /// For std::size_t
#include <cstdint>    /// For integral typedefs
#include <vector>     /// For std::vector

/*
 * @namespace
 * @brief Dynamic Programming Algorithms
 */
namespace dynamic_programming {
/**
 * @brief Function to calculate the trapped rainwater
 * @param heights Array representing the heights of walls
 * @return The amount of trapped rainwater
 */
uint32_t trappedRainwater(const std::vector<uint32_t>& heights) {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls

    std::vector<uint32_t> leftMax(n), rightMax(n);

    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (std::size_t i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
    }
Repository: TheAlgorithms/C-Plus-Plus
File: strings/duval.cpp (C++)

Code before:
 * @author [Amine Ghoussaini](https://github.com/aminegh20)
*/

#include <array>    ///< for std::array
#include <cassert>  ///< for assert
#include <cstddef>  ///< for std::size_t
#include <deque>    ///< for std::deque
#include <iostream> ///< for std::cout and std::endl
#include <string>   ///< for std::string
#include <vector>   ///< for std::vector

namespace string {
/**
 * @brief Find the lexicographically smallest cyclic shift of a sequence.
 * @tparam T type of the sequence
 * @param s the sequence
 * @returns the 0-indexed position of the least cyclic shift of the sequence
 */
template <typename T>
size_t duval(const T& s) {
    size_t n = s.size();
    size_t i = 0, ans = 0;
    while (i < n) {
        ans = i;
        size_t j = i + 1, k = i;
        while (j < n + n && s[j % n] >= s[k % n]) {
            if (s[k % n] < s[j % n]) {
                k = i;
            } else {
                k++;
            }
            j++;
        }
        while (i <= k) {
            i += j - k;
        }
    }
    return ans;
    // returns 0-indexed position of the least cyclic shift
}

}  // namespace string

static void test() {
    using namespace string;

    // Test 1
    std::string s1 = "abcab";
    assert(duval(s1) == 3);

    // Test 2

Review comment (suggestion):
```suggestion
        while (j < (n + n) && s[j % n] >= s[k % n]) {
```
For clarity


Code after:
 * @author [Amine Ghoussaini](https://github.com/aminegh20)
*/

#include <array>    /// for std::array
#include <cassert>  /// for assert
#include <cstddef>  /// for std::size_t
#include <deque>    /// for std::deque
#include <iostream> /// for std::cout and std::endl
#include <string>   /// for std::string
#include <vector>   /// for std::vector

/**
 * @brief string manipulation algorithms
 * @namespace
 */
namespace string {
/**
 * @brief Find the lexicographically smallest cyclic shift of a sequence.
 * @tparam T type of the sequence
 * @param s the sequence
 * @returns the 0-indexed position of the least cyclic shift of the sequence
 */
template <typename T>
size_t duval(const T& s) {
    size_t n = s.size();
    size_t i = 0, ans = 0;
    while (i < n) {
        ans = i;
        size_t j = i + 1, k = i;
        while (j < (n + n) && s[j % n] >= s[k % n]) {
            if (s[k % n] < s[j % n]) {
                k = i;
            } else {
                k++;
            }
            j++;
        }
        while (i <= k) {
            i += j - k;
        }
    }
    return ans;
    // returns 0-indexed position of the least cyclic shift
}

}  // namespace string

/**
 * @brief self test implementation
 * returns void
 */
Repository: TheAlgorithms/C-Plus-Plus
File: strings/duval.cpp (C++)

Code before:

    // Test 1
    std::string s1 = "abcab";
    assert(duval(s1) == 3);

    // Test 2
    std::string s2 = "011100";
    assert(duval(s2) == 4);

    // Test 3
    std::vector<int> v = {5, 2, 1, 3, 4};
    assert(duval(v) == 2);

    // Test 4
    std::array<int, 5> a = {1, 2, 3, 4, 5};
    assert(duval(a) == 0);

    // Test 5
    std::deque<char> d = {'a', 'z', 'c', 'a', 'b'};
    assert(duval(d) == 3);

    std::cout << "All tests passed!" << std::endl;
}

int main() {
    test();
    return 0;
}


Review comment (suggestion):
```suggestion
    test(); // run self test implementations
```


Code after:
}  // namespace string

/**
 * @brief self test implementation
 * returns void
 */
static void test() {
    using namespace string;

    // Test 1
    std::string s1 = "abcab";
    assert(duval(s1) == 3);

    // Test 2
    std::string s2 = "011100";
    assert(duval(s2) == 4);

    // Test 3
    std::vector<int> v = {5, 2, 1, 3, 4};
    assert(duval(v) == 2);

    // Test 4
    std::array<int, 5> a = {1, 2, 3, 4, 5};
    assert(duval(a) == 0);

    // Test 5
    std::deque<char> d = {'a', 'z', 'c', 'a', 'b'};
    assert(duval(d) == 3);

    // Test 6
    std::string s3;
    assert(duval(s3) == 0);

    // Test 7
    std::vector<int> v2 = {5, 2, 1, 3, -4};
    assert(duval(v2) == 4);

    std::cout << "All tests passed!" << std::endl;
}

/**
 * @brief main function
 * @returns 0 on exit
 */
int main() {
    test();  // run self test implementations
    return 0;
}