Song repetition manager with Stack

The exercise was to take a file such as this:

You say yes
I say no
You say stop
And I say go go go
CHORUS:
Oh no
You say Goodbye
And I say hello
Hello hello
I don't know why
You say Goodbye
I say hello
#repeat 9 12
Why
#repeat 11 13
I say high
You say low
You say why
And I say I don't know
#repeat 5 19


And parse the repeats so they actually repeat the lines. Nested repeats have to work and I had to use my own stack class.

main.cpp

#include "Stack.h"
#include
#include
#include
#include

void parseLines(const std::vector text, const int begin, const int end);
void parseRepeat(const std::string repeatLine, int &begin, int &end);

int main() {
int fileLines = 0;

std::string in;
std::string fileName = "lyrics";
std::ifstream inFile(fileName.c_str());
std::vector text;

while(!inFile.eof()) {
getline(inFile, in);
text.push_back(in);
fileLines++;
}

parseLines(text, 0, fileLines);
}

void parseLines(const std::vector text, const int begin, const int end) {
Stack lyricStack;

int fromLine = begin;
int toLine = end;

while(fromLine

Stack.h

#ifndef STACK_H_
#define STACK_H_

#include

template
struct NODE {
A data;
NODE* next;
};

template
class Stack {
private:
NODE* head;

public:
Stack();
virtual ~Stack();

void push(const B item);
B pop();
bool isEmpty();
};

#endif / STACK_H_ /


Stack.cpp

#include "Stack.h"
#include

template
Stack::Stack() {
head = NULL;
}

template
Stack::~Stack() {
NODE* current = head;
NODE* previous;

while(current) {
previous = current;
current = current->next;
delete previous;
}
}

template
void Stack::push(const B item) {
NODE* newNode = new NODE;
newNode->data = item;

if(!head) {
newNode->next = NULL;
head = newNode;
} else {
newNode->next = head;
head = newNode;
}
}

template
B Stack::pop() {
NODE* next = head->n

First main problem is the code does not compile:

When you implement template classes. The compiler instantiates the templates on use. This means the compilation unit that is instantiating the class must have already seen the source for the template (if it has not then it marks it as unresolved) and then tries to resolve them at link time. In your case this does not happen.

main.cpp: Uses Stack thus needs the constructor and destructor.
          But does not have them at this point. So waits for the linker to find one.

Stack.cpp: Contains only template definition and thus does **NOT** generate any code.
           Templates only become real code when there is an instantiation
           (implicit as done by the compiler in main.cpp or explicit when you do it).
           Since there is no instantiation there is no code.

This all means that main fill fail to link.

The easiest way to solve this:

• Rename Stack.cpp to Stack.tpp

• #include "Stack.tpp" from inside "Stack.h"

The reason to rename to Stack.tpp is that some build systems will try to build all source and since this is included by a header this can cause problems with some build systems. So it is best to change the name just to avoid any future problems. tpp is often used to hold template definitions.

Never do this:

while(!inFile.eof()) {
    getline(inFile, in);
    text.push_back(in);
    fileLines++;
}

Several problems:

• If getline() fails with a real error (not EOF) you end up with an infinite loop.

• The last line read reads up to (but not past the EOF).

So you have read the last line but EOF is not set. You then re-enter the loop try to get another line, this fails and sets EOF but nothing is done with in yet you still push in onto text. So you end up pushing the last line twice.

The correct way to read from a file is:

while(getline(inFile, in))
{
    // The loop is only entered if getline() successfully reads a line.
    // Thus it solves the two problems above.

    text.push_back(in);
    fileLines++;
}

This works because getline() returns a reference to a stream. When a stream is used in a boolean context it is converted to a type that can be used as a boolean (type unspecified in C++03 but bool in C++11). It is converted by checking the fail() flag. If this is true the conversion returns an object equivalent to false otherwise an object equivalent to true.

When passing big objects as parameters consider passing them by reference. If they are never modified pass by const reference. If you don't the compiler is going to generate a copy.

void parseLines(const std::vector text, const int begin, const int end) {

Here you should probably pass text by const reference.

void parseLines(const std::vector const& text, const int begin, const int end) {
//                                            ^^^^^^^^

Same thing here:

void parseRepeat(const std::string repeatLine, int &begin, int &end) {
// Should probably be
void parseRepeat(const std::string& repeatLine, int &begin, int &end) {
//                               ^^^

Casting is nearly always a sign that something is wrong with your design:

(unsigned int)fromLine

This should be a hint that fromLine is the wrong type. Since it is measuring a size and will never by less than 0 this is an indication that the correct type for the type is unsigned int (or probably size_t).

void parseLines(const std::vector text, std::size_t const begin, std::size_t const end) {
    Stack lyricStack;

    std::size_t fromLine = begin;
    std::size_t toLine   = end;

    while(fromLine <= toLine && fromLine < text.size()) {

atoi() is fast but non standard and not always available. An easier way is to just use the stream operators. This will always work and 99% of the time will be sufficiently fast. Only optimize out when you know it makes a difference.

Also this code is so dense it is nearly unreadable. White space is your friend.

void parseRepeat(const std::string repeatLine, int &begin, int &end)
{
    std::string numbers = repeatLine.substr(repeatLine.find(" ") + 1);
    begin = atoi((numbers.substr(0, numbers.find(" "))).c_str()) - 1;
    end = atoi((numbers.substr(numbers.find(" "))).c_str()) - 1;
}

Much easier to write with streams:

void parseRepeat(const std::string repeatLine, int &begin, int &end)
{
    // This line always has the form 
    // #repeat  
    std::stringstream   linestream(repeatLine);
    std::string         repeat;

    linestream >> repeat >> begin >> end;
}

Both NODE and Stack contain RAW pointers. Yet they do not obey the rule of three. This is very dangerous. The simple rule is your classes should never contain RAW pointers (all pointers should be wrapped in smart pointers) unless you are writing a smart pointer or container.

In this situation NODE would be easy to implement using smart pointer.

Also you do a work handling node inside stack. It simplifies the design if y

StackExchange Code Review Q#6224, answer score: 12