/*
 * Object (and inventory) common code.
 */

#include <curses.h>
#include <stdlib.h>
#include <strings.h>

#include "vars.h"
#include "math.h"
#include "dice.h"
#include "pline.h"
#include "debug.h"
#include "signals.h"
#include "display.h"
#include "structs.h"
#include "disputil.h"
#include "objtypes.h"
#include "stdio-util.h"
#include "obj-armour.h"
#include "obj-weapon.h"

#include "obj.h"

/*
 * The vector of characters used to name objects in inventories.  The
 *  first 26 are used alone; after that, the following 36 are used
 *  followed by one of the full 62.  That is, things go a, b, ..., y,
 *  z, Aa, Ab, Ac, ..., Az, AA, AB, ..., AZ, A0, ..., A9, Ba, Bb, ...,
 *  Bz, BA, ..., BZ, B0, ..., B9, Ca, ..., C9, Da, ..., Z9, 0a, ...,
 *  09, 1a, ..., 19, ..., 9a, ..., 99.  This supports up to
 *  26+(36*62)=2258 slots in an inventory.  Objects after the first
 *  2258 in an inventory are not directly accessible.
 */
static const char icv[62] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

/*
 * Shuffle the name2 and name3 strings for an object class.  This is
 *  used during startup to randomize, eg, the correspondence between
 *  scroll titles and scroll effects.
 */
static void shuffle_name23(int class)
{
 int tlist[OCC__MAX];
 int tn;
 int i;
 int j;

 tn = 0;
 for (i=0;i<OBJ__N;i++)
  { if (objtypes[i].class == class)
     { if (tn > OCC__MAX) abort();
       tlist[tn++] = i;
     }
  }
 for (i=1;i<tn;i++)
  { j = rnd(i+1);
    if (j != i)
     { const char *tmp;
       tmp = objtypes[tlist[i]].name2;
       objtypes[tlist[i]].name2 = objtypes[tlist[j]].name2;
       objtypes[tlist[j]].name2 = tmp;
       tmp = objtypes[tlist[i]].name3;
       objtypes[tlist[i]].name3 = objtypes[tlist[j]].name3;
       objtypes[tlist[j]].name3 = tmp;
     }
  }
}

/*
 * Initialize the object code.  We just clear all the known bits and
 *  randomize the scroll, potion, wand, and ring mappings between
 *  descriptions and effects.
 */
void initobj(void)
{
 int i;

 for (i=0;i<OBJ__N;i++) objtypes[i].flags &= ~OTF_KNOWN;
 shuffle_name23(OC_SCROLL);
 shuffle_name23(OC_POTION);
 shuffle_name23(OC_WAND);
 shuffle_name23(OC_RING);
}

/*
 * Free up an OBJ.
 */
void objfree(OBJ *o)
{
 (*objtypes[o->type].ops->old)(o);
 free(o);
}

/*
 * Free up an INVOBJ, including all the OBJs that make it up.
 */
void invobjfree(INVOBJ *io)
{
 int i;

 for (i=0;i<io->n;i++) objfree(io->v[i]);
 free(io->v);
 free(io);
}

/*
 * Remove an INVOBJ from an INVENT.  If it's not there, or if it's
 *  there and its inventory backpointer is wrong, we panic.
 */
void inv_remove(INVENT *inv, INVOBJ *io)
{
 INVOBJ **l;
 INVOBJ *t;

 l = &inv->inv;
 while ((t = *l))
  { if (t == io)
     { *l = t->link;
       if (t->inv != inv) panic("invobj in wrong inventory");
       t->inv = 0;
       (*objtypes[io->v[0]->type].ops->moved)(io,inv,0);
       return;
     }
    l = &t->link;
  }
 panic("invobj not in inventory");
}

/*
 * Destroy an inventory, including destroying everything in it.
 */
void destroy_inv(INVENT *inv)
{
 INVOBJ *io;

 while (inv->inv)
  { io = inv->inv;
    inv->inv = io->link;
    invobjfree(io);
  }
}

/*
 * Merge objects from one inventory (from) into another (to).  After
 *  this, from will be empty.
 */
