fork download
copy 
  1. #include <vector>
  2. #include <iostream>
  3. #include <fstream>
  4.  
  5. using namespace std;
  6.  
  7. class Node
  8. {
  9.   public:
  10.     Node *prev;
  11.     Node *next;
  12.     int key;
  13.  
  14.     Node(int k, Node *p, Node *n)
  15.     {
  16.         prev = p;
  17.         next = n;
  18.         key = k;
  19.     }
  20.  
  21.     void print() // print the contents of this node
  22.     {
  23.         //cout << "Node: key = " << key << ", prev = " << ((prev) ? prev->key : 0) << ", next = " << ((next) ? next->key : 0) << '\n';
  24.         printf("Node: key = %d, prev = %d, next = %d\n", key, ((prev) ? prev->key : 0),((next) ? next->key : 0));
  25.     }
  26.  
  27.     void printAll() // when printing all nodes in array form, print this node's
  28.     {               // key, and then call this function for the next node
  29.         //cout << "node printall" << '\n';
  30.         if (next)
  31.         {
  32.             //cout << key << ", ";
  33.             printf("%d, ",key);
  34.             next->printAll();
  35.         }
  36.         else
  37.             //cout << key;
  38.             printf("%d",key);
  39.     }
  40. };
  41.  
  42. class DLL
  43. {
  44.   public:
  45.     Node *head;
  46.     Node *tail;
  47.     int size;
  48.  
  49.     DLL()
  50.     {
  51.         size = 0;
  52.     }
  53.  
  54.     void updateTail()
  55.     {
  56.         Node *temp = head;
  57.         while (temp->next)
  58.         {
  59.             temp = temp->next;
  60.         }
  61.         tail = temp;
  62.     }
  63.  
  64.     void insert(int k) // insert node with key k at head
  65.     {
  66.         Node *temp = head;
  67.         while (temp) // check for duplicate key
  68.         {
  69.             if (temp->key == k)
  70.             {
  71.                 //cout << "rejecting - duplicate key " << k << '\n';
  72.                 printf("rejecting - duplicate key %d\n", k);
  73.                 return;
  74.             }
  75.             temp = temp->next;
  76.         }
  77.  
  78.         Node *n = new Node(k, nullptr, nullptr);
  79.         n->next = head;
  80.         if (head)
  81.             head->prev = n;
  82.         head = n;
  83.         updateTail();
  84.         size++;
  85.     }
  86.  
  87.     void insert(int k, int i) // insert node with key k after node with key i
  88.     {
  89.         Node *temp = head;
  90.         while (temp) // check for duplicate key
  91.         {
  92.             if (temp->key == k)
  93.             {
  94.                 //cout << "rejecting - duplicate key " << k << '\n';
  95.                 printf("rejecting - duplicate key %d\n", k);
  96.                 return;
  97.             }
  98.             temp = temp->next;
  99.         }
  100.  
  101.         Node *n = new Node(k, nullptr, nullptr);
  102.         temp = head;
  103.         while (temp)
  104.         {
  105.             if (temp->key == i)
  106.             {
  107.                 n->next = temp->next;
  108.                 n->prev = temp;
  109.                 if (temp->next)
  110.                     temp->next->prev = n;
  111.                 temp->next = n;
  112.                 size++;
  113.                 updateTail();
  114.                 return;
  115.             }
  116.             temp = temp->next;
  117.         }
  118.         //cout << "rejecting - key " << i << " not found" << '\n'; // reject invalid key
  119.         printf("rejecting - key %d not found\n", i);
  120.     }
  121.  
  122.     void remove(int k) // remove node which contains key k
  123.     {
  124.         Node *temp = head;
  125.         while (temp)
  126.         {
  127.             if (temp->key == k)
  128.             {
  129.                 temp->prev->next = temp->next;
  130.                 if (temp->next)
  131.                     temp->next->prev = temp->prev;
  132.                 size--;
  133.                 updateTail();
  134.                 return;
  135.             }
  136.             temp = temp->next;
  137.         }
  138.         //cout << "cannot delete - key " << k << " not found" << '\n';
  139.         printf("cannot delete - key %d not found\n", k);
  140.     }
  141.  
  142.     bool search(int k) // determine if DLL contains key k
  143.     {
  144.         Node *temp = head;
  145.         while (temp)
  146.         {
  147.             if (temp->key == k)
  148.                 return true;
  149.             temp = temp->next;
  150.         }
  151.         return false;
  152.     }
  153.  
  154.     void print() // print all nodes' keys in array format
  155.     {
  156.         //cout << "[ ";
  157.         printf("[ ");
  158.         if (head) head->printAll();
  159.         //cout << " ]" << '\n';
  160.         printf(" ]\n");
  161.     }
  162.  
  163.     void print(int i) // print node at index i
  164.     {
  165.         Node *temp = head;
  166.         for (int j = 0; j < i; j++)
  167.         {
  168.             temp = temp->next;
  169.         }
  170.         temp->print();
  171.     }
  172.  
  173.     void printAll() // print the contents of all nodes in DLL
  174.     {
  175.         for (int i = 0; i < size; i++)
  176.         {
  177.             print(i);
  178.         }
  179.     }
  180. };
  181.  
  182. /* SPLIT STRING FUNCTION */
  183. void split(const string &s, char c, vector<string> &v)
  184. {
  185.     string::size_type i = 0;
  186.     string::size_type j = s.find(c);
  187.  
  188.     while (j != string::npos)
  189.     {
  190.         v.push_back(s.substr(i, j - i));
  191.         i = ++j;
  192.         j = s.find(c, j);
  193.  
  194.         if (j == string::npos)
  195.             v.push_back(s.substr(i, s.length()));
  196.     }
  197. }
  198.  
  199. int main(int argc, const char **argv)
  200. {
  201.     DLL *list = new DLL();
  202.  
  203.     /* GET FILE NAME */
  204.     //cout << "Enter input file name:" << '\n';
  205.     printf("Enter input file name:\n");
  206.  
  207.     string fileName;
  208.     getline(cin, fileName);
  209.     //cout << '\n';
  210.  
  211.     /* READ FIRST LINE OF FILE */
  212.     string input;
  213.     ifstream inFile(fileName.c_str());
  214.  
  215.     if (inFile.is_open())
  216.     {
  217.         getline(inFile, input);
  218.         inFile.close();
  219.     }
  220.     else
  221.     {
  222.         //cout << "unable to open input file " << fileName.c_str() << '\n';
  223.         //cout << "Default ";
  224.         printf("unable to open input file %s\nDefault ", fileName.c_str());
  225.  
  226.         /* DEFAULT LIST OF COMMANDS */
  227.         input = string("1.in 3.in 5.in 3.del 7.in 9.in 11.in 12.in 2.in 1.sch 15.in_7");
  228.     }
  229.  
  230.     //cout << "Input: " << input.c_str() << '\n';
  231.     printf("Input: %s\n", input.c_str());
  232.  
  233.     list->print();
  234.  
  235.     /* PARSE AND EXECUTE COMMANDS */
  236.     vector<string> commands;
  237.     split(input, ' ', commands);
  238.     int key;
  239.     for (int i = 0; i < commands.size(); i++)
  240.     {
  241.         string command = commands[i];
  242.         vector<string> pieces;
  243.         split(command, '.', pieces);
  244.         key = stoi(pieces[0]);
  245.  
  246.         if (pieces[1].length() > 3)
  247.         {
  248.             vector<string> todos;
  249.             split(pieces[1].c_str(), '_', todos);
  250.  
  251.             int location = stoi(todos[1]);
  252.             list->insert(key, location);
  253.         }
  254.         else
  255.         {
  256.             if (pieces[1] == "in")
  257.             {
  258.                 list->insert(key);
  259.             }
  260.             else if (pieces[1] == "del")
  261.             {
  262.                 list->remove(key);
  263.             }
  264.             else if (pieces[1] == "sch")
  265.             {
  266.                 //cout << key << " " << ((list->search(key)) ? "found" : "not found") << '\n';
  267.                 printf("%d %s\n", key, ((list->search(key)) ? "found" : "not found"));
  268.             }
  269.         }
  270.  
  271.         /* PRINT LIST CONTENTS AFTER EACH COMMAND */
  272.         list->print();
  273.     }
  274.  
  275.     //cout << '\n';
  276.     //cout << "Detailed final list contents:" << '\n';
  277.     //cout << '\n';
  278.     printf("\nDetailed final list contents:\n\n");
  279.     list->printAll();
  280.     return 0;
  281. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter input file name:
unable to open input file 
Default Input: 1.in 3.in 5.in 3.del 7.in 9.in 11.in 12.in 2.in 1.sch 15.in_7
[  ]
[ 1 ]
[ 3, 1 ]
[ 5, 3, 1 ]
[ 5, 1 ]
[ 7, 5, 1 ]
[ 9, 7, 5, 1 ]
[ 11, 9, 7, 5, 1 ]
[ 12, 11, 9, 7, 5, 1 ]
[ 2, 12, 11, 9, 7, 5, 1 ]
1 found
[ 2, 12, 11, 9, 7, 5, 1 ]
[ 2, 12, 11, 9, 7, 15, 5, 1 ]

Detailed final list contents:

Node: key = 2, prev = 0, next = 12
Node: key = 12, prev = 2, next = 11
Node: key = 11, prev = 12, next = 9
Node: key = 9, prev = 11, next = 7
Node: key = 7, prev = 9, next = 15
Node: key = 15, prev = 7, next = 5
Node: key = 5, prev = 15, next = 1
Node: key = 1, prev = 5, next = 0
https://ideone.com/HWebpl
language:
C++ (gcc 8.3)
created:
5 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!