algorithm.cc

Go to the documentation of this file.
00001 /*                            Package   : libhex
00002  * algorithm.cc               Created   : 2007/10/11
00003  *                            Author    : Alex Tingle
00004  *
00005  *    Copyright (C) 2007-2008, Alex Tingle.
00006  *
00007  *    This file is part of the libhex application.
00008  *
00009  *    libhex is free software; you can redistribute it and/or
00010  *    modify it under the terms of the GNU Lesser General Public
00011  *    License as published by the Free Software Foundation; either
00012  *    version 2.1 of the License, or (at your option) any later version.
00013  *
00014  *    libhex is distributed in the hope that it will be useful,
00015  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
00016  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017  *    Lesser General Public License for more details.
00018  *
00019  *    You should have received a copy of the GNU Lesser General Public
00020  *    License along with this library; if not, write to the Free Software
00021  *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00022  */
00023 
00024 #include "hex.h"
00025 
00026 #include <cassert>
00027 #include <sstream>
00028 
00029 namespace hex {
00030 
00031 
00032 void
00033 go(int& i, int& j, Direction d, int distance)
00034 {
00035   for(; distance>0; --distance)
00036       if(j%2)
00037           switch(d) // odd
00038           {
00039             case A: ++i;      break;
00040             case B: ++i; ++j; break;
00041             case C:      ++j; break;
00042             case D: --i;      break;
00043             case E:      --j; break;
00044             case F: ++i; --j; break;
00045           }
00046       else
00047           switch(d) // even
00048           {
00049             case A: ++i;      break;
00050             case B:      ++j; break;
00051             case C: --i; ++j; break;
00052             case D: --i;      break;
00053             case E: --i; --j; break;
00054             case F:      --j; break;
00055           }
00056 }
00057 
00058 
00059 void
00060 go(int& i, int& j, const std::string& steps)
00061 {
00062   for(std::string::const_iterator s=steps.begin(); s!=steps.end(); ++s)
00063     if('A'<=*s && *s<='F')
00064         go(i,j,to_direction(*s));
00065     else
00066         break; // Just bail out if we encounter a non-Direction character.
00067 }
00068 
00069 
00070 std::string
00071 steps(const Hex* from, const Hex* to)
00072 {
00073   std::string result ="";
00074   int i =from->i;
00075   int j =from->j;
00076   const int to_i =to->i;
00077   const int to_j =to->j;
00078   Direction direction;
00079   while(true)
00080   {
00081     if( j < to_j )                                   // go up
00082     {
00083         if(      i < to_i )          direction = B;
00084         else if( i > to_i || j%2 )   direction = C;
00085         else                         direction = B;
00086     }
00087     else if( j > to_j )                              // go down
00088     {
00089         if(      i < to_i )          direction = F;
00090         else if( i > to_i || j%2 )   direction = E;
00091         else                         direction = F;
00092     }
00093     else // j == to_j                                // go across
00094     {
00095         if(      i < to_i )          direction = A;
00096         else if( i > to_i )          direction = D;
00097         else                         break;          //  Done!
00098     }
00099     result += to_char(direction);
00100     go(i,j,direction);
00101   }
00102   return result;
00103 }
00104 
00105 
00106 int
00107 distance(const Hex* from, const Hex* to)
00108 {
00109   return steps(from,to).size();
00110 }
00111 
00112 
00113 std::set<Hex*>
00114 range(Hex* h, int distance)
00115 {
00116   std::set<Hex*> result;
00117   if(distance<1)
00118   {
00119     result.insert(h);
00120   }
00121   else
00122   {
00123     const Grid& grid =h->grid();
00124     int i =h->i;
00125     int j =h->j;
00126   
00127     try {
00128       go(i,j,hex::A,distance); // in/out: i,j
00129       result.insert( grid.hex(i,j) );
00130     } catch(hex::out_of_range&) {}
00131   
00132     for(int d=0; d<DIRECTIONS; ++d)
00133     {
00134       Direction direction =C+d;
00135       for(int count=0; count<distance; ++count)
00136           try {
00137             go(i,j,direction); // in/out: i,j
00138             result.insert( grid.hex(i,j) );
00139           } catch(hex::out_of_range&) {}
00140     }
00141   }
00142   return result;
00143 }
00144 
00145 
00146 std::set<Hex*>
00147 set_difference(const std::set<Hex*>& a, const std::set<Hex*>& b)
00148 {
00149   std::set<Hex*> result;
00150   std::set_difference(
00151     a.begin(),a.end(),
00152     b.begin(),b.end(),
00153     std::inserter(result,result.end())
00154   );
00155   return result;
00156 }
00157 
00158 
00159 std::set<Hex*>
00160 set_intersection(const std::set<Hex*>& a, const std::set<Hex*>& b)
00161 {
00162   std::set<Hex*> result;
00163   std::set_intersection(
00164     a.begin(),a.end(),
00165     b.begin(),b.end(),
00166     std::inserter(result,result.end())
00167   );
00168   return result;
00169 }
00170 
00171 
00172 std::set<Hex*>
00173 set_union(const std::set<Hex*>& a, const std::set<Hex*>& b)
00174 {
00175   std::set<Hex*> result;
00176   std::set_union(
00177     a.begin(),a.end(),
00178     b.begin(),b.end(),
00179     std::inserter(result,result.end())
00180   );
00181   return result;
00182 }
00183 
00184 
00185 std::string
00186 set_str(const std::set<Hex*>& a)
00187 {
00188   std::ostringstream ss;
00189   for(std::set<Hex*>::const_iterator h=a.begin(); h!=a.end(); ++h)
00190       ss<<(**h).str()<<" ";
00191   return ss.str();
00192 }
00193 
00194 
00195 bool
00196 bounding_box(const std::set<Hex*>& a, int& i0, int& j0, int& i1, int& j1)
00197 {
00198   for(std::set<Hex*>::const_iterator h=a.begin(); h!=a.end(); ++h)
00199   {
00200     if(h==a.begin())
00201     {
00202       i0 = i1 = (**h).i;
00203       j0 = j1 = (**h).j;
00204     }
00205     else
00206     {
00207       i0 = std::min(i0,(**h).i);
00208       j0 = std::min(j0,(**h).j);
00209       i1 = std::max(i1,(**h).i);
00210       j1 = std::max(j1,(**h).j);
00211     }
00212   }
00213   return !a.empty();
00214 }
00215 
00216 
00217 Area
00218 fill(const std::set<Hex*>& beyond, Hex* h)
00219 {
00220   return fill( beyond, Area(h) );
00221 }
00222 
00223 
00224 Area
00225 fill(const std::set<Hex*>& beyond, const Area& a)
00226 {
00227   std::set<Hex*> queue   =a.hexes();
00228   std::set<Hex*> result  =a.hexes();
00229   while(!queue.empty())
00230   {
00231     Hex* h = *queue.begin();
00232     queue.erase( queue.begin() );
00233     for(int d=0; d<DIRECTIONS; ++d)
00234     {
00235       Hex* hd =h->go(A+d);
00236       if(!beyond.count(hd) && !result.count(hd))
00237       {
00238         queue.insert(hd);
00239         result.insert(hd);
00240       }
00241     }
00242   }
00243   return result;
00244 }
00245 
00246 
00248 inline std::set<Hex*>
00249 extract_connected_set(std::set<Hex*>& s)
00250 {
00251   std::set<Hex*> result;
00252   std::set<Hex*> queue; // Hexes in result that have not yet been checked.
00253   Hex* h =*s.begin(); // Just pick a random hex in s.
00254   while(true)
00255   {
00256     result.insert(h);
00257     s.erase(h);
00258     if(s.empty())
00259         break; // optimisation - not strictly necessary.
00260     std::set<Hex*> range1 =set_intersection( s, range(h,1) );
00261     queue.insert( range1.begin(), range1.end() );
00262     if(queue.empty())
00263         break;
00264     h = *queue.begin();
00265     queue.erase( queue.begin() );
00266   }
00267   return result;
00268 }
00269 
00270 
00271 std::list<Area>
00272 areas(const std::set<Hex*>& s)
00273 {
00274   std::set<Hex*> unallocated = s;
00275   std::list<Area> result;
00276   while(!unallocated.empty())
00277   {
00278     result.push_back( extract_connected_set(unallocated) );
00279   }
00280   return result;
00281 }
00282 
00283 
00284 bool
00285 is_connected(const std::set<Hex*>& s)
00286 {
00287   std::set<Hex*> unallocated = s;
00288   extract_connected_set( unallocated );
00289   return unallocated.empty();
00290 }
00291 
00292 
00293 std::list<Boundary>
00294 skeleton(const std::list<Area>& a, bool include_boundary)
00295 {
00296   std::list<Boundary> result;
00297   for(std::list<Area>::const_iterator iter=a.begin(); iter!=a.end(); ++iter)
00298   {
00299     std::list<Boundary> b =iter->skeleton(include_boundary);
00300     std::copy(b.begin(),b.end(),inserter(result,result.end()));
00301   }
00302   return result;
00303 }
00304 
00305 
00306 } // end namespace hex

Generated on Thu Feb 21 00:00:54 2008 for libhex by  doxygen 1.5.1