fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. struct Node {
  6. // data member
  7.     std::string value;
  8. // constructors
  9.     Node (std::string v) : value(v) { }
  10.    Node (const Node& src) : value(src.value) { }
  11. // overloaded operators
  12.     friend std::ostream& operator<< (std::ostream& os, const Node& g);
  13.     friend bool operator< (const Node& lhs, const Node& rhs);
  14.     friend bool operator> (const Node& lhs, const Node& rhs);
  15. };
  16. //====================================================================================
  17. // doubly linkes list accepting any object type as its data member (value)
  18. template<class T>
  19. class Link {
  20. public:
  21.     // public data member
  22.     T value;
  23.  
  24.     // constructor
  25.     Link<T> (T v, Link<T>* p = 0, Link<T>* s = 0) : value(v), prev(p), succ(s) { }
  26.     // copy constructor
  27.     Link<T> (const Link<T>& l) : value(l.value), prev(l.next()), succ(l.previous()) { }
  28.  
  29.     // non-modifying members
  30.     Link<T>* next () const { return succ; }
  31.     Link<T>* previous () const { return prev; }
  32.  
  33.     // modifying members
  34.     Link<T>* insert (Link<T>* n);
  35.     Link<T>* add (Link<T>* n);
  36.     Link<T>* add_ordered (Link<T>* n);
  37. private:
  38.     // private data members
  39.     Link<T>* prev;
  40.     Link<T>* succ;
  41. };
  42.  
  43. std::ostream& operator<<(std::ostream& os, const Node& g) {
  44.     os << g.value ;
  45.     return os;
  46. }
  47.  
  48. bool operator< (const Node& lhs, const Node& rhs) {
  49.     return lhs.value < rhs.value;
  50. }
  51.  
  52. bool operator> (const Node& lhs, const Node& rhs) {
  53.     return lhs.value > rhs.value;
  54. }
  55. //=======================================================================================
  56.  
  57. // It inserts the node passed as a parameter before the node currently pointed to by this.
  58. template<class T>
  59. Link<T>* Link<T>::insert (Link<T>* n) {
  60.     if (!n) return this;
  61.     if (!this) return n;
  62.  
  63.     n->succ = this;
  64.     n->prev = prev;
  65.     if (prev) prev->succ = n;
  66.     prev = n;
  67.  
  68.     return n;
  69. }
  70.  
  71. // It inserts the node passed as a parameter after the node currently pointer to by this.
  72. template<class T>
  73. Link<T>* Link<T>::add (Link<T>* n) {
  74.     if (!n) return this;
  75.     if (!this) return n;
  76.  
  77.     // n->succ = nullptr;
  78.     n->succ = succ;
  79.     n->prev = this;
  80.     succ = n;   // !!!
  81.     if (n->succ) n->succ->prev = n; ///!!!
  82.  
  83.     return n;
  84. }
  85.  
  86. /*
  87.     It inserts the new node such that 
  88.     current node and new node in
  89.     lexicographical order; returns 
  90.     pointer to last node. 
  91.  
  92.     First node in ordered list contains the 
  93.     lexicographically smaller value.
  94.  
  95.     It assumes argument is the tail.
  96. */
  97. template<class T>
  98. Link<T>* Link<T>::add_ordered (Link<T>* n) {
  99.     if (!n) return this;
  100.     if (!this) { std::cout <<"new node first\n"; return n; }
  101.  
  102.     Link<T>* tail = this; 
  103.     if (n->value > tail->value) {
  104.         std::cout <<"new node largest \n";
  105.         return insert(n); // add after current node !!!
  106.     }
  107.  
  108.     Link<T>* current_node = this; 
  109.     while (current_node) {
  110.         if (n->value > current_node->value) {
  111.             std::cout <<"new node spliced \n";
  112.             add(n);
  113.             return this;
  114.         }
  115.         std::cout <<"advance to head\n";
  116.         current_node = current_node->previous();
  117.     } 
  118.  
  119.     add(n); // insert before current node !!
  120.     std::cout << "new node smallest\n";
  121.     return this;
  122. }
  123.  
  124. template<class T>
  125. void create_ordered_list (Link<T>* src, Link<T>*& dest) {
  126.     while (src){    
  127.         Link<T> l(src->value, nullptr, nullptr);
  128.         dest = dest->add_ordered(new Link<T>(l));
  129.         src = src->next();
  130.     }  
  131. }
  132.  
  133. template<class T>
  134. void print(Link<T>* n) {
  135.     Link<T>* tail = n;
  136.  
  137.     if (tail->next()) {
  138.         std::cout <<"[";
  139.         while (tail) {
  140.             std::cout << tail->value;
  141.             if (tail = tail->next()) std::cout <<"\n";
  142.         }
  143.         std::cout <<"]";
  144.     } else if (tail->previous()) {
  145.         std::cout <<"[";
  146.         while (tail) {
  147.             std::cout << tail->value;
  148.             if (tail = tail->previous()) std::cout <<"\n";
  149.         }
  150.         std::cout <<"]";
  151.     }
  152.     getchar();
  153. }
  154. //===============================================================
  155. int main () {
  156.     Link<Node>* head = new Link<Node>(Node("Zeus"));
  157.     head = head->insert(new Link<Node>(Node("Hera")));
  158.     head = head->insert(new Link<Node>(Node("Athena")));
  159.     head = head->insert(new Link<Node>(Node("Ares")));
  160.     head = head->insert(new Link<Node>(Node("Poseidon")));
  161.  
  162.     print<Node>(head);
  163.  
  164.     std::cout <<"\nOrdered lists\n";
  165.     Link<Node>* ordered_list = nullptr;
  166.     create_ordered_list(head, ordered_list);
  167.     print(ordered_list);
  168. }
Success #stdin #stdout 0s 3464KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
[Poseidon
Ares
Athena
Hera
Zeus]
Ordered lists
new node first
advance to head
new node smallest
advance to head
new node smallest
advance to head
new node smallest
new node largest 
[Zeus
Poseidon
Hera
Athena
Ares]
https://ideone.com/wIt4O5
language:
C++14 (gcc 8.3)
created:
9 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!