void mergeinv(INVENT *from, INVENT *to)
{
 INVOBJ *io;
 int i;

 while (from->inv)
  { io = from->inv;
    from->inv = io->link;
    (*objtypes[io->v[0]->type].ops->moved)(io,from,0);
    for (i=0;i<io->n;i++) add_obj_to_inv(io->v[i],to);
    free(io->v);
    free(io);
  }
}

/*
 * Just like mergeinv(), above, except that it makes callbacks.  See
 *  obj.h's comment for details.
 */
void merge_with_cb(INVENT *from, INVENT *to, void (*cb)(MWC_OP, INVOBJ *, void *), void *cbarg)
{
 INVOBJ *io;
 int i;

 (*cb)(MWC_BEGIN,0,cbarg);
 while (from->inv)
  { io = from->inv;
    from->inv = io->link;
    (*cb)(MWC_PRE,io,cbarg);
    (*objtypes[io->v[0]->type].ops->moved)(io,from,0);
    for (i=0;i<io->n;i++) (*cb)(MWC_POST,add_obj_to_inv(io->v[i],to),cbarg);
    (*cb)(MWC_DONE,0,cbarg);
    free(io->v);
    free(io);
  }
 (*cb)(MWC_END,0,cbarg);
}

/*
 * Move a single INVOBJ (io) from one inventory (oldinv) to another
 *  (newinv).  Returns the new INVOBJ, which never equals io; io is
 *  freed.
 */
INVOBJ *inv_move_1(INVENT *oldinv, INVOBJ *io, INVENT *newinv)
{
 INVOBJ *p;
 int i;

 inv_remove(oldinv,io);
 for (i=0;i<io->n;i++) p = add_obj_to_inv(io->v[i],newinv);
 io->n = 0;
 invobjfree(io);
 return(p);
}

/*
 * Make a new object of a given type.  This creates a singular object;
 *  if a plural object is desired, the number must be set elsewhere.
 */
OBJ *obj_make(int type)
{
 OBJ *o;

 o = malloc(sizeof(OBJ));
 o->type = type;
 o->number = 1;
 return((*objtypes[type].ops->new)(type,o));
}

/*
 * Return true if two objects are collapsible.  If their types are
 *  different, they never are; otherwise, call the type's collapsible
 *  method to see.
 */
static int obj_collapsible(OBJ *o1, OBJ *o2)
{
 if (objtypes[o1->type].ops != objtypes[o2->type].ops) return(0);
 return((*objtypes[o1->type].ops->collapsible)(o1,o2));
}

/*
 * Return true if two objects are identical.  If their types are
 *  different, they never are; otherwise, call the type's identical
 *  method to see.
 */
static int obj_identical(OBJ *o1, OBJ *o2)
{
 if (o1->type != o2->type) return(0);
 return((*objtypes[o1->type].ops->identical)(o1,o2));
}

/*
 * Add an OBJ to an inventory, including creating an INVOBJ for it if
 *  necessary.
 */
INVOBJ *add_obj_to_inv(OBJ *o, INVENT *inv)
{
 INVOBJ *io;
 int i;

 for (io=inv->inv;io;io=io->link)
  { if (obj_collapsible(o,io->v[0]))
     { for (i=0;i<io->n;i++)
	{ if (obj_identical(o,io->v[i]))
	   { io->v[i]->number += o->number;
	     io->dispn += o->number;
	     objfree(o);
	     return(io);
	   }
	}
       io->n ++;
       io->v = realloc(io->v,io->n*sizeof(OBJ *));
       io->v[io->n-1] = o;
       o->io = io;
       io->dispn += o->number;
       return(io);
     }
  }
 io = malloc(sizeof(INVOBJ));
 io->inv = inv;
 io->xwi = (o->type == OBJ_GOLD) ? 0 : find_xwi(inv);
 io->dispn = o->number;
 io->n = 1;
 io->v = malloc(sizeof(OBJ *));
 io->v[0] = o;
 o->io = io;
 io->link = inv->inv;
 inv->inv = io;
 (*objtypes[o->type].ops->moved)(io,0,inv);
 return(io);
}

/*
 * Return true if an object (o) is present in an inventory (inv), false
 *  if not.
 */
