/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) 2001,2007 Mark Wedel & Crossfire Development Team
 * Copyright (©) 1992,2007 Frank Tore Johansen
 * 
 * Deliantra is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

#include <global.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <object.h>
#include <sproto.h>
#include <loader.h>

#include <bitset>

UUID UUID::cur;
static uint64_t seq_next_save;
static const uint64 UUID_GAP = 1<<19;
uint32_t mapspace::smellcount = 10000;

objectvec objects;
activevec actives;

short freearr_x[SIZEOFFREE] = {
   0,
   0,  1,  1,  1,  0, -1, -1, -1,
   0,  1,  2,  2,  2,  2,  2,  1,  0, -1, -2, -2, -2, -2, -2, -1,
   0,  1,  2,  3,  3,  3,  3,  3,  3,  3,  2,  1,  0, -1, -2, -3, -3, -3, -3, -3, -3, -3, -2, -1
};
short freearr_y[SIZEOFFREE] = {
   0,
  -1, -1,  0,  1,  1,  1,  0, -1,
  -2, -2, -2, -1,  0,  1,  2,  2,  2,  2,  2,  1,  0, -1, -2, -2,
  -3, -3, -3, -3, -2, -1,  0,  1,  2,  3,  3,  3,  3,  3,  3,  3,  2,  1,  0, -1, -2, -3, -3, -3
};
int maxfree[SIZEOFFREE] = {
   0,
   9, 10, 13, 14, 17, 18, 21, 22,
  25, 26, 27, 30, 31, 32, 33, 36, 37, 39, 39, 42, 43, 44, 45, 48,
  49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49
};
int freedir[SIZEOFFREE] = {
   0,
   1,  2,  3,  4,  5,  6,  7,  8,
   1,  2,  2,  2,  3,  4,  4,  4,  5,  6,  6,  6,  7,  8,  8,  8,
   1,  2,  2,  2,  2,  2,  3,  4,  4,  4,  4,  4,  5,  6,  6,  6,  6,  6,  7,  8,  8,  8,  8,  8
};

static void
write_uuid (uval64 skip, bool sync)
{
  CALL_BEGIN (2);
  CALL_ARG_SV (newSVval64 (skip));
  CALL_ARG_SV (boolSV (sync));
  CALL_CALL ("cf::write_uuid", G_DISCARD);
  CALL_END;
}

static void
read_uuid (void)
{
  char filename[MAX_BUF];

  sprintf (filename, "%s/uuid", settings.localdir);

  seq_next_save = 0;

  FILE *fp;

  if (!(fp = fopen (filename, "r")))
    {
      if (errno == ENOENT)
        {
          LOG (llevInfo, "RESET uid to 1\n");
          UUID::cur.seq = 0;
          write_uuid (UUID_GAP, true);
          return;
        }

      LOG (llevError, "FATAL: cannot open %s for reading!\n", filename);
      _exit (1);
    }

  UUID::BUF buf;
  buf[0] = 0;
  fgets (buf, sizeof (buf), fp);

  if (!UUID::cur.parse (buf))
    {
      LOG (llevError, "FATAL: error reading uid from %s (%s)!\n", filename, buf);
      _exit (1);
    }

  LOG (llevDebug, "read UUID: %s\n", UUID::cur.c_str ());

  write_uuid (UUID_GAP, true);
  fclose (fp);
}

UUID
UUID::gen ()
{
  UUID uid;

  uid.seq = ++cur.seq;

  if (expect_false (cur.seq >= seq_next_save))
    {
      seq_next_save = UUID::cur.seq + (UUID_GAP >> 1);
      write_uuid (UUID_GAP, false);
    }


  return uid;
}

void
UUID::init ()
{
  read_uuid ();
}

/* Returns TRUE if every key_values in wants has a partner with the same value in has. */
static bool
compare_ob_value_lists_one (const object *wants, const object *has)
{
  /* n-squared behaviour (see kv_get), but I'm hoping both
   * objects with lists are rare, and lists stay short. If not, use a
   * different structure or at least keep the lists sorted... 
   */

  /* For each field in wants, */
  for (key_value *kv = wants->key_values; kv; kv = kv->next)
    if (has->kv_get (kv->key) != kv->value)
      return false;

  /* If we get here, every field in wants has a matching field in has. */
  return true;
}

/* Returns TRUE if ob1 has the same key_values as ob2. */
static bool
compare_ob_value_lists (const object *ob1, const object *ob2)
{
  /* However, there may be fields in has which aren't partnered in wants,
   * so we need to run the comparison *twice*. :(
   */
  return compare_ob_value_lists_one (ob1, ob2)
      && compare_ob_value_lists_one (ob2, ob1);
}

/* Function examines the 2 objects given to it, and returns true if
 * they can be merged together.
 *
 * Note that this function appears a lot longer than the macro it
 * replaces - this is mostly for clarity - a decent compiler should hopefully
 * reduce this to the same efficiency.
 *
 * Check nrof variable *before* calling can_merge()
 *
 * Improvements made with merge:  Better checking on potion, and also
 * check weight
 */
bool object::can_merge_slow (object *ob1, object *ob2)
{
  /* A couple quicksanity checks */
  if (ob1 == ob2
      || ob1->type  != ob2->type
      || ob1->speed != ob2->speed
      || ob1->value != ob2->value
      || ob1->name  != ob2->name)
    return 0;

  /* Do not merge objects if nrof would overflow, assume nrof
   * is always 0 .. 2**31-1 */
  if (ob1->nrof > 0x7fffffff - ob2->nrof)
    return 0;

  /* If the objects have been identified, set the BEEN_APPLIED flag.
   * This is to the comparison of the flags below will be OK. We
   * just can't ignore the been applied or identified flags, as they
   * are not equal - just if it has been identified, the been_applied
   * flags lose any meaning.
   */
  if (QUERY_FLAG (ob1, FLAG_IDENTIFIED))
    SET_FLAG (ob1, FLAG_BEEN_APPLIED);

  if (QUERY_FLAG (ob2, FLAG_IDENTIFIED))
    SET_FLAG (ob2, FLAG_BEEN_APPLIED);

  if (ob1->arch->archname  != ob2->arch->archname
      || ob1->name         != ob2->name
      || ob1->title        != ob2->title
      || ob1->msg          != ob2->msg
      || ob1->weight       != ob2->weight
      || ob1->attacktype   != ob2->attacktype
      || ob1->magic        != ob2->magic
      || ob1->slaying      != ob2->slaying
      || ob1->skill        != ob2->skill
      || ob1->value        != ob2->value
      || ob1->animation_id != ob2->animation_id
      || (ob1->face != ob2->face && !ob1->animation_id) // face and animation are dependent on each other
      || ob1->client_type  != ob2->client_type
      || ob1->materialname != ob2->materialname
      || ob1->lore         != ob2->lore
      || ob1->subtype      != ob2->subtype
      || ob1->move_type    != ob2->move_type
      || ob1->move_block   != ob2->move_block
      || ob1->move_allow   != ob2->move_allow
      || ob1->move_on      != ob2->move_on
      || ob1->move_off     != ob2->move_off
      || ob1->move_slow    != ob2->move_slow
      || ob1->move_slow_penalty != ob2->move_slow_penalty
      || memcmp (&ob1->resist, &ob2->resist, sizeof (ob1->resist))
      || memcmp (&ob1->stats , &ob2->stats , sizeof (ob1->stats)))
    return 0;

  if ((ob1->flag ^ ob2->flag)
      .reset (FLAG_INV_LOCKED)
      .reset (FLAG_REMOVED)
      .any ())
    return 0;

  /* This is really a spellbook check - we should in general
   * not merge objects with real inventories, as splitting them
   * is hard.
   */
  if (ob1->inv || ob2->inv)
    {
      if (!(ob1->inv && ob2->inv))
        return 0; /* inventories differ in length */

      if (ob1->inv->below || ob2->inv->below)
        return 0; /* more than one object in inv */

      if (!object::can_merge (ob1->inv, ob2->inv))
        return 0; /* inventory objects differ */

      /* inventory ok - still need to check rest of this object to see
       * if it is valid.
       */
    }

  /* Don't merge objects that are applied.  With the new 'body' code,
   * it is possible for most any character to have more than one of
   * some items equipped, and we don't want those to merge.
   */
  if (QUERY_FLAG (ob1, FLAG_APPLIED) || QUERY_FLAG (ob2, FLAG_APPLIED))
    return 0;

  /* Note sure why the following is the case - either the object has to
   * be animated or have a very low speed.  Is this an attempted monster
   * check?
   */
  if (!QUERY_FLAG (ob1, FLAG_ANIMATE) && ob1->has_active_speed ())
    return 0;

  switch (ob1->type)
    {
      case SCROLL:
        if (ob1->level != ob2->level)
          return 0;
        break;
    }

  if (ob1->key_values || ob2->key_values)
    {
      /* At least one of these has key_values. */
      if ((!ob1->key_values) != (!ob2->key_values))
        return 0; /* One has fields, but the other one doesn't. */

      if (!compare_ob_value_lists (ob1, ob2))
        return 0;
    }

  if (ob1->self || ob2->self)
    {
      ob1->optimise ();
      ob2->optimise ();

      if (ob1->self || ob2->self)
        {
          int k1 = ob1->self ? HvTOTALKEYS (ob1->self) : 0;
          int k2 = ob2->self ? HvTOTALKEYS (ob2->self) : 0;

          if (k1 != k2)
            return 0;

          if (k1 == 0)
            return 1;

          if (!cfperl_can_merge (ob1, ob2))
            return 0;
        }
    }

  /* Everything passes, must be OK. */
  return 1;
}

