iLinkedList.h

Go to the documentation of this file.

/*
imagen - Simple object-oriented imaging library
Copyright (C) 2011-2012 Mark D. Procarione

imagen 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 3 of the License, or (at your option) any later version.

imagen 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.
*/

#ifndef __ILINKEDLIST_H__
#define __ILINKEDLIST_H__

#include <cstdio>

namespace imagen
{
        template <class dType> class iListNode
        {
                public:
                        iListNode()
                        {
                                // Warning! Undefined data. Only use this constructor for head!
                                next = NULL;
                                prev = NULL;
                        }

                        iListNode( const dType &nodeData )
                        {
                                data = nodeData;
                                next = NULL;
                                prev = NULL;
                        }

                public: // This should probably be private
                        dType data;
                        iListNode *next, *prev;
        };


        template <class dType> class iLinkedList
    {
                typedef iListNode<dType> Node;

        public:

                        iLinkedList()
                        {
                                head = new Node();
                                tail = new Node();
                                size = 0;
                        }

                        iLinkedList( const iLinkedList<dType> &list )
                        {
                head = new Node();
                                tail = new Node();
                                size = 0;

                            *this = list;
                        }

                        ~iLinkedList()
                        {
                                clear();
                                delete head;
                                delete tail;
                        }


                        void append( const dType &newData )
                        {
                                Node *node = new Node(newData);

                                if(head->next == NULL)
                                        head->next = node;
                                if(tail->prev == NULL)
                                        tail->prev = node;

                                node->next = tail;
                                node->prev = tail->prev;
                                node->prev->next = node;
                                tail->prev = node;

                                size++;
                        }


                        void prepend( const dType &newData )
                        {
                                Node *node = new Node(newData);

                                if(head->next == NULL)
                                        head->next = node;
                                if(tail->prev == NULL)
                                        tail->prev = node;

                                node->next = head->next;
                                node->prev = head;
                                node->next->prev = node;
                                head->next = node;

                                size++;
                        }


                        void insert( int i, const dType &newData )
                        {
                                Node *node = new Node(newData);
                                Node *after;

                                if(i <= 0) prepend(newData);
                                else if(i >= size-1) append(newData);
                                else
                                {
                                        after = _getNode(i);

                                        node->next = after;
                                        node->prev = after->prev;
                                        node->prev->next = node;
                                        after->prev = node;

                                        size++;
                                }
                        }

                        void removeFirst()
                        {
                                Node *tmp = head->next;

                                head->next = head->next->next;
                                head->next->prev = head;

                                delete tmp;

                                size--;
                        }

                        void removeLast()
                        {
                                Node *tmp = tail->prev;

                                tail->prev = tail->prev->prev;
                                tail->prev->next = tail;

                                delete tmp;

                                size--;
                        }


                        void remove( int i )
                        {
                                if(size == 0) return;

                                if(i <= 0) removeFirst();
                                else if(i >= size-1) removeLast();
                                else
                                {
                                        Node *node = _getNode(i);

                                        node->prev->next = node->next;
                                        node->next->prev = node->prev;

                                        delete node;

                                        size--;
                                }
                        }


                        int removeAll( dType val )
                        {
                                if(size == 0) return 0;

                                Node *node = head->next;
                                int num = 0;
                                int count = 0;

                                while(count < size)
                                {
                                        if(node->data == val)
                                        {
                                                Node *tmp = node;
                                                node->prev->next = node->next;
                                                node->next->prev = node->prev;
                                                node = node->next;
                                                delete tmp;
                                                num++;
                                        }
                                        else
                                                node = node->next;

                                        count++;
                                }

                                size-=num;
                                return num;
                        }


                        void replace( int i, const dType &newData )
                        {
                                _getNode(i)->data = newData;
                        }


                        dType &getFirst() { return head->next->data; }


                        const dType &getFirst() const { return head->next->data; }


                        dType &getLast() { return tail->prev->data; }


                        const dType &getLast() const { return tail->prev->data; }


                        dType &getItem( int i ) { return _getNode(i)->data; }


                        const dType &getItem( int i ) const { return _getNode(i)->data; }


                        dType takeFirst()
                        {
                                dType data = getFirst();
                        removeFirst();
                        return data;
                        }


                        dType takeLast()
                        {
                                dType data = getLast();
                        removeLast();
                        return data;
                        }


                        dType takeItem( int i )
                        {
                                dType data = getItem(i);
                        remove(i);
                        return data;
                        }


                        void reverse()
                        {
                                /*
                                Node *result = NULL;
                                Node *current = head->next;
                                Node *next = NULL;
                                int count = 0;

                                while(count < size)
                                {
                                        next = current->next;
                                        current->next = result;
                                        result = current;
                                        current = next;
                                }

                                head = result;
                                 */
                        }


                        int countAll( dType val )
                        {
                                Node *node = head->next;
                                int num = 0;
                                int count = 0;

                                while(count < size)
                                {
                                        if(node->data == val)
                                                num++;

                                        node = node->next;
                                        count++;
                                }

                                return num;
                        }


            int getSize() { return size; }

                        void clear()
                        {
                                if(isEmpty()) return;

                                //Node *tmp;
                                Node *node = head->next;
                                int count = 0;

                                while(count < size)
                                {
                                        Node *tmp = node;
                                        node = node->next;
                                        delete tmp;
                                        count++;
                                }

                                head->next = NULL;
                                tail->prev = NULL;

                                size = 0;
                        }


            bool isMember( const dType &val )
            {
                                Node *node = head->next;
                                int count = 0;

                                while(count < size)
                                {
                                        if(node->data == val)
                                                return true;

                                        node = node->next;
                                        count++;
                                }
                                return false;
                        }


            bool isEmpty() { return !size; }

            iLinkedList<dType> &operator = ( const iLinkedList<dType> &l )
            {
                                clear();

                for(int i=0; i<l.size; i++)
                    append(l[i]);

                return *this;
            }

            iLinkedList<dType> &operator += ( const iLinkedList<dType> &l )
            {
                for(int i=0; i<l.size; i++)
                    append(l[i]);

                return *this;
            }


            dType &operator[] ( int i ) { return getItem(i); }


            const dType &operator[] ( int i ) const { return getItem(i); }

        private:
                        iListNode<dType> *_getNode( int i )
                        {
                                Node *current = head->next;
                                int count = 0;

                                if(i <= 0) return head->next;
                                else if(i >= size-1) return tail->prev;
                                //if(i < 0) i = 0;
                                //else if(i > size-1) i = size-1;

                                // Determines whether to work backward or forward.
                                // This cuts search time by half.
                                // More optimizations would be welcome.
                                if(i < (size/2))
                                {
                                        while(count < i)
                                        {
                                                current = current->next;
                                                count++;
                                        }
                                }
                                else if(i >= (size/2))
                                {
                                        current = tail->prev;
                                        count = size-1;

                                        while(count > i)
                                        {
                                                current = current->prev;
                                                count--;
                                        }
                                }

                                return current;
                        }

            const iListNode<dType> *_getNode( int i ) const
                        {
                Node *current = head->next;
                                int count = 0;

                                if(i <= 0) return head->next;
                                else if(i >= size-1) return tail->prev;
                                //if(i < 0) i = 0;
                                //else if(i > size-1) i = size-1;

                                // Determines whether to work backward or forward.
                                // This cuts search time by half.
                                // More optimizations would be welcome.
                                if(i < (size/2))
                                {
                                        while(count < i)
                                        {
                                                current = current->next;
                                                count++;
                                        }
                                }
                                else if(i >= (size/2))
                                {
                                        current = tail->prev;
                                        count = size-1;

                                        while(count > i)
                                        {
                                                current = current->prev;
                                                count--;
                                        }
                                }

                                return current;
                        }

        private:
            iListNode<dType> *head;
            iListNode<dType> *tail;
            int size;
    };
}

#endif // __ILINKEDLIST_H__