quadtree.h

/**
 * @file quadtree.h
 * quadtree class definition.
 * @date Spring 2008
 * @date Modified Summer 2014
 */

#ifndef QUADTREE_H_
#define QUADTREE_H_

#include <iostream>
#include <cstdint>
#include "epng.h"

namespace cs225
{

/**
 * A tree structure that is used to compress epng::png images.
 */
class quadtree
{
  public:
     //The constructors and destrcutor
     quadtree();
     quadtree(const epng::png& source, uint64_t resolution);
     quadtree(const quadtree& other);
     quadtree(quadtree&& other);
     ~quadtree() = default;

     /**
      * Assignment operator
      * @param The element to be assigned into this quadtree
      * @return A reference to the current quadtree
      */
     quadtree& operator=(quadtree other);

     /**
      * Access operator
      * @param x-coordinate, y-coordinate of pixel to access
      * @return Reference to the pixel at the coordinates
      */
     const epng::rgba_pixel& operator()(uint64_t x, uint64_t y) const;

     /**
      * Replaces current object with d by d block from the source image
      * @param The source image, the size of the block
      * @return Void
      */
     void build_tree(const epng::png& source, uint64_t resolution);

     /**
      * Returns underlying png object represented by the quadtree
      * @param None
      * @return A png object
      */
     epng::png decompress() const;

     /**
      * Rotates the image clockwise by 90 degrees
      * @param None
      * @return Void
      */
     void rotate_clockwise();

     /**
      * Compresses the image the quadtree represents
      * @param The integer tolerance between two nodes
      * @return Void
      */
     void prune(uint32_t tolerance);//TODO

     /**
      * Gets the number of leaves in the tree if it were pruned
      * @param The integer tolerance between two nodes
      * @return Number of leaves
      */
     uint64_t pruned_size(uint32_t tolerance) const;//TODO

     /**
      * Calculates and returns the minimum tolerance to gaurantee that no more than num_leaves remain upon pruning
      * @param The number of leaves to remain
      * @return Minimum tolerance to give the number of leaves specified
      */
     uint32_t ideal_prune(uint64_t num_leaves) const;//TODO

  private:
    /**
     * A simple class representing a single node of a quadtree.
     */
    class node
    {
      public:
        //Constructors for the node class
        node();
        node(const node& other);

        /**
        * helper function for the copy constructor
        * @param A node class
        * @return A reference to an epng::rgba_pixel
        */
        const epng::rgba_pixel& copy_nodes(const node& other);

        /**
         * Helper function to clear an existing quadtree
         * @param Reference to the node class
         * @return Void
         */
        //void clear(node& subroot);

        std::unique_ptr<node> northwest;
        std::unique_ptr<node> northeast;
        std::unique_ptr<node> southwest;
        std::unique_ptr<node> southeast;

        //The pixel stored as this node's "data"
        epng::rgba_pixel element;
    };

    //The root and # of nodes in the tree
    std::unique_ptr<node> root_;
    uint64_t size_;

    /**
     * Helper function to clear an existing quadtree
     * @param Reference to the node class
     * @return Void
     */
    void clear(node& subroot);

     /**
      * Helper function to swap the contents of two quadtrees
      * @param The quadtree to swap with
      * @return Void
      */
     void swap(quadtree& other);

     /**
      * Helper function to access a pixel from the quadtree
      * @param A subroot of the tree, a pixel, x-coordinate of pixel, y-coordinate of pixel, x-bound of block, y-bound of block
      * @return Reference to the pixel at the coordinates
      */
     const epng::rgba_pixel& 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;

     /**
      * Helper function to traverse tree and return the pixel at the leaves
      * @param A subroot of the tree, the png image to make, x-coordinate of pixel, y-coordinate of pixel
      * @return Reference to the pixel at the coordinates
      */
     const epng::png& get_pixels(const node& subroot, epng::png& out_png, uint64_t x, uint64_t y, uint64_t level) const;

     /**
      * Helper function to build the quad tree utilizing a breadth-first like build algorithm
      * @param The source image, the size of the block
      * @return Void
      */
     void 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);

     /**
      * Rotates the image by 90 clockwise
      * @param A reference to a node
      * @return Void
      */
     void rotate_clockwise(node& subroot);

/**** Do not remove this line or copy its contents here! ****/
#include "quadtree_given.h"
};
}
#endif