obslist.h

Go to the documentation of this file.

/**
 * \file obslist.h <mi32/obslist.h>
 * \brief Define OBSERVABLE_LIST template
 *
 * \if NODOC
 * $Id: obslist.h_v 1.7 2003/09/15 13:49:56 fileserver!dwilliss Exp $
 *
 * $Log: obslist.h_v $
 * Revision 1.7  2003/09/15 13:49:56  fileserver!dwilliss
 * Doxygen
 *
 * Revision 1.6  2003/01/30 17:43:16  mju
 * Use container class name for iterator so get the one we want.
 *
 * Revision 1.5  2002/06/25 16:35:16  mju
 * Make NotifyChanged() non-const as calls non-const method on member.
 *
 * Revision 1.4  2001/01/24 20:39:36  mju
 * Fix member access.
 *
 * Revision 1.3  2001/01/24 13:53:23  mju
 * OBSERVER is now our friend.
 *
 * Revision 1.2  2001/01/23 23:01:59  mju
 * Add NotifyChange.
 *
 * Revision 1.1  2001/01/23 15:42:29  mju
 * Initial revision
 *
 * \endif
**/

#ifndef INC_MI32_OBSLIST_H
#define INC_MI32_OBSLIST_H

#ifndef  INC_MI32_STDDEFNS_H
   #include <mi32/stddefns.h>
#endif

#ifndef  INC_MI32_STDANSIC_H
   #include <mi32/stdansic.h>
#endif

#ifndef  INC_MI32_MIODEFNS_H
   #include <mi32/miodefns.h>
#endif

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

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

