#include <cstdlib>
#include <cstdio>
#include <stdio.h>
#include "funciones.h"
#include <iostream>
using namespace std;

int main(int argc, char** argv) {

    freopen("imgmini1_3x4.txt", "r", stdin);
    int* image;
    int** sparse, **sparse2, **sparse3, **sparse4, **sparse5;

    image = readImg(3, 4);

    writeImg(image, 3, 4);

    sparse = toSparseImg(image, 3, 4);
    for (int i = 0; i < 3; i++) {
        if (sparse[i] == NULL)
            cout << "NULL" << endl;
        else {
            for (int j = 0; sparse[i][j] != -1; j++) {
                cout << sparse[i][j];
            }
            cout << endl;
        }
    }
    writeSparseImg(sparse, 3, 4);
    cout << endl;

    sparse2 = bitwiseNOT_sprImg(sparse, 3, 4);
    for (int i = 0; i < 3; i++) {
        if (sparse2[i] == NULL)
            cout << "NULL" << endl;
        else {
            for (int j = 0; sparse2[i][j] != -1; j++) {
                cout << sparse2[i][j];
            }
            cout << endl;
        }
    }
    writeSparseImg(sparse2, 3, 4);
    cout << endl;

    sparse3 = bitwiseAND_sprImg(sparse, sparse2, 3, 4, 3, 4);
    writeSparseImg(sparse3, 3, 4);

    int a = 3;
    int b = 4;
    sparse4 = trim_sprImg(sparse, a, b);
    writeSparseImg(sparse4, a, b);

    a = 3;
    b = 4;
    sparse5 = scaleUP_sprImg(sparse, a,b,2);
    writeSparseImg(sparse5, a, b);

    return 0;
}
-----------------------//sparce.cpp---------------------------

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include "funciones.h"
#define INC 5

using namespace std;

int* readImg(int height, int width) {
    int * image = new int[height * width + 1];
    char dato;
    for (int i = 0; i < height * width; i++) {
        cin >> dato;
        if (dato == '0')
            image[i] = 0;
        else
            image[i] = 1;
    }
    image[height * width + 1] = -1;
    return image;
}

void writeImg(int* image, int height, int width) {
    int cont = 0;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (image[cont] == 0)
                cout << ". ";
            else
                cout << "# ";
            cont++;
        }
        cout << endl;
    }
}

void incrementar(int* &lista, int numElem) {
    if (lista == NULL) {
        lista = new int[INC + 1];
        for (int i = 0; i <= INC; i++) {
            lista[i] = -1;
        }
    } else {
        int* listaAux = new int[numElem + INC + 1];
        for (int i = 0; i < numElem; i++) {
            listaAux[i] = lista[i];
        }
        for (int i = numElem; i <= numElem + INC; i++) {
            listaAux[i] = -1;
        }
        delete [] lista;
        lista = listaAux;
    }
}

void agregarDato(int * & lista, int dato) {
    if (lista == NULL) {
        incrementar(lista, INC);
        lista[0] = dato;
        lista[1] = -1;
    } else {
        int numElem = 0;
        for (int i = 0; lista[i] != -1; i++, numElem++);
        if (numElem % INC == 0)
            incrementar(lista, numElem);
        lista[numElem] = dato;
        lista[numElem + 1] = -1;
    }
}

int** toSparseImg(int* image, int height, int width) {
    int** sparse = new int*[height + 1];
    for (int i = 0; i <= height; i++) {
        sparse[i] = NULL;
    }
    int cont = 0;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (image[cont] == 1)
                agregarDato(sparse[i], j);
            cont++;
        }
        cout << endl;
    }
    return sparse;
}

