Example: Print Unique Rows using Trie in C++

// Print Unique Rows using Trie
#include <iostream>
#include <vector>
#include <memory> // For std::unique_ptr

using namespace std;

// Trie Node structure
struct TrieNode {
    unique_ptr<TrieNode> children[2]; // children[0] for '0', children[1] for '1'
    bool isEndOfRow; // Marks if a path ending at this node represents a complete row

    TrieNode() : isEndOfRow(false) {
        children[0] = nullptr;
        children[1] = nullptr;
    }
};

// Function to insert a row into the Trie and check for uniqueness
// Returns true if the row was unique (i.e., newly inserted), false otherwise
bool insert(TrieNode* root, const vector<int>& row) {
    TrieNode* curr = root;
    bool isNewRow = false; // Flag to check if we created any new nodes

    for (int bit : row) {
        if (curr->children[bit] == nullptr) {
            curr->children[bit] = make_unique<TrieNode>();
            isNewRow = true; // A new path segment was created
        }
        curr = curr->children[bit].get();
    }

    // If isNewRow is true, it means we created at least one new node,
    // making the entire path (row) unique until this point.
    // Also, if the current node's isEndOfRow was false, but now we mark it true,
    // that also signifies a unique *complete* row.
    if (!curr->isEndOfRow) {
        curr->isEndOfRow = true;
        isNewRow = true; // This specific row is now marked as complete for the first time
    }

    return isNewRow;
}

// Function to print unique rows using Trie
void printUniqueRowsTrie(const vector<vector<int>>& matrix) {
    int R = matrix.size();
    if (R == 0) return; // Handle empty matrix
    // No need for C, as vector<int> row can handle different lengths (though typical for matrices to be uniform)

    // Create the root of the Trie
    TrieNode* root = new TrieNode(); // Using raw pointer for root, manage memory with smart pointers for children

    for (const auto& row : matrix) {
        // If insert returns true, it means this row was unique
        if (insert(root, row)) {
            for (int bit : row) {
                cout << bit << " ";
            }
            cout << endl;
        }
    }
    // Clean up dynamically allocated root node
    // For simplicity in this example, manual delete for root.
    // In a full application, a smart pointer or a wrapper class for Trie would handle this.
    delete root; 
}

int main() {
    // Step 1: Define the boolean matrix
    vector<vector<int>> matrix = {
        {0, 1, 0, 0},
        {1, 0, 1, 1},
        {0, 1, 0, 0},
        {1, 1, 0, 0}
    };

    cout << "Unique rows in the matrix (using Trie):" << endl;
    // Step 2: Call the function to print unique rows using Trie
    printUniqueRowsTrie(matrix);

    // Another example matrix
    cout << "\nUnique rows for another matrix (using Trie):" << endl;
    vector<vector<int>> matrix2 = {
        {1, 1},
        {0, 1},
        {1, 1},
        {0, 0},
        {1, 0}
    };
    printUniqueRowsTrie(matrix2);

    return 0;
}