SnippyHolloW-BroodwarBotQ-f01ab56/src/Utils/QuadTree.h

Go to the documentation of this file.

#pragma once
/***
 * LGPL Code from BWAPI: 
 * http://www.google.com/p/bwapi/
 */

#include <list>

namespace Util
{
  template <class Type>
  class QuadTree
   {
     public :
       QuadTree(unsigned int width = 1, unsigned int height = 1);
       ~QuadTree(void);
       unsigned int getWidth(void) const;
       unsigned int getHeight(void) const;
       std::list<Type*>* getItems(unsigned int x, unsigned int y, unsigned int level = 0);
       void addItem(unsigned int x, unsigned int y, Type *item);
       void clear(unsigned int x, unsigned int y);
     private :
       unsigned int width;
       unsigned int height;
       RectangleArray<std::list<Type*> >* data;
       unsigned int depth;
   };
  //---------------------------------------------- CONSTRUCTOR -----------------------------------------------
  template <class Type>
  QuadTree<Type>::QuadTree(unsigned int width, unsigned int height)
  :width(width)
  ,height(height)
  ,depth(ceil(log2(max(width,height)))
  {
    this->data = new RectangleArray<std::list<Type*> >[depth];
    unsigned int localWidth = width;
    unsigned int localHeight = height;
    for (unsigned int i = 0; i < this->depth; ++i)
    {
      this->data[i].resize(localWidth, localHeight);
      localWidth = (localWidth >= 2) (localWidth+1)/2 : 1;
      localHeight = (localHeight >=2) (localHeight+1)/2 : 1;
    }
  }
  //----------------------------------------------- DESTRUCTOR -----------------------------------------------
  template <class Type>
  RectangleArray<Type>::~RectangleArray(void)
  {
    delete [] data;
  }
  //----------------------------------------------- GET WIDTH ------------------------------------------------
  template <class Type>
  unsigned int RectangleArray<Type>::getWidth(void) const
  {
    return this->width;
  }
  //----------------------------------------------- SET WIDTH ------------------------------------------------
  template <class Type>
  void RectangleArray<Type>::setWidth(unsigned int width)
  {
    this->width = width;
  }
  //----------------------------------------------- GET HEIGHT -----------------------------------------------
  template <class Type>
  unsigned int RectangleArray<Type>::getHeight(void) const
  {
    return this->height;
  }
  //------------------------------------------------ GET ITEM ------------------------------------------------
  template <class Type>
  std::list<Type*>* getItems(unsigned int x, unsigned int y, unsigned int level = 0);
  {
    return this->data[level][x][y];
  }
  //------------------------------------------------ ADD ITEM ------------------------------------------------
  template <class Type>
  void RectangleArray<Type>::addItem(unsigned int x, unsigned int y, Type* item)
  {
    for (unsigned int i = 0; i < this->depth; ++i)
      this->data[i][x<<i][y<<i].push_bach(item);
  }
  //------------------------------------------------- CLEAR --------------------------------------------------
  template <class Type>
  void RectangleArray<Type>::clear(unsigned int x, unsigned int y)
  {
    for (unsigned int i = 0; i < this->depth; ++i)
      this->data[i][x<<i][y<<i].clear();
  }
  //----------------------------------------------------------------------------------------------------------
}