41 template<
typename K_TYPE,
43 typename ALLOC = allocator<K_TYPE>,
44 typename Compare = increaseComparator<K_TYPE>>
156 mutable std::mt19937
gen_{std::random_device{}()};
157 mutable std::uniform_real_distribution<>
dis_{0.0, 1.0};
249 u_integer levels = 1, std::initializer_list<skipListNode*> next = {})
const;
265 bool highPriority(skipListNode* cur, skipListNode* next)
const;
274 bool highPriority(
const K_TYPE& key, skipListNode* next)
const;
282 static bool equal(
const K_TYPE& key, skipListNode* next);
324 explicit skipList(Compare compare = Compare{});
332 skipListNode*
find(
const K_TYPE& key)
const;
340 bool modify(
const K_TYPE& key,
const V_TYPE& value);
349 bool insert(
const K_TYPE& key,
const V_TYPE& value);
357 bool erase(
const K_TYPE& key);
373template <typename K_TYPE, typename V_TYPE, typename ALLOC, typename Compare>
377 if (next.size() != 0 &&
static_cast<u_integer>(next.size()) !=
levels) {
381 for (
auto&& ptr: next) {
382 this->next_[i] = ptr;
387template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
393template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
399template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
402 return this->data_.template
get<0>();
405template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
408 return this->data_.template
get<1>();
411template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
414 return this->data_.template
get<1>();
417template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
419 return this->next_.size();
422template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
429 this->next_.pushEnd(
nullptr);
433template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
440 this->next_.popEnd();
444template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
446 this->data_.template
set<1>(value);
449template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
452 return this->next_[
levels - 1];
455template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
458 this->next_[
levels - 1] = next;
461template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
469template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
473template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
475 this->operator=(
other);
478template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
485 this->cur_ =
other.cur_;
489template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
491 return this->cur_->getPNext(1);
494template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
496 this->cur_ = this->cur_->getPNext(1);
499template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
505template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
516template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
523 return this->cur_ >
other.cur_ ?
524 std::numeric_limits<integer>::max() :
525 std::numeric_limits<integer>::min();
528template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
531 if (!this->isValid()){
535 return this->cur_->getVal();
538template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
541 if (!this->isValid()){
545 return this->cur_->getVal();
548template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
553template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
559 while (
s->isValid()){
560 if (
s->cur_ ==
e->cur_){
567 dis = std::numeric_limits<integer>::max();
572template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
575 std::initializer_list<skipListNode*> next)
const {
581template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
587template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
596template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
605template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
615template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
620 while (this->
dis_(this->
gen_) < p) {
626template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
632template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
637template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
642template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
663template<
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
667 while (
cur->getPNext(1)){
673template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
677template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
681 if (this->size_ == 0){
686 auto cur_p = this->head_;
704template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
712 cur_p->setValue(value);
716template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
728 while (
cur->getPNext(
i) && !
this->highPriority(
key,
cur->getPNext(
i))) {
734 if (equal(
key,
cur) &&
cur != this->head_) {
744 skipListNode::connect(
i + 1, update[
i],
new_node);
751template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
776 this->destroyNode(
cur_p);
786 this->shrinkCurLevels(this->getCurLevels() -
decrement);
792template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
795 auto cur = this->head_;
797 auto next =
cur->getPNext(1);
798 this->destroyNode(
cur);
803template <
typename K_TYPE,
typename V_TYPE,
typename ALLOC,
typename Compare>
Exception for container index out-of-range errors.
Definition error.h:192
Unique ownership smart pointer with move semantics.
Definition ownerPtr.h:37
Forward iterator for skipList.
Definition skipList.h:164
Iterator & operator=(const Iterator &other)
Copy assignment operator.
Definition skipList.h:480
static integer ptrDistance(const Iterator *start, const Iterator *end)
Calculates distance between two iterators.
Definition skipList.h:555
integer operator-(const Iterator &other) const
Calculates distance between iterators.
Definition skipList.h:518
void operator+=(integer steps) const
Advances iterator by steps.
Definition skipList.h:506
couple< const K_TYPE, V_TYPE > & get()
Gets current element (non-const)
Definition skipList.h:530
skipListNode * cur_
Current node pointer.
Definition skipList.h:166
Iterator(skipListNode *cur=nullptr)
Constructs iterator.
Definition skipList.h:470
void next() const
Moves to next element.
Definition skipList.h:495
bool isValid() const
Checks if iterator is valid.
Definition skipList.h:549
Iterator * clone() const
Creates a copy of this iterator.
Definition skipList.h:501
bool hasNext() const
Checks if more elements exist forward.
Definition skipList.h:490
Internal node class for Skip List.
Definition skipList.h:54
void expandLevels(u_integer new_levels)
Expands node to more levels.
Definition skipList.h:423
void setPNext(u_integer levels, skipListNode *next)
Sets next node at specified level.
Definition skipList.h:456
void shrinkLevels(u_integer new_levels)
Shrinks node to fewer levels.
Definition skipList.h:434
static void connect(u_integer levels, skipListNode *prev, skipListNode *next)
Connects two nodes at specified level.
Definition skipList.h:462
u_integer getLevels() const
Gets number of levels for this node.
Definition skipList.h:418
const V_TYPE & getValue() const
Gets value (const)
Definition skipList.h:407
couple< const K_TYPE, V_TYPE > & getVal()
Gets key-value pair (non-const)
Definition skipList.h:389
const K_TYPE & getKey() const
Gets key.
Definition skipList.h:401
void setValue(const V_TYPE &value)
Sets new value.
Definition skipList.h:445
skipListNode * getPNext(u_integer levels) const
Gets next node at specified level.
Definition skipList.h:451
Skip List container implementation.
Definition skipList.h:45
rebind_alloc_node rebind_alloc
Node allocator.
Definition skipList.h:155
skipListNode * findLastNode() const
Finds last node in list.
Definition skipList.h:665
void listDestroy() noexcept
Destroys entire list and deallocates all nodes.
Definition skipList.h:793
u_integer size_
Number of elements.
Definition skipList.h:152
skipListNode * head_
Head node pointer.
Definition skipList.h:153
ALLOC::template rebind_alloc< skipListNode > rebind_alloc_node
Rebound allocator for nodes.
Definition skipList.h:149
skipListNode * listCopy() const
Creates a deep copy of the list.
Definition skipList.h:644
u_integer getCurLevels() const
Gets current number of levels in list.
Definition skipList.h:628
ALLOC::template rebind_alloc< skipListNode * > rebind_alloc_pointer
Rebound allocator for pointers.
Definition skipList.h:150
bool insert(const K_TYPE &key, const V_TYPE &value)
Inserts new key-value pair.
Definition skipList.h:717
std::uniform_real_distribution dis_
Uniform distribution for level generation.
Definition skipList.h:157
skipListNode * createNode(const K_TYPE &key=K_TYPE{}, const V_TYPE &value=V_TYPE{}, u_integer levels=1, std::initializer_list< skipListNode * > next={}) const
Creates a new node with given parameters.
Definition skipList.h:574
void expandCurLevels(u_integer new_levels)
Expands list to more levels.
Definition skipList.h:633
void shrinkCurLevels(u_integer new_levels)
Shrinks list to fewer levels.
Definition skipList.h:638
skipListNode * find(const K_TYPE &key) const
Finds node with given key.
Definition skipList.h:679
bool modify(const K_TYPE &key, const V_TYPE &value)
Modifies value for existing key.
Definition skipList.h:705
static bool equal(const K_TYPE &key, skipListNode *next)
Checks if key matches node's key.
Definition skipList.h:606
Compare compare_
Comparison function.
Definition skipList.h:154
bool highPriority(skipListNode *cur, skipListNode *next) const
Compares priority between two nodes.
Definition skipList.h:588
u_integer getRandomLevels() const
Generates random number of levels for new node.
Definition skipList.h:616
~skipList()
Destructor.
Definition skipList.h:804
void destroyNode(skipListNode *node) const
Destroys a node and deallocates memory.
Definition skipList.h:582
bool erase(const K_TYPE &key)
Erases node with given key.
Definition skipList.h:752
skipList(Compare compare=Compare{})
Constructs skipList with given comparison function.
Definition skipList.h:674
std::mt19937 gen_
Random number generator.
Definition skipList.h:156
Exception for unimplemented method calls.
Definition error.h:271
Comparator base class and concrete comparator classes.
Combines Comparable and CallbackOf for comparison callbacks.
Definition types.h:377
Generic pair container implementation.
std::uint32_t u_integer
32-bit unsigned integer type for sizes and indexes
Definition config.h:263
std::int64_t integer
64-bit signed integer type for arithmetic operations
Definition config.h:254
Main namespace for the project Original.
Definition algorithms.h:21
TYPE find(coroutine::generator< TYPE > gen, Callback &&c)
Finds the first element satisfying a predicate.
Definition generators.h:863
Standard namespace extensions for original::alternative.
Definition allocator.h:351
Dynamic array container with automatic resizing.