Nuts and Bolts

Nuts_and_Bolts.cpp

/**
 * class Comparator {
 *     public:
 *      int cmp(string a, string b);
 * };
 * You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
 * if "a" is bigger than "b", it will return 1, else if they are equal,
 * it will return 0, else if "a" is smaller than "b", it will return -1.
 * When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
class Solution {
    void print(vector<string> &vec, int start, int end) {
        for(int i = start; i <= end; i++) {
            cerr << vec[i] << ", ";
        }
        cerr << "|";
    }
    
    int partition(vector<string> &nuts, vector<string> &bolts, int start, int end, Comparator compare) {
        print(nuts, start, end);
        print(bolts, start, end);
        for(int i = start; i < end; i++) {
            if(compare.cmp(nuts[i], bolts[end]) == 0) {
                swap(nuts[i], nuts[end]);
                break;
            }
        }
        int leftn = start - 1;
        int leftb = start - 1;
        for(int i = 0; i <= end - 1; i++) {
            if(compare.cmp(nuts[i], bolts[end]) <= 0) {
                swap(nuts[i], nuts[leftn + 1]);
                leftn++;
            }
            if(compare.cmp(nuts[end], bolts[i]) >= 0) {
                swap(bolts[i], bolts[leftb + 1]);
                leftb++;
            }
        }
        cerr << "DEBUG: " <<leftn - start<< " " << leftb - start <<" "<<(leftn == leftb);
        swap(nuts[end], nuts[leftn + 1]);
        swap(bolts[end], bolts[leftb + 1]);
        return leftn + 1;
    }
    
    void helper(vector<string> &nuts, vector<string> &bolts, int start, int end, Comparator compare) {
        if(start >= end) {
            return; 
        }
        

        int pivotIdx = partition(nuts, bolts, start, end, compare);
        helper(nuts, bolts, start, pivotIdx - 1, compare);
        helper(nuts, bolts, pivotIdx + 1, end, compare);
    }
public:
    /**
     * @param nuts: a vector of integers
     * @param bolts: a vector of integers
     * @param compare: a instance of Comparator
     * @return: nothing
     */
    void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
        helper(nuts, bolts, 0, nuts.size() - 1, compare);
    }
};