//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MJF 05/22/89 -- Initial design.
// Updated: JCB 06/26/89 -- Implementation.
// Updated: MBN 08/19/89 -- Changed template usage to reflect new syntax
// Updated: MBN 08/24/89 -- Added conditional exception handling and base class
// Updated: LGO 10/02/89 -- Removed destructor - Vector does the work
// Updated: MBN 10/07/89 -- Removed put(Pair<Ktype,Vtype>) method and added
//                          missing set_key_compare/set_value_compare methods
// Updated: MBN 10/11/89 -- Changed "current_position" to "curpos" 
// Updated: LGO 10/16/89 -- Re-wrote operator== to be const
// Updated: MBN 10/19/89 -- Added optional argument to set_compare methods
// Updated: MBN 11/01/89 -- Added constructor with user-provided storage param
// Updated: LGO 11/09/89 -- Inherit publicly from Vector to workaround bugs
//                          in Glockenspiel C++ 1.2 for OS/2
// Updated: MBN 01/31/89 -- Added current_position() member function
// Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The Association<Ktype,Vtype> class is privatly derived from the Vector<Type>
// class and  is used  to implement a  collection of  pairs  that  is privately
// derived from the Vector class.  The first of the pair is called the  key and
// the  second  of the pair is called  the value.  The Association<Ktype,Vtype>
// class implements a  single dimensional vector  parameterized over two types.
// The first type specifies the type of the key, and  the second type specifies
// the  type  of  the  value.  The Association<Ktype,Vtype>  class inherits the
// dynamic  growth  capability of  the  Vector class.    The growth size can be
// determined by the value  of a  static  variable for the class as  a whole or
// from  a growth ratio for each  instance  of the  class.   In addition, fixed
// length vectors are also supported  by  setting the  value  of the allocation
// size variable to zero.
//
// Since  Association is  a specialization of   the Vector class, there are  no
// extra data slots needed in  the private section.   The protected section has
// two static data  slots for  the class  as a whole  that contain pointers  to
// comparison functions for  the key   and the  value types, repectively.   The
// default  compare function is operator== for  the appropriate type. There are
// four constructors for the Association class.  The first constructor takes no
// arguments  and creates an  empty Association object.  The second constructor
// takes a single argument specifying the initial size of the Association.  The
// third  constructor takes two  arguments,  the first a  pointer to a block of
// user-provided  storage and the  second providing indicating  the  number  of
// elements it  can  hold.  The  fourth constructor  is  similar to  the third,
// except that   it  takes a variable number   of arguments  to  allow  for the
// initialization   of  any  number of key/value  pairs.    Finally,  the fifth
// constructor  takes a single  argument  consisting  of    a  reference to   a
// Association and duplicates its size and element values.
//
// Due to  the  private  inheritance  of  the  Vector  class,  the only methods
// available for the Association class  are those that are  explicitly defined.
// Methods are available to set the compare functions  for the key and value, a
// resize method, and get, get key,  and remove methods  used  to add, inspect,
// and remove pairs.  In addition, the Association<Ktype,Vtype> class maintains
// the notion of a current position and  provides reset, next,  prev, find, and
// value methods for working with the  pair at  the current position.  Finally,
// the assignment, equality and inequality, and output operators are overloaded
// for the Association class.

#ifndef ASSOCIATIONH				// If we have not defined class
#define ASSOCIATIONH				// indicate that it is done now

#ifndef VECTORH					// If have not defined Vector
#include <cool/Vector.h>				// Include header file
#endif

#ifndef PAIRH					// If we have not defined Pair
#include <cool/Pair.h>				// Include header file
#endif

template <class Ktype, class Vtype> Association {
  typedef Boolean (*Association<Ktype,Vtype>_Key_Compare)
    (const Ktype&, const Ktype&);
  typedef Boolean (*Association<Ktype,Vtype>_Value_Compare)
    (const Vtype&, const Vtype&);
  DECLARE Pair<Ktype,Vtype>;			// Declare Pair object type
  DECLARE Vector<Pair<Ktype,Vtype>>;		// Declare Vector of Pairs
}

#ifndef ASSOC_STATE
#define ASSOC_STATE
typedef long Association_state;			// Current position state
#endif

template <class Ktype, class Vtype>
class Association<Ktype, Vtype> : public Vector<Pair<Ktype,Vtype>> {
protected:
  static Association<Ktype,Vtype>_Key_Compare compare_keys_s;
  static Association<Ktype,Vtype>_Value_Compare compare_values_s;

