-
Notifications
You must be signed in to change notification settings - Fork 0
/
bsearch-dictionary.cpp
executable file
·130 lines (115 loc) · 3.52 KB
/
bsearch-dictionary.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// Implementation of a dictionary using an array and binary search
// It will inherit from the ArrayDictionary
#include <stdlib.h>
#include <string>
#include <list>
#include <iostream>
#include <vector>
#include "bsearch-dictionary.h"
using std::list;
using std::cout;
using std::endl;
// Constructor
BinarySearchDictionary::BinarySearchDictionary()
{
// Add needed code
}
// Find a key in the dictionary and return corresponding record or NULL
DataType
BinarySearchDictionary::findRecord( KeyType key)
{
// Ue binary search
// Add needed code
sort();
for(vector<dictionaryEntry>::iterator sItr = dictionaryArray.begin(); sItr != dictionaryArray.end(); sItr++){
cout<<(*sItr)._key<<endl;
}
int left = 0;
int right = dictionaryArray.size() - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(dictionaryArray[mid]._key.compare(key) < 0){
left = mid + 1;
}
else if(!dictionaryArray[mid]._key.compare(key)){
return dictionaryArray[mid]._data;
}
else{
right = mid - 1;
}
}
return NULL;
}
// Sort array using heap sort.
void
BinarySearchDictionary::sort()
{
// Add needed code
vector<dictionaryEntry> heapArray;
heapArray.clear();
for(vector<dictionaryEntry>::iterator itr = dictionaryArray.begin(); itr != dictionaryArray.end(); itr++){
heapArray.push_back((*itr));
upHeap(&heapArray);
}
dictionaryArray.clear();
vector<dictionaryEntry>::iterator itrR = heapArray.begin();
//Problem is here; after removing the first element (which is the min) need to take the last element in the vector and place it at the front
while(itrR != heapArray.end()){
dictionaryArray.push_back((*itrR));
dictionaryEntry endEntry = heapArray.back();
heapArray.front() = endEntry;
heapArray.pop_back();
itrR = heapArray.begin();
downHeap(&heapArray);
}
}
void
BinarySearchDictionary::upHeap(vector<dictionaryEntry> * array){
int upHeapIndex = array->size() - 1;
int parent = getParent(upHeapIndex);
while(parent >= 0 && (array->at(upHeapIndex))._key.compare( array->at(parent)._key) < 0){
dictionaryEntry temp = array->at(upHeapIndex);
array->at(upHeapIndex) = array->at(parent);
array->at(parent) = temp;
upHeapIndex = parent;
parent = getParent(upHeapIndex);
}
}
void
BinarySearchDictionary::downHeap(vector<dictionaryEntry> * array){
int downHeapIndex = 0;
int lChild = getLChild(downHeapIndex);
int rChild = getRChild(downHeapIndex);
int smallerIndex;
while(lChild < array->size()){
if(rChild < array->size() && (array->at(rChild))._key.compare((array->at(lChild))._key) < 0){
smallerIndex = rChild;
}
else{
smallerIndex = lChild;
}
if((array->at(downHeapIndex))._key.compare((array->at(smallerIndex))._key) < 0){
break;
}
else{
dictionaryEntry temp = array->at(downHeapIndex);
(*array)[downHeapIndex] = array->at(smallerIndex);
(*array)[smallerIndex] = temp;
downHeapIndex = smallerIndex;
lChild = getLChild(downHeapIndex);
rChild = getRChild(downHeapIndex);
}
}
}
int
BinarySearchDictionary::getLChild(int parent){
return 2*parent + 1;
}
int
BinarySearchDictionary::getRChild(int parent){
return 2*parent + 2;
}
int
BinarySearchDictionary::getParent(int child){
return (child - 1) / 2;
}