// -*- compile-command: "g++ -g -ggdb -W -Wall -pedantic seam_carving.cpp -o seam_carving -lSDL_image" -*-

#include <iomanip>
#include <iostream> 
#include <ostream>
#include <string> 
#include <vector> 
#include <sstream>
#include <cmath>
#include <algorithm>

#include <SDL/SDL.h>

const int c_negative_energy = -255;
const int c_seam_energy = 1<<21;


////////////////////////////////////////////////////////////////////// Podstawowe typy i operacje na nich
struct Color {
    Uint8 r;
    Uint8 g;
    Uint8 b;

    bool operator== (const Color& rhs) const {
        return r == rhs.r && g == rhs.g && b == rhs.b;
    }
};

Color mix_colors(const Color& c1, const Color& c2) {
    Color result;
    result.r = (c1.r + c2.r)/2;
    result.g = (c1.g + c2.g)/2;
    result.b = (c1.b + c2.b)/2;
    return result;
}

Color mix_color_with_energy(const Color& c, int e) {
    if (e == c_negative_energy) {
        Color result;
        result.r = 255;
        result.g = 0;
        result.b = 0;
        return result;
    }
    else {
        return c;
    }
}

struct Image {
    std::vector<std::vector<Color> > data;
    std::vector<std::vector<int> > energy;
    int width;
    int height;
    size_t negative_energy_count; // liczba pikseli o ujemnej energii
};

void flip_image_vertically(Image* img) {
    for (int y = 0; y < img->height/2; ++y) {
        img->data.at(y).swap(img->data.at(img->height-y-1));;
    }
}

bool load_image(Image* result, const std::string& fname) {
    SDL_Surface* img = SDL_LoadBMP(fname.c_str());
    if (!img) {
        return false;
    }

    result->negative_energy_count = 0;
    result->width = img->w;
    result->height = img->h;

    result->data.resize(result->height);
    Uint8* pixels = reinterpret_cast<Uint8*>(img->pixels);

    for (int y = 0; y < result->height; ++y) {
        result->data.at(y).resize(result->width);
        for (int x = 0; x < result->width; ++x) {
            int current_pix = y * img->pitch + x * img->format->BytesPerPixel;
            Color c;

            c.b = pixels[current_pix+0];
            c.g = pixels[current_pix+1];
            c.r = pixels[current_pix+2];

            result->data.at(y).at(x) = c;
        }
    };

    SDL_FreeSurface(img);
    flip_image_vertically(result);
    return true;
}

bool store_image(Image img, const std::string& fname) {
    flip_image_vertically(&img);
    const int bpp = 3;
    SDL_Surface* output = SDL_CreateRGBSurface(SDL_SWSURFACE, img.width, img.height,
                                               bpp*8, 
                                               0xFF0000, 0x00FF00, 0x0000FF, 0);
    if (!output) {
        std::cerr << "Can not create output SDL_Surface";
        return false;
    }

    Uint8* pixels = reinterpret_cast<Uint8*>(output->pixels);
    for (int y = 0; y < img.height; ++y) {
        for (int x = 0; x < img.width; ++x) {
            int current_pix = y * output->pitch + x * output->format->BytesPerPixel;
            Color c = img.data.at(y).at(x);
            pixels[current_pix+2] = c.r;
            pixels[current_pix+1] = c.g;
            pixels[current_pix+0] = c.b;
        }
    }

    size_t last_dot = fname.find_last_of(".");
    if (last_dot == std::string::npos) {
        std::cerr << "Can not find extension of " << fname << "\n";
        return false;
    }
    std::string out_fname = fname.substr(0, last_dot) + ".bmp";
    SDL_SaveBMP(output, out_fname.c_str());

    SDL_FreeSurface(output);
    return true;
}

bool store_image_with_energy(Image img, const std::string& fname) {
    Image result = img;
    for (int y = 0; y < img.height; ++y) {
        for (int x = 0; x < img.width; ++x) {
            result.data.at(y).at(x) = 
                mix_color_with_energy(img.data.at(y).at(x),
                                      img.energy.at(y).at(x));
        }
    }
    return store_image(result, fname);
}


////////////////////////////////////////////////////////////////////// Energia
void compute_pixel_energy(Image* img, int x, int y) {
    if (x < 0 || x > static_cast<int>(img->data.at(0).size())-1) {
        return;
    }
    
    if (y < 0 || y > static_cast<int>(img->data.size())-1) {
        return;
    }

    const Color& c = img->data.at(y).at(x);

    int dy = 0;
    if (y > 0) {
        const Color& up = img->data.at(y-1).at(x);
        dy = abs(c.r - up.r) + abs(c.g - up.g) + abs(c.b - up.b);
    }

    int dx = 0;
    if (x > 0) {
        const Color& left = img->data.at(y).at(x-1);
        dx = abs(c.r - left.r) + abs(c.g - left.g) + abs(c.b - left.b);
    }

    img->energy.at(y).at(x) = abs(dx) + abs(dy);
}

