Sorted Linked List.

SortedList.cpp

template <class T>
class SortedList
{
public:
    SortedList():m_head(nullptr),size(0)
    {}

    void Push(T value);
    T Pop();
    int Size();
    bool Find(T value);
    bool Remove(T value);

private:
    class Node
    {
    public:
        Node(T value_, Node* next_)
        {
            value = value_;
            next = next_;
        }

        T value;
        Node* next;
    };

    Node* m_head;
    int size;
};

template<class T>
void SortedList<T>::Push(T value)
{
    Node *where = this->m_head;
    Node *prev = nullptr;

    // list is sorted ascending
    while (where && where->value < value)
    {
        prev = where;
        where = where->next;
    }
    
    where = new Node(value,where);

    // fix pointers
    if( prev )
        prev->next= where;
    else
        this->m_head = where;    
    this->size++;
}

template <class T>
T SortedList<T>::Pop()
{
    Node* pResult = this->m_head;

    if( pResult )
    {
        T result = pResult->value;
        this->m_head = this->m_head->next;
        this->size--;
        delete pResult;       
        return result;
    }
    else
        throw std::underflow_error("Empty stack when pop() called."); 
}

template<class T>
int SortedList<T>::Size()
{
    return this->size;
}

template<class T>
bool SortedList<T>::Find(T value)
{
    Node *p = this->m_head;
    while( p )
    {    
        if ( p->value == value )
            return true;
        p = p->next;
    }
    return false;
}

template<class T>
bool SortedList<T>::Remove(T value)
{
    Node *p = this->m_head;
    Node *prev = nullptr;

    // find the node with the value
    while( p && p->value < value )
    {
        prev = p;
        p = p->next;
    }

    // if p is empty of if p's value isn't
    // what we're looking for
    if( !p || p->value != value )
        return false;

    // figure out if we need to fix 
    // previous node's next pointer
    // or if we need to fix head pointer
    if( prev )
        prev->next = p->next;
    else if( p->next )
        this->m_head = p->next;
    else
        this->m_head = nullptr;

    delete p;
    this->size--;
    return true;
}

testSortedList.cpp

#include "SortedList.cpp"
#include <iostream>
#include <random>
#include <time.h>
#include <string>
using namespace std;

template <class T>
class testSortedList{
private:
    bool first_push();
    bool sorted_push();
    bool unsorted_push();
    bool a_lot_push();
    bool pop_empty();
    bool test_size();
    bool test_find();
    bool test_remove();
    bool test_string();
    string gen_string();

    SortedList<T> *mylist;
public:

    void start();
};

template <class T>
bool testSortedList<T>::first_push(){
    mylist = new SortedList<T>();
    T n = 1;
    mylist->Push(n);
    T first = mylist->Pop();

    return (first == n);
}

template <class T>
bool testSortedList<T>::pop_empty(){
    mylist = new SortedList<T>();
    try{
        T first = mylist->Pop();
    }
    catch(const std::underflow_error &){
        return true;
    }
    return false;
}

template <class T>
bool testSortedList<T>::sorted_push(){
    mylist = new SortedList<T>();
    T n = 1, m = 2, o = 3;
    mylist->Push(n);
    mylist->Push(m);
    mylist->Push(o);
    T result = mylist->Pop();    
    if (result != n)
        return false;
    result = mylist->Pop();
    if (result != m)
        return false;
    result = mylist->Pop();
    if (result != o)
        return false;
    return true;
}

template <class T>
bool testSortedList<T>::unsorted_push(){
    mylist = new SortedList<T>();
    T n = 1, m = 2, o = 3;

    mylist->Push(o);
    mylist->Push(m);
    mylist->Push(n);
    T result = mylist->Pop();    
    if (result != n)
        return false;
    result = mylist->Pop();
    if (result != m)
        return false;
    result = mylist->Pop();
    if (result != o)
        return false;
    return true;
}

template <class T>
bool testSortedList<T>::a_lot_push(){
    SortedList<int> *local = new SortedList<int>();

    for(int i = 0; i < 20; i++)
        local->Push(i);

    if( local->Size() != 20 )
        return false;

    int temp = -1, other = 0;
    for(int i = 0; i < 20; i++)
    {
        other = local->Pop();
        if( temp > other )
            return false;
        temp = other;
    }

    if( local->Size() != 0 )
        return false;

    for(int i = 20; i > 0; i--)
        local->Push(i);

    temp = -1; other = 0;
    for(int i = 0; i < 20; i++)
    {
        other = local->Pop();
        if( temp > other )
            return false;
        temp = other;
    }


    return true;
}

