Info
Get involved
Documentation

src/global/SAL_list.h

/*
    SAL - Simple Application Library
    Copyright (C) 2006-2006 Kronon

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
    License as published by the Free Software Foundation; either
    version 2.1 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    Kronon
    kronon88@users.sourceforge.net
*/

//SAL list class
//Created by Kronon

#ifndef SAL_LIST_H
#define SAL_LIST_H

//Include for error messaging system
#include "SAL_console.h"

template<class SAL_list_entry>
class salList
{
        private:
                struct SAL_list_node
                {
                        public:
                                SAL_list_node *next;
                                SAL_list_node *previous;
                                SAL_list_entry entry;
                };
                
                //Nr. of entries
                int size;
                SAL_list_node *begin;
                SAL_list_node *end;
                SAL_list_node *current;
                Uint32 loop_position;
        
        public:
        
                salList();
                //Functions for accessing the list
                int append(SAL_list_entry );                                                            //Add an new entry to the end of the list
                int pop();                                                                                                      //Remove the last entry
                int top(SAL_list_entry &);                                                                      //Read the last entry
                
                int clear();                                                                                            //Clear the list
                bool isEmpty();                                                                                         //Is the list empty?
                int getSize();                                                                                          //Get the size of the list
                
                int funcRemove(bool (*)(SAL_list_entry, SAL_list_entry), SAL_list_entry condition, int times = -1);     //Remove entries using an function
                
                //For/While loop functionality
                bool inLoop(int stepSize=1);                                                            //while(list.inWhile(increment)){ }
                SAL_list_entry getLoopEntry();                                                          //Get current loop entry
                void setLoopBegin();                                                                            //Set walk truh pointer to beginning of list
                
                //Operators of the list
                SAL_list_entry operator[]( int position);                                       //Get variable from given point
                int operator-=( SAL_list_entry entry);                                          //Remove variable from list

};

//Constructor
template<class SAL_list_entry> 
salList<SAL_list_entry>::salList()
{
        begin = end = current = NULL;
        size = 0;
        loop_position =0;
}

//Remove the last entry of the list
template<class SAL_list_entry> 
int salList<SAL_list_entry>::clear()
{
        //Remove the last nodes in the list
        SAL_list_node *node;
        while(begin != NULL)
        {
                node = begin->next;
                delete begin;
                begin = node;           
        }
        begin = end = current = NULL;
        
        //Decrease list size
        size = 0;
        return 0;
}

//Remove the last entry of the list
template<class SAL_list_entry> 
int salList<SAL_list_entry>::pop()
{
        if(size == 0)
                return -1;
        
        //Remove the last node in the list
        SAL_list_entry *node = end;
        end = end->previous;
        delete node;
        
        //Decrease list size
        size--;
        return 0;
}

//Get the last entry of the list
template<class SAL_list_entry> 
int salList<SAL_list_entry>::top(SAL_list_entry &entry)
{
        if(size == 0)
                return -1;
        
        entry = end->entry;
        return 0;
}

//Add an entry to the end of the list
template<class SAL_list_entry> 
int salList<SAL_list_entry>::append(SAL_list_entry entry)
{
        SAL_list_node *node = new SAL_list_node;
        node->next = NULL;
        node->entry = entry;
        
        if( begin == NULL)
                begin = node;
        else
                end->next = node;
        
        node->previous = end;
        end = node;
        size++;
        
        return 0;
}

//Return the size of the list
template<class SAL_list_entry> 
int salList<SAL_list_entry>::getSize()
{
        return size;
}

//Check if the list is empty
template<class SAL_list_entry> 
bool salList<SAL_list_entry>::isEmpty()
{
        return (size == 0);
}

//Get the n'th entry and return it
template<class SAL_list_entry> 
SAL_list_entry salList<SAL_list_entry>::operator[](int pos)
{
        //Some basic sanity checks
        if(size == 0)
        {
#ifdef SAL_DEBUG_ON
                salError("The size of your list is 0, there is nothing to be found");
#endif
                return 0;
        }
        else if(pos >= size)
        {
#ifdef SAL_DEBUG_ON
                salError("You want to search outside the list, there is nothing to be found");
#endif
                return 0;
        }
        
        // Find the "pos"'t target
        SAL_list_node *node= begin;
        for(int i = 0; i < pos; i++)
        {
                node=node->next;
        }
        return node->entry;
}

