rendered paste body#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;
}