fork download
  1. #include<iostream>
  2. #include <string>
  3. #include <utility>
  4. #include <functional>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. template <class TYPE>
  10. class Table
  11. {
  12. public:
  13. Table() {}
  14. virtual bool update(const string& key, const TYPE& value) = 0;
  15. virtual bool remove(const string& key) = 0;
  16. virtual bool find(const string& key, TYPE& value) = 0;
  17. virtual ~Table() {}
  18. };
  19.  
  20. template <class TYPE>
  21. class SimpleTable :public Table<TYPE>
  22. {
  23.  
  24. struct Record
  25. {
  26. TYPE data_;
  27. string key_;
  28. Record(const string& key, const TYPE& data)
  29. {
  30. key_ = key;
  31. data_ = data;
  32. }
  33.  
  34. };
  35.  
  36. Record** records_; //the table
  37. int max_; //capacity of the array
  38. int size_; //current number of records held
  39. int search(const string& key);
  40. void sort();
  41. void grow();
  42. public:
  43. SimpleTable(int maxExpected);
  44. SimpleTable(const SimpleTable& other);
  45. SimpleTable(SimpleTable&& other);
  46. virtual bool update(const string& key, const TYPE& value);
  47. virtual bool remove(const string& key);
  48. virtual bool find(const string& key, TYPE& value);
  49. virtual const SimpleTable& operator=(const SimpleTable& other);
  50. virtual const SimpleTable& operator=(SimpleTable&& other);
  51. virtual ~SimpleTable();
  52. };
  53.  
  54.  
  55. //returns index of where key is found.
  56. template <class TYPE>
  57. int SimpleTable<TYPE>::search(const string& key)
  58. {
  59. int rc = -1;
  60. for (int i = 0; i<size_; i++)
  61. {
  62. if (records_[i]->key_ == key)
  63. {
  64. rc = i;
  65. }
  66. }
  67. return rc;
  68. }
  69. //sort the according to keyt = in table
  70. template <class TYPE>
  71. void SimpleTable<TYPE>::sort()
  72. {
  73. int minIdx = 0;
  74. for (int i = 0; i<size_; i++)
  75. {
  76. minIdx = i;
  77. for (int j = i + 1; j<size_; j++)
  78. {
  79. if (records_[j]->key_ < records_[minIdx]->key_)
  80. {
  81. minIdx = j;
  82. }
  83. }
  84. Record* tmp = records_[i];
  85. records_[i] = records_[minIdx];
  86. records_[minIdx] = tmp;
  87. }
  88. }
  89.  
  90. //grow the array by one element
  91. template <class TYPE>
  92. void SimpleTable<TYPE>::grow()
  93. {
  94. Record** newArray = new Record*[max_ + 1];
  95. max_ = max_ + 1;
  96. for (int i = 0; i<size_; i++)
  97. {
  98. newArray[i] = records_[i];
  99. }
  100. delete[] records_;
  101. records_ = newArray;
  102. }
  103.  
  104. /* none of the code in the function definitions below are correct. You can replace what you need
  105. */
  106. template <class TYPE>
  107. SimpleTable<TYPE>::SimpleTable(int maxExpected) : Table<TYPE>()
  108. {
  109. records_ = new Record*[maxExpected];
  110. max_ = maxExpected;
  111. size_ = 0;
  112. }
  113.  
  114. template <class TYPE>
  115. SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& other)
  116. {
  117. records_ = new Record*[other.max_];
  118. max_ = other.max_;
  119. size_ = 0;
  120. for (int i = 0; i<other.size_; i++)
  121. {
  122. update(other.records_[i]->key_, other.records_[i]->data_);
  123. }
  124. }
  125. template <class TYPE>
  126. SimpleTable<TYPE>::SimpleTable(SimpleTable<TYPE>&& other)
  127. {
  128. size_ = other.size_;
  129. max_ = other.max_;
  130. records_ = other.records_;
  131. other.records_ = nullptr;
  132. other.size_ = 0;
  133. other.max_ = 0;
  134. }
  135.  
  136. template <class TYPE>
  137. bool SimpleTable<TYPE>::update(const string& key, const TYPE& value)
  138. {
  139. int idx = search(key);
  140. if (idx == -1)
  141. {
  142. if (size_ == max_)
  143. {
  144. grow();
  145. }
  146. records_[size_++] = new Record(key, value);
  147. sort();
  148. }
  149. else
  150. {
  151. records_[idx]->data_ = value;
  152. }
  153. return true;
  154. }
  155.  
  156. template <class TYPE>
  157. bool SimpleTable<TYPE>::remove(const string& key)
  158. {
  159. int idx = search(key);
  160. if (idx != -1)
  161. {
  162. delete records_[idx];
  163. for (int i = idx; i<size_ - 1; i++)
  164. {
  165. records_[i] = records_[i + 1];
  166. }
  167. size_--;
  168. return true;
  169. }
  170. else
  171. {
  172. return false;
  173. }
  174. }
  175.  
  176. template <class TYPE>
  177. bool SimpleTable<TYPE>::find(const string& key, TYPE& value)
  178. {
  179. int idx = search(key);
  180. if (idx == -1)
  181. return false;
  182. else
  183. {
  184. value = records_[idx]->data_;
  185. return true;
  186. }
  187. }
  188.  
  189. template <class TYPE>
  190. const SimpleTable<TYPE>& SimpleTable<TYPE>::operator=(const SimpleTable<TYPE>& other)
  191. {
  192. if (this != &other)
  193. {
  194. if (records_)
  195. {
  196. int sz = size_;
  197. for (int i = 0; i<sz; i++)
  198. {
  199. remove(records_[0]->key_);
  200. }
  201. delete[] records_;
  202. }
  203. records_ = new Record*[other.max_];
  204. max_ = other.max_;
  205. size_ = 0;
  206. for (int i = 0; i<other.size_; i++)
  207. {
  208. update(other.records_[i]->key_, other.records_[i]->data_);
  209. }
  210.  
  211. }
  212. return *this;
  213. }
  214. template <class TYPE>
  215. const SimpleTable<TYPE>& SimpleTable<TYPE>::operator=(SimpleTable<TYPE>&& other)
  216. {
  217. swap(records_, other.records_);
  218. swap(size_, other.size_);
  219. swap(max_, other.max_);
  220. return *this;
  221. }
  222. template <class TYPE>
  223. SimpleTable<TYPE>::~SimpleTable()
  224. {
  225. if (records_)
  226. {
  227. int sz = size_;
  228. for (int i = 0; i<sz; i++)
  229. {
  230. remove(records_[0]->key_);
  231. }
  232. delete[] records_;
  233. }
  234. }
  235.  
  236. template <class TYPE>
  237. class HashTable :public Table<TYPE>
  238. {
  239. struct Record
  240. {
  241. TYPE data_;
  242. string key_;
  243. Record* Next;
  244.  
  245. Record(const string& key, const TYPE& data)
  246. {
  247. key_ = key;
  248. data_ = data;
  249. Next = nullptr;
  250. }
  251. Record(const Record& a) {
  252. if(!a.key_.empty()){
  253.  
  254. if(a.Next == nullptr){
  255. this->data_ = a.data_ ;
  256. this->key_ = a.key_;
  257.  
  258.  
  259. }
  260. else
  261. {
  262.  
  263.  
  264. } // user-defined copy ctor
  265.  
  266. }
  267.  
  268. };
  269. int TableSize;
  270. Record** records;
  271.  
  272. public:
  273. HashTable(int maxExpected);
  274. HashTable(const HashTable& other);
  275. HashTable(HashTable&& other);
  276. virtual bool update(const string& key, const TYPE& value);
  277. virtual bool remove(const string& key);
  278. virtual bool find(const string& key, TYPE& value);
  279. virtual const HashTable& operator=(const HashTable& other);
  280. virtual const HashTable& operator=(HashTable&& other);
  281. virtual ~HashTable();
  282. int NumOfItems(int index);
  283. void Print();
  284. void PrintItemsInIndex(int index);
  285.  
  286. };
  287. /* none of the code in the function definitions below are correct. You can replace what you need
  288. */
  289. template <class TYPE>
  290. void HashTable<TYPE>::Print()
  291. {
  292.  
  293. int number;
  294. for (int i = 0; i < TableSize; i++)
  295. {
  296. number = NumOfItems(i);
  297. cout << "------start-----" << endl;
  298. cout << "index = " << i << endl;
  299. cout << records[i]->key_ << " key" << endl;
  300. cout << records[i]->data_ << " data" << endl;
  301. cout << "# of item" << number << endl;
  302. cout << "----------end----" << endl;
  303. }
  304.  
  305.  
  306. }
  307. template <class TYPE>
  308. void HashTable<TYPE>::PrintItemsInIndex(int index)
  309. {
  310. Record* temp = records[index];
  311. if (temp->key_.empty())
  312. {
  313. cout << "Index is empty" << endl;
  314.  
  315. }
  316. else
  317. {
  318.  
  319. while (temp != nullptr)
  320. {
  321. cout << "index item" << endl;
  322. cout << temp->data_ << " index data" << endl;
  323. cout << temp->key_ << " key data" << endl;
  324. temp = temp->Next;
  325. }
  326. }
  327.  
  328. }
  329.  
  330. template <class TYPE>
  331. HashTable<TYPE>::HashTable(int maxExpected) : Table<TYPE>()
  332. {
  333. records = new Record*[maxExpected];
  334. TableSize = maxExpected;
  335. for (int i = 0; i < TableSize; i++)
  336. records[i] = nullptr;
  337.  
  338. }
  339.  
  340. template <class TYPE>
  341. HashTable<TYPE>::HashTable(const HashTable<TYPE>& other)
  342. {
  343. records = new Record*[other.TableSize] ;
  344. TableSize = other.TableSize ;
  345. for(int i = 0 ; i < other.TableSize; i++)
  346. records[i]= (new Record(*other.records[i]));
  347.  
  348. }
  349.  
  350.  
  351.  
  352. template <class TYPE>
  353. int HashTable<TYPE>::NumOfItems(int index)
  354. {
  355. int count = 0;
  356. if (records[index]->key_.empty())
  357. {
  358. return count;
  359. }
  360. else
  361. {
  362. count++;
  363. Record* temp = records[index];
  364. while (temp->Next != nullptr)
  365. {
  366. count++;
  367. temp = temp->Next;
  368.  
  369.  
  370. }
  371.  
  372. }
  373. return count;
  374. }
  375.  
  376.  
  377. template <class TYPE>
  378. HashTable<TYPE>::HashTable(HashTable<TYPE>&& other)
  379. {
  380. TableSize = other.TableSize;
  381. records = other.records;
  382. other.records = nullptr;
  383. other.TableSize = 0;
  384. }
  385. template <class TYPE>
  386. bool HashTable<TYPE>::update(const string& key, const TYPE& value)
  387. {
  388. // int index = std::hash<TYPE> {}(value)%TableSize ;
  389. int index = std::hash<string>{}(key) % TableSize;
  390.  
  391. if (records[index] == nullptr)
  392. {
  393. Record *temp = new Record(key, value);
  394. records[index] = temp;
  395. return true;
  396.  
  397. }
  398. else
  399. {
  400. Record* n = new Record(key, value);
  401.  
  402. if (records[index]->key_ == key)
  403. {
  404. records[index] = n;
  405. return true;
  406. }
  407. Record* temp = records[index];
  408.  
  409.  
  410.  
  411.  
  412. while (temp->Next != nullptr)
  413. {
  414. temp = temp->Next;
  415. }
  416.  
  417. temp->Next = n;
  418. return true;
  419.  
  420. }
  421.  
  422. return false;
  423. }
  424.  
  425. template <class TYPE>
  426. bool HashTable<TYPE>::remove(const string& key)
  427. {
  428. // int index = std::hash<TYPE> {}(value)%TableSize ;
  429. int index = std::hash<string>{}(key) % TableSize;
  430.  
  431. Record* temp1del;
  432. Record* p1;
  433. Record* p2;
  434. if (records[index] == nullptr) // bucket is empty
  435. {
  436. return false;
  437. }
  438. else if (records[index]->key_ == key && records[index]->Next == nullptr) // only 1 item is in bucket and that item has matching key
  439. {
  440. records[index] = nullptr;
  441.  
  442.  
  443. return true;
  444.  
  445. }
  446. else if (records[index]->key_ == key) // match is located in the first item in the bucket but there are more items in the bucket
  447. {
  448. temp1del = records[index];
  449. records[index] = records[index]->Next;
  450. delete temp1del;
  451. return true;
  452. }
  453. else // case 3 bucket contains item but first item is not much
  454. {
  455. p1 = records[index]->Next;
  456. p2 = records[index];
  457. while (p1 != nullptr && p1->key_ != key)
  458. {
  459. p2 = p1;
  460. p1 = p1->Next;
  461.  
  462. }
  463. if (p1 == nullptr) // no much
  464. {
  465. return false;
  466. }
  467. else // match is found
  468. {
  469. temp1del = p1;
  470. p1 = p1->Next;
  471. p2->Next = p1;
  472. delete temp1del;
  473. return true;
  474. }
  475. }
  476.  
  477. }
  478.  
  479. template <class TYPE>
  480. bool HashTable<TYPE>::find(const string& key, TYPE& value)
  481. {
  482. bool found = false;
  483. // int index = std::hash<TYPE> {}(value)%TableSize ;
  484. int index = std::hash<string>{}(key) % TableSize;
  485. Record* temp = records[index];
  486.  
  487. while (temp != nullptr)
  488. {
  489. if (temp->key_ == key) {
  490. value = temp->data_;
  491. return true;
  492. }
  493. temp = temp->Next;
  494. }
  495.  
  496. return false;
  497. }
  498.  
  499. template <class TYPE>
  500. const HashTable<TYPE>& HashTable<TYPE>::operator=(const HashTable<TYPE>& other)
  501. {
  502.  
  503. if (this != &other)
  504. {
  505. delete [] records ;
  506. records = new Record*[other.TableSize];
  507. for(int i = 0 ; i < other.TableSize ; i++)
  508. records[i] = other.records[i] ;
  509. TableSize = other.TableSize;
  510. }
  511.  
  512.  
  513. return *this;
  514.  
  515. }
  516. template <class TYPE>
  517. const HashTable<TYPE>& HashTable<TYPE>::operator=(HashTable<TYPE>&& other)
  518. {
  519.  
  520. swap(records, other.records);
  521. swap(TableSize, other.TableSize);
  522.  
  523. return *this;
  524.  
  525. }
  526. template <class TYPE>
  527. HashTable<TYPE>::~HashTable()
  528. {
  529. if (records)
  530. {
  531. for (int i = 0; i < TableSize; i++)
  532. records[i] = nullptr;
  533. delete[] records;
  534. }
  535.  
  536. }
  537.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
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
stdout
Standard output is empty