int inv_present(INVENT *inv, OBJ *o)
{
 INVOBJ *io;
 int i;

 for (io=inv->inv;io;io=io->link) for (i=io->n-1;i>=0;i--) if (io->v[i] == o)
  { if (o->io->inv == inv) return(1);
    panic("inv has obj but backpointer disagrees");
  }
 if (o->io->inv == inv) panic("inv hasn't obj but backpointer disagrees");
 return(0);
}

/*
 * An inventory interest function that selects everything.
 */
int invtest_all(INVOBJ *inv __attribute__((__unused__)))
{
 return(1);
}

/*
 * Format just the inventory letter for an xwi, writing the result to
 *  f.  Objects after the first 2258 do not get label characters; they
 *  are not directly accessible.
 */
void format_inv_letter(int xwi, FILE *f)
{
 if (xwi == 0)
  { fprintf(f," $) ");
  }
 else if (xwi < 1+26)
  { fprintf(f," %c) ",icv[xwi-1]);
  }
 else if (xwi < 1+26+(36*62))
  { fprintf(f,"%c%c) ",icv[26+((xwi-27)/62)],icv[(xwi-27)%62]);
  }
}

/*
 * Format an INVOBJ (io) for display in an inventory list, writing the
 *  result to f.
 */
void format_inv_line(INVOBJ *io, FILE *f)
{
 format_inv_letter(io->xwi,f);
 (*objtypes[io->v[0]->type].ops->format)(f,io);
}

/*
 * Check whether c is a one-character inventory label.  If so, set *vp
 *  to the corresponding number and return 1; if not, return 0 without
 *  storing through vp.
 */
static int inv_c_is_1(char c, int *vp)
{
 char *xp;

 if (c == '$')
  { *vp = 0;
    return(1);
  }
 xp = memchr(&icv[0],c,26);
 if (xp)
  { *vp = 1 + (xp - &icv[0]);
    return(1);
  }
 return(0);
}

/*
 * Check whether c is the first character of a two-character inventory
 *  label.  If so, set *vp to the corresponding base number needed so
 *  that inv_c_is_2_2 will produce the correct index and return 1; if
 *  not, return 0 without storing through vp.
 */
static int inv_c_is_2_1(char c, int *vp)
{
 char *xp;

 xp = memchr(&icv[26],c,36);
 if (xp)
  { *vp = (xp - &icv[26]) * 62;
    return(1);
  }
 return(0);
}

/*
 * Check whether c is the second character of a two-character inventory
 *  label.  If so, *vp is assumed to be set as if by inv_c_is_2_1 and
 *  it is updated to the actual inventory index, and 1 is returned;
 *  otherwise, 0 is returned.
 */
static int inv_c_is_2_2(char c, int *vp)
{
 char *xp;

 xp = memchr(&icv[0],c,62);
 if (xp)
  { *vp += 1 + (xp - &icv[0]) + 26;
    return(1);
  }
 return(0);
}

/*
 * Find an INVOBJ in an inventory by index.
 */
static INVOBJ *x_in_inv(INVENT *inv, int x, int (*interest)(INVOBJ *))
{
 INVOBJ *io;

 for (io=inv->inv;io;io=io->link) if ((io->xwi == x) && (*interest)(io)) return(io);
 return(0);
}

/*
 * SIKA = Show Inventory Keystroke Action.  These are the return values
 *  from show_inventory_'s keystroke function:
 *
 *	SI_K_IGNORE:
 *		Ignore this keystroke entirely.
 *	SI_K_CONTINUE:
 *		Save this keystroke and accept another.
 *	SI_K_ABORT:
 *		Quit now.  (This may be success or may be an error.)
 */
typedef enum {
	  SI_K_IGNORE = 1,
	  SI_K_CONTINUE,
	  SI_K_ABORT,
	  } SIKA;

/*
 * The internal show-inventory function.  This just uses display_list
 *  to page through the inventory, possibly accepting additional
 *  characters, depending on keystroke.  inv is the inventory, prompt
 *  is the a prompt string, interest is a filter on the inventory to
 *  decide which items to show, and keystroke is used to process user
 *  input.  ifnone is a string which is pline()d if the inventory
 *  contains nothing matching the test function; if it is nil, this is
 *  a no-op in that case.
 */
