fork 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= nullptr; // Always initialize. Worst case if you do it 
  13.                              // twice: the compiler will be smart enough to 
  14.                              // remove one of the occurrences
  15.         Node *prev= nullptr; // Ditto
  16.     };
  17.     Node *any= nullptr; // Use nullptr on C++11 and onwards
  18.     // Also, any is not a very good name, prefer using root or first
  19.  
  20. public:
  21.  
  22. /******* iterator class methods definitions ********/
  23.     class iterator
  24.     {
  25.         Node *el= nullptr; // Ditto
  26.     public:
  27.         iterator()= default; // or iterator() {}
  28.         ~iterator()= default; // or ~iterator() {}
  29.  
  30.         constexpr iterator(const iterator& copyIter)
  31.         : el(copyIter.el)
  32.         {
  33.         	// Empty constructor gets to be constexpr
  34.         	// Improves optimizing and can be evaluated at runtime
  35.         }
  36.  
  37.         constexpr iterator(Node *copyEl)
  38.         : el(copyEl)
  39.         {
  40.         }
  41.  
  42.         iterator &operator = (const iterator &copyIter)
  43.         {
  44.             el = copyIter.el;
  45.             return *this;
  46.         }
  47.  
  48.         bool operator == (const iterator &comp) const
  49.         {
  50.             return el == comp.el;
  51.         }
  52.  
  53.         bool operator != (const iterator &comp) const
  54.         {
  55.             return el != comp.el;
  56.         }
  57.  
  58. 		/* I don't think this operator is good practice
  59.         iterator operator + (const unsigned int number) const
  60.         {
  61.             iterator new_iter = *this; // Could be auto new_iter = *this in C++11
  62.             for(int i = 0; i < number; i++) { // Style: Always put brackets
  63.                 new_iter++;
  64.             }
  65.             return new_iter;
  66.         }*/
  67.  
  68.         iterator& operator ++ ()
  69.         {
  70.             if (el) {
  71.                 el = el->next;
  72.             }
  73.             return *this;
  74.             // You had no return if it's null
  75.             // Also, no need for != nullptr or != NULL
  76.             // Usually, you return a reference to self
  77.         }
  78.  
  79.         iterator operator ++ (int)
  80.         {
  81.             iterator copy_iter(el);
  82.             if (el) {
  83.                 el = el->next;
  84.             }
  85.             return copy_iter; // You return the copy, no matter what
  86.         }
  87.  
  88.         /* Ditto
  89.         iterator operator - (const unsigned int number) const
  90.         {
  91.             iterator new_iter = *this;
  92.             for(int i = 0; i < number; i++) {
  93.                 new_iter--;
  94.             }
  95.             return new_iter;
  96.         }*/
  97.  
  98.         iterator& operator --()
  99.         {
  100.             if (el) {
  101.                 el = el->prev;
  102.             }
  103.         	return *this;
  104.         }
  105.  
  106.         iterator operator -- (int)
  107.         {
  108.             iterator copy_iter(el);
  109.             if (el) {
  110.                 el= el->prev;
  111.             }
  112.         	return copy_iter;
  113.         }
  114.  
  115.         Key getKey() const
  116.         {
  117.             if (el) {
  118.                 return el->key;
  119.             }
  120.             cerr << "getKey(): (iterator = NULL)" << endl;
  121.             return Key(); // Empty element, might aswell throw here
  122.         }
  123.  
  124.         bool isNULL() const
  125.         {
  126.             return !el;
  127.         }
  128.  
  129.         operator bool() const
  130.         {
  131.         	return !isNULL();
  132.         }
  133.     };
  134.  
  135. /******* methods ********/
  136.     Ring();
  137.     ~Ring();
  138.     Ring(const Ring<Key> &Ring);
  139.     friend ostream &operator << (ostream &o, const Ring<Key> &Ring){Ring.print(); return o;};
  140.     bool operator ==(const Ring<Key> &Ring);
  141.     bool operator != (const Ring<Key> &Ring);
  142.     Ring<Key> &operator = (const Ring<Key> &Ring);
  143.     Ring<Key> operator + (const Ring<Key> &second)const;
  144.     Ring<Key> operator - (const Ring<Key> &second)const;
  145.     bool insertFront(const Key &key);
  146.     bool insertLast(const Key &key);
  147.     bool insertAt(int pos, const Key &key);
  148.     bool insertAfter(const Key &where, const Key &key);
  149.     bool popByKey(const Key &key);
  150.     bool popLast();
  151.     bool popFront();
  152.     bool ifExists(const Key &key);
  153.     bool isEmpty()const;
  154.     int length()const;
  155.     void print()const;
  156.     bool clear();
  157.     void reverse();
  158.  
  159. /******* additional iterators definitions *******/
  160.     iterator begin() const
  161.     {
  162.         return iterator(any);
  163.     }
  164.  
  165.     iterator end() const
  166.     {
  167.         return iterator(any? any->prev : nullptr); // Always check before dereference
  168.     }
  169. };
  170.  
  171. /******* methods definitions ********/
  172. template <typename Key>
  173. Ring<Key>::Ring()
  174. // : any(nullptr) // Prefer initializers. No need anyway because we did any= nullptr
  175. {
  176.     cout << "Constructor: (Empty Ring created)" << endl;
  177. }
  178.  
  179. template <typename Key>
  180. Ring<Key>::~Ring()
  181. {
  182.     if (!any) {
  183.         cout << "Destructor: ( Ring deleted )" << endl;
  184.     }
  185.     Node *curr = any; // auto
  186.     if (curr) {
  187.         while(any) {
  188.             this->popLast();
  189.         }
  190.         cout << "Destructor: ( Ring deleted )" << endl;
  191.     }
  192. }
  193.  
  194. template <typename Key>
  195. Ring<Key>::Ring(const Ring<Key> &ring) // Please be consistent. If you're using 
  196. // capital letters for classes, dont call the variable Ring; it should be ring
  197. // : any(nullptr) // Prefer initializers. No need anyway because we did any= nullptr
  198. {
  199.     if (ring.any) {
  200.         Node *curr = ring.any;
  201.         do {
  202.             this->insertLast(curr->key);
  203.             curr = curr->next;
  204.         } while(curr != ring.any);
  205.     }
  206. }
  207.  
  208. template <typename Key>
  209. bool Ring<Key>::popLast()
  210. {
  211.     if (!any) {
  212.         return true;
  213.     }
  214.     Node *curr = any;
  215.     if (curr->next == curr) { // one Node
  216.         any = NULL;
  217.         delete curr; // Here is where you "hope" no one copied your class
  218.                      // because you're deleting a pointer that other might be
  219.                      // using, that's what's called a dangling pointer
  220.         return true;
  221.     }
  222.     if(curr->next->next == curr) // two Nodes
  223.     {
  224.         Node *temp = curr->next;
  225.         curr->next = curr;
  226.         curr->prev = curr;
  227.         delete temp;
  228.         return true;
  229.     }
  230.     do
  231.     {
  232.         if(curr->next->next == any) // Last Node
  233.         {
  234.             Node *temp = curr->next;
  235.             temp->next->prev = curr;
  236.             curr->next = temp->next;
  237.             delete temp;
  238.             return true;
  239.         }
  240.         curr = curr->next;
  241.     }
  242.     while(curr != any);
  243.     return false;
  244. }
  245.  
  246. template <typename Key>
  247. bool Ring<Key>::insertFront(const Key &key)
  248. {
  249.     Node *newNode = new Node; // Either way
  250.     newNode->key = key; // Always set the key
  251.  
  252.     if (!any) { // Empty
  253.         newNode->next = newNode;
  254.         newNode->prev = newNode;
  255.         any = newNode;
  256.     } else {
  257. 	    newNode->next= any; // Will be always before the "any"
  258. 		newNode->prev= any->prev; // Will always steal any's previous
  259. 		any->prev= newNode;  // Any will always point at newNode as previous
  260. 	    any= newNode; // I'm the captain now
  261. 		// Actually, for the above, We don't care if it's only one or more	    
  262.     }
  263.     return true;
  264. }
  265.  
  266. template <typename Key>
  267. bool Ring<Key>::operator == (const Ring<Key> &ring)
  268. {
  269.     if (this->isEmpty() && ring.isEmpty()) {
  270.         return true;
  271.     }
  272.     if (this->length() != ring.length()) {
  273.         return false;
  274.     }
  275.     Node *curr1 = this->any;
  276.     Node *curr2 = ring.any;
  277.     do {
  278.         if (curr1->key != curr2->key) {
  279.             return false;
  280.         }
  281.         curr1 = curr1->next;
  282.         curr2 = curr2->next;
  283.         // No null check needed for non empty rings
  284.     } while(curr1 != this->any);
  285.     return true;
  286. }
  287.  
  288. template <typename Key>
  289. bool Ring<Key>::insertLast(const Key &key)
  290. {
  291.     if (!any) {  // no elements
  292.         this->insertFront(key);
  293.         return true;
  294.     }
  295.     Node *newNode = new Node;
  296.     newNode->key = key;
  297.     newNode->next = any;
  298.     Node* curr = any;
  299.     do {
  300.         if (curr->next == any) {
  301.             newNode->prev = curr;
  302.             any->prev = newNode;
  303.             curr->next = newNode;
  304.             return true;
  305.         }
  306.         curr= curr->next;
  307.     } while(curr != any);
  308.     return false;
  309. }
  310.  
  311. template<typename Key>
  312. bool Ring<Key>::isEmpty() const
  313. {
  314.     // return !any;
  315.     if (!any) {
  316.         cout << "isEmpty(): (Ring empty)" << endl;
  317.         return true;
  318.     }
  319.     return false;
  320. }
  321.  
  322. template <typename Key>
  323. int Ring<Key>::length() const
  324. {
  325.     int count = 0;
  326.     Node *curr = any;
  327.     if (!curr) {
  328.         return count;
  329.     }
  330.     do {
  331.         count++;
  332.         curr = curr->next;
  333.     } while(curr != any);
  334.     return count;
  335. }
  336.  
  337. template<typename Key>
  338. void Ring<Key>::print() const
  339. {
  340.     Node * curr = any;
  341.     if(!curr) {
  342.         cout << "print(): (Ring empty)" << endl;
  343.         return;
  344.     }
  345.     do {
  346.         cout << "\t(" << curr->key<< ")";
  347.         curr = curr->next;
  348.     } while(curr != any);
  349.     cout << endl;
  350. }
  351.  
  352. /******* external function ********/
  353. /****** Example of the split function:
  354. split (r3,r1,true,3,r2,false,6)
  355. r3= 1,2,3,4,5
  356. r1= 1,3,5
  357. r2= 2,5,3,1,4,2
  358. ********/
  359.  
  360. template <typename Key>
  361. Ring<Key> split(const Ring<Key> &source, Ring<Key> &result1, bool dir1, 
  362.                 int len1, Ring<Key> &result2, bool dir2, int len2)
  363. {
  364.     if (source.isEmpty()) {
  365.         cout<<"Empty source Ring"<<endl;
  366.         return source;
  367.     }
  368.  
  369.     if (source.length()==1 || source.length()==2) {
  370.         return source;
  371.     }
  372.  
  373.     if (len1 <= 0 || len2 <= 0) {
  374.         cout << "split():(incorrect lengths)" << endl;
  375.         return source;
  376.     }
  377.  
  378. 	auto i1 = source.begin(); // typename Ring<Key>::iterator i1 = source.begin()
  379. 	auto i2 = source.begin(); // typename Ring<Key>::iterator 21 = source.begin()
  380.  
  381. 	/* I moved second iterator to the 2nd position in original Ring */
  382. 	++i2; // Prefer ++i to i++
  383.  
  384.     if (i1) {
  385.         for (int i= 0; i < len1; ++i) {
  386.             result1.insertLast(i1.getKey());
  387.             if(dir1) {
  388.                 ++i1;
  389.                 ++i1;
  390.             } else {
  391.             	--i1;
  392.                 --i1;
  393.             }
  394.         }
  395.     }
  396. 	cout << result1;
  397.  
  398.     if (i2) {
  399.         for(int i = 0; i < len2; ++i) {
  400.             result2.insertLast(i2.getKey());
  401.             if(dir2) {
  402.                 ++i2;
  403.                 ++i2;
  404.             } else {
  405.             	--i2;
  406.                 --i2;
  407.             }
  408.     	}
  409.     }
  410.  
  411. 	cout << result2;
  412.  
  413. 	return source; // You *ALWAYS* need to return a value. 
  414. 	// This was causing the SEGFAULT (and others like this might also)
  415. }
  416.  
  417. int main()
  418. {
  419.     Ring<int> R1,R2,R3,R4,R5;
  420.  
  421.     R1.insertLast(2);
  422.     R1.insertLast(3);
  423.     R1.insertLast(4);
  424.     R1.insertLast(5);
  425.     R1.insertLast(6);
  426.     R1.insertLast(1);
  427.  
  428.     R2.insertLast(10);
  429.     R2.insertLast(20);
  430.     R2.insertLast(30);
  431.     R2.insertLast(40);
  432.     R2.insertLast(50);
  433.     R2.insertLast(60);
  434.     R2.insertLast(70);
  435.  
  436. 	cout<<"Split function:"<<endl;
  437. 	split(R1,R3,false,3,R4,false,6);
  438.  
  439. 	R5.insertLast(10);
  440.     R5.insertLast(20);
  441.     R5.insertLast(30);
  442.     R5.insertLast(50);
  443.     R5.insertLast(50);
  444.     R5.insertLast(60);
  445.     R5.insertLast(70);
  446.  
  447. 	R5.print();
  448.  
  449. 	cout << __FILE__ << ':' << __LINE__ << " I'm alive (no segfault)" << endl;
  450.  
  451. 	return 0;
  452. }
  453.  
Success #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)
Destructor: ( Ring deleted )
	(10)	(20)	(30)	(50)	(50)	(60)	(70)
prog.cpp:449 I'm alive (no segfault)
Destructor: ( Ring deleted )
Destructor: ( Ring deleted )
Destructor: ( Ring deleted )
Destructor: ( Ring deleted )
Destructor: ( Ring deleted )
https://ideone.com/7af6D7
language:
C++ (gcc 8.3)
created:
6 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!