src/Utils/UniqueQueue.h

   1 // TortoiseGit - a Windows shell extension for easy version control
   2
   3 // Copyright (C) 2010-2011 - TortoiseSVN
   4
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License
   7 // as published by the Free Software Foundation; either version 2
   8 // of the License, or (at your option) any later version.
   9
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software Foundation,
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 //
  19 #pragma once
  20
  21 /**
  22  * \ingroup Utils
  23  * Implements a queue like container which avoids storing duplicates.
  24  * If an entry is added that's already in the queue, it gets moved to
  25  * the end of the queue.
  26  *
  27  * \code
  28  * UniqueQueue<CString> myQueue;
  29  * myQueue.Push(CString(L"one"));
  30  * myQueue.Push(CString(L"two"));
  31  * myQueue.Push(CString(L"one"));  // "one" already exists, so moved to the end of the queue
  32  * myQueue.Push(CString(L"three"));
  33  * myQueue.Push(CString(L"three"));
  34  *
  35  * ATLASSERT(myQueue.Pop().Compare(L"two") == 0);   // because "one" got moved
  36  * ATLASSERT(myQueue.Pop().Compare(L"one") == 0);
  37  * ATLASSERT(myQueue.Pop().Compare(L"three") == 0);
  38  * \endcode
  39  */
  40 template <class T>
  41 class UniqueQueue
  42 {
  43 public:
  44         UniqueQueue();
  45         ~UniqueQueue();
  46
  47         size_t                  Push(T value);
  48         T                               Pop();
  49         size_t                  erase(T value);
  50         size_t                  size() { return m_Queue.size(); }
  51         bool                    empty() { return m_Queue.empty(); }
  52 private:
  53         typedef struct UniqueQueueStruct
  54         {
  55                 T                       value;
  56                 size_t          priority;
  57         };
  58         std::map<T, size_t>                             m_QueueTMap;
  59         std::deque<UniqueQueueStruct>   m_Queue;
  60         size_t                                                  m_highestValue;
  61 };
  62
  63 template <class T>
  64 UniqueQueue<T>::UniqueQueue()
  65         : m_highestValue(0)
  66 {
  67 }
  68
  69 template <class T>
  70 UniqueQueue<T>::~UniqueQueue()
  71 {
  72
  73 }
  74
  75 template <class T>
  76 size_t UniqueQueue<T>::Push( T value )
  77 {
  78         std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
  79         if (it != m_QueueTMap.end())
  80         {
  81                 // value is already in the queue: we don't allow duplicates
  82                 // so just move the existing value to the end of the queue
  83                 for (std::deque<UniqueQueueStruct>::iterator qIt = m_Queue.begin(); qIt != m_Queue.end(); ++qIt)
  84                 {
  85                         if (qIt->priority == it->second)
  86                         {
  87                                 m_Queue.erase(qIt);
  88                                 break;
  89                         }
  90                 }
  91                 it->second = m_highestValue;
  92                 UniqueQueueStruct s;
  93                 s.priority = m_highestValue++;
  94                 s.value = it->first;
  95                 m_Queue.push_back(s);
  96         }
  97         else
  98         {
  99                 m_QueueTMap.insert(it, std::map<T, size_t>::value_type(value, m_highestValue));
 100                 UniqueQueueStruct s;
 101                 s.priority = m_highestValue++;
 102                 s.value = value;
 103                 m_Queue.push_back(s);
 104                 if (m_highestValue == 0)
 105                 {
 106                         // overflow of priority value
 107                         // recreate the whole queue from scratch
 108                         std::map<T, size_t> tempQueue = m_QueueTMap;
 109                         m_QueueTMap.clear();
 110                         m_Queue.clear();
 111
 112                         for (std::map<T, size_t>::const_iterator tempIt = tempQueue.begin(); tempIt != tempQueue.end(); ++tempIt)
 113                         {
 114                                 m_QueueTMap.insert(m_QueueTMap.end(), std::map<T, size_t>::value_type(tempIt->first, m_highestValue));
 115                                 UniqueQueueStruct s2;
 116                                 s2.priority = m_highestValue++;
 117                                 s2.value = tempIt->first;
 118                                 m_Queue.push_back(s2);
 119                         }
 120                 }
 121         }
 122
 123         return m_Queue.size();
 124 }
 125
 126 template <class T>
 127 T UniqueQueue<T>::Pop()
 128 {
 129         if (m_Queue.empty())
 130                 return T();
 131
 132         T value = m_Queue.front().value;
 133         m_Queue.pop_front();
 134         m_QueueTMap.erase(value);
 135
 136         if (m_Queue.empty())
 137                 m_highestValue = 0;
 138
 139         return value;
 140 }
 141
 142 template <class T>
 143 size_t UniqueQueue<T>::erase( T value )
 144 {
 145         std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
 146         if (it != m_QueueTMap.end())
 147         {
 148                 for (std::deque<UniqueQueueStruct>::iterator qIt = m_Queue.begin(); qIt != m_Queue.end(); ++qIt)
 149                 {
 150                         if (qIt->priority == it->second)
 151                         {
 152                                 m_Queue.erase(qIt);
 153                                 break;
 154                         }
 155                 }
 156                 m_QueueTMap.erase(it);
 157         }
 158
 159         return m_QueueTMap.size();
 160 }