Stroika Library 3.0d18
 
Loading...
Searching...
No Matches
SortedMultiSet_SkipList.inl
1/*
2 * Copyright(c) Sophist Solutions, Inc. 1990-2025. 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::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
38 return Memory::MakeSharedPtr<Rep_> (*this);
39 }
40 virtual size_t size () const override
41 {
42 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
43 return fData_.size ();
44 }
45 virtual bool empty () const override
46 {
47 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
48 return fData_.empty ();
49 }
50 virtual Iterator<value_type> MakeIterator () const override
51 {
52 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
53 return Iterator<value_type>{make_unique<IteratorRep_> (&fData_, &fChangeCounts_)};
54 }
55 virtual Iterator<value_type> Find (const function<bool (ArgByValueType<value_type> item)>& that, Execution::SequencePolicy seq) const override
56 {
57 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
58 return this->inherited::Find (that, seq); // @todo rewrite to use fData
59 }
60
61 // MultiSet<T, TRAITS>::_IRep overrides
62 public:
63 virtual ElementEqualityComparerType GetElementEqualsComparer () const override
64 {
65 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
66 return Common::EqualsComparerAdapter<T, COMPARER>{fData_.key_comp ()};
67 }
68 virtual shared_ptr<typename MultiSet<T, TRAITS>::_IRep> CloneEmpty () const override
69 {
70 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
71 return Memory::MakeSharedPtr<Rep_> (fData_.key_comp ()); // keep comparer, but lose data
72 }
73 virtual shared_ptr<typename MultiSet<T, TRAITS>::_IRep> CloneAndPatchIterator (Iterator<value_type>* i) const override
74 {
75 RequireNotNull (i);
76 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
77 auto result = Memory::MakeSharedPtr<Rep_> (*this);
78 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i->ConstGetRep ());
79 result->fData_.MoveIteratorHereAfterClone (&mir.fIterator, &fData_);
80 i->Refresh (); // reflect updated rep
81 return result;
82 }
83 virtual bool Equals (const typename MultiSet<T, TRAITS>::_IRep& rhs) const override
84 {
85 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
86 return this->_Equals_Reference_Implementation (rhs);
87 }
88 virtual bool Contains (ArgByValueType<T> item) const override
89 {
90 value_type tmp{item};
91 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
92 return fData_.Find (item) != fData_.end ();
93 }
94 virtual void Add (ArgByValueType<T> item, CounterType count) override
95 {
96 if (count == 0) [[unlikely]] {
97 return;
98 }
99 Debug::AssertExternallySynchronizedMutex::WriteContext declareContext{fData_};
100 auto i = fData_.Find (item);
101 if (i == fData_.end ()) {
102 fData_.Add ({item, count});
103 }
104 else {
105 i.UpdateValue (i->fValue + count);
106 }
107 fChangeCounts_.PerformedChange ();
108 }
109 virtual size_t RemoveIf (ArgByValueType<T> item, CounterType count) override
110 {
111 Require (count != 0);
112 Debug::AssertExternallySynchronizedMutex::WriteContext declareContext{fData_};
113 auto i = fData_.Find (item);
114 Require (i != fData_.end ());
115 if (i != fData_.end ()) {
116 size_t result; // intentionally uninitialized
117 if (i->fValue > count) {
118 i.UpdateValue (i->fValue - count);
119 result = count;
120 }
121 else {
122 result = i->fValue;
123 fData_.erase (i);
124 }
125 fChangeCounts_.PerformedChange ();
126 return result;
127 }
128 return 0;
129 }
130 virtual void Remove (const Iterator<value_type>& i, Iterator<value_type>* nextI) override
131 {
132 Require (not i.Done ());
133 Debug::AssertExternallySynchronizedMutex::WriteContext declareContext{fData_};
134 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i.ConstGetRep ());
135 mir.fIterator.AssertDataMatches (&fData_);
136 auto nextIRes = fData_.erase (mir.fIterator);
137 fChangeCounts_.PerformedChange ();
138 if (nextI != nullptr) {
139 *nextI = Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, nextIRes)};
140 }
141 }
142 virtual void UpdateCount (const Iterator<value_type>& i, CounterType newCount, Iterator<value_type>* nextI) override
143 {
144 Debug::AssertExternallySynchronizedMutex::WriteContext declareContext{fData_};
145 auto& mir = Debug::UncheckedDynamicCast<const IteratorRep_&> (i.ConstGetRep ());
146 if (newCount == 0) {
147 if (nextI == nullptr) {
148 fData_.Remove (mir.fIterator);
149 }
150 else {
151 auto nextIRes = fData_.erase (mir.fIterator);
152 *nextI = Iterator<value_type>{make_unique<IteratorRep_> (&fChangeCounts_, nextIRes)};
153 }
154 }
155 else {
156 fData_.Update (mir.fIterator, newCount);
157 if (nextI != nullptr) {
158 *nextI = i; // update doesn't affect iterators
159 }
160 }
161 fChangeCounts_.PerformedChange ();
162 if (nextI != nullptr) {
163 Debug::UncheckedDynamicCast<IteratorRep_&> (nextI->GetRep ()).UpdateChangeCount ();
164 nextI->Refresh (); // update to reflect changes made to rep
165 }
166 }
167 virtual CounterType OccurrencesOf (ArgByValueType<T> item) const override
168 {
169 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
170 auto i = fData_.Find (item);
171 if (i == fData_.end ()) {
172 return 0;
173 }
174 return i->fValue;
175 }
176
177 // SortedMultiSet<T,TRAITS>::_IRep overrides
178 public:
179 virtual ElementThreeWayComparerType GetElementThreeWayComparer () const override
180 {
181 Debug::AssertExternallySynchronizedMutex::ReadContext declareContext{fData_};
182 return fData_.key_comp ();
183 }
184
185 private:
186 using DataStructureImplType_ = SKIPLIST<COMPARER>;
187 struct IterTraits_ : Private::IteratorImplHelper_DefaultTraits<value_type, DataStructureImplType_> {
188 static constexpr value_type ConvertDataStructureIterationResult2ContainerIteratorResult (const typename DataStructureImplType_::value_type& t)
189 {
190 return value_type{t.fKey, t.fValue};
191 }
192 };
193 using IteratorRep_ = Private::IteratorImplHelper_<value_type, DataStructureImplType_, IterTraits_>;
194
195 private:
196 DataStructureImplType_ fData_;
197 [[no_unique_address]] Private::ContainerDebugChangeCounts_ fChangeCounts_;
198
199 private:
200 friend inherited;
201 };
202
203 /*
204 ********************************************************************************
205 ********************** SortedMultiSet_SkipList<T, TRAITS> **********************
206 ********************************************************************************
207 */
208 template <typename T, typename TRAITS>
209 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList ()
210 : SortedMultiSet_SkipList{compare_three_way{}}
211 {
212 AssertRepValidType_ ();
213 }
214 template <typename T, typename TRAITS>
215 template <IThreeWayComparer<T> COMPARER>
216 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer)
217 : inherited{Memory::MakeSharedPtr<Rep_<remove_cvref_t<COMPARER>>> (forward<COMPARER> (comparer))}
218 {
219 AssertRepValidType_ ();
220 }
221 template <typename T, typename TRAITS>
222 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (const initializer_list<T>& src)
223 : SortedMultiSet_SkipList{}
224 {
225 this->AddAll (src);
226 AssertRepValidType_ ();
227 }
228 template <typename T, typename TRAITS>
229 template <IThreeWayComparer<T> COMPARER>
230 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, const initializer_list<T>& src)
231 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
232 {
233 this->AddAll (src);
234 AssertRepValidType_ ();
235 }
236 template <typename T, typename TRAITS>
237 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (const initializer_list<value_type>& src)
238 : SortedMultiSet_SkipList{}
239 {
240 this->AddAll (src);
241 AssertRepValidType_ ();
242 }
243 template <typename T, typename TRAITS>
244 template <IThreeWayComparer<T> COMPARER>
245 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, const initializer_list<value_type>& src)
246 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
247 {
248 this->AddAll (src);
249 AssertRepValidType_ ();
250 }
251#if !qCompilerAndStdLib_RequiresNotMatchInlineOutOfLineForTemplateClassBeingDefined_Buggy
252 template <typename T, typename TRAITS>
253 template <IIterableOfTo<typename TRAITS::CountedValueType> ITERABLE_OF_ADDABLE>
254 requires (not derived_from<remove_cvref_t<ITERABLE_OF_ADDABLE>, SortedMultiSet_SkipList<T, TRAITS>>)
255 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (ITERABLE_OF_ADDABLE&& src)
256 : SortedMultiSet_SkipList{}
257 {
258 this->AddAll (forward<ITERABLE_OF_ADDABLE> (src));
259 AssertRepValidType_ ();
260 }
261#endif
262 template <typename T, typename TRAITS>
263 template <IThreeWayComparer<T> COMPARER, IIterableOfTo<typename TRAITS::CountedValueType> ITERABLE_OF_ADDABLE>
264 inline SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, ITERABLE_OF_ADDABLE&& src)
265 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
266 {
267 this->AddAll (forward<ITERABLE_OF_ADDABLE> (src));
268 AssertRepValidType_ ();
269 }
270 template <typename T, typename TRAITS>
271 template <IInputIterator<typename TRAITS::CountedValueType> ITERATOR_OF_ADDABLE>
272 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (ITERATOR_OF_ADDABLE&& start, ITERATOR_OF_ADDABLE&& end)
273 : SortedMultiSet_SkipList{}
274 {
275 AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
276 AssertRepValidType_ ();
277 }
278 template <typename T, typename TRAITS>
279 template <IThreeWayComparer<T> COMPARER, IInputIterator<typename TRAITS::CountedValueType> ITERATOR_OF_ADDABLE>
280 SortedMultiSet_SkipList<T, TRAITS>::SortedMultiSet_SkipList (COMPARER&& comparer, ITERATOR_OF_ADDABLE&& start, ITERATOR_OF_ADDABLE&& end)
281 : SortedMultiSet_SkipList{forward<COMPARER> (comparer)}
282 {
283 AddAll (forward<ITERATOR_OF_ADDABLE> (start), forward<ITERATOR_OF_ADDABLE> (end));
284 AssertRepValidType_ ();
285 }
286 template <typename T, typename TRAITS>
287 inline void SortedMultiSet_SkipList<T, TRAITS>::AssertRepValidType_ () const
288 {
289 if constexpr (qStroika_Foundation_Debug_AssertionsChecked) {
290 typename inherited::template _SafeReadRepAccessor<IImplRepBase_> tmp{this}; // for side-effect of AssertMember
291 }
292 }
293
294}
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:48
RequireNotNull
#define RequireNotNull(p)
Definition Assertions.h:347
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
Stroika::Foundation::Debug::AssertExternallySynchronizedMutex::ReadContext
shared_lock< const AssertExternallySynchronizedMutex > ReadContext
Instantiate AssertExternallySynchronizedMutex::ReadContext to designate an area of code where protect...
Definition AssertExternallySynchronizedMutex.h:288
Stroika::Foundation::Debug::AssertExternallySynchronizedMutex::WriteContext
unique_lock< AssertExternallySynchronizedMutex > WriteContext
Instantiate AssertExternallySynchronizedMutex::WriteContext to designate an area of code where protec...
Definition AssertExternallySynchronizedMutex.h:309
Stroika::Foundation::Execution::SequencePolicy
SequencePolicy
equivalent which of 4 types being used std::execution::sequenced_policy, parallel_policy,...
Definition Foundation/Execution/Common.h:21