// find player who can see this object
object *
object::visible_to () const
{
  if (client_visible () && !flag [FLAG_REMOVED])
    {
      // see if we are in a container of sorts
      if (env)
        {
          // the player inventory itself is always visible
          if (env->is_player ())
            return env;

          // else a player could have our env open
          object *envest = env->outer_env_or_self ();

          // the player itself is always on a map, so we will find him here
          // even if our inv is in a player.
          if (envest->is_on_map ())
            if (object *pl = envest->ms ().player ())
              if (pl->container == env)
                return pl;
        }
      else
        {
          // maybe there is a player standing on the same mapspace
          // this will catch the case where "this" is a player
          if (object *pl = ms ().player ())
            if ((!pl->container && pl->contr->ns && !pl->contr->ns->update_look)
                || this == pl->container)
              return pl;
        }
    }

  return 0;
}

// adjust weight per container type ("of holding")
static sint32
weight_adjust_for (object *op, sint32 weight)
{
  return op->type == CONTAINER
         ? lerp (weight, 0, 100, 0, 100 - op->stats.Str)
         : weight;
}

/*
 * adjust_weight(object, weight) adds the specified weight to an object,
 * and also updates how much the environment(s) is/are carrying.
 */
static void
adjust_weight (object *op, sint32 weight)
{
  while (op)
    {
      // adjust by actual difference to account for rounding errors
      // i.e. (w2 - w1) / f != w2 / f - w1 / f and the latter is correct
      weight = weight_adjust_for (op, op->carrying)
             - weight_adjust_for (op, op->carrying - weight);

      if (!weight)
        return;

      op->carrying += weight;

      if (object *pl = op->visible_to ())
        if (pl != op) // player is handled lazily
          esrv_update_item (UPD_WEIGHT, pl, op);

      op = op->env;
    }
}

/*
 * this is a recursive function which calculates the weight
 * an object is carrying. It goes through op and figures out how much
 * containers are carrying, and sums it up.
 */
void
object::update_weight ()
{
  sint32 sum = 0;

  for (object *op = inv; op; op = op->below)
    {
      if (op->inv)
        op->update_weight ();

      sum += op->total_weight ();
    }

  sum = weight_adjust_for (this, sum);

  if (sum != carrying)
    {
      carrying = sum;

      if (object *pl = visible_to ())
        if (pl != this) // player is handled lazily
          esrv_update_item (UPD_WEIGHT, pl, this);
    }
}

/*
 * Used by: Server DM commands: dumpbelow, dump. Some error messages.
 */
char *
dump_object (object *op)
{
  if (!op)
    return strdup ("[NULLOBJ]");

  object_freezer freezer;
  op->write (freezer);
  return freezer.as_string ();
}

char *
object::as_string ()
{
  return dump_object (this);
}

/*
 * get_nearest_part(multi-object, object 2) returns the part of the
 * multi-object 1 which is closest to the second object.
 * If it's not a multi-object, it is returned.
 */
object *
get_nearest_part (object *op, const object *pl)
{
  object *tmp, *closest;
  int last_dist, i;

  if (!op->more)
    return op;

  for (last_dist = distance (op, pl), closest = op, tmp = op->more;
       tmp;
       tmp = tmp->more)
    if ((i = distance (tmp, pl)) < last_dist)
      closest = tmp, last_dist = i;

  return closest;
}

/*
 * Returns the object which has the count-variable equal to the argument.
 * VERRRY slow.
 */
object *
find_object (tag_t i)
{
  for_all_objects (op)
   if (op->count == i)
     return op;

  return 0;
}

/*
 * Returns the first object which has a name equal to the argument.
 * Used only by the patch command, but not all that useful.
 * Enables features like "patch <name-of-other-player> food 999"
 */
object *
find_object_name (const char *str)
{
  shstr_cmp str_ (str);

  if (str_)
    for_all_objects (op)
      if (op->name == str_)
        return op;

  return 0;
}

/*
 * Sets the owner and sets the skill and exp pointers to owner's current
 * skill and experience objects.
 * ACTUALLY NO! investigate! TODO
 */
void
object::set_owner (object *owner)
{
  // allow objects which own objects
  if (owner)
    while (owner->owner)
      owner = owner->owner;

  if (flag [FLAG_FREED])
    {
      LOG (llevError | logBacktrace, "tried to set owner of %s to %s\n", debug_desc (), owner->debug_desc ());
      return;
    }

  this->owner = owner;
}

int
object::slottype () const
{
  if (type == SKILL)
    {
      if (IS_COMBAT_SKILL (subtype)) return slot_combat;
      if (IS_RANGED_SKILL (subtype)) return slot_ranged;
    }
  else
    {
      if (slot [body_combat].info) return slot_combat;
      if (slot [body_range ].info) return slot_ranged;
    }
  
  return slot_none;
}

bool
object::change_weapon (object *ob)
{
  if (current_weapon == ob)
    return true;

  if (chosen_skill)
    chosen_skill->flag [FLAG_APPLIED] = false;

  current_weapon = ob;
  chosen_skill = !ob || ob->type == SKILL ? ob : find_skill_by_name (this, ob->skill);

  if (chosen_skill)
    chosen_skill->flag [FLAG_APPLIED] = true;

  update_stats ();

  if (ob)
    {
      // now check wether any body locations became invalid, in which case
      // we cannot apply the weapon at the moment.
      for (int i = 0; i < NUM_BODY_LOCATIONS; ++i)
        if (slot[i].used < 0)
          {
            current_weapon = chosen_skill = 0;
            update_stats ();

            new_draw_info_format (NDI_UNIQUE, 0, this,
                                  "You try to balance all your items at once, "
                                  "but the %s is just too much for your body. "
                                  "[You need to unapply some items first - use the 'body' command to see "
                                  "how many items you cna wera on a specific body part.]", &ob->name);
            return false;
          }

      //new_draw_info_format (NDI_UNIQUE, 0, this, "You switch to your %s.", &ob->name);
    }
  else
    ;//new_draw_info_format (NDI_UNIQUE, 0, this, "You unwield your weapons.");

  if (ob && !ob->flag [FLAG_APPLIED] && ob->type != SPELL)
    {
      LOG (llevError | logBacktrace, "%s changed to unapplied weapon %s",
           &name, ob->debug_desc ());
      return false;
    }

  return true;
}

/* Zero the key_values on op, decrementing the shared-string
 * refcounts and freeing the links. 
 */
static void
free_key_values (object *op)
{
  for (key_value *i = op->key_values; i; )
    {
      key_value *next = i->next;
      delete i;

      i = next;
    }

  op->key_values = 0;
}

/*
 * copy_to first frees everything allocated by the dst object,
 * and then copies the contents of itself into the second
 * object, allocating what needs to be allocated.  Basically, any
 * data that is malloc'd needs to be re-malloc/copied.  Otherwise,
 * if the first object is freed, the pointers in the new object
 * will point at garbage.
 */
void
object::copy_to (object *dst)
{
  dst->remove ();
  *(object_copy *)dst = *this;
  dst->flag [FLAG_REMOVED] = true;

  /* Copy over key_values, if any. */
  if (key_values)
    {
      key_value *tail = 0;
      dst->key_values = 0;

      for (key_value *i = key_values; i; i = i->next)
        {
          key_value *new_link = new key_value;

          new_link->next  = 0;
          new_link->key   = i->key;
          new_link->value = i->value;

          /* Try and be clever here, too. */
          if (!dst->key_values)
            {
              dst->key_values = new_link;
              tail = new_link;
            }
          else
            {
              tail->next = new_link;
              tail = new_link;
            }
        }
    }

  if (speed < 0)
    dst->speed_left -= rndm ();

  dst->activate ();
}

void
object::instantiate ()
{
  if (!uuid.seq) // HACK
    uuid = UUID::gen ();

