-
Notifications
You must be signed in to change notification settings - Fork 0
/
Search.cpp
162 lines (123 loc) · 5.36 KB
/
Search.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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;
bool isLeapYear(int year);
int getDaysInMonth(int month, int year);
int daysBetweenDate(int startDay, int startMonth, int startYear, int endDay, int endMonth, int endYear);
void binarySearch(vector<int>& day, vector<int>& month, vector<int>& year, vector<long>& value, vector<long long>& cumulative, int start, int finish, int searchday, int searchmonth, int searchyear);
void interpolationSearch(vector<int>& day, vector<int>& month, vector<int>& year, vector<long>& value, vector<long long>& cumulative, int start, int finish, int searchday, int searchmonth, int searchyear);
int main(){
ifstream file("file.csv");
if (!file.is_open()){
cout<<"Error opening file"<<endl;
return 1;
}
int records=0, i=0;
vector<int> day, month, year;
vector<long> value;
vector<long long> cumulative;
string searchDate;
string line;
while(getline(file, line)){
vector<string> row;
stringstream ss(line);
string cell;
while (getline(ss, cell, ','))
row.push_back(cell);
stringstream ss1(row[2]);
string dayStr, monthStr, yearStr;
getline(ss1, dayStr, '/');
getline(ss1, monthStr, '/');
getline(ss1, yearStr, '/');
day.push_back(stoi(dayStr));
month.push_back(stoi(monthStr));
year.push_back(stoi(yearStr));
value.push_back(stol(row[8]));
cumulative.push_back(stoll(row[9]));
records ++;
}
cout<<"Input date in format dd/mm/yyyy:"<<endl;
cin>>searchDate;
stringstream ss(searchDate);
string dayStr, monthStr, yearStr;
getline(ss, dayStr, '/');
getline(ss, monthStr, '/');
getline(ss, yearStr, '/');
//Letting the user choose between binary search and interpolation search
int choice;
do{
cout<<"Press 1 to use Binary Search or press 2 to use Interpolation Search"<<endl<<"in order to find out the value and the cumulative of a record with the above date:"<<endl;
cin>>choice;
} while(choice!=1 && choice!=2);
if(choice==1)
binarySearch(day, month, year, value, cumulative, 0, records-1, stoi(dayStr), stoi(monthStr), stoi(yearStr));
else
interpolationSearch(day, month, year, value, cumulative, 0, records-1, stoi(dayStr), stoi(monthStr), stoi(yearStr));
if(choice==1)
cout<<endl<<endl<<"Binary Search was executed successfully";
else
cout<<endl<<endl<<"Interpolation Search was executed successfully";
return 0;
}
bool isLeapYear(int year){
return(year%4==0 && year%100!=0) || (year%400==0);
}
int getDaysInMonth(int month, int year){
if (month==2)
return isLeapYear(year)?29:28;
else if (month==4 || month==6 || month==9 || month==11)
return 30;
else
return 31;
}
int daysBetweenDate(int startDay, int startMonth, int startYear, int endDay, int endMonth, int endYear){
int days=0;
for(int year=0; year<startYear; year++)
days-=isLeapYear(year)?366:365;
for(int month=1; month<startMonth; month++)
days-=getDaysInMonth(month, endYear);
days-=startDay;
for(int year=0; year<endYear; year++)
days+=isLeapYear(year)?366:365;
for(int month=1; month<endMonth; month++)
days += getDaysInMonth(month, endYear);
days+=endDay;
int daysBetween=days;
return daysBetween;
}
void binarySearch(vector<int>& day, vector<int>& month, vector<int>& year, vector<long>& value, vector<long long>& cumulative, int start, int finish, int searchday, int searchmonth, int searchyear){
int low=start, high=finish, mid;
do{
mid=low+(high-low)/2;
if(year[mid]==searchyear && month[mid]==searchmonth && day[mid]==searchday){
cout<<"Value: "<<value[mid]<<", Cumulative: "<<cumulative[mid]<<endl;
break;
}
else{
if(year[mid]<searchyear || (year[mid]==searchyear && month[mid]<searchmonth) || (year[mid]==searchyear && month[mid]==searchmonth && day[mid]<searchday))
low=mid+1; //search the right half
else
high=mid-1; //search the left half
}
}while(low<=high);
}
void interpolationSearch(vector<int>& day, vector<int>& month, vector<int>& year, vector<long>& value, vector<long long>& cumulative, int start, int finish, int searchday, int searchmonth, int searchyear){
int lo=start, hi=finish, mid;
do{
//Calculate the interpolated mid-point
mid=lo+(((hi-lo)/(daysBetweenDate(day[lo], month[lo], year[lo], day[hi], month[hi], year[hi]))) * (daysBetweenDate(day[lo], month[lo], year[lo], searchday, searchmonth, searchyear)));
if(year[mid]==searchyear && month[mid]==searchmonth && day[mid]==searchday){
cout<<"Value: "<<value[mid]<<", Cumulative: "<<cumulative[mid]<<endl;
break;
}
else{
if(year[mid]<searchyear || (year[mid]==searchyear && month[mid]<searchmonth) || (year[mid]==searchyear && month[mid]==searchmonth && day[mid]<searchday))
lo=mid+1; //search the right part
else
hi=mid-1; //search the left part
}
}while(lo<=hi);
}