void update_pixel_energy(Image* img, int x, int y) {
    if (x < 0 || x > static_cast<int>(img->data.at(0).size())-1) {
        return;
    }
    if (y < 0 || y > static_cast<int>(img->data.size())-1) {
        return;
    }
    if (img->energy.at(y).at(x) == c_negative_energy) {
        return;
    }
    compute_pixel_energy(img, x, y);
}

void normalize_energy(Image* img) {
    // znajdz najwieksza wartosc energii
    int e_max = 0;
    for (int y = 0; y < img->height; ++y) {
        for (int x = 0; x < img->width; ++x) {
            if (img->energy.at(y).at(x) > e_max) {
                e_max = img->energy.at(y).at(x);
            }
        }
    }    

    // przeskaluj wartosci energii do przedzialu [0,255]
    if (e_max > 0) { 
        for (int y = 0; y < img->height; ++y) {
            for (int x = 0; x < img->width; ++x) {
                if (img->energy.at(y).at(x) == 255)
                    img->energy.at(y).at(x) = 254;
                if (img->energy.at(y).at(x) > 255)
                    img->energy.at(y).at(x) = 255;
//                 img->energy.at(y).at(x) *= 255;
//                 img->energy.at(y).at(x) /= e_max;
            }
        }
    }
}

void add_energy(Image* img, const Image& energy) {
    img->negative_energy_count = 0;
    for (int y = 0; y < img->height; ++y) {
        for (int x = 0; x < img->width; ++x) {
            if (energy.data.at(y).at(x).r == 255) { // czerwone chronimy
                img->energy.at(y).at(x) = 255;
            }
            else if (energy.data.at(y).at(x).g == 255) { // zielone usuwamy
                img->energy.at(y).at(x) = c_negative_energy;
                img->negative_energy_count++;
            }
        }
    }
}

void compute_image_energy(Image* img) {
    img->energy.resize(img->height);
    for (int y = 0; y < img->height; ++y) {
        img->energy.at(y).resize(img->width);
        for (int x = 0; x < img->width; ++x) {
            compute_pixel_energy(img, x, y);
        }
    }    
    normalize_energy(img);
}

void compute_image_energy(Image* img, const Image& energy) {
    compute_image_energy(img);
    add_energy(img, energy);
}


int linear_mix(double ratio, int start, int end) {
    return (end - start) * ratio + start;
}

Color energy_to_color(int energy) { // do zapisywania energii w
                                    // postaci obrazka
    Color c;
    c.r = c.g = c.b = 0;
    if (energy == 255) {
        c.r = c.g = c.b = 255;
    }
    else if (0 <= energy && energy < 5) { // black -> dark blue
        c.b = linear_mix(energy / 5.0, 0, 0xAA);
    }
    else if (5 <= energy && energy < 10) { // dark blue -> light blue
        c.g = linear_mix((energy - 5) / 5.0, 0x00, 0x55);
        c.b = linear_mix((energy - 5) / 5.0, 0xAA, 0xFF);
    }
    else if (10 <= energy && energy < 20) { // light blue -> dark green
        c.g = linear_mix((energy - 10) / 10.0, 0x55, 0xAA);
        c.b = linear_mix((energy - 10) / 10.0, 0xFF, 0x00);
    }
    else if (20 <= energy && energy < 30) { // dark green -> light green
        c.g = linear_mix((energy - 20) / 10.0, 0xAA, 0xFF);
    }
    else if (30 <= energy && energy < 40) { // light green -> dark yellow
        c.g = linear_mix((energy - 30) / 10.0, 0xFF, 0xAA);
        c.r = linear_mix((energy - 30) / 10.0, 0x00, 0xAA);
    }
    else if (40 <= energy && energy < 70) { // dark yellow -> light yellow
        c.g = linear_mix((energy - 40) / 30.0, 0xAA, 0xFF);
        c.r = linear_mix((energy - 40) / 30.0, 0xAA, 0xFF);
    }
    else if (70 <= energy && energy < 130) { // light yellow -> orange
        c.g = linear_mix((energy - 70) / 60.0, 0xFF, 0xAA);
        c.r = 0xFF;
    }
    else if (130 <= energy && energy < 256) { // orange -> red
        c.r = 0xFF;
        c.g = linear_mix((energy - 130) / 125.0, 0xAA, 0x00);
    }

    return c;
}

