/**************************************************************
 *** This file contains definition of TWeightIndexedArray class
 *** This class is basivally one dimentional array of integer
 *** values indexed by weights (where weight are also integer
 *** values).
 *** This class was used to implement the dynamic version of
 *** the KnapSack problem and keep track of items in the
 *** knapsack.
 *** You will be needing an array of objects of this class.
 *** Array should contain as many elements as many objects
 *** you have to choose from. Let's say you defined:
 *** TWeightIndexedArray taken[N];
 *** Then you can access each element you stored inside the
 *** TWIA as:
 *** taken[i][w]
 *** where
 ***  i - is the number of the element you are interested in
 ***  w - is a weight
 *** Using this array you can store information like 'do I take
 *** element number 4 if my weight is 27'. this information is
 *** to be stored in
 *** taken[4][27]
 **************************************************************/
// ------------------------------------------------------------
//     Associated array.
class TWeightIndexedArray {
   public:
      TWeightIndexedArray() { Init(256); };
      TWeightIndexedArray(int size) { Init(size); };
      ~TWeightIndexedArray() { delete data;  delete index; };
      int& operator[](int weight);
      int max_ind();
      bool is_present(int weight);
      void print();
   private:
      int  N;      // actual size of the array
      int  count;  // number of elements stored in the array
      int *data;   // elements of the array
      int *index;  // array of indexes
      // -----------------------------
      void Init(int size);
};

void TWeightIndexedArray::Init(int size)
{
   if( size > 0 ){
      N = size;
      data = new int[N];
      index = new int[N];
      count = 0;
   }
}

int& TWeightIndexedArray::operator[](int weight)
{
   for(int i=0;i<count;i++)
      if( index[i] == weight ) return data[i];
   index[count] = weight;
   data[count++] = 0;
   return data[count-1];
}

bool TWeightIndexedArray::is_present(int weight)
{
   for(int i=0;i<count;i++)
      if( index[i] == weight ) return true;
   return false;
}

void TWeightIndexedArray::print()
{
   for(int i=0;i<count;i++)
      cout<<"weight: "<<index[i]<<"   item index: "<<data[i]<<endl;
}

int TWeightIndexedArray::max_ind()
{
   if( count > 0 ){
      int max = index[0];
      for(int i=1;i<count;i++)
         if( index[i] > max ) max = index[i];
      return max;
   }
   return -1;
}
// ------------------------------------------------------------