Stroika Library 3.0d24
 
Loading...
Searching...
No Matches
SortedMultiSet_SkipList.inl
1/*
2 * Copyright(c) Sophist Solutions, Inc. 1990-2026. All rights reserved
3 */
4#include "Stroika/Foundation/Containers/DataStructures/STLContainerWrapper.h"
5#include "Stroika/Foundation/Containers/Private/IteratorImplHelper.h"
6#include "Stroika/Foundation/Debug/Cast.h"
7#include "Stroika/Foundation/Memory/BlockAllocated.h"
8
9namespace Stroika::Foundation::Containers::Concrete {
10
11 /**
12 */
13 template <typename T, typename TRAITS>
14 template <qCompilerAndStdLib_ConstraintDiffersInTemplateRedeclaration_BWA (IThreeWayComparer<T>) COMPARER>
15 class SortedMultiSet_SkipList<T, TRAITS>::Rep_ : public Private::SkipListBasedContainerRepImpl<Rep_<COMPARER>, IImplRepBase_>,
16 public Memory::UseBlockAllocationIfAppropriate<Rep_<COMPARER>> {
17 private:
18 using inherited = Private::SkipListBasedContainerRepImpl<Rep_<COMPARER>, IImplRepBase_>;
19
20 public:
21 static_assert (not is_reference_v<COMPARER>);
22
23 public:
24 Rep_ (const COMPARER& comparer)
25 : fData_{comparer}
26 {
27 }
28 Rep_ (const Rep_& from) = default;
29
30 public:
31 nonvirtual Rep_& operator= (const Rep_&) = delete;
32
33 // Iterable<typename TRAITS::CountedValueType>::_IRep overrides
34 public:
35 virtual shared_ptr<typename Iterable<typename TRAITS::CountedValueType>::_IRep> Clone () const override
36 {
37 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
38 return Memory::MakeSharedPtr<Rep_> (*this);
39 }
40 virtual size_t size () const override
41 {
42 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
43 return fData_.size ();
44 }
45 virtual bool empty () const override
46 {
47 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
48 return fData_.empty ();
49 }
50 virtual Iterator<value_type> MakeIterator () const override
51 {
52 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
53 return Iterator<value_type>{make_unique<IteratorRep_> (&fData_, &fChangeCounts_)};
54 }
55 virtual Iterator<value_type> Find (bool findFirst, const function<bool (ArgByValueType<value_type> item)>& that,
56 Execution::SequencePolicy seq) const override
57 {
58 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
59 return this->inherited::Find (findFirst, that, seq); // @todo rewrite to use fData
60 }
61
62 // MultiSet<T, TRAITS>::_IRep overrides
63 public:
64 virtual ElementEqualityComparerType GetElementEqualsComparer () const override
65 {
66 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
67 return Common::EqualsComparerAdapter<T, COMPARER>{fData_.key_comp ()};
68 }
69 virtual shared_ptr<typename MultiSet<T, TRAITS>::_IRep> CloneEmpty () const override
70 {
71 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
72 return Memory::MakeSharedPtr<Rep_> (fData_.key_comp ()); // keep comparer, but lose data
73 }
74 virtual shared_ptr<typename MultiSet<T, TRAITS>::_IRep> CloneAndPatchIterator (Iterator<value_type>* i) const override
75 {
76 RequireNotNull (i);
77 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
78 auto result = Memory::MakeSharedPtr<Rep_> (*this);
79 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i->ConstGetRep ());
80 result->fData_.MoveIteratorHereAfterClone (&mir.fIterator, &fData_);
81 i->Refresh (); // reflect updated rep
82 return result;
83 }
84 virtual bool Equals (const typename MultiSet<T, TRAITS>::_IRep& rhs) const override
85 {
86 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
87 return this->_Equals_Reference_Implementation (rhs);
88 }
89 virtual bool Contains (ArgByValueType<T> item) const override
90 {
91 value_type tmp{item};
92 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
93 return fData_.Find (item) != fData_.end ();
94 }
95 virtual void Add (ArgByValueType<T> item, CounterType count) override
96 {
97 if (count == 0) [[unlikely]] {
98 return;
99 }
100 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
101 auto i = fData_.Find (item);
102 if (i == fData_.end ()) {
103 fData_.Add ({item, count});
104 }
105 else {
106 i.UpdateValue (i->fValue + count);
107 }
108 fChangeCounts_.PerformedChange ();
109 }
110 virtual size_t RemoveIf (ArgByValueType<T> item, CounterType count) override
111 {
112 Require (count != 0);
113 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
114 auto i = fData_.Find (item);
115 Require (i != fData_.end ());
116 if (i != fData_.end ()) {
117 qStroika_ATTRIBUTE_INDETERMINATE size_t result;
118 if (i->fValue > count) {
119 i.UpdateValue (i->fValue - count);
120 result = count;
121 }
122 else {
123 result = i->fValue;
124 fData_.erase (i);
125 }
126 fChangeCounts_.PerformedChange ();
127 return result;
128 }
129 return 0;
130 }
131 virtual void Remove (const Iterator<value_type>& i, Iterator<value_type>* nextI) override
132 {
133 Require (not i.AtEnd ());
134 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
135 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i.ConstGetRep ());
136 mir.fIterator.AssertDataMatches (&fData_);
137 auto nextIRes = fData_.erase (mir.fIterator);
138 fChangeCounts_.PerformedChange ();
139 if (nextI != nullptr) {
140 *nextI = Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, nextIRes)};
141 }
142 }
143 virtual void UpdateCount (const Iterator<value_type>& i, CounterType newCount, Iterator<value_type>* nextI) override
144 {
145 Debug::AssertExternallySynchronizedChecker::WriteContext declareContext{fData_};
146 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i.ConstGetRep ());
147 if (newCount == 0) {
148 if (nextI == nullptr) {
149 fData_.Remove (mir.fIterator);
150 }
151 else {
152 auto nextIRes = fData_.erase (mir.fIterator);
153 *nextI = Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, nextIRes)};
154 }
155 }
156 else {
157 fData_.Update (mir.fIterator, newCount);
158 if (nextI != nullptr) {
159 *nextI = i; // update doesn't affect iterators
160 }
161 }
162 fChangeCounts_.PerformedChange ();
163 if (nextI != nullptr) {
164 Debug::UncheckedDynamicCast<IteratorRep_&> (nextI->GetRep ()).UpdateChangeCount ();
165 nextI->Refresh (); // update to reflect changes made to rep
166 }
167 }
168 virtual CounterType OccurrencesOf (ArgByValueType<T> item) const override
169 {
170 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
171 auto i = fData_.Find (item);
172 if (i == fData_.end ()) {
173 return 0;
174 }
175 return i->fValue;
176 }
177
178 // SortedMultiSet<T,TRAITS>::_IRep overrides
179 public:
180 virtual ElementThreeWayComparerType GetElementThreeWayComparer () const override
181 {
182 Debug::AssertExternallySynchronizedChecker::ReadContext declareContext{fData_};
183 return fData_.key_comp ();
184 }
185
186 private:
187 using DataStructureImplType_ = SKIPLIST<COMPARER>;
188 struct IterTraits_ : Private::IteratorImplHelper_DefaultTraits<value_type, DataStructureImplType_> {
189 static constexpr value_type ConvertDataStructureIterationResult2ContainerIteratorResult (const typename DataStructureImplType_::value_type& t)
190 {
191 return value_type{t.fKey, t.fValue};
192 }
193 };
194 using IteratorRep_ = Private::IteratorImplHelper_<value_type, DataStructureImplType_, IterTraits_>;
195
196 private:
197 DataStructureImplType_ fData_;
198 qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS_VCFORCE Private::ContainerDebugChangeCounts_ fChangeCounts_;
199
200 private:
201 friend inherited;
202 };
203
204 /*
205 ********************************************************************************
206 ********************** SortedMultiSet_SkipList<T, TRAITS> **********************
207 ********************************************************************************
208 */
209 template <typename T, typename TRAITS>
210 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList ()
211 : SortedMultiSet_SkipList{compare_three_way{}}
212 {
213 AssertRepValidType_ ();
214 }
215 template <typename T, typename TRAITS>
216 template <IThreeWayComparer<T> COMPARER>
217 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer)
218 : inherited{Memory::MakeSharedPtr<Rep_<remove_cvref_t<COMPARER>>> (forward<COMPARER> (comparer))}
219 {
220 AssertRepValidType_ ();
221 }
222 template <typename T, typename TRAITS>
223 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (const initializer_list<T>& src)
224 : SortedMultiSet_SkipList{}
225 {
226 this->AddAll (src);
227 AssertRepValidType_ ();
228 }
229 template <typename T, typename TRAITS>
230 template <IThreeWayComparer<T> COMPARER>
231 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, const initializer_list<T>& src)
232 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
233 {
234 this->AddAll (src);
235 AssertRepValidType_ ();
236 }
237 template <typename T, typename TRAITS>
238 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (const initializer_list<value_type>& src)
239 : SortedMultiSet_SkipList{}
240 {
241 this->AddAll (src);
242 AssertRepValidType_ ();
243 }
244 template <typename T, typename TRAITS>
245 template <IThreeWayComparer<T> COMPARER>
246 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, const initializer_list<value_type>& src)
247 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
248 {
249 this->AddAll (src);
250 AssertRepValidType_ ();
251 }
252#if !qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
253 template <typename T, typename TRAITS>
254 template <IIterableOfTo<typename TRAITS::CountedValueType> ITERABLE_OF_ADDABLE>
255 requires (not derived_from<remove_cvref_t<ITERABLE_OF_ADDABLE>, SortedMultiSet_SkipList<T, TRAITS>>)
256 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (ITERABLE_OF_ADDABLE&& src)
257 : SortedMultiSet_SkipList{}
258 {
259 this->AddAll (forward<ITERABLE_OF_ADDABLE> (src));
260 AssertRepValidType_ ();
261 }
262#endif
263 template <typename T, typename TRAITS>
264 template <IThreeWayComparer<T> COMPARER, IIterableOfTo<typename TRAITS::CountedValueType> ITERABLE_OF_ADDABLE>
265 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, ITERABLE_OF_ADDABLE&& src)
266 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
267 {
268 this->AddAll (forward<ITERABLE_OF_ADDABLE> (src));
269 AssertRepValidType_ ();
270 }
271 template <typename T, typename TRAITS>
272 template <IInputIterator<typename TRAITS::CountedValueType> ITERATOR_OF_ADDABLE>
273 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (ITERATOR_OF_ADDABLE&& start, ITERATOR_OF_ADDABLE&& end)
274 : SortedMultiSet_SkipList{}
275 {
276 AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
277 AssertRepValidType_ ();
278 }
279 template <typename T, typename TRAITS>
280 template <IThreeWayComparer<T> COMPARER, IInputIterator<typename TRAITS::CountedValueType> ITERATOR_OF_ADDABLE>
281 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, ITERATOR_OF_ADDABLE&& start, ITERATOR_OF_ADDABLE&& end)
282 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
283 {
284 AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
285 AssertRepValidType_ ();
286 }
287 template <typename T, typename TRAITS>
288 inline void SortedMultiSet_SkipList<T, TRAITS>::AssertRepValidType_ () const
289 {
290 if constexpr (qStroika_Foundation_Debug_AssertionsChecked) {
291 typename inherited::template _SafeReadRepAccessor<IImplRepBase_> tmp{this}; // for side-effect of AssertMember
292 }
293 }
294
295}
qStroika_Foundation_Debug_AssertionsChecked
#define qStroika_Foundation_Debug_AssertionsChecked
The qStroika_Foundation_Debug_AssertionsChecked flag determines if assertions are checked and validat...
Definition Assertions.h:49
RequireNotNull
#define RequireNotNull(p)
Definition Assertions.h:348
Stroika::Foundation::Memory::MakeSharedPtr
auto MakeSharedPtr(ARGS_TYPE &&... args) -> shared_ptr< T >
same as make_shared, but if type T has block allocation, then use block allocation for the 'shared pa...
Definition BlockAllocated.inl:52
Stroika::Foundation::Characters::CString::Equals
bool Equals(const T *lhs, const T *rhs)
strcmp or wsccmp() as appropriate == 0
qStroika_ATTRIBUTE_INDETERMINATE
#define qStroika_ATTRIBUTE_INDETERMINATE
qStroika_ATTRIBUTE_INDETERMINATE is used where you would use a C++ attribute for a variable that is i...
Definition StdCompat.h:393
qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS_VCFORCE
#define qStroika_ATTRIBUTE_NO_UNIQUE_ADDRESS_VCFORCE
[[msvc::no_unique_address]] isn't always broken in MSVC. Annotate with this on things where its not b...
Definition StdCompat.h:443
Stroika::Foundation::Debug::AssertExternallySynchronizedChecker::WriteContext
unique_lock< AssertExternallySynchronizedChecker > WriteContext
Instantiate AssertExternallySynchronizedChecker::WriteContext to designate an area of code where prot...
Definition AssertExternallySynchronizedChecker.h:335
Stroika::Foundation::Debug::AssertExternallySynchronizedChecker::ReadContext
shared_lock< const AssertExternallySynchronizedChecker > ReadContext
Instantiate AssertExternallySynchronizedChecker::ReadContext to designate an area of code where prote...
Definition AssertExternallySynchronizedChecker.h:314
Stroika::Foundation::Execution::SequencePolicy
SequencePolicy
equivalent which of 4 types being used std::execution::sequenced_policy, parallel_policy,...
Definition Foundation/Execution/Common.h:46