bool store_energy_as_image(Image img, const std::string& fname) {
    normalize_energy(&img);

    Image energy_image;
    energy_image.width = img.width;
    energy_image.height = img.height;
    
    energy_image.data.resize(energy_image.height);
    for (int y = 0; y < energy_image.height; ++y) {
        energy_image.data.at(y).resize(energy_image.width);
        for (int x = 0; x < energy_image.width; ++x) {
            Color c = energy_to_color(img.energy.at(y).at(x));
            energy_image.data.at(y).at(x) = c;
        }
    }

    return store_image(energy_image, fname);
}


////////////////////////////////////////////////////////////////////// HISTOGRAMS
std::vector<int> compute_energy_histogram(const Image& image) {
    std::vector<int> hist(256, 0);
    for (int y = 0; y < image.height; ++y) {
        for (int x = 0; x < image.width; ++x) {
            hist.at(image.energy.at(y).at(x))++;
        }
    }
    return hist;
}

std::ostream& print_histogram(std::ostream& os, std::vector<int> histogram) {
    int max = 0;
    for (size_t i = 0; i < histogram.size(); ++i) {
        if (histogram.at(i) > max) {
            max = histogram.at(i);
        }
    }

    for (size_t i = 0; i < histogram.size(); ++i) {
        os << std::setw(3) << i << " [";
        
        for (int j = 0; j < 100; ++j) {
            if (histogram.at(i) * 100 / max >= j) {
                os << "#";
            }
            else {
                os << " ";
            }
        }

        os << "]\n";
    }

    return os;
}



////////////////////////////////////////////////////////////////////// Szwy poziome
void compute_horizontal_cumulated_energy(const Image& img, std::vector<std::vector<int> >* result) {
    std::vector<std::vector<int> >& cumulated_energy = *result;
    cumulated_energy.resize(img.height);

    for (size_t y = 0; y < cumulated_energy.size(); ++y) {
        cumulated_energy.at(y).resize(img.width);
    }
    
    // wypelnij pierwsza kolumne
    for (int y = 0; y < img.height; ++y) {
        cumulated_energy.at(y).at(0) = img.energy.at(y).at(0);
    }

    // oblicz wartosci pozostalych pol (alg. dynamiczny)
    for (int x = 1; x < img.width; ++x) {
        for (int y = 0; y < img.height; ++y) {
            int min = cumulated_energy.at(y).at(x-1);
            if (y > 0 && cumulated_energy.at(y-1).at(x-1) < min) {
                min = cumulated_energy.at(y-1).at(x-1);
            }
            if (y < img.height-1 && cumulated_energy.at(y+1).at(x-1) < min) {
                min = cumulated_energy.at(y+1).at(x-1);
            }
            cumulated_energy.at(y).at(x) = min + img.energy.at(y).at(x); 
        }
    }
}


void find_many_minimal_horizontal_seams(Image img, std::vector<std::vector<int> >* result, int k) {
    std::vector<std::vector<bool> > image_seams; // true = w tym miejscu przebiega szew
    image_seams.resize(img.height);
    for (int y = 0; y < img.height; ++y) {
        image_seams.at(y).resize(img.width);
    }

    result->clear();
    result->resize(k);
    int seams_count = 0;
    for (int i = 0; i < k; ++i) {
        std::vector<std::vector<int> > cumulated_energy;
        compute_horizontal_cumulated_energy(img, &cumulated_energy);

        // znajdz pierwszy szew, ktory mozna uzyc
        int min_y = 0;
        while (min_y < img.height && image_seams.at(min_y).at(img.width-1)) {
            min_y++;
        }

        if (min_y >= img.height) {
            return;
        }

        // znajdz koniec szwu o najmniejszej energii
        for (int y = min_y; y < img.height; ++y) {
            if (!image_seams.at(y).at(img.width-1)) {
                if (cumulated_energy.at(y).at(img.width-1) < cumulated_energy.at(min_y).at(img.width-1)) {
                    min_y = y;
                }
            }
        }

        // odtworz pozostala czesc szwu
        int y = min_y;
        result->at(i).push_back(y);
        image_seams.at(min_y).at(img.width-1) = true;
        img.energy.at(min_y).at(img.width-1) = c_seam_energy;
        for (int x = img.width-2; x >= 0; --x) {
            int new_y = y;
            if (y > 0 && cumulated_energy.at(y-1).at(x) < cumulated_energy.at(new_y).at(x)) {
                new_y = y-1;
            }
            if (y < img.height-1 && cumulated_energy.at(y+1).at(x) < cumulated_energy.at(new_y).at(x)) {
                new_y = y+1;
            }

            y = new_y;

            if (image_seams.at(y).at(x)) {
                result->resize(seams_count);
                return;
            }

            result->at(i).push_back(y);
            image_seams.at(y).at(x) = true;
            img.energy.at(y).at(x) = c_seam_energy;
        }

        seams_count++;
        std::reverse(result->at(i).begin(), result->at(i).end());
    }
}