static void show_inventory_(INVENT *inv, const char *prompt, int (*interest)(INVOBJ *), SIKA (*keystroke)(int), const char *ifnone)
{
 INVOBJ *io;

 DLLS line(FILE *f)
  { while (io && !(*interest)(io)) io = io->link;
    if (! io) return(DL_L_DONE);
    format_inv_line(io,f);
    io = io->link;
    return(DL_L_MORE);
  }

 DLKS key(int ks)
  { switch ((*keystroke)(ks))
     { case SI_K_IGNORE:
	  return(DL_K_IGNORE);
	  break;
       case SI_K_CONTINUE:
	  return(DL_K_CONTINUE);
	  break;
       case SI_K_ABORT:
	  return(DL_K_ABORT);
	  break;
       default:
	  abort();
	  break;
     }
  }

 if (! test_inventory(inv,interest))
  { if (ifnone) pline("%s",ifnone);
    return;
  }
 io = inv->inv;
 display_list(&line,prompt,&key);
 showdisp();
}

/*
 * A show-inventory keystroke action for just looking at inventory, not
 *  selecting an item from it.
 */
static SIKA si_justmore(int ch)
{
 switch (ch)
  { case ' ': case '\r': case '\n': return(SI_K_CONTINUE); break;
    case '\e':                      return(SI_K_ABORT);    break;
  }
 return(SI_K_IGNORE);
}

/*
 * The exported show-inventory function.
 */
void show_inventory(INVENT *inv, const char *prompt, int (*interest)(INVOBJ *), const char *ifnone)
{
 show_inventory_(inv,prompt,interest,&si_justmore,ifnone);
}

/*
 * See whether an inventory has anything in it satisfying the filter
 *  predicate (return true) or not (return false).
 */
int test_inventory(INVENT *inv, int (*interest)(INVOBJ *))
{
 INVOBJ *io;

 for (io=inv->inv;io;io=io->link) if ((*interest)(io)) return(1);
 return(0);
}

/*
 * Exported interface: pick an object from a (filtered) inventory.
 *  Returns the INVOBJ, or nil if the operation is aborted.
 */