  speed_left = -0.1f;
  /* copy the body_info to the body_used - this is only really
   * need for monsters, but doesn't hurt to do it for everything.
   * by doing so, when a monster is created, it has good starting
   * values for the body_used info, so when items are created 
   * for it, they can be properly equipped.
   */
  for (int i = NUM_BODY_LOCATIONS; i--; )
    slot[i].used = slot[i].info;

  attachable::instantiate ();
}

object *
object::clone ()
{
  object *neu = create ();
  copy_to (neu);
  neu->map = map; // not copied by copy_to
  return neu;
}

/*
 * If an object with the IS_TURNABLE() flag needs to be turned due
 * to the closest player being on the other side, this function can
 * be called to update the face variable, _and_ how it looks on the map.
 */
void
update_turn_face (object *op)
{
  if (!QUERY_FLAG (op, FLAG_IS_TURNABLE) || !op->arch)
    return;

  SET_ANIMATION (op, op->direction);
  update_object (op, UP_OBJ_FACE);
}

/*
 * Updates the speed of an object.  If the speed changes from 0 to another
 * value, or vice versa, then add/remove the object from the active list.
 * This function needs to be called whenever the speed of an object changes.
 */
void
object::set_speed (float speed)
{
  if (flag [FLAG_FREED] && speed)
    {
      LOG (llevError, "Object %s is freed but has speed.\n", &name);
      speed = 0;
    }

  this->speed = speed;

  if (has_active_speed ())
    activate ();
  else
    deactivate ();
}

/*
 * update_object() updates the the map.
 * It takes into account invisible objects (and represent squares covered
 * by invisible objects by whatever is below them (unless it's another
 * invisible object, etc...)
 * If the object being updated is beneath a player, the look-window
 * of that player is updated (this might be a suboptimal way of
 * updating that window, though, since update_object() is called _often_)
 *
 * action is a hint of what the caller believes need to be done.
 * current action are:
 * UP_OBJ_INSERT: op was inserted
 * UP_OBJ_REMOVE: op was removed
 * UP_OBJ_CHANGE: object has somehow changed.  In this case, we always update
 *  as that is easier than trying to look at what may have changed.
 * UP_OBJ_FACE: only the objects face has changed.
 */
void
update_object (object *op, int action)
{
  if (!op)
    {
      /* this should never happen */
      LOG (llevError | logBacktrace, "update_object() called for NULL object.\n");
      return;
    }

  if (!op->is_on_map ())
    {
      /* Animation is currently handled by client, so nothing
       * to do in this case.
       */
      return;
    }

  /* make sure the object is within map boundaries */
  if (op->x < 0 || op->x >= op->map->width || op->y < 0 || op->y >= op->map->height)
    {
      LOG (llevError, "update_object() called for object out of map!\n");
#ifdef MANY_CORES
      abort ();
#endif
      return;
    }

  mapspace &m = op->ms ();

  if (!(m.flags_ & P_UPTODATE))
    /* nop */;
  else if (action == UP_OBJ_INSERT)
    {
      // this is likely overkill, TODO: revisit (schmorp)
      if ((QUERY_FLAG (op, FLAG_BLOCKSVIEW)  && !(m.flags_ & P_BLOCKSVIEW))
          || (QUERY_FLAG (op, FLAG_NO_MAGIC) && !(m.flags_ & P_NO_MAGIC))
          || (op->is_player ()               && !(m.flags_ & P_PLAYER))
          || (op->type == SAFE_GROUND        && !(m.flags_ & P_SAFE))
          || (QUERY_FLAG (op, FLAG_ALIVE)    && !(m.flags_ & P_IS_ALIVE))
          || (QUERY_FLAG (op, FLAG_DAMNED)   && !(m.flags_ & P_NO_CLERIC))
          || (m.move_on   | op->move_on  ) != m.move_on
          || (m.move_off  | op->move_off ) != m.move_off
          || (m.move_slow | op->move_slow) != m.move_slow
          /* This isn't perfect, but I don't expect a lot of objects to
           * have move_allow right now.    
           */
          || ((m.move_block | op->move_block) & ~op->move_allow) != m.move_block
          || 1) // the above is not strong enough a test to skip updating. los maybe? TODO (Schmorp)
        m.invalidate ();
    }
    /* if the object is being removed, we can't make intelligent
     * decisions, because remove_ob can't really pass the object
     * that is being removed.
     */
  else if (action == UP_OBJ_CHANGE || action == UP_OBJ_REMOVE)
    m.invalidate ();
  else if (action == UP_OBJ_FACE)
    /* Nothing to do for that case */ ;
  else
    LOG (llevError, "update_object called with invalid action: %d\n", action);

  if (op->more)
    update_object (op->more, action);
}

object::object ()
{
  SET_FLAG (this, FLAG_REMOVED);

  //expmul = 1.0; declared const for the time being
  face = blank_face;
}

object::~object ()
{
  unlink ();

  free_key_values (this);
}

static int object_count;

void object::link ()
{
  assert (!index);//D
  uuid = UUID::gen ();
  count = ++object_count;

  refcnt_inc ();
  objects.insert (this);
}

void object::unlink ()
{
  if (!index)
    return;

  objects.erase (this);
  refcnt_dec ();
}

void
object::activate ()
{
  /* If already on active list, don't do anything */
  if (active)
    return;

  if (has_active_speed ())
    {
      if (flag [FLAG_FREED])
        LOG (llevError | logBacktrace, "BUG: tried to activate freed object %s\n", debug_desc ());//D

      actives.insert (this);
    }
}

void
object::activate_recursive ()
{
  activate ();

  for (object *op = inv; op; op = op->below)
    op->activate_recursive ();
}

/* This function removes object 'op' from the list of active
 * objects.
 * This should only be used for style maps or other such 
 * reference maps where you don't want an object that isn't
 * in play chewing up cpu time getting processed.
 * The reverse of this is to call update_ob_speed, which
 * will do the right thing based on the speed of the object.
 */
void
object::deactivate ()
{
  /* If not on the active list, nothing needs to be done */
  if (!active)
    return;

  actives.erase (this);
}

void
object::deactivate_recursive ()
{
  for (object *op = inv; op; op = op->below)
    op->deactivate_recursive ();

  deactivate ();
}

void
object::set_flag_inv (int flag, int value)
{
  for (object *op = inv; op; op = op->below)
    {
      op->flag [flag] = value;
      op->set_flag_inv (flag, value);
    }
}

/*
 * Remove and free all objects in the inventory of the given object.
 * object.c ?
 */
void
object::destroy_inv (bool drop_to_ground)
{
  // need to check first, because the checks below might segfault
  // as we might be on an invalid mapspace and crossfire code
  // is too buggy to ensure that the inventory is empty.
  // corollary: if you create arrows etc. with stuff in its inventory,
  // cf will crash below with off-map x and y
  if (!inv)
    return;

  /* Only if the space blocks everything do we not process -
   * if some form of movement is allowed, let objects
   * drop on that space.
   */
  if (!drop_to_ground
      || !map
      || map->in_memory != MAP_ACTIVE
      || map->no_drop
      || ms ().move_block == MOVE_ALL)
    {
      while (inv)
        inv->destroy ();
    }
  else
    {                       /* Put objects in inventory onto this space */
      while (inv)
        {
          object *op = inv;

          if (op->flag [FLAG_STARTEQUIP]
              || op->flag [FLAG_NO_DROP]
              || op->type == RUNE
              || op->type == TRAP
              || op->flag [FLAG_IS_A_TEMPLATE]
              || op->flag [FLAG_DESTROY_ON_DEATH])
            op->destroy ();
          else
            map->insert (op, x, y);
        }
    }
}

object *object::create ()
{
  object *op = new object;
  op->link ();
  return op;
}

static struct freed_map : maptile
{
  freed_map ()
  {
    path     = "<freed objects map>";
    name     = "/internal/freed_objects_map";
    width    = 3;
    height   = 3;
    no_drop  = 1;
    no_reset = 1;

    alloc ();
    in_memory = MAP_ACTIVE;
  }

  ~freed_map ()
  {
    destroy ();
  }
} freed_map; // freed objects are moved here to avoid crashes

void
object::do_destroy ()
{
  if (flag [FLAG_IS_LINKED])
    remove_link ();

  if (flag [FLAG_FRIENDLY])
    remove_friendly_object (this);

  remove ();

  attachable::do_destroy ();

  deactivate ();
  unlink ();

  flag [FLAG_FREED] = 1;

  // hack to ensure that freed objects still have a valid map
  map = &freed_map;
  x = 1;
  y = 1;

  if (more)
    {
      more->destroy ();
      more = 0;
    }

  head = 0;

  // clear those pointers that likely might cause circular references
  owner          = 0;
  enemy          = 0;
  attacked_by    = 0;
  current_weapon = 0;
}

void
object::destroy ()
{
  if (destroyed ())
    return;