void add_horizontal_seams(Image* img, const std::vector<std::vector<int> >& seams) {
    Image old = *img;
    
    // wyczyść obraz
    Color black = {0,0,0};
    for (int y = 0; y < img->height; ++y) {
        for (int x = 0; x < img->width; ++x) {
            img->data.at(y).at(x) = black;
        }
    }

    // zaznacz na czerwono szwy
    Image img_with_seams = *img;
    Color red  = {255,0,0};
    for (size_t i = 0; i < seams.size(); ++i) {
        for (int x = 0; x < img->width; ++x) {
            int y = seams.at(i).at(x);
            img_with_seams.data.at(y).at(x) =  red;
        }
    }

    // w każdej kolumnie idź od dołu ku górze, uśredniając miejsca, gdzie są szwy
    img->height += seams.size();
    img->data.resize(img->height);
    img->energy.resize(img->height);
    for (int y = img->height - seams.size(); y < img->height; ++y) {
        img->data.at(y).resize(img->width);
        img->energy.at(y).resize(img->width);
    }
    for (int x = 0; x < old.width; ++x) {
        int k = 0;
        for (int y = 0; y < old.height; ++y) {
            img->data.at(y+k).at(x) = old.data.at(y).at(x);
            if (img_with_seams.data.at(y).at(x) == red) {
                ++k;
                if (y < old.height-1) {
                    img->data.at(y+k).at(x) = mix_colors(old.data.at(y).at(x), old.data.at(y+1).at(x));
                    update_pixel_energy(img, y+k, x);
                    update_pixel_energy(img, y+k+1, x);
                    update_pixel_energy(img, y+k, x+1);
                }
                else {
                    img->data.at(y+k).at(x) = old.data.at(y).at(x);
                    img->energy.at(y+k).at(x) = old.energy.at(y).at(x);
                }
            }
        }
    }
}

void find_minimal_horizontal_seam(const Image& img, std::vector<int>* result) {
    std::vector<std::vector<int> > cumulated_energy(img.height);
    for (size_t y = 0; y < cumulated_energy.size(); ++y) {
        cumulated_energy.at(y).resize(img.width);
    }
    
    // wypelnij pierwsza kolumne
    for (size_t y = 0; y < cumulated_energy.size(); ++y) {
        cumulated_energy.at(y).at(0) = img.energy.at(y).at(0);
    }

    // oblicz pozostale wartosci
    for (int x = 1; x < img.width; ++x) {
        for (int y = 0; y < img.height; ++y) {
            int min = cumulated_energy.at(y).at(x-1);
            if (y > 0 && cumulated_energy.at(y-1).at(x-1) < min) {
                min = cumulated_energy.at(y-1).at(x-1);
            }
            if (y < img.height-1 && cumulated_energy.at(y+1).at(x-1) < min) {
                min = cumulated_energy.at(y+1).at(x-1);
            }
            cumulated_energy.at(y).at(x) = min + img.energy.at(y).at(x);
        }
    }

    // znajdz koniec optymalnego szwu
    int min_y = 0;
    for (int y = 1; y < img.height-1; ++y) {
        if (cumulated_energy.at(y).at(img.width-1) < cumulated_energy.at(min_y).at(img.width-1)) {
            min_y = y;
        }
    }

    // znajdz szew
    int y = min_y;
    result->push_back(y);
    for (int x = img.width-2; x >= 0; --x) {
        if (y > 0 && cumulated_energy.at(y-1).at(x) < cumulated_energy.at(y).at(x)) {
            y = y-1;
        }
        if (y < img.height-1 && cumulated_energy.at(y+1).at(x) < cumulated_energy.at(y).at(x)) {
            y = y+1;
        }
        result->push_back(y);
    }

    std::reverse(result->begin(), result->end());
}

void draw_horizontal_seam(Image* img, const std::vector<int>& hseam, const Color& c) {
    for (size_t x = 0; x < hseam.size(); ++x) {
        img->data.at(hseam.at(x)).at(x) = c;
    }
}

