orderedList.h

Go to the documentation of this file.

// This software is distributed as part of the Improla library. 
// Improla is a library of classes for image processing.
// 
// Copyright (c) 2004, B. R. Siva Chandra, India
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program 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 General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// In case you would like to contact the author, use the following e-mail
// address: sivachandra_br@yahoo.com

// First Created    : 21st September 2004
// Author           : Siva Chandra
// Purpose          : Declares a class which is a doubly-linked list and can be ordered.

#ifndef __ORDERED_LIST_H__
#define __ORDERED_LIST_H__

#include <templateNode.h>

namespace tutk
{ // Start of namespace brace.

template < class T >
class OrderedList
{
public:
    OrderedList(void);
    
    OrderedList(const OrderedList &ol);
    
    virtual ~OrderedList();
    
    void push(T *data, double key);
    
    void pop(void);
    
    int getSize(void);
    
    void sortAscendingBubbleSort(void);
    
    void sortDescendingBubbleSort(void);
    
    tutk::TemplateNode< T >* getFirstNodePtr(void);
    
    //void operator=(const OrderedList &ol);
    
private:
    tutk::TemplateNode< T > *firstNodePtr;
    tutk::TemplateNode< T > *lastNodePtr;
    tutk::TemplateNode< T > *currentNodePtr;
    
    int *size;
    int *refCount;
};
    
template < class T >
OrderedList< T >::OrderedList(void)
{
    firstNodePtr = lastNodePtr = currentNodePtr = NULL;
    
    size = new int;
    refCount = new int;
    
    *size = 0;
    *refCount = 1;
}

template < class T >
OrderedList< T >::OrderedList(const OrderedList &ol)
{
    firstNodePtr = ol.firstNodePtr;
    lastNodePtr = ol.lastNodePtr;
    currentNodePtr = ol.currentNodePtr;
    
    size = ol.size;
    refCount = ol.refCount;
    (*refCount)++;
}    

template < class T >
OrderedList< T >::~OrderedList()
{
    if (*refCount <= 1)
    {
        while (*size != 0)
            pop();
            
        delete size; size = NULL;
        delete refCount; refCount = NULL;
    }    
    else
    {
        (*refCount)--;
        
        size = NULL;
        refCount = NULL;
    }    
}    

template < class T >
void OrderedList< T >::push(T *data, double key)
{
    if (firstNodePtr == NULL)
    {
        firstNodePtr = new tutk::TemplateNode< T >();
        currentNodePtr = lastNodePtr = firstNodePtr;
        
        firstNodePtr->data = data;
        firstNodePtr->key = key;
        
        (*size)++;
    }
    else
    {
        lastNodePtr->nextNodePtr = new tutk::TemplateNode< T >();
        (lastNodePtr->nextNodePtr)->prevNodePtr = lastNodePtr;
        
        lastNodePtr = lastNodePtr->nextNodePtr;
        lastNodePtr->data = data;
        lastNodePtr->key = key;
        
        (*size)++;
    }
            
    return;
}    

template < class T >
void OrderedList< T >::pop(void)
{
    if (lastNodePtr == NULL)
        return;
        
    if (lastNodePtr->prevNodePtr == NULL)
    {
        delete lastNodePtr->data; lastNodePtr->data = NULL;
        delete lastNodePtr;
        
        lastNodePtr = firstNodePtr = currentNodePtr = NULL;
        *size = 0;
        
        return;
    }    
    
    delete lastNodePtr->data; lastNodePtr->data = NULL;
    lastNodePtr == lastNodePtr->prevNodePtr;
    if (currentNodePtr == lastNodePtr->nextNodePtr)
        currentNodePtr = lastNodePtr;
        
    delete lastNodePtr->nextNodePtr;
    lastNodePtr->nextNodePtr = NULL;
    
    (*size)--;
    
    return;
}    

template < class T >
int OrderedList< T >::getSize(void)
{
    return *size;
}    

template < class T >
tutk::TemplateNode< T >* OrderedList< T >::getFirstNodePtr(void)
{
    return firstNodePtr;
}    

template < class T >
void OrderedList< T >::sortAscendingBubbleSort(void)
{
    int s = *size;
    for (int i = s - 1; i > 0; i--)
    {
        tutk::TemplateNode< T >* temp = firstNodePtr;
        T *tempT; double tempk;
        if (temp->key > (temp->nextNodePtr)->key)
        {
            tempT = temp->data;
            tempk = temp->key;
            
            temp->data = (temp->nextNodePtr)->data;
            temp->key = (temp->nextNodePtr)->key;
            
            (temp->nextNodePtr)->data = tempT;
            (temp->nextNodePtr)->key = tempk;
        }
            
        for (int j = 2; j <= i; j++)
        {
            temp = temp->nextNodePtr;
            
            if (temp->key > (temp->nextNodePtr)->key)
            {
                tempT = temp->data;
                tempk = temp->key;
                
                temp->data = (temp->nextNodePtr)->data;
                temp->key = (temp->nextNodePtr)->key;
                
                (temp->nextNodePtr)->data = tempT;
                (temp->nextNodePtr)->key = tempk;
            }
        }    
    }    
    
    return;
}    

template < class T >
void OrderedList< T >::sortDescendingBubbleSort(void)
{
    int s = *size;
    for (int i = s - 1; i > 0; i--)
    {
        tutk::TemplateNode< T >* temp = firstNodePtr;
        T *tempT; double tempk;
        if (temp->key < (temp->nextNodePtr)->key)
        {
            tempT = temp->data;
            tempk = temp->key;
            
            temp->data = (temp->nextNodePtr)->data;
            temp->key = (temp->nextNodePtr)->key;
            
            (temp->nextNodePtr)->data = tempT;
            (temp->nextNodePtr)->key = tempk;
        }
            
        for (int j = 2; j <= i; j++)
        {
            temp = temp->nextNodePtr;
            
            if (temp->key < (temp->nextNodePtr)->key)
            {
                tempT = temp->data;
                tempk = temp->key;
                
                temp->data = (temp->nextNodePtr)->data;
                temp->key = (temp->nextNodePtr)->key;
                
                (temp->nextNodePtr)->data = tempT;
                (temp->nextNodePtr)->key = tempk;
            }
        }    
    }    
    
    return;
}    
    
} // End of namespace brace.

#endif // __ORDERED_LIST_H__

---