daily pastebin goal
69%
SHARE
TWEET

Untitled

a guest May 16th, 2018 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Read the value from the file , and then hash the value, then the hashed value put into the table of the desired position,
  2.     if the position is full, remove the exsisting element and do its linear probing */
  3.  
  4. #include <iostream>
  5. #include <fstream>
  6. #include <math.h>
  7.  
  8. using namespace std;
  9.  
  10. void alpha_value();
  11. void method(int size);
  12. void function1(long long int capacity);
  13. void function2(long long int capacity);
  14. void function3(long long int capacity);
  15.  
  16. int main()
  17. {
  18.     alpha_value();
  19.    
  20.     return 0;
  21. }
  22.  
  23. void alpha_value()
  24. {  
  25.     double load_alpha;
  26.     cout << "Enter Load Alpha (0.25/0.50/0.75): " << endl;
  27.     cin >> load_alpha;
  28.    
  29.    
  30.     int x;
  31.     if (load_alpha == 0.25)
  32.     {       x = 1;  }
  33.     if (load_alpha == 0.50)
  34.     {       x = 2;  }
  35.     if (load_alpha == 0.75)
  36.     {       x = 3;  }
  37.    
  38.     switch (x) {
  39.         case 1: //4000037
  40.             method(20);
  41.             break;
  42.        
  43.         case 2: //2000003
  44.             method(20);
  45.             break;
  46.                
  47.         case 3: //1333357
  48.             method(20);
  49.             break;
  50.     }
  51.    
  52. }
  53.  
  54. void method(int size)
  55. {
  56.     int choice;
  57.     cout << "\nEnter Your Choice:\n";
  58.     cout << "1. Method1: the LIFO \n";
  59.     cout << "2. Method2: Double hashing \n";
  60.     cout << "3. Method3 \n";
  61.     cin >> choice;
  62.    
  63.     switch (choice) {
  64.         case 1:
  65.             cout << " Your Choice is: " << choice << endl << endl;
  66.             function1(size);
  67.             break;
  68.            
  69.         case 2:
  70.             cout << " Your Choice is: " << choice << endl << endl;
  71.             function2(size);
  72.             break;
  73.            
  74.         case 3:
  75.             cout << " Your Choice is: " << choice << endl << endl;
  76.             function3(size);
  77.             break;
  78.     }
  79.    
  80. }
  81.  
  82.  
  83.  
  84. void function1(long long int capacity)
  85. {   int copy=capacity;
  86.     int counter=1;
  87.     //int stopper2=0;
  88.     int collisions=0;
  89.     long long int *myarray=new long long int[capacity]; //capacity is the size of the array
  90.    
  91.     for (int i = 0; i < capacity; i ++)
  92.          {   //Setting NULL Values
  93.               myarray[i] = -1;
  94.          }
  95.    
  96.     int long long temp=0;
  97.     ifstream infile; //Reading the values from the file
  98.     infile.open("sample.txt");
  99.    
  100.     while (infile >> temp) //while reading values from the file
  101.     {   int long long final=temp;
  102.    
  103.         if (temp <=0) //converting the negative values to positive
  104.             temp = -temp;
  105.            
  106.         //int stopper =0;
  107.         int i =1;
  108.         int key = temp % capacity; //hash key
  109.         cout << i << ": " << temp << " The Hash Key is: " << key << endl;
  110.        
  111.         long long int my_index=key;
  112.    
  113.         //If there is a pre-exiting value in the hashIndex
  114.         if (myarray[my_index]!=-1)
  115.         {  
  116.            
  117.             int long long temp_value = myarray[my_index]; //copying the exsisting key into temp_value
  118.             myarray[my_index]=final;
  119.             cout << my_index << " : Value Isnt Empty Since " << temp_value << "  Exsits there\n";
  120.             cout << my_index << " Position replaced by " << myarray[my_index] << endl;
  121.             ++collisions;
  122.            
  123.             //find next free space for linear  probing
  124.             cout << "Linear Probing for : " << temp_value;
  125.             while(myarray[my_index] != -1)
  126.             {   my_index++;
  127.                 if (my_index >= copy) //if my_index reaches the end of the array, and hence resetting it to start from the array
  128.                         my_index=0;
  129.                                
  130.             }
  131.             cout << "Empty at Index: " << my_index;
  132.             //storing the temp_value key to the empty space.
  133.             myarray[my_index]=temp_value;
  134.             cout << "\nStored at index " << my_index << " Value which was taken: " << temp_value << "  New Value in Array: "<<  myarray[my_index];
  135.             cout << "Done with the loop at " << my_index << "\n";
  136.             //cin >> stopper;
  137.         }
  138.        
  139.         else //if the if condition doesnt run that means the array at hashIndex is initially empty hence we directly copy the value
  140.             {myarray[my_index]=final;}
  141.            
  142.             cout << "\nNo collision";
  143.             counter++;
  144.             i++;
  145.             cout << "\nDone Adding the element in the loop\n\n";
  146.             //cin >> stopper2;
  147.     }
  148.    
  149.     cout << "\nCollisions: " << collisions;
  150.     infile.close();
  151. }
  152.  
  153.  
  154. void function2(long long int capacity)
  155. {   int collisions=0;
  156.     int i=1;
  157.     int counter=1;
  158.    
  159.     long long int *myarray=new long long int[capacity]; //capacity is the size of the array which we will get from option 4
  160.    
  161.     for (long long int i = 0; i < capacity; i ++)//initializing the array values to -1
  162.          {      //NULL
  163.                 myarray[i] = -1;         
  164.          }
  165.    
  166.     int long long temp=0;
  167.     ifstream infile;
  168.     infile.open("sample.txt");
  169.     while (infile >> temp) //while reading values from the file
  170.     {   long long int final = temp;
  171.         if (temp <=0) //converting the negative values to positive
  172.             temp = -temp;
  173.        
  174.         long long int key = temp % capacity; //hash key
  175.         cout << i << ":   Value: " << final << "    Hash Key:" << key << endl;
  176.        
  177.         string a;
  178.         long long int my_index2=key;
  179.         //finding whether there is any collision
  180.             if (myarray[my_index2] != -1)
  181.                     a = "TRUE";
  182.             else
  183.                     a = "FALSE";
  184.            
  185.            
  186.        
  187.         //If there is a pre-exiting value in the hashIndex
  188.         if (a == "TRUE")
  189.         {    cout << "\nCouldnt Store at Index: " << my_index2 << " Due to collision\n";
  190.              cout << "Value Exsisting at Collision: " << myarray[my_index2];
  191.             int j=1; //counter
  192.             int q=5; //prime number
  193.             long long int hashIndex;
  194.             string b="BTRUE";
  195.             cout << "\nFinding the Empty Index to store value : " << final;
  196.             while(b=="BTRUE")
  197.             {
  198.                 hashIndex = ((key+j*(q-(temp%q)))%capacity);
  199.                 j++;
  200.                
  201.                 if (myarray[hashIndex] == -1)
  202.                     b = "BFALSE";
  203.             }
  204.             cout << "\nEmpty Index Found at : " << hashIndex;
  205.             myarray[hashIndex]=final;
  206.             cout << "\nStored Value: " << final << " at index " << hashIndex;
  207.             //cin >> stopper;
  208.         }
  209.          else
  210.             {myarray[my_index2]=final;
  211.              cout << "Stored: " << myarray[my_index2] << "    At Index: " << my_index2;
  212.             }
  213.                    
  214.             counter++;
  215.             i++;
  216.             cout << "\nDone with This loop\n\n";
  217.             //cin >> stopper2;
  218.     }
  219.     infile.close();
  220.     cout << "Collisions: " << collisions;
  221. }
  222.  
  223.  
  224.  
  225. void function3(long long int capacity)
  226. {
  227.     int long long capacity_copy=capacity;
  228.     int stopping;
  229.     int collision=0;
  230.     long long int copy =capacity;
  231.     long long int *myarray=new long long int[capacity]; //capacity is the size of the array which we will get from option 4
  232.    
  233.     for (long long int i = 0; i < capacity; i ++)  //setting all the values to -1 initially
  234.          {      //NULL
  235.                 myarray[i]= -1;
  236.          }
  237.    
  238.     int long long temp=0;
  239.     //Opening the file
  240.     ifstream infile;
  241.     infile.open("sample.txt");
  242.     int counter =1;
  243.     int check=0;
  244.    
  245.     while (infile >> temp) //while reading values from the file
  246.     {  
  247.         int long long key = 0;
  248.         int long long final =temp;
  249.         if (temp <=0)
  250.             temp =-temp;
  251.         int checker =0;
  252.            
  253.         do{
  254.         key=temp % capacity; //hash key
  255.         long long int my_index3 = key;
  256.         cout << endl << counter << ":   Value:" << final << "   Key:" << key << endl;
  257.        
  258.         checker=0;
  259.                
  260.         //finding whether there is any collision before storing into the array
  261.             string a= "FALSE";
  262.             if (myarray[my_index3]!= -1)
  263.                     { a = "TRUE";}
  264.                 else
  265.                     { a= "FALSE"; }
  266.             cout << "Collision Status(False-No Collision/True-Collision) :" << a << endl;
  267.             //cin >> stopping;
  268.         int n=1000000; //total number of keys
  269.        
  270.         //If theis a pre-exiting value in the array at the index then
  271.         if (a == "TRUE")
  272.         {  
  273.             //copying the current value present at the index
  274.             long long int value_b=0;
  275.             value_b= myarray[my_index3]; //value copied
  276.             int long long b= value_b%capacity_copy; //calculating the key
  277.             cout << "Present Value of B: " << value_b << endl;
  278.             cout << "Present Value of K: " << final << endl;
  279.            
  280.             //finding the distance
  281.             long long int distance_b= (abs(b%n - my_index3))%n;
  282.             long long int distance_k= (abs(key%n - my_index3))%n;
  283.             cout << "Present Key in Array:" << b << "    Distance:" << distance_b << endl; //the present value
  284.             cout << "Calculated Key Value for Temp: " << key << "    Distance:" << distance_k <<  endl; //the key value which we calculated previously
  285.             ++collision;
  286.            
  287.             if (distance_b<=distance_k)//b is closer than a in terms of home position
  288.             {
  289.                 my_index3=my_index3+1;
  290.                 if (my_index3 >= copy) //if the index is in the end of the loop
  291.                         my_index3=0;
  292.                 cout << "Incremented the index, heading back to LOOP\n";
  293.                 //cin >> stopping;
  294.                
  295.             }
  296.             else  //if b>k, we swap and find new position for b's key
  297.             {   cout << "Swapping the values (b to k) \n";
  298.                
  299.                 /*saving the value of original k into the array, since b was already
  300.                 copied in the variable b, so can copy it without losing the value*/
  301.                 myarray[my_index3]=final;
  302.                 cout << "K's Key :" << key << "    Array: " << myarray[my_index3] << endl;
  303.                 final=value_b; //copying b' value to k                
  304.                 temp =final;
  305.                 cout << "K's New Value :" << final;
  306.                 my_index3++;
  307.                 if (my_index3 >= copy)
  308.                         my_index3=0;
  309.                 cout << "\nSwapped.\n";
  310.                 //cin >> stopping;
  311.                
  312.             }
  313.            
  314.         }
  315.        
  316.         else //if the if condition doesnt run that means the array at hashIndex is initially empty hence we directly copy the value
  317.             {   myarray[my_index3]=final; checker=1;}
  318.         counter++;
  319.         cout << "Value Stored at Index:" << my_index3 << "   Value:" << myarray[my_index3];
  320.         cout << endl;
  321.    
  322.     }while (checker!=1);
  323. }
  324.     cout << "\nTotal Collisions: " << collision;
  325.     system("PAUSE");
  326. }
RAW Paste Data
Top