  friend Boolean Association<Ktype,Vtype>_keys_eql(const Ktype&, const Ktype&);
  friend Boolean Association<Ktype,Vtype>_values_eql(const Vtype&,const Vtype&);

public:
  Association<Ktype,Vtype>();			// Simple constructor
  Association<Ktype,Vtype>(unsigned long);	// Constructor w/ element count
  Association<Ktype,Vtype>(void*, unsigned long); // Assoc with static storage
  Association<Ktype,Vtype>(const Association<Ktype,Vtype>&); // reference const
  ~Association<Ktype,Vtype>();			// Destructor

  inline void resize(long);			// Resize for at least count
  inline long length();				// Return number of elements
  inline long capacity();			// Max. number of elements
  inline long set_length(long);			// Set number of elements
  inline void set_growth_ratio(float);		// Set growth percentage
  inline void set_alloc_size(int);		// Set alloc size

  inline void set_key_compare (Association<Ktype,Vtype>_Key_Compare = NULL);
  inline void set_value_compare (Association<Ktype,Vtype>_Value_Compare = NULL);

  inline void reset();				// Invalidate current position
  inline void clear();				// Clear objects from assoc
  inline Boolean next();			// Advance current position
  inline Boolean prev();			// Backup current position
  inline Vtype& value();			// Value at current position
  inline const Ktype& key() CONST;		// Key at current position
  inline Association_state& current_position (); // Set/Get current position
  Boolean find(const Ktype&);			// Find/set current position
  Boolean get(const Ktype&, Vtype&);		// Get associated value for key
  Boolean get_key(const Vtype&, Ktype&) CONST;	// Get associated key for value

  Boolean put(const Ktype&, const Vtype&);	// Add/update key/value pair
  Boolean remove(const Ktype&);			// Removes pair with key
  Vtype& remove();				// Removes pair at cur pos

  Association<Ktype,Vtype>& operator=(const Association<Ktype,Vtype>&);

  Boolean operator==(const Association<Ktype,Vtype>&) CONST;
  inline Boolean operator!=(const Association<Ktype,Vtype>&) CONST;
  friend ostream& operator<< (ostream&,CONST Association<Ktype,Vtype>&);
  friend ostream& operator<< (ostream&,CONST Association<Ktype,Vtype>*);
};

template <class Ktype, class Vtype> Association {
  IMPLEMENT Pair<Ktype,Vtype>;
  IMPLEMENT Vector<Pair<Ktype,Vtype>>;
}


// void reset () -- Set current position to INVALID.
// Input:           None
// Output:          None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::reset() {
  Vector<Pair<Ktype,Vtype>>::reset();
}


// void clear () -- Clear all objects from association
// Input:           None
// Output:          None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::clear() {
  Vector<Pair<Ktype,Vtype>>::clear();
}


// Boolean next () -- Increment current position. If INVALID, set to first.
// Input:             None
// Output:            TRUE/FALSE

template <class Ktype, class Vtype>
inline Boolean Association<Ktype,Vtype>::next() {
  return Vector<Pair<Ktype,Vtype>>::next();
}


// Boolean prev () -- Decrement current position. If INVALID, set to last.
// Input:             None
// Output:            TRUE/FALSE

template <class Ktype, class Vtype>
inline Boolean Association<Ktype,Vtype>::prev() {
  return Vector<Pair<Ktype,Vtype>>::prev();
}


// void resize () -- Adjust the memory size of object to accomodate some size
// Input:            Interger number of elements to hold
// Output:           None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::resize (long n) {
  Vector<Pair<Ktype,Vtype>>::resize(n);
}


// long length () -- Return the number of elements in object.
// Input:            None
// Output:           Integer representing number of elements

template <class Ktype, class Vtype>
inline long Association<Ktype,Vtype>::length() {
  return Vector<Pair<Ktype,Vtype>>::length();
}


// long capacity () -- Return maximum number of elements object can hold.
// Input:              None
// Output:             Integer value of maximum number of elements

template <class Ktype, class Vtype>
inline long Association<Ktype,Vtype>::capacity () {
  return this->Vector::capacity();
}


// long set_length () -- Set the number of elements in a object.
// Input:                Length value
// Output:               Integer representing number of elements

template <class Ktype, class Vtype>
inline long Association<Ktype,Vtype>::set_length(long n) {
  return Vector<Pair<Ktype,Vtype>>::set_length(n);
}


// void set_growth_ratio () -- Set the growth percentage for the object
// Input:                      Float ratio
// Output:                     None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::set_growth_ratio(float n) {
  Vector<Pair<Ktype,Vtype>>::set_growth_ratio(n);
}


