BWAPI
|
00001 #pragma once 00002 00003 #include <list> 00004 00005 namespace Util 00006 { 00015 template <class Type> 00016 class RegionQuadTree 00017 { 00018 public : 00024 RegionQuadTree(unsigned int width = 1, unsigned int height = 1); 00026 ~RegionQuadTree(void); 00031 unsigned int getWidth(void) const; 00036 unsigned int getHeight(void) const; 00043 std::list<Type*>* getItems(unsigned int x, unsigned int y, unsigned int level = 0); 00050 void addItem(unsigned int x, unsigned int y, Type *item); 00051 void clear(unsigned int x, unsigned int y); 00052 private : 00054 unsigned int width; 00056 unsigned int height; 00061 RectangleArray<std::list<Type*> >* data; 00063 unsigned int depth; 00064 }; 00065 //---------------------------------------------- CONSTRUCTOR ----------------------------------------------- 00066 template <class Type> 00067 RegionQuadTree<Type>::RegionQuadTree(unsigned int width, unsigned int height) 00068 :width(width) 00069 ,height(height) 00070 ,depth(ceil(log2(max(width,height))) 00071 { 00072 this->data = new RectangleArray<std::list<Type*> >[depth]; 00073 unsigned int localWidth = width; 00074 unsigned int localHeight = height; 00075 for (unsigned int i = 0; i < this->depth; ++i) 00076 { 00077 this->data[i].resize(localWidth, localHeight); 00078 localWidth = (localWidth >= 2) (localWidth+1)/2 : 1; 00079 localHeight = (localHeight >=2) (localHeight+1)/2 : 1; 00080 } 00081 } 00082 //----------------------------------------------- DESTRUCTOR ----------------------------------------------- 00083 template <class Type> 00084 RectangleArray<Type>::~RectangleArray(void) 00085 { 00086 delete [] data; 00087 } 00088 //----------------------------------------------- GET WIDTH ------------------------------------------------ 00089 template <class Type> 00090 unsigned int RectangleArray<Type>::getWidth(void) const 00091 { 00092 return this->width; 00093 } 00094 //----------------------------------------------- SET WIDTH ------------------------------------------------ 00095 template <class Type> 00096 void RectangleArray<Type>::setWidth(unsigned int width) 00097 { 00098 this->width = width; 00099 } 00100 //----------------------------------------------- GET HEIGHT ----------------------------------------------- 00101 template <class Type> 00102 unsigned int RectangleArray<Type>::getHeight(void) const 00103 { 00104 return this->height; 00105 } 00106 //------------------------------------------------ GET ITEM ------------------------------------------------ 00107 template <class Type> 00108 std::list<Type*>* getItems(unsigned int x, unsigned int y, unsigned int level = 0); 00109 { 00110 return this->data[level][x][y]; 00111 } 00112 //------------------------------------------------ ADD ITEM ------------------------------------------------ 00113 template <class Type> 00114 void RectangleArray<Type>::addItem(unsigned int x, unsigned int y, Type* item) 00115 { 00116 for (unsigned int i = 0; i < this->depth; ++i) 00117 this->data[i][x<<i][y<<i].push_bach(item); 00118 } 00119 //------------------------------------------------- CLEAR -------------------------------------------------- 00120 template <class Type> 00121 void RectangleArray<Type>::clear(unsigned int x, unsigned int y) 00122 { 00123 for (unsigned int i = 0; i < this->depth; ++i) 00124 this->data[i][x<<i][y<<i].clear(); 00125 } 00126 //---------------------------------------------------------------------------------------------------------- 00127 }