Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <iostream>
- #include <vector>
- #include <fstream>
- #define SUCCESS (0)
- #define NOT_FOUND (404)
- #define FOUND (-404)
- #define NEWLINE std::cout << std::endl;
- // Print matrix to stdout.
- template <typename type>
- void printmat(std::vector< std::vector<type> >&);
- // Read matrix from stdin.
- template <typename type>
- void readmat(std::vector< std::vector<type> >&);
- // Read matrix from a given fstream.
- template <typename type>
- void readmat(std::vector< std::vector<type> >&, std::fstream&);
- // Binary search a matrix.
- template <typename type>
- int binS_matrix(std::vector< std::vector<type> >&, const type);
- int main()
- {
- std::fstream input;
- int rows, cols;
- /* Open file for reading. */
- input.open("matrix.txt", std::ios::in);
- /* Read the number of lines and collums */
- input >> rows;
- input >> cols;
- if (input.peek() == EOF) {
- std::cerr << "[Error] Not enough input."; NEWLINE;
- exit(1);
- }
- // The MATRIX
- std::vector< std::vector<int> > mat(rows, std::vector<int>(cols));
- // Read the matrix from file.
- readmat(mat, input);
- input.close();
- int search_value;
- std::cout << "Search for: ";
- std::cin >> search_value;
- if ( binS_matrix(mat, search_value) == FOUND ) {
- std::cout << "Found " << search_value << "!";
- }
- else {
- std::cout << "Not found " << search_value << ".";
- }
- NEWLINE;
- return SUCCESS;
- }
- template <typename type>
- int binS_matrix(std::vector< std::vector<type> >& mat, const type search_value)
- {
- /* [Note] Could use auto. */
- typename std::vector< std::vector<type> >::iterator row;
- typename std::vector<type>::iterator col;
- // Variable used to shrink the vector horizontally.
- unsigned int shrink_H = 0;
- for (
- row = mat.begin();
- row < mat.end();
- ++row
- )
- {
- for(
- col = row->end() - 1 - shrink_H;
- col >= row->begin();
- --col
- )
- {
- if (search_value > *col) {
- break; // skip current line = verical shrink
- }
- else if (search_value < *col) {
- ++shrink_H;
- }
- else {
- return FOUND; // found!
- }
- }
- }
- /* Not found. */
- return NOT_FOUND;
- }
- template <typename type>
- void printmat(std::vector< std::vector<type> >& mat)
- {
- NEWLINE;
- for (auto& row : mat) {
- for (auto& elem : row) {
- std::cout << elem << " ";
- }
- NEWLINE;
- }
- NEWLINE;
- }
- template <typename type>
- void readmat(std::vector< std::vector<type> >& mat)
- {
- for (auto& row : mat) {
- for (auto& elem : row)
- {
- std::cin >> elem;
- }
- }
- }
- template <typename type>
- void readmat(std::vector< std::vector<type> >& mat, std::fstream& input)
- {
- for (auto& row : mat) {
- for (auto& elem : row)
- {
- input >> elem;
- // C++ makes sense! :PPP
- if (input.peek() == EOF) {
- std::cerr << "[Error] Not enough input."; NEWLINE;
- exit(1);
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement