23 #ifndef __CLRX_DTREE_H__ 24 #define __CLRX_DTREE_H__ 29 #include <initializer_list> 39 template<
typename T1,
typename T2>
42 const T1& operator()(
const std::pair<T1, T2>& v)
const 44 T1& operator()(std::pair<T1, T2>& v)
const 52 const T& operator()(
const T& v)
const 54 T& operator()(T& v)
const 73 template<
typename K,
typename T = K,
typename Comp = std::less<K>,
74 typename KeyOfVal = Identity<K>,
typename AT = T>
75 class DTree:
private Comp, KeyOfVal
88 static const cxuint maxNode1Size = 8;
89 static const cxuint maxNode1Shift = 3;
90 static const cxuint normalNode1Shift = 2;
91 static const cxuint maxNode1Depth = (
sizeof(size_t)*8)>>1;
93 static const cxuint maxNode0Capacity = 63;
94 static const cxuint normalNode0Capacity = maxNode0Capacity>>1;
95 static const cxuint minNode0Capacity = 20;
96 static const cxuint freePlacesShift = 1;
97 static const cxuint minFreePlacesShift = 3;
99 static const cxuint maxNode0Size = ((maxNode0Capacity*1000 /
100 ((1<<minFreePlacesShift)+1))*(1<<minFreePlacesShift)) / 1000;
101 static const cxuint normalNode0Size = ((normalNode0Capacity*1000 /
102 ((1<<minFreePlacesShift)+1))*(1<<minFreePlacesShift)) / 1000;
103 static const cxuint minNode0Size = maxNode0Size / 3;
106 static size_t maxTotalSize(
cxuint level)
110 return size_t(maxNode0Size) << (normalNode1Shift * level);
114 static size_t normalTotalSize(
cxuint level)
117 return normalNode0Size;
118 return size_t(normalNode0Size) << (normalNode1Shift * level - 1);
122 static size_t minTotalSize(
cxuint level)
126 return (
size_t(maxNode0Size) << (normalNode1Shift * level)) / 3;
130 static const int parentEntrySize =
sizeof(
void*) <= 8 ? 8 :
sizeof(
void*);
141 static const int parentEntryIndex = -int(parentEntrySize /
sizeof(
void*));
161 firstPos(0), bitMask(0ULL), array(
nullptr)
165 index(node.index), size(node.size), capacity(node.capacity),
166 firstPos(node.firstPos), bitMask(node.bitMask), array(
nullptr)
168 if (node.array !=
nullptr)
170 array =
new AT[capacity];
171 std::copy(node.array, node.array+capacity, array);
175 index(node.index), size(node.size), capacity(node.capacity),
176 firstPos(node.firstPos), bitMask(node.bitMask), array(node.array)
178 node.array =
nullptr;
188 NodeBase::type = node.NodeBase::type;
191 capacity = node.capacity;
192 firstPos = node.firstPos;
193 bitMask = node.bitMask;
194 AT* newArray =
nullptr;
195 if (node.array !=
nullptr)
197 newArray =
new AT[capacity];
198 std::copy(node.array, node.array+capacity, newArray);
208 NodeBase::type = node.NodeBase::type;
211 capacity = node.capacity;
212 firstPos = node.firstPos;
213 bitMask = node.bitMask;
216 node.array =
nullptr;
222 {
return index!=255U ?
223 reinterpret_cast<Node1*
const *
>(
this-index)[parentEntryIndex] :
nullptr; }
227 {
return index!=255U ?
228 reinterpret_cast<Node1**
>(
this-index)[parentEntryIndex] :
nullptr; }
230 const AT& operator[](
cxuint i)
const 241 cxuint index = std::lower_bound(array, array+capacity, kt,
242 [&comp, &kofval](
const AT& v1,
const AT& v2)
243 {
return comp(kofval(v1), kofval(v2)); }) - array;
252 cxuint index = std::lower_bound(array, array+capacity, kt,
253 [&comp, &kofval](
const AT& v1,
const AT& v2)
254 {
return comp(kofval(v1), kofval(v2)); }) - array;
255 for (; (bitMask & (1ULL<<index)) != 0; index++);
264 cxuint index = std::upper_bound(array, array+capacity, kt,
265 [&comp, &kofval](
const T& v1,
const T& v2)
266 {
return comp(kofval(v1), kofval(v2)); }) - array;
267 for (; (bitMask & (1ULL<<index)) != 0; index++);
272 cxuint find(
const K& k,
const Comp& comp,
const KeyOfVal& kofval)
const 274 cxuint index = lower_bound(k, comp, kofval);
275 if (index == capacity ||
277 comp(k, kofval(array[index])) || comp(kofval(array[index]), k))
284 cxuint& i,
cxuint size,
const AT* array, uint64_t inBitMask,
285 cxuint& k,
cxuint newSize, AT* out, uint64_t& outBitMask,
288 while ((inBitMask & (1ULL<<i)) != 0)
292 for (; p0 < size; k++, p0++)
294 toFill = out[k] = array[i];
297 if (factor >= newSize)
303 outBitMask |= (1ULL<<k);
307 while ((inBitMask & (1ULL<<i)) != 0)
312 void setFromArray(
cxuint size,
const AT* input)
314 cxuint newCapacity = std::min(
cxbyte(size + (size>>freePlacesShift)),
315 cxbyte(maxNode0Capacity));
316 AT* newArray =
new AT[newCapacity];
320 const cxuint finc = newCapacity - size;
323 uint64_t newBitMask = 0;
324 organizeArray(toFill, i, size, input, 0ULL, k, size, newArray,
325 newBitMask, factor, finc);
328 newArray[k] = toFill;
329 newBitMask |= (1ULL<<k);
335 bitMask = newBitMask;
336 capacity = newCapacity;
340 void allocate(
cxuint size)
342 capacity = std::min(
cxbyte(size + (size>>freePlacesShift)),
343 cxbyte(maxNode0Capacity));
344 AT* newArray =
new AT[capacity];
353 const AT* array, uint64_t inBitMask,
size_t newSize,
356 cxuint finc = capacity - newSize;
358 organizeArray(toFill, index, remainingSize, array,
359 inBitMask, k, newSize, this->array, bitMask, factor, finc);
360 size += remainingSize;
361 pos += remainingSize;
367 cxuint newSize = size+node2.size;
368 cxuint newCapacity = std::min(
369 cxbyte(newSize + (newSize>>freePlacesShift)),
370 cxbyte(maxNode0Capacity));
371 AT* newArray =
nullptr;
372 if (newCapacity != 0)
373 newArray =
new AT[newCapacity];
375 uint64_t newBitMask = 0ULL;
378 const cxuint finc = newCapacity - newSize;
380 cxuint i = 0, j = 0, k = 0;
382 organizeArray(toFill, i, size, array, bitMask, k, newSize, newArray,
383 newBitMask, factor, finc);
385 organizeArray(toFill, j, node2.size, node2.array, node2.bitMask,
386 k, newSize, newArray, newBitMask, factor, finc);
391 newArray[k] = toFill;
392 newBitMask |= (1ULL<<k);
397 capacity = newCapacity;
399 bitMask = newBitMask;
406 cxuint newSize0 = (size+1)>>1;
407 cxuint newSize1 = size-newSize0;
408 cxuint newCapacity0 = std::min(
409 cxbyte(newSize0 + (newSize0>>freePlacesShift)),
410 cxbyte(maxNode0Capacity));
411 cxuint newCapacity1 = std::min(
412 cxbyte(newSize1 + (newSize1>>freePlacesShift)),
413 cxbyte(maxNode0Capacity));
414 std::unique_ptr<AT[]> newArray0 =
nullptr;
415 std::unique_ptr<AT[]> newArray1 =
nullptr;
416 if (newCapacity0 != 0)
417 newArray0.reset(
new AT[newCapacity0]);
418 if (newCapacity1 != 0)
419 newArray1.reset(
new AT[newCapacity1]);
420 uint64_t newBitMask0 = 0ULL;
421 uint64_t newBitMask1 = 0ULL;
427 cxuint finc = newCapacity0 - newSize0;
429 organizeArray(toFill, i, newSize0, array, bitMask, k, newSize0,
430 newArray0.get(), newBitMask0, factor, finc);
433 if (k < newCapacity0)
435 newArray0[k] = toFill;
436 newBitMask0 |= (1ULL<<k);
443 finc = newCapacity1 - newSize1;
445 organizeArray(toFill, i, newSize1, array, bitMask,
446 k, newSize1, newArray1.get(), newBitMask1, factor, finc);
449 if (k < newCapacity1)
451 newArray1[k] = toFill;
452 newBitMask1 |= (1ULL<<k);
457 array = newArray0.release();
458 capacity = newCapacity0;
460 bitMask = newBitMask0;
462 delete[] node2.array;
464 node2.array = newArray1.release();
465 node2.capacity = newCapacity1;
466 node2.size = newSize1;
467 node2.bitMask = newBitMask1;
475 cxuint newCapacity = std::min(
476 cxbyte(size+extraSize + ((size+extraSize)>>freePlacesShift)),
477 cxbyte(maxNode0Capacity));
478 AT* newArray =
nullptr;
479 if (newCapacity != 0)
480 newArray =
new AT[newCapacity];
482 uint64_t newBitMask = 0ULL;
484 const cxuint finc = newCapacity - size;
489 organizeArray(toFill, i, size, array, bitMask, j, size, newArray,
490 newBitMask, factor, finc);
494 newArray[j] = toFill;
495 newBitMask |= (1ULL<<j);
500 capacity = newCapacity;
501 bitMask = newBitMask;
506 std::pair<cxuint, bool>
insert(
const T& v,
const Comp& comp,
507 const KeyOfVal& kofval)
510 idx = lower_boundFree(kofval(v), comp, kofval);
512 if (idx < capacity && (bitMask & (1ULL<<idx))==0 &&
513 !comp(kofval(v), kofval(array[idx])))
515 return std::make_pair(idx,
false);
517 cxuint minFreePlaces = ((size+1)>>minFreePlacesShift);
518 if ((size+1) + minFreePlaces > capacity)
521 idx = lower_boundFree(kofval(v), comp, kofval);
524 if ((bitMask & (1ULL<<idx)) == 0)
527 const uint64_t leftMask = bitMask & ((1ULL<<idx)-1U);
528 const uint64_t rightMask = bitMask & ~((2ULL<<idx)-1U);
532 cxuint leftLen = 255, rightLen = 255;
534 leftLen = idx-(63-
CLZ64(leftMask));
536 rightLen =
CTZ64(rightMask)-idx;
538 if (leftLen >= rightLen)
541 cxuint k = idx + rightLen;
542 bitMask &= ~(1ULL<<k);
544 array[k] = array[k-1];
550 bitMask &= ~(1ULL<<k);
551 for (; k < idx-1; k++)
552 array[k] = array[k+1];
556 while ((bitMask & (1U<<firstPos)) != 0)
565 bitMask &= ~(1ULL<<idx);
568 firstPos = std::min(
cxuint(firstPos), idx);
569 return std::make_pair(idx,
true);
575 if ((bitMask & (1ULL<<index)) != 0)
577 bitMask |= (1ULL<<index);
580 cxuint maxFreePlaces = ((size+1)>>freePlacesShift);
581 if (size + maxFreePlaces < capacity)
583 else if (index == firstPos)
584 while ((bitMask & (1U<<firstPos)) != 0)
590 bool erase(
const K& k,
const Comp& comp,
const KeyOfVal& kofval)
592 cxuint index = lower_bound(k, comp, kofval);
593 if (index >= capacity || comp(k, kofval(array[index])))
613 Node1():
NodeBase(NODE1), index(255), size(0), capacity(0), totalSize(0),
614 first(), array(nullptr)
620 if (array !=
nullptr)
622 if (NodeBase::type == NODE1)
624 for (
cxuint i = 0; i < capacity; i++)
626 delete[] (
reinterpret_cast<cxbyte*
>(array) - parentEntrySize);
630 for (
cxuint i = 0; i < capacity; i++)
632 delete[] (
reinterpret_cast<cxbyte*
>(array1) - parentEntrySize);
641 if (NodeBase::type == NODE1)
644 if (node.array !=
nullptr)
647 capacity*
sizeof(
Node0)];
649 array =
reinterpret_cast<Node0*
>(arrayData + parentEntrySize);
651 *
reinterpret_cast<Node1**
>(arrayData) =
this;
652 for (
cxuint i = 0; i < capacity; i++)
653 new (array+i)
Node0();
654 std::copy(node.array, node.array+size, array);
660 if (node.
array1 !=
nullptr)
663 capacity*
sizeof(
Node1)];
665 array1 =
reinterpret_cast<Node1*
>(arrayData + parentEntrySize);
667 *
reinterpret_cast<Node1**
>(arrayData) =
this;
668 for (
cxuint i = 0; i < capacity; i++)
669 new (array1+i)
Node1();
677 totalSize(node.
totalSize), first(node.first), array(
nullptr)
684 totalSize(node.
totalSize), first(node.first), array(node.array)
686 if (array !=
nullptr)
687 reinterpret_cast<Node1**
>(array)[parentEntryIndex] =
this;
688 node.array =
nullptr;
693 :
NodeBase(NODE1), index(255), size(2), capacity(2),
694 totalSize(n0.size+n1.size), first(kofval(n0.array[n0.firstPos])),
698 array =
reinterpret_cast<Node0*
>(arrayData + parentEntrySize);
699 new (array+0)
Node0();
700 new (array+1)
Node0();
701 *
reinterpret_cast<Node1**
>(arrayData) =
this;
702 array[0] = std::move(n0);
703 array[1] = std::move(n1);
709 size(2), capacity(2), totalSize(n0.totalSize+n1.totalSize),
710 first(n0.first), array(nullptr)
713 array1 =
reinterpret_cast<Node1*
>(arrayData + parentEntrySize);
714 new (array1+0)
Node1();
715 new (array1+1)
Node1();
716 *
reinterpret_cast<Node1**
>(arrayData) =
this;
717 array1[0] = std::move(n0);
718 array1[1] = std::move(n1);
730 NodeBase::type = node.NodeBase::type;
743 NodeBase::type = node.NodeBase::type;
749 if (array !=
nullptr)
750 reinterpret_cast<Node1**
>(array)[parentEntryIndex] =
this;
752 node.array =
nullptr;
756 Node0* getFirstNode0()
759 while (cur->NodeBase::type == NODE2)
764 const Node0* getFirstNode0()
const 766 const Node1* cur =
this;
767 while (cur->NodeBase::type == NODE2)
772 Node0* getLastNode0()
775 while (cur->NodeBase::type == NODE2)
777 return cur->array + cur->
size - 1;
780 const Node0* getLastNode0()
const 782 const Node1* cur =
this;
783 while (cur->NodeBase::type == NODE2)
785 return cur->array + cur->
size - 1;
790 {
return index!=255U ?
791 reinterpret_cast<Node1*
const *
>(
this-index)[parentEntryIndex] :
nullptr; }
795 {
return index!=255U ?
796 reinterpret_cast<Node1**
>(
this-index)[parentEntryIndex] :
nullptr; }
802 *
reinterpret_cast<Node1**
>(newData) =
this;
803 Node0* newArray =
reinterpret_cast<Node0*
>(newData + parentEntrySize);
805 for (
cxuint i = 0; i < newCapacity; i++)
806 new (newArray+i)
Node0();
807 if (array !=
nullptr)
809 for (
cxuint i = 0; i < size; i++)
811 delete[] (
reinterpret_cast<cxbyte*
>(array) - parentEntrySize);
816 capacity = newCapacity;
825 *
reinterpret_cast<Node1**
>(newData) =
this;
826 Node1* newArray =
reinterpret_cast<Node1*
>(newData + parentEntrySize);
828 for (
cxuint i = 0; i < newCapacity; i++)
829 new (newArray+i)
Node1();
830 if (array !=
nullptr)
832 for (
cxuint i = 0; i < size; i++)
834 delete[] (
reinterpret_cast<cxbyte*
>(array1) - parentEntrySize);
839 capacity = newCapacity;
849 *
reinterpret_cast<Node1**
>(newData) =
this;
850 Node0* newArray =
reinterpret_cast<Node0*
>(newData + parentEntrySize);
852 for (
cxuint i = 0; i < newCapacity; i++)
853 new (newArray+i)
Node0();
855 if (array !=
nullptr)
857 for (
cxuint i = newSize; i < size; i++)
859 totalSize -= array[i].size;
862 std::move(array, array + newSize, newArray);
863 delete[] (
reinterpret_cast<cxbyte*
>(array) - parentEntrySize);
867 capacity = newCapacity;
878 *
reinterpret_cast<Node1**
>(newData) =
this;
879 Node1* newArray =
reinterpret_cast<Node1*
>(newData + parentEntrySize);
881 for (
cxuint i = 0; i < newCapacity; i++)
882 new (newArray+i)
Node1();
884 if (array !=
nullptr)
886 for (
cxuint i = newSize; i < size; i++)
888 totalSize -= array1[i].totalSize;
891 std::move(array1, array1 + newSize, newArray);
892 delete[] (
reinterpret_cast<cxbyte*
>(array1) - parentEntrySize);
896 capacity = newCapacity;
908 if (NodeBase::type == NODE1)
915 if (comp(kofval(array[m].array[array[m].firstPos]), v))
921 if (comp(kofval(array[l].array[array[l].firstPos]), v))
929 return !comp(array1[0].first, v) ? 0 : 1;
935 if (comp(array1[m].first, v))
941 if (comp(array1[l].first, v))
952 if (NodeBase::type == NODE1)
959 if (comp(v, kofval(array[m].array[array[m].firstPos])))
965 if (!comp(v, kofval(array[l].array[array[l].firstPos])))
976 if (comp(v, array1[m].first))
982 if (!comp(v, array1[l].first))
990 bool updateTotSize =
true)
992 NodeBase::type = NODE1;
993 if (size+1 > capacity)
994 reserve0(std::min(std::max(capacity + (capacity>>1), size+1),
997 for (
size_t i = size; i > index; i--)
999 array[i] = std::move(array[i-1]);
1003 array[index] = std::move(node);
1004 array[index].index = index;
1005 if (index == 0 && array[0].array!=
nullptr)
1006 first = kofval(array[0].array[array[0].firstPos]);
1009 totalSize += node.
size;
1015 NodeBase::type = NODE2;
1016 if (size+1 > capacity)
1017 reserve1(std::min(std::max(capacity + (capacity>>1), size+1),
1018 int(maxNode1Size)));
1020 for (
size_t i = size; i > index; i--)
1022 array1[i] = std::move(array1[i-1]);
1023 array1[i].index = i;
1026 array1[index] = std::move(node);
1027 array1[index].index = index;
1029 first = array1[0].first;
1039 totalSize -= array[index].size;
1040 std::move(array+index+1, array+size, array+index);
1041 if (size == index+1)
1043 array[size-1].~Node0();
1044 array[size-1].array =
nullptr;
1046 for (
cxuint i = index; i < size-1U; i++)
1048 if (size > 1 && index == 0)
1049 first = kofval(array[0].array[array[0].firstPos]);
1051 if (size + (size>>1) < capacity)
1061 totalSize -= array1[index].totalSize;
1062 std::move(array1+index+1, array1+size, array1+index);
1063 if (size == index+1)
1065 array1[size-1].~Node1();
1066 array1[size-1].array =
nullptr;
1068 for (
cxuint i = index; i < size-1U; i++)
1069 array1[i].index = i;
1070 if (size > 1 && index == 0)
1071 first = array1[0].first;
1073 if (size + (size>>1) < capacity)
1079 void reorganizeNode0s(
cxuint start,
cxuint end,
bool removeOneNode0 =
false)
1081 Node0 temps[maxNode1Size];
1083 for (
cxuint i = start; i < end; i++)
1084 nodesSize += array[i].size;
1086 cxuint newNodeSize = nodesSize / (end-start - removeOneNode0);
1087 cxuint withExtraElem = nodesSize - newNodeSize*(end-start - removeOneNode0);
1093 cxuint newSize = newNodeSize + (ni < withExtraElem);
1094 temps[ni].allocate(newSize);
1095 temps[ni].index = start + ni;
1097 for (
cxuint i = start; i < end; i++)
1099 inPos = inIndex = 0;
1100 while(inIndex < array[i].capacity)
1102 temps[ni].assignArray(toFill, array[i].size, inIndex, inPos,
1103 array[i].array, array[i].bitMask, newSize, k, factor);
1104 if (inPos < array[i].size)
1107 if (k < temps[ni].capacity)
1109 temps[ni].array[k] = toFill;
1110 temps[ni].bitMask |= (1ULL<<k);
1115 newSize = newNodeSize + (ni < withExtraElem);
1118 temps[ni].allocate(newSize);
1119 temps[ni].index = start + ni;
1125 std::move(temps, temps + end-start - removeOneNode0, array+start);
1128 std::move(array + end, array + size, array + end - 1);
1135 void merge(
Node1&& n2)
1138 if ((n2.size != 0 && n2.NodeBase::type == NODE1) ||
1139 (size != 0 && NodeBase::type == NODE1))
1141 reserve0(std::max(
cxuint(maxNode1Size),
cxuint(capacity + n2.capacity)));
1142 std::move(n2.array, n2.array + n2.size, array + size);
1143 for (
cxuint i = size; i < size+n2.size; i++)
1148 NodeBase::type = NODE2;
1149 reserve1(std::max(
cxuint(maxNode1Size),
cxuint(capacity + n2.capacity)));
1150 std::move(n2.array1, n2.array1 + n2.size, array1 + size);
1151 for (
cxuint i = size; i < size+n2.size; i++)
1152 array1[i].index = i;
1154 totalSize += n2.totalSize;
1160 void splitNode(
Node1& n2,
const KeyOfVal& kofval)
1162 if (NodeBase::type == NODE1)
1165 size_t halfTotSize = 0;
1166 for (; halfPos < size && halfTotSize < (totalSize>>1); halfPos++)
1167 halfTotSize += array[halfPos].size;
1168 if ((halfTotSize - (totalSize>>1)) > size_t(array[halfPos-1].size>>1))
1171 halfTotSize -= array[halfPos].size;
1174 cxuint newSize2 = size - halfPos;
1175 size_t secHalfTotSize = totalSize - halfTotSize;
1177 std::move(array + halfPos, array + size, n2.array);
1179 n2.first = kofval(n2.array[0].array[n2.array[0].firstPos]);
1180 for (
cxuint i = 0; i < newSize2; i++)
1181 n2.array[i].index = i;
1188 size_t halfTotSize = 0;
1189 for (; halfPos < size && halfTotSize < (totalSize>>1); halfPos++)
1190 halfTotSize += array1[halfPos].totalSize;
1191 if ((halfTotSize - (totalSize>>1)) > (array1[halfPos-1].totalSize>>1))
1194 halfTotSize -= array1[halfPos].totalSize;
1197 n2.NodeBase::type = NODE2;
1198 cxuint newSize2 = size - halfPos;
1199 size_t secHalfTotSize = totalSize - halfTotSize;
1201 std::move(array1 + halfPos, array1 + size, n2.
array1);
1203 n2.first = n2.
array1[0].first;
1204 for (
cxuint i = 0; i < newSize2; i++)
1211 void reorganizeNode1s(
cxuint start,
cxuint end,
const KeyOfVal& kofval,
1212 bool removeOneNode1 =
false)
1214 Node1 temps[maxNode1Size];
1216 size_t nodesTotSize = 0;
1217 for (
cxuint i = start; i < end; i++)
1219 node0sNum += array1[i].
size;
1220 nodesTotSize += array1[i].totalSize;
1223 const cxuint end2 = end - removeOneNode1;
1227 cxuint remaining = end2-start-1;
1228 for (
cxuint i = 0; i < end2-start; i++, remaining--)
1230 temps[i].
index = start+i;
1231 cxuint newNodeSize = nodesTotSize / (end2-start-i);
1232 for (; j < end; j++)
1234 const Node1& child = array1[j];
1235 if (child.type == NODE2)
1236 for (; k < child.
size && temps[i].
size < maxNode1Size &&
1237 (temps[i].
size < 2 ||
1238 (node0sNum-node0Count > remaining*maxNode1Size) ||
1241 newNodeSize); k++, node0Count++)
1243 if (node0sNum-node0Count <= (remaining<<1))
1250 for (; k < child.
size && temps[i].
size < maxNode1Size &&
1251 (temps[i].
size < 2 ||
1252 (node0sNum-node0Count > remaining*maxNode1Size) ||
1254 temps[i].totalSize+(child.array[k].size>>1) < newNodeSize);
1257 if (node0sNum-node0Count <= (remaining<<1))
1261 temps[i].
size, kofval);
1264 if (k >= child.
size)
1274 std::move(temps, temps + end-start - removeOneNode1, array1+start);
1277 std::move(array1 + end, array1 + size, array1 + end - 1);
1279 array1[i].index = i;
1285 static const size_t MaxNode01Size =
sizeof(
Node0) <
sizeof(
Node1) ?
1288 static const size_t NodeVElemsNum = (MaxNode01Size -
1290 (2 <
alignof(T) ?
alignof(T) : 2)) /
sizeof(T);
1296 AT array[NodeVElemsNum];
1297 T arrayOut[NodeVElemsNum];
1304 { std::copy(nv.array, nv.array + nv.size, array); }
1306 { std::copy(nv.array, nv.array + nv.size, array); }
1310 NodeBase::type = nv.NodeBase::type;
1312 std::copy(nv.array, nv.array + nv.size, array);
1317 NodeBase::type = nv.NodeBase::type;
1319 std::copy(nv.array, nv.array + nv.size, array);
1323 void assignNode0(
const Node0& n0)
1327 for (
cxuint i = 0; j < size; i++)
1328 if ((n0.bitMask & (1ULL<<i)) == 0)
1329 array[j++] = n0.array[i];
1333 {
return size >= NodeVElemsNum; }
1335 cxuint lower_bound(
const K& key,
const Comp& comp,
const KeyOfVal& kofval)
const 1338 for (; index < size && comp(kofval(array[index]), key); index++);
1342 cxuint upper_bound(
const K& key,
const Comp& comp,
const KeyOfVal& kofval)
const 1345 for (; index < size && !comp(key, kofval(array[index])); index++);
1349 cxuint find(
const K& key,
const Comp& comp,
const KeyOfVal& kofval)
const 1352 for (; index < size && comp(kofval(array[index]), key); index++);
1353 if (index < size && !comp(key, kofval(array[index])))
1359 std::pair<cxuint, bool> insert(
const T& v,
1360 const Comp& comp,
const KeyOfVal& kofval)
1362 const K key = kofval(v);
1363 cxuint index = lower_bound(key, comp, kofval);
1364 if (index < size && !comp(key, kofval(array[index])))
1366 return std::make_pair(index,
false);
1368 std::copy_backward(array + index, array + size, array + size + 1);
1371 return std::make_pair(index,
true);
1376 std::copy(array + index + 1, array + size, array + index);
1380 const AT& operator[](
cxuint i)
const 1381 {
return array[i]; }
1384 {
return array[i]; }
1390 typedef T value_type;
1400 IterBase() : cn0(nullptr), index(0)
1416 if (n0->type != NODE0)
1419 n0 =
reinterpret_cast<Node1*
>(n0)->getLastNode0();
1427 if (n0->type == NODEV)
1435 while (index < n0->capacity && inc != 0)
1437 if ((n0->bitMask & (1ULL<<index)) == 0)
1441 while (index < n0->capacity && (n0->bitMask & (1ULL<<index)) != 0)
1446 if (index >= n0->capacity)
1448 const Node1* n[maxNode1Depth];
1451 if (n[1] !=
nullptr)
1455 for (; n0 < n[1]->array+n[1]->
size; n0++)
1456 if (n0->size <= inc)
1461 if (n0 - n[1]->array >= n[1]->size)
1464 for (; i < 20 ; i++)
1467 if (n[i+1] ==
nullptr)
1469 cn0 =
reinterpret_cast<const Node0*
>(n[i]);
1476 for (; n[i] < n[i+1]->
array1+n[i+1]->
size; n[i]++)
1477 if (n[i]->totalSize <= inc)
1483 if (n[i] - n[i+1]->array1 < n[i+1]->size)
1489 if (n[i+1] !=
nullptr)
1494 for (; n[i-1] < n[i]->
array1+n[i]->
size; n[i-1]++)
1495 if (n[i-1]->totalSize <= inc)
1500 if (n[2] !=
nullptr)
1504 for (; n0 < n[1]->array+n[1]->
size; n0++)
1505 if (n0->size <= inc)
1516 index = n0->firstPos;
1525 while (index < n0->capacity && inc != 0)
1527 if ((n0->bitMask & (1ULL<<index)) == 0)
1532 while (index < n0->capacity && (n0->bitMask & (1ULL<<index)) != 0)
1540 if (index >= n0->capacity)
1542 const Node1* n[maxNode1Depth];
1545 if (n[1] !=
nullptr)
1548 if (n0 - n[1]->array >= n[1]->size)
1552 for (; i < 20 ; i++)
1555 if (n[i+1] ==
nullptr)
1558 cn0 =
reinterpret_cast<const Node0*
>(n[i]);
1564 if (n[i] - n[i+1]->array1 < n[i+1]->size)
1571 if (n[i+1] !=
nullptr)
1574 if (n[2] !=
nullptr)
1584 index = n0->firstPos;
1594 if (n0->type == NODEV)
1604 while (index < n0->capacity && (n0->bitMask & (1ULL<<index)) != 0)
1613 if (n0->type == NODEV)
1620 while (index != UINT_MAX && inc != 0)
1622 if (index==n0->capacity || (n0->bitMask & (1ULL<<index)) == 0)
1626 while (index != UINT_MAX &&
1627 (index != n0->capacity && (n0->bitMask & (1ULL<<index)) != 0))
1631 if (index == UINT_MAX)
1633 const Node1* n[maxNode1Depth];
1636 if (n[1] !=
nullptr)
1640 for (; n0 >= n[1]->array; n0--)
1641 if (n0->size <= inc)
1645 if (n0 - n[1]->array < 0)
1648 for (; i < 20 ; i++)
1651 if (n[i+1] ==
nullptr)
1658 for (; n[i] >= n[i+1]->
array1; n[i]--)
1659 if (n[i]->totalSize <= inc)
1663 if (n[i] - n[i+1]->array1 >= 0)
1667 if (n[i+1] !=
nullptr)
1677 for (; n[i-1] >= n[i]->
array1; n[i-1]--)
1678 if (n[i-1]->totalSize <= inc)
1683 if (n[2] !=
nullptr)
1689 n0 = n[1]->array + n[1]->
size-1;
1690 for (; n0 >= n[1]->array; n0--)
1691 if (n0->size <= inc)
1700 index = n0->capacity-1;
1712 while (index != UINT_MAX && inc != 0)
1714 if ((n0->bitMask & (1ULL<<index)) == 0)
1719 while (index != UINT_MAX && (n0->bitMask & (1ULL<<index)) != 0)
1727 if (n0->type == NODEV)
1735 while (index != UINT_MAX &&
1736 (index != n0->capacity && (n0->bitMask & (1ULL<<index)) != 0))
1740 if (index == UINT_MAX)
1742 const Node1* n[maxNode1Depth];
1745 if (n[1] !=
nullptr)
1748 if (n0 - n[1]->array < 0)
1751 for (; i < 20 ; i++)
1754 if (n[i+1] ==
nullptr)
1760 if (n[i] - n[i+1]->array1 >= 0)
1765 if (n[i+1] !=
nullptr && !end)
1768 if (n[2] !=
nullptr && !end)
1770 n0 = n[1]->array + n[1]->
size-1;
1773 index = n0->capacity-1;
1784 while (index != UINT_MAX && (n0->bitMask & (1ULL<<index)) != 0)
1800 if (n0->type == NODEV)
1801 return index - k2.
index;
1814 for (
cxuint i = index1; i < index2; i++)
1815 if ((i1.n0->bitMask & (1ULL<<i)) == 0)
1817 return index2 == i1.
index ? count : -count;
1819 const Node1* n1[maxNode1Depth];
1820 const Node1* n2[maxNode1Depth];
1821 const Node0* xn0_1 = i1.n0;
1822 const Node0* xn0_2 = i2.n0;
1830 while (n1[i] != n2[i])
1833 n1[i] = n1[i-1]->
parent();
1834 n2[i] = n2[i-1]->
parent();
1837 bool negate =
false;
1839 if ((i==0 && xn0_2->index < xn0_1->index) ||
1843 std::swap_ranges(n1, n1+i+1, n2);
1844 std::swap(xn0_1, xn0_2);
1845 std::swap(index1, index2);
1851 for (
cxuint j = xn0_1->index+1; j < xn0_2->index; j++)
1852 count += n1[i]->array[j].size;
1856 for (
cxuint j = n1[i-1]->index+1; j < n2[i-1]->
index; j++)
1857 count += n1[i]->array1[j].totalSize;
1859 for (i--; i >= 1; i--)
1862 for (
cxuint j = n1[i-1]->index+1; j < n1[i]->
size; j++)
1863 count += n1[i]->array1[j].totalSize;
1866 count += n2[i]->array1[j].totalSize;
1869 for (
cxuint j = xn0_1->index+1; j < n1[0]->
size; j++)
1870 count += n1[0]->array[j].size;
1872 for (
cxuint j = 0; j < xn0_2->index; j++)
1873 count += n2[0]->array[j].size;
1877 for (
cxuint j = index1; j < xn0_1->capacity; j++)
1878 if ((xn0_1->bitMask & (1ULL<<j)) == 0)
1881 for (
cxuint j = 0; j < index2; j++)
1882 if ((xn0_2->bitMask & (1ULL<<j)) == 0)
1885 return negate ? -count : count;
1892 typedef T value_type;
1893 typedef T& reference;
1895 typedef ssize_t difference_type;
1896 typedef std::bidirectional_iterator_tag iterator_category;
1912 Iter operator++(
int)
1922 tmp.IterBase::step(i);
1948 tmp.IterBase::step(-i);
1958 ssize_t operator-(
const IterBase& i2)
const 1959 {
return IterBase::diff(i2); }
1963 return (IterBase::n0->type == NODE0) ?
1964 IterBase::n0->arrayOut[IterBase::index] :
1965 IterBase::nv->arrayOut[IterBase::index];
1970 return (IterBase::n0->type == NODE0) ?
1971 IterBase::n0->arrayOut + IterBase::index :
1972 IterBase::nv->arrayOut + IterBase::index;
1976 {
return IterBase::n0==it.n0 && IterBase::index==it.
index; }
1979 {
return IterBase::n0!=it.n0 || IterBase::index!=it.
index; }
1985 typedef T value_type;
1986 typedef const T& reference;
1987 typedef const T* pointer;
1988 typedef ssize_t difference_type;
1989 typedef std::bidirectional_iterator_tag iterator_category;
2015 tmp.IterBase::step(i);
2041 tmp.IterBase::step(-i);
2052 ssize_t operator-(
const IterBase& i2)
const 2053 {
return IterBase::diff(i2); }
2057 return (IterBase::n0->type == NODE0) ?
2058 IterBase::n0->arrayOut[IterBase::index] :
2059 IterBase::nv->arrayOut[IterBase::index];
2064 return (IterBase::n0->type == NODE0) ?
2065 IterBase::n0->arrayOut + IterBase::index :
2066 IterBase::nv->arrayOut + IterBase::index;
2070 {
return IterBase::n0==it.n0 && IterBase::index==it.
index; }
2073 {
return IterBase::n0!=it.n0 || IterBase::index!=it.
index; }
2075 #ifdef DTREE_TESTING 2089 typedef T value_type;
2093 DTree(
const Comp& comp = Comp(),
const KeyOfVal& kofval = KeyOfVal())
2094 : Comp(comp), KeyOfVal(kofval), nv()
2098 DTree(
const Node0& node0,
const Comp& comp = Comp(),
2099 const KeyOfVal& kofval = KeyOfVal()) : Comp(comp), KeyOfVal(kofval), n0(node0)
2102 DTree(
const Node1& node1,
const Comp& comp = Comp(),
2103 const KeyOfVal& kofval = KeyOfVal()) : Comp(comp), KeyOfVal(kofval), n1(node1)
2106 template<
typename Iter>
2108 DTree(Iter first, Iter last,
const Comp& comp = Comp(),
2109 const KeyOfVal& kofval = KeyOfVal()) : Comp(comp), KeyOfVal(kofval), nv()
2111 for (Iter it = first; it != last; ++it)
2116 DTree(std::initializer_list<value_type> init,
const Comp& comp = Comp(),
2117 const KeyOfVal& kofval = KeyOfVal()) : Comp(comp), KeyOfVal(kofval), nv()
2119 for (
const value_type& v: init)
2125 if (dt.nv.type == NODEV)
2127 else if (dt.n0.type == NODE0)
2141 if (dt.nv.type == NODEV)
2143 else if (dt.n0.type == NODE0)
2146 n0 = std::move(dt.n0);
2151 n1 = std::move(dt.n1);
2157 if (n0.type == NODE0)
2159 else if (n0.type != NODEV)
2168 if (n0.type == NODE0)
2170 else if (n0.type != NODEV)
2173 if (dt.n0.type == NODEV)
2175 else if (dt.n0.type == NODE0)
2192 if (n0.type == NODE0)
2194 else if (n0.type != NODEV)
2197 if (dt.n0.type == NODEV)
2199 else if (dt.n0.type == NODE0)
2202 n0 = std::move(dt.n0);
2207 n1 = std::move(dt.n1);
2217 {
return (n0.type==NODE0 && n0.size==0) || (nv.type==NODEV && nv.size==0); }
2224 return n0.type==NODE0 ? n0.size : n1.totalSize;
2230 if (n0.type == NODE0)
2232 else if (n0.type != NODEV)
2238 IterBase findInt(
const key_type& key)
const 2240 if (n0.type == NODEV)
2241 return IterBase{&n0, nv.find(key, *
this, *
this)};
2243 if (n0.type == NODE0)
2244 return IterBase{&n0, n0.find(key, *
this, *
this)};
2245 const Node1* curn1 = &n1;
2247 while (curn1->type == NODE2)
2249 index = curn1->upperBoundN(key, *
this, *
this);
2252 curn1 = curn1->array1 + index - 1;
2255 index = curn1->upperBoundN(key, *
this, *
this);
2258 const Node0* curn0 = curn1->array + index - 1;
2260 IterBase it{curn0, curn0->find(key, *
this, *
this)};
2261 if (it.index == curn0->capacity)
2266 IterBase lower_boundInt(
const key_type& key)
const 2268 if (n0.type == NODEV)
2269 return IterBase{&n0, nv.lower_bound(key, *
this, *
this)};
2271 if (n0.type == NODE0)
2272 return IterBase{&n0, n0.lower_bound(key, *
this, *
this)};
2273 const Node1* curn1 = &n1;
2275 while (curn1->type == NODE2)
2277 index = curn1->upperBoundN(key, *
this, *
this);
2280 curn1 = curn1->array1 + index - 1;
2283 index = curn1->upperBoundN(key, *
this, *
this);
2286 const Node0* curn0 = curn1->array + index - 1;
2288 IterBase it{curn0, curn0->lower_bound(key, *
this, *
this)};
2289 if (it.index == curn0->capacity)
2294 IterBase upper_boundInt(
const key_type& key)
const 2296 if (n0.type == NODEV)
2297 return IterBase{&n0, nv.upper_bound(key, *
this, *
this)};
2299 if (n0.type == NODE0)
2300 return IterBase{&n0, n0.upper_bound(key, *
this, *
this)};
2301 const Node1* curn1 = &n1;
2303 while (curn1->type == NODE2)
2305 index = curn1->upperBoundN(key, *
this, *
this);
2308 curn1 = curn1->array1 + index - 1;
2310 index = curn1->upperBoundN(key, *
this, *
this);
2313 const Node0* curn0 = curn1->array + index - 1;
2315 IterBase it{curn0, curn0->upper_bound(key, *
this, *
this)};
2316 if (it.index == curn0->capacity)
2324 {
return findInt(key); }
2326 const_iterator
find(
const key_type& key)
const 2327 {
return findInt(key); }
2332 if (nv.type == NODEV)
2333 return iterator(&n0, 0);
2334 if (n0.type == NODE0)
2335 return iterator(&n0, n0.firstPos);
2338 iterator it(n1.getFirstNode0());
2339 it.index = it.n0->firstPos;
2346 if (nv.type == NODEV)
2347 return const_iterator(&n0, 0);
2348 if (n0.type == NODE0)
2349 return const_iterator(&n0, n0.firstPos);
2352 const_iterator it(n1.getFirstNode0());
2353 it.index = it.n0->firstPos;
2359 {
return cbegin(); }
2363 if (nv.type == NODEV)
2364 return iterator(&n0, nv.size);
2365 return iterator(&n0, n0.type==NODE0 ? n0.capacity : n1.size);
2370 if (nv.type == NODEV)
2371 return const_iterator(&n0, nv.size);
2372 return const_iterator(&n0, n0.type==NODE0 ? n0.capacity : n1.size);
2377 if (nv.type == NODEV)
2378 return const_iterator(&n0, nv.size);
2379 return const_iterator(&n0, n0.type==NODE0 ? n0.capacity : n1.size);
2384 {
return lower_boundInt(key); }
2387 {
return lower_boundInt(key); }
2390 {
return upper_boundInt(key); }
2393 {
return upper_boundInt(key); }
2395 #ifdef DTREE_TESTING 2400 static void findReorgBounds0(
cxuint n0Index,
const Node1* curn1,
cxuint neededN0Size,
2401 cxint& left,
cxint& right,
bool* removeOneNode =
nullptr)
2404 left = right = n0Index;
2411 freeSpace += maxNode0Size - curn1->array[left].size;
2414 if (right < curn1->size)
2416 freeSpace += maxNode0Size - curn1->array[right].size;
2419 }
while (freeSpace < neededN0Size && (left >= 0 || right < curn1->size));
2421 left = std::max(0, left);
2422 right = std::min(curn1->size-1, right);
2423 if (removeOneNode !=
nullptr)
2424 *removeOneNode = freeSpace >= neededN0Size;
2427 static void findReorgBounds1(
const Node1* prevn1,
const Node1* curn1,
2428 size_t neededN1Size,
size_t maxN1Size,
cxint& left,
cxint& right,
2429 bool* removeOneNode =
nullptr)
2431 cxuint n1Index = prevn1->index;
2432 size_t freeSpace = 0;
2433 left = right = n1Index;
2434 cxuint children = prevn1->size;
2435 const size_t needed = neededN1Size + (neededN1Size>>2);
2442 freeSpace += maxN1Size -
2443 std::min(curn1->array1[left].totalSize, maxN1Size);
2444 children += curn1->array1[left].size;
2446 if (right < curn1->size)
2448 freeSpace += maxN1Size -
2449 std::min(curn1->array1[right].totalSize, maxN1Size);
2450 children += curn1->array1[right].size;
2452 }
while (freeSpace < needed && (left >= 0 || right < curn1->size));
2454 left = std::max(0, left);
2455 right = std::min(curn1->size-1, right);
2456 if (removeOneNode !=
nullptr)
2457 *removeOneNode = (freeSpace >= needed &&
2458 children < maxNode1Size*(right-left));
2463 std::pair<iterator, bool>
insert(
const value_type& value)
2465 if (nv.type == NODEV)
2469 auto res = nv.insert(value, *
this, *
this);
2470 return std::make_pair(iterator(&n0, res.first), res.second);
2478 n0.setFromArray(tmpnv.size, tmpnv.array);
2481 const key_type key = KeyOfVal::operator()(value);
2482 iterator it = lower_bound(key);
2485 const key_type itkey = KeyOfVal::operator()(*it);
2486 if (!Comp::operator()(key, itkey))
2487 return std::make_pair(it,
false);
2490 if (it.n0->type != NODE0)
2493 cxuint index = it.n0->insert(value, *
this, *
this).first;
2494 Node1* curn1 = it.n0->parent();
2495 iterator newit(it.n0, index);
2497 if (it.n0->size > maxNode0Size)
2500 cxuint n0Index = it.n0->index;
2501 if (curn1 ==
nullptr || curn1->size < maxNode1Size)
2505 it.n0->split(node0_2);
2507 bool secondNode =
false;
2508 if (Comp::operator()(key,
2509 KeyOfVal::operator()(node0_2.array[it.n0->firstPos])))
2511 index = it.n0->lower_bound(key, *
this, *
this);
2515 index = node0_2.lower_bound(key, *
this, *
this);
2517 if (curn1 ==
nullptr)
2519 Node1 node1(std::move(*it.n0), std::move(node0_2), *
this);
2521 n1 = std::move(node1);
2523 return std::make_pair(iterator(n1.array + secondNode, index),
true);
2525 curn1->insertNode0(std::move(node0_2), n0Index+1, *
this,
false);
2526 newit = iterator(curn1->array + n0Index + secondNode, index);
2532 findReorgBounds0(it.n0->index, curn1, it.n0->size, left, right);
2535 curn1->reorganizeNode0s(left, right+1);
2537 newit.n0 = curn1->array + curn1->upperBoundN(key, *
this, *
this) - 1;
2538 newit.index = newit.n0->lower_bound(key, *
this, *
this);
2543 Node1* prevn1 =
nullptr;
2544 while (curn1 !=
nullptr)
2547 curn1 = prevn1->parent();
2548 prevn1->first = prevn1->NodeBase::type==NODE1 ?
2549 KeyOfVal::operator()(
2550 prevn1->array[0].array[prevn1->array[0].firstPos]) :
2551 prevn1->array1[0].first;
2553 prevn1->totalSize++;
2554 cxuint maxN1Size = maxTotalSize(level);
2556 if (prevn1->totalSize > maxN1Size)
2558 cxuint n0Index = newit.n0->index;
2559 cxuint n1Index = prevn1->index;
2560 if (curn1 ==
nullptr || curn1->size < maxNode1Size)
2564 prevn1->splitNode(node1_2, *
this);
2568 if (n0Index < prevn1->size)
2569 newit.n0 = prevn1->array + n0Index;
2571 newit.n0 = node1_2.array + n0Index - prevn1->size;
2574 if (curn1 ==
nullptr)
2576 Node1 node1(std::move(*prevn1), std::move(node1_2));
2577 n1 = std::move(node1);
2580 curn1->insertNode1(std::move(node1_2), n1Index+1,
false);
2586 findReorgBounds1(prevn1, curn1, prevn1->totalSize,
2587 maxN1Size, left, right);
2589 curn1->reorganizeNode1s(left, right+1, *
this);
2592 const Node1* pn1 = curn1->array1 +
2593 curn1->upperBoundN(key, *
this, *
this) - 1;
2594 newit.n0 = pn1->array + pn1->upperBoundN(key, *
this, *
this) - 1;
2601 return std::make_pair(newit,
true);
2604 void insert(std::initializer_list<value_type> ilist)
2606 for (
const value_type& v: ilist)
2610 template<
typename Iter>
2611 void insert(Iter first, Iter last)
2613 for (Iter it = first; it != last; ++it)
2620 if (nv.type == NODEV)
2627 K key = KeyOfVal::operator()(*it);
2629 const_iterator newit(it);
2632 if (!it.n0->erase(it.index))
2636 newit.index = newit.n0->lower_bound(key, *
this, *
this);
2637 if (newit.n0->size != 0 && newit.index == newit.n0->firstPos)
2639 key = KeyOfVal::operator()(*newit);
2642 if (n0.size <= NodeVElemsNum)
2645 Node0 tmpn0 = std::move(n0);
2648 nv.assignNode0(tmpn0);
2653 Node1* curn1 = it.n0->parent();
2654 if (it.n0->size < minNode0Size)
2656 Node1* curn1 = it.n0->parent();
2657 const cxuint n0Index = it.n0->index;
2658 cxuint n0Left1 = n0Index > 0 ? curn1->array[n0Index-1].size : UINT_MAX;
2659 cxuint n0Right1 = n0Index+1 < curn1->size ? curn1->array[n0Index+1].size :
2661 cxuint mergedN0Index = UINT_MAX;
2662 if (n0Left1 < n0Right1)
2664 if (n0Left1+minNode0Size-1 <= maxNode0Size)
2666 curn1->array[n0Index-1].merge(*it.n0);
2667 curn1->eraseNode0(n0Index, *
this,
false);
2668 mergedN0Index = n0Index-1;
2669 newit.n0 = curn1->array + n0Index-1;
2670 newit.index = newit.n0->lower_bound(key, *
this, *
this);
2673 else if (n0Right1 != UINT_MAX)
2675 if (n0Right1+minNode0Size-1 <= maxNode0Size)
2677 it.n0->merge(curn1->array[n0Index+1]);
2678 curn1->eraseNode0(n0Index+1, *
this,
false);
2679 mergedN0Index = n0Index;
2680 newit.n0 = curn1->array + n0Index;
2681 newit.index = newit.n0->lower_bound(key, *
this, *
this);
2684 if (mergedN0Index == UINT_MAX)
2688 bool removeNode0 =
false;
2690 findReorgBounds0(n0Index, curn1, curn1->array[n0Index].size,
2691 left, right, &removeNode0);
2692 curn1->reorganizeNode0s(left, right+1, removeNode0);
2694 newit.n0 = curn1->array + curn1->upperBoundN(key, *
this, *
this) - 1;
2695 newit.index = newit.n0->lower_bound(key, *
this, *
this);
2698 if (newit.index == newit.n0->capacity)
2700 newit.toNextNode0();
2702 key = KeyOfVal::operator()(newit.n0->array[newit.n0->firstPos]);
2706 Node1* prevn1 =
nullptr;
2707 const Node1* newItN1 = newit.n0->parent();
2708 while (curn1 !=
nullptr)
2712 curn1 = prevn1->parent();
2713 prevn1->first = prevn1->NodeBase::type==NODE1 ?
2714 KeyOfVal::operator()(
2715 prevn1->array[0].array[prevn1->array[0].firstPos]) :
2716 prevn1->array1[0].first;
2718 cxuint maxN1Size = maxTotalSize(level);
2719 cxuint minN1Size = minTotalSize(level);
2720 if (curn1 ==
nullptr)
2722 if (prevn1->size == 1)
2725 if (prevn1->type == NODE1)
2727 Node0 tempN0 = std::move(prevn1->array[0]);
2730 n0 = std::move(tempN0);
2736 Node1 tempN1 = std::move(prevn1->array1[0]);
2739 n1 = std::move(tempN1);
2746 const cxuint n1Index = prevn1->index;
2747 size_t n1Left1 = n1Index > 0 ? curn1->array1[n1Index-1].totalSize : SIZE_MAX;
2748 size_t n1Right1 = n1Index+1 < curn1->size ?
2749 curn1->array1[n1Index+1].totalSize : SIZE_MAX;
2751 if (prevn1->totalSize >= minN1Size && prevn1->size > 1)
2758 if (n1Left1!=SIZE_MAX &&
2759 prevn1->size + curn1->array1[n1Index-1].size > maxNode1Size)
2761 if (n1Right1!=SIZE_MAX &&
2762 prevn1->size + curn1->array1[n1Index+1].size > maxNode1Size)
2763 n1Right1 = SIZE_MAX;
2765 cxuint mergedN1Index = UINT_MAX;
2766 if (n1Left1 < n1Right1 && n1Left1 != SIZE_MAX)
2768 if (n1Left1+minN1Size-1 <= maxN1Size)
2770 curn1->array1[n1Index-1].merge(std::move(*prevn1));
2771 curn1->eraseNode1(n1Index,
false);
2772 mergedN1Index = n1Index-1;
2773 if (level == 1 && newItN1 == prevn1)
2774 newit.n0 = curn1->array1[n1Index-1].array +
2775 curn1->array1[n1Index-1].upperBoundN(key, *
this, *
this) - 1;
2778 else if (n1Right1 != SIZE_MAX)
2780 if (n1Right1+minN1Size-1 <= maxN1Size)
2782 prevn1->merge(std::move(curn1->array1[n1Index+1]));
2783 curn1->eraseNode1(n1Index+1,
false);
2784 mergedN1Index = n1Index;
2785 if (level == 1 && newItN1 == prevn1)
2786 newit.n0 = curn1->array1[n1Index].array +
2787 curn1->array1[n1Index].upperBoundN(key, *
this, *
this) - 1;
2790 if (mergedN1Index == UINT_MAX)
2794 bool removeNode1 =
false;
2796 findReorgBounds1(prevn1, curn1, prevn1->totalSize, maxN1Size,
2797 left, right, &removeNode1);
2798 curn1->reorganizeNode1s(left, right+1, *
this, removeNode1);
2799 if (level == 1 && newItN1 == prevn1)
2801 const Node1* pn1 = curn1->array1 +
2802 curn1->upperBoundN(key, *
this, *
this) - 1;
2803 newit.n0 = pn1->array + pn1->upperBoundN(key, *
this, *
this) - 1;
2813 iterator it = find(key);
2821 void replace(iterator iter,
const value_type& value)
2825 if (iter != begin())
2827 iterator prevIt = iter;
2829 if (*prevIt >= value)
2830 throw std::out_of_range(
"Value out of range");
2832 iterator nextIt = iter;
2834 if (nextIt != end() && value >= *nextIt)
2835 throw std::out_of_range(
"Value out of range");
2837 if (iter.n0->type == NODE0)
2839 Node0* n0 = iter.n0;
2840 n0->array[iter.index] = value;
2842 for (
cxint i = iter.index-1; i >= 0 && (n0->bitMask & (1ULL<<i)) != 0; i--)
2843 n0->array[i] = value;
2844 for (
cxint i = iter.index+1; i < n0->capacity &&
2845 (n0->bitMask & (1ULL<<i)) != 0; i++)
2846 n0->array[i] = value;
2848 else if (iter.n0->type == NODEV)
2849 nv.array[iter.index] = value;
2854 {
return size()==dt.
size() && std::equal(begin(), end(), dt.
begin()); }
2857 {
return size()!=dt.
size() || !std::equal(begin(), end(), dt.
begin()); }
2860 {
return std::lexicographical_compare(begin(), end(), dt.
begin(), dt.
end()); }
2863 {
return !(dt < *
this); }
2866 {
return (dt < *
this); }
2869 {
return !(*
this < dt); }
2874 template<
typename T,
typename Comp = std::less<T> >
2880 typedef typename Impl::const_iterator const_iterator;
2881 typedef typename Impl::iterator iterator;
2882 typedef typename Impl::value_type value_type;
2883 typedef typename Impl::key_type key_type;
2888 #ifdef DTREE_TESTING 2889 DTreeSet(
const typename Impl::Node0& node0,
const Comp& comp = Comp())
2892 DTreeSet(
const typename Impl::Node1& node1,
const Comp& comp = Comp())
2896 template<
typename Iter>
2898 DTreeSet(Iter first, Iter last,
const Comp& comp = Comp()) :
2899 Impl(first, last, comp)
2902 DTreeSet(std::initializer_list<value_type> init,
const Comp& comp = Comp())
2908 template<
typename K,
typename V,
typename Comp = std::less<K> >
2914 std::pair<K, V> > Impl;
2916 typedef typename Impl::const_iterator const_iterator;
2917 typedef typename Impl::iterator iterator;
2918 typedef typename Impl::value_type value_type;
2919 typedef typename Impl::key_type key_type;
2920 typedef V mapped_type;
2926 template<
typename Iter>
2927 DTreeMap(Iter first, Iter last,
const Comp& comp = Comp()) :
2928 Impl(first, last, comp)
2931 DTreeMap(std::initializer_list<value_type> init,
const Comp& comp = Comp())
2936 void replace(iterator iter,
const value_type& value)
2938 if (iter == Impl::end())
2940 if (iter != Impl::begin())
2942 iterator prevIt = iter;
2944 if (prevIt->first >= value.first)
2945 throw std::out_of_range(
"Key out of range");
2947 iterator nextIt = iter;
2949 if (nextIt != Impl::end() && value.first >= nextIt->first)
2950 throw std::out_of_range(
"Key out of range");
2951 if (iter.n0->type == Impl::NODE0)
2953 typename Impl::Node0* n0 = iter.n0;
2954 n0->array[iter.index].first = value.first;
2955 n0->array[iter.index].second = value.second;
2957 for (
cxint i = iter.index-1; i >= 0 && (n0->bitMask & (1ULL<<i)) != 0; i--)
2958 n0->array[i].first = value.first;
2959 for (
cxint i = iter.index+1; i < n0->capacity &&
2960 (n0->bitMask & (1ULL<<i)) != 0; i++)
2961 n0->array[i].first = value.first;
2963 else if (iter.n0->type == Impl::NODEV)
2965 Impl::nv.array[iter.index].first = value.first;
2966 Impl::nv.array[iter.index].second = value.second;
2971 std::pair<iterator, bool>
put(
const value_type& value)
2973 auto res = Impl::insert(value);
2975 res.first->second = value.second;
2980 mapped_type&
at(
const key_type& key)
2982 iterator it = Impl::find(key);
2983 if (it == Impl::end())
2984 throw std::out_of_range(
"DTreeMap key not found");
2988 const mapped_type&
at(
const key_type& key)
const 2990 const_iterator it = Impl::find(key);
2991 if (it == Impl::end())
2992 throw std::out_of_range(
"DTreeMap key not found");
2998 iterator it = Impl::insert(std::pair<const K, V>(key, V())).first;
iterator end()
return iterator after last element
Definition: DTree.h:2361
bool operator<=(const DTree &dt) const
lexicograhical less or equal
Definition: DTree.h:2862
bool operator!=(const DTree &dt) const
lexicograhical not equal
Definition: DTree.h:2856
const T * operator->() const
get element
Definition: DTree.h:2062
main D-Tree container of the unique ordered elements (D-Tree is kind of the B-Tree) ...
Definition: DTree.h:75
Node1 * parent()
get parent node
Definition: DTree.h:226
~DTree()
destructor
Definition: DTree.h:2155
const_iterator find(const key_type &key) const
find element or return end iterator
Definition: DTree.h:2326
bool operator==(const IterBase &it) const
equal to
Definition: DTree.h:1975
void next()
go to next element
Definition: DTree.h:1592
cxbyte size
number of the nodes
Definition: DTree.h:603
iterator lower_bound(const key_type &key)
first element that not less than key
Definition: DTree.h:2383
DTreeMap(Iter first, Iter last, const Comp &comp=Comp())
constructor iterator ranges
Definition: DTree.h:2927
Node1(Node0 &&n0, Node0 &&n1, const KeyOfVal &kofval)
create from two Node0's
Definition: DTree.h:692
DTreeSet(Iter first, Iter last, const Comp &comp=Comp())
constructor iterator ranges
Definition: DTree.h:2898
DTree(const Comp &comp=Comp(), const KeyOfVal &kofval=KeyOfVal())
default constructor
Definition: DTree.h:2093
Node1 - main node that holds Node0's or Node1's.
Definition: DTree.h:600
DTree(DTree &&dt) noexcept
move constructor
Definition: DTree.h:2139
ConstIter & operator++()
pre-increment
Definition: DTree.h:1999
static void organizeArray(AT &toFill, cxuint &i, cxuint size, const AT *array, uint64_t inBitMask, cxuint &k, cxuint newSize, AT *out, uint64_t &outBitMask, cxuint &factor, cxuint finc)
internal routine to organize array with empty holes
Definition: DTree.h:283
bool erase(const K &k, const Comp &comp, const KeyOfVal &kofval)
erase element of value v
Definition: DTree.h:590
cxuint lowerBoundN(const K &v, const Comp &comp, const KeyOfVal &kofval) const
find node that hold first element not less than value
Definition: DTree.h:904
bool operator==(const DTree &dt) const
lexicograhical equal to
Definition: DTree.h:2853
Iter operator--(int)
post-decrement
Definition: DTree.h:1938
const Node1 * parent() const
get parent node
Definition: DTree.h:789
DTree & operator=(DTree &&dt) noexcept
move assignment
Definition: DTree.h:2188
Iter & operator--()
pre-decrement
Definition: DTree.h:1932
DTree set.
Definition: DTree.h:2875
const_iterator lower_bound(const key_type &key) const
first element that not less than key
Definition: DTree.h:2386
void insert(std::initializer_list< value_type > ilist)
insert new elements from initializer list
Definition: DTree.h:2604
void step(ssize_t i)
go to i element from current position
Definition: DTree.h:1789
Iter(Node0 *n0=nullptr, cxuint index=0)
constructor
Definition: DTree.h:1899
T * operator->() const
get element
Definition: DTree.h:1968
const_iterator begin() const
return iterator to first element
Definition: DTree.h:2358
DTree & operator=(std::initializer_list< value_type > init)
assignment of initilizer list
Definition: DTree.h:2212
const_iterator upper_bound(const key_type &key) const
first element that greater than key
Definition: DTree.h:2392
ConstIter(const Node0 *n0=nullptr, cxuint index=0)
constructor
Definition: DTree.h:1992
void split(Node0 &node2)
split this node and store in this node and node2
Definition: DTree.h:404
Node1 * parent()
get parent node
Definition: DTree.h:794
void prev(size_t inc)
go to inc previous element
Definition: DTree.h:1611
ConstIter operator--(int)
post-decrement
Definition: DTree.h:2031
iterator which allow to modify underlying element
Definition: DTree.h:1890
Node0 & operator=(Node0 &&node) noexcept
moving assigment
Definition: DTree.h:206
DTreeMap(std::initializer_list< value_type > init, const Comp &comp=Comp())
constructor with element ranges
Definition: DTree.h:2931
cxuint CTZ64(uint64_t v)
counts trailing zeroes for 64-bit unsigned integer. For zero behavior is undefined ...
Definition: Utilities.h:422
bool operator==(const IterBase &it) const
equal to
Definition: DTree.h:2069
size_t erase(const key_type &key)
remove element by key
Definition: DTree.h:2811
Iter & operator+=(ssize_t i)
add to iterator with assignment
Definition: DTree.h:1926
bool empty() const
return true if empty
Definition: DTree.h:2216
Node1 that holds Node0's.
Definition: DTree.h:82
DTree(Iter first, Iter last, const Comp &comp=Comp(), const KeyOfVal &kofval=KeyOfVal())
constructor with range assignment
Definition: DTree.h:2108
void reserve1(cxuint newCapacity)
reserve1 elements in Node0's array
Definition: DTree.h:874
void insertNode1(Node1 &&node, cxuint index, bool updateTotSize=true)
insert Node1 - (move to this node)
Definition: DTree.h:1013
cxuint upper_bound(const K &k, const Comp &comp, const KeyOfVal &kofval) const
get upper_bound (first index of element greater than value)
Definition: DTree.h:260
bool operator<(const DTree &dt) const
lexicograhical less
Definition: DTree.h:2859
DTree(const DTree &dt)
copy construcror
Definition: DTree.h:2123
Node1 that holds Node1's.
Definition: DTree.h:83
cxuint lower_bound(const K &k, const Comp &comp, const KeyOfVal &kofval) const
get lower_bound (first index of element not less than value)
Definition: DTree.h:248
void copyArray(const Node1 &node)
Definition: DTree.h:639
bool operator!=(const IterBase &it) const
not equal
Definition: DTree.h:1978
std::pair< iterator, bool > insert(const value_type &value)
insert new element
Definition: DTree.h:2463
void allocate0(cxuint newCapacity)
Definition: DTree.h:798
DTreeSet(const Comp &comp=Comp())
default constructor
Definition: DTree.h:2886
ConstIter operator++(int)
post-increment
Definition: DTree.h:2005
iterator upper_bound(const key_type &key)
first element that greater than key
Definition: DTree.h:2389
unsigned char cxbyte
unsigned byte
Definition: Config.h:229
const_iterator end() const
return iterator after last element
Definition: DTree.h:2368
std::pair< iterator, bool > put(const value_type &value)
put element, insert or replace if found
Definition: DTree.h:2971
ssize_t diff(const IterBase &k2) const
calculate distance between iterators
Definition: DTree.h:1798
iterator find(const key_type &key)
find element or return end iterator
Definition: DTree.h:2323
main namespace
Definition: AsmDefs.h:38
Node1(Node1 &&n0, Node1 &&n1)
create from two Node1's
Definition: DTree.h:708
DTree map.
Definition: DTree.h:2909
size_t size() const
return size
Definition: DTree.h:2220
bool operator>=(const DTree &dt) const
lexicograhical greater or equal
Definition: DTree.h:2868
DTreeMap(const Comp &comp=Comp())
default constructor
Definition: DTree.h:2923
unsigned int cxuint
unsigned int
Definition: Config.h:237
get element same as input
Definition: DTree.h:50
Node0 & operator=(const Node0 &node)
copying assignment
Definition: DTree.h:186
Node1 * array1
array hold Node0's
Definition: DTree.h:610
Select first element from pair.
Definition: DTree.h:40
cxuint lower_boundFree(const K &k, const Comp &comp, const KeyOfVal &kofval) const
get lower_bound (first index of element not less than value)
Definition: DTree.h:237
const mapped_type & at(const key_type &key) const
get reference to element pointed by key
Definition: DTree.h:2988
bool operator>(const DTree &dt) const
lexicograhical greater
Definition: DTree.h:2865
Iter & operator++()
pre-increment
Definition: DTree.h:1906
const_iterator cend() const
return iterator after last element
Definition: DTree.h:2375
cxbyte index
index in array
Definition: DTree.h:602
void toNextNode0()
Definition: DTree.h:1537
void reserve0(cxuint newCapacity)
reserve0 elements in Node0's array
Definition: DTree.h:845
const_iterator cbegin() const
return iterator to first element
Definition: DTree.h:2344
ConstIter operator+(ssize_t i) const
add to iterator
Definition: DTree.h:2012
std::pair< cxuint, bool > insert(const T &v, const Comp &comp, const KeyOfVal &kofval)
insert element
Definition: DTree.h:506
cxuint find(const K &k, const Comp &comp, const KeyOfVal &kofval) const
get lower_bound (first index of element not less than value)
Definition: DTree.h:272
void prev()
go to previous element
Definition: DTree.h:1725
iterator erase(const_iterator it)
remove element in postion pointed by iterator
Definition: DTree.h:2617
ConstIter & operator--()
pre-decrement
Definition: DTree.h:2025
mapped_type & at(const key_type &key)
get reference to element pointed by key
Definition: DTree.h:2980
DTree & operator=(const DTree &dt)
copy assignment
Definition: DTree.h:2164
void next(size_t inc)
go to inc next elements
Definition: DTree.h:1425
const T & operator*() const
get element
Definition: DTree.h:2055
DTreeSet(std::initializer_list< value_type > init, const Comp &comp=Comp())
constructor with element ranges
Definition: DTree.h:2902
bool erase(cxuint index)
erase element in index
Definition: DTree.h:573
iterator begin()
return iterator to first element
Definition: DTree.h:2330
void insertNode0(Node0 &&node, cxuint index, const KeyOfVal &kofval, bool updateTotSize=true)
insert Node0 - (move to this node)
Definition: DTree.h:989
utilities for other libraries and programs
main iterator class
Definition: DTree.h:1389
void merge(const Node0 &node2)
merge this node with node2
Definition: DTree.h:365
cxuint index
index in array
Definition: DTree.h:1398
Iter & operator-=(ssize_t i)
subtract from iterator with assignment
Definition: DTree.h:1952
size_t totalSize
total size in this node (count recursively)
Definition: DTree.h:605
void replace(iterator iter, const value_type &value)
replace element with checking range
Definition: DTree.h:2821
Iter operator-(ssize_t i) const
subtract from iterator
Definition: DTree.h:1945
const Node1 * parent() const
get parent node
Definition: DTree.h:221
ConstIter & operator-=(ssize_t i)
subtract from iterator with assignment
Definition: DTree.h:2045
Iter operator+(ssize_t i) const
add to iterator
Definition: DTree.h:1919
signed int cxint
signed int
Definition: Config.h:235
cxbyte capacity
capacity
Definition: DTree.h:604
iterator that allow only to read element
Definition: DTree.h:1983
DTree(std::initializer_list< value_type > init, const Comp &comp=Comp(), const KeyOfVal &kofval=KeyOfVal())
constructor with initializer list
Definition: DTree.h:2116
cxuint CLZ64(uint64_t v)
counts leading zeroes for 64-bit unsigned integer. For zero behavior is undefined ...
Definition: Utilities.h:378
void freeArray()
helper for freeing array
Definition: DTree.h:618
T & operator*() const
get element
Definition: DTree.h:1961
void resize(cxint extraSize)
simple resize
Definition: DTree.h:472
ConstIter operator-(ssize_t i) const
subtract from iterator
Definition: DTree.h:2038
mapped_type & operator[](const key_type &key)
get reference to element pointed by key (add if key doesn't exists)
Definition: DTree.h:2996
void clear()
clear (remove all elements)
Definition: DTree.h:2228
void eraseNode1(cxuint index, bool updateTotSize=true)
remove node1 with index from this node
Definition: DTree.h:1058
bool operator!=(const IterBase &it) const
not equal
Definition: DTree.h:2072
cxuint upperBoundN(const K &v, const Comp &comp, const KeyOfVal &kofval) const
find node that hold first element greater than value
Definition: DTree.h:948
void eraseNode0(cxuint index, const KeyOfVal &kofval, bool updateTotSize=true)
remove node0 with index from this node
Definition: DTree.h:1036
void allocate1(cxuint newCapacity)
Definition: DTree.h:821
void replace(iterator iter, const value_type &value)
replace element with checking range of the key
Definition: DTree.h:2936
ConstIter & operator+=(ssize_t i)
add to iterator with assignment
Definition: DTree.h:2019