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