I am trying to implement a suffix trie in C++ for a programming assignment. Now I think I have the right idea, but I keep getting a segmentation fault and I haven't been able to find what's causing it.
For this assignment, we are encouraged to use VIM/some other basic text editor, and compile programs from the console. Nevertheless, I've downloaded CLion to try and debug the code so I can find the error.
Now when running in CLion I get the message
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Trying to run the debugger gives the message
Error during pretty printers setup:
Undefined info command: "pretty-printer". Try "help info".
Some features and performance optimizations will not be available.
I'm new to CLion and I'm not sure what to do about this (The only JetBrains IDE I use is Pycharm). Can you help me resolve this?
Now the program itself consists of three classes, Trie, Edge and Node, whose implementations can be seen below. The main idea behind the implementation of the Trie is in the constructor of Trie.cpp.
The code is detailed in full below. I appreciate any help.
Main.cpp
#include <iostream>
using namespace std;
#include "Trie.hpp"
int main(){
string s = "Stef";
Trie trie(s);
return 0;
}
Trie.hpp
#ifndef TRIE_HPP
#define TRIE_HPP
#include <string>
#include "Node.hpp"
#include "Edge.hpp"
using namespace std;
class Trie{
private:
string T;
vector<Node> nodes;
void addWord(Node*, string);
public:
Trie(string);
};
#endif
Trie.cpp
#include <iostream>
#include <cstring>
#include "Trie.hpp"
using namespace std;
Trie::Trie(string T){
T += "#"; //terminating character
this->T = T;
vector<string> suffix; //array of suffixes
for(unsigned int i = 0; i < T.length(); i++)
suffix.push_back(T.substr(i, T.length()-i));
//Create the Root, and start from it
nodes.push_back(Node("")); //root has blank label
Node* currentNode = &nodes[0];
//While there are words in the array of suffixes
while(!suffix.empty()){
//If the character under consideration already has an edge, then this will be its index. Otherwise, it's -1.
int edgeIndex = currentNode->childLoc(suffix[0].at(0));
//If there is no such edge, add the rest of the word
if(edgeIndex == -1){
addWord(currentNode, suffix[0]); //add rest of word
suffix.erase(suffix.begin()); //erase the suffix from the suffix array
break; //break from the for loop
}
//if there is
else{
currentNode = (currentNode->getEdge(edgeIndex))->getTo(); //current Node is the next Node
suffix[0] = suffix[0].substr(1, suffix[0].length()); //remove first character
}
}
}
//This function adds the rest of a word
void Trie::addWord(Node* parent, string word){
for(unsigned int i = 0; i < word.length(); i++){ //For each remaining letter
nodes.push_back(Node(parent->getLabel()+word.at(i))); //Add a node with label of parent + label of edge
Edge e(word.at(i), parent, &nodes.back()); //Create an edge joining the parent to the node we just added
parent->addEdge(e); //Join the two with this edge
}
}
Node.hpp
#ifndef NODE_HPP
#define NODE_HPP
#include <string>
#include <vector>
#include "Edge.hpp"
using namespace std;
class Node{
private:
string label;
vector<Edge> outgoing_edges;
public:
Node();
Node(string);
string getLabel();
int childLoc(char);
void addEdge(Edge);
Edge* getEdge(int);
};
#endif
Node.cpp
#include "Node.hpp"
using namespace std;
Node::Node(){
}
Node::Node(string label){
this->label = label;
}
string Node::getLabel(){
return label;
}
//This function returns the edge matching the given label, returning -1 if there is no such edge.
int Node::childLoc(char label){
int loc = -1;
for(unsigned int i = 0; i < outgoing_edges.size(); i++)
if(outgoing_edges[i].getLabel() == label)
loc = i;
return loc;
}
void Node::addEdge(Edge e){
outgoing_edges.push_back(e);
}
Edge* Node::getEdge(int n){
return &outgoing_edges[n];
}
Edge.hpp
#ifndef EDGE_HPP
#define EDGE_HPP
#include <string>
using namespace std;
class Node; //Forward definition
class Edge{
private:
char label;
Node* from;
Node* to;
public:
Edge(char, Node*, Node*);
char getLabel();
Node* getTo();
Node* getFrom();
};
#endif
Edge.cpp
#include "Edge.hpp"
using namespace std;
Edge::Edge(char label, Node* from, Node* to){
this->label = label;
this->from = from;
this->to = to;
}
char Edge::getLabel(){
return label;
}
Node* Edge::getFrom(){
return from;
}
Node* Edge::getTo(){
return to;
}
