nsortedlist.hpp

Go to the documentation of this file.

// LICENSE: (Please see the file COPYING for details)
//
// NUS - Nemesis Utilities System: A C++ application development framework 
// Copyright (C) 2006, 2008 Otavio Rodolfo Piske
//
//  This file is part of NUS
//
//  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 version 2.1
//  of the License.
//
//  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 Street, Fifth Floor, Boston, MA  02110-1301  USA
//
#ifndef NSORTEDLIST_HPP
#define NSORTEDLIST_HPP

template <typename T>
class NSortedList: public NList<T> { 
      public:
            NSortedList(void);
      
            NSortedList(const T &val);
            
            NSortedList(const NSortedList<T> &other);
            
            NSortedList<T> &insert(const T &val);
      
      private:
            NSortedList<T> &append(const T &val);
      
            NListNode<T> *locate(const T &val);
};


template <typename T>
NSortedList<T>::NSortedList(void)
      : NList<T>()
{

} 


template <typename T>
NSortedList<T>::NSortedList(const T &val)
      : NList<T>(val)
{

}


template <typename T>
NSortedList<T>::NSortedList(const NSortedList<T> &other)
      : NList<T>(other)
{
      copy(other);
}


template <typename T>
NListNode<T> *NSortedList<T>::locate(const T &val) { 
      NList<T>::gotoFirst();
      
      while (NList<T>::m_node && NList<T>::m_node->next 
                  && NList<T>::m_node->data < val) 
      {
            NList<T>::m_node = NList<T>::m_node->next;
      }
      
      if (NList<T>::m_node) { 
            return NList<T>::m_node->previous;
      }
      
      return NList<T>::m_node;
}


template <typename T>
NSortedList<T> &NSortedList<T>::insert(const T &val) {
      NListNode<T> *tmp = NULL;

      if (contains(val)) {
            return *this;
      }
      
      NList<T>::m_node = locate(val);
      if (NList<T>::m_node) { 
            tmp = new NListNode<T>;
            tmp->data = val;
            
            tmp->previous = NList<T>::m_node;
            tmp->next = NList<T>::m_node->next;
            
            if (NList<T>::m_node->next) {
                  NList<T>::m_node->next->previous = tmp;
            }
            NList<T>::m_node->next = tmp;
            
      }
      else {
            // There's no smaller item than val.
            tmp = new NListNode<T>;
            tmp->data = val;
            tmp->next = NList<T>::m_first;
            
            // If there's something in the list, fix it.
            if (NList<T>::m_first) { 
                  NList<T>::m_first->previous = tmp;
            }
            NList<T>::m_first = tmp;
            NList<T>::m_node = NList<T>::m_first;
      }
      
#ifdef NEXTRADEBUG
      std::cout << "Node: " << (void *) NList<T>::m_node << std::endl;
      std::cout << "Previous: " << (void *) NList<T>::m_node->previous << std::endl;
      std::cout << "Next: " << (void *) NList<T>::m_node->next << std::endl;
#endif

      NList<T>::m_count++;
      return *this;
}


#endif // NSORTEDLIST_HPP

---