void remove_horizontal_seam(Image* img, const std::vector<int>& hseam) {
    img->height--;
    for (int x = 0; x < img->width; ++x) {
        int y = hseam.at(x);
        if (img->energy.at(y).at(x) == c_negative_energy) {
            img->negative_energy_count--;
        }

        for (size_t i = y; i < img->data.size()-1; ++i) {
            // przesun piksele i energie aby zmniejszyc obraz
            img->data.at(i).at(x) = img->data.at(i+1).at(x);
            img->energy.at(i).at(x) = img->energy.at(i+1).at(x);
        }

        // uaktualnij energie
        update_pixel_energy(img, x, y);
        update_pixel_energy(img, x+1, y);
    }
    
    img->data.resize(img->data.size()-1);
    img->energy.resize(img->energy.size()-1);
}


////////////////////////////////////////////////////////////////////// Szwy pionowe
void compute_vertical_cumulated_energy(const Image& img, std::vector<std::vector<int> >* result) {
    std::vector<std::vector<int> >& cumulated_energy = *result;
    cumulated_energy.resize(img.height);

    for (size_t y = 0; y < cumulated_energy.size(); ++y) {
        cumulated_energy.at(y).resize(img.width);
    }
    
    // wypelnij pierwszy wiersz
    for (int x = 0; x < img.width; ++x) {
        cumulated_energy.at(0).at(x) = img.energy.at(0).at(x);
    }

    // znajdz pozostale wartosc (alg. dynamiczny)
    for (int y = 1; y < img.height; ++y) {
        for (int x = 0; x < img.width; ++x) {
            int min = cumulated_energy.at(y-1).at(x);
            if (x > 0 && cumulated_energy.at(y-1).at(x-1) < min) {
                min = cumulated_energy.at(y-1).at(x-1);
            }
            if (x < img.width-1 && cumulated_energy.at(y-1).at(x+1) < min) {
                min = cumulated_energy.at(y-1).at(x+1);
            }
            cumulated_energy.at(y).at(x) = min + img.energy.at(y).at(x);
        }
    }
}

void find_many_minimal_vertical_seams(Image img, std::vector<std::vector<int> >* result, int k) {
    std::vector<std::vector<bool> > image_seams; // true = w tym miejscu przebiega szew
    image_seams.resize(img.height);
    for (int y = 0; y < img.height; ++y) {
        image_seams.at(y).resize(img.width);
    }

    result->clear();
    result->resize(k);
    int seams_count = 0;
    for (int i = 0; i < k; ++i) {
        std::vector<std::vector<int> > cumulated_energy;
        compute_vertical_cumulated_energy(img, &cumulated_energy);

        // znajdz pierwszy punkt, ktory moze byc koncem szwu
        int min_x = 0;
        while (min_x < img.width && image_seams.at(img.height-1).at(min_x)) {
            min_x++;
        }

        if (min_x >= img.width) {
            return; // nie ma już szwów do usunięcia
        }

        // znajdz koniec optymalnego szwu
        for (int x = 1; x < img.width-1; ++x) {
            if (!image_seams.at(img.height-1).at(x)) {
                if (cumulated_energy.at(img.height-1).at(x) < cumulated_energy.at(img.height-1).at(min_x)) {
                    min_x = x;
                }
            }
        }

        // znajdz szew
        int x = min_x;
        result->at(i).push_back(x);
        image_seams.at(img.height-1).at(x) = true;
        img.energy.at(img.height-1).at(x) = c_seam_energy;
        for (int y = img.height-2; y >= 0; --y) {
            int new_x = x;
            if (x > 0 && cumulated_energy.at(y).at(x-1) < cumulated_energy.at(y).at(new_x)) {
                new_x = x-1;
            }
            if (x < img.width-1 && cumulated_energy.at(y).at(x+1) < cumulated_energy.at(y).at(new_x)) {
                new_x = x+1;
            }

            x = new_x;

            if (image_seams.at(y).at(x)) {
                result->resize(seams_count);
                return;
            }

            result->at(i).push_back(x);
            image_seams.at(y).at(x) = true;
            img.energy.at(y).at(x) = c_seam_energy;
        }

        seams_count++;
        std::reverse(result->at(i).begin(), result->at(i).end());
    }
}

