Wrote my own list and graph. Have much troubles with it and don't understand how to fix. Here's the code:
template<typename T>
class List {
public:
List() {
Size = 0;
head = nullptr;
tale = nullptr;
}
T& operator[](int index) {
Node* current = head;
int counter = 0;
while (current->pNext != nullptr) {
if (counter == index) {
break;
}
current = current->pNext;
counter++;
}
return current->data;
}
void push_back(const T& data) {
if (head == nullptr) {
head = new Node;
head->data = data;
head->pPrev = nullptr;
head->pNext = nullptr;
tale = head;
}
else {
Node* newNode = new Node;
newNode->data = data;
newNode->pPrev = tale;
newNode->pNext = nullptr;
tale->pNext = newNode;
tale = newNode;
//delete newNode;
}
Size++;
}
void push_front(const T& data) {
if (head == nullptr) {
head = new Node;
head->data = data;
head->pPrev = nullptr;
head->pNext = nullptr;
tale = head;
}
else {
Node* newNode = new Node;
newNode->data = data;
newNode->pPrev = nullptr;
newNode->pNext = head;
head->pPrev = newNode;
head = newNode;
// delete newNode;
}
Size++;
}
int size() {
return Size;
}
bool empty() const {
return (head == nullptr && tale == nullptr);
}
T top() {
return tale->data;
}
T& pop_back() {
if (Size == 1) {
Size = 0;
T x = head->data;
delete head;
head = tale = nullptr;
return x;
}
else {
Node* tempo = tale;
T x = tempo->data;
tale = tempo->pPrev;
tale->pNext = nullptr;
delete tempo;
Size--;
return x;
}
}
T& pop_front() {
if (Size == 1) {
Size = 0;
T x = head->data;
delete head;
head = tale = nullptr;
return x;
}
else {
Node* tempo = head;
head = tempo->pNext;
tale->pPrev = nullptr;
T x = tempo->data;
delete tempo;
Size--;
return x;
}
}
/*void print() {
Node* current = this->head;
while (current != nullptr) {
cout << current->data << ' ';
current = current->pNext;
}
}*/
void clear() {
while (Size!=0) {
pop_back();
}
// head = nullptr;
// tale = nullptr;
}
private:
struct Node {
T data;
Node* pNext{};
Node* pPrev{};
};
int Size;
Node* head;
Node* tale;
};
struct Edge {
int destination;
int weight;
Edge() {}
Edge(int d, int w) {
this->destination = d;
this->weight = w;
}
int getDestination() {
return destination;
}
};
struct Vertex {
int id;
List<Edge> edgeList;
Vertex() {
id = 0;
}
Vertex(int id) {
this->id = id;
}
int getId() {
return id;
}
};
class Graph {
public:
void print() {
for (int i = 0; i != vertices.size(); i++) {
Vertex* temp = &vertices[i];
std::cout << "(" << temp->id << ") --> ";
for (int j = 0; j != temp->edgeList.size(); j++) {
std::cout << "(" << temp->edgeList[j].destination << ")";
}
std::cout << std::endl;
}
}
void addVertex(Vertex v) {
for (int i = 0; i != vertices.size(); i++) {
if (vertices[i].getId() == v.getId()) return;
}
vertices.push_back(v);
}
void addEdges(int id1, int id2, int weight = 0) {
for (int i = 0; i != vertices.size(); i++) {
if(vertices[i].getId() == id1) {
Edge e(id2, weight);
vertices[i].edgeList.push_back(e);
}
}
}
void dfs(int start, int end) {
path.push_back(start);
Vertex* current = &vertices[start - 1];
if (start == end) {
allPath.push_back(path);
path.pop_back();
return;
}
else {
for (int i = 0; i != current->edgeList.size(); i++) {
dfs(current->edgeList[i].destination, end);
}
}
path.pop_back();
}
List<List<int>> returnPath() const {
return allPath;
}
List<List<int>> bfs(int start, int end) {
List<int> bfspath;
List<List<int>> result;
List<List<int>> queue;
bfspath.push_back(start);
queue.push_front(bfspath);
while (!queue.empty()) {
bfspath = queue.pop_front();
int lastNode = bfspath[bfspath.size()-1];
if (lastNode == end) {
result.push_back(bfspath);
//queue.pop_front();
}
else {
Vertex* current = &vertices[lastNode - 1];
List<Edge> neighbors = current->edgeList;
for (int neighbor = 0; neighbor != neighbors.size(); neighbor++){
List<int> t = bfspath;
t.push_back(neighbors[neighbor].destination);
queue.push_front(t);
//bfspath.pop_back();
}
// delete &neighbors;
}
}
return result;
}
private:
List<int> path;
List<List<int>> allPath;
List<Vertex> vertices;
};
I have to print all paths from one vertex to another, so i write dfs and bfs. dfs() works only if i use STL library. But wneh i use my own list, it returns another data. Maybe its the problem with returned data in operator[]. in bfs() when t is changed, it also changes in queue. For example: i need [[1,2,5],[1,2,10]], but queue actually is [[1,2,10],[1,2,10]], so my bfs just print the shortest path to the direction twice.
When i work with primitive types (int, float, etc), all works correctly. But when there is list of lists, it's always have much troubles and i don`t understand why.
Thanks for replying