INVOBJ *pick_inventory(INVENT *inv, const char *prompt, int (*interest)(INVOBJ *), int (*key)(char))
{
 INVOBJ *io;
 int c;
 static char *ptmp = 0;
 static int pta = 0;
 static char *epp;
 int ks;
 int c2;
 JMP j;
 int filter;
 char filter_known;
 char filter_unknown;
 char filter_types[64];
 int reinv;

 void reprompt(void)
  { if (filter)
     { char s2[2];
       s2[0] = c2;
       s2[1] = '\0';
       sprintf(epp," %s%s%s %s",filter_unknown?"u":"",filter_known?"k":"",&filter_types[0],&s2[0]);
     }
    else
     { epp[0] = c2;
       epp[1] = '\0';
     }
  }

 void setpt(int c)
  { c2 = c;
    reprompt();
  }

 void clrpt(void)
  { c2 = 0;
    reprompt();
  }

 int intfilter(INVOBJ *io)
  { if ( filter &&
	 !( (filter_unknown && invtest_unidentified(io)) ||
	    (filter_known && !invtest_unidentified(io)) ||
	    index(&filter_types[0],objtypes[io->v[0]->type].sym) ) ) return(0);
    return((*interest)(io));
  }

 int intwrap(INVOBJ *io)
  { if (c2 && ((io->xwi <= ks+26) || (io->xwi > ks+26+62))) return(0);
    return(intfilter(io));
  }

 int set_type_filter(void)
  { char prompt[64];
    char types[64];
    char lastc;
    char *cp;
    char *cp0;
    int i;
    int j;
    CHOK pcharok(char typed)
     { return(index(&types[0],typed)?CHOK_OK:CHOK_BAD);
     }
    cp = &types[0];
    lastc = '\0';
    for (io=inv->inv;io;io=io->link)
     { c = objtypes[io->v[0]->type].sym;
       if (c != lastc)
	{ if ((cp == cp0) || !memchr(&types[0],c,cp-&types[0])) *cp++ = c;
	  lastc = c;
	}
     }
    *cp++ = 'u';
    *cp++ = 'k';
    *cp = '\0';
    sprintf(&prompt[0],"What types [%s]?  ",&types[0]);
    if (prompt_and_read(&prompt[0],&filter_types[0],sizeof(filter_types),0,&pcharok) != PR_OK) return(0);
    if (! filter_types[0])
     { filter = 0;
     }
    else
     { j = 0;
       filter_known = 0;
       filter_unknown = 0;
       for (i=0;filter_types[i];i++)
	{ if (filter_types[i] == 'u')
	   { filter_unknown = 1;
	   }
	  else if (filter_types[i] == 'k')
	   { filter_known = 1;
	   }
	  else
	   { if (j != i) filter_types[j] = filter_types[i];
	     j ++;
	   }
	}
       filter_types[j] = '\0';
       clrpt();
       filter = 1;
     }
    reprompt();
    return(1);
  }

 SIKA key2(int c)
  { switch (c)
     { case ' ': case '\r': case '\n':
	  return(SI_K_CONTINUE);
	  break;
       case '\e':
	  return(SI_K_ABORT);
	  break;
       case 0x14: // ^T
	  if (set_type_filter())
	   { reprompt();
	     reinv = 1;
	     return(SI_K_ABORT);
	   }
	  break;
     }
    if (c2)
     { switch (c)
	{ case '\b': case '\177':
	     clrpt();
	     reinv = 1;
	     return(SI_K_ABORT);
	     break;
	}
       if (inv_c_is_2_2(c,&ks))
	{ io = x_in_inv(inv,ks,&intfilter);
	  if (io) return(SI_K_ABORT);
	  beep();
	}
     }
    else
     { if (inv_c_is_1(c,&ks))
	{ io = x_in_inv(inv,ks,&intfilter);
	  if (io) return(SI_K_ABORT);
	}
       else if (inv_c_is_2_1(c,&ks))
	{ setpt(c);
	  reinv = 1;
	  return(SI_K_ABORT);
	}
       else if (key && (*key)(c))
	{ return(SI_K_ABORT);
	}
       else
	{ beep();
	}
     }
    return(SI_K_IGNORE);
  }

 c = strlen(prompt);
 if (c+64 > pta)
  { free(ptmp);
    pta = c + 64;
    ptmp = malloc(pta);
  }
 strcpy(ptmp,prompt);
 epp = ptmp + c;
 *epp++ = ' ';
 io = 0;
 c2 = 0;
 filter = 0;
 reinv = 0;
 reprompt();
 if (setjmp(j.b))
  { pop_sigint_throw();
    move(LINES-1,0);
    clrtoeol();
    return(0);
  }
 while <"done"> (1)
  { move(LINES-1,0);
    addstr(ptmp);
    clrtoeol();
    if (reinv)
     { c = '?';
       reinv = 0;
     }
    else
     { push_sigint_throw(&j);
       c = tget();
       pop_sigint_throw();
     }
    switch (c)
     { case '?':
	  show_inventory_(inv,ptmp,&intwrap,&key2,0);
	  if (io) break <"done">;
	  showdisp();
	  continue;
	  break;
       case '\e':
	  io = 0;
	  break <"done">;
	  break;
       case '\b': case '\177':
	  clrpt();
	  break;
       case 0x14: // ^T
	  if (set_type_filter()) reprompt();
	  break;
       default:
	  if (c2)
	   { switch (c)
	      { case '\b': case '\177':
		   clrpt();
		   break;
		case '\e':
		   io = 0;
		   break <"done">;
		default:
		   if (inv_c_is_2_2(c,&ks))
		    { io = x_in_inv(inv,ks,interest);
		      if (io) break <"done">;
		      beep();
		    }
		   else
		    { beep();
		    }
		   break;
	      }
	   }
	  else if (inv_c_is_1(c,&ks))
	   { io = x_in_inv(inv,ks,interest);
	     if (io) break <"done">;
	     beep();
	   }
	  else if (inv_c_is_2_1(c,&ks))
	   { setpt(c);
	   }
	  else if (key && (*key)(c))
	   { io = 0;
	     break <"done">;
	   }
	  else
	   { beep();
	   }
	  break;
     }
  }
 move(LINES-1,0);
 clrtoeol();
 return(io);
}

