Item Piles

Joe user would expect an item pile to have the following properties:

• Turning an item into a pile with a single item
• Creating an empty pile
• Removing all the objects from a pile
• Adding a specific amount of a certain object to a pile
• Removing a specific amount of an object (if there are not enough, then mention how many more objects would have been necessary).
• Counting the objects of a certain type.
• Combining two piles together.

It is similar to associating to each item an integer (the amount of said item present in the pile). As far as implementation goes, the user will need to access (read and/or modify) at a moment's notice the amount of a particular item present in the pile, which rules out all list containers and their O(n) random access.

A vector where the indices are the item types would be the fastest method, allowing O(1) access, but this approach has two problems : first, item piles can contain as little as a single object, so allocating an array just for one is wasted memory (especially when the vector's length is equal to the number of different items in the game). Second, an item is not just a number: it also has other properties than its type. Having two items with the same type but with different properties in a single pile would lead to big problems (forcing us into a vector of item containers later on). The only way to avoid this is basing the access not on the type of object, but on the comparison functions for the object.

The next best random access time is O(log n), and can be implemented with either sorted vectors or maps (or sets) without any serious memory hits. Going the vector (or set) way would be impractical, because we would have to store item-amount pairs in the container, making the implementation more complex to code. A map, however, works perfectly.

This leads us to the class definition for item piles:

class cItemPack { 
         
  std::map< cItem, unsigned long > contents;

public:

   cItemPack( cItem & , unsigned long );
  void clear( );
  unsigned long add( const cItem & , const unsigned long );
  unsigned long remove( const cItem & , const unsigned long );
  unsigned long getAmount( const cItem & ) const;
  const std::map< cItem, unsigned long > & getItems( ) const;
  cItemPack & operator= ( const cItemPack & );
  cItemPack & operator+= ( const cItemPack & );
  cItemPack operator+ ( const cItemPack & ) const;

};

I have chosen to allow only positive amounts of objects. While this could have been useful to represent a NPC merchant's "plans" about what to buy or sell, it only adds unnecessary complication, since in almost all cases an item pile represents a physical entity where negative amounts are impossible. Next up is the implementation:

cItemPack::cItemPack( cItem & i, unsigned long a ) { contents[i] = a; }
void cItemPack::clear( void ) { contents.clear( ); } 
cItemPack & cItemPack::operator=( const cItemPack & o ) {

  contents = o.contents;
  return( *this );

}

The two constructors, the clear function and the assignment operator are pretty straightforward: there is nothing to specifically initialize. The "from item" constructor showcases the ease of use associated with the map implementation: items can actually be used as indices to access elements of the map. The following function adds a definite amount of a certain object to the pile, and returns the amount of objects after the addition:

unsigned long cItemPack::add( const cItem & i,
                              const unsigned long a )
{

  return( contents[i] += a );

}

A function that returns the amount of a certain type of object could work as well, but it would be convenient if it could be used on a const object. The problem with this is that the [] operator on a map is not a const function, so the code needs to work around this by using a const iterator, setting it to a possible amount of that item in the map, and if the item is not present, return 0.

unsigned long cItemPack::getAmount( const cItem & i ) const {

  std::map< cItem,unsigned long >::const_iterator j;
  j = contents.find( i );
  if( j == contents.end( ) ) { return( 0 ); }
  else { return( j->second ); }

}

However, a little bit more care needs to be taken of the removal function, because we have to check if there are enough elements inside the pile to be removed (you would not want the player to unequip 200 helmets and end up with 199 bonus headgear). The value returned by the function will be the amount of items that could not be removed (because there were some missing):

unsigned long cItemPack::remove( const cItem & i,
                                 const unsigned long a )
{

  unsigned long t = contents[i];
  if( a > t ) { contents[i] = 0; return( a-t ); }
  else { contents[i] = t-a; return( 0 ); }

}

Also, there are the functions for combining two piles together. The + operator uses the += operator (because it is easier to add objects from one pile to another pile, than adding two piles together into a new one).

cItemPack & cItemPack::operator+=( const cItemPack & o ) {

  std::map< cItem,unsigned long >::const_iterator i;
  for( i = o.contents.begin( ); i != o.contents.end( ); ++i ) {

    add( i->first, i->second );

  }
  return( *this );

}

cItemPack cItemPack::operator+( const cItemPack & o ) const {

  return( cItemPack(*this) += o );

}

And finally, in order not to restrict ourselves to these functions as far as reading through the pile goes, I have added a final function that returns a const instance of the map, which can then be used to access directly the data about the various objects (namely through iterators).

const std::map< cItem,unsigned long > &
cItemPack::getItems( void ) { return( contents ); }

The Item Database