void add_vertical_seams(Image* img, const std::vector<std::vector<int> >& seams) {
    Image old = *img;
    
    // wyczyść obraz
    Color black = {0,0,0};
    for (int y = 0; y < img->height; ++y) {
        for (int x = 0; x < img->width; ++x) {
            img->data.at(y).at(x) = black;
        }
    }

    // zaznacz na czerwono szwy
    Image img_with_seams = *img;
    Color red  = {255,0,0};
    for (size_t i = 0; i < seams.size(); ++i) {
        for (int y = 0; y < img->height; ++y) {
            int x = seams.at(i).at(y);
            img_with_seams.data.at(y).at(x) =  red;
        }
    }

    // w każdym wierszu idź od lewej do prawej uśredniając miejsca, gdzie są szwy
    img->width += seams.size();
    for (int y = 0; y < old.height; ++y) {
        img->data.at(y).resize(img->width);
        img->energy.at(y).resize(img->width);
    }
    for (int y = 0; y < old.height; ++y) {
        int k = 0;
        for (int x = 0; x < old.width; ++x) {
            img->data.at(y).at(x+k) = old.data.at(y).at(x);
            img->energy.at(y).at(x+k) = old.energy.at(y).at(x);
            if (img_with_seams.data.at(y).at(x) == red) {
                ++k;
                if (x < old.width-1) {
                    img->data.at(y).at(x+k) = mix_colors(old.data.at(y).at(x), 
                                                         old.data.at(y).at(x));
                    update_pixel_energy(img, x+k, y);
                    update_pixel_energy(img, x+k+1, y);
                    update_pixel_energy(img, x+k, y+1);
                }
                else {
                    img->data.at(y).at(x+k) = old.data.at(y).at(x);
                    img->energy.at(y).at(x+k) = old.energy.at(y).at(x);
                }
            }
        }
    }
}

void find_minimal_vertical_seam(const Image& img, std::vector<int>* result) {
    std::vector<std::vector<int> > cumulated_energy(img.height);
    compute_vertical_cumulated_energy(img, &cumulated_energy);

    // znajdz koniec optymalnego szwu
    int min_x = 0;
    for (int x = 1; x < img.width-1; ++x) {
        if (cumulated_energy.at(img.height-1).at(x) 
            < cumulated_energy.at(img.height-1).at(min_x)) {
            min_x = x;
        }
    }

    // znajdz szew
    int x = min_x;
    result->push_back(x);
    for (int y = img.height-2; y >= 0; --y) {
        if (x > 0 && cumulated_energy.at(y).at(x-1) 
            < cumulated_energy.at(y).at(x)) {
            x = x-1;
        }
        if (x < img.width-1 && cumulated_energy.at(y).at(x+1) <
            cumulated_energy.at(y).at(x)) {
            x = x+1;
        }
        result->push_back(x);
    }

    std::reverse(result->begin(), result->end());
}

void draw_vertical_seam(Image* img, const std::vector<int>& vseam, 
                        const Color& c) {
    for (size_t y = 0; y < vseam.size(); ++y) {
        img->data.at(y).at(vseam.at(y)) = c;
    }
}

void remove_vertical_seam(Image* img, const std::vector<int>& vseam) {
    img->width--;
    for (int y = 0; y < img->height; ++y) {
        int x = vseam.at(y);
        if (img->energy.at(y).at(x) == c_negative_energy) {
            img->negative_energy_count--;
        }

        // przesun piksele i energie (zmniejsza obraz)
        for (size_t i = x; i < img->data.at(y).size()-1; ++i) {
            img->data.at(y).at(i) = img->data.at(y).at(i+1);
            img->energy.at(y).at(i) = img->energy.at(y).at(i+1);
        }

        // zmniejsz pamiec dla obrazu
        img->data.at(y).resize(img->data.at(y).size()-1);
        img->energy.at(y).resize(img->energy.at(y).size()-1);

        // uaktualnij energi
        update_pixel_energy(img, x, y-1);
        update_pixel_energy(img, x, y);
    }
}

////////////////////////////////////////////////////////////////////// RETARGET
void retarget(Image* image, int dest_width, int dest_height) {
    // policz czy zwiekszamy czy zmniejszamy obraz (dla poziomu i dla pionu)
    int dx = dest_width - image->width;
    int dy = dest_height - image->height;

    // pomniejszaj obraz tak dlugo az osiagnie wymagany rozmiar
    while (dx < 0 || dy < 0) {
        if (dx < 0) { // pomniejszanie w poziomie
            std::vector<int> vseam;
            find_minimal_vertical_seam(*image, &vseam);
            remove_vertical_seam(image, vseam);
            ++dx;
        }
        if (dy < 0) { // pomniejszanie w pionie
            std::vector<int> hseam;
            find_minimal_horizontal_seam(*image, &hseam);
            remove_horizontal_seam(image, hseam);
            ++dy;
        }
    }

    // sprawdz czy trzeba powiekszyc obraz. Jezeli tak to zrob to
    while (dx > 0) {
        std::vector<std::vector<int > > vseams;
        find_many_minimal_vertical_seams(*image, &vseams, dx);
        add_vertical_seams(image, vseams);
        dx -= vseams.size();
    }
    while (dy > 0) {
        std::vector<std::vector<int > > hseams;
        find_many_minimal_horizontal_seams(*image, &hseams, dy);
        add_horizontal_seams(image, hseams);
        dy -= hseams.size();
    }
}

