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 "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.atend());
  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>::const_iterator
 116                         it = itemstrings.begin();
 117                         it != itemstrings.end(); it++) {
 118                 result.push_back(craftGetItemName(*it, gamedef));
 119         }
 120         return result;
 121 }
 122
 123 // Get name of each item, and return them as a new list.
 124 static std::vector<std::string> craftGetItemNames(
 125                 const std::vector<ItemStack> &items, IGameDef *gamedef)
 126 {
 127         std::vector<std::string> result;
 128         for (std::vector<ItemStack>::const_iterator
 129                         it = items.begin();
 130                         it != items.end(); it++) {
 131                 result.push_back(it->name);
 132         }
 133         return result;
 134 }
 135
 136 // convert a list of item names, to ItemStacks.
 137 static std::vector<ItemStack> craftGetItems(
 138                 const std::vector<std::string> &items, IGameDef *gamedef)
 139 {
 140         std::vector<ItemStack> result;
 141         for (std::vector<std::string>::const_iterator
 142                         it = items.begin();
 143                         it != items.end(); it++) {
 144                 result.push_back(ItemStack(std::string(*it), (u16)1,
 145                         (u16)0, "", gamedef->getItemDefManager()));
 146         }
 147         return result;
 148 }
 149
 150 // Compute bounding rectangle given a matrix of items
 151 // Returns false if every item is ""
 152 static bool craftGetBounds(const std::vector<std::string> &items, unsigned int width,
 153                 unsigned int &min_x, unsigned int &max_x,
 154                 unsigned int &min_y, unsigned int &max_y)
 155 {
 156         bool success = false;
 157         unsigned int x = 0;
 158         unsigned int y = 0;
 159         for (std::vector<std::string>::const_iterator
 160                         it = items.begin();
 161                         it != items.end(); it++) {
 162                 // Is this an actual item?
 163                 if (*it != "") {
 164                         if (!success) {
 165                                 // This is the first nonempty item
 166                                 min_x = max_x = x;
 167                                 min_y = max_y = y;
 168                                 success = true;
 169                         } else {
 170                                 if (x < min_x) min_x = x;
 171                                 if (x > max_x) max_x = x;
 172                                 if (y < min_y) min_y = y;
 173                                 if (y > max_y) max_y = y;
 174                         }
 175                 }
 176
 177                 // Step coordinate
 178                 x++;
 179                 if (x == width) {
 180                         x = 0;
 181                         y++;
 182                 }
 183         }
 184         return success;
 185 }
 186
 187 // Removes 1 from each item stack
 188 static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 189 {
 190         for (std::vector<ItemStack>::iterator
 191                         it = input.items.begin();
 192                         it != input.items.end(); it++) {
 193                 if (it->count != 0)
 194                         it->remove(1);
 195         }
 196 }
 197
 198 // Removes 1 from each item stack with replacement support
 199 // Example: if replacements contains the pair ("bucket:bucket_water", "bucket:bucket_empty"),
 200 //   a water bucket will not be removed but replaced by an empty bucket.
 201 static void craftDecrementOrReplaceInput(CraftInput &input,
 202                 const CraftReplacements &replacements,
 203                 IGameDef *gamedef)
 204 {
 205         if (replacements.pairs.empty()) {
 206                 craftDecrementInput(input, gamedef);
 207                 return;
 208         }
 209
 210         // Make a copy of the replacements pair list
 211         std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;
 212
 213         for (std::vector<ItemStack>::iterator
 214                         it = input.items.begin();
 215                         it != input.items.end(); it++) {
 216                 if (it->count == 1) {
 217                         // Find an appropriate replacement
 218                         bool found_replacement = false;
 219                         for (std::vector<std::pair<std::string, std::string> >::iterator
 220                                         j = pairs.begin();
 221                                         j != pairs.end(); j++) {
 222                                 if (it->name == craftGetItemName(j->first, gamedef)) {
 223                                         it->deSerialize(j->second, gamedef->idef());
 224                                         found_replacement = true;
 225                                         pairs.erase(j);
 226                                         break;
 227                                 }
 228                         }
 229                         // No replacement was found, simply decrement count to zero
 230                         if (!found_replacement)
 231                                 it->remove(1);
 232                 } else if (it->count >= 2) {
 233                         // Ignore replacements for items with count >= 2
 234                         it->remove(1);
 235                 }
 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>::const_iterator
 247                         it = items.begin();
 248                         it != items.end(); it++, x++) {
 249                 if (x == width) {
 250                         os<<"; ";
 251                         x = 0;
 252                 } else if (x != 0) {
 253                         os<<",";
 254                 }
 255                 os << '"' << (*it) << '"';
 256         }
 257         os << " }";
 258         return os.str();
 259 }
 260
 261 // Dump an item matrix
 262 std::string craftDumpMatrix(const std::vector<ItemStack> &items,
 263                 unsigned int width)
 264 {
 265         std::ostringstream os(std::ios::binary);
 266         os << "{ ";
 267         unsigned int x = 0;
 268         for (std::vector<ItemStack>::const_iterator
 269                         it = items.begin();
 270                         it != items.end(); it++, x++) {
 271                 if (x == width) {
 272                         os << "; ";
 273                         x = 0;
 274                 } else if (x != 0) {
 275                         os<<",";
 276                 }
 277                 os << '"' << (it->getItemString()) << '"';
 278         }
 279         os << " }";
 280         return os.str();
 281 }
 282
 283
 284 /*
 285         CraftInput
 286 */
 287
 288 std::string CraftInput::dump() const
 289 {
 290         std::ostringstream os(std::ios::binary);
 291         os << "(method=" << ((int)method) << ", items="
 292                 << craftDumpMatrix(items, width) << ")";
 293         return os.str();
 294 }
 295
 296 /*
 297         CraftOutput
 298 */
 299
 300 std::string CraftOutput::dump() const
 301 {
 302         std::ostringstream os(std::ios::binary);
 303         os << "(item=\"" << item << "\", time=" << time << ")";
 304         return os.str();
 305 }
 306
 307 /*
 308         CraftReplacements
 309 */
 310
 311 std::string CraftReplacements::dump() const
 312 {
 313         std::ostringstream os(std::ios::binary);
 314         os<<"{";
 315         const char *sep = "";
 316         for (std::vector<std::pair<std::string, std::string> >::const_iterator
 317                         it = pairs.begin();
 318                         it != pairs.end(); it++) {
 319                 os << sep << '"' << (it->first) << "\"=>\"" << (it->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, IGameDef *gamedef) const
 412 {
 413         craftDecrementOrReplaceInput(input, replacements, gamedef);
 414 }
 415
 416 CraftHashType CraftDefinitionShaped::getHashType() const
 417 {
 418         assert(hash_inited); // Pre-condition
 419         bool has_group = false;
 420         for (size_t i = 0; i < recipe_names.size(); i++) {
 421                 if (isGroupRecipeStr(recipe_names[i])) {
 422                         has_group = true;
 423                         break;
 424                 }
 425         }
 426         if (has_group)
 427                 return CRAFT_HASH_TYPE_COUNT;
 428         else
 429                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 430 }
 431
 432 u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 433 {
 434         assert(hash_inited); // Pre-condition
 435         assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
 436                 || (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
 437
 438         std::vector<std::string> rec_names = recipe_names;
 439         std::sort(rec_names.begin(), rec_names.end());
 440         return getHashForGrid(type, rec_names);
 441 }
 442
 443 void CraftDefinitionShaped::initHash(IGameDef *gamedef)
 444 {
 445         if (hash_inited)
 446                 return;
 447         hash_inited = true;
 448         recipe_names = craftGetItemNames(recipe, gamedef);
 449 }
 450
 451 std::string CraftDefinitionShaped::dump() const
 452 {
 453         std::ostringstream os(std::ios::binary);
 454         os << "(shaped, output=\"" << output
 455                 << "\", recipe=" << craftDumpMatrix(recipe, width)
 456                 << ", replacements=" << replacements.dump() << ")";
 457         return os.str();
 458 }
 459
 460 /*
 461         CraftDefinitionShapeless
 462 */
 463
 464 std::string CraftDefinitionShapeless::getName() const
 465 {
 466         return "shapeless";
 467 }
 468
 469 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 470 {
 471         if (input.method != CRAFT_METHOD_NORMAL)
 472                 return false;
 473
 474         // Filter empty items out of input
 475         std::vector<std::string> input_filtered;
 476         for (std::vector<ItemStack>::const_iterator
 477                         it = input.items.begin();
 478                         it != input.items.end(); it++) {
 479                 if (it->name != "")
 480                         input_filtered.push_back(it->name);
 481         }
 482
 483         // If there is a wrong number of items in input, no match
 484         if (input_filtered.size() != recipe.size()) {
 485                 /*dstream<<"Number of input items ("<<input_filtered.size()
 486                                 <<") does not match recipe size ("<<recipe.size()<<") "
 487                                 <<"of recipe with output="<<output<<std::endl;*/
 488                 return false;
 489         }
 490
 491         std::vector<std::string> recipe_copy;
 492         if (hash_inited)
 493                 recipe_copy = recipe_names;
 494         else {
 495                 recipe_copy = craftGetItemNames(recipe, gamedef);
 496                 std::sort(recipe_copy.begin(), recipe_copy.end());
 497         }
 498
 499         // Try with all permutations of the recipe,
 500         // start from the lexicographically first permutation (=sorted),
 501         // recipe_names is pre-sorted
 502         do {
 503                 // If all items match, the recipe matches
 504                 bool all_match = true;
 505                 //dstream<<"Testing recipe (output="<<output<<"):";
 506                 for (size_t i=0; i<recipe.size(); i++) {
 507                         //dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
 508                         if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
 509                                         gamedef->idef())) {
 510                                 all_match = false;
 511                                 break;
 512                         }
 513                 }
 514                 //dstream<<" -> match="<<all_match<<std::endl;
 515                 if (all_match)
 516                         return true;
 517         } while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
 518
 519         return false;
 520 }
 521
 522 CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
 523 {
 524         return CraftOutput(output, 0);
 525 }
 526
 527 CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 528 {
 529         return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 530 }
 531
 532 void CraftDefinitionShapeless::decrementInput(CraftInput &input, IGameDef *gamedef) const
 533 {
 534         craftDecrementOrReplaceInput(input, replacements, gamedef);
 535 }
 536
 537 CraftHashType CraftDefinitionShapeless::getHashType() const
 538 {
 539         assert(hash_inited); // Pre-condition
 540         bool has_group = false;
 541         for (size_t i = 0; i < recipe_names.size(); i++) {
 542                 if (isGroupRecipeStr(recipe_names[i])) {
 543                         has_group = true;
 544                         break;
 545                 }
 546         }
 547         if (has_group)
 548                 return CRAFT_HASH_TYPE_COUNT;
 549         else
 550                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 551 }
 552
 553 u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 554 {
 555         assert(hash_inited); // Pre-condition
 556         assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
 557                 || type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
 558         return getHashForGrid(type, recipe_names);
 559 }
 560
 561 void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
 562 {
 563         if (hash_inited)
 564                 return;
 565         hash_inited = true;
 566         recipe_names = craftGetItemNames(recipe, gamedef);
 567         std::sort(recipe_names.begin(), recipe_names.end());
 568 }
 569
 570 std::string CraftDefinitionShapeless::dump() const
 571 {
 572         std::ostringstream os(std::ios::binary);
 573         os << "(shapeless, output=\"" << output
 574                 << "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
 575                 << ", replacements=" << replacements.dump() << ")";
 576         return os.str();
 577 }
 578
 579 /*
 580         CraftDefinitionToolRepair
 581 */
 582
 583 static ItemStack craftToolRepair(
 584                 const ItemStack &item1,
 585                 const ItemStack &item2,
 586                 float additional_wear,
 587                 IGameDef *gamedef)
 588 {
 589         IItemDefManager *idef = gamedef->idef();
 590         if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
 591                         || idef->get(item1.name).type != ITEM_TOOL
 592                         || idef->get(item2.name).type != ITEM_TOOL) {
 593                 // Failure
 594                 return ItemStack();
 595         }
 596
 597         s32 item1_uses = 65536 - (u32) item1.wear;
 598         s32 item2_uses = 65536 - (u32) item2.wear;
 599         s32 new_uses = item1_uses + item2_uses;
 600         s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
 601         if (new_wear >= 65536)
 602                 return ItemStack();
 603         if (new_wear < 0)
 604                 new_wear = 0;
 605
 606         ItemStack repaired = item1;
 607         repaired.wear = new_wear;
 608         return repaired;
 609 }
 610
 611 std::string CraftDefinitionToolRepair::getName() const
 612 {
 613         return "toolrepair";
 614 }
 615
 616 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 617 {
 618         if (input.method != CRAFT_METHOD_NORMAL)
 619                 return false;
 620
 621         ItemStack item1;
 622         ItemStack item2;
 623         for (std::vector<ItemStack>::const_iterator
 624                         it = input.items.begin();
 625                         it != input.items.end(); it++) {
 626                 if (!it->empty()) {
 627                         if (item1.empty())
 628                                 item1 = *it;
 629                         else if (item2.empty())
 630                                 item2 = *it;
 631                         else
 632                                 return false;
 633                 }
 634         }
 635         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 636         return !repaired.empty();
 637 }
 638
 639 CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameDef *gamedef) const
 640 {
 641         ItemStack item1;
 642         ItemStack item2;
 643         for (std::vector<ItemStack>::const_iterator
 644                         it = input.items.begin();
 645                         it != input.items.end(); it++) {
 646                 if (!it->empty()) {
 647                         if (item1.empty())
 648                                 item1 = *it;
 649                         else if (item2.empty())
 650                                 item2 = *it;
 651                 }
 652         }
 653         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 654         return CraftOutput(repaired.getItemString(), 0);
 655 }
 656
 657 CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
 658 {
 659         std::vector<ItemStack> stack;
 660         stack.push_back(ItemStack());
 661         return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
 662 }
 663
 664 void CraftDefinitionToolRepair::decrementInput(CraftInput &input, IGameDef *gamedef) const
 665 {
 666         craftDecrementInput(input, gamedef);
 667 }
 668
 669 std::string CraftDefinitionToolRepair::dump() const
 670 {
 671         std::ostringstream os(std::ios::binary);
 672         os << "(toolrepair, additional_wear=" << additional_wear << ")";
 673         return os.str();
 674 }
 675
 676 /*
 677         CraftDefinitionCooking
 678 */
 679
 680 std::string CraftDefinitionCooking::getName() const
 681 {
 682         return "cooking";
 683 }
 684
 685 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 686 {
 687         if (input.method != CRAFT_METHOD_COOKING)
 688                 return false;
 689
 690         // Filter empty items out of input
 691         std::vector<std::string> input_filtered;
 692         for (std::vector<ItemStack>::const_iterator
 693                         it = input.items.begin();
 694                         it != input.items.end(); it++) {
 695                 if (it->name != "")
 696                         input_filtered.push_back(it->name);
 697         }
 698
 699         // If there is a wrong number of items in input, no match
 700         if (input_filtered.size() != 1) {
 701                 /*dstream<<"Number of input items ("<<input_filtered.size()
 702                                 <<") does not match recipe size (1) "
 703                                 <<"of cooking recipe with output="<<output<<std::endl;*/
 704                 return false;
 705         }
 706
 707         // Check the single input item
 708         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 709 }
 710
 711 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
 712 {
 713         return CraftOutput(output, cooktime);
 714 }
 715
 716 CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
 717 {
 718         std::vector<std::string> rec;
 719         rec.push_back(recipe);
 720         return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 721 }
 722
 723 void CraftDefinitionCooking::decrementInput(CraftInput &input, IGameDef *gamedef) const
 724 {
 725         craftDecrementOrReplaceInput(input, replacements, gamedef);
 726 }
 727
 728 CraftHashType CraftDefinitionCooking::getHashType() const
 729 {
 730         if (isGroupRecipeStr(recipe_name))
 731                 return CRAFT_HASH_TYPE_COUNT;
 732         else
 733                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 734 }
 735
 736 u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 737 {
 738         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 739                 return getHashForString(recipe_name);
 740         } else if (type == CRAFT_HASH_TYPE_COUNT) {
 741                 return 1;
 742         } else {
 743                 //illegal hash type for this CraftDefinition (pre-condition)
 744                 assert(false);
 745                 return 0;
 746         }
 747 }
 748
 749 void CraftDefinitionCooking::initHash(IGameDef *gamedef)
 750 {
 751         if (hash_inited)
 752                 return;
 753         hash_inited = true;
 754         recipe_name = craftGetItemName(recipe, gamedef);
 755 }
 756
 757 std::string CraftDefinitionCooking::dump() const
 758 {
 759         std::ostringstream os(std::ios::binary);
 760         os << "(cooking, output=\"" << output
 761                 << "\", recipe=\"" << recipe
 762                 << "\", cooktime=" << cooktime << ")"
 763                 << ", replacements=" << replacements.dump() << ")";
 764         return os.str();
 765 }
 766
 767 /*
 768         CraftDefinitionFuel
 769 */
 770
 771 std::string CraftDefinitionFuel::getName() const
 772 {
 773         return "fuel";
 774 }
 775
 776 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 777 {
 778         if (input.method != CRAFT_METHOD_FUEL)
 779                 return false;
 780
 781         // Filter empty items out of input
 782         std::vector<std::string> input_filtered;
 783         for (std::vector<ItemStack>::const_iterator
 784                         it = input.items.begin();
 785                         it != input.items.end(); it++) {
 786                 if (it->name != "")
 787                         input_filtered.push_back(it->name);
 788         }
 789
 790         // If there is a wrong number of items in input, no match
 791         if (input_filtered.size() != 1) {
 792                 /*dstream<<"Number of input items ("<<input_filtered.size()
 793                                 <<") does not match recipe size (1) "
 794                                 <<"of fuel recipe with burntime="<<burntime<<std::endl;*/
 795                 return false;
 796         }
 797
 798         // Check the single input item
 799         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 800 }
 801
 802 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
 803 {
 804         return CraftOutput("", burntime);
 805 }
 806
 807 CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
 808 {
 809         std::vector<std::string> rec;
 810         rec.push_back(recipe);
 811         return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 812 }
 813
 814 void CraftDefinitionFuel::decrementInput(CraftInput &input, IGameDef *gamedef) const
 815 {
 816         craftDecrementOrReplaceInput(input, replacements, gamedef);
 817 }
 818
 819 CraftHashType CraftDefinitionFuel::getHashType() const
 820 {
 821         if (isGroupRecipeStr(recipe_name))
 822                 return CRAFT_HASH_TYPE_COUNT;
 823         else
 824                 return CRAFT_HASH_TYPE_ITEM_NAMES;
 825 }
 826
 827 u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 828 {
 829         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 830                 return getHashForString(recipe_name);
 831         } else if (type == CRAFT_HASH_TYPE_COUNT) {
 832                 return 1;
 833         } else {
 834                 //illegal hash type for this CraftDefinition (pre-condition)
 835                 assert(false);
 836                 return 0;
 837         }
 838 }
 839
 840 void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 841 {
 842         if (hash_inited)
 843                 return;
 844         hash_inited = true;
 845         recipe_name = craftGetItemName(recipe, gamedef);
 846 }
 847 std::string CraftDefinitionFuel::dump() const
 848 {
 849         std::ostringstream os(std::ios::binary);
 850         os << "(fuel, recipe=\"" << recipe
 851                 << "\", burntime=" << burntime << ")"
 852                 << ", replacements=" << replacements.dump() << ")";
 853         return os.str();
 854 }
 855
 856 /*
 857         Craft definition manager
 858 */
 859
 860 class CCraftDefManager: public IWritableCraftDefManager
 861 {
 862 public:
 863         CCraftDefManager()
 864         {
 865                 m_craft_defs.resize(craft_hash_type_max + 1);
 866         }
 867
 868         virtual ~CCraftDefManager()
 869         {
 870                 clear();
 871         }
 872
 873         virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
 874                         bool decrementInput, IGameDef *gamedef) const
 875         {
 876                 output.item = "";
 877                 output.time = 0;
 878
 879                 // If all input items are empty, abort.
 880                 bool all_empty = true;
 881                 for (std::vector<ItemStack>::const_iterator
 882                                 it = input.items.begin();
 883                                 it != input.items.end(); it++) {
 884                         if (!it->empty()) {
 885                                 all_empty = false;
 886                                 break;
 887                         }
 888                 }
 889                 if (all_empty)
 890                         return false;
 891
 892                 std::vector<std::string> input_names;
 893                 input_names = craftGetItemNames(input.items, gamedef);
 894                 std::sort(input_names.begin(), input_names.end());
 895
 896                 // Try hash types with increasing collision rate, and return if found.
 897                 for (int type = 0; type <= craft_hash_type_max; type++) {
 898                         u64 hash = getHashForGrid((CraftHashType) type, input_names);
 899
 900                         /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/
 901
 902                         // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];"
 903                         // but that doesn't compile for some reason. This does.
 904                         std::map<u64, std::vector<CraftDefinition*> >::const_iterator
 905                                 col_iter = (m_craft_defs[type]).find(hash);
 906
 907                         if (col_iter == (m_craft_defs[type]).end())
 908                                 continue;
 909
 910                         const std::vector<CraftDefinition*> &hash_collisions = col_iter->second;
 911                         // Walk crafting definitions from back to front, so that later
 912                         // definitions can override earlier ones.
 913                         for (std::vector<CraftDefinition*>::const_reverse_iterator
 914                                         it = hash_collisions.rbegin();
 915                                         it != hash_collisions.rend(); it++) {
 916                                 CraftDefinition *def = *it;
 917
 918                                 /*errorstream << "Checking " << input.dump() << std::endl
 919                                         << " against " << def->dump() << std::endl;*/
 920
 921                                 if (def->check(input, gamedef)) {
 922                                         // Get output, then decrement input (if requested)
 923                                         output = def->getOutput(input, gamedef);
 924                                         if (decrementInput)
 925                                                 def->decrementInput(input, gamedef);
 926                                         /*errorstream << "Check RETURNS TRUE" << std::endl;*/
 927                                         return true;
 928                                 }
 929                         }
 930                 }
 931                 return false;
 932         }
 933
 934         virtual std::vector<CraftDefinition*> getCraftRecipes(CraftOutput &output,
 935                         IGameDef *gamedef, unsigned limit=0) const
 936         {
 937                 std::vector<CraftDefinition*> recipes;
 938
 939                 std::map<std::string, std::vector<CraftDefinition*> >::const_iterator
 940                         vec_iter = m_output_craft_definitions.find(output.item);
 941
 942                 if (vec_iter == m_output_craft_definitions.end())
 943                         return recipes;
 944
 945                 const std::vector<CraftDefinition*> &vec = vec_iter->second;
 946
 947                 recipes.reserve(limit ? MYMIN(limit, vec.size()) : vec.size());
 948
 949                 for (std::vector<CraftDefinition*>::const_reverse_iterator
 950                                 it = vec.rbegin(); it != vec.rend(); ++it) {
 951                         if (limit && recipes.size() >= limit)
 952                                 break;
 953                         recipes.push_back(*it);
 954                 }
 955
 956                 return recipes;
 957         }
 958         virtual std::string dump() const
 959         {
 960                 std::ostringstream os(std::ios::binary);
 961                 os << "Crafting definitions:\n";
 962                 for (int type = 0; type <= craft_hash_type_max; type++) {
 963                         for (std::map<u64, std::vector<CraftDefinition*> >::const_iterator
 964                                         it = (m_craft_defs[type]).begin();
 965                                         it != (m_craft_defs[type]).end(); it++) {
 966                                 for (std::vector<CraftDefinition*>::const_iterator
 967                                                 iit = it->second.begin(); iit != it->second.end(); iit++) {
 968                                         os << "type " << type << " hash " << it->first << (*iit)->dump() << "\n";
 969                                 }
 970                         }
 971                 }
 972                 return os.str();
 973         }
 974         virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
 975         {
 976                 verbosestream << "registerCraft: registering craft definition: "
 977                                 << def->dump() << std::endl;
 978                 m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
 979
 980                 CraftInput input;
 981                 std::string output_name = craftGetItemName(
 982                                 def->getOutput(input, gamedef).item, gamedef);
 983                 m_output_craft_definitions[output_name].push_back(def);
 984         }
 985         virtual void clear()
 986         {
 987                 for (int type = 0; type <= craft_hash_type_max; type++) {
 988                         for (std::map<u64, std::vector<CraftDefinition*> >::iterator
 989                                         it = m_craft_defs[type].begin();
 990                                         it != m_craft_defs[type].end(); it++) {
 991                                 for (std::vector<CraftDefinition*>::iterator
 992                                                 iit = it->second.begin(); iit != it->second.end(); iit++) {
 993                                         delete *iit;
 994                                 }
 995                                 it->second.clear();
 996                         }
 997                         m_craft_defs[type].clear();
 998                 }
 999                 m_output_craft_definitions.clear();
1000         }
1001         virtual void initHashes(IGameDef *gamedef)
1002         {
1003                 // Move the CraftDefs from the unhashed layer into layers higher up.
1004                 for (std::vector<CraftDefinition*>::iterator
1005                         it = (m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0]).begin();
1006                         it != (m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0]).end(); it++) {
1007                         CraftDefinition *def = *it;
1008
1009                         // Initialize and get the definition's hash
1010                         def->initHash(gamedef);
1011                         CraftHashType type = def->getHashType();
1012                         u64 hash = def->getHash(type);
1013
1014                         // Enter the definition
1015                         m_craft_defs[type][hash].push_back(def);
1016                 }
1017                 m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].clear();
1018         }
1019 private:
1020         //TODO: change both maps to unordered_map when c++11 can be used
1021         std::vector<std::map<u64, std::vector<CraftDefinition*> > > m_craft_defs;
1022         std::map<std::string, std::vector<CraftDefinition*> > m_output_craft_definitions;
1023 };
1024
1025 IWritableCraftDefManager* createCraftDefManager()
1026 {
1027         return new CCraftDefManager();
1028 }
1029