fork(1) download
copy 
  1. #include <iostream>
  2. #include <stdlib.h>
  3.  
  4. using namespace std;
  5.  
  6. template <typename Key>
  7. class Ring
  8. {
  9.     struct Node
  10.     {
  11.         Key key;
  12.         Node *next;
  13.         Node *prev;
  14.     };
  15.     Node *any = NULL;
  16.  
  17. public:
  18.  
  19. /******* iterator class methods definitions ********/
  20.     class iterator
  21.     {
  22.         Node *el;
  23.     public:
  24.         iterator(){
  25.             el = NULL;}
  26.  
  27.         ~iterator(){}
  28.  
  29.         iterator(const iterator &copyIter){
  30.             el = copyIter.el;}
  31.  
  32.         iterator(Node *copyEl){
  33.             el = copyEl;}
  34.  
  35.         const iterator &operator = (const iterator &copyIter){
  36.             el = copyIter.el;
  37.             return *this;}
  38.  
  39.         bool operator == (const iterator &comp)const{
  40.             return el == comp.el;}
  41.  
  42.         bool operator != (const iterator &comp)const{
  43.             return el != comp.el;}
  44.  
  45.         iterator operator + (const unsigned int number)const{
  46.             iterator new_iter = *this;
  47.             for(int i = 0; i < number; i++)
  48.                 new_iter++;
  49.             return new_iter;}
  50.  
  51.         iterator operator ++ (){
  52.             if(el != NULL)
  53.                 return el = el->next;}
  54.  
  55.         iterator operator ++ (int){
  56.             iterator copy_iter(el);
  57.             if(el != NULL)
  58.                 return el = el->next;}
  59.  
  60.         iterator operator - (const unsigned int number)const{
  61.             iterator new_iter = *this;
  62.                 for(int i = 0; i < number; i++)
  63.                     new_iter--;
  64.             return new_iter;}
  65.  
  66.         iterator operator --(){
  67.             if(el != NULL)
  68.                 return el = el->prev;}
  69.  
  70.         iterator operator -- (int){
  71.             iterator copy_iter(el);
  72.             if(el != NULL)
  73.                 return el = el->prev;}
  74.  
  75.         Key getKey(){
  76.             //if(!this->isNULL())
  77.                 return el->key;
  78.             //cerr << "getKey(): (iterator = NULL)" << endl;
  79.             }
  80.  
  81.         bool isNULL(){
  82.             if(el)
  83.                 return false;
  84.             return true;}
  85.     };
  86.  
  87. /******* methods ********/
  88.     Ring();
  89.     ~Ring();
  90.     Ring(const Ring<Key> &Ring);
  91.     friend ostream &operator << (ostream &o, const Ring<Key> &Ring){Ring.print(); return o;};
  92.     bool operator ==(const Ring<Key> &Ring);
  93.     bool operator != (const Ring<Key> &Ring);
  94.     Ring<Key> &operator = (const Ring<Key> &Ring);
  95.     Ring<Key> operator + (const Ring<Key> &second)const;
  96.     Ring<Key> operator - (const Ring<Key> &second)const;
  97.     bool insertFront(const Key &key);
  98.     bool insertLast(const Key &key);
  99.     bool insertAt(int pos, const Key &key);
  100.     bool insertAfter(const Key &where, const Key &key);
  101.     bool popByKey(const Key &key);
  102.     bool popLast();
  103.     bool popFront();
  104.     bool ifExists(const Key &key);
  105.     bool isEmpty()const;
  106.     int length()const;
  107.     void print()const;
  108.     bool clear();
  109.     void reverse();
  110.  
  111. /******* additional iterators definitions *******/
  112.     iterator begin()const{
  113.         return iterator(any);}
  114.  
  115.     iterator end()const{
  116.         return iterator(any->prev);}
  117.  
  118. };
  119.  
  120. /******* methods definitions ********/
  121. template <typename Key>
  122. Ring<Key>::Ring()
  123. {
  124.     this->any = NULL;
  125.     cout << "Constructor: (Empty Ring created)" << endl;
  126. }
  127.  
  128. template <typename Key>
  129. Ring<Key>::~Ring()
  130. {
  131.     if(any == NULL)
  132.         cout << "Destructor: ( Ring deleted )" << endl;
  133.     Node *curr = any;
  134.     if(curr)
  135.     {
  136.         while(any != NULL)
  137.         {
  138.             this->popLast();
  139.         }
  140.         cout << "Destructor: ( Ring deleted )" << endl;
  141.     }
  142. }
  143.  
  144. template <typename Key>
  145. Ring<Key>::Ring(const Ring<Key> &Ring)
  146. {
  147.     this->any = NULL;
  148.     if(Ring.any)
  149.     {
  150.         Node *curr = Ring.any;
  151.         do
  152.         {
  153.             this->insertLast(curr->key);
  154.             curr = curr->next;
  155.         }
  156.         while(curr != Ring.any);
  157.     }
  158. }
  159. template <typename Key>
  160. bool Ring<Key>::popLast()
  161. {
  162.     if(any == NULL)
  163.         return true;
  164.     Node *curr = any;
  165.     if(curr->next == curr) // one Node
  166.     {
  167.         any = NULL;
  168.         delete curr;
  169.         return true;
  170.     }
  171.     if(curr->next->next == curr) // two Nodes
  172.     {
  173.         Node *temp = curr->next;
  174.         curr->next = curr;
  175.         curr->prev = curr;
  176.         delete temp;
  177.         return true;
  178.     }
  179.     do
  180.     {
  181.         if(curr->next->next == any) // Last Node
  182.         {
  183.             Node *temp = curr->next;
  184.             temp->next->prev = curr;
  185.             curr->next = temp->next;
  186.             delete temp;
  187.             return true;
  188.         }
  189.         curr = curr->next;
  190.     }
  191.     while(curr != any);
  192.     return false;
  193. }
  194.  
  195. template <typename Key>
  196. bool Ring<Key>::insertFront(const Key &key)
  197. {
  198.     Node* curr = any;
  199.     if(curr == NULL)
  200.     {
  201.         Node *newNode = new Node;
  202.         newNode->key = key;
  203.         newNode->next = newNode;
  204.         newNode->prev = newNode;
  205.         any = newNode;
  206.         return true;
  207.  
  208.     }
  209.     if(curr->next == curr) // one Node
  210.     {
  211.         Node *newNode = new Node;
  212.         newNode->key = key;
  213.         newNode->next = curr;
  214.         newNode->prev = curr;
  215.         curr->prev = newNode;
  216.         curr->next = newNode;
  217.         any = newNode;
  218.         return true;
  219.     }
  220.     Node *newNode = new Node; // many Nodes
  221.     newNode->key = key;
  222.     newNode->next = curr;
  223.     newNode->prev = curr->prev;
  224.     curr->prev->next = newNode;
  225.     curr->prev = newNode;
  226.     any = newNode;
  227.     return true;
  228. }
  229.  
  230.  
  231. template <typename Key>
  232. bool Ring<Key>::operator == (const Ring<Key> &Ring)
  233. {
  234.     if(this->isEmpty() && Ring.isEmpty())
  235.         return true;
  236.     if(this->length() != Ring.length())
  237.         return false;
  238.     Node *curr1 = this->any;
  239.     Node *curr2 = Ring.any;
  240.     do
  241.     {
  242.         if(curr1->key != curr2->key)
  243.             return false;
  244.         curr1 = curr1->next;
  245.         curr2 = curr2->next;
  246.     }
  247.     while(curr1 != this->any);
  248.     return true;
  249. }
  250.  
  251. template <typename Key>
  252. bool Ring<Key>::insertLast(const Key &key)
  253. {
  254.     Node* curr = any;
  255.     if(curr == NULL) // no elements
  256.     {
  257.         this->insertFront(key);
  258.         return true;
  259.     }
  260.     if(curr->next == curr) // one Node
  261.     {
  262.         Node *newNode = new Node;
  263.         newNode->key = key;
  264.         newNode->next = curr;
  265.         newNode->prev = curr;
  266.         curr->prev = newNode;
  267.         curr->next = newNode;
  268.         return true;
  269.     }
  270.     do
  271.     {
  272.         if(curr->next == any)
  273.         {
  274.             Node *newNode = new Node;
  275.             newNode->key = key;
  276.             newNode->next = curr->next;
  277.             newNode->prev = curr;
  278.             curr->next->prev = newNode;
  279.             curr->next = newNode;
  280.             return true;
  281.         }
  282.         curr = curr->next;
  283.     }
  284.     while(curr != any);
  285.     return false;
  286. }
  287.  
  288.  
  289.  
  290. template<typename Key>
  291. bool Ring<Key>::isEmpty()const
  292. {
  293.     if(any == NULL)
  294.     {
  295.         cout << "isEmpty(): (Ring empty)" << endl;
  296.         return true;
  297.     }
  298.     return false;
  299. }
  300.  
  301. template <typename Key>
  302. int Ring<Key>::length()const
  303. {
  304.     int count = 0;
  305.     Node *curr = any;
  306.     if(curr == NULL)
  307.         return count;
  308.     do
  309.     {
  310.         count++;
  311.         curr = curr->next;
  312.     }
  313.     while(curr != any);
  314.     return count;
  315. }
  316.  
  317. template<typename Key>
  318. void Ring<Key>::print()const
  319. {
  320.     Node * curr = any;
  321.     if(curr == NULL)
  322.     {
  323.         cout << "print(): (Ring empty)" << endl;
  324.         return;
  325.     }
  326.     do
  327.     {
  328.         cout << "\t(" << curr->key<< ")";
  329.         curr = curr->next;
  330.     }
  331.     while(curr != any);
  332.     cout << endl;
  333. }
  334.  
  335.  
  336.  
  337. /******* external function ********/
  338. /****** Example of the split function:
  339. split (r3,r1,true,3,r2,false,6)
  340. r3= 1,2,3,4,5
  341. r1= 1,3,5
  342. r2= 2,5,3,1,4,2
  343. ********/
  344.  
  345. template <typename Key>
  346. Ring<Key> split(const Ring<Key> &source,Ring<Key> &result1, bool dir1, int len1, Ring<Key> &result2, bool dir2, int len2){
  347.  
  348. typename Ring<Key>::iterator i1 = source.begin();
  349. typename Ring<Key>::iterator i2 = source.begin();
  350. /*I moved second iterator to the 2nd position in original Ring*/
  351. i2++;
  352.  
  353.  
  354.     if (source.isEmpty()){
  355.         cout<<"Empty source Ring"<<endl;}
  356.  
  357.     if (source.length()==1||source.length()==2){
  358.         return source;
  359.             }
  360.  
  361.     if((len1 <= 0) || (len2 <= 0))
  362.     {
  363.         cout << "split():(incorrect lengths)" << endl;
  364.     }
  365.  
  366.         if(!i1.isNULL()){
  367.             for(int i = 0; i < len1; i++)
  368.             {
  369.                 result1.insertLast(i1.getKey());
  370.                 if(dir1){
  371.                     i1++;
  372.                     i1++;;
  373.                     }
  374.                 else
  375.                     {i1--;
  376.                     i1--;
  377.                     }}}
  378. cout<<result1;
  379.  
  380.         if(!i2.isNULL()){
  381.             for(int i = 0; i < len2; i++)
  382.             {
  383.                 result2.insertLast(i2.getKey());
  384.                if(dir2){
  385.                     i2++;
  386.                     i2++;
  387.                     }
  388.                 else
  389.                     {i2--;
  390.                     i2--;
  391.                     }}}
  392. cout<<result2;
  393.  
  394. }
  395.  
  396. int main()
  397. {
  398.     Ring<int> R1,R2,R3,R4,R5;
  399.  
  400.     R1.insertLast(2);
  401.     R1.insertLast(3);
  402.     R1.insertLast(4);
  403.     R1.insertLast(5);
  404.     R1.insertLast(6);
  405.     R1.insertLast(1);
  406.  
  407.     R2.insertLast(10);
  408.     R2.insertLast(20);
  409.     R2.insertLast(30);
  410.     R2.insertLast(40);
  411.     R2.insertLast(50);
  412.     R2.insertLast(60);
  413.     R2.insertLast(70);
  414.  
  415. cout<<"Split function:"<<endl;
  416. split(R1,R3,false,3,R4,false,6);
  417.  
  418.  R5.insertLast(10);
  419.     R5.insertLast(20);
  420.     R5.insertLast(30);
  421.     R5.insertLast(50);
  422.     R5.insertLast(50);
  423.     R5.insertLast(60);
  424.     R5.insertLast(70);
  425.  
  426. R5.print();
  427.  
  428.    return 0;
  429. }
  430.  
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Constructor: (Empty Ring created)
Constructor: (Empty Ring created)
Constructor: (Empty Ring created)
Constructor: (Empty Ring created)
Constructor: (Empty Ring created)
Split function:
	(2)	(6)	(4)
	(3)	(1)	(5)	(3)	(1)	(5)
https://ideone.com/63i8rk
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!