// void set_alloc_size () -- Set the default allocation size growth rate.
// Input:                    Growth size in number of elements
// Output:                   None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::set_alloc_size(int n){
  Vector<Pair<Ktype,Vtype>>::set_alloc_size(n);
}


// Ktype& key () -- Get key (first) item in pair object at current position
// Input:           None
// Output:          Reference to Key value of pair

template <class Ktype, class Vtype>
inline const Ktype& Association<Ktype,Vtype>::key() CONST {
  return (this->data[this->curpos].get_first());
}


// Vtype& value () -- Return value at current position.
// Input:             None
// Output:            Type reference to value at current position

template <class Ktype, class Vtype>
inline Vtype& Association<Ktype,Vtype>::value() {
  return (this->data[this->curpos].second());
}


// Boolean operator!= -- Test for inequality of the data of two objects
// Input:                Reference to objects
// Output:               TRUE/FALSE

template <class Ktype, class Vtype>
inline Boolean Association<Ktype,Vtype>::operator!=(const Association<Ktype, Vtype>& a) CONST {
  return (!operator==(a));
}


// set_key_compare -- Set the compare function for the key of the pair
// Input:             Pointer to new function
// Output:            None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::set_key_compare(Association<Ktype,Vtype>_Key_Compare f) {
  if (f == NULL)
    this->compare_keys_s=&Association<Ktype,Vtype>_keys_eql; // Default equal   
  else
    this->compare_keys_s = f;
}


// set_value_compare -- Set the compare function for the value of the pair
// Input:               Pointer to new function
// Output:              None

template <class Ktype, class Vtype>
inline void Association<Ktype,Vtype>::set_value_compare(Association<Ktype,Vtype>_Value_Compare f) {
  if (f == NULL)
    this->compare_values_s = &Association<Ktype,Vtype>_values_eql; // Default
  else
    this->compare_values_s = f;
}


// Association -- Destructor (not inline because it's virtual)
// Input:         None
// Output:        None

template <class Ktype, class Vtype>
Association<Ktype,Vtype>::~Association<Ktype,Vtype> () {;}

// Association -- Empty constructor for the Association class
// Input:         None
// Output:        None

template <class Ktype, class Vtype>
Association<Ktype,Vtype>::Association<Ktype,Vtype> () {
  if (this->compare_keys_s == NULL)		// If no compare function
    compare_keys_s=&Association<Ktype,Vtype>_keys_eql; // Set to default equal
  if (this->compare_values_s == NULL)		// If no compare function
    compare_values_s = &Association<Ktype,Vtype>_values_eql; // Set to default
}


// Association -- Constructor that specifies number of elements
// Input:         Number of elements of Type T
// Output:        None

template <class Ktype, class Vtype>
Association<Ktype,Vtype>::Association<Ktype,Vtype> (unsigned long n)
#ifdef __cplusplus
 : Vector<Pair<Ktype,Vtype>>(n)
#else
 : (n)
#endif
{
  if (this->compare_keys_s == NULL)		// If no compare function
    compare_keys_s=&Association<Ktype,Vtype>_keys_eql; // Set to default equal
  if (this->compare_values_s == NULL)		// If no compare function
    compare_values_s = &Association<Ktype,Vtype>_values_eql; // Set to default
}


// Association -- Constructor that specifies number of elements and storage
// Input:         Pointer to storage and number of elements of Type T
// Output:        None

template <class Ktype, class Vtype>
Association<Ktype,Vtype>::Association<Ktype,Vtype> (void* s,unsigned long n)
#ifdef __cplusplus
 : Vector<Pair<Ktype,Vtype>>(s,n)
#else
 : (s,n)
#endif
{
  if (this->compare_keys_s == NULL)		// If no compare function
    compare_keys_s=&Association<Ktype,Vtype>_keys_eql; // Set to default equal
  if (this->compare_values_s == NULL)		// If no compare function
    compare_values_s = &Association<Ktype,Vtype>_values_eql; // Set to default
}


// Association -- Constructor for reference to another Association object
// Input:         Association reference
// Output:        None

template <class Ktype, class Vtype>
Association<Ktype,Vtype>::Association<Ktype,Vtype>
                         (const Association<Ktype,Vtype>& a)
#ifdef __cplusplus
 : Vector<Pair<Ktype,Vtype>>(a)
#else
 : (a)
