src/craftdef.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "craftdef.h"
  21
  22 #include "irrlichttypes.h"
  23 #include "log.h"
  24 #include <sstream>
  25 #include <set>
  26 #include <algorithm>
  27 #include "gamedef.h"
  28 #include "inventory.h"
  29 #include "util/serialize.h"
  30 #include "util/string.h"
  31 #include "util/numeric.h"
  32 #include "util/strfnd.h"
  33 #include "exceptions.h"
  34
  35 inline bool isGroupRecipeStr(const std::string &rec_name)
  36 {
  37         return str_starts_with(rec_name, std::string("group:"));
  38 }
  39
  40 inline u64 getHashForString(const std::string &recipe_str)
  41 {
  42         /*errorstream << "Hashing craft string  \"" << recipe_str << '"';*/
  43         return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef);
  44 }
  45
  46 static u64 getHashForGrid(CraftHashType type, const std::vector<std::string> &grid_names)
  47 {
  48         switch (type) {
  49                 case CRAFT_HASH_TYPE_ITEM_NAMES: {
  50                         std::ostringstream os;
  51                         bool is_first = true;
  52                         for (size_t i = 0; i < grid_names.size(); i++) {
  53                                 if (grid_names[i] != "") {
  54                                         os << (is_first ? "" : "\n") << grid_names[i];
  55                                         is_first = false;
  56                                 }
  57                         }
  58                         return getHashForString(os.str());
  59                 } case CRAFT_HASH_TYPE_COUNT: {
  60                         u64 cnt = 0;
  61                         for (size_t i = 0; i < grid_names.size(); i++)
  62                                 if (grid_names[i] != "")
  63                                         cnt++;
  64                         return cnt;
  65                 } case CRAFT_HASH_TYPE_UNHASHED:
  66                         return 0;
  67         }
  68         // invalid CraftHashType
  69         assert(false);
  70         return 0;
  71 }
  72
  73 // Check if input matches recipe
  74 // Takes recipe groups into account
  75 static bool inputItemMatchesRecipe(const std::string &inp_name,
  76                 const std::string &rec_name, IItemDefManager *idef)
  77 {
  78         // Exact name
  79         if (inp_name == rec_name)
  80                 return true;
  81
  82         // Group
  83         if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) {
  84                 const struct ItemDefinition &def = idef->get(inp_name);
  85                 Strfnd f(rec_name.substr(6));
  86                 bool all_groups_match = true;
  87                 do {
  88                         std::string check_group = f.next(",");
  89                         if (itemgroup_get(def.groups, check_group) == 0) {
  90                                 all_groups_match = false;
  91                                 break;
  92                         }
  93                 } while (!f.at_end());
  94                 if (all_groups_match)
  95                         return true;
  96         }
  97
  98         // Didn't match
  99         return false;
 100 }
 101
 102 // Deserialize an itemstring then return the name of the item
 103 static std::string craftGetItemName(const std::string &itemstring, IGameDef *gamedef)
 104 {
 105         ItemStack item;
 106         item.deSerialize(itemstring, gamedef->idef());
 107         return item.name;
 108 }
 109
 110 // (mapcar craftGetItemName itemstrings)
 111 static std::vector<std::string> craftGetItemNames(
 112                 const std::vector<std::string> &itemstrings, IGameDef *gamedef)
 113 {
 114         std::vector<std::string> result;
 115         for (std::vector<std::string>::size_type i = 0;
 116                         i < itemstrings.size(); i++) {
 117                 result.push_back(craftGetItemName(itemstrings[i], gamedef));
 118         }
 119         return result;
 120 }
 121
 122 // Get name of each item, and return them as a new list.
 123 static std::vector<std::string> craftGetItemNames(
 124                 const std::vector<ItemStack> &items, IGameDef *gamedef)
 125 {
 126         std::vector<std::string> result;
 127         for (std::vector<ItemStack>::size_type i = 0;
 128                         i < items.size(); i++) {
 129                 result.push_back(items[i].name);
 130         }
 131         return result;
 132 }
 133
 134 // convert a list of item names, to ItemStacks.
 135 static std::vector<ItemStack> craftGetItems(
 136                 const std::vector<std::string> &items, IGameDef *gamedef)
 137 {
 138         std::vector<ItemStack> result;
 139         for (std::vector<std::string>::size_type i = 0;
 140                         i < items.size(); i++) {
 141                 result.push_back(ItemStack(std::string(items[i]), (u16)1,
 142                         (u16)0, "", gamedef->getItemDefManager()));
 143         }
 144         return result;
 145 }
 146
 147 // Compute bounding rectangle given a matrix of items
 148 // Returns false if every item is ""
 149 static bool craftGetBounds(const std::vector<std::string> &items, unsigned int width,
 150                 unsigned int &min_x, unsigned int &max_x,
 151                 unsigned int &min_y, unsigned int &max_y)
 152 {
 153         bool success = false;
 154         unsigned int x = 0;
 155         unsigned int y = 0;
 156         for (std::vector<std::string>::size_type i = 0;
 157                         i < items.size(); i++) {
 158                 // Is this an actual item?
 159                 if (items[i] != "") {
 160                         if (!success) {
 161                                 // This is the first nonempty item
 162                                 min_x = max_x = x;
 163                                 min_y = max_y = y;
 164                                 success = true;
 165                         } else {
 166                                 if (x < min_x) min_x = x;
 167                                 if (x > max_x) max_x = x;
 168                                 if (y < min_y) min_y = y;
 169                                 if (y > max_y) max_y = y;
 170                         }
 171                 }
 172
 173                 // Step coordinate
 174                 x++;
 175                 if (x == width) {
 176                         x = 0;
 177                         y++;
 178                 }
 179         }
 180         return success;
 181 }
 182
 183 // Removes 1 from each item stack
 184 static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 185 {
 186         for (std::vector<ItemStack>::size_type i = 0;
 187                         i < input.items.size(); i++) {
 188                 if (input.items[i].count != 0)
 189                         input.items[i].remove(1);
 190         }
 191 }
 192
 193 // Removes 1 from each item stack with replacement support
 194 // Example: if replacements contains the pair ("bucket:bucket_water", "bucket:bucket_empty"),
 195 //   a water bucket will not be removed but replaced by an empty bucket.
 196 static void craftDecrementOrReplaceInput(CraftInput &input,
 197                 std::vector<ItemStack> &output_replacements,
 198                 const CraftReplacements &replacements,
 199                 IGameDef *gamedef)
 200 {
 201         if (replacements.pairs.empty()) {
 202                 craftDecrementInput(input, gamedef);
 203                 return;
 204         }
 205
 206         // Make a copy of the replacements pair list
 207         std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;
 208
 209         for (std::vector<ItemStack>::size_type i = 0;
 210                         i < input.items.size(); i++) {
 211                 ItemStack &item = input.items[i];
 212                 // Find an appropriate replacement
 213                 bool found_replacement = false;
 214                 for (std::vector<std::pair<std::string, std::string> >::iterator
 215                                 j = pairs.begin();
 216                                 j != pairs.end(); ++j) {
 217                         if (inputItemMatchesRecipe(item.name, j->first, gamedef->idef())) {
 218                                 if (item.count == 1) {
 219                                         item.deSerialize(j->second, gamedef->idef());
 220                                         found_replacement = true;
 221                                         pairs.erase(j);
 222                                         break;
 223                                 } else {
 224                                         ItemStack rep;
 225                                         rep.deSerialize(j->second, gamedef->idef());
 226                                         item.remove(1);
 227                                         found_replacement = true;
 228                                         output_replacements.push_back(rep);
 229                                         break;
 230                                 }
 231                         }
 232                 }
 233                 // No replacement was found, simply decrement count by one
 234                 if (!found_replacement && item.count > 0)
 235                         item.remove(1);
 236         }
 237 }
 238
 239 // Dump an itemstring matrix
 240 static std::string craftDumpMatrix(const std::vector<std::string> &items,
 241                 unsigned int width)
 242 {
 243         std::ostringstream os(std::ios::binary);
 244         os << "{ ";
 245         unsigned int x = 0;
 246         for(std::vector<std::string>::size_type i = 0;
 247                         i < items.size(); i++, x++) {
 248                 if (x == width) {
 249                         os << "; ";
 250                         x = 0;
 251                 } else if (x != 0) {
 252                         os << ",";
 253                 }
 254                 os << '"' << items[i] << '"';
 255         }
 256         os << " }";
 257         return os.str();
 258 }
 259
 260 // Dump an item matrix
 261 std::string craftDumpMatrix(const std::vector<ItemStack> &items,
 262                 unsigned int width)
 263 {
 264         std::ostringstream os(std::ios::binary);
 265         os << "{ ";
 266         unsigned int x = 0;
 267         for (std::vector<ItemStack>::size_type i = 0;
 268                         i < items.size(); i++, x++) {
 269                 if (x == width) {
 270                         os << "; ";
 271                         x = 0;
 272                 } else if (x != 0) {
 273                         os << ",";
 274                 }
 275                 os << '"' << (items[i].getItemString()) << '"';
 276         }
 277         os << " }";
 278         return os.str();
 279 }
 280
 281
 282 /*
 283         CraftInput
 284 */
 285
 286 std::string CraftInput::dump() const
 287 {
 288         std::ostringstream os(std::ios::binary);
 289         os << "(method=" << ((int)method) << ", items="
 290                 << craftDumpMatrix(items, width) << ")";
 291         return os.str();
 292 }
 293
 294 /*
 295         CraftOutput
 296 */
 297
 298 std::string CraftOutput::dump() const
 299 {
 300         std::ostringstream os(std::ios::binary);
 301         os << "(item=\"" << item << "\", time=" << time << ")";
 302         return os.str();
 303 }
 304
 305 /*
 306         CraftReplacements
 307 */
 308
 309 std::string CraftReplacements::dump() const
 310 {
 311         std::ostringstream os(std::ios::binary);
 312         os<<"{";
 313         const char *sep = "";
 314         for (std::vector<std::pair<std::string, std::string> >::size_type i = 0;
 315                         i < pairs.size(); i++) {
 316                 const std::pair<std::string, std::string> &repl_p = pairs[i];
 317                 os << sep
 318                         << '"' << (repl_p.first)
 319                         << "\"=>\"" << (repl_p.second) << '"';
 320                 sep = ",";
 321         }
 322         os << "}";
 323         return os.str();
 324 }
 325
 326 /*
 327         CraftDefinitionShaped
 328 */
 329
 330 std::string CraftDefinitionShaped::getName() const
 331 {
 332         return "shaped";
 333 }
 334
 335 bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
 336 {
 337         if (input.method != CRAFT_METHOD_NORMAL)
 338                 return false;
 339
 340         // Get input item matrix
 341         std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
 342         unsigned int inp_width = input.width;
 343         if (inp_width == 0)
 344                 return false;
 345         while (inp_names.size() % inp_width != 0)
 346                 inp_names.push_back("");
 347
 348         // Get input bounds
 349         unsigned int inp_min_x = 0, inp_max_x = 0, inp_min_y = 0, inp_max_y = 0;
 350         if (!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x,
 351                         inp_min_y, inp_max_y))
 352                 return false;  // it was empty
 353
 354         std::vector<std::string> rec_names;
 355         if (hash_inited)
 356                 rec_names = recipe_names;
 357         else
 358                 rec_names = craftGetItemNames(recipe, gamedef);
 359
 360         // Get recipe item matrix
 361         unsigned int rec_width = width;
 362         if (rec_width == 0)
 363                 return false;
 364         while (rec_names.size() % rec_width != 0)
 365                 rec_names.push_back("");
 366
 367         // Get recipe bounds
 368         unsigned int rec_min_x=0, rec_max_x=0, rec_min_y=0, rec_max_y=0;
 369         if (!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x,
 370                         rec_min_y, rec_max_y))
 371                 return false;  // it was empty
 372
 373         // Different sizes?
 374         if (inp_max_x - inp_min_x != rec_max_x - rec_min_x ||
 375                         inp_max_y - inp_min_y != rec_max_y - rec_min_y)
 376                 return false;
 377
 378         // Verify that all item names in the bounding box are equal
 379         unsigned int w = inp_max_x - inp_min_x + 1;
 380         unsigned int h = inp_max_y - inp_min_y + 1;
 381
 382         for (unsigned int y=0; y < h; y++) {
 383                 unsigned int inp_y = (inp_min_y + y) * inp_width;
 384                 unsigned int rec_y = (rec_min_y + y) * rec_width;
 385
 386                 for (unsigned int x=0; x < w; x++) {
 387                         unsigned int inp_x = inp_min_x + x;
 388                         unsigned int rec_x = rec_min_x + x;
 389
 390                         if (!inputItemMatchesRecipe(
 391                                         inp_names[inp_y + inp_x],
 392                                         rec_names[rec_y + rec_x], gamedef->idef())) {
 393                                 return false;
 394                         }
 395                 }
 396         }
 397
 398         return true;
 399 }
 400
 401 CraftOutput CraftDefinitionShaped::getOutput(const CraftInput &input, IGameDef *gamedef) const
 402 {
 403         return CraftOutput(output, 0);
 404 }
 405
 406 CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *gamedef) const
 407 {
 408         return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
 409 }
 410
 411 void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 412          IGameDef *gamedef) const
 413 {
 414         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 415 }
 416
 417 CraftHashType CraftDefinitionShaped::getHashType() const
 418 {
 419         assert(hash_inited); // Pre-condition
 420         bool has_group = false;
 421         for (size_t i = 0; i < recipe_names.size(); i++) {
 422                 if (isGroupRecipeStr(recipe_names[i])) {
 423                         has_group = true;
 424                         break;
 425                 }
 426         }
 427         if (has_group)
 428                 return CRAFT_HASH_TYPE_COUNT;
 429         else
 430                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 431 }
 432
 433 u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 434 {
 435         assert(hash_inited); // Pre-condition
 436         assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
 437                 || (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
 438
 439         std::vector<std::string> rec_names = recipe_names;
 440         std::sort(rec_names.begin(), rec_names.end());
 441         return getHashForGrid(type, rec_names);
 442 }
 443
 444 void CraftDefinitionShaped::initHash(IGameDef *gamedef)
 445 {
 446         if (hash_inited)
 447                 return;
 448         hash_inited = true;
 449         recipe_names = craftGetItemNames(recipe, gamedef);
 450 }
 451
 452 std::string CraftDefinitionShaped::dump() const
 453 {
 454         std::ostringstream os(std::ios::binary);
 455         os << "(shaped, output=\"" << output
 456                 << "\", recipe=" << craftDumpMatrix(recipe, width)
 457                 << ", replacements=" << replacements.dump() << ")";
 458         return os.str();
 459 }
 460
 461 /*
 462         CraftDefinitionShapeless
 463 */
 464
 465 std::string CraftDefinitionShapeless::getName() const
 466 {
 467         return "shapeless";
 468 }
 469
 470 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 471 {
 472         if (input.method != CRAFT_METHOD_NORMAL)
 473                 return false;
 474
 475         // Filter empty items out of input
 476         std::vector<std::string> input_filtered;
 477         for (std::vector<ItemStack>::size_type i = 0;
 478                         i < input.items.size(); i++) {
 479                 const ItemStack &item = input.items[i];
 480                 if (item.name != "")
 481                         input_filtered.push_back(item.name);
 482         }
 483
 484         // If there is a wrong number of items in input, no match
 485         if (input_filtered.size() != recipe.size()) {
 486                 /*dstream<<"Number of input items ("<<input_filtered.size()
 487                                 <<") does not match recipe size ("<<recipe.size()<<") "
 488                                 <<"of recipe with output="<<output<<std::endl;*/
 489                 return false;
 490         }
 491
 492         std::vector<std::string> recipe_copy;
 493         if (hash_inited)
 494                 recipe_copy = recipe_names;
 495         else {
 496                 recipe_copy = craftGetItemNames(recipe, gamedef);
 497                 std::sort(recipe_copy.begin(), recipe_copy.end());
 498         }
 499
 500         // Try with all permutations of the recipe,
 501         // start from the lexicographically first permutation (=sorted),
 502         // recipe_names is pre-sorted
 503         do {
 504                 // If all items match, the recipe matches
 505                 bool all_match = true;
 506                 //dstream<<"Testing recipe (output="<<output<<"):";
 507                 for (size_t i=0; i<recipe.size(); i++) {
 508                         //dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
 509                         if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
 510                                         gamedef->idef())) {
 511                                 all_match = false;
 512                                 break;
 513                         }
 514                 }
 515                 //dstream<<" -> match="<<all_match<<std::endl;
 516                 if (all_match)
 517                         return true;
 518         } while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
 519
 520         return false;
 521 }
 522
 523 CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
 524 {
 525         return CraftOutput(output, 0);
 526 }
 527
 528 CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 529 {
 530         return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 531 }
 532
 533 void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 534         IGameDef *gamedef) const
 535 {
 536         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 537 }
 538
 539 CraftHashType CraftDefinitionShapeless::getHashType() const
 540 {
 541         assert(hash_inited); // Pre-condition
 542         bool has_group = false;
 543         for (size_t i = 0; i < recipe_names.size(); i++) {
 544                 if (isGroupRecipeStr(recipe_names[i])) {
 545                         has_group = true;
 546                         break;
 547                 }
 548         }
 549         if (has_group)
 550                 return CRAFT_HASH_TYPE_COUNT;
 551         else
 552                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 553 }
 554
 555 u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 556 {
 557         assert(hash_inited); // Pre-condition
 558         assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
 559                 || type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
 560         return getHashForGrid(type, recipe_names);
 561 }
 562
 563 void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
 564 {
 565         if (hash_inited)
 566                 return;
 567         hash_inited = true;
 568         recipe_names = craftGetItemNames(recipe, gamedef);
 569         std::sort(recipe_names.begin(), recipe_names.end());
 570 }
 571
 572 std::string CraftDefinitionShapeless::dump() const
 573 {
 574         std::ostringstream os(std::ios::binary);
 575         os << "(shapeless, output=\"" << output
 576                 << "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
 577                 << ", replacements=" << replacements.dump() << ")";
 578         return os.str();
 579 }
 580
 581 /*
 582         CraftDefinitionToolRepair
 583 */
 584
 585 static ItemStack craftToolRepair(
 586                 const ItemStack &item1,
 587                 const ItemStack &item2,
 588                 float additional_wear,
 589                 IGameDef *gamedef)
 590 {
 591         IItemDefManager *idef = gamedef->idef();
 592         if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
 593                         || idef->get(item1.name).type != ITEM_TOOL
 594                         || idef->get(item2.name).type != ITEM_TOOL) {
 595                 // Failure
 596                 return ItemStack();
 597         }
 598
 599         s32 item1_uses = 65536 - (u32) item1.wear;
 600         s32 item2_uses = 65536 - (u32) item2.wear;
 601         s32 new_uses = item1_uses + item2_uses;
 602         s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
 603         if (new_wear >= 65536)
 604                 return ItemStack();
 605         if (new_wear < 0)
 606                 new_wear = 0;
 607
 608         ItemStack repaired = item1;
 609         repaired.wear = new_wear;
 610         return repaired;
 611 }
 612
 613 std::string CraftDefinitionToolRepair::getName() const
 614 {
 615         return "toolrepair";
 616 }
 617
 618 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 619 {
 620         if (input.method != CRAFT_METHOD_NORMAL)
 621                 return false;
 622
 623         ItemStack item1;
 624         ItemStack item2;
 625         for (std::vector<ItemStack>::size_type i = 0;
 626                         i < input.items.size(); i++) {
 627                 const ItemStack &item = input.items[i];
 628                 if (!item.empty()) {
 629                         if (item1.empty())
 630                                 item1 = item;
 631                         else if (item2.empty())
 632                                 item2 = item;
 633                         else
 634                                 return false;
 635                 }
 636         }
 637         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 638         return !repaired.empty();
 639 }
 640
 641 CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameDef *gamedef) const
 642 {
 643         ItemStack item1;
 644         ItemStack item2;
 645         for (std::vector<ItemStack>::size_type i = 0;
 646                         i < input.items.size(); i++) {
 647                 const ItemStack &item = input.items[i];
 648                 if (!item.empty()) {
 649                         if (item1.empty())
 650                                 item1 = item;
 651                         else if (item2.empty())
 652                                 item2 = item;
 653                 }
 654         }
 655         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 656         return CraftOutput(repaired.getItemString(), 0);
 657 }
 658
 659 CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
 660 {
 661         std::vector<ItemStack> stack;
 662         stack.push_back(ItemStack());
 663         return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
 664 }
 665
 666 void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 667         IGameDef *gamedef) const
 668 {
 669         craftDecrementInput(input, gamedef);
 670 }
 671
 672 std::string CraftDefinitionToolRepair::dump() const
 673 {
 674         std::ostringstream os(std::ios::binary);
 675         os << "(toolrepair, additional_wear=" << additional_wear << ")";
 676         return os.str();
 677 }
 678
 679 /*
 680         CraftDefinitionCooking
 681 */
 682
 683 std::string CraftDefinitionCooking::getName() const
 684 {
 685         return "cooking";
 686 }
 687
 688 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 689 {
 690         if (input.method != CRAFT_METHOD_COOKING)
 691                 return false;
 692
 693         // Filter empty items out of input
 694         std::vector<std::string> input_filtered;
 695         for (std::vector<ItemStack>::size_type i = 0;
 696                         i < input.items.size(); i++) {
 697                 const std::string &name = input.items[i].name;
 698                 if (name != "")
 699                         input_filtered.push_back(name);
 700         }
 701
 702         // If there is a wrong number of items in input, no match
 703         if (input_filtered.size() != 1) {
 704                 /*dstream<<"Number of input items ("<<input_filtered.size()
 705                                 <<") does not match recipe size (1) "
 706                                 <<"of cooking recipe with output="<<output<<std::endl;*/
 707                 return false;
 708         }
 709
 710         // Check the single input item
 711         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 712 }
 713
 714 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
 715 {
 716         return CraftOutput(output, cooktime);
 717 }
 718
 719 CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
 720 {
 721         std::vector<std::string> rec;
 722         rec.push_back(recipe);
 723         return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 724 }
 725
 726 void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 727         IGameDef *gamedef) const
 728 {
 729         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 730 }
 731
 732 CraftHashType CraftDefinitionCooking::getHashType() const
 733 {
 734         if (isGroupRecipeStr(recipe_name))
 735                 return CRAFT_HASH_TYPE_COUNT;
 736         else
 737                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 738 }
 739
 740 u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 741 {
 742         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 743                 return getHashForString(recipe_name);
 744         } else if (type == CRAFT_HASH_TYPE_COUNT) {
 745                 return 1;
 746         } else {
 747                 //illegal hash type for this CraftDefinition (pre-condition)
 748                 assert(false);
 749                 return 0;
 750         }
 751 }
 752
 753 void CraftDefinitionCooking::initHash(IGameDef *gamedef)
 754 {
 755         if (hash_inited)
 756                 return;
 757         hash_inited = true;
 758         recipe_name = craftGetItemName(recipe, gamedef);
 759 }
 760
 761 std::string CraftDefinitionCooking::dump() const
 762 {
 763         std::ostringstream os(std::ios::binary);
 764         os << "(cooking, output=\"" << output
 765                 << "\", recipe=\"" << recipe
 766                 << "\", cooktime=" << cooktime << ")"
 767                 << ", replacements=" << replacements.dump() << ")";
 768         return os.str();
 769 }
 770
 771 /*
 772         CraftDefinitionFuel
 773 */
 774
 775 std::string CraftDefinitionFuel::getName() const
 776 {
 777         return "fuel";
 778 }
 779
 780 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 781 {
 782         if (input.method != CRAFT_METHOD_FUEL)
 783                 return false;
 784
 785         // Filter empty items out of input
 786         std::vector<std::string> input_filtered;
 787         for (std::vector<ItemStack>::size_type i = 0;
 788                         i < input.items.size(); i++) {
 789                 const std::string &name = input.items[i].name;
 790                 if (name != "")
 791                         input_filtered.push_back(name);
 792         }
 793
 794         // If there is a wrong number of items in input, no match
 795         if (input_filtered.size() != 1) {
 796                 /*dstream<<"Number of input items ("<<input_filtered.size()
 797                                 <<") does not match recipe size (1) "
 798                                 <<"of fuel recipe with burntime="<<burntime<<std::endl;*/
 799                 return false;
 800         }
 801
 802         // Check the single input item
 803         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 804 }
 805
 806 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
 807 {
 808         return CraftOutput("", burntime);
 809 }
 810
 811 CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
 812 {
 813         std::vector<std::string> rec;
 814         rec.push_back(recipe);
 815         return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 816 }
 817
 818 void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 819         IGameDef *gamedef) const
 820 {
 821         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 822 }
 823
 824 CraftHashType CraftDefinitionFuel::getHashType() const
 825 {
 826         if (isGroupRecipeStr(recipe_name))
 827                 return CRAFT_HASH_TYPE_COUNT;
 828         else
 829                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 830 }
 831
 832 u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 833 {
 834         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 835                 return getHashForString(recipe_name);
 836         } else if (type == CRAFT_HASH_TYPE_COUNT) {
 837                 return 1;
 838         } else {
 839                 //illegal hash type for this CraftDefinition (pre-condition)
 840                 assert(false);
 841                 return 0;
 842         }
 843 }
 844
 845 void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 846 {
 847         if (hash_inited)
 848                 return;
 849         hash_inited = true;
 850         recipe_name = craftGetItemName(recipe, gamedef);
 851 }
 852 std::string CraftDefinitionFuel::dump() const
 853 {
 854         std::ostringstream os(std::ios::binary);
 855         os << "(fuel, recipe=\"" << recipe
 856                 << "\", burntime=" << burntime << ")"
 857                 << ", replacements=" << replacements.dump() << ")";
 858         return os.str();
 859 }
 860
 861 /*
 862         Craft definition manager
 863 */
 864
 865 class CCraftDefManager: public IWritableCraftDefManager
 866 {
 867 public:
 868         CCraftDefManager()
 869         {
 870                 m_craft_defs.resize(craft_hash_type_max + 1);
 871         }
 872
 873         virtual ~CCraftDefManager()
 874         {
 875                 clear();
 876         }
 877
 878         virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
 879                         std::vector<ItemStack> &output_replacement, bool decrementInput,
 880                         IGameDef *gamedef) const
 881         {
 882                 output.item = "";
 883                 output.time = 0;
 884
 885                 // If all input items are empty, abort.
 886                 bool all_empty = true;
 887                 for (std::vector<ItemStack>::size_type i = 0;
 888                         i < input.items.size(); i++) {
 889                         if (!input.items[i].empty()) {
 890                                 all_empty = false;
 891                                 break;
 892                         }
 893                 }
 894                 if (all_empty)
 895                         return false;
 896
 897                 std::vector<std::string> input_names;
 898                 input_names = craftGetItemNames(input.items, gamedef);
 899                 std::sort(input_names.begin(), input_names.end());
 900
 901                 // Try hash types with increasing collision rate, and return if found.
 902                 for (int type = 0; type <= craft_hash_type_max; type++) {
 903                         u64 hash = getHashForGrid((CraftHashType) type, input_names);
 904
 905                         /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/
 906
 907                         // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];"
 908                         // but that doesn't compile for some reason. This does.
 909                         std::map<u64, std::vector<CraftDefinition*> >::const_iterator
 910                                 col_iter = (m_craft_defs[type]).find(hash);
 911
 912                         if (col_iter == (m_craft_defs[type]).end())
 913                                 continue;
 914
 915                         const std::vector<CraftDefinition*> &hash_collisions = col_iter->second;
 916                         // Walk crafting definitions from back to front, so that later
 917                         // definitions can override earlier ones.
 918                         for (std::vector<CraftDefinition*>::size_type
 919                                         i = hash_collisions.size(); i > 0; i--) {
 920                                 CraftDefinition *def = hash_collisions[i - 1];
 921
 922                                 /*errorstream << "Checking " << input.dump() << std::endl
 923                                         << " against " << def->dump() << std::endl;*/
 924
 925                                 if (def->check(input, gamedef)) {
 926                                         // Get output, then decrement input (if requested)
 927                                         output = def->getOutput(input, gamedef);
 928                                         if (decrementInput)
 929                                                 def->decrementInput(input, output_replacement, gamedef);
 930                                         /*errorstream << "Check RETURNS TRUE" << std::endl;*/
 931                                         return true;
 932                                 }
 933                         }
 934                 }
 935                 return false;
 936         }
 937
 938         virtual std::vector<CraftDefinition*> getCraftRecipes(CraftOutput &output,
 939                         IGameDef *gamedef, unsigned limit=0) const
 940         {
 941                 std::vector<CraftDefinition*> recipes;
 942
 943                 std::map<std::string, std::vector<CraftDefinition*> >::const_iterator
 944                         vec_iter = m_output_craft_definitions.find(output.item);
 945
 946                 if (vec_iter == m_output_craft_definitions.end())
 947                         return recipes;
 948
 949                 const std::vector<CraftDefinition*> &vec = vec_iter->second;
 950
 951                 recipes.reserve(limit ? MYMIN(limit, vec.size()) : vec.size());
 952
 953                 for (std::vector<CraftDefinition*>::size_type i = vec.size();
 954                                 i > 0; i--) {
 955                         CraftDefinition *def = vec[i - 1];
 956                         if (limit && recipes.size() >= limit)
 957                                 break;
 958                         recipes.push_back(def);
 959                 }
 960
 961                 return recipes;
 962         }
 963
 964         virtual bool clearCraftRecipesByOutput(const CraftOutput &output, IGameDef *gamedef)
 965         {
 966                 std::map<std::string, std::vector<CraftDefinition*> >::iterator vec_iter =
 967                         m_output_craft_definitions.find(output.item);
 968
 969                 if (vec_iter == m_output_craft_definitions.end())
 970                         return false;
 971
 972                 std::vector<CraftDefinition*> &vec = vec_iter->second;
 973                 for (std::vector<CraftDefinition*>::iterator i = vec.begin();
 974                                 i != vec.end(); ++i) {
 975                         CraftDefinition *def = *i;
 976                         // Recipes are not yet hashed at this point
 977                         std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
 978                         std::vector<CraftDefinition*> new_vec_by_input;
 979                         /* We will preallocate necessary memory addresses, so we don't need to reallocate them later.
 980                                 This would save us some performance. */
 981                         new_vec_by_input.reserve(unhashed_inputs_vec.size());
 982                         for (std::vector<CraftDefinition*>::iterator i2 = unhashed_inputs_vec.begin();
 983                                         i2 != unhashed_inputs_vec.end(); ++i2) {
 984                                 if (def != *i2) {
 985                                         new_vec_by_input.push_back(*i2);
 986                                 }
 987                         }
 988                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
 989                 }
 990                 m_output_craft_definitions.erase(output.item);
 991                 return true;
 992         }
 993
 994         virtual bool clearCraftRecipesByInput(CraftMethod craft_method, unsigned int craft_grid_width,
 995                 const std::vector<std::string> &recipe, IGameDef *gamedef)
 996         {
 997                 bool all_empty = true;
 998                 for (std::vector<std::string>::size_type i = 0;
 999                                 i < recipe.size(); i++) {
1000                         if (!recipe[i].empty()) {
1001                                 all_empty = false;
1002                                 break;
1003                         }
1004                 }
1005                 if (all_empty)
1006                         return false;
1007
1008                 CraftInput input(craft_method, craft_grid_width, craftGetItems(recipe, gamedef));
1009                 // Recipes are not yet hashed at this point
1010                 std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1011                 std::vector<CraftDefinition*> new_vec_by_input;
1012                 bool got_hit = false;
1013                 for (std::vector<CraftDefinition*>::size_type
1014                                 i = unhashed_inputs_vec.size(); i > 0; i--) {
1015                         CraftDefinition *def = unhashed_inputs_vec[i - 1];
1016                         /* If the input doesn't match the recipe definition, this recipe definition later
1017                                 will be added back in source map. */
1018                         if (!def->check(input, gamedef)) {
1019                                 new_vec_by_input.push_back(def);
1020                                 continue;
1021                         }
1022                         CraftOutput output = def->getOutput(input, gamedef);
1023                         got_hit = true;
1024                         std::map<std::string, std::vector<CraftDefinition*> >::iterator
1025                                 vec_iter = m_output_craft_definitions.find(output.item);
1026                         if (vec_iter == m_output_craft_definitions.end())
1027                                 continue;
1028                         std::vector<CraftDefinition*> &vec = vec_iter->second;
1029                         std::vector<CraftDefinition*> new_vec_by_output;
1030                         /* We will preallocate necessary memory addresses, so we don't need
1031                                 to reallocate them later. This would save us some performance. */
1032                         new_vec_by_output.reserve(vec.size());
1033                         for (std::vector<CraftDefinition*>::iterator i = vec.begin();
1034                                         i != vec.end(); ++i) {
1035                                 /* If pointers from map by input and output are not same,
1036                                         we will add 'CraftDefinition*' to a new vector. */
1037                                 if (def != *i) {
1038                                         /* Adding dereferenced iterator value (which are
1039                                                 'CraftDefinition' reference) to a new vector. */
1040                                         new_vec_by_output.push_back(*i);
1041                                 }
1042                         }
1043                         // Swaps assigned to current key value with new vector for output map.
1044                         m_output_craft_definitions[output.item].swap(new_vec_by_output);
1045                 }
1046                 if (got_hit)
1047                         // Swaps value with new vector for input map.
1048                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
1049
1050                 return got_hit;
1051         }
1052
1053         virtual std::string dump() const
1054         {
1055                 std::ostringstream os(std::ios::binary);
1056                 os << "Crafting definitions:\n";
1057                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1058                         for (std::map<u64, std::vector<CraftDefinition*> >::const_iterator
1059                                         it = (m_craft_defs[type]).begin();
1060                                         it != (m_craft_defs[type]).end(); ++it) {
1061                                 for (std::vector<CraftDefinition*>::size_type i = 0;
1062                                                 i < it->second.size(); i++) {
1063                                         os << "type " << type
1064                                                 << " hash " << it->first
1065                                                 << " def " << it->second[i]->dump()
1066                                                 << "\n";
1067                                 }
1068                         }
1069                 }
1070                 return os.str();
1071         }
1072         virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
1073         {
1074                 verbosestream << "registerCraft: registering craft definition: "
1075                                 << def->dump() << std::endl;
1076                 m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
1077
1078                 CraftInput input;
1079                 std::string output_name = craftGetItemName(
1080                                 def->getOutput(input, gamedef).item, gamedef);
1081                 m_output_craft_definitions[output_name].push_back(def);
1082         }
1083         virtual void clear()
1084         {
1085                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1086                         for (std::map<u64, std::vector<CraftDefinition*> >::iterator
1087                                         it = m_craft_defs[type].begin();
1088                                         it != m_craft_defs[type].end(); ++it) {
1089                                 for (std::vector<CraftDefinition*>::iterator
1090                                                 iit = it->second.begin();
1091                                                 iit != it->second.end(); ++iit) {
1092                                         delete *iit;
1093                                 }
1094                                 it->second.clear();
1095                         }
1096                         m_craft_defs[type].clear();
1097                 }
1098                 m_output_craft_definitions.clear();
1099         }
1100         virtual void initHashes(IGameDef *gamedef)
1101         {
1102                 // Move the CraftDefs from the unhashed layer into layers higher up.
1103                 std::vector<CraftDefinition *> &unhashed =
1104                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1105                 for (std::vector<CraftDefinition*>::size_type i = 0;
1106                         i < unhashed.size(); i++) {
1107                         CraftDefinition *def = unhashed[i];
1108
1109                         // Initialize and get the definition's hash
1110                         def->initHash(gamedef);
1111                         CraftHashType type = def->getHashType();
1112                         u64 hash = def->getHash(type);
1113
1114                         // Enter the definition
1115                         m_craft_defs[type][hash].push_back(def);
1116                 }
1117                 unhashed.clear();
1118         }
1119 private:
1120         //TODO: change both maps to unordered_map when c++11 can be used
1121         std::vector<std::map<u64, std::vector<CraftDefinition*> > > m_craft_defs;
1122         std::map<std::string, std::vector<CraftDefinition*> > m_output_craft_definitions;
1123 };
1124
1125 IWritableCraftDefManager* createCraftDefManager()
1126 {
1127         return new CCraftDefManager();
1128 }
1129