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.
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.
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);
49 size_t erase(T value
);
50 size_t size() { return m_Queue
.size(); }
52 typedef struct UniqueQueueStruct
57 std::map
<T
, size_t> m_QueueTMap
;
58 std::deque
<UniqueQueueStruct
> m_Queue
;
59 size_t m_highestValue
;
63 UniqueQueue
<T
>::UniqueQueue()
69 UniqueQueue
<T
>::~UniqueQueue()
75 size_t UniqueQueue
<T
>::Push( T value
)
77 std::map
<T
, size_t>::iterator it
= m_QueueTMap
.find(value
);
78 if (it
!= m_QueueTMap
.end())
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
)
84 if (qIt
->priority
== it
->second
)
90 it
->second
= m_highestValue
;
92 s
.priority
= m_highestValue
++;
98 m_QueueTMap
.insert(it
, std::map
<T
, size_t>::value_type(value
, m_highestValue
));
100 s
.priority
= m_highestValue
++;
102 m_Queue
.push_back(s
);
103 if (m_highestValue
== 0)
105 // overflow of priority value
106 // recreate the whole queue from scratch
107 std::map
<T
, size_t> tempQueue
= m_QueueTMap
;
111 for (std::map
<T
, size_t>::const_iterator tempIt
= tempQueue
.begin(); tempIt
!= tempQueue
.end(); ++tempIt
)
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
);
122 return m_Queue
.size();
126 T UniqueQueue
<T
>::Pop()
128 if (m_Queue
.size() == 0)
131 T value
= m_Queue
.front().value
;
133 m_QueueTMap
.erase(value
);
135 if (m_Queue
.size() == 0)
142 size_t UniqueQueue
<T
>::erase( T value
)
144 std::map
<T
, size_t>::iterator it
= m_QueueTMap
.find(value
);
145 if (it
!= m_QueueTMap
.end())
147 for (std::deque
<UniqueQueueStruct
>::iterator qIt
= m_Queue
.begin(); qIt
!= m_Queue
.end(); ++qIt
)
149 if (qIt
->priority
== it
->second
)
155 m_QueueTMap
.erase(it
);
158 return m_QueueTMap
.size();