#include<iostream> #include <string> #include <utility> #include <functional> #include <algorithm> using namespace std; template <class TYPE> class Table { public: Table() {} virtual bool update(const string& key, const TYPE& value) = 0; virtual bool remove(const string& key) = 0; virtual bool find(const string& key, TYPE& value) = 0; virtual ~Table() {} }; template <class TYPE> class SimpleTable :public Table<TYPE> { struct Record { TYPE data_; string key_; Record(const string& key, const TYPE& data) { key_ = key; data_ = data; } }; Record** records_; //the table int max_; //capacity of the array int size_; //current number of records held int search(const string& key); void sort(); void grow(); public: SimpleTable(int maxExpected); SimpleTable(const SimpleTable& other); SimpleTable(SimpleTable&& other); virtual bool update(const string& key, const TYPE& value); virtual bool remove(const string& key); virtual bool find(const string& key, TYPE& value); virtual const SimpleTable& operator=(const SimpleTable& other); virtual const SimpleTable& operator=(SimpleTable&& other); virtual ~SimpleTable(); }; //returns index of where key is found. template <class TYPE> int SimpleTable<TYPE>::search(const string& key) { int rc = -1; for (int i = 0; i<size_; i++) { if (records_[i]->key_ == key) { rc = i; } } return rc; } //sort the according to keyt = in table template <class TYPE> void SimpleTable<TYPE>::sort() { int minIdx = 0; for (int i = 0; i<size_; i++) { minIdx = i; for (int j = i + 1; j<size_; j++) { if (records_[j]->key_ < records_[minIdx]->key_) { minIdx = j; } } Record* tmp = records_[i]; records_[i] = records_[minIdx]; records_[minIdx] = tmp; } } //grow the array by one element template <class TYPE> void SimpleTable<TYPE>::grow() { Record** newArray = new Record*[max_ + 1]; max_ = max_ + 1; for (int i = 0; i<size_; i++) { newArray[i] = records_[i]; } delete[] records_; records_ = newArray; } /* none of the code in the function definitions below are correct. You can replace what you need */ template <class TYPE> SimpleTable<TYPE>::SimpleTable(int maxExpected) : Table<TYPE>() { records_ = new Record*[maxExpected]; max_ = maxExpected; size_ = 0; } template <class TYPE> SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& other) { records_ = new Record*[other.max_]; max_ = other.max_; size_ = 0; for (int i = 0; i<other.size_; i++) { update(other.records_[i]->key_, other.records_[i]->data_); } } template <class TYPE> SimpleTable<TYPE>::SimpleTable(SimpleTable<TYPE>&& other) { size_ = other.size_; max_ = other.max_; records_ = other.records_; other.records_ = nullptr; other.size_ = 0; other.max_ = 0; } template <class TYPE> bool SimpleTable<TYPE>::update(const string& key, const TYPE& value) { int idx = search(key); if (idx == -1) { if (size_ == max_) { grow(); } records_[size_++] = new Record(key, value); sort(); } else { records_[idx]->data_ = value; } return true; } template <class TYPE> bool SimpleTable<TYPE>::remove(const string& key) { int idx = search(key); if (idx != -1) { delete records_[idx]; for (int i = idx; i<size_ - 1; i++) { records_[i] = records_[i + 1]; } size_--; return true; } else { return false; } } template <class TYPE> bool SimpleTable<TYPE>::find(const string& key, TYPE& value) { int idx = search(key); if (idx == -1) return false; else { value = records_[idx]->data_; return true; } } template <class TYPE> const SimpleTable<TYPE>& SimpleTable<TYPE>::operator=(const SimpleTable<TYPE>& other) { if (this != &other) { if (records_) { int sz = size_; for (int i = 0; i<sz; i++) { remove(records_[0]->key_); } delete[] records_; } records_ = new Record*[other.max_]; max_ = other.max_; size_ = 0; for (int i = 0; i<other.size_; i++) { update(other.records_[i]->key_, other.records_[i]->data_); } } return *this; } template <class TYPE> const SimpleTable<TYPE>& SimpleTable<TYPE>::operator=(SimpleTable<TYPE>&& other) { swap(records_, other.records_); swap(size_, other.size_); swap(max_, other.max_); return *this; } template <class TYPE> SimpleTable<TYPE>::~SimpleTable() { if (records_) { int sz = size_; for (int i = 0; i<sz; i++) { remove(records_[0]->key_); } delete[] records_; } } template <class TYPE> class HashTable :public Table<TYPE> { struct Record { TYPE data_; string key_; Record* Next; Record(const string& key, const TYPE& data) { key_ = key; data_ = data; Next = nullptr; } Record(const Record& a) { if(!a.key_.empty()){ if(a.Next == nullptr){ this->data_ = a.data_ ; this->key_ = a.key_; } else { } // user-defined copy ctor } }; int TableSize; Record** records; public: HashTable(int maxExpected); HashTable(const HashTable& other); HashTable(HashTable&& other); virtual bool update(const string& key, const TYPE& value); virtual bool remove(const string& key); virtual bool find(const string& key, TYPE& value); virtual const HashTable& operator=(const HashTable& other); virtual const HashTable& operator=(HashTable&& other); virtual ~HashTable(); int NumOfItems(int index); void Print(); void PrintItemsInIndex(int index); }; /* none of the code in the function definitions below are correct. You can replace what you need */ template <class TYPE> void HashTable<TYPE>::Print() { int number; for (int i = 0; i < TableSize; i++) { number = NumOfItems(i); cout << "------start-----" << endl; cout << "index = " << i << endl; cout << records[i]->key_ << " key" << endl; cout << records[i]->data_ << " data" << endl; cout << "# of item" << number << endl; cout << "----------end----" << endl; } } template <class TYPE> void HashTable<TYPE>::PrintItemsInIndex(int index) { Record* temp = records[index]; if (temp->key_.empty()) { cout << "Index is empty" << endl; } else { while (temp != nullptr) { cout << "index item" << endl; cout << temp->data_ << " index data" << endl; cout << temp->key_ << " key data" << endl; temp = temp->Next; } } } template <class TYPE> HashTable<TYPE>::HashTable(int maxExpected) : Table<TYPE>() { records = new Record*[maxExpected]; TableSize = maxExpected; for (int i = 0; i < TableSize; i++) records[i] = nullptr; } template <class TYPE> HashTable<TYPE>::HashTable(const HashTable<TYPE>& other) { records = new Record*[other.TableSize] ; TableSize = other.TableSize ; for(int i = 0 ; i < other.TableSize; i++) records[i]= (new Record(*other.records[i])); } template <class TYPE> int HashTable<TYPE>::NumOfItems(int index) { int count = 0; if (records[index]->key_.empty()) { return count; } else { count++; Record* temp = records[index]; while (temp->Next != nullptr) { count++; temp = temp->Next; } } return count; } template <class TYPE> HashTable<TYPE>::HashTable(HashTable<TYPE>&& other) { TableSize = other.TableSize; records = other.records; other.records = nullptr; other.TableSize = 0; } template <class TYPE> bool HashTable<TYPE>::update(const string& key, const TYPE& value) { // int index = std::hash<TYPE> {}(value)%TableSize ; int index = std::hash<string>{}(key) % TableSize; if (records[index] == nullptr) { Record *temp = new Record(key, value); records[index] = temp; return true; } else { Record* n = new Record(key, value); if (records[index]->key_ == key) { records[index] = n; return true; } Record* temp = records[index]; while (temp->Next != nullptr) { temp = temp->Next; } temp->Next = n; return true; } return false; } template <class TYPE> bool HashTable<TYPE>::remove(const string& key) { // int index = std::hash<TYPE> {}(value)%TableSize ; int index = std::hash<string>{}(key) % TableSize; Record* temp1del; Record* p1; Record* p2; if (records[index] == nullptr) // bucket is empty { return false; } else if (records[index]->key_ == key && records[index]->Next == nullptr) // only 1 item is in bucket and that item has matching key { records[index] = nullptr; return true; } else if (records[index]->key_ == key) // match is located in the first item in the bucket but there are more items in the bucket { temp1del = records[index]; records[index] = records[index]->Next; delete temp1del; return true; } else // case 3 bucket contains item but first item is not much { p1 = records[index]->Next; p2 = records[index]; while (p1 != nullptr && p1->key_ != key) { p2 = p1; p1 = p1->Next; } if (p1 == nullptr) // no much { return false; } else // match is found { temp1del = p1; p1 = p1->Next; p2->Next = p1; delete temp1del; return true; } } } template <class TYPE> bool HashTable<TYPE>::find(const string& key, TYPE& value) { bool found = false; // int index = std::hash<TYPE> {}(value)%TableSize ; int index = std::hash<string>{}(key) % TableSize; Record* temp = records[index]; while (temp != nullptr) { if (temp->key_ == key) { value = temp->data_; return true; } temp = temp->Next; } return false; } template <class TYPE> const HashTable<TYPE>& HashTable<TYPE>::operator=(const HashTable<TYPE>& other) { if (this != &other) { delete [] records ; records = new Record*[other.TableSize]; for(int i = 0 ; i < other.TableSize ; i++) records[i] = other.records[i] ; TableSize = other.TableSize; } return *this; } template <class TYPE> const HashTable<TYPE>& HashTable<TYPE>::operator=(HashTable<TYPE>&& other) { swap(records, other.records); swap(TableSize, other.TableSize); return *this; } template <class TYPE> HashTable<TYPE>::~HashTable() { if (records) { for (int i = 0; i < TableSize; i++) records[i] = nullptr; delete[] records; } }
Standard input is empty
Main.java:1: error: illegal character: '#'
#include<iostream>
^
Main.java:1: error: class, interface, or enum expected
#include<iostream>
^
Main.java:2: error: illegal character: '#'
#include <string>
^
Main.java:3: error: illegal character: '#'
#include <utility>
^
Main.java:4: error: illegal character: '#'
#include <functional>
^
Main.java:5: error: illegal character: '#'
#include <algorithm>
^
Main.java:9: error: class, interface, or enum expected
template <class TYPE>
^
Main.java:9: error: '{' expected
template <class TYPE>
^
Main.java:12: error: illegal start of type
public:
^
Main.java:12: error: ';' expected
public:
^
Main.java:13: error: illegal start of type
Table() {}
^
Main.java:13: error: <identifier> expected
Table() {}
^
Main.java:13: error: ';' expected
Table() {}
^
Main.java:14: error: ';' expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: invalid method declaration; return type required
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: illegal start of type
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: ')' expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: ';' expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: illegal start of type
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:14: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value) = 0;
^
Main.java:15: error: ';' expected
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: invalid method declaration; return type required
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: illegal start of type
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: ')' expected
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: ';' expected
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: <identifier> expected
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: illegal start of type
virtual bool remove(const string& key) = 0;
^
Main.java:15: error: <identifier> expected
virtual bool remove(const string& key) = 0;
^
Main.java:16: error: ';' expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: invalid method declaration; return type required
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: illegal start of type
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: ')' expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: ';' expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: <identifier> expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: ';' expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: <identifier> expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: illegal start of type
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:16: error: <identifier> expected
virtual bool find(const string& key, TYPE& value) = 0;
^
Main.java:17: error: <identifier> expected
virtual ~Table() {}
^
Main.java:17: error: invalid method declaration; return type required
virtual ~Table() {}
^
Main.java:20: error: class, interface, or enum expected
template <class TYPE>
^
Main.java:20: error: '{' expected
template <class TYPE>
^
Main.java:21: error: '{' expected
class SimpleTable :public Table<TYPE>
^
Main.java:21: error: <identifier> expected
class SimpleTable :public Table<TYPE>
^
Main.java:24: error: ';' expected
struct Record
^
Main.java:28: error: illegal start of expression
Record(const string& key, const TYPE& data)
^
Main.java:28: error: ';' expected
Record(const string& key, const TYPE& data)
^
Main.java:28: error: illegal start of expression
Record(const string& key, const TYPE& data)
^
Main.java:28: error: <identifier> expected
Record(const string& key, const TYPE& data)
^
Main.java:28: error: not a statement
Record(const string& key, const TYPE& data)
^
Main.java:28: error: ';' expected
Record(const string& key, const TYPE& data)
^
Main.java:36: error: <identifier> expected
Record** records_; //the table
^
Main.java:36: error: illegal start of type
Record** records_; //the table
^
Main.java:39: error: illegal start of type
int search(const string& key);
^
Main.java:39: error: ')' expected
int search(const string& key);
^
Main.java:39: error: ';' expected
int search(const string& key);
^
Main.java:39: error: <identifier> expected
int search(const string& key);
^
Main.java:42: error: illegal start of type
public:
^
Main.java:42: error: ';' expected
public:
^
Main.java:43: error: illegal start of type
SimpleTable(int maxExpected);
^
Main.java:43: error: <identifier> expected
SimpleTable(int maxExpected);
^
Main.java:43: error: ';' expected
SimpleTable(int maxExpected);
^
Main.java:43: error: illegal start of type
SimpleTable(int maxExpected);
^
Main.java:43: error: <identifier> expected
SimpleTable(int maxExpected);
^
Main.java:43: error: ';' expected
SimpleTable(int maxExpected);
^
Main.java:44: error: illegal start of type
SimpleTable(const SimpleTable& other);
^
Main.java:44: error: <identifier> expected
SimpleTable(const SimpleTable& other);
^
Main.java:44: error: ';' expected
SimpleTable(const SimpleTable& other);
^
Main.java:44: error: illegal start of type
SimpleTable(const SimpleTable& other);
^
Main.java:44: error: ';' expected
SimpleTable(const SimpleTable& other);
^
Main.java:45: error: <identifier> expected
SimpleTable(SimpleTable&& other);
^
Main.java:45: error: ';' expected
SimpleTable(SimpleTable&& other);
^
Main.java:45: error: illegal start of type
SimpleTable(SimpleTable&& other);
^
Main.java:45: error: <identifier> expected
SimpleTable(SimpleTable&& other);
^
Main.java:45: error: ';' expected
SimpleTable(SimpleTable&& other);
^
Main.java:46: error: illegal start of type
virtual bool update(const string& key, const TYPE& value);
^
Main.java:46: error: ')' expected
virtual bool update(const string& key, const TYPE& value);
^
Main.java:46: error: ';' expected
virtual bool update(const string& key, const TYPE& value);
^
Main.java:46: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value);
^
Main.java:46: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value);
^
Main.java:46: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value);
^
Main.java:46: error: <identifier> expected
virtual bool update(const string& key, const TYPE& value);
^
Main.java:47: error: ';' expected
virtual bool remove(const string& key);
^
Main.java:47: error: invalid method declaration; return type required
virtual bool remove(const string& key);
^
Main.java:47: error: illegal start of type
virtual bool remove(const string& key);
^
Main.java:47: error: ')' expected
virtual bool remove(const string& key);
^
Main.java:47: error: ';' expected
virtual bool remove(const string& key);
^
Main.java:47: error: <identifier> expected
virtual bool remove(const string& key);
^
Main.java:48: error: ';' expected
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: invalid method declaration; return type required
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: illegal start of type
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: ')' expected
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: ';' expected
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: <identifier> expected
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: ';' expected
virtual bool find(const string& key, TYPE& value);
^
Main.java:48: error: <identifier> expected
virtual bool find(const string& key, TYPE& value);
^
100 errors
Standard output is empty