#endif
{
  if (this->compare_keys_s == NULL)		// If no compare function
    compare_keys_s=&Association<Ktype,Vtype>_keys_eql; // Set to default equal
  if (this->compare_values_s == NULL)		// If no compare function
    compare_values_s = &Association<Ktype,Vtype>_values_eql; // Set to default
}


// operator= -- Overload the assignment operator to copy the elements
//              in one Association to another. If there are more elements in
//              the source than the destination and the destination is
//              not of static size, then storage will be allocated and
//              the destination Association will grow.
// Input:       Reference to Association
// Output:      Reference to copied Association object

template <class Ktype, class Vtype>
Association<Ktype,Vtype>& Association<Ktype,Vtype>::operator=(const Association<Ktype,Vtype>& a) {
  Vector<Pair<Ktype,Vtype>>::operator=(a);
  return *this;
}


// operator== -- Compare the elements of two Associations of Type Type using
//               the Compare pointer to funtion (default is ==). If one 
//               Association has more elements than another Association, 
//               then result is FALSE
// Input:        Reference to Association object
// Output:       TRUE/FALSE

template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::operator==
        (const Association<Ktype,Vtype>& a) CONST {
  if (this->number_elements != a.number_elements) // If not same number
    return FALSE;				  // Then not equal
  for (long i = 0; i < this->number_elements; i++) { // For each element
    for (long j = 0; j < a.number_elements; j++) {
      if ((*this->compare_keys_s)(this->data[i].get_first(),
				  a.data[j].get_first()) == TRUE) {
	if ((*this->compare_values_s) (this->data[i].second(),
				       a.data[j].second()) == TRUE)
	  goto match;				// Match
	return FALSE;				// Values different
      }
    }
    return FALSE;				// Key not found
  match: ;
  }
  return TRUE;					// All are equal
}


// find -- Find first occurence of element in an Association
// Input:  Element value searching for
// Output: TRUE/FALSE; current_position updated

template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::find (const Ktype& key) {
  for (this->reset(); this->next(); )		           // For each element 
    if ((*this->compare_keys_s)(this->key(), key) == TRUE) // Are they equal?
      return TRUE;					   // Yes, return TRUE
  return FALSE;						   // Return failure
}


// get -- Get the associated value for a key in the Association; return TRUE 
//        and modify the given value variable if the key is found, otherwise 
//        return FALSE and do not modify the value variable
// Input:  Reference to a key, reference to a value 
// Output: TRUE or FALSE

template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::get (const Ktype& key, Vtype& value) {
  for (long i = 0; i < this->number_elements; i++)
    if ((*this->compare_keys_s)(this->data[i].get_first(), key) == TRUE) {
      value = this->data[i].second();
      return TRUE;
    }
  return FALSE;
}


// get_key -- Get the associated key for a value in the Association; return 
//            TRUE and modify the given key variable if the value is found, 
//            otherwise return FALSE and do not modify the value variable
// Input:     Reference to a value, reference to a key 
// Output:    TRUE or FALSE

template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::get_key (const Vtype& value, Ktype& key) CONST {
  for (long i = 0; i < this->number_elements; i++)
   if ((*this->compare_values_s)(this->data[i].get_second(), value) == TRUE) {
     key = this->data[i].first();
     return TRUE;
   }
  return FALSE;
}


// remove() -- Remove the pair at the current position and return the 
//             value associated with that pair
// Input:      None.
// Output:     Reference to the value of the pair removed

template <class Ktype, class Vtype>
Vtype& Association<Ktype,Vtype>::remove () {
  Pair<Ktype,Vtype>* temp = new Pair<Ktype,Vtype>[this->size]; // Temporary
  for (long i = 0; i < this->curpos; i++)       // For each element
    temp[i] = this->data[i];			// Copy data
  this->curpos = i;				// Point after element removed
  Vtype& value = this->data[i].second();	// Copy value removed
  for (++i; i < this->number_elements; i++)	// Copy remaining elements
    temp[i-1] = this->data[i];		        // Copy data
  delete this->data;				// Deallocate memory
  this->data = temp;				// Assign to new block
  this->number_elements--;			// Update element count
  if (this->curpos == this->number_elements)	// If past end 
    this->curpos = INVALID;			// Invalidate current position
  return value;					// Return Association reference
}


// remove (key) -- Search for key and remove the pair associated with it, 
//                 if found, and return TRUE; otherwise return FALSE
// Input:          Reference to a key
// Output:         TRUE or FALSE

