#ifndef WEISBART_H
#define WEISBART_H
#include <cstdlib>
#include <exception>
#include <stdexcept>
template <class K, class V>
class keyed_node {
	public:
		K key;
		V data;
};
template <class K, class V>
class const_iterator{
	public :
		typedef keyed_node<K,V> keyed_node;
		const_iterator(){
			current = 0;
			std::cout << "No data has been added" << std::endl;
			system("PAUSE");
		}
		const_iterator(keyed_node* d){
			current = 0;
			data = d;
			std::cout << "Current is now " << 0 << std::endl;
			system("PAUSE");
		}
	 	const_iterator(keyed_node* d,int i){
			current = i;
			data = d;
			std::cout << "Current is now " << i << std::endl;
			system("PAUSE");
		}
		const_iterator<K,V>& operator *(){
			first = data[current].data;
			second = data[current].key;
			return *this;
		}
		const_iterator<K,V>& operator ++(int){
			current++;
			std::cout << "Current is now " << current << std::endl;
			return *this;
		}
		const_iterator<K,V>& operator --(){
			return current--;
		}
		bool operator !=(const_iterator other){
			return(current != other.current);
		}
		K second;
		V first;
	private :
		
		int current;
		keyed_node *data;
};
template <class K, class V>
class keyed_bag4 {
	public:
		typedef const_iterator<K,V> const_iterator;
		
		typedef K key_type;
		typedef V value_type;
		typedef std::size_t size_type;
		keyed_bag4();
		keyed_bag4(const keyed_bag4& source);
		~keyed_bag4();
		keyed_bag4& operator =(const keyed_bag4& source);
		void insert(const value_type& entry, key_type key);
		bool erase(key_type key);
		value_type get(key_type key) const throw(std::invalid_argument);
		size_type size() const;
		size_type count(const value_type& target) const;
		bool has_key(key_type key) const;
		const_iterator begin(){
			return const_iterator(data);
		}
		const_iterator end(){
			return const_iterator(data,current_size);
		}
	private:
		typedef keyed_node<K,V> keyed_node;
		static const size_type DEFAULT_CAPACITY = 20000;
		keyed_node *data;
		bool *free_slots;
		int get_free_slot();
		void clean_data();
		void init_free_slots();
		int current_size;
		int capacity;
		keyed_node associate_key_2_member(key_type key,int& i);
		keyed_node associate_key_2_member(key_type key,int& i) const;
};
#include "keyed_bag4.template"
#endif


#include <cstdlib>
#include <iostream>
#include <exception>
#include <stdexcept>
template <class K, class V>
keyed_bag4<K,V>::keyed_bag4(){
	capacity = DEFAULT_CAPACITY;
	data = new keyed_node[capacity];
	free_slots = new bool[capacity];
	clean_data();
	current_size = 0;
	init_free_slots();
}
template <class K, class V>
keyed_bag4<K,V>::keyed_bag4(const keyed_bag4& source){
	if (this == &source){
          return;
     }
     keyed_node *new_data;
     bool *new_free_keys;
	new_data = new keyed_node[source.capacity];
     delete [ ] data;
     data = new_data;
     new_free_keys = new bool[source.capacity];
     delete [ ] free_slots;
     free_slots = new_free_keys;
     capacity = source.capacity;
     current_size = source.current_size;
     copy(source.data,source.data+capacity,data);
     copy(source.free_slots,source.free_slots+capacity,free_slots);
}
template <class K, class V>
keyed_bag4<K,V>::~keyed_bag4(){
	delete [] data;
	delete [] free_slots;
}
template <class K, class V>
void keyed_bag4<K,V>::init_free_slots(){
	int i;
	for(i=0;i<capacity;i++){
		free_slots[i] = true;
	}
}
template <class K, class V>
bool keyed_bag4<K,V>::has_key(key_type key) const{
	int i = 0;
     typename keyed_bag4::keyed_node node =keyed_bag4::associate_key_2_member(key,i);
     if(node.key == capacity+1)
          return false;
     else
          return true;
}
template <class K, class V>
typename keyed_bag4<K,V>::value_type keyed_bag4<K,V>::get(K key) const throw(std::invalid_argument){
	int i=0;
	keyed_node node=associate_key_2_member(key,i);
	
	if(node.key == capacity+1){
		throw std::invalid_argument("Key not found!");
	}else{
		return node.data;
	}
}
template <class K, class V>
bool keyed_bag4<K,V>::erase(key_type key){
     int i=0;
     keyed_node node = associate_key_2_member(key,i);
     if(node.key = capacity+1)
     	return false;
     data[i].key = 0;
     data[i].data = 0;
     free_slots[key] = false;
     return true;
}
template <class K, class V>
typename keyed_bag4<K,V>::keyed_node keyed_bag4<K,V>::associate_key_2_member(key_type key,int& i){
     while(data[i].key != key){
          i++;
          if(i == capacity){
               //Create an oversized key to return an error that the key was not found
               keyed_node data2;
               data2.key = capacity+1;
               return data2;
          }
     }
     return data[i];
}
template <class K, class V>
typename keyed_bag4<K,V>::keyed_node keyed_bag4<K,V>::associate_key_2_member(key_type key,int& i) const{
     while(data[i].key != key){
          i++;
          if(i == capacity){
               //Create an oversized key to return an error that the key was not found
               keyed_node data2;
               data2.key = capacity+1;
               return data2;
          }
     }
     return data[i];
}
template <class K, class V>
//Insersts a value into a key on the key ring (data)
void keyed_bag4<K,V>::insert(const value_type& value, key_type _key){
     int i=0;
     keyed_node node = keyed_bag4::associate_key_2_member(_key,i);
     if(node.key > capacity){ //key not found
          i = keyed_bag4::get_free_slot();
          data[i].key = _key;
          data[i].data = value;
     }else{
          data[i].data = value;
     }
     free_slots[i] = false; //Make sure that the key gets registered
     current_size++;
}
template <class K, class V>
//My indexing function from hell!
int keyed_bag4<K,V>::get_free_slot(){
     int i=0;
     while(bool(free_slots[i]) != true){
          i++;
          if(i == capacity){
               //WTF? We have no free keys how the hell did this get run >_< GG
               return capacity+1;
          }
     }
     return i;
}
template <class K, class V>
std::size_t keyed_bag4<K,V>::count(const value_type& target) const{
     size_type answer;
     int i;
     answer =0;
     for(i=0;i<capacity;++i){
          if(free_slots[i] == false){                   
               if(data[i].data == target){
                    answer++;
               }
		}
     }
     return answer;
}
template <class K, class V>
void keyed_bag4<K,V>::clean_data(){
	int i;
	data[0].data = 0;
	data[0].key = 0;

}
template <class K, class V>
std::size_t keyed_bag4<K,V>::size() const{
  return current_size;
}
template <class K, class V>
keyed_bag4<K,V>& keyed_bag4<K,V>::operator =(const keyed_bag4& source){
     keyed_node *new_data;
     bool *new_free_keys;
	if (this == &source){
          return *this;
     }
     if (capacity != source.capacity){
          new_data = new keyed_node[source.capacity];
          delete [ ] data;
          data = new_data;
          new_free_keys = new bool[source.capacity];
          delete [ ] free_slots;
          free_slots = new_free_keys;
          capacity = source.capacity;
     }
     current_size = source.current_size;
     copy(source.data,source.data+capacity,data);
     copy(source.free_slots,source.free_slots+capacity,free_slots);
     return *this;
}
#include <iostream>
#include <stdexcept>
#include "keyed_bag4.h"