/*
 * Find and return the lowest xwi value not currently in use by the
 *  inventory.  This is used for things like adding new objects to the
 *  inventory.
 */
int find_xwi(INVENT *inv)
{
 static char *map = 0;
 static int ma = 0;
 int ml;
 int i;
 INVOBJ *io;

 ml = 0;
 for (io=inv->inv;io;io=io->link)
  { if (io->xwi >= ma) map = realloc(map,ma=io->xwi+1);
    if (io->xwi >= ml)
     { if (io->xwi > ml) bzero(map+ml,io->xwi-ml);
       ml = io->xwi + 1;
     }
    map[io->xwi] = 1;
  }
 for (i=1;i<ml;i++) if (!map[i]) break;
 return(i);
}

/*
 * Split an inventory object, internal version that actually does the
 *  work.  For example, if you have 100 arrows in an inventory, this
 *  could be used to split off 10 of them into a separate INVOBJ (for
 *  example, to be dropped).  The new INVOBJ is returned.
 *
 * old is the INVOBJ to be split.  newn is the split number; after the
 *  split operation, new will have newn objects and the old INVOBJ will
 *  have the rest.  newxwi is the xwi at which the new INVOBJ is to
 *  appear (it's always put in the same inventory as old)..
 *
 * If newn is less than one or >= the number of objects in old (ie, of
 *  one of the putative split objects would have a nonpositive number
 *  of objects in it), nothing is done and nil is returned.
 *
 * If old is an INVOBJ formed by coalescing multiple OBJs, it is as if
 *  old were made up of a lot of individual objects, with the relevant
 *  number of them chosen randomly to go into the new INVOBJ.  (For
 *  example, if it is made up of 60 +0 arrows and 40 +1 arrows,
 *  splitting 10 of them will give you a random sampling, which could
 *  be anywhere between the (unlikely) extremes of 10 +0 arrows and 10
 *  +1 arrows, with the mean being 6 +0 and 4 +1 arrows.)
 *
 * This function does not preserve the invariant that backpointers from
 *  the OBJs to the INVOBJs are correct.  This is not the exported
 *  interface; the exported interface maintains that invariant.
 *
 * It is specifically not promised whether the old OBJ structs are
 *  reused, nor, if they are, which of them stay with the old INVOBJ
 *  and which go with the new.
 */
static INVOBJ *inventory_split_n_(INVOBJ *old, int newn, int newxwi)
{
 INVOBJ *new;
 OBJ *o;
 int i;
 int j;
 int n;
 int nleft;
 int tleft;

 if ((newn < 1) || (newn >= old->dispn)) return(0);
 nleft = newn;
 tleft = old->dispn;
 new = malloc(sizeof(INVOBJ));
 new->inv = old->inv;
 new->xwi = newxwi;
 new->dispn = newn;
 new->link = old->link;
 old->link = new;
 new->n = old->n;
 old->dispn -= newn;
 if (old->n == 1)
  { new->v = malloc(sizeof(OBJ *));
    new->v[0] = (*objtypes[old->v[0]->type].ops->split)(old->v[0],new->dispn);
    return(new);
  }
 new->v = malloc(old->n*sizeof(OBJ *));
 new->n = 0;
 // We have tleft objects and need nleft of them.
 // All the OBJs are still in the old INVOBJ.
 for (i=old->n-1;i>=0;i--)
  { o = old->v[i];
    n = 0;
    // I'm not aware of any closed-form way to get this right.
    // (Where "closed-form" means, approximately, "doing less than
    //  O(original old->dispn) work overall".)
    for (j=o->number-1;j>=0;j--)
     { if ((nleft > 0) && ((tleft <= nleft) || (rnd(tleft) < nleft)))
	{ n ++;
	  nleft --;
	}
       tleft --;
     }
    if (n > 0)
     { if (n == o->number)
	{ if (i != old->n-1) old->v[i] = old->v[old->n-1];
	  old->n --;
	}
       else
	{ o = (*objtypes[o->type].ops->split)(o,n);
	}
       new->v[new->n++] = o;
     }
  }
 if (tleft || nleft) panic("inconsistency in inventory_split_n_");
 return(new);
}