void writeSparseImg(int** sparseImg, int height, int width) {
    for (int i = 0; i < height; i++) {
        if (sparseImg[i] != NULL) {
            int * aux = sparseImg[i];
            int cont = 0;
            for (int j = 0; j < width; j++) {
                if (j == aux[cont]) {
                    cout << setw(2) << '#';
                    cont++;
                } else cout << setw(2) << '.';
            }
        } else {
            for (int j = 0; j < width; j++) cout << setw(2) << '.';
        }
        cout << endl;
    }
}

bool esta(int* lista, int dato) {
    bool esta = false;
    for (int i = 0; lista[i] != -1; i++) {
        if (lista[i] == dato) {
            esta = true;
            break;
        }
    }
    return esta;
}

int ** bitwiseNOT_sprImg(int** sparseImg, int height, int width) {
    int** sparse = new int*[height + 1];
    for (int i = 0; i <= height; i++)
        sparse[i] = NULL;

    for (int i = 0; i < height; i++) {
        if (sparseImg[i] == NULL)
            for (int j = 0; j < width; j++) {
                agregarDato(sparse[i], j);
            } else {
            int* aux = sparseImg[i];
            for (int j = 0; j < width; j++) {
                if (!esta(aux, j)) {
                    agregarDato(sparse[i], j);
                }
            }
        }
    }
    return sparse;
}

int ** bitwiseAND_sprImg(int ** sprImg1, int ** sprImg2, int h1, int w1, int h2, int w2){

    int max;
    if(h1 > h2) max = h1; else max = h2;
    int ** sparce = new int *[max+1];
    for(int i=0; i<= max; i++) sparce[i] = NULL;

    for(int i=0; i < max ; i++){
        if(sprImg1[i] != NULL && sprImg2[i] != NULL ){
            int * aux1 = sprImg1[i];
            int * aux2 = sprImg2[i];
            for(int j=0; aux1[j] != -1; j++){
                if(esta(aux2, aux1[j])){
                    agregarDato(sparce[i], j);
                }
            }
        }
    }
    return sparce;
}

int **trim_sprImg(int** sparseImg, int &height, int &width){
    int cant = 0;
    for (int i = 0; i < height; i++)
        if(sparseImg[i] != NULL) cant++;

    int ** trim = new int*[cant+1];
    for (int i = 0; i <= cant; i++) trim[i] = NULL;


    int cont = 0;

    int max = 0;
    for (int i = 0; i < height; i++) {
        if(sparseImg[i] != NULL){
            int *aux = sparseImg[i];
            width = 0;
            for (int j = 0; aux[j] != -1; j++) {
                agregarDato(trim[cont], aux[j]-1); //Para
                width++;
            }
            if (width > max) max = width;
            cont++;
        }
    }
    width = max;
    height = cant;
    return trim;
}

int** scaleUP_sprImg(int ** sparceImg, int & height, int & width, int scale){
    int cant = height*2;
    int ** dupli = new int*[cant + 1];
    for(int i=0; i<= cant; i++) dupli[i] = NULL;

    for(int i=0; i < cant; i+=2){
        if(sparceImg[i/2] == NULL)
            dupli[i+1] = dupli[i];
        if(sparceImg[i/2] != NULL){
            int * aux = sparceImg[i/2];
            for(int j=0; aux[j] != -1; j++){
                agregarDato(dupli[i], aux[j]*2);
                agregarDato(dupli[i], (aux[j]*2)+1);
            }
            dupli[i+1] = dupli[i];
        }
    }
    height = height*2;
    width = width*2;
    return dupli;
}
//sparse.h
#ifndef FUNCIONES_H
#define FUNCIONES_H

int* readImg(int, int);
void writeImg(int*, int, int);
int ** toSparseImg(int*, int, int);
void writeSparseImg(int** , int , int );
int ** bitwiseNOT_sprImg(int**, int, int);
int ** bitwiseAND_sprImg(int **, int **, int, int, int, int);
int ** trim_sprImg(int**, int &, int&);
int **scaleUP_sprImg(int**, int &, int&, int);

#endif /* FUNCIONES_H */