mi32/milist.h

Go to the documentation of this file.

#ifndef INC_MI32_MILIST_H
#define INC_MI32_MILIST_H

#ifndef  INC_MI32_MEMALLOC_H
   #include <mi32/memalloc.h>
#endif

#include <functional>

template <typename _LIT> class MILIST {

   protected:

      struct LISTITEM {             
         _LIT m_Item;                  
         LISTITEM *m_Next, *m_Prev;

         LISTITEM (                 
            const _LIT& item
            ) : m_Item(item), m_Prev(0), m_Next(0) {}
            
         private:
            #ifndef GENERATING_DOXYGEN_OUTPUT
         
            LISTITEM (const LISTITEM&);
            LISTITEM& operator= (const LISTITEM&);
            #endif // GENERATING_DOXYGEN_OUTPUT
         };

   public:

      // Forward declarations.

      class ITERATOR;               
      class CONST_ITERATOR;
      friend class CONST_ITERATOR;

      class CONST_ITERATOR {
         public:

            CONST_ITERATOR (           
               ) {}

            CONST_ITERATOR (           
               LISTITEM *item
               ) : m_Ptr(item) {}

            CONST_ITERATOR (           
               const ITERATOR& item
               ) : m_Ptr(item.m_Ptr) {}

            const _LIT& operator* (    
               ) const { return (CONST_ITERATOR::m_Ptr->m_Item); }

            const _LIT* operator-> (   
               ) const { return (&**this); }

            CONST_ITERATOR& operator++ (
               ) {
               CONST_ITERATOR::m_Ptr = CONST_ITERATOR::m_Ptr->m_Next;
               return (*this);
               }

            CONST_ITERATOR operator++(int
               ) {
               CONST_ITERATOR temp = *this;
               ++*this;
               return (temp);
               }

            CONST_ITERATOR& operator-- (
               ) {
               CONST_ITERATOR::m_Ptr = CONST_ITERATOR::m_Ptr->m_Prev;
               return (*this);
               }

            CONST_ITERATOR operator--(int
               ) {
               CONST_ITERATOR temp = *this;
               --*this;
               return (temp);
               }

            bool operator== (          
               const CONST_ITERATOR& rhs
               ) const { return (CONST_ITERATOR::m_Ptr == rhs.m_Ptr); }

            bool operator!= (          
               const CONST_ITERATOR& rhs
               ) const { return (!(*this == rhs)); }

            LISTITEM *GetNode (        
               ) const { return (m_Ptr); }

         protected:
            LISTITEM *m_Ptr;
         };

      friend class ITERATOR;        

      class ITERATOR : public CONST_ITERATOR {
         public:

            ITERATOR (                 
               ) {}

            ITERATOR (                 
               LISTITEM *item
               ) : CONST_ITERATOR(item) {}
               
            _LIT& operator* (          
               ) const { return (CONST_ITERATOR::m_Ptr->m_Item); }

            _LIT* operator-> (
               ) const { return (&**this); }

            ITERATOR& operator++ (
               ) {
               CONST_ITERATOR::m_Ptr = CONST_ITERATOR::m_Ptr->m_Next;
               return (*this);
               }

            ITERATOR operator++(int
               ) {
               ITERATOR temp = *this;
               ++*this;
               return (temp);
               }

            ITERATOR& operator-- (
               ) {
               CONST_ITERATOR::m_Ptr = CONST_ITERATOR::m_Ptr->m_Prev;
               return (*this);
               }

            ITERATOR operator--(int
               ) {
               ITERATOR temp = *this;
               --*this;
               return (temp);
               }

            bool operator== (
               const ITERATOR& rhs
               ) const { return (CONST_ITERATOR::m_Ptr == rhs.m_Ptr); }

            bool operator!= (
               const ITERATOR& rhs
               ) const { return (!(*this == rhs)); }

         };

      MILIST (                      
         ) : m_Head(0), m_NumItems(0) {
         MmAllocCExc((void **)&m_Head, sizeof(LISTITEM));      
         m_Head->m_Next = m_Head->m_Prev = m_Head;
         }

      MILIST (                      
         const MILIST<_LIT>& rhs
         ) : m_Head(0), m_NumItems(0) {
         MmAllocCExc((void **)&m_Head, sizeof(LISTITEM));      
         m_Head->m_Next = m_Head->m_Prev = m_Head;
         for (CONST_ITERATOR it = rhs.Begin(); (it != rhs.End()); ++it) {
            Insert(End(), *it);
            }
         }

      ~MILIST (                     
         ) {
         Clear();
         MmFree(m_Head);
         }

      MILIST<_LIT>& operator= (     
         const MILIST<_LIT>& rhs
         ) {
         if (this != &rhs) {
            Clear();
            for (CONST_ITERATOR it = rhs.Begin(); (it != rhs.End()); ++it) {
               Insert(End(), *it);
               }
            }
         return (*this);
         }

      ITERATOR Begin (              
         ) { return (ITERATOR(m_Head->m_Next)); }

      CONST_ITERATOR Begin (       
         ) const { return (CONST_ITERATOR(m_Head->m_Next)); }

      void Clear (                  
         ) { Remove(Begin(), End()); }

      bool Contains (
         const _LIT& item
         ) const {
         for (CONST_ITERATOR it = Begin(); (it != End()); ++it) {
            if (*it == item) return (true);
            }
         return (false);
         }

      ITERATOR CopyIterator (
         CONST_ITERATOR it
         ) { return (ITERATOR(it.GetNode())); }

      CONST_ITERATOR Find (
         const _LIT& item
         ) const {
         CONST_ITERATOR it = Begin();
         for (; (it != End()); ++it) {
            if (*it == item) break;
            }
         return (it);
         }

      ITERATOR Find (
         const _LIT& item
         ) {
         ITERATOR it = Begin();
         for (; (it != End()); ++it) {
            if (*it == item) break;
            }
         return (it);
         }

      ITERATOR End (
         ) { return (ITERATOR(m_Head)); }

      CONST_ITERATOR End (
         ) const { return (CONST_ITERATOR(m_Head)); }

      void Exchange (
         MILIST<_LIT>& other
         ) {
         LISTITEM *TempHead = m_Head;
         m_Head = other.m_Head;
         other.m_Head = TempHead;
         INT32 TempNumItems = m_NumItems;
         m_NumItems = other.m_NumItems;
         other.m_NumItems = TempNumItems;
         return;
         }

      void Extract (
         MILIST<_LIT>& other, 
         ITERATOR& it         
         ) {
         other.RemoveItem(it);
         InsertItem(it,End());
         }

      const _LIT& GetBack (
         ) const { return (m_Head->m_Prev->m_Item); }

      _LIT& GetBack (
         ) { return (m_Head->m_Prev->m_Item); }

      const _LIT& GetFront (
         ) const { return (m_Head->m_Next->m_Item); }

      _LIT& GetFront (
         ) { return (m_Head->m_Next->m_Item); }

      const _LIT& GetIndexed (
         int index
         ) const {
         CONST_ITERATOR it = Begin();
         while (index > 0 && it != End()) {++it;--index;}
         return (*it);
         }

      _LIT& GetIndexed (
         int index
         ) {
         ITERATOR it = Begin();
         while (index > 0 && it != End()) {++it;--index;}
         return (*it);
         }

      INT32 GetNumItems (           
         ) const { return (m_NumItems); }

      bool HasSameValues (
         const MILIST<_LIT>& rhs
         ) const {
         if (m_NumItems != rhs.m_NumItems) return (false);
         for (CONST_ITERATOR lit = Begin();(lit != End()); ++lit) {
            if (!rhs.Contains(*lit)) return (false);
            }
         return (true);
         }
         
      _LIT& Insert (
         ITERATOR it,
         const _LIT& item
         ) { return (InsertBefore(it,item)); }

      _LIT& InsertAfter (                 
         ITERATOR it,
         const _LIT& item
         ) {
         LISTITEM *pPrev = it.GetNode();
         LISTITEM *pNew = new LISTITEM(item);
         pNew->m_Prev = pPrev;
         pNew->m_Next = pPrev->m_Next;
         pPrev->m_Next->m_Prev = pNew;
         pPrev->m_Next = pNew;
         ++m_NumItems;
         return (pNew->m_Item);
         }

      _LIT& InsertBefore (
         ITERATOR it,
         const _LIT& item
         ) {
         LISTITEM *pNext = it.GetNode();
         LISTITEM *pNew = new LISTITEM(item);
         pNew->m_Next = pNext;
         pNew->m_Prev = pNext->m_Prev;
         pNext->m_Prev->m_Next = pNew;
         pNext->m_Prev = pNew;
         ++m_NumItems;
         return (pNew->m_Item);
         }

      bool IsEmpty (                
         ) const { return (m_NumItems == 0); }

      bool IsEqual (
         const MILIST<_LIT>& rhs
         ) const {
         if (m_NumItems != rhs.m_NumItems) return (false);
         for (CONST_ITERATOR lit = Begin(), rit = rhs.Begin(); (lit != End()); ++lit, ++rit) {
            if (*lit != *rit) return (false);
            }
         return (true);
         }

      void Lower (
         ITERATOR it
         ) {
         if (it == Begin()) return;
         ITERATOR lower = it;
         --lower;
         RemoveItem(it);
         InsertItem(it, lower);
         }

      void Lower (
         int pos
         ) {
         ITERATOR it;
         for (it = Begin(); (it != End() && pos > 0); --pos, ++it)
            ;
         if (it != End()) Lower(it);
         }

      void Merge (                  
         MILIST<_LIT>& other
         ) {
         if (other.IsEmpty()) return;
         if (IsEmpty()) {
            LISTITEM *temp = m_Head;
            m_Head = other.m_Head;
            other.m_Head = temp;
            m_NumItems = other.m_NumItems;
            other.m_NumItems = 0;
            }
         else {
            other.m_Head->m_Prev->m_Next = m_Head;
            other.m_Head->m_Next->m_Prev = m_Head->m_Prev;
            m_Head->m_Prev->m_Next = other.m_Head->m_Next;
            m_Head->m_Prev = other.m_Head->m_Prev;
            m_NumItems += other.m_NumItems;
            other.m_Head->m_Prev = other.m_Head->m_Next = other.m_Head;
            other.m_NumItems = 0;
            }  
         return;
         }

      void MoveToBack (
         ITERATOR it
         ) {
         if (it == --End()) return;
         RemoveItem(it);
         InsertItem(it, End());
         }

      void MoveToFront (
         ITERATOR it
         ) {
         if (it == Begin()) return;
         RemoveItem(it);
         InsertItem(it, Begin());
         }

      _LIT& PushFront (             
         const _LIT& item
         ) { return (Insert(Begin(), item)); }

      void PopFront (               
         ) { Remove(Begin()); }

      _LIT& PushBack (              
         const _LIT& item
         ) { return (Insert(End(), item)); }

      void PopBack (                
         ) { Remove(--End()); }
         
      void Raise (
         ITERATOR it
         ) {
         if (it == --End()) return;
         ITERATOR upper = it;
         ++upper;
         RemoveItem(it);
         InsertItem(it, ++upper);
         }

      void Raise (
         int pos
         ) {
         ITERATOR it;
         for (it = Begin(); (it != End() && pos > 0); --pos, ++it)
            ;
         if (it != End()) Raise(it);
         }

      void Remove (
         ITERATOR it
         ) {
         RemoveItem(it);
         delete it.GetNode();
         }

      void Remove (
         ITERATOR start,                  
         ITERATOR end                     
         ) {
         for (ITERATOR it = start; (it != end); ) {
            Remove(it++);
            }
         }

      void RemoveDuplicates (       
         ) {
         if (m_NumItems < 2) return;
         for (ITERATOR check = Begin(); (check != End()); ++check) {
            ITERATOR it = check;
            for (++it; (it != End()); ++it) {
               if (*check == *it) {
                  ITERATOR prev = it;
                  --prev;
                  Remove(it);
                  it = prev;
                  }
               }
            }
         return;
         }

      void RemoveMatching (
         const _LIT& item
         ) {
         for (ITERATOR it = Begin(); (it != End()); ) {
            if (*it == item) {
               Remove(it++);
               }
            else {
               ++it;
               }
            }
         return;
         }

      void RemovePos (
         int pos                          
         ) {
         ITERATOR it;
         for (it = Begin(); (it != End() && pos > 0); --pos, ++it)
            ;
         if (it != End()) Remove(it);
         }

      void Reverse (
         ) {
         LISTITEM *pItem = m_Head;
         do {
            LISTITEM *pNext = pItem->m_Next;
            pItem->m_Next = pItem->m_Prev;
            pItem->m_Prev = pNext;
            pItem = pNext;
            } while (pItem != m_Head);
         return;
         }

      ITERATOR ReverseBegin (             
         ) { return (ITERATOR(m_Head->m_Prev)); }

      CONST_ITERATOR ReverseBegin (
         ) const { return (CONST_ITERATOR(m_Head->m_Prev)); }

      ITERATOR ReverseEnd (
         ) { return (ITERATOR(m_Head)); }

      CONST_ITERATOR ReverseEnd (
         ) const { return (CONST_ITERATOR(m_Head)); }

      void Sort (
         ) { SortItems(); }

      template<class _Pr1>
      void Sort (
         _Pr1 _Pr
         ) { 
         if (m_NumItems < 2) return;
         MILIST<_LIT> NewList;
         ITERATOR *ItArray = new ITERATOR[m_NumItems+1];
         ItArray[0] = NewList.End();

         while (m_NumItems > 0) {
            ITERATOR item = Begin();
            RemoveItem(item);

            INT32 index = 0;
            if (NewList.m_NumItems) {
               INT32 Left = 0, Right = NewList.m_NumItems-1;
               do {
                  index = (Left+Right) / 2;
                  if (_Pr(*item, *ItArray[index])) {
                     Right = index - 1;
                     }
                  else {
                     Left = ++index;         // The insert method is a place behind, add one to index in case Left > Right
                     }
                  } while (Left <= Right);
               }
            
            ITERATOR place = ItArray[index];
            for (int i = NewList.m_NumItems+1; (i > index); --i) ItArray[i] = ItArray[i-1];
            ItArray[index] = item;
            NewList.InsertItem(item, place);
            }
         
         delete [] ItArray;
         LISTITEM *temp = m_Head;      // Switch headers
         m_Head = NewList.m_Head;
         NewList.m_Head = temp;
         m_NumItems = NewList.m_NumItems;
         return;
         }
      
      void Sort (                   
         bool (*PredFunc)(const _LIT& lhs, const _LIT& rhs)
         ) { SortItems(PredFunc); }

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT

      void InsertItem (
         ITERATOR it,
         ITERATOR place
         ) {
         LISTITEM *q = it.GetNode();
         LISTITEM *after = place.GetNode();

         q->m_Next = after;
         q->m_Prev = after->m_Prev;
         after->m_Prev->m_Next = q;
         after->m_Prev = q;
         m_NumItems ++;
         return;
         }

      void RemoveItem (
         ITERATOR it
         ) {
         LISTITEM *q = it.GetNode();
         q->m_Next->m_Prev = q->m_Prev;
         q->m_Prev->m_Next = q->m_Next;
         m_NumItems --;
         return;
         }
         
      void SortItems (                    
         ) {
         if (m_NumItems < 2) return;
         MILIST<_LIT> NewList;
         ITERATOR *ItArray = new ITERATOR[m_NumItems+1];
         ItArray[0] = NewList.End();

         while (m_NumItems > 0) {
            ITERATOR item = Begin();
            RemoveItem(item);

            INT32 index = 0;
            if (NewList.m_NumItems) {
               INT32 Left = 0, Right = NewList.m_NumItems-1;
               do {
                  index = (Left+Right) / 2;
                  if (*item < *ItArray[index]) {
                     Right = index - 1;
                     }
                  else {
                     Left = ++index;         // The insert method is a place behind, add one to index in case Left > Right
                     }
                  } while (Left <= Right);
               }
            
            ITERATOR place = ItArray[index];
            for (int i = NewList.m_NumItems+1; (i > index); --i) ItArray[i] = ItArray[i-1];
            ItArray[index] = item;
            NewList.InsertItem(item, place);
            }
         
         delete [] ItArray;
         LISTITEM *temp = m_Head;      // Switch headers
         m_Head = NewList.m_Head;
         NewList.m_Head = temp;
         m_NumItems = NewList.m_NumItems;
         return;
         }

      void SortItems (                    
         bool (*PredFunc)(const _LIT& lhs, const _LIT& rhs)
         ) {
         if (m_NumItems < 2) return;
         MILIST<_LIT> NewList;
         ITERATOR *ItArray = new ITERATOR[m_NumItems+1];
         ItArray[0] = NewList.End();

         while (m_NumItems > 0) {
            ITERATOR item = Begin();
            RemoveItem(item);

            INT32 index = 0;
            if (NewList.m_NumItems) {
               INT32 Left = 0, Right = NewList.m_NumItems-1;
               do {
                  index = (Left+Right) / 2;
                  if (PredFunc(*item, *ItArray[index])) {
                     Right = index - 1;
                     }
                  else {
                     Left = ++index;         // The insert method is a place behind, add one to index in case Left > Right
                     }
                  } while (Left <= Right);
               }

            ITERATOR place = ItArray[index];
            for (int i = NewList.m_NumItems + 1; (i > index); --i) ItArray[i] = ItArray[i-1];
            ItArray[index] = item;
            NewList.InsertItem(item, place);
            }
         
         delete [] ItArray;
         LISTITEM *temp = m_Head;      // Switch headers
         m_Head = NewList.m_Head;
         NewList.m_Head = temp;
         m_NumItems = NewList.m_NumItems;
         return;
         }

      LISTITEM *m_Head;
      INT32 m_NumItems;
      #endif // GENERATING_DOXYGEN_OUTPUT
   };

#endif      // INC_MI32_MILIST_H

---