  if (!is_head () && !head->destroyed ())
    {
      LOG (llevError | logBacktrace, "tried to destroy the tail of an object");
      head->destroy ();
      return;
    }

  destroy_inv (false);

  if (is_head ())
    if (sound_destroy)
      play_sound (sound_destroy);
    else if (flag [FLAG_MONSTER])
      play_sound (sound_find ("monster_destroy")); // quick hack, too lazy to create a generic mechanism

  attachable::destroy ();
}

/* op->remove ():
 *   This function removes the object op from the linked list of objects
 *   which it is currently tied to.  When this function is done, the
 *   object will have no environment.  If the object previously had an
 *   environment, the x and y coordinates will be updated to
 *   the previous environment.
 */
void
object::do_remove ()
{
  object *tmp, *last = 0;
  object *otmp;

  if (flag [FLAG_REMOVED])
    return;

  INVOKE_OBJECT (REMOVE, this);

  flag [FLAG_REMOVED] = true;

  if (more)
    more->remove ();

  /* 
   * In this case, the object to be removed is in someones
   * inventory.
   */
  if (env)
    {
      flag [FLAG_REMOVED] = false; // hack around the issue of visible_to checking flag_removed
      if (object *pl = visible_to ())
        esrv_del_item (pl->contr, count);
      flag [FLAG_REMOVED] = true; // hack around the issue of visible_to checking flag_removed

      adjust_weight (env, -total_weight ());

      object *pl = in_player ();

      /* we set up values so that it could be inserted into
       * the map, but we don't actually do that - it is up
       * to the caller to decide what we want to do.
       */
      map   = env->map;
      x     = env->x;
      y     = env->y;

      // make sure cmov optimisation is applicable
      *(above ? &above->below : &env->inv) = below;
      *(below ? &below->above : &above   ) = above; // &above is just a dummy

      above = 0;
      below = 0;
      env   = 0;

      /* NO_FIX_PLAYER is set when a great many changes are being
       * made to players inventory.  If set, avoiding the call
       * to save cpu time.
       */
      if (pl)
        if (pl->is_player () && (glow_radius || !QUERY_FLAG (pl, FLAG_NO_FIX_PLAYER)))
          {
            pl->update_stats ();

            if (glow_radius && pl->is_on_map ())
              update_all_los (pl->map, pl->x, pl->y);
          }
    }
  else if (map)
    {
      map->dirty = true;
      mapspace &ms = this->ms ();

      if (object *pl = ms.player ())
        {
          if (is_player ())
            {
              if (!flag [FLAG_WIZPASS])
                ms.smell = ++mapspace::smellcount; // remember the smell of the player

              // leaving a spot always closes any open container on the ground
              if (container && !container->env)
                // this causes spurious floorbox updates, but it ensures
                // that the CLOSE event is being sent.
                close_container ();

              --map->players;
              map->touch ();
            }
          else if (pl->container == this)
            {
              // removing a container should close it
              close_container ();
            }

          esrv_del_item (pl->contr, count);
        }

      /* link the object above us */
      // re-link, make sure compiler can easily use cmove
      *(above ? &above->below : &ms.top) = below;
      *(below ? &below->above : &ms.bot) = above;

      above = 0;
      below = 0;

      ms.invalidate ();

      if (map->in_memory == MAP_SAVING)
        return;

      int check_walk_off = !flag [FLAG_NO_APPLY];

      if (object *pl = ms.player ())
        {
          if (pl->container == this)
            /* If a container that the player is currently using somehow gets
             * removed (most likely destroyed), update the player view
             * appropriately.
             */
            pl->close_container ();

          //TODO: the floorbox prev/next might need updating
          //esrv_del_item (pl->contr, count);
          //TODO: update floorbox to preserve ordering
          if (pl->contr->ns)
            pl->contr->ns->floorbox_update ();
        }

      for (tmp = ms.bot; tmp; tmp = tmp->above)
        {
          /* No point updating the players look faces if he is the object
           * being removed.
           */

          /* See if object moving off should effect something */
          if (check_walk_off
              && ((move_type & tmp->move_off)
                  && (move_type & ~tmp->move_off & ~tmp->move_block) == 0))
            {
              move_apply (tmp, this, 0);

              if (destroyed ())
                LOG (llevError, "BUG: remove_ob(): name %s, destroyed leaving object\n", tmp->debug_desc ());
            }

          last = tmp;
        }

      if (affects_los ())
        update_all_los (map, x, y);
    }
}

/*
 * merge_ob(op,top):
 *
 * This function goes through all objects below and including top, and
 * merges op to the first matching object.
 * If top is NULL, it is calculated.
 * Returns pointer to object if it succeded in the merge, otherwise NULL
 */
object *
merge_ob (object *op, object *top)
{
  if (!op->nrof)
    return 0;

  if (!top)
    for (top = op; top && top->above; top = top->above)
      ;

  for (; top; top = top->below)
    if (object::can_merge (op, top))
      {
        top->nrof += op->nrof;

        if (object *pl = top->visible_to ())
          esrv_update_item (UPD_NROF, pl, top);

        op->weight   = 0; // cancel the addition above
        op->carrying = 0; // must be 0 already

        op->destroy ();

        return top;
      }

  return 0;
}

void
object::expand_tail ()
{
  if (more)
    return;

  object *prev = this;

  for (archetype *at = (archetype *)arch->more; at; at = (archetype *)at->more)
    {
      object *op = arch_to_object (at);

      op->name    = name;
      op->name_pl = name_pl;
      op->title   = title;

      op->head = this;
      prev->more = op;

      prev = op;
    }
}

/*
 * same as insert_ob_in_map except it handles separate coordinates and does a clean
 * job preparing multi-part monsters.
 */
object *
insert_ob_in_map_at (object *op, maptile *m, object *originator, int flag, int x, int y)
{
  op->remove ();

  for (object *tmp = op->head_ (); tmp; tmp = tmp->more)
    {
      tmp->x = x + tmp->arch->x;
      tmp->y = y + tmp->arch->y;
    }

  return insert_ob_in_map (op, m, originator, flag);
}

/*
 * insert_ob_in_map (op, map, originator, flag):
 * This function inserts the object in the two-way linked list
 * which represents what is on a map.
 * The second argument specifies the map, and the x and y variables
 * in the object about to be inserted specifies the position.
 *
 * originator: Player, monster or other object that caused 'op' to be inserted
 * into 'map'.  May be NULL.
 *
 * flag is a bitmask about special things to do (or not do) when this
 * function is called.  see the object.h file for the INS_ values.
 * Passing 0 for flag gives proper default values, so flag really only needs
 * to be set if special handling is needed.
 *
 * Return value:
 *   new object if 'op' was merged with other object
 *   NULL if 'op' was destroyed
 *   just 'op' otherwise
 */
