Repository navigation
Expand file tree
/
Copy pathdbLib.cpp
More file actions
235 lines (218 loc) · 6.6 KB
/
Copy pathdbLib.cpp
File metadata and controls
235 lines (218 loc) · 6.6 KB
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
/*
* =========================================================================================
* Name : dbLib.cpp
* Author : Duc Dung Nguyen
* Email : nddung@hcmut.edu.vn
* Copyright : Faculty of Computer Science and Engineering - Bach Khoa University
* Description : library for Assignment 2 - Data structures and Algorithms - Fall 2017
* This file implements functions used for database management
* =========================================================================================
*/
#include "dbLib.h"
#include <time.h>
#include <fstream>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>
#define __PI 3.14159265358979323846
#define earthRadiusKm 6371.0
using namespace std;
void strPrintTime(char* des, time_t& t) {
tm *pTime = gmtime(&t);
strftime(des, 26, "%Y-%m-%d %H:%M:%S", pTime);
}
AVL_AVL dbAVLTree;
// assuming newNode is an external node
template<>
void AVLTree< AVLTree<VM_Record, time_t>, string>::insert(TreeNode<VM_Record, time_t> *newNode, VM_Record *d)
{
string str{ (d->id) };
Node_AVL_str **pTmp{ &root };
//TreeNode< AVLTree<VM_Record, time_t>, string > **p1{ &root };
GData *pGtmp;
L1List< TreeNode<AVLTree<VM_Record, time_t>, string>** > lPath;
while (*pTmp)
{
if (str == *((*pTmp)->key)) // there exists a avl child with the same key
{
pGtmp = static_cast<GData*>((*pTmp)->data->pGData);
if (d->longitude < pGtmp->minLong) // find minLong
{
pGtmp->minLong = d->longitude;
}
else
{
if (d->longitude > pGtmp->maxLong) // find maxLong
pGtmp->maxLong = d->longitude;
}
if (d->latitude < pGtmp->minLat) // find minLat
{
pGtmp->minLat = d->latitude;
}
else
{
if (d->latitude > pGtmp->maxLat) // find maxLat
pGtmp->maxLat = d->latitude;
}
(*pTmp)->data->insert(newNode);
return;
}
else
{
lPath.insertHead(pTmp);
if (str < *((*pTmp)->key))
{
pTmp = &((*pTmp)->left);
}
else // str > *(pTmp->key)
{
pTmp = &((*pTmp)->right);
}
}
}
// create new Node_AVL_str
AVL_VmR_Time *p{ new AVL_VmR_Time() };
p->pGData = new GData(d->longitude, d->longitude, d->latitude, d->latitude);
p->insert(newNode);
*pTmp = new Node_AVL_str(p, &(d->id));
size++;
// fix balanced
L1Item< Node_AVL_str ** > *pt{ lPath.getHead() };
int tmpH;
while (pt) // null when *pTmp == root or all item in lPath have been removed
{
pTmp = pt->data;
tmpH = (*pTmp)->getHeight();
(*pTmp)->updateH();
keepBalanced(*pTmp);
if ((*pTmp)->getHeight() == tmpH) return; // check if it needs to fix balanced
lPath.removeHead();
pt = lPath.getHead();
}
}
template<>
void AVL_AVL::insert(VM_Record *d)
{
//TreeNode<VM_Record, time_t> *newNode{ new TreeNode<VM_Record, time_t>(d, &(d->timestamp)) };
insert(new TreeNode<VM_Record, time_t>(d, &(d->timestamp)), d);
}
void loadVMDB(char* fName, L1List<VM_Record> &db) {
//ifstream inFile(fName);
ifstream dbFile(fName);
//if (inFile) {
// string line;
// getline(inFile , line);// skip the first line
// VM_Record record;
// db.insertHead(record);/// add dummy object
// while (getline(inFile , line)) {
// /// On Windows, lines on file ends with \r\n. So you have to remove \r
// if (line[line.length() - 1] == '\r')
// line.erase(line.length() - 1);
// if (line.length() > 0) {
// if (parseVMRecord((char*)line.data(), db[0]))/// parse and store data directly
// db.insertHead(record);/// add dummy object for next turn
// }
// }
// db.removeHead();/// remove the first dummy
// db.reverse();
// inFile.close();
//}
//else {
// cout << "The file is not found!";
//}
if (!dbFile)
{
db.clean();
cerr << "\nCannot open the database file for reading!\n";
return;
}
else
{
stringstream buf;
string str;
tm t;
//int in;
VM_Record n;
getline(dbFile, str); // discard the first line
while (!dbFile.eof())
{
getline(dbFile, str, ','); // discard the 1st item on each line
// handle time data
if (!str.empty() && (str.back() > ' ')) //
{
getline(dbFile, str, ' '); // "day/mon/year"
getline(dbFile, str, ',');
buf << str;
buf >> t.tm_hour;
buf.ignore(); // discard ':'
buf >> t.tm_min;
buf.ignore(); // discard ':'
buf >> t.tm_sec;
t.tm_mday = 7; t.tm_mon = 6; t.tm_year = 70;
//buf >> get_time(&t, "%m/%d/%Y %H:%M:%S");
n.timestamp = mktime(&t); // convert from tm to time_t
buf.str("");
buf.clear();
// handle vehicle id
getline(dbFile, str, ','); // vehicle tag
n.id = str;
// handle longitude
getline(dbFile, str, ','); // Longitude
n.longitude = stod(str);
// handle latitude
getline(dbFile, str, ','); // Latitude
n.latitude = stod(str);
getline(dbFile, str); // read the rest of the line
db.push_back(n);
dbAVLTree.insert(&(db.getTail()->data));
}
}
dbFile.close();
}
return;
}
bool parseVMRecord(char *pBuf, VM_Record &bInfo) {
// TODO: write code to parse a record from given line
return 1;
}
void process(L1List<VM_Request>& requestList, L1List<VM_Record>& rList) {
void* pGData = NULL;
initVMGlobalData(&pGData);
while (!requestList.isEmpty()) {
if(!processRequest(requestList[0], rList, pGData))
cout << requestList[0].code << " is an invalid event\n";
requestList.removeHead();
}
releaseVMGlobalData(pGData);
}
void printVMRecord(VM_Record &b) {
// printf("%s: (%0.5f, %0.5f), %s\n", b.id, b.longitude, b.latitude, ctime(&b.timestamp));
}
/// This function converts decimal degrees to radians
inline double deg2rad(double deg) {
return (deg * __PI / 180);
}
/// This function converts radians to decimal degrees
inline double rad2deg(double rad) {
return (rad * 180 / __PI);
}
/**
* Returns the distance between two points on the Earth.
* Direct translation from http://en.wikipedia.org/wiki/Haversine_formula
* @param lat1d Latitude of the first point in degrees
* @param lon1d Longitude of the first point in degrees
* @param lat2d Latitude of the second point in degrees
* @param lon2d Longitude of the second point in degrees
* @return The distance between the two points in kilometers
*/
double distanceEarth(double lon1d, double lat1d, double lon2d, double lat2d) {
double lat1r, lon1r, lat2r, lon2r, u, v;
lat1r = deg2rad(lat1d);
lon1r = deg2rad(lon1d);
lat2r = deg2rad(lat2d);
lon2r = deg2rad(lon2d);
u = sin((lat2r - lat1r)/2);
v = sin((lon2r - lon1r)/2);
return 2.0 * earthRadiusKm * asin(sqrt(u * u + cos(lat1r) * cos(lat2r) * v * v));
}