Simple Set and Map: Source Code Download Page

Create the file simple_set_and_map.cpp on your own computer. In the new file, you should put the code below. The link [Sets and maps: simplified] has the examples in which the code is used.

//*************************************************************************************************
//*************************************************************************************************
//* The MIT License (MIT)                                                                         *
//* Copyright (C) 2023 Ivan Matic                                                                 *
//*                                                                                               *
//* Permission is hereby granted, free of charge, to any person obtaining a copy of this          *
//* software and associated documentation files (the "Software"), to deal in the Software         *
//* without restriction, including without limitation the rights to use, copy, modify, merge,     *
//* publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons    *
//* to whom the Software is furnished to do so, subject to the following conditions:              *
//*                                                                                               *
//* The above copyright notice and this permission notice shall be included in all copies or      *
//* substantial portions of the Software.                                                         *
//*                                                                                               *
//* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,           *
//* INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR      *
//* PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE     *
//* FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR          *
//* OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER        *
//* DEALINGS IN THE SOFTWARE.                                                                     *
//*************************************************************************************************

#ifndef _INCL_STsetmap_CPP
#define _INCL_STsetmap_CPP

namespace ssm{
  template<typename KEY> class set{
  private:
    class AVLNode{
    public:
      KEY value;
      long leftCount;
      long rightCount;
      long height;
      AVLNode* leftChild;
      AVLNode* rightChild;
      AVLNode(){
        leftChild=nullptr;
        rightChild=nullptr;
        leftCount=-17;
        rightCount=-17;
      }
      AVLNode(const KEY& k ) {
        value = k; leftChild = nullptr;
        rightChild = nullptr;
        leftCount=-17;
        rightCount=-17;
        height = 1;
      }
    }* _dRoot;
    long _size;
    long getHeight(AVLNode * );
    long hDiff(AVLNode * );
    long redoHeight(AVLNode * );
    AVLNode* rRotation(AVLNode* );
    AVLNode* lRotation(AVLNode* );
    AVLNode* balance(AVLNode* );
    AVLNode* insertInTree(AVLNode* , const KEY & , long & );
    AVLNode* getMinNode(AVLNode* );
    AVLNode* rewireMin(AVLNode* );
    AVLNode* removeFromTree(AVLNode* , const KEY& , long & );
    AVLNode* duplicateTree(AVLNode*);
    void clearAVLTree(AVLNode*);
    KEY avl_access(AVLNode* , const long & ) const;
  public:
    set();
    set(const set &);
    set& operator=(const set &);
    set(set&&);
    set& operator=(set &&);
    long size() const;
    long erase(const KEY & );
    long erase(const set & );
    long insert(const KEY & );
    long insert(const set &);
    long operator+=(const KEY &);
    long operator+=(const set &);
    long operator-=(const KEY &);
    long operator-=(const set &);
    std::pair<long,KEY> findIK(const KEY &, const long & = 0) const;
    long find(const KEY &, const long & = 0) const; 
    long upperBound(const KEY &) const;
    void clear();
    KEY operator[](const long & ) const;
    virtual ~set();
  };
  template<typename KEY> long set<KEY>::getHeight(AVLNode * root){
    if(root==nullptr){
      return 0;
    }
    return root->height;
  }
  template<typename KEY> long set<KEY>::hDiff(AVLNode * root){
    return getHeight(root->rightChild)-getHeight(root->leftChild);
  }
  template<typename KEY> long set<KEY>::redoHeight(AVLNode * root){
    long lHeight = getHeight(root->leftChild);
    long rHeight = getHeight(root->rightChild);
    root->height = rHeight;
    if(lHeight>rHeight){root->height = lHeight;}
    root->height += 1;
    return root->height;
  }
  template<typename KEY>
  typename set<KEY>::AVLNode* set<KEY>::rRotation(AVLNode * root){
    AVLNode * other = root->leftChild;
    root->leftChild = other->rightChild;
    other->rightChild = root;
    long a,c;
    a= other->leftCount;
    c= root->rightCount;
    root->leftCount -= (a+1);
    other->rightCount += (c+1);
    redoHeight(root);
    redoHeight(other);
    return other;
  }
  template<typename KEY>
  typename set<KEY>::AVLNode * set<KEY>::lRotation(AVLNode * root){
    AVLNode * other = root->rightChild;
    root->rightChild = other->leftChild;
    other->leftChild = root;
    long a,c;
    a= other->rightCount;
    c=root->leftCount;
    root->rightCount -= (a+1);
    other->leftCount += (c+1);
    redoHeight(root);
    redoHeight(other);
    return other;
  }
  template<typename KEY>
  typename set<KEY>::AVLNode * set<KEY>::
  balance(AVLNode * root){
    redoHeight(root);
    if( hDiff(root)==2 ){
      if( hDiff(root->rightChild) < 0 ){
        root->rightChild = rRotation(root->rightChild);
      }
      return lRotation(root);
    }
    if( hDiff(root)==-2 ){
      if( hDiff(root->leftChild) > 0 ){
        root->leftChild = lRotation(root->leftChild);
      }
      return rRotation(root);
    }
    return root;
  }
  template<typename KEY>
  typename set<KEY>::AVLNode * set<KEY>::
  insertInTree(AVLNode * root, const KEY & _value, long & insSucc){
    if( root==nullptr ){
      insSucc=1;
      AVLNode *fR=new AVLNode (_value);
      fR->leftCount=0;
      fR->rightCount=0;
      return fR;
    }
    if( _value < root->value ){
      root->leftChild = insertInTree(root->leftChild,_value,insSucc);
      if(insSucc==1){
        root->leftCount+=1;
      }
    }
    else{
      if(root->value < _value ){
        root->rightChild = insertInTree(root->rightChild,_value,insSucc);
        if(insSucc==1){
          root->rightCount+=1;
        }
      }
      else{
        insSucc=0;
        return root;
      }
    }
    if(insSucc==1){
      return balance(root);
    }
    return root;
  }
  template<typename KEY>
  typename set<KEY>::AVLNode * set<KEY>::getMinNode(AVLNode * root){
    if(root->leftChild==nullptr){
      return root;
    }
    return getMinNode(root->leftChild);
  }
  template<typename KEY>
  typename set<KEY>::AVLNode * set<KEY>::rewireMin(AVLNode * root){
    if( root->leftChild==nullptr ){
      return root->rightChild;
    }
    root->leftChild = rewireMin(root->leftChild);
    root->leftCount -= 1;
    return balance(root);
  }
  template<typename KEY>
  typename set<KEY>::AVLNode * 
        set<KEY>::removeFromTree(AVLNode * root, const KEY& _value, 
           long & remSucc){
    if( root==nullptr ){
      remSucc=0;
      return nullptr;
    }
    if( _value < root->value ){
      root->leftChild = removeFromTree(root->leftChild,_value, remSucc);
      if(remSucc==1){
        root->leftCount -=1;
      }
    }
    else{
      if(root->value < _value ){
        root->rightChild = removeFromTree(root->rightChild,_value,remSucc);
        if(remSucc==1){
          root->rightCount -=1;
        }
      }
      else{
        AVLNode * lTemp = root->leftChild;
        AVLNode * rTemp = root->rightChild;
        long oldleftCount,oldrightCount;
        oldleftCount=root->leftCount;
        oldrightCount=root->rightCount;
        delete root;
        remSucc=1;
        if( rTemp == nullptr ){
          return lTemp;
        }
        AVLNode * rightMin = getMinNode(rTemp);
        rightMin->rightChild = rewireMin(rTemp);
        rightMin->leftChild = lTemp;
        rightMin->leftCount=oldleftCount;
        rightMin->rightCount=oldrightCount-1;
        remSucc=1;
        return balance(rightMin);
      }
    }
    return balance(root);
  }
  template<typename KEY> void set<KEY>::clearAVLTree(AVLNode *root){
    if(root!=nullptr){
      clearAVLTree(root->leftChild);
      clearAVLTree(root->rightChild);
      delete root;
    }
    return;
  }
  template<typename KEY> 
  typename set<KEY>::AVLNode * 
     set<KEY>::duplicateTree(AVLNode *root){
    AVLNode *newN;
    newN=nullptr;
    if(root!=nullptr){
      newN=new AVLNode;
      newN->value=root->value;
      newN->leftCount=root->leftCount;
      newN->rightCount=root->rightCount;
      newN->height=root->height;
      newN->leftChild = duplicateTree(root->leftChild);
      newN->rightChild= duplicateTree(root->rightChild);
    }
    return newN;
  }
  template<typename KEY> KEY 
   set<KEY>::avl_access(AVLNode *root, const long &i) const{
    if(root==nullptr){
      KEY tempWithRandValue;
      return tempWithRandValue;
    }
    if(i==root->leftCount){
      return root->value;
    }
    if(i<root->leftCount){
      return avl_access(root->leftChild,i);
    }
    return avl_access(root->rightChild, i-root->leftCount-1);
  }
  template<typename KEY> set<KEY>::set(){
    _dRoot=nullptr;
    _size=0;
  }
  template<typename KEY> set<KEY>::set(const set<KEY>& _copyFrom){
    _dRoot=nullptr;
    _dRoot= duplicateTree(_copyFrom._dRoot);
    _size= _copyFrom._size;
  }
  template<typename KEY> set<KEY>::set( set<KEY>&& _moveFrom){
    _size= _moveFrom._size;
    _moveFrom._size=0;
    _dRoot=_moveFrom._dRoot;
    _moveFrom._dRoot=nullptr;
  }
  template<typename KEY> set<KEY>& 
    set<KEY>::operator=(const set<KEY>& _copyFrom){
    if(&_copyFrom!=this){
      clear();
      _dRoot= duplicateTree(_copyFrom._dRoot);
      _size= _copyFrom._size;
    }
    return *this;
  }
  template<typename KEY> set<KEY>& 
     set<KEY>::operator=( set<KEY>&& _moveFrom){
    if(&_moveFrom!=this){
      clear();
      _size= _moveFrom._size;
      _dRoot= _moveFrom._dRoot;
      _moveFrom._size=0;
      _moveFrom._dRoot=nullptr;
    }
    return *this;
  }
  template<typename KEY> long set<KEY>::size() const{
    return _size;
  }
  template<typename KEY> set<KEY>::~set(){
    clear();
  }
  template<typename KEY> void set<KEY>::clear(){
    _size=0;
    clearAVLTree(_dRoot);
    _dRoot=nullptr;
  }
  template<typename KEY> long set<KEY>::erase(const KEY & _value){
    long delSucc=0;
    _dRoot=removeFromTree(_dRoot,_value,delSucc);
    if(delSucc==1){
      --_size;
    }
    return delSucc;
  }
  template<typename KEY> long set<KEY>::insert(const KEY & _value){
    long addSucc=0;
    _dRoot=insertInTree(_dRoot,_value,addSucc);
    if(addSucc==1){
      ++_size;
    }
    return addSucc;
  }
  template<typename KEY> long set<KEY>::insert(const set<KEY> & _s2){
    long l2=_s2.size();
    long fR=0;
    for(int i=0;i<l2;++i){
      fR+= insert(_s2[i]);
    }
    return fR;
  }
  template<typename KEY> long set<KEY>::erase(const set<KEY> & _s2){
    long l2=_s2.size();
    long fR=0;
    for(int i=0;i<l2;++i){
      fR+= erase(_s2[i]);
    }
    return fR;
  }
  template<typename KEY> long set<KEY>::operator+=(const KEY & _value){
    return insert(_value);
  }
  template<typename KEY> long set<KEY>::operator+=(const set<KEY> & _s){
    return insert(_s);
  }
  template<typename KEY> long set<KEY>::operator-=(const KEY & _value){
    return erase(_value);
  }
  template<typename KEY> long set<KEY>::operator-=(const set<KEY> & _s){
    return erase(_s);
  }
  template<typename KEY> KEY set<KEY>::operator[](const long & i) const{
    if((i>-1)&&(i<_size)){
      return avl_access(_dRoot,i);
    }
    KEY irrelevantValue;
    return irrelevantValue;
  }
  template<typename KEY> std::pair<long,KEY> 
  set<KEY>::findIK(const KEY & _v, 
      const long & upperBoundInsteadOfNegOne) const{
    AVLNode* researcher= _dRoot;
    std::pair<long, KEY> found;
    found.first=-1;
    long discardedLeft=0;
    while( (researcher!=nullptr)&&(found.first==-1)){
      if(_v<researcher->value){
        researcher=researcher->leftChild;
      }
      else{
        if(researcher->value < _v){
          discardedLeft+=researcher->leftCount+1;
          researcher=researcher->rightChild;
        }
        else{
          found.first=discardedLeft+researcher->leftCount;
          found.second=researcher->value;
        }
      }
    }
    if(found.first*upperBoundInsteadOfNegOne==-1){
      found.first=discardedLeft;
    }
    return found;
  }
  template<typename KEY> long 
  set<KEY>::find(const KEY & _v, 
      const long & upperBoundInsteadOfNegOne) const{
     return findIK(_v,upperBoundInsteadOfNegOne).first;
  }
  template<typename KEY> long 
    set<KEY>::upperBound(const KEY & _v) const{
    return find(_v,1);
  }
  template<typename KEY, typename VAL> class map{
  private:
    struct CompPair{
    public:
      KEY k;
      VAL v;
      int operator<(const CompPair& ) const;
    };
    set<CompPair> s;
  public:
    long size() const;
    long erase(const KEY & );
    long erase(const map & );
    long insert(const KEY & , const VAL &);
    long insert(const map &);
    std::pair<long,std::pair<KEY,VAL> > 
    findIKV(const KEY & , const long & = 0) const;
    long find(const KEY &, const long & = 0) const;
    long upperBound(const KEY &) const;
    void clear();
    std::pair<KEY,VAL> operator[](const long & ) const;
  };
  template<typename KEY, typename VAL>
  int map<KEY,VAL>::CompPair::operator<(const CompPair& oth) const{
    if(k<oth.k){return 1;}
    return 0;
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::size() const{
    return s.size();
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::erase(const KEY & _k){
    CompPair p;
    p.k=_k;
    return s.erase(p);
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::erase(const map<KEY,VAL>& _m){
    return s.erase(_m.s);
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::insert(const KEY& _k, const VAL& _v){
    CompPair p;
    p.k=_k;p.v=_v;
    return s.insert(p);
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::insert(const map<KEY,VAL>& _m){
    return s.insert(_m.s);
  }
  template<typename KEY, typename VAL>
  std::pair<long, std::pair<KEY,VAL> > 
  map<KEY,VAL>::findIKV(const KEY & _k, 
  const long & upperBoundInsteadOfNegOne) const{
     CompPair p;
     p.k=_k;
     std::pair<long, CompPair> res=s.findIK(p,upperBoundInsteadOfNegOne);
     std::pair<long,std::pair<KEY,VAL> > retVal;
     retVal.first=res.first;
     retVal.second.first=res.second.k;
     retVal.second.second=res.second.v;
     return retVal;
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::find(const KEY & _k, 
    const long & upperBoundInsteadOfNegOne) const{
    CompPair p;
    p.k=_k;
    return s.find(p,upperBoundInsteadOfNegOne);
  }
  template<typename KEY, typename VAL> 
  long map<KEY,VAL>::upperBound(const KEY & _k) const{
    return find(_k,1);
  }
  template<typename KEY, typename VAL> 
  void map<KEY,VAL>::clear(){
    s.clear();
  }
  template<typename KEY, typename VAL> 
  std::pair<KEY,VAL> map<KEY,VAL>::operator[](const long & j) const{
    std::pair<KEY,VAL> res;
    CompPair p=s[j];
    res.first=p.k; res.second=p.v;
    return res;
  }
}
#endif