-
Notifications
You must be signed in to change notification settings - Fork 0
/
string_set.cpp
142 lines (118 loc) · 3.48 KB
/
string_set.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
#include <cmath>
#include <algorithm>
#include <locale>
#include <iostream>
#include <sstream>
#include <ostream>
#include "string_set.hpp"
/* list<std::string>* table; //array of pointers to lists of strings
int size; //the current number of lists in the table array*/
string_set::string_set(int n) : size(n), table(new listptr[n])
{
std::list<std::string> *test;
for (int i = 0; i <= n; i++) {
test = new std::list<std::string>;
table[i] = test;
//std::cout << table[i]->empty() << std::endl;
}
}
string_set::~string_set()
{
//std::cout << hash("conventional") << "\t" << hash("mental") << "\t" << hash("strangers") << "\t" << hash("walked") << std::endl;
//std::cout << (hash("conventional") == hash("mental"));
//std::cout << "destructing" << std::endl;
for(int i =0; i <= size; i++)
{
delete table[i];
}
size = 0;
}
// should add the given string to the string_set if it is not already present.
// The boolean returned should indicate whether the string_set was modified.
// void insert ( iterator position, size_type n, const T& x );
bool string_set::insert(std::string s)
{
//std::cout << "Inserting: " << s << " hash is: " << hash(s) << std::endl;
int new_str = hash(s);
std::list<std::string>* curr = table[new_str];
std::list<std::string> ans;
ans.push_front(s);
if(member(s) == true)
return false; // It was already in the table
if(curr == NULL) // Need to be careful with null pointers
{
*curr = ans;
return true;
}
// Special cases gone
curr->insert(curr->end(), 1, s);
return true; // Inserted worked.
}
// should remove the given string from the string_set if it is present.
// The boolean returned should indicate whether the string_set was modified.
bool string_set::remove(std::string s)
{
//std::cout << (hash("Jameson") == hash("part")) << "\t";
//std::cout << member("Jameson") << std::endl;
if(member(s) == false)
{
return false;
}
// Special cases gone
int new_str = hash(s);
for(std::list<std::string>::iterator front(table[new_str]->begin()); front != table[new_str]->end(); ++front)
{
//std::cout << "Got here to delete";
if(s == *front)
{
table[new_str]->erase(front);
//std::cout << "Got here to delete";
return true; // Just erased it from the list
}
}
//std::cout << "Got here to delete";
return false; // Went through the list, fixed.
}
//should return a boolean indicating whether the given string is present in the string_set.
bool string_set::member(std::string s)
{
int new_str = hash(s);
// That's the special case...
for(std::list<std::string>::iterator front(table[new_str]->begin());
front != table[new_str]->end(); ++front)
{
if(s == *front)
//std::cout << *front << "\n";
return true;
}
return false;
}
// in no particular order concatenated together, each followed by a newline.
// The empty set should produce just a newline.
string_set::operator std::string()
{
std::stringstream prnt;
if(table == NULL)
return "\n";
for(int i = 0; i <= size; ++i)
{
if(not table[i]->empty())
{
for(std::list<std::string>::iterator front(table[i]->begin()); front != table[i]->end(); ++front)
prnt << *front << " ";
prnt << "\n";
}
}
return prnt.str();
}
//Use the STL hash function...
int string_set::hash(std::string s)
{
using namespace std;
string test = s;
std::locale loc; // the "C" locale
const collate<char>& coll = use_facet<collate<char> >(loc);
int ans = coll.hash(test.data(),test.data()+test.length());
ans = ans%size;
return abs(ans);
}