object *
insert_ob_in_map (object *op, maptile *m, object *originator, int flag)
{
  op->remove ();

  if (m == &freed_map)//D TODO: remove soon
    {//D
      LOG (llevError | logBacktrace, "tries to insret object on freed objects map: %s", op->debug_desc ());//D
    }//D

  /* Ideally, the caller figures this out.  However, it complicates a lot
   * of areas of callers (eg, anything that uses find_free_spot would now
   * need extra work
   */
  maptile *newmap = m;
  if (!xy_normalise (newmap, op->x, op->y))
    {
      op->head_ ()->destroy ();// remove head_ once all tail object destroyers found
      return 0;
    }

  if (object *more = op->more)
    if (!insert_ob_in_map (more, m, originator, flag))
      return 0;

  op->flag [FLAG_REMOVED] = false;
  op->env = 0;
  op->map = newmap;

  mapspace &ms = op->ms ();

  /* this has to be done after we translate the coordinates.
   */
  if (op->nrof && !(flag & INS_NO_MERGE))
    for (object *tmp = ms.bot; tmp; tmp = tmp->above)
      if (object::can_merge (op, tmp))
        {
          // TODO: we actually want to update tmp, not op,
          // but some caller surely breaks when we return tmp
          // from here :/
          op->nrof += tmp->nrof;
          tmp->destroy ();
        }

  CLEAR_FLAG (op, FLAG_APPLIED);        /* hack for fixing F_APPLIED in items of dead people */
  CLEAR_FLAG (op, FLAG_INV_LOCKED);

  if (!QUERY_FLAG (op, FLAG_ALIVE))
    CLEAR_FLAG (op, FLAG_NO_STEAL);

  if (flag & INS_BELOW_ORIGINATOR)
    {
      if (originator->map != op->map || originator->x != op->x || originator->y != op->y)
        {
          LOG (llevError, "insert_ob_in_map called with INS_BELOW_ORIGINATOR when originator not on same space!\n");
          abort ();
        }

      if (!originator->is_on_map ())
        {
          LOG (llevError, "insert_ob_in_map(%s) called with INS_BELOW_ORIGINATOR when originator '%s' not on map",
               op->debug_desc (), originator->debug_desc ());
          abort ();
        }

      op->above = originator;
      op->below = originator->below;
      originator->below = op;

      *(op->below ? &op->below->above : &ms.bot) = op;
    }
  else
    {
      object *floor = 0;
      object *top   = ms.top;

      /* If there are other objects, then */
      if (top)
        {
          /*
           * If there are multiple objects on this space, we do some trickier handling.
           * We've already dealt with merging if appropriate.
           * Generally, we want to put the new object on top. But if
           * flag contains INS_ABOVE_FLOOR_ONLY, once we find the last
           * floor, we want to insert above that and no further.
           * Also, if there are spell objects on this space, we stop processing
           * once we get to them.  This reduces the need to traverse over all of 
           * them when adding another one - this saves quite a bit of cpu time
           * when lots of spells are cast in one area.  Currently, it is presumed
           * that flying non pickable objects are spell objects.
           */
          for (object *tmp = ms.bot; tmp; tmp = tmp->above)
            {
              if (QUERY_FLAG (tmp, FLAG_IS_FLOOR) || QUERY_FLAG (tmp, FLAG_OVERLAY_FLOOR))
                floor = tmp;

              if (QUERY_FLAG (tmp, FLAG_NO_PICK) && (tmp->move_type & (MOVE_FLY_LOW | MOVE_FLY_HIGH)) && !QUERY_FLAG (tmp, FLAG_IS_FLOOR))
                {
                  /* We insert above top, so we want this object below this */
                  top = tmp->below;
                  break;
                }

              top = tmp;
            }

          /* We let update_position deal with figuring out what the space
           * looks like instead of lots of conditions here.
           * makes things faster, and effectively the same result.
           */

          /* Have object 'fall below' other objects that block view.
           * Unless those objects are exits.
           * If INS_ON_TOP is used, don't do this processing
           * Need to find the object that in fact blocks view, otherwise
           * stacking is a bit odd.
           */
          if (!(flag & INS_ON_TOP)
              && ms.flags () & P_BLOCKSVIEW
              && (op->face && !faces [op->face].visibility))
            {
              object *last;

              for (last = top; last != floor; last = last->below)
                if (QUERY_FLAG (last, FLAG_BLOCKSVIEW) && (last->type != EXIT))
                  break;

              /* Check to see if we found the object that blocks view,
               * and make sure we have a below pointer for it so that
               * we can get inserted below this one, which requires we
               * set top to the object below us.
               */
              if (last && last->below && last != floor)
                top = last->below;
            }
        }                       /* If objects on this space */

      if (flag & INS_ABOVE_FLOOR_ONLY)
        top = floor;

      // insert object above top, or bottom-most if top = 0
      if (!top)
        {
          op->below = 0;
          op->above = ms.bot;
          ms.bot = op;

          *(op->above ? &op->above->below : &ms.top) = op;
        }
      else
        {
          op->above = top->above;
          top->above = op;

          op->below = top;
          *(op->above ? &op->above->below : &ms.top) = op;
        }
    }

  if (op->is_player ())
    {
      op->contr->do_los = 1;
      ++op->map->players;
      op->map->touch ();
    }

  op->map->dirty = true;

  if (object *pl = ms.player ())
    //TODO: the floorbox prev/next might need updating
    //esrv_send_item (pl, op);
    //TODO: update floorbox to preserve ordering
    if (pl->contr->ns)
      pl->contr->ns->floorbox_update ();

  /* If this object glows, it may affect lighting conditions that are
   * visible to others on this map.  But update_all_los is really
   * an inefficient way to do this, as it means los for all players
   * on the map will get recalculated.  The players could very well
   * be far away from this change and not affected in any way -
   * this should get redone to only look for players within range,
   * or just updating the P_UPTODATE for spaces within this area
   * of effect may be sufficient.
   */
  if (op->affects_los ())
    {
      op->ms ().invalidate ();
      update_all_los (op->map, op->x, op->y);
    }

  /* updates flags (blocked, alive, no magic, etc) for this map space */
  update_object (op, UP_OBJ_INSERT);

  INVOKE_OBJECT (INSERT, op);

  /* Don't know if moving this to the end will break anything.  However,
   * we want to have floorbox_update called before calling this.
   *
   * check_move_on() must be after this because code called from
   * check_move_on() depends on correct map flags (so functions like
   * blocked() and wall() work properly), and these flags are updated by
   * update_object().
   */

  /* if this is not the head or flag has been passed, don't check walk on status */
  if (!(flag & INS_NO_WALK_ON) && op->is_head ())
    {
      if (check_move_on (op, originator))
        return 0;

      /* If we are a multi part object, lets work our way through the check
       * walk on's.
       */
      for (object *tmp = op->more; tmp; tmp = tmp->more)
        if (check_move_on (tmp, originator))
          return 0;
    }

  return op;
}

/* this function inserts an object in the map, but if it
 * finds an object of its own type, it'll remove that one first. 
 * op is the object to insert it under: supplies x and the map.
 */
void
replace_insert_ob_in_map (shstr_tmp archname, object *op)
{
  /* first search for itself and remove any old instances */

  for (object *tmp = op->ms ().bot; tmp; tmp = tmp->above)
    if (tmp->arch->archname == archname)       /* same archetype */
      tmp->destroy ();

  object *tmp = arch_to_object (archetype::find (archname));

  tmp->x = op->x;
  tmp->y = op->y;

  insert_ob_in_map (tmp, op->map, op, 0);
}

object *
object::insert_at (object *where, object *originator, int flags)
{
  if (where->env)
    return where->env->insert (this);
  else
    return where->map->insert (this, where->x, where->y, originator, flags);
}

/*
 * decrease(object, number) decreases a specified number from
 * the amount of an object. If the amount reaches 0, the object
 * is subsequently removed and freed.
 *
 * Return value: 'op' if something is left, NULL if the amount reached 0
 */
bool
object::decrease (sint32 nr)
{
  if (!nr)
    return true;

  nr = min (nr, nrof);

  if (nrof > nr)
    {
      nrof -= nr;
      adjust_weight (env, -weight * max (1, nr)); // carrying == 0

      if (object *pl = visible_to ())
        esrv_update_item (UPD_NROF, pl, this);

      return true;
    }
  else
    {
      destroy ();
      return false;
    }
}

/*
 * split(ob,nr) splits up ob into two parts.  The part which
 * is returned contains nr objects, and the remaining parts contains
 * the rest (or is removed and returned if that number is 0).
 * On failure, NULL is returned.
 */
object *
object::split (sint32 nr)
{
  int have = number_of ();

  if (have < nr)
    return 0;
  else if (have == nr)
    {
      remove ();
      return this;
    }
  else
    {
      decrease (nr);

      object *op = deep_clone ();
      op->nrof = nr;
      return op;
    }
}

object *
insert_ob_in_ob (object *op, object *where)
{
  if (!where)
    {
      char *dump = dump_object (op);
      LOG (llevError, "Trying to put object in NULL.\n%s\n", dump);
      free (dump);
      return op;
    }

  if (where->head_ () != where)
    {
      LOG (llevError | logBacktrace, "Warning: Tried to insert object into wrong part of multipart object.\n");
      where = where->head;
    }

  return where->insert (op);
}

/*
 * env->insert (op)
 *   This function inserts the object op in the linked list
 *   inside the object environment.
 *
 * The function returns now pointer to inserted item, and return value can 
 * be != op, if items are merged. -Tero
 */
object *
object::insert (object *op)
{
  if (op->more)
    {
      LOG (llevError, "Tried to insert multipart object %s (%d)\n", &op->name, op->count);
      return op;
    }

  op->remove ();

  op->flag [FLAG_OBJ_ORIGINAL] = 0;

  if (op->nrof)
    for (object *tmp = inv; tmp; tmp = tmp->below)
      if (object::can_merge (tmp, op))
        {
          /* return the original object and remove inserted object
             (client needs the original object) */
          tmp->nrof += op->nrof;

          if (object *pl = tmp->visible_to ())
            esrv_update_item (UPD_NROF, pl, tmp);

          adjust_weight (this, op->total_weight ());

          op->destroy ();
          op = tmp;
          goto inserted;
        }

  op->owner = 0; // it's his/hers now. period.
  op->map   = 0;
  op->x     = 0;
  op->y     = 0;

  op->above = 0;
  op->below = inv;
  op->env   = this;

  if (inv)
    inv->above = op;

  inv = op;

  op->flag [FLAG_REMOVED] = 0;

  if (object *pl = op->visible_to ())
    esrv_send_item (pl, op);

  adjust_weight (this, op->total_weight ());

inserted:
  /* reset the light list and los of the players on the map */
  if (op->glow_radius && is_on_map ())
    {
      update_stats ();
      update_all_los (map, x, y);
    }
  else if (is_player () && !flag [FLAG_NO_FIX_PLAYER])
    // if this is a player's inventory, update stats
    update_stats ();

