src/Utils/UniqueQueue.h

   1 // TortoiseGit - a Windows shell extension for easy version control
   2
   3 // Copyright (C) 2013 - TortoiseGit
   4 // Copyright (C) 2010-2011, 2015 - TortoiseSVN
   5
   6 // This program is free software; you can redistribute it and/or
   7 // modify it under the terms of the GNU General Public License
   8 // as published by the Free Software Foundation; either version 2
   9 // of the License, or (at your option) any later version.
  10
  11 // This program is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this program; if not, write to the Free Software Foundation,
  18 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  19 //
  20 #pragma once
  21
  22 /**
  23  * \ingroup Utils
  24  * Implements a queue like container which avoids storing duplicates.
  25  * If an entry is added that's already in the queue, it gets moved to
  26  * the end of the queue.
  27  *
  28  * \code
  29  * UniqueQueue<CString> myQueue;
  30  * myQueue.Push(CString(L"one"));
  31  * myQueue.Push(CString(L"two"));
  32  * myQueue.Push(CString(L"one"));  // "one" already exists, so moved to the end of the queue
  33  * myQueue.Push(CString(L"three"));
  34  * myQueue.Push(CString(L"three"));
  35  *
  36  * ATLASSERT(myQueue.Pop().Compare(L"two") == 0);   // because "one" got moved
  37  * ATLASSERT(myQueue.Pop().Compare(L"one") == 0);
  38  * ATLASSERT(myQueue.Pop().Compare(L"three") == 0);
  39  * \endcode
  40  */
  41 template <class T>
  42 class UniqueQueue
  43 {
  44 public:
  45         UniqueQueue();
  46         ~UniqueQueue();
  47
  48         size_t                  Push(const T &value);
  49         T                               Pop();
  50         size_t                  erase(const T &value);
  51         size_t                  size() const { return m_Queue.size(); }
  52         bool                    empty() { return m_Queue.empty(); }
  53 private:
  54         struct UniqueQueueStruct
  55         {
  56                 T                       value;
  57                 size_t          priority;
  58         };
  59         std::map<T, size_t>                             m_QueueTMap;
  60         std::deque<UniqueQueueStruct>   m_Queue;
  61         size_t                                                  m_highestValue;
  62 };
  63
  64 template <class T>
  65 UniqueQueue<T>::UniqueQueue()
  66         : m_highestValue(0)
  67 {
  68 }
  69
  70 template <class T>
  71 UniqueQueue<T>::~UniqueQueue()
  72 {
  73 }
  74
  75 template <class T>
  76 size_t UniqueQueue<T>::Push(const 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 (auto qIt = m_Queue.cbegin(); qIt != m_Queue.cend(); ++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 (auto tempIt = tempQueue.cbegin(); tempIt != tempQueue.cend(); ++tempIt)
 113                         {
 114                                 m_QueueTMap.insert(m_QueueTMap.cend(), 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(const T &value)
 144 {
 145         std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
 146         if (it != m_QueueTMap.end())
 147         {
 148                 for (auto qIt = m_Queue.cbegin(); qIt != m_Queue.cend(); ++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 }