//Remove 1 entry with the value of given value
template<class SAL_list_entry> 
int salList<SAL_list_entry>::operator-=(SAL_list_entry entry)
{
        if(size == 0)
        {
#ifdef SAL_DEBUG_ON
                salError(" The size of your list is %i, there is nothing to be found",size);
#endif
                return 0;
        }
        
        SAL_list_node *node, *next_node;        //Node that run truh list, node that gets deleted
        node = begin;
        do
        {
                next_node = node->next;
                
                if(node->entry == entry)
                {
                        size--;
                        //Route list around current node
                        if(node->previous == NULL)              //First node doesn't have a previous node
                        {
                                begin = node->next;                     //Make next node first node
                                if(begin != NULL)
                                        begin->previous = NULL;
                        }
                        else
                        {
                                node->previous->next = node->next;
                                if(node->next != NULL)
                                        node->next->previous = node->previous;
                        }
                        
                        //Delete node
                        if(node == current)                     //Current node should alway point to valid node
                                setLoopBegin();
                        delete node;
                        
                        if(size == 0)
                                clear();
                        return 1;
                }
                node = next_node;
                
        }
        while(node != NULL);
        return 0;
}

//Remove 1 value by selection criterium given by function
//When funtion returns "not false" the routine will delete the node
template<class SAL_list_entry> 
int salList<SAL_list_entry>::funcRemove(bool (*function)(SAL_list_entry, SAL_list_entry), SAL_list_entry condition, int times)
{
        SAL_list_node *node = begin, *next_node;
        if(node == NULL)
        {
#ifdef SAL_DEBUG_ON
                salError("The size of your list is %i, there is nothing to be found", size);
#endif
                return 0;
        }
        do
        {
                next_node = node->next;
                if((*function)(node->entry,condition))
                {
                        size--;

                        //Route list around current node
                        if(node == begin)                               //First node doesn't have a previous node
                                begin = node->next;                     //Make next node first node
                        else
                                node->previous->next = node->next;
                        
                        if(node == end)
                                end = node->previous;
                        else
                                node->next->previous = node->previous;
                        
                        if(node == current)                     //Current node should alway point to valid node
                                setLoopBegin();
                        //Delete node
                        delete node;
                        
                        if(size == 0)
                                clear();
                        return 1;
                }
                node = next_node;
                
                if(times != -1)                                         //Count back times that are left
                        times--;
        }
        while(node != NULL && times != 0);
#ifdef SAL_DEBUG_ON
        printf("##Nothing found\n\n\n");
#endif
        return 0;
}

//while/for loop functionality

template<class SAL_list_entry>
void salList<SAL_list_entry>::setLoopBegin()                                                                    //Set walk truh pointer to beginning of list
{
        loop_position = 0;                                                                                                                      //(loop_position++)
        current = begin;
}

template<class SAL_list_entry> 
bool salList<SAL_list_entry>::inLoop(int stepSize)                                                              //while(list.inLoop()){ }
{
        loop_position++;
        if(size == 0)                                                                                                                           //Only loop truh filled lists
                return false;
        if(loop_position > (Uint32)size)                                                                                        //We have passed the end of the list so loop no further;)
                return false;
        
        if(loop_position != 1)                                                                                                          //Also show first node;)
        {
                if(current != NULL)
                        for(int i=0; i < stepSize; i++)
                                current = current->next;
        }
        
        return true;
}

template<class SAL_list_entry> 
SAL_list_entry salList<SAL_list_entry>::getLoopEntry()                                                  //Get current walk truh entry
{
        if(current != NULL)
                return current->entry;
                
#ifdef SAL_DEBUG_ON
        printf("Size = %i\n",size);     //debug
                
        //After this line debug
        printf("salList: Error entry doesn't exist\n");
#endif
        return current->entry;
}

#endif