  INVOKE_OBJECT (INSERT, this);

  return op;
}

/*
 * Checks if any objects has a move_type that matches objects
 * that effect this object on this space.  Call apply() to process
 * these events.
 *
 * Any speed-modification due to SLOW_MOVE() of other present objects
 * will affect the speed_left of the object.
 *
 * originator: Player, monster or other object that caused 'op' to be inserted
 * into 'map'.  May be NULL.
 *
 * Return value: 1 if 'op' was destroyed, 0 otherwise.
 *
 * 4-21-95 added code to check if appropriate skill was readied - this will
 * permit faster movement by the player through this terrain. -b.t.
 *
 * MSW 2001-07-08: Check all objects on space, not just those below
 * object being inserted.  insert_ob_in_map may not put new objects
 * on top.
 */
int
check_move_on (object *op, object *originator)
{
  if (QUERY_FLAG (op, FLAG_NO_APPLY))
    return 0;

  object *tmp;
  maptile *m = op->map;
  int x = op->x, y = op->y;

  mapspace &ms = m->at (x, y);

  ms.update ();

  MoveType move_on    = ms.move_on;
  MoveType move_slow  = ms.move_slow;
  MoveType move_block = ms.move_block;

  /* if nothing on this space will slow op down or be applied,
   * no need to do checking below.    have to make sure move_type
   * is set, as lots of objects don't have it set - we treat that
   * as walking.
   */
  if (op->move_type && !(op->move_type & move_on) && !(op->move_type & move_slow))
    return 0;

  /* This is basically inverse logic of that below - basically,
   * if the object can avoid the move on or slow move, they do so,
   * but can't do it if the alternate movement they are using is
   * blocked.  Logic on this seems confusing, but does seem correct.
   */
  if ((op->move_type & ~move_on & ~move_block) != 0 && (op->move_type & ~move_slow & ~move_block) != 0)
    return 0;

  /* The objects have to be checked from top to bottom.
   * Hence, we first go to the top: 
   */
  for (object *next, *tmp = ms.top; tmp; tmp = next)
    {
      next = tmp->below;

      if (tmp == op)
        continue;               /* Can't apply yourself */

      /* Check to see if one of the movement types should be slowed down.
       * Second check makes sure that the movement types not being slowed
       * (~slow_move) is not blocked on this space - just because the
       * space doesn't slow down swimming (for example), if you can't actually
       * swim on that space, can't use it to avoid the penalty.
       */
      if (!QUERY_FLAG (op, FLAG_WIZPASS))
        {
          if ((!op->move_type && tmp->move_slow & MOVE_WALK) ||
              ((op->move_type & tmp->move_slow) && (op->move_type & ~tmp->move_slow & ~tmp->move_block) == 0))
            {
              float diff = tmp->move_slow_penalty * fabs (op->speed);

              if (op->is_player ())
                if ((tmp->flag [FLAG_IS_HILLY ] && find_skill_by_number (op, SK_CLIMBING)) ||
                    (tmp->flag [FLAG_IS_WOODED] && find_skill_by_number (op, SK_WOODSMAN)))
                  diff /= 4.0;

              op->speed_left -= diff;
            }
        }

      /* Basically same logic as above, except now for actual apply. */
      if ((!op->move_type && tmp->move_on & MOVE_WALK) ||
          ((op->move_type & tmp->move_on) && (op->move_type & ~tmp->move_on & ~tmp->move_block) == 0))
        {
          move_apply (tmp, op, originator);

          if (op->destroyed ())
            return 1;

          /* what the person/creature stepped onto has moved the object
           * someplace new.  Don't process any further - if we did,
           * have a feeling strange problems would result.
           */
          if (op->map != m || op->x != x || op->y != y)
            return 0;
        }
    }

  return 0;
}

/*
 * present_arch(arch, map, x, y) searches for any objects with
 * a matching archetype at the given map and coordinates.
 * The first matching object is returned, or NULL if none.
 */
object *
present_arch (const archetype *at, maptile *m, int x, int y)
{
  if (!m || out_of_map (m, x, y))
    {
      LOG (llevError, "Present_arch called outside map.\n");
      return NULL;
    }

  for (object *tmp = m->at (x, y).bot; tmp; tmp = tmp->above)
    if (tmp->arch->archname == at->archname)
      return tmp;

  return NULL;
}

/*
 * present(type, map, x, y) searches for any objects with
 * a matching type variable at the given map and coordinates.
 * The first matching object is returned, or NULL if none.
 */
object *
present (unsigned char type, maptile *m, int x, int y)
{
  if (out_of_map (m, x, y))
    {
      LOG (llevError, "Present called outside map.\n");
      return NULL;
    }

  for (object *tmp = m->at (x, y).bot; tmp; tmp = tmp->above)
    if (tmp->type == type)
      return tmp;

  return NULL;
}

/*
 * present_in_ob(type, object) searches for any objects with
 * a matching type variable in the inventory of the given object.
 * The first matching object is returned, or NULL if none.
 */
object *
present_in_ob (unsigned char type, const object *op)
{
  for (object *tmp = op->inv; tmp != NULL; tmp = tmp->below)
    if (tmp->type == type)
      return tmp;

  return NULL;
}

/*
 * present_in_ob (type, str, object) searches for any objects with
 * a matching type & name variable in the inventory of the given object.
 * The first matching object is returned, or NULL if none.
 * This is mostly used by spell effect code, so that we only
 * have one spell effect at a time.
 * type can be used to narrow the search - if type is set,
 * the type must also match.  -1 can be passed for the type,
 * in which case the type does not need to pass.
 * str is the string to match against.  Note that we match against
 * the object name, not the archetype name.  this is so that the
 * spell code can use one object type (force), but change it's name
 * to be unique.
 */
object *
present_in_ob_by_name (int type, const char *str, const object *op)
{
  for (object *tmp = op->inv; tmp; tmp = tmp->below)
    if ((type == -1 || tmp->type == type) && (!strcmp (str, tmp->name)))
      return tmp;

  return 0;
}

/*
 * present_arch_in_ob(archetype, object) searches for any objects with
 * a matching archetype in the inventory of the given object.
 * The first matching object is returned, or NULL if none.
 */
object *
present_arch_in_ob (const archetype *at, const object *op)
{
  for (object *tmp = op->inv; tmp; tmp = tmp->below)
    if (tmp->arch->archname == at->archname)
      return tmp;

  return NULL;
}

/*
 * activate recursively a flag on an object inventory
 */
void
flag_inv (object *op, int flag)
{
  for (object *tmp = op->inv; tmp; tmp = tmp->below)
    {
      SET_FLAG (tmp, flag);
      flag_inv (tmp, flag);
    }
}

/*
 * deactivate recursively a flag on an object inventory
 */
void
unflag_inv (object *op, int flag)
{
  for (object *tmp = op->inv; tmp; tmp = tmp->below)
    {
      CLEAR_FLAG (tmp, flag);
      unflag_inv (tmp, flag);
    }
}

/*
 * find_free_spot(object, map, x, y, start, stop) will search for
 * a spot at the given map and coordinates which will be able to contain
 * the given object.  start and stop specifies how many squares
 * to search (see the freearr_x/y[] definition).
 * It returns a random choice among the alternatives found.
 * start and stop are where to start relative to the free_arr array (1,9
 * does all 4 immediate directions).  This returns the index into the
 * array of the free spot, -1 if no spot available (dir 0 = x,y)
 * Note: This function does correctly handle tiled maps, but does not
 * inform the caller.  However, insert_ob_in_map will update as
 * necessary, so the caller shouldn't need to do any special work.
 * Note - updated to take an object instead of archetype - this is necessary
 * because arch_blocked (now ob_blocked) needs to know the movement type
 * to know if the space in question will block the object.  We can't use
 * the archetype because that isn't correct if the monster has been 
 * customized, changed states, etc.
 */
