*.js files: keep the style consistent
[TortoiseGit.git] / src / Utils / UniqueQueue.h
blob0c0237db5535526016b5ca6b8fff0a5b269041f2
1 // TortoiseGit - a Windows shell extension for easy version control
3 // Copyright (C) 2010-2011 - TortoiseSVN
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.
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.
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.
19 #pragma once
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.
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"));
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
40 template <class T>
41 class UniqueQueue
43 public:
44 UniqueQueue();
45 ~UniqueQueue();
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
55 T value;
56 size_t priority;
58 std::map<T, size_t> m_QueueTMap;
59 std::deque<UniqueQueueStruct> m_Queue;
60 size_t m_highestValue;
63 template <class T>
64 UniqueQueue<T>::UniqueQueue()
65 : m_highestValue(0)
69 template <class T>
70 UniqueQueue<T>::~UniqueQueue()
75 template <class T>
76 size_t UniqueQueue<T>::Push( T value )
78 std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
79 if (it != m_QueueTMap.end())
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)
85 if (qIt->priority == it->second)
87 m_Queue.erase(qIt);
88 break;
91 it->second = m_highestValue;
92 UniqueQueueStruct s;
93 s.priority = m_highestValue++;
94 s.value = it->first;
95 m_Queue.push_back(s);
97 else
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)
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();
112 for (std::map<T, size_t>::const_iterator tempIt = tempQueue.begin(); tempIt != tempQueue.end(); ++tempIt)
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);
123 return m_Queue.size();
126 template <class T>
127 T UniqueQueue<T>::Pop()
129 if (m_Queue.empty())
130 return T();
132 T value = m_Queue.front().value;
133 m_Queue.pop_front();
134 m_QueueTMap.erase(value);
136 if (m_Queue.empty())
137 m_highestValue = 0;
139 return value;
142 template <class T>
143 size_t UniqueQueue<T>::erase( T value )
145 std::map<T, size_t>::iterator it = m_QueueTMap.find(value);
146 if (it != m_QueueTMap.end())
148 for (std::deque<UniqueQueueStruct>::iterator qIt = m_Queue.begin(); qIt != m_Queue.end(); ++qIt)
150 if (qIt->priority == it->second)
152 m_Queue.erase(qIt);
153 break;
156 m_QueueTMap.erase(it);
159 return m_QueueTMap.size();