/*
 * Split an inventory object, exported version.  If newn is negative,
 *  its absolute value is how many will remain in the old object, with
 *  the new object taking the rest; if newn is positive, that many go to
 *  the new object, with the rest remaining in the old.
 */
INVOBJ *inventory_split_n(INVOBJ *old, int newn, int newxwi)
{
 INVOBJ *new;
 int i;

 if (newn < 0)
  { INVOBJ t;
    new = inventory_split_n_(old,-newn,newxwi);
    if (! new) return(0);
    t = *new;
    new->dispn = old->dispn;
    new->n = old->n;
    new->v = old->v;
    old->dispn = t.dispn;
    old->n = t.n;
    old->v = t.v;
  }
 else
  { new = inventory_split_n_(old,newn,newxwi);
  }
 for (i=old->n-1;i>=0;i--) old->v[i]->io = old;
 for (i=new->n-1;i>=0;i--) new->v[i]->io = new;
  { int n;
    n = 0;
    for (i=old->n-1;i>=0;i--) n += old->v[i]->number;
    if (n != old->dispn) panic("split inconsistency");
    n = 0;
    for (i=new->n-1;i>=0;i--) n += new->v[i]->number;
    if (n != new->dispn) panic("split inconsistency");
  }
 return(new);
}

/*
 * Sort a list of INVOBJs based on a comparison function, returning the
 *  new (sorted) list.
 *
 * (*cmp)(A,B) must return negative, zero, or positive according as A
 *  must, may or may not, or must not come before B in the sorted list.
 */
INVOBJ *sort_inv(INVOBJ *inv, int (*cmp)(INVOBJ *, INVOBJ *))
{
 INVOBJ *l1;
 INVOBJ **t1;
 INVOBJ *l2;
 INVOBJ **t2;
 INVOBJ **t;
 INVOBJ *o;

 if (! inv->link) return(inv);
 t1 = &l1;
 t2 = &l2;
 while (inv)
  { *t1 = inv;
    t1 = &inv->link;
    inv = inv->link;
    if (! inv) break;
    *t2 = inv;
    t2 = &inv->link;
    inv = inv->link;
  }
 *t1 = 0;
 *t2 = 0;
 l1 = sort_inv(l1,cmp);
 l2 = sort_inv(l2,cmp);
 t = &inv;
 while (1)
  { if (l1 && (!l2 || ((*cmp)(l1,l2) < 0)))
     { o = l1;
       l1 = l1->link;
     }
    else if (l2)
     { o = l2;
       l2 = l2->link;
     }
    else
     { break;
     }
    *t = o;
    t = &o->link;
  }
 *t = 0;
 return(inv);
}

/*
 * Initialize an INVENT to be of a given type.  The type must be
 *  followed by a backpointer: if t is IT_MON, the backpointer must be
 *  a MONST *; if IT_LOC, a LOC *.
 */
void inv_init(INVENT *i, INVTYPE t, void *bp)
{
 i->inv = 0;
 i->type = t;
 switch (t)
  { case IT_MON:
       i->u.m = bp;
       break;
    case IT_LOC:
       i->u.l = bp;
       break;
    default:
       panic("bad type %d to inv_init",t);
       break;
  }
}

/*
 * Split a plural OBJ.  old is the OBJ to split; n is the number to be
 *  split off.  Returns a new OBJ holding n of the old OBJ's objects;
 *  the old OBJ holds the remainder.  It is the caller's responsibility
 *  to ensure that n is strictly between 0 and the object's number.
 */
OBJ *std_split(OBJ *old, int n)
{
 OBJ *o;

 old->number -= n;
 o = obj_make(old->type);
 o->number = n;
 return(o);
}

/*
 * Scan an inventory, looking for an object satisfying a predicate.
 *  Returns the first one found, or nil if none of them match.
 */
INVOBJ *inv_scan(INVENT *inv, int (*interest)(INVOBJ *))
{
 INVOBJ *io;

 for (io=inv->inv;io;io=io->link) if ((*interest)(io)) return(io);
 return(0);
}

