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