// Student name :
// Student ID :
// Submission deadline : Sunday, 8 Oct 2017, 11pm
// Upload your .cpp file via Canvas
// Late submission or submission by other means will not be graded
/*
In this tutorial, we shall use the string class in C++.
The string class in C++ offers a lot more functionality than cstring.
You can compare 2 string objects using the relational operators.
For example,
string s1, s2;
...
if (s1 == s2)
...
if (s1 < s2)
...
You can use the subscript operator [] to access the char at a given index.
For example,
if (s1[i] == ',') // test if char at index i is equal to ','
You can use substr(start, end) to get the substring from index start to end-1
For example,
string sub = s1.substr(0, i); // get the substring from 0 to i-1
You can find the length of the string using the function length().
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include<algorithm>
using namespace std;
struct telRec {
string name;
string tel;
};
struct chatGroup {
string groupName;
string *member; // array of string storing the tel no. of group members
int size;
};
const string NotFound = "not found";
void readTelList(const string& filename, telRec*& telList, int& n)
{
// File format :
// Number of records is given on the first line.
// Each telephone record is stored in 1 line (starting from 2nd line).
// Name is delimited by comma ',' followed by a space char, and then the telephone number.
// Telephone records in the file are ordered by telephone number.
// Read in the data from the file.
// Create the array telList, and set the value of n (number of telRec)
ifstream infile(filename);
if (!infile.is_open())
{
cout << "Error: cannot open data file : " << filename << endl;
system("pause");
exit(0);
}
string temp;
infile >> temp >> n;
telList = new telRec[n];
// Use getline() to read in one line of text from the file.
// The C++ function getline() is similar to Scanner.nextLine() in Java.
string line;
getline(infile, line); // consume the '
' after the value of n
// Your codes
int k = 0;
while (getline(infile, line))
{
string name = "";
string tel = "";
int loc = 0;
for (int i = 0; i < line.length(); i++){
if (line[i] == ','){
loc = i;
break;
}
}
if (loc == 0) continue;
name = line.substr(0, loc);
tel = line.substr(loc + 2, line.length());
telList[k].name = name;
telList[k].tel = tel;
k++;
}
infile.close(); // close the file after use
}
void readChatGroup(const string& filename, chatGroup*& groupList, int& g)
{
// File format :
// Number of chat groups is given on the first line.
// Each group contains:
// group_name size
// telephone numbers of the members in the chat group (not ordered)
// Chat groups in the file are ordered by group name.
// Read in the data from the file.
// Create the array groupList, and set the value of g (number of groups)
ifstream infile(filename);
if (!infile.is_open())
{
cout << "Error: cannot open data file : " << filename << endl;
system("pause");
exit(0);
}
// Your codes
string temp;
infile >> temp >> g;
groupList = new chatGroup[g];
// Use getline() to read in one line of text from the file.
// The C++ function getline() is similar to Scanner.nextLine() in Java.
string line;
getline(infile, line); // consume the '
' after the value of n
//cout << line << endl;
int k = -1;
int j = 0;
while (getline(infile, line))
{
if (line.length() == 0)
continue;
istringstream is(line);
if (line.find(' ', 0) == string::npos){
is >> groupList[k].member[j++];
}else{
k++;
is >> groupList[k].groupName >> groupList[k].size;
groupList[k].member = new string[groupList[k].size];
j = 0;
}
}
infile.close();
}
const string& getNameByTel(const telRec *telList, int n, const string& tel)
{
// Return the name (by reference) that is associated with the given tel number
// If the input tel is not found,
// return Notfound (the const string defined at the top of the file).
// The returned string object is a const, i.e. the calling function cannot modify
// the returned string object.
// Use binary search to find the telRec
// Your codes
// (a) copy data
telRec* tmpTelList = new telRec[n];
for (int i = 0; i < n; i++){
tmpTelList[i] = telList[i];
}
// (b) sort
telRec tmp;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (tmpTelList[i].tel > tmpTelList[j].tel){
tmp = tmpTelList[i];
tmpTelList[i] = tmpTelList[j];
tmpTelList[j] = tmp;
}
}
}
// (c) binary search
int left = 0;
int right = n;
int mid = 0;
while (1){
if (left > right)
break;
mid = (left + right) / 2;
if (tmpTelList[mid].tel == tel)
return tmpTelList[mid].name;
if (tmpTelList[mid].tel > tel)
right = mid-1;
if (tmpTelList[mid].tel < tel)
left = mid + 1;
}
return NotFound;
}
void printChatGroupByName(const chatGroup *groupList, int g, string gname, const telRec *telList, int n)
{
// Print the chat group to the standard output.
// If the chat group is found, format of the output:
// Chat group : group_name
// Number of members :
// name, tel (one line per member)
// If the chat group is not found, format of the output:
// Chat group : group_name not found
// Use binary search to find the group
// Your codes
// (a) copy data
chatGroup* tmpGroupList = new chatGroup[g];
for (int i = 0; i < g; i++){
tmpGroupList[i] = groupList[i];
}
// (b) sort
chatGroup tmp;
for (int i = 0; i < g; i++){
for (int j = i + 1; j < g; j++){
if (tmpGroupList[i].groupName > tmpGroupList[j].groupName){
tmp = tmpGroupList[i];
tmpGroupList[i] = tmpGroupList[j];
tmpGroupList[j] = tmp;
}
}
}
// (c) binary search
int left = 0;
int right = g;
int mid = 0;
while (1){
if (left > right)
break;
mid = (left + right) / 2;
if (tmpGroupList[mid].groupName == gname)
break;
if (tmpGroupList[mid].groupName > gname)
right = mid - 1;
if (tmpGroupList[mid].groupName < gname)
left = mid + 1;
}
// (d) not finded
if (left > right){
cout << "Chat group : " + gname + " not found" << endl;
return;
}
// (e) finded
char chTmp[512];
sprintf(chTmp, "%d", tmpGroupList[mid].size);
string strSize = chTmp;
cout << "Chat group : " + tmpGroupList[mid].groupName << endl;
cout << "Number of members : " + strSize << endl;
for (int i = 0; i < tmpGroupList[mid].size; i++){
cout << getNameByTel(telList, n, tmpGroupList[mid].member[i]) + ", " + tmpGroupList[mid].member[i] << endl;
}
}
int main()
{
telRec *telList;
int n; // number of tel records
chatGroup *groupList;
int g; // number of chat groups
string file1 = "tel-name.txt"; // sorted by telephone number
string file2 = "chat-groups.txt"; // sorted by group name, tel no. within a group are not sorted
readTelList(file1, telList, n);
string t1 = "91765295";
cout << "Owner of tel. no. " << t1 << " is " << getNameByTel(telList, n, t1) << endl << endl;
// Expected output
// Owner of tel. no. 91765295 is WONG Kin Ho
string t2 = "90001111";
cout << "Owner of tel. no. " << t2 << " is " << getNameByTel(telList, n, t2) << endl << endl;;
// Expected output
// Owner of tel. no. 90001111 is not found
readChatGroup(file2, groupList, g);
string gname = "group-04";
printChatGroupByName(groupList, g, gname, telList, n);
// Expected output
// Chat group : group-04
// Number of members : 7
// CHAN Wai Hang, 98512078
// LUI Ka Fai, 98529423
// TSE Tsz Hin, 95871616
// SIU Ka Hin, 92432172
// LOK Kam Hung, 93670697
// WAN Tsun Man, 97039667
// CHAN Man Hong, 92026350
gname = "group-03";
printChatGroupByName(groupList, g, gname, telList, n);
// Expected output
// Chat group : group-03 not found
system("pause");
exit(0);
}