1 // TortoiseGit - a Windows shell extension for easy version control
3 // Copyright (C) 2013 - TortoiseGit
4 // Copyright (C) 2010-2011, 2015 - TortoiseSVN
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.
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.
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.
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.
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"));
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);
48 size_t Push(const T
&value
);
50 size_t erase(const T
&value
);
51 size_t size() const { return m_Queue
.size(); }
52 bool empty() { return m_Queue
.empty(); }
54 struct UniqueQueueStruct
59 std::map
<T
, size_t> m_QueueTMap
;
60 std::deque
<UniqueQueueStruct
> m_Queue
;
61 size_t m_highestValue
;
65 UniqueQueue
<T
>::UniqueQueue()
71 UniqueQueue
<T
>::~UniqueQueue()
76 size_t UniqueQueue
<T
>::Push(const 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 (auto qIt
= m_Queue
.cbegin(); qIt
!= m_Queue
.cend(); ++qIt
)
85 if (qIt
->priority
== it
->second
)
91 it
->second
= m_highestValue
;
93 s
.priority
= m_highestValue
++;
99 m_QueueTMap
.insert(it
, std::map
<T
, size_t>::value_type(value
, m_highestValue
));
101 s
.priority
= m_highestValue
++;
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
;
112 for (auto tempIt
= tempQueue
.cbegin(); tempIt
!= tempQueue
.cend(); ++tempIt
)
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
);
123 return m_Queue
.size();
127 T UniqueQueue
<T
>::Pop()
132 T value
= m_Queue
.front().value
;
134 m_QueueTMap
.erase(value
);
143 size_t UniqueQueue
<T
>::erase(const T
&value
)
145 std::map
<T
, size_t>::iterator it
= m_QueueTMap
.find(value
);
146 if (it
!= m_QueueTMap
.end())
148 for (auto qIt
= m_Queue
.cbegin(); qIt
!= m_Queue
.cend(); ++qIt
)
150 if (qIt
->priority
== it
->second
)
156 m_QueueTMap
.erase(it
);
159 return m_QueueTMap
.size();