//! Template for a list container which supports the OBSERVER pattern (see observer.h).
//! An observer is defined by inheriting from OBSERVABLE_LIST<type>::OBSERVER and overriding
//! the desired virtual methods.  Each list may have as many OBSERVERs as desired, however,
//! a particular OBSERVER may only be associated with one list at a time.
//! Notification when items are added, removed, reordered or sorted is automatic.  However,
//! if an item is changed (through a non-const reference) then notification is the responsibility
//! of the programmer.  NotifyChanged() should be called after the change is made so that all
//! observers are notified of the change.
template <class _LIT> class OBSERVABLE_LIST {

   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT

      //! Internal list item holder structure
      struct LISTITEM {
         _LIT m_Item;                  //!< Actual template item
         LISTITEM *m_Next, *m_Prev;

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

         void Swap (                //! Efficient swap method that does not call template's methods
            LISTITEM& other
            ) {
            UINT8 buffer[sizeof(LISTITEM)];
            memcpy(buffer, this, sizeof(LISTITEM));
            memcpy(this, &other, sizeof(LISTITEM));
            memcpy(&other, buffer, sizeof(LISTITEM));
            return;
            }
         };

      #endif //!< GENERATING_DOXYGEN_OUTPUT

   public:

      class OBSERVER;
      friend class OBSERVER;

      //! Base class for observers of this list to inherit from.
      class OBSERVER : public OBSERVER_BASE {
         public:

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

            //! Called when item has been changed through non-const reference.
            virtual void OnChanged (
               const _LIT& item              //!< Reference to item which was changed
               ) { }

            //! Called before item is repositioned in list.
            virtual void OnChangeOrderBegin (
               const _LIT& item              //!< Reference to item before position changed
               ) { }

            //! Called after item is repositioned in list.
            virtual void OnChangeOrderEnd (
               const _LIT& item              //!< Reference to item after position changed
               ) { }

            //! Called after list has been cleared.
            virtual void OnClear (
               ) { }

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

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

            //! Called when list has been sorted.
            virtual void OnSort (
               ) { }

         };

      class ITERATOR;               
      class CONST_ITERATOR;
      friend class ITERATOR;
      friend class CONST_ITERATOR;

      //! Constant bidirectional iterator.
      class CONST_ITERATOR {
         public:

            CONST_ITERATOR (           //! Default constructor
               ) {}

            CONST_ITERATOR (           //! Internal constructor
               LISTITEM *item
               ) : m_Ptr(item) {}

            CONST_ITERATOR (           //! Copy constructor
               const ITERATOR& item
               ) : m_Ptr(item.m_Ptr) {}

            const _LIT& operator* (    //! Dereference operator, returns reference to templated item
               ) const {
               return (m_Ptr->m_Item);
               }

            const _LIT* operator-> (   //! Dereference operator, returns pointer to templated item
               ) const {
               return (&**this);
               }

            //! Pre-increment operator.
            CONST_ITERATOR& operator++ (
               ) {
               m_Ptr = m_Ptr->m_Next;
               return (*this);
               }

            //! Post-increment operator.
            CONST_ITERATOR operator++(int
               ) {
               CONST_ITERATOR temp = *this;
               ++*this;
               return (temp);
               }

            //! Pre-decrement operator.
            CONST_ITERATOR& operator-- (
               ) {
               m_Ptr = m_Ptr->m_Prev;
               return (*this);
               }

            //! Post-decrement operator.
            CONST_ITERATOR operator--(int
               ) {
               CONST_ITERATOR temp = *this;
               --*this;
               return (temp);
               }

            bool operator== (          //! Equality operator
               const CONST_ITERATOR& rhs
               ) const {
               return (m_Ptr == rhs.m_Ptr);
               }

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

            LISTITEM *GetNode (        //! Internal, get a LISTITEM*
               ) const {
               return (m_Ptr);
               }

         protected:

            LISTITEM *m_Ptr;
         }; //! End of CONST_ITERATOR

      //! Non-constant bidirectional iterator.
      class ITERATOR : public CONST_ITERATOR {
         public:

            ITERATOR (                 //! Default constructor
               ) {}

            ITERATOR (                 //! Internal constructor
               LISTITEM *item
               ) : CONST_ITERATOR(item) {}

            _LIT& operator* (          //! Dereference operator, returns reference to templated item
               ) const {
               return (m_Ptr->m_Item);
               }

            _LIT* operator-> (         //! Dereference operator, returns pointer to templated item
               ) const {
               return (&**this);
               }

            //! Pre-increment operator.
            ITERATOR& operator++ (
               ) {
               m_Ptr = m_Ptr->m_Next;
               return (*this);
               }

            //! Post-increment operator.
            ITERATOR operator++(int
               ) {
               ITERATOR temp = *this;
               ++*this;
               return (temp);
               }

            //! Pre-decrement operator.
            ITERATOR& operator-- (
               ) {
               m_Ptr = m_Ptr->m_Prev;
               return (*this);
               }

            //! Post-increment operator.
            ITERATOR operator--(int
               ) {
               ITERATOR temp = *this;
               --*this;
               return (temp);
               }

            //! Equality operator
            bool operator== (
               const ITERATOR& rhs
               ) const {
               return (m_Ptr == rhs.m_Ptr);
               }

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

         }; //! End of ITERATOR


      // CONSTRUCTION / DESTRUCTION

      //! Construct empty list.
      OBSERVABLE_LIST (
         ) : m_Head(0), m_NumItems(0) {
         MmAllocCExc((void **)&m_Head, sizeof(LISTITEM));      //! Deliberate MmAllocC instead of new
         m_Head->m_Next = m_Head->m_Prev = m_Head;
         }

      //! Copy constructor, copies list items, not observers.
      OBSERVABLE_LIST (                   
         const OBSERVABLE_LIST<_LIT>& rhs
         ) : m_Head(0), m_NumItems(0) {
         MmAllocCExc((void **)&m_Head, sizeof(LISTITEM));      //! Deliberate MmAllocC instead of new
         m_Head->m_Next = m_Head->m_Prev = m_Head;
         for (CONST_ITERATOR it = rhs.Begin(); (it != rhs.End()); ++it) {
            Insert(End(), *it);
            }
         }

      //! Destructor.
      ~OBSERVABLE_LIST (                     
         ) {
         Clear();
         MmFree(m_Head);
         }

      //! Assignment operator, copies list items, not observers.
      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);
         }

      //! Return an ITERATOR that refers to the beginning of the list.
      ITERATOR Begin (              
         ) { return (ITERATOR(m_Head->m_Next)); }

      //! Return a CONST_ITERATOR that refers to the beginning of the list.
      CONST_ITERATOR Begin (       
         ) const { return (CONST_ITERATOR(m_Head->m_Next)); }

      //! Remove all entries from the list.
      void Clear (                  
         ) {
         for (ITERATOR it = Begin(); (it != End()); ) {
            Remove(it++,false);
            }
         m_ObserverMgr.NotifyClear();
         return;
         }

      //! Return an ITERATOR that refers to the end of the list, not a valid list item.
      ITERATOR End (                
         ) { return (ITERATOR(m_Head)); }

      //! Return a CONST_ITERATOR that refers to the end of the list, not a valid list item.
      CONST_ITERATOR End (          
         ) const { return (CONST_ITERATOR(m_Head)); }
         
      //! Return a reference to a const _LIT item from the front of the list
      const _LIT& GetBack (
         ) const { return (*(--End())); }

      //! Return a reference to a _LIT item from the front of the list
      _LIT& GetBack (
         ) { return (*(--End())); }

      //! Return a reference to a const _LIT item from the front of the list
      const _LIT& GetFront (
         ) const { return (*Begin()); }

      //! Return a reference to a _LIT item from the front of the list
      _LIT& GetFront (
         ) { return (*Begin()); }

      //! Return the number of items in the list.
      INT32 GetNumItems (           
         ) const { return (m_NumItems); }

      //! Insert an item into the place BEFORE the iterator.
      //! @return Reference to new item in list (not same as 'item' parameter as will be copied).
      _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);
         }

      //! Determine if any list entries exist.
      bool IsEmpty (                
         ) const { return (m_NumItems == 0); }

      //! Moves the item referenced by the iterator toward the beginning of the list.
      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;
         }

      //! Moves the item referenced by the iterator to the back of the list
      void MoveToBack (
         ITERATOR it
         ) {
         if (it == --End()) return;
         m_ObserverMgr.NotifyChangeOrderBegin(*it);
         RemoveItem(it);
         InsertItem(it, End());
         m_ObserverMgr.NotifyChangeOrderEnd(*it);
         return;
         }

      //! Moves the item referenced by the iterator to the front of the list
      void MoveToFront (
         ITERATOR it
         ) {
         if (it == Begin()) return;
         m_ObserverMgr.NotifyChangeOrderBegin(*it);
         RemoveItem(it);
         InsertItem(it, Begin());
         m_ObserverMgr.NotifyChangeOrderEnd(*it);
         return;
         }

      //! Notify all list observers that a change has been made to the specified item.
      //! There is no verification that the item is actually in the list.
      void NotifyChanged (
         const _LIT& item
         ) { m_ObserverMgr.NotifyChanged(item); }

      //! Insert an item at the beginning of the list.
      //! @return Reference to new item in list (not same as 'item' parameter as will be copied).
      _LIT& PushFront (             
         const _LIT& item
         ) { return (Insert(Begin(), item)); }

      //! Remove an item from the beginning of the list.
      void PopFront (               
         ) { Remove(Begin()); }

      //! Insert an item on the end of the list.
      //! @return Reference to new item in list (not same as 'item' parameter as will be copied).
      _LIT& PushBack (              
         const _LIT& item
         ) { return (Insert(End(), item)); }

      //! Remove the last item from the list.
      void PopBack (                
         ) { Remove(--End()); }
         
      //! Moves the item referenced by the iterator toward the end of the list.
      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;
         }

      //! Remove item specified by reference from the list.
      void Remove (
         const _LIT& item                 //!< Item to remove
         ) {
         for (ITERATOR it = Begin(); (it != End()); ) {
            if ((&*it) == &item) {
               Remove(it++);
               }
            else {
               ++it;
               }
            }
         return;
         }

      //! Remove item specified by ITERATOR from the list.
      //! Do not use the specified iterator after using this method as it will be invalid.
      void Remove (
         ITERATOR it,
         bool notify = true
         ) {
         RemoveItem(it);
         if (notify) m_ObserverMgr.NotifyRemove(*it);
         delete it.GetNode();
         return;
         }

      //! Remove a range of items from the list.
      void Remove (
         ITERATOR start,                  //!< Iterator for first item to remove
         ITERATOR end                     //!< Ending item, exclusive, will not be removed
         ) {
         for (ITERATOR it = start; (it != end); ) {
            Remove(it++);
            }
         return;
         }

      //! Remove item at specified position.
      void RemovePos (
         int pos                          //!< Position starting at 0 for beginning of list
         ) {
         ITERATOR it;
         for (it = Begin(); (it != End() && pos > 0); --pos)
            ;
         if (it != End()) Remove(it);
         return;
         }

      //! Sort the list in operator< () order.
      void Sort (
         ) {
         SortItems();
         m_ObserverMgr.NotifySort();
         return;
         }

      //! Sort the list in operator< () order.
      void Sort (                   
         bool (*PredFunc)(const _LIT& lhs, const _LIT& rhs)
         ) {
         SortItems(PredFunc);
         m_ObserverMgr.NotifySort();
         return;
         }

      //! Remove duplicate entries.
      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:
            void NotifyChanged (
               const _LIT& item
               ) {
               for (OBSERVERMGR::ITERATOR it = ObserverBegin(); (it != ObserverEnd()); ++it) {
                  (*it)->OnChanged(item);
                  }
               }

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

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

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

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

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

            void NotifySort (
               ) {
               for (OBSERVERMGR::ITERATOR it = ObserverBegin(); (it != 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 (                    //! Sort the list in operator< () order
         ) {
         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;         //!< 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 (                    //! Sort the list in operator< () order
         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;         //!< 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;
      OBSERVERMGR m_ObserverMgr;
      #endif // GENERATING_DOXYGEN_OUTPUT

   };

#endif      //!< INC_MI32_OBSLIST_H

---