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 private:
  52         typedef struct UniqueQueueStruct
  53         {
  54                 T                       value;
  55                 size_t          priority;
  56         };
  57         std::map<T, size_t>                             m_QueueTMap;
  58         std::deque<UniqueQueueStruct>   m_Queue;
  59         size_t                                                  m_highestValue;
  60 };
  61
  62 template <class T>
  63 UniqueQueue<T>::UniqueQueue()
  64         : m_highestValue(0)
  65 {
  66 }
  67
  68 template <class T>
  69 UniqueQueue<T>::~UniqueQueue()
  70 {
  71
  72 }
  73
  74 template <class T>
  75 size_t UniqueQueue<T>::Push( T value )
  76 {
  77         std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
  78         if (it != m_QueueTMap.end())
  79         {
  80                 // value is already in the queue: we don't allow duplicates
  81                 // so just move the existing value to the end of the queue
  82                 for (std::deque<UniqueQueueStruct>::iterator qIt = m_Queue.begin(); qIt != m_Queue.end(); ++qIt)
  83                 {
  84                         if (qIt->priority == it->second)
  85                         {
  86                                 m_Queue.erase(qIt);
  87                                 break;
  88                         }
  89                 }
  90                 it->second = m_highestValue;
  91                 UniqueQueueStruct s;
  92                 s.priority = m_highestValue++;
  93                 s.value = it->first;
  94                 m_Queue.push_back(s);
  95         }
  96         else
  97         {
  98                 m_QueueTMap.insert(it, std::map<T, size_t>::value_type(value, m_highestValue));
  99                 UniqueQueueStruct s;
 100                 s.priority = m_highestValue++;
 101                 s.value = value;
 102                 m_Queue.push_back(s);
 103                 if (m_highestValue == 0)
 104                 {
 105                         // overflow of priority value
 106                         // recreate the whole queue from scratch
 107                         std::map<T, size_t> tempQueue = m_QueueTMap;
 108                         m_QueueTMap.clear();
 109                         m_Queue.clear();
 110
 111                         for (std::map<T, size_t>::const_iterator tempIt = tempQueue.begin(); tempIt != tempQueue.end(); ++tempIt)
 112                         {
 113                                 m_QueueTMap.insert(m_QueueTMap.end(), std::map<T, size_t>::value_type(tempIt->first, m_highestValue));
 114                                 UniqueQueueStruct s2;
 115                                 s2.priority = m_highestValue++;
 116                                 s2.value = tempIt->first;
 117                                 m_Queue.push_back(s2);
 118                         }
 119                 }
 120         }
 121
 122         return m_Queue.size();
 123 }
 124
 125 template <class T>
 126 T UniqueQueue<T>::Pop()
 127 {
 128         if (m_Queue.size() == 0)
 129                 return T();
 130
 131         T value = m_Queue.front().value;
 132         m_Queue.pop_front();
 133         m_QueueTMap.erase(value);
 134
 135         if (m_Queue.size() == 0)
 136                 m_highestValue = 0;
 137
 138         return value;
 139 }
 140
 141 template <class T>
 142 size_t UniqueQueue<T>::erase( T value )
 143 {
 144         std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
 145         if (it != m_QueueTMap.end())
 146         {
 147                 for (std::deque<UniqueQueueStruct>::iterator qIt = m_Queue.begin(); qIt != m_Queue.end(); ++qIt)
 148                 {
 149                         if (qIt->priority == it->second)
 150                         {
 151                                 m_Queue.erase(qIt);
 152                                 break;
 153                         }
 154                 }
 155                 m_QueueTMap.erase(it);
 156         }
 157
 158         return m_QueueTMap.size();
 159 }