/*
 * Scan an inventory, looking for objects satisfying a predicate.
 *  Returns how many were found.
 */
int inv_count(INVENT *inv, int (*interest)(INVOBJ *))
{
 INVOBJ *io;
 int n;

 n = 0;
 for (io=inv->inv;io;io=io->link) if ((*interest)(io)) n ++;
 return(n);
}

/*
 * Inventory predicate that looks for unidentified objects.
 */
int invtest_unidentified(INVOBJ *io)
{
 return(!(*objtypes[io->v[0]->type].ops->identified)(io));
}

/*
 * Show a one-line inventory listing of a single INVOBJ.
 */
void pline_invobj(INVOBJ *io)
{
 char *s;
 FILE *f;

 f = fopenmalloc(&s,0);
 format_inv_line(io,f);
 fclose(f);
 pline("%s",s);
 free(s);
}

/*
 * Identify an INVOBJ.  If noisy is true, report the result.
 */
void identify_it(INVOBJ *io, int noisy)
{
 io = (*objtypes[io->v[0]->type].ops->identify)(io);
 if (noisy) pline_invobj(io);
}

/*
 * Remove one OBJ from an INVOBJ, the one at index inx.  It is the
 *  caller's responsibility to ensure that inx is in range for the
 *  INVOBJ.
 */
OBJ *remove_obj_from_invobj(int inx, INVOBJ *io)
{
 OBJ *o;

 o = io->v[inx];
 io->n --;
 if (inx != io->n) io->v[inx] = io->v[io->n];
 io->dispn -= o->number;
 o->io = 0;
 return(o);
}

/*
 * A no-op object-moved method.
 */
void noop_moved(INVOBJ *io __attribute__((__unused__)), INVENT *from __attribute__((__unused__)), INVENT *to __attribute__((__unused__)))
{
}

/*
 * "Should never be called" fmt_cond and fmt_spec methods.  These are
 *  suitable for object types which have completely custom format
 *  functions or which have format strings that don't use the per-type
 *  custom escapes.
 */

int panic_fmt_cond(char ch __attribute__((__unused__)), INVOBJ *io __attribute__((__unused__)))
{
 panic("impossible fmt_cond");
}

void panic_fmt_spec(FILE *f __attribute__((__unused__)), char ch __attribute__((__unused__)), INVOBJ *io __attribute__((__unused__)))
{
 panic("impossible fmt_spec");
}

/*
 * identified method for object types which are always fully identified.
 */
int always_identified(INVOBJ *io __attribute__((__unused__)))
{
 return(1);
}

/*
 * identify method for object types which are always fully identified.
 */
INVOBJ *already_identify(INVOBJ *io)
{
 return(io);
}

/*
 * A no-op object-type new method, for object types which have no
 *  private data.
 */
OBJ *noop_new(int type __attribute__((__unused__)), OBJ *o)
{
 o->private = 0;
 return(o);
}

/*
 * A no-op object-type old method, for object types which have no
 *  private data.
 */
void noop_old(OBJ *o __attribute__((__unused__)))
{
}

/*
 * Inventory predicate that looks for ungateable objects.
 */
int invtest_ungateable(INVOBJ *io)
{
 switch (objtypes[io->v[0]->type].class)
  { case OC_SCARAB:
    case OC_CROWN:
       return(1);
       break;
  }
 return(0);
}

/*
 * Map a callback over an inventory.
 */
int inv_map(INVENT *inv, int (*cb)(INVOBJ *))
{
 int rv;
 int cbrv;
 INVOBJ *io;

 rv = 0;
 for (io=inv->inv;io;io=io->link)
  { cbrv = (*cb)(io);
    if (cbrv < 0) return(cbrv);
    rv += cbrv;
  }
 return(rv);
}

/*
 * Return true if an object type is cursable, that is, if an object of
 *  this type could possibly be cursed.
 */
int obj_cursable(int type)
{
 return(objtypes[type].ops->cursable);
}

/*
 * Set an object's is-cursed status.  No-op for non-cursable objects.
 */
void obj_set_cursed(OBJ *o, int cursed)
{
 (*objtypes[o->type].ops->setcursed)(o,cursed);
}