using namespace std;

int main() {
  keyed_bag4<int, double> k0;
  
  // Test dynamic allocation
  
  for (int i = 0; i < 1000; ++i)
    k0.insert(i, 1000*i);
  
  cout << endl;
  cout << "After 1000 insertions:" << endl;
  cout << "The bag k0 has " << k0.size() << " [1000] elements." << endl;
  cout << "The value of key 50,000 is " << k0.get(50000) << " [50]" << endl;
  cout << "k0.has_key(50000) returns " << k0.has_key(50000) << " [1]" << endl << endl;
  
  // Test the copy constructor
  
  keyed_bag4<int, double> k1(k0);
  
  cout << "After keyed_bag3 k1(k0):" << endl;
  cout << "The bag k1 has " << k1.size() << " [1000] elements." << endl << endl;
  
  // Test erase() and has_key()
  
  for (int i = 0; i < 1000; ++i)
    k0.erase(1000*i);
  
  cout << "After 1000 erases: " << endl;
  cout << "The bag k0 has " << k0.size() << " [0] elements." << endl;
  cout << "The bag k1 has " << k1.size() << " [1000] elements." << endl;
  cout << "k0.has_key(50000) returns " << k0.has_key(50000) << " [0]" << endl << endl;
 
  // Test the assignment operator
  
  k1 = k0;
  
  cout << "After k1 = k0:" << endl;
  cout << "The bag k1 has " << k1.size() << " [0] elements." << endl << endl;
  
  // Test the insert() of duplicate keys
  
  k1.insert(1, 1000);
  k1.insert(2, 1000);
  k1.insert(3, 1000);
  
  cout << "After inserting into K1 (1, 1000); (2, 1000); (3, 1000):" << endl;
  cout << "   The value of key 1000 is " << k1.get(1000) << " [3]" << endl << endl;

  // Test count()
  
  k1.insert(1, 1000);
  k1.insert(1, 2000);
  k1.insert(1, 3000);
  
  cout << "After inserting (1, 1000); (1, 2000); (1, 3000):" << endl;
  cout << "   The count of value 1 is " << k1.count(1) << " [3]" << endl << endl;
   system("PAUSE");
  // Test the iterator
  
  keyed_bag4<int, double> k2;
  
  for (int i = 10; i < 30; ++i)
    k2.insert(i, 100*i); 
  const_iterator<int, double> i, e = k2.end();
  
  for (i = k2.begin(); i != e; i++)
    cout << "Key: " << (*i).second << " Value: " << (*i).first << endl;
  cout << endl;
  
  // Test get() and exception handling
  double v;
  try {
    v = k2.get(31416);
    cout << "The get for key 31316 was successful, v = " << v << endl; }
  catch (invalid_argument ia) {
    cout << "Key 31316 not found!" << endl
         << "ia.what() returns: " << ia.what() << endl << endl; }
  catch (...) {
    cout << "Unknown exception caught." << endl; }
  
  return EXIT_SUCCESS;
}