mi32/obslist.h

Go to the documentation of this file.

#ifndef INC_MI32_OBSLIST_H
#define INC_MI32_OBSLIST_H

#ifndef  INC_MI32_OBSERVER_H
   #include <mi32/observer.h>
#endif

// When modifying this template consider making similar modifications to MILIST<>.

template <typename _LIT> class OBSERVABLE_LIST {

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT

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

         LISTITEM (                 
            const _LIT& item
            ) : m_Item(item), m_Prev(0), m_Next(0) {}

         void Swap (                
            LISTITEM& other
            ) {
            UINT8 buffer[sizeof(LISTITEM)];
            memcpy(buffer, this, sizeof(LISTITEM));
            memcpy(this, &other, sizeof(LISTITEM));
            memcpy(&other, buffer, sizeof(LISTITEM));
            return;
            }
         };

      #endif 

   public:

      class OBSERVER;
      friend class OBSERVER;

      class OBSERVER : public OBSERVER_BASE {
         public:

            OBSERVER (
               OBSERVABLE_LIST<_LIT>& list
               ): OBSERVER_BASE(list.m_ObserverMgr) { }

            virtual void OnChanged (
               const _LIT&    // item              //!< Reference to item which was changed
               ) { }

            virtual void OnChangeOrderBegin (
               const _LIT&    // item              //!< Reference to item before position changed
               ) { }

            virtual void OnChangeOrderEnd (
               const _LIT&    // item              //!< Reference to item after position changed
               ) { }

            virtual void OnClear (
               ) { }

            virtual void OnInsert (
               const _LIT&    // item              //!< Reference to item which has been inserted
               ) { }

            virtual void OnRemove (
               const _LIT&    // item              //!< Reference to item which is about to be removed
               ) { }

            virtual void OnSort (
               ) { }

         };

      class ITERATOR;               
      class CONST_ITERATOR;
      friend class 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 (m_Ptr->m_Item);
               }

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

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

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

            CONST_ITERATOR& operator-- (
               ) {
               m_Ptr = 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 (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;
         }; 

      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));
               }

         }; 


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

      OBSERVABLE_LIST (                   
         const OBSERVABLE_LIST<_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);
            }
         }

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

      OBSERVABLE_LIST<_LIT>& operator= (     
         const OBSERVABLE_LIST<_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 (                  
         ) {
         for (ITERATOR it = Begin(); (it != End()); ) {
            Remove(it++,false);
            }
         m_ObserverMgr.NotifyClear();
         return;
         }

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

      CONST_ITERATOR End (          
         ) const { return (CONST_ITERATOR(m_Head)); }
         
      const _LIT& GetBack (
         ) const { return (*(--End())); }

      _LIT& GetBack (
         ) { return (*(--End())); }

      const _LIT& GetFront (
         ) const { return (*Begin()); }

      _LIT& GetFront (
         ) { return (*Begin()); }

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

      _LIT& Insert (                
         ITERATOR p,
         const _LIT& item
         ) {
         LISTITEM *obj = p.GetNode();
         LISTITEM *newitem = new LISTITEM(item);
         newitem->m_Next = obj;
         newitem->m_Prev = obj->m_Prev;
         obj->m_Prev->m_Next = newitem;
         obj->m_Prev = newitem;
         m_NumItems ++;
         m_ObserverMgr.NotifyInsert(newitem->m_Item);
         return (newitem->m_Item);
         }

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

      void Lower (
         ITERATOR it
         ) {
         if (it == Begin()) return;
         m_ObserverMgr.NotifyChangeOrderBegin(*it);
         ITERATOR lower = it;
         --lower;
         RemoveItem(it);
         InsertItem(it, lower);
         m_ObserverMgr.NotifyChangeOrderEnd(*it);
         return;
         }

      void MoveToBack (
         ITERATOR it
         ) {
         if (it == --End()) return;
         m_ObserverMgr.NotifyChangeOrderBegin(*it);
         RemoveItem(it);
         InsertItem(it, End());
         m_ObserverMgr.NotifyChangeOrderEnd(*it);
         return;
         }

      void MoveToFront (
         ITERATOR it
         ) {
         if (it == Begin()) return;
         m_ObserverMgr.NotifyChangeOrderBegin(*it);
         RemoveItem(it);
         InsertItem(it, Begin());
         m_ObserverMgr.NotifyChangeOrderEnd(*it);
         return;
         }

      void NotifyChanged (
         const _LIT& item
         ) { m_ObserverMgr.NotifyChanged(item); }

      _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;
         m_ObserverMgr.NotifyChangeOrderBegin(*it);
         ITERATOR upper = it;
         ++upper;
         RemoveItem(it);
         InsertItem(it, ++upper);
         m_ObserverMgr.NotifyChangeOrderEnd(*it);
         return;
         }

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

      void Remove (
         ITERATOR it,
         bool notify = true
         ) {
         RemoveItem(it);
         if (notify) m_ObserverMgr.NotifyRemove(*it);
         delete it.GetNode();
         return;
         }

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

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

      void Sort (
         ) {
         SortItems();
         m_ObserverMgr.NotifySort();
         return;
         }

      void Sort (                   
         bool (*PredFunc)(const _LIT& lhs, const _LIT& rhs)
         ) {
         SortItems(PredFunc);
         m_ObserverMgr.NotifySort();
         return;
         }

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


   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT

      class OBSERVERMGR : public SUBJECT<OBSERVER> {
         public:
            typedef SUBJECT<OBSERVER> BASECLASS;
            typedef typename BASECLASS::ITERATOR ITERATOR;

            void NotifyChanged (
               const _LIT& item
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnChanged(item);
                  }
               }

            void NotifyChangeOrderBegin (
               const _LIT& item
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnChangeOrderBegin(item);
                  }
               }

            void NotifyChangeOrderEnd (
               const _LIT& item
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnChangeOrderEnd(item);
                  }
               }

            void NotifyClear (
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnClear();
                  }
               }

            void NotifyInsert (
               const _LIT& item
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnInsert(item);
                  }
               }

            void NotifyRemove (
               const _LIT& item
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnRemove(item);
                  }
               }

            void NotifySort (
               ) {
               for (ITERATOR it = BASECLASS::ObserverBegin(); (it != BASECLASS::ObserverEnd()); ++it) {
                  (*it)->OnSort();
                  }
               }
         };

      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;
         OBSERVABLE_LIST<_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;         
                     }
                  } 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;      
         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;
         OBSERVABLE_LIST<_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;         
                     }
                  } 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;      
         m_Head = NewList.m_Head;
         NewList.m_Head = temp;
         m_NumItems = NewList.m_NumItems;
         return;
         }

      LISTITEM *m_Head;
      INT32 m_NumItems;
      OBSERVERMGR m_ObserverMgr;
      #endif // GENERATING_DOXYGEN_OUTPUT

   };

#endif      // INC_MI32_OBSLIST_H

---