int
find_free_spot (const object *ob, maptile *m, int x, int y, int start, int stop)
{
  int altern[SIZEOFFREE];
  int index = 0, flag;

  for (int i = start; i < stop; i++)
    {
      mapxy pos (m, x, y); pos.move (i);

      if (!pos.normalise ())
        continue;

      mapspace &ms = *pos;

      if (ms.flags () & P_IS_ALIVE)
        continue;

      /* However, often
       * ob doesn't have any move type (when used to place exits)
       * so the AND operation in OB_TYPE_MOVE_BLOCK doesn't work.
       */
      if (ob && ob->move_type == 0 && ms.move_block != MOVE_ALL)
        {
          altern [index++] = i;
          continue;
        }

      /* Basically, if we find a wall on a space, we cut down the search size.
       * In this way, we won't return spaces that are on another side of a wall.
       * This mostly work, but it cuts down the search size in all directions - 
       * if the space being examined only has a wall to the north and empty
       * spaces in all the other directions, this will reduce the search space
       * to only the spaces immediately surrounding the target area, and
       * won't look 2 spaces south of the target space.
       */
      if (ms.move_block == MOVE_ALL && maxfree[i] < stop)
        {
          stop = maxfree[i];
          continue;
        }

      /* Note it is intentional that we check ob - the movement type of the
       * head of the object should correspond for the entire object.
       */
      if (OB_TYPE_MOVE_BLOCK (ob, ms.move_block))
        continue;

      if (ob->blocked (pos.m, pos.x, pos.y))
        continue;

      altern [index++] = i;
    }

  if (!index)
    return -1;

  return altern [rndm (index)];
}

/*
 * find_first_free_spot(archetype, maptile, x, y) works like
 * find_free_spot(), but it will search max number of squares.
 * But it will return the first available spot, not a random choice.
 * Changed 0.93.2: Have it return -1 if there is no free spot available.
 */
int
find_first_free_spot (const object *ob, maptile *m, int x, int y)
{
  for (int i = 0; i < SIZEOFFREE; i++)
    if (!ob->blocked (m, x + freearr_x[i], y + freearr_y[i]))
      return i;

  return -1;
}

/*
 * The function permute(arr, begin, end) randomly reorders the array
 * arr[begin..end-1].
 * now uses a fisher-yates shuffle, old permute was broken
 */
static void
permute (int *arr, int begin, int end)
{
  arr += begin;
  end -= begin;

  while (--end)
    swap (arr [end], arr [rndm (end + 1)]);
}

/* new function to make monster searching more efficient, and effective! 
 * This basically returns a randomized array (in the passed pointer) of
 * the spaces to find monsters.  In this way, it won't always look for
 * monsters to the north first.  However, the size of the array passed
 * covers all the spaces, so within that size, all the spaces within
 * the 3x3 area will be searched, just not in a predictable order.
 */
void
get_search_arr (int *search_arr)
{
  int i;

  for (i = 0; i < SIZEOFFREE; i++)
    search_arr[i] = i;

  permute (search_arr, 1, SIZEOFFREE1 + 1);
  permute (search_arr, SIZEOFFREE1 + 1, SIZEOFFREE2 + 1);
  permute (search_arr, SIZEOFFREE2 + 1, SIZEOFFREE);
}

/*
 * find_dir(map, x, y, exclude) will search some close squares in the
 * given map at the given coordinates for live objects.
 * It will not considered the object given as exclude among possible
 * live objects.
 * It returns the direction toward the first/closest live object if finds
 * any, otherwise 0.
 * Perhaps incorrectly, but I'm making the assumption that exclude
 * is actually want is going to try and move there.  We need this info
 * because we have to know what movement the thing looking to move
 * there is capable of.
 */
int
find_dir (maptile *m, int x, int y, object *exclude)
{
  int max = SIZEOFFREE, mflags;
  MoveType move_type;

  if (exclude && exclude->head_ () != exclude)
    {
      exclude = exclude->head;
      move_type = exclude->move_type;
    }
  else
    {
      /* If we don't have anything, presume it can use all movement types. */
      move_type = MOVE_ALL;
    }

  for (int i = 1; i < max; i++)
    {
      mapxy pos (m, x, y);
      pos.move (i);

      if (!pos.normalise ())
        max = maxfree[i];
      else
        {
          mapspace &ms = *pos;

          if ((move_type & ms.move_block) == move_type)
            max = maxfree [i];
          else if (ms.flags () & P_IS_ALIVE)
            {
              for (object *tmp = ms.bot; tmp; tmp = tmp->above)
                if ((tmp->flag [FLAG_MONSTER] || tmp->is_player ())
                    && (tmp != exclude || (tmp->head_ () != tmp && tmp->head_ () != exclude)))
                  return freedir [i];
            }
        }
    }

  return 0;
}

/*
 * distance(object 1, object 2) will return the square of the
 * distance between the two given objects.
 */
int
distance (const object *ob1, const object *ob2)
{
  return (ob1->x - ob2->x) * (ob1->x - ob2->x) + (ob1->y - ob2->y) * (ob1->y - ob2->y);
}

/*
 * find_dir_2(delta-x,delta-y) will return a direction in which
 * an object which has subtracted the x and y coordinates of another
 * object, needs to travel toward it.
 */
int
find_dir_2 (int x, int y)
{
  int q;

  if (y)
    q = x * 100 / y;
  else if (x)
    q = -300 * x;
  else
    return 0;

  if (y > 0)
    {
      if (q < -242)
        return 3;
      if (q < -41)
        return 2;
      if (q < 41)
        return 1;
      if (q < 242)
        return 8;
      return 7;
    }

  if (q < -242)
    return 7;
  if (q < -41)
    return 6;
  if (q < 41)
    return 5;
  if (q < 242)
    return 4;

  return 3;
}

/*
 * dirdiff(dir1, dir2) returns how many 45-degrees differences there is
 * between two directions (which are expected to be absolute (see absdir())
 */
int
dirdiff (int dir1, int dir2)
{
  int d;

  d = abs (dir1 - dir2);
  if (d > 4)
    d = 8 - d;

  return d;
}

/* peterm:
 * do LOS stuff for ball lightning.  Go after the closest VISIBLE monster.
 * Basically, this is a table of directions, and what directions
 * one could go to go back to us.  Eg, entry 15 below is 4, 14, 16.
 * This basically means that if direction is 15, then it could either go
 * direction 4, 14, or 16 to get back to where we are.
 * Moved from spell_util.c to object.c with the other related direction
 * functions.
 */
const int reduction_dir[SIZEOFFREE][3] = {
  {0, 0, 0},                    /* 0 */
  {0, 0, 0},                    /* 1 */
  {0, 0, 0},                    /* 2 */
  {0, 0, 0},                    /* 3 */
  {0, 0, 0},                    /* 4 */
  {0, 0, 0},                    /* 5 */
  {0, 0, 0},                    /* 6 */
  {0, 0, 0},                    /* 7 */
  {0, 0, 0},                    /* 8 */
  {8, 1, 2},                    /* 9 */
  {1, 2, -1},                   /* 10 */
  {2, 10, 12},                  /* 11 */
  {2, 3, -1},                   /* 12 */
  {2, 3, 4},                    /* 13 */
  {3, 4, -1},                   /* 14 */
  {4, 14, 16},                  /* 15 */
  {5, 4, -1},                   /* 16 */
  {4, 5, 6},                    /* 17 */
  {6, 5, -1},                   /* 18 */
  {6, 20, 18},                  /* 19 */
  {7, 6, -1},                   /* 20 */
  {6, 7, 8},                    /* 21 */
  {7, 8, -1},                   /* 22 */
  {8, 22, 24},                  /* 23 */
  {8, 1, -1},                   /* 24 */
  {24, 9, 10},                  /* 25 */
  {9, 10, -1},                  /* 26 */
  {10, 11, -1},                 /* 27 */
  {27, 11, 29},                 /* 28 */
  {11, 12, -1},                 /* 29 */
  {12, 13, -1},                 /* 30 */
  {12, 13, 14},                 /* 31 */
  {13, 14, -1},                 /* 32 */
  {14, 15, -1},                 /* 33 */
  {33, 15, 35},                 /* 34 */
  {16, 15, -1},                 /* 35 */
  {17, 16, -1},                 /* 36 */
  {18, 17, 16},                 /* 37 */
  {18, 17, -1},                 /* 38 */
  {18, 19, -1},                 /* 39 */
  {41, 19, 39},                 /* 40 */
  {19, 20, -1},                 /* 41 */
  {20, 21, -1},                 /* 42 */
  {20, 21, 22},                 /* 43 */
  {21, 22, -1},                 /* 44 */
  {23, 22, -1},                 /* 45 */
  {45, 47, 23},                 /* 46 */
  {23, 24, -1},                 /* 47 */
  {24, 9, -1}
};                              /* 48 */

/* Recursive routine to step back and see if we can
 * find a path to that monster that we found.  If not,
 * we don't bother going toward it.  Returns 1 if we
 * can see a direct way to get it
 * Modified to be map tile aware -.MSW
 */
int
can_see_monsterP (maptile *m, int x, int y, int dir)
{
  sint16 dx, dy;
  int mflags;

  if (dir < 0)
    return 0;                   /* exit condition:  invalid direction */

  dx = x + freearr_x[dir];
  dy = y + freearr_y[dir];

  mflags = get_map_flags (m, &m, dx, dy, &dx, &dy);

  /* This functional arguably was incorrect before - it was
   * checking for P_WALL - that was basically seeing if
   * we could move to the monster - this is being more
   * literal on if we can see it.  To know if we can actually
   * move to the monster, we'd need the monster passed in or
   * at least its move type.
   */
  if (mflags & (P_OUT_OF_MAP | P_BLOCKSVIEW))
    return 0;

  /* yes, can see. */
  if (dir < 9)
    return 1;

  return can_see_monsterP (m, x, y, reduction_dir[dir][0])
         | can_see_monsterP (m, x, y, reduction_dir[dir][1])
         | can_see_monsterP (m, x, y, reduction_dir[dir][2]);
}

