quadtree.cpp

/**
 * @file quadtree.cpp
 * quadtree class implementation.
 * @date Spring 2008
 * @date Modified Summer 2014
 */

#include <iostream>
#include <cstdint>
#include <memory>
#include <exception>
#include <cmath>
#include "quadtree.h"
#include "epng.h"
#include "rgba_pixel.h"

namespace cs225
{
     /*
      * Constructors for the quadtree class:
      * Defualt constructor
      * Cropped image Constructor
      * Copy constructor
      * Move constructor
      */

     quadtree::quadtree()
          :root_{nullptr}, size_{0}
     {
          //Call the defualt node constructor
          node();
     }

     quadtree::quadtree(const epng::png& source, uint64_t resolution)
           :root_{nullptr}, size_{0}
     {
          //Build_tree will initialize and construct the tree
          build_tree(source, resolution);
     }

     quadtree::quadtree(const quadtree& other)
          :root_{nullptr}, size_{other.size_}
     {
          //Check if other is empty
          if(other.root_ != nullptr)
               root_ = std::make_unique<node>(node(*(other.root_.get())));
     }

     quadtree::quadtree(quadtree&& other)
          :root_{nullptr}, size_{0}
     {
          std::swap(root_, other.root_);
          std::swap(size_, other.size_);
     }

     /*
      * Constructors for the node structures:
      * Defualt constructor
      * Copy constructor
      */

     quadtree::node::node()
          :northwest{nullptr}, northeast{nullptr},
           southwest{nullptr}, southeast{nullptr},
           element{epng::rgba_pixel()}
     {
          //Nothing!
     }

     quadtree::node::node(const node& other)
          :northwest{nullptr}, northeast{nullptr},
           southwest{nullptr}, southeast{nullptr},
           element{epng::rgba_pixel()}
     {
          //Copy over all the nodes and elements
          element = std::move(copy_nodes(other));
     }

     quadtree& quadtree::operator=(quadtree other)
     {
          if(root_ != nullptr)
          {
               clear(*(root_.get()));
               root_.reset(nullptr);
          }
          size_ = std::move(other.size_);
          swap(other);
          return *this;
     }

     const epng::rgba_pixel& quadtree::operator()(uint64_t x, uint64_t y) const
     {
          uint64_t x_bound = size_;
          uint64_t y_bound = size_;
          epng::rgba_pixel temp = epng::rgba_pixel();

          //Check the bounds of the given coordinates
          if(!root_)
               throw std::out_of_range("Empty tree");
          else if(x > (size_-1) || y > (size_-1))
               throw std::out_of_range("Invalid coordinates");

          //Call the helper function to return the pixel
          return find_pixel(*(root_.get()), temp, x, y, x_bound, y_bound);
     }

     void quadtree::build_tree(const epng::png& source, uint64_t resolution)
     {
          uint64_t height = 0;
          uint64_t level = 0;
          uint64_t x = 0;
          uint64_t y = 0;
          uint64_t iter_x = 0;
          uint64_t iter_y = 0;
          int base = 0;

          if(root_ != nullptr)
          {
               //Delete the contents of the current tree
               clear(*(root_.get()));
               root_ = nullptr;
          }

          //Set the size of the quadtree
          size_ = resolution;

          //Compute the height of the tree to be built
          height = log2(resolution);

          //Create the root for the tree
          root_ = std::make_unique<node>(node());

          //build the tree by looping through the pixels recursively
          build_tree(source, resolution, *(root_.get()), level, height, x, y, iter_x, iter_y, base);
     }

     epng::png quadtree::decompress() const
     {
          //Check for an empty tree
          if(!root_)
               throw std::runtime_error("Empty tree");

          //Create the png image from the quadtree
          epng::png* out_png = new epng::png(size_, size_);
          epng::png temp_png = epng::png(size_, size_);

          uint64_t height = log2(size_);

          //Set each pixel to its respective pixel in the quadtree
          *out_png = get_pixels(*(root_.get()), temp_png, size_, size_, height+1);

          return *out_png;
     }

     void quadtree::rotate_clockwise()
     {
          //Call the helper function
          rotate_clockwise(*(root_.get()));

     }

