nel/src/misc/algo.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "stdmisc.h"
  18
  19 #include "nel/misc/algo.h"
  20
  21
  22 using   namespace std;
  23
  24 #ifdef DEBUG_NEW
  25         #define new DEBUG_NEW
  26 #endif
  27
  28 namespace NLMISC
  29 {
  30
  31 bool            testWildCard(const std::string &strIn, const std::string &wildCard)
  32 {
  33         return testWildCard(strIn.c_str(), wildCard.c_str());
  34 }
  35
  36
  37 // ***************************************************************************
  38 bool            testWildCard(const char *strIn, const char *wildCard)
  39 {
  40         // run the 2 string in //el
  41         while(*wildCard!=0 && *strIn!=0)
  42         {
  43                 // if same char, continue.
  44                 if(*wildCard==*strIn)
  45                 {
  46                         wildCard++;
  47                         strIn++;
  48                 }
  49                 // if wildCard is ?, continue
  50                 else if(*wildCard=='?')
  51                 {
  52                         wildCard++;
  53                         strIn++;
  54                 }
  55                 // if wildcard is *, recurs check.
  56                 else if(*wildCard=='*')
  57                 {
  58                         wildCard++;
  59                         // if last *, its OK.
  60                         if(*wildCard==0)
  61                                 return true;
  62                         // else must check next strings.
  63                         else
  64                         {
  65                                 // build the wilcard token. eg from "*pipo?", take "pipo"
  66                                 string  token;
  67                                 while(*wildCard!='*' && *wildCard!='?' && *wildCard!=0)
  68                                 {
  69                                         token+= *wildCard;
  70                                         wildCard++;
  71                                 }
  72                                 // if token size is empty, error
  73                                 if(token.empty())
  74                                         return false;
  75
  76                                 // in strIn, search all the occurence of token. For each solution, recurs test.
  77                                 string  sCopy= strIn;
  78                                 string::size_type pos= sCopy.find(token, 0);
  79                                 while(pos!=string::npos)
  80                                 {
  81                                         // do a testWildCard test on the remaining string/wildCard
  82                                         if( testWildCard(strIn+pos+token.size(), wildCard) )
  83                                                 // if succeed, end
  84                                                 return true;
  85                                         // fails=> test with another occurence of token in the string.
  86                                         pos= sCopy.find(token, pos+1);
  87                                 }
  88
  89                                 // if all failed, fail
  90                                 return false;
  91                         }
  92                 }
  93                 // else fail
  94                 else
  95                         return false;
  96         }
  97
  98         // If quit here because end Of 2 strs, OK.
  99         if(*wildCard==0 && *strIn==0)
 100                 return true;
 101         // if quit here because wildCard=="*" and s="", OK too.
 102         if(*strIn==0 && wildCard[0]=='*' && wildCard[1]==0)
 103                 return true;
 104
 105         /*
 106                 Else false:
 107                         It may be wildCard="?aez" and s="" => error
 108                         It may be wildCard="" and s="aer" => error
 109         */
 110         return false;
 111 }
 112
 113
 114 // ***************************************************************************
 115 void            splitString(const std::string &str, const std::string &separator, std::vector<std::string> &retList)
 116 {
 117         string::size_type pos=0;
 118         string::size_type newPos=0;
 119         retList.clear();
 120         while( (newPos= str.find(separator,pos)) != string::npos)
 121         {
 122                 // if not empty sub str. (skip repetition of separator )
 123                 if(newPos-pos>0)
 124                         retList.push_back(str.substr(pos, newPos-pos));
 125                 // skip token
 126                 pos= newPos+separator.size();
 127         }
 128         // copy the last substr
 129         if( pos<str.size() )
 130                 retList.push_back(str.substr(pos, str.size()-pos));
 131 }
 132
 133
 134 // ***************************************************************************
 135 void            splitUCString(const ucstring &ucstr, const ucstring &separator, std::vector<ucstring> &retList)
 136 {
 137         ucstring::size_type pos=0;
 138         ucstring::size_type newPos=0;
 139         retList.clear();
 140         while( (newPos= ucstr.find(separator,pos)) != ucstring::npos)
 141         {
 142                 // if not empty sub str. (skip repetition of separator )
 143                 if(newPos-pos>0)
 144                         retList.push_back(ucstr.substr(pos, newPos-pos));
 145                 // skip token
 146                 pos= newPos+separator.size();
 147         }
 148         // copy the last substr
 149         if( pos<ucstr.size() )
 150                 retList.push_back(ucstr.substr(pos, ucstr.size()-pos));
 151 }
 152
 153 // ***************************************************************************
 154
 155 void drawFullLine (float x0, float y0, float x1, float y1, std::vector<std::pair<sint, sint> > &result)
 156 {
 157         result.clear ();
 158         // x0 must be < x1
 159         float dx = (float) fabs (x0-x1);
 160         float dy = (float) fabs (y0-y1);
 161         if ((dx == 0) && (dy == 0))
 162                 result.push_back (pair<sint, sint> ((sint)floor (x0), (sint)floor (y0)));
 163         else if (dx > dy)
 164         {
 165                 if (x0 > x1)
 166                 {
 167                         // Xchg 0 and 1
 168                         float temp = x0;
 169                         x0 = x1;
 170                         x1 = temp;
 171                         temp = y0;
 172                         y0 = y1;
 173                         y1 = temp;
 174                 }
 175
 176                 float deltaX = x1 - x0;
 177                 const float deltaY = (y1-y0)/deltaX;
 178
 179                 // Current integer pixel
 180                 sint currentX = (sint)floor (x0);
 181                 sint currentY = (sint)floor (y0);
 182
 183                 while (deltaX >= 0)
 184                 {
 185                         // Next point
 186                         sint previousY = currentY;
 187
 188                         // Next y0
 189                         if (deltaX > 1)
 190                                 y0 += deltaY;
 191                         else
 192                                 y0 += deltaX * deltaY;
 193
 194                         deltaX -= 1;
 195
 196                         currentY = (sint)y0;
 197
 198                         // Add point
 199                         if (currentY<=previousY)
 200                         {
 201                                 do
 202                                 {
 203                                         result.push_back (pair<sint, sint> (currentX, previousY));
 204                                         previousY--;
 205                                 }
 206                                 while (currentY<=previousY);
 207                         }
 208                         else
 209                         {
 210                                 do
 211                                 {
 212                                         result.push_back (pair<sint, sint> (currentX, previousY));
 213                                         previousY++;
 214                                 }
 215                                 while (currentY>=previousY);
 216                         }
 217
 218                         // Next X
 219                         currentX++;
 220                 }
 221         }
 222         else
 223         {
 224                 if (y0 > y1)
 225                 {
 226                         // Xchg 0 and 1
 227                         float temp = y0;
 228                         y0 = y1;
 229                         y1 = temp;
 230                         temp = x0;
 231                         x0 = x1;
 232                         x1 = temp;
 233                 }
 234
 235                 float deltaY = y1 - y0;
 236                 const float deltaX = (x1-x0)/deltaY;
 237
 238                 // Current integer pixel
 239                 sint currentY = (sint)floor (y0);
 240                 sint currentX = (sint)floor (x0);
 241
 242                 while (deltaY >= 0)
 243                 {
 244                         // Next point
 245                         sint previousX = currentX;
 246
 247                         // Next x0
 248                         if (deltaY > 1)
 249                                 x0 += deltaX;
 250                         else
 251                                 x0 += deltaY * deltaX;
 252
 253                         deltaY -= 1;
 254
 255                         currentX = (sint)x0;
 256
 257                         // Add point
 258                         if (currentX<=previousX)
 259                         {
 260                                 do
 261                                 {
 262                                         result.push_back (pair<sint, sint> (previousX, currentY));
 263                                         previousX--;
 264                                 }
 265                                 while (currentX<=previousX);
 266                         }
 267                         else
 268                         {
 269                                 do
 270                                 {
 271                                         result.push_back (pair<sint, sint> (previousX, currentY));
 272                                         previousX++;
 273                                 }
 274                                 while (currentX>=previousX);
 275                         }
 276
 277                         // Next Y
 278                         currentY++;
 279                 }
 280         }
 281 }
 282
 283 // ***************************************************************************
 284
 285 void drawLine (float x0, float y0, float x1, float y1, vector<pair<sint, sint> > &result)
 286 {
 287         float   dx = (float)(floor(x1+0.5) - floor(x0+0.5));
 288         float   dy = (float)(floor(y1+0.5) - floor(y0+0.5));
 289
 290         float   rdx = x1-x0;
 291         float   rdy = y1-y0;
 292
 293         sint    d = (sint)std::max(fabs(dx), fabs(dy));
 294         float   maxd = (float)(std::max(fabs(rdx), fabs(rdy)));
 295
 296         rdx /= maxd;
 297         rdy /= maxd;
 298
 299         for (; d>=0; --d)
 300         {
 301                 result.push_back(make_pair<sint,sint>((sint)floor(x0+0.5), (sint)floor(y0+0.5)));
 302
 303                 x0 += rdx;
 304                 y0 += rdy;
 305         }
 306 }
 307
 308 // ***************************************************************************
 309
 310 } // NLMISC