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