     void quadtree::clear(node& subroot)
     {
          //Perform a depth-first deletion of the tree
          //Base case: At a leaf
          if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
          {
               return;
          }

          //Traverse the Northwest child
          if(subroot.northwest.get() != nullptr)
          {
               clear(*(subroot.northwest.get()));
               subroot.northwest.reset(nullptr);
          }

          //Traverse the Northeast child
          if(subroot.northeast.get() != nullptr)
          {
               clear(*(subroot.northeast.get()));
               subroot.northeast.reset(nullptr);
          }

          //Traverse the Southwest child
          if(subroot.southwest.get() != nullptr)
          {
               clear(*(subroot.southwest.get()));
               subroot.southwest.reset(nullptr);
          }

          //Traverse the Southeast child
          if(subroot.southeast.get() != nullptr)
          {
               clear(*(subroot.southeast.get()));
               subroot.southeast.reset(nullptr);
          }

          return;
     }

     void quadtree::swap(quadtree& other)
     {
          //Call the copy_nodes function to copy the nodes
          root_ = std::make_unique<node>(node(*(other.root_.get())));
     }

     void quadtree::build_tree(const epng::png source, const uint64_t scope, node& subroot, uint64_t level,
                               const uint64_t height, uint64_t x, uint64_t y, uint64_t iter_x, uint64_t iter_y, int& base)
     {
          if(base == pow(scope, 2))
               return;

          iter_x = x;
          iter_y = y;

          //Base case: At a  leaf
          if(level == height)
          {
               base++;

               //Get the element
               subroot.element = std::move(*source(x+iter_x, y+iter_y));

               if(iter_x == 1)
               {
                    iter_x = 0;
                    if(iter_y == 1)
                         iter_y = 0;
                    else
                         iter_y++;
               }
               else
                    iter_x++;

               return;
          }

          //Perform a breadth-first like build of the tree
          subroot.northwest = std::make_unique<node>(node());
          subroot.northeast = std::make_unique<node>(node());
          subroot.southwest = std::make_unique<node>(node());
          subroot.southeast = std::make_unique<node>(node());

          level++;

          //recursively call the the subroots
          build_tree(source, scope, *(subroot.northwest.get()), level, height, x, y, iter_x, iter_y, base);
          build_tree(source, scope, *(subroot.northeast.get()), level, height, (x+(level/2)), y, iter_x, iter_y, base);
          build_tree(source, scope, *(subroot.southwest.get()), level, height, x, (y+(level/2)), iter_x, iter_y, base);
          build_tree(source, scope, *(subroot.southeast.get()), level, height, (x+(level/2)), (y+(level/2)), iter_x, iter_y, base);

          //Compute the average of the colors
          subroot.element.red = (subroot.northwest.get()->element.red + subroot.northeast.get()->element.red +
                                 subroot.southwest.get()->element.red + subroot.southeast.get()->element.red)/4;
          subroot.element.green = (subroot.northwest.get()->element.green + subroot.northeast.get()->element.green +
                                 subroot.southwest.get()->element.green + subroot.southeast.get()->element.green)/4;
          subroot.element.blue = (subroot.northwest.get()->element.blue + subroot.northeast.get()->element.blue +
                                 subroot.southwest.get()->element.blue + subroot.southeast.get()->element.blue)/4;
          subroot.element.alpha = (subroot.northwest.get()->element.alpha + subroot.northeast.get()->element.alpha +
                                 subroot.southwest.get()->element.alpha + subroot.southeast.get()->element.alpha)/4;
          return;
     }

     const epng::rgba_pixel& quadtree::find_pixel(node& subroot, epng::rgba_pixel& temp, const uint64_t x, const uint64_t y,
                                                  uint64_t x_bound, uint64_t y_bound) const
     {
          //Base case: At a leaf
          if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
          {
               temp = subroot.element;
               return temp;
          }
          if(x >= (x_bound/2))
          {
               if(y >= (y_bound/2))
               {
                    //Pixel is in the southeast node
                    temp = find_pixel(*(subroot.southeast.get()), temp, x, y, (x_bound+2), (y_bound+2));
               }
               else
               {
                    //Pixel is in the northeast node
                    temp = find_pixel(*(subroot.northeast.get()), temp, x, y, (x_bound+2), (y_bound/2));
               }
          }
          else
          {
               if(y >= (y_bound/2))
               {
                    //Pixel is in the southwest node
                    temp = find_pixel(*(subroot.southwest.get()), temp, x, y, (x_bound/2), (y_bound+2));
               }
               else
               {
                    //Pixel is in the northwest node
                    temp = find_pixel(*(subroot.northwest.get()), temp, x, y, (x_bound/2), (y_bound/2));
               }
          }

          return temp;
     }