void retarget(const std::string& fname, int dest_width,
              int dest_height, const std::string& energy_fname) {
    // wczytaj obrazek
    Image image;
    if (!load_image(&image, fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }

    // oblicz energię obrazka (uwzgledniajac opcjonalny plik z energia)
    if (energy_fname == "") {
        compute_image_energy(&image);
    }
    else {
        Image energy;
        if (!load_image(&energy, energy_fname)) {
            std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
            return;
        }
        compute_image_energy(&image, energy);
    }

    retarget(&image, dest_width, dest_height);
    store_image(image, "output.bmp");
}

////////////////////////////////////////////////////////////////////// AMPLIFY
void amplify(const std::string& fname, int horizontal_amplification,
             int vertical_amplification, const std::string& energy_fname) {
    // wczytaj obrazek
    Image image;
    if (!load_image(&image, fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }

    // oblicz energię obrazka (uwzgledniajac opcjonalny plik z energia)
    if (energy_fname == "") {
        compute_image_energy(&image);
    }
    else {
        Image energy;
        if (!load_image(&energy, energy_fname)) {
            std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
            return;
        }
        compute_image_energy(&image, energy);
    }

    // pomniejsz, a nastepnie powieksz obrazek
    int original_width = image.width;
    int original_height = image.height;
    int amplify_width = image.width * horizontal_amplification / 100;
    int amplify_height = image.height * vertical_amplification / 100;

    retarget(&image, amplify_width, amplify_height);
    retarget(&image, original_width, original_height);

    store_image(image, "output.bmp");
}

////////////////////////////////////////////////////////////////////// REMOVE OBJECTS
void remove_objects(const std::string& fname, const std::string& energy_fname, int mode) {
    // wczytaj obrazek
    Image image;
    if (!load_image(&image, fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }

    // oblicz energię obrazka (uwzgledniajac plik z energia)
    Image energy;
    if (!load_image(&energy, energy_fname)) {
        std::cerr << "[ ERROR ] Can not open file [" << fname << "]\n";
        return;
    }
    compute_image_energy(&image, energy);

    // pomniejszaj obrazek az nie bedzie juz miejsc 'do usuniecia'
    int original_width = image.width;
    int original_height = image.height;
    int count = 0;
    int no_change_steps = 0; // przez ile krokow nie zmieniala
                              // sie negatywna energia
    bool horizontal = false;
    if (mode == 1) horizontal = true; // 1 = tylko linie poziome, 2 = tylko pionowe, 3 = oba typy
    while (image.negative_energy_count > 0) {
        ++count;
        size_t last_negative_energy = image.negative_energy_count;
//         std::cout << count << " " << no_change_steps << " " << image.negative_energy_count << "\n";

        if (horizontal) {
            retarget(&image, image.width, image.height-1);
        }
        else {
            retarget(&image, image.width-1, image.height);
        }

        if (mode == 3) {
            horizontal = !horizontal;
        }

        ++no_change_steps;
        if (last_negative_energy != image.negative_energy_count) {
            no_change_steps = 0;
        }
        if (no_change_steps > 5 && image.negative_energy_count < 5) {
            break;
        }
    }

    // usun negatywna energie (nie moze przeszkadzac w powiekszaniu
    for (int y = 0; y < image.height; ++y) {
        for (int x = 0; x < image.width; ++x) {
            if (image.energy.at(y).at(x) == c_negative_energy) {
                compute_pixel_energy(&image, x, y);
            }
        }
    }

    // przywroc pierwotny rozmiar obrazka
    retarget(&image, original_width, original_height);

    store_image(image, "output.bmp");
}

////////////////////////////////////////////////////////////////////// MAIN
void print_usage(const std::string& program_name) {
    std::cout << "\n\n\tImplementacja algorytmu Seam Carving by Lukasz Milewski (lmilewski@gmail.com) "
              << "\n\nUZYCIE: " << program_name << " AKCJA OPCJE\n\n"
              << "Kazda akcja zapisuje wynik dzialania w postaci pliku output.bmp\n\n"
              << "Dostepne akcje\n"
              << "~~~~~~~~~~~~~~\n"
              << " skaluj - Zmienia wymiary obrazka (powiekszanie / pomniejszanie)\n"
              << " wzmocnij - Uwydatnia najwazniejsze elementy na obrazku (o najwiekszej energii\n"
              << " usun - Usuwa z obrazka wszystkie obiekty o negatywnej energii\n"
              << " energia - Oblicza funkcję energii dla obrazka i zapisuje ją w postaci obrazka\n"
              << "\n\n"
              << "   Kazda akcja ma swoj zestaw opcji. Niektore akcje maja jako opcje plik z energia.\n"
              << "Jest to dodatkowy plik bmp o wymiarach TAKICH SAMYCH jak obraz wejsciowy.\n"
              << "Powinien byc to czarny (lub przezroczysty) obraz z zaznaczonymi fragmentami na: "
              << "  o zielono - te obszary beda mialy znacznie zmniejszona energie (beda szybko usuwane)\n"
              << "  o czerwono - te obszary beda mialy znacznie zwiekszona energie (nie beda usuwane)\n"
              << "\n\n"
              << "Opcje funkcji 'skaluj'\n"
              << " 1. nazwa pliku wejsciowego\n"
              << " 2. docelowa szerokosc\n"
              << " 3. docelowa wysokosc\n"
              << " 4. [ OPCJONALNY ] plik z energia\n"
              << "\n\n"
              << "Opcje funkcji 'wzmocnij'\n"
              << " 1. nazwa pliku wejsciowego\n"
              << " 2. procentowe wzmocnienie w pionie\n"
              << " 3. procentowe wzmocnienie w poziomie\n"
              << "\n\n"
              << "Opcje funkcji 'usun'\n"
              << " 1. nazwa pliku wejsciowego\n"
              << " 2. nazwa pliku z energia\n"
              << " 3. tryb usuwania\n"
              << "   3a) 1 => usuwane sa linie poziome\n"
              << "   3b) 2 => usuwane sa linie pionowe\n"
              << "   3c) 3 => usuwane sa linie pionowe i poziome\n"
              << "\n\n" 
              << "Opcje funkcji 'energia'\n"
              << " 1. nazwa pliku wejsciowego\n";
}

int main(int argc, char** argv) {
    std::string pname = argv[0];
    if (argc < 2) {
        print_usage(pname);
        return 1;
    }
    std::string command = argv[1];

    if (command == "skaluj") {
        // argv:
        //  0. nazwa programu
        //  1. nazwa akcji = 'skaluj'
        //  2. nazwa pliku wejsciowego
        //  3. docelowa szerokosc
        //  4. docelowa wysokosc
        //  5. [ OPCJONALNY ] plik z energia
        if (argc < 5) {
            print_usage(pname);
            return 3;
        }
        std::string fname = argv[2];
        int dest_width; std::istringstream(argv[3]) >> dest_width;
        int dest_height; std::istringstream(argv[4]) >> dest_height;

        std::string energy_fname;
        if (argc >= 6) {
            energy_fname = argv[5];
        }

        retarget(fname, dest_width, dest_height, energy_fname);
    }
    else if (command == "wzmocnij") {
        // argv:
        //  0. nazwa programu
        //  1. nazwa akcji = 'wzmocnij'
        //  2. nazwa pliku wejsciowego
        //  3. procentowe wzmocnienie w pionie
        //  4. procentowe wzmocnienie w poziomie
        //
        //  Procentowe zmniejszenie oznacza do ilu procent
        //  oryginalnego rozmiaru obraz zostanie pomniejszony w
        //  pierwszej fazie
        if (argc < 5) {
            print_usage(pname);
            return 4;
        }
        std::string fname = argv[2];
        int horizontal_amplification; 
        std::istringstream(argv[3]) >> horizontal_amplification;
        int vertical_amplification;
        std::istringstream(argv[4]) >> vertical_amplification;

        std::string energy_fname;
        if (argc >= 6) {
            energy_fname = argv[5];
        }
        amplify(fname, horizontal_amplification,
                vertical_amplification, energy_fname);
    }
    else if (command == "usun") {
        // argv:
        //  0. nazwa programu
        //  1. nazwa akcji = 'usun'
        //  2. nazwa pliku wejsciowego
        //  3. nazwa pliku z energia
        //  4. tryb usuwania (1 - usuwaj poziome linie
        //                    2 - usuwaj pionowe linie
        //                    3 - usuwaj poziome i pionowe linie)
        if (argc < 5) {
            print_usage(pname);
            return 5;
        }
        std::string fname = argv[2];
        std::string energy_fname = argv[3];
        int mode;
        std::istringstream(argv[4]) >> mode;
        remove_objects(fname, energy_fname, mode);
    }
    else if (command == "energia") {
        // argv:
        //  0. nazwa programu
        //  1. nazwa akcji = 'energia'
        //  2. nazwa pliku wejściowego
        if (argc < 3) {
            print_usage(pname);
            return 6;
        }
        std::string fname = argv[2];
        Image image;
        if (!load_image(&image, fname)) {
            std::cerr << "Can not open file [" << fname << "]\n";
            return 0;
        }
        compute_image_energy(&image);
        store_energy_as_image(image, "output.bmp");
    }
    else {
        print_usage(pname);
        return 2;
    }
    return 0;
}