template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::remove (const Ktype& key) {
  Pair<Ktype,Vtype>* temp = new Pair<Ktype,Vtype>[this->size];
  for (long i = 0; i < this->number_elements; i++)
    if ((*(this->compare_keys_s))(this->data[i].get_first(), key) == TRUE)
      break;					// Stop if key is found
    else temp[i] = this->data[i];		// Copy data
  if (i == this->number_elements) {		// The key was not found
    curpos = INVALID;				// Invalidate current position
    return FALSE;				// Return failure
  }
  this->curpos = i;				// Else update curpos
  for (++i; i < this->number_elements; i++)     // For remaining elements
    temp[i-1] = this->data[i];		        // Copy data
  delete this->data;				// Deallocate memory
  this->data = temp;				// Assign to new block
  this->number_elements--;			// Update element count
  if (this->curpos == this->number_elements)	// If past end 
    this->curpos = INVALID;			// Invalidate current position
  return TRUE;					// Report success
}


// put -- Add a key-value pair to the Association; if the key already exists,
//        replace its associated value in the Association; return TRUE if 
//        successful
// Input:  Reference to a key, reference to a value
// Output: TRUE or FALSE

template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::put (const Ktype& key, const Vtype& value) {
  for (long i = 0; i < this->number_elements; i++) // Search for key in list
     if ((*this->compare_keys_s)(this->data[i].get_first(), key) == TRUE) {
       this->data[i].set_second(value);		// Update value if found
       this->curpos = i;			// Update current position
       return TRUE;				// Return success
    }
  if (this->number_elements == this->size) {	// If not enough memory
    if (this->alloc_size == INVALID) {		// If not allowed to grow
#if ERROR_CHECKING
      RAISE (Error, SYM(Association), SYM(Static_Size),
	     "Association<%s,%s>::put(): Static-size association",
	     #Ktype,#Vtype);
#endif
      return FALSE;				// Return failure flag
    }
    Pair<Ktype,Vtype>* temp;			// Temporary storage
    if (this->growth_ratio != 0.0) 		// If growth ratio specified
      this->size = (long)(this->size * (1.0 + growth_ratio)); // New size
    else
      this->size += alloc_size;			// Update vector size
    temp = new Pair<Ktype,Vtype>[this->size];	// Allocate storage
    for (long i = 0; i < this->length(); i++)	// For all elements
      temp[i] = this->data[i];			// Copy data
    delete this->data;				// Free up old memory
    this->data = temp;				// Assign new memory block
  }
  this->curpos = this->length();		// Set current position
  this->data[this->length()].set_first(key);	// Set the key (first) value
  this->data[this->length()].set_second(value); // Set the value (second)
  this->number_elements++;			// Increment element count
  return TRUE;					// Return success status
}


// keys_eql -- Compare two keys to see if they are equal using operator==
// Input:      Two Ktype references
// Output:     TRUE or FALSE

template <class Ktype, class Vtype> Association {
  Boolean Association<Ktype,Vtype>_keys_eql (const Ktype& k1, const Ktype& k2) {
    return ((k1 == k2) ? TRUE : FALSE);
  }
}


// values_eql -- Compare two values to see if they are equal using operator==
// Input:        Two Vtype references
// Output:       TRUE or FALSE

template <class Ktype, class Vtype> Association {
  Boolean Association<Ktype,Vtype>_values_eql(const Vtype& v1,const Vtype& v2) {
    return ((v1 == v2) ? TRUE : FALSE);
  }
}


// operator<< -- Overload the output operator for pointer to Association
// Input:        ostream reference, Assocition pointer
// Output:       Association data is output to ostream

template <class Ktype, class Vtype> Association {
ostream& operator<< (ostream& os, CONST Association<Ktype,Vtype>* v) {
  return operator<< (os, (CONST Vector<Pair<Ktype,Vtype>>*) v);
}
}

  
// operator<< -- Overload the output operator for reference to Association
// Input:        ostream reference, Association reference
// Output:       Association data is output to ostream

template <class Ktype, class Vtype> Association {
ostream& operator<< (ostream& os, CONST Association<Ktype,Vtype>& v) {
  return operator<< (os, (CONST Vector<Pair<Ktype,Vtype>>&) v);
}
}


// Set/Get current position
template <class Ktype, class Vtype>
inline Association_state& Association<Ktype,Vtype>::current_position () {
  return Vector<Pair<Ktype,Vtype>>::current_position();
}


// If all the generic support hasn't been loaded yet, do it now.
#ifndef GENERIC_H
#include <cool/Generic.h>
#endif

#endif				// End #ifdef of ASSOCIATIONH