     const epng::png& quadtree::get_pixels(const node& subroot, epng::png& out_png, uint64_t x, uint64_t y, uint64_t level) const
     {
          //Base case: At a leaf
          if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
          {
               *out_png(x-1, y-1) = subroot.element;
               return out_png;
          }

          level--;

          //Traverse the northwest node
          if(subroot.northwest.get() != nullptr)
               get_pixels(*(subroot.northwest.get()), out_png, ceil(x/2), ceil(y/2), level);

          //Traverse the northeast node
          if(subroot.northeast.get() != nullptr)
               get_pixels(*(subroot.northeast.get()), out_png, ceil(x/2+level), ceil(y/2), level);

          //Traverse the southwest node
          if(subroot.southwest.get() != nullptr)
               get_pixels(*(subroot.southwest.get()), out_png, ceil(x/2), ceil(y/2+level),level);

          //Traverse the southeast node
          if(subroot.southeast.get() != nullptr)
               get_pixels(*(subroot.southeast.get()), out_png, ceil(x/2+level), ceil(y/2+level), level);

          return out_png;
     }

     const epng::rgba_pixel& quadtree::node::copy_nodes(const node& other)
     {
          //Base case: At a leaf
          if(!other.northwest.get() && !other.northeast.get() && !other.southwest.get() && !other.southeast.get())
          {
               return other.element;
          }

          //Traverse the northwest node
          if(other.northwest.get() != nullptr)
          {
               //Create a node at the child
               this->northwest = std::make_unique<node>(node(*(other.northwest.get())));
          }

          //Traverse the northeast node
          if(other.northeast.get() != nullptr)
          {
               //Create a node at the child
               this->northeast = std::make_unique<node>(node(*(other.northeast.get())));
          }

          //Traverse the southwest node
          if(other.southwest.get() != nullptr)
          {
               //Create a node at the child
               this->southwest = std::make_unique<node>(node(*(other.southwest.get())));
          }

          //Traverse the southeast node
          if(other.southeast.get() != nullptr)
          {
               //Create a node at the child
               this->southeast = std::make_unique<node>(node(*(other.southeast.get())));
          }

          return other.element;
     }

     void quadtree::rotate_clockwise(node& subroot)
     {
          //Base case: At a leaf
          if(!subroot.northwest.get() && !subroot.northeast.get() && !subroot.southwest.get() && !subroot.southeast.get())
          {
               return;
          }

          //Traverse the northwest node
          if(subroot.northwest != nullptr)
          {
               rotate_clockwise(*(subroot.northwest.get()));

               //Rotate the nodes
               std::swap(subroot.northwest, subroot.southeast);
               std::swap(subroot.northwest, subroot.southwest);
               std::swap(subroot.northwest, subroot.northeast);
          }

          //Traverse the northeast node
          if(subroot.northeast != nullptr)
          {
               rotate_clockwise(*(subroot.northeast.get()));

               //Rotate the nodes
               std::swap(subroot.northwest, subroot.southeast);
               std::swap(subroot.northwest, subroot.southwest);
               std::swap(subroot.northwest, subroot.northeast);
          }

          //Traverse the southwest node
          if(subroot.southwest != nullptr)
          {
               rotate_clockwise(*(subroot.southwest.get()));

               //Rotate the nodes
               std::swap(subroot.northwest, subroot.southeast);
               std::swap(subroot.northwest, subroot.southwest);
               std::swap(subroot.northwest, subroot.northeast);
          }

          //Traverse the southeast node
          if(subroot.southwest != nullptr)
          {
               rotate_clockwise(*(subroot.southeast.get()));

               //Rotate the nodes
               std::swap(subroot.northwest, subroot.southeast);
               std::swap(subroot.northwest, subroot.southwest);
               std::swap(subroot.northwest, subroot.northeast);
          }
     }
}