template <class T>
bool testSortedList<T>::test_size(){
    mylist = new SortedList<T>();
    int size = 0;
    T n = 1, m = 2, o = 3;
    if( mylist->Size() != 0 )
        return false;
    mylist->Push(o);
    if( mylist->Size() != 1 )
        return false;
    mylist->Push(m);    
    if( mylist->Size() != 2 )
        return false;
    mylist->Push(n);    
    if( mylist->Size() != 3 )
        return false;
    T result = mylist->Pop();       
    if( mylist->Size() != 2 )
        return false;
    result = mylist->Pop();     
    if( mylist->Size() != 1 )
        return false;
    result = mylist->Pop();     
    if( mylist->Size() != 0 )
        return false;

    return true;
}

template <class T>
bool testSortedList<T>::test_find(){
    mylist = new SortedList<T>();
    T n = 1, m = 2, o = 3;

    if( mylist->Find(0) )
        return false;
    mylist->Push(o);
    if( !mylist->Find(3) )
        return false;
    mylist->Push(m);    
    if( !mylist->Find(2) )
        return false;
    mylist->Push(n);
    if( !mylist->Find(1) )
        return false;

    mylist->Pop();       
    if( mylist->Find(1) )
        return false;
    mylist->Pop();     
    if( mylist->Find(2) )
        return false;
    mylist->Pop();     
    if( mylist->Find(3) )
        return false;

    return true;
}

template <class T>
bool testSortedList<T>::test_remove(){
    mylist = new SortedList<T>();
    T n = 1, m = 2, o = 3;

    if( mylist->Remove(0) )
        return false;

    mylist->Push(o);
    mylist->Push(m);    
    mylist->Push(n);

    if( !mylist->Remove(1) )
        return false;
    if( mylist->Find(1) )
        return false;

    if( !mylist->Remove(2) )
        return false;    
    if( mylist->Find(2) )
        return false;

    if( !mylist->Remove(3) )
        return false;     
    if( mylist->Find(3) )
        return false;

    if( mylist->Find(0) )
        return false;

    return true;
}

template <class T>
string testSortedList<T>::gen_string(){
    string *x = new string;
    static const char alphanum[] =
        "0123456789"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

    for (int i = 0; i < 5; ++i)
        (*x) += alphanum[rand() % (sizeof(alphanum) - 1)];

    return *x;
}

template <class T>
bool testSortedList<T>::test_string(){
    srand((unsigned int)time(NULL));
    SortedList<string> *local = new SortedList<string>();

    for(int i = 0; i < 20; i++)
        local->Push(gen_string());

    if( local->Size() != 20 )
        return false;

    string temp, other;
    for(int i = 0; i < 20; i++)
    {
        other = local->Pop();

        if( temp > other )
            return false;
        temp = other;
    }

    if( local->Size() != 0 )
        return false;

    for(int i = 20; i > 0; i--)
        local->Push(gen_string());

    temp = ""; other = "";
    for(int i = 0; i < 20; i++)
    {
        other = local->Pop();
        if( temp > other )
            return false;
        temp = other;
    }

    return true;
}

template <class T>
void testSortedList<T>::start(){
    if( !first_push() )
        cout << "fail: on test_first" << endl;
    else
        cout << "pass: test_first " << endl;

    if( !sorted_push() )
        cout << "fail: on sorted_push" << endl;
    else
        cout << "pass: sorted_push" << endl;

    if( !unsorted_push() )
        cout << "fail: on unsorted_push" << endl;
    else
        cout << "pass: unsorted_push " << endl;

    if( !unsorted_push() )
        cout << "fail: on a_lot_push" << endl;
    else
        cout << "pass: a_lot_push " << endl;

    if( !pop_empty() )
        cout << "fail: on pop_empty" << endl;
    else
        cout << "pass: pop_empty " << endl;

    if( !test_size() )
        cout << "fail: on test_size" << endl;
    else
        cout << "pass: test_size " << endl;

    if( !test_find() )
        cout << "fail: on test_find" << endl;
    else
        cout << "pass: test_find " << endl;

    if( !test_remove() )
        cout << "fail: on test_remove" << endl;
    else
        cout << "pass: test_remove " << endl;

    if( !test_string() )
        cout << "fail: on test_string" << endl;
    else
        cout << "pass: test_string " << endl;
}

int main(){
    testSortedList<int> test;
    cout << "Testing SortedList class... " << endl << endl;

    test.start();
    cout << endl << "Done." <<endl;
    cin.get();
    return 0;
}