/*
 * can_pick(picker, item): finds out if an object is possible to be
 * picked up by the picker.  Returnes 1 if it can be
 * picked up, otherwise 0.
 *
 * Cf 0.91.3 - don't let WIZ's pick up anything - will likely cause
 * core dumps if they do.
 *
 * Add a check so we can't pick up invisible objects (0.93.8)
 */
int
can_pick (const object *who, const object *item)
{
  return                        /*QUERY_FLAG(who,FLAG_WIZ)|| */
    (item->weight > 0 && !QUERY_FLAG (item, FLAG_NO_PICK) &&
     !QUERY_FLAG (item, FLAG_ALIVE) && !item->invisible && (who->is_player () || item->weight < who->weight / 3));
}

/*
 * create clone from object to another
 */
object *
object::deep_clone ()
{
  assert (("deep_clone called on non-head object", is_head ()));

  object *dst = clone ();

  object *prev = dst;
  for (object *part = this->more; part; part = part->more)
    {
      object *tmp = part->clone ();
      tmp->head = dst;
      prev->more = tmp;
      prev = tmp;
    }

  for (object *item = inv; item; item = item->below)
    insert_ob_in_ob (item->deep_clone (), dst);

  return dst;
}

/* This returns the first object in who's inventory that
 * has the same type and subtype match.
 * returns NULL if no match.
 */
object *
find_obj_by_type_subtype (const object *who, int type, int subtype)
{
  for (object *tmp = who->inv; tmp; tmp = tmp->below)
    if (tmp->type == type && tmp->subtype == subtype)
      return tmp;

  return 0;
}

shstr_tmp
object::kv_get (shstr_tmp key) const
{
  for (key_value *kv = key_values; kv; kv = kv->next)
    if (kv->key == key)
      return kv->value;

  return shstr ();
}

void
object::kv_set (shstr_tmp key, shstr_tmp value)
{
  for (key_value *kv = key_values; kv; kv = kv->next)
    if (kv->key == key)
      {
        kv->value = value;
        return;
      }

  key_value *kv = new key_value;

  kv->next  = key_values;
  kv->key   = key;
  kv->value = value;

  key_values = kv;
}

void
object::kv_del (shstr_tmp key)
{
  for (key_value **kvp = &key_values; *kvp; kvp = &(*kvp)->next)
    if ((*kvp)->key == key)
      {
        key_value *kv = *kvp;
        *kvp = (*kvp)->next;
        delete kv;
        return;
      }
}

object::depth_iterator::depth_iterator (object *container)
: iterator_base (container)
{
  while (item->inv)
    item = item->inv;
}

void
object::depth_iterator::next ()
{
  if (item->below)
    {
      item = item->below;

      while (item->inv)
        item = item->inv;
    }
  else
    item = item->env;
}

const char *
object::flag_desc (char *desc, int len) const
{
  char *p = desc;
  bool first = true;

  *p = 0;

  for (int i = 0; i < NUM_FLAGS; i++)
    {
      if (len <= 10) // magic constant!
        {
          snprintf (p, len, ",...");
          break;
        }

      if (flag [i])
        {
          int cnt = snprintf (p, len, "%s%d", first ? "" : ",", i);
          len -= cnt;
          p += cnt;
          first = false;
        }
    }

  return desc;
}

// return a suitable string describing an object in enough detail to find it
const char *
object::debug_desc (char *info) const
{
  char flagdesc[512];
  char info2[256 * 4];
  char *p = info;

  p += snprintf (p, 512, "{cnt:%d,uuid:%s,name:\"%s\"%s%s%s,flags:[%s],type:%d}",
                 count,
                 uuid.c_str (),
                 &name,
                 title ? ",title:\"" : "",
                 title ? (const char *)title : "",
                 title ? "\"" : "",
                 flag_desc (flagdesc, 512), type);

  if (!flag[FLAG_REMOVED] && env)
    p += snprintf (p, 256, "(in %s)", env->debug_desc (info2));

  if (map)
    p += snprintf (p, 256, "(on %s@%d+%d)", &map->path, x, y);

  return info;
}

const char *
object::debug_desc () const
{
  static char info[3][256 * 4];
  static int info_idx;

  return debug_desc (info [++info_idx % 3]);
}

struct region *
object::region () const
{
  return map ? map->region (x, y)
             : region::default_region ();
}

const materialtype_t *
object::dominant_material () const
{
  if (materialtype_t *mt = name_to_material (materialname))
    return mt;

  return name_to_material (shstr_unknown);
}

void
object::open_container (object *new_container)
{
  if (container == new_container)
    return;

  object *old_container = container;

  if (old_container)
    {
      if (INVOKE_OBJECT (CLOSE, old_container, ARG_OBJECT (this)))
        return;

#if 0
      // remove the "Close old_container" object.
      if (object *closer = old_container->inv)
        if (closer->type == CLOSE_CON)
          closer->destroy ();
#endif

      // make sure the container is available
      esrv_send_item (this, old_container);

      old_container->flag [FLAG_APPLIED] = false;
      container = 0;

      // client needs item update to make it work, client bug requires this to be separate
      esrv_update_item (UPD_FLAGS, this, old_container);

      new_draw_info_format (NDI_UNIQUE, 0, this, "You close %s.", old_container->query_name ());
      play_sound (sound_find ("chest_close"));
    }

  if (new_container)
    {
      if (INVOKE_OBJECT (OPEN, new_container, ARG_OBJECT (this)))
        return;

      // TODO: this does not seem to serve any purpose anymore?
#if 0
      // insert the "Close Container" object.
      if (archetype *closer = new_container->other_arch)
        {
          object *closer = arch_to_object (new_container->other_arch);
          closer->flag [FLAG_NO_MAP_SAVE] = 1;
          new_container->insert (closer);
        }
#endif

      new_draw_info_format (NDI_UNIQUE, 0, this, "You open %s.", new_container->query_name ());

      // make sure the container is available, client bug requires this to be separate
      esrv_send_item (this, new_container);

      new_container->flag [FLAG_APPLIED] = true;
      container = new_container;

      // client needs flag change
      esrv_update_item (UPD_FLAGS, this, new_container);
      esrv_send_inventory (this, new_container);
      play_sound (sound_find ("chest_open"));
    }
//  else if (!old_container->env && contr && contr->ns)
//    contr->ns->floorbox_reset ();
}

object *
object::force_find (shstr_tmp name)
{
  /* cycle through his inventory to look for the MARK we want to 
   * place 
   */
  for (object *tmp = inv; tmp; tmp = tmp->below)
    if (tmp->type == FORCE && tmp->slaying == name)
      return splay (tmp);

  return 0;
}

void
object::force_set_timer (int duration)
{
  this->duration   = 1;
  this->speed_left = -1.f;

  this->set_speed (duration ? 1.f / duration : 0.f);
}

object *
object::force_add (shstr_tmp name, int duration)
{
  if (object *force = force_find (name))
    force->destroy ();

  object *force = get_archetype (FORCE_NAME);

  force->slaying = name;

  force->force_set_timer (duration);

  force->flag [FLAG_APPLIED]    = true;

  return insert (force);
}

void
object::play_sound (faceidx sound) const
{
  if (!sound)
    return;

  if (is_on_map ())
    map->play_sound (sound, x, y);
  else if (object *pl = in_player ())
    pl->contr->play_sound (sound);
}

void
object::say_msg (const char *msg) const
{
  if (is_on_map ())
    map->say_msg (msg, x, y);
  else if (object *pl = in_player ())
    pl->contr->play_sound (sound);
}

void
object::make_noise ()
{
  // we do not model noise in the map, so instead put
  // a temporary light into the noise source
  // could use the map instead, but that's less reliable for our
  // goal, which is to make invisibility a bit harder to exploit

  // currently only works sensibly for players
  if (!is_player ())
    return;

  // find old force, or create new one
  object *force = force_find (shstr_noise_force);

  if (force)
    force->speed_left = -1.f; // patch old speed up
  else
    {
      force = archetype::get (shstr_noise_force);

      force->slaying    = shstr_noise_force;
      force->stats.food = 1;
      force->speed_left = -1.f;

      force->set_speed (1.f / 4.f);
      force->flag [FLAG_IS_USED_UP] = true;
      force->flag [FLAG_APPLIED]    = true;

      insert (force);
    }
}