// You have an array. For eg [23,12,45,23,9,23,45]. Now you have to print the elements in the order of decreasing frequency, and the same no of times as it is coming in the imput aray. The output for this eg would be 23[3]45[2]12[1]9[1].If frequency of two elements is equal, they should come in the same order as they are coming in the input array.

   1  
   2  struct Node
   3  {
   4      int element;
   5      int frequency;
   6      int order;
   7      struct Node *next;
   8      struct Node *prev;
   9  };
  10  
  11  class FreqList {
  12  
  13   public:
  14      FreqList();
  15      virtual ~FreqList();
  16      virtual void addElement(int newEl);
  17      virtual void Print();
  18      virtual void createSorted();
  19      virtual void printSorted();
  20  
  21   private:
  22      void addAtEnd(int val, int freq, int order);
  23      Node* findElement(int val); 
  24      Node* partition(Node *head, Node *tail, int pivot);
  25      bool  deleteAfter(Node *p, int &val, int &freq, int &order);
  26      void insertSorted(int val, int freq, int order);
  27      void addAfter(Node *p, int val, int freq, int order);
  28      bool deleteFirst(int &val,int &freq, int &order);
  29      int orderOfElement;
  30      int numElements;
  31  
  32      Node *dummy;
  33      Node *dummySorted;
  34      Node *tail;
  35  
  36  };
  37  
  38  
  39  #include <stdio.h>
  40  #include "FreqList.h"
  41  #include <time.h>
  42  #include <stdlib.h>
  43  
  44  FreqList::FreqList() {
  45      dummy = new Node;
  46      dummy->next = NULL;
  47      tail = dummy;
  48      dummySorted = new Node;
  49      dummySorted->next = NULL;
  50      numElements = 0;
  51      orderOfElement = 0;
  52  }
  53  
  54  FreqList::~FreqList() {
  55      //lot of cleanup to be done
  56  }
  57  
  58  void FreqList::addAtEnd(int val, int freq, int order) {
  59      Node *temp = new Node;
  60      temp->element = val;
  61      temp->frequency = freq;
  62      temp->order = order;
  63      temp->next = NULL;
  64  
  65      if(tail != NULL) {
  66  	tail->next = temp;
  67  	tail = temp;
  68      }
  69      else
  70  	printf("Oooops!\n");
  71  }
  72  
  73  /* This will return a pointer whose next is the desired node */
  74  Node * FreqList::findElement(int val) {
  75      Node *temp = dummy;
  76      while(temp->next != NULL) {
  77  	if(temp->next->element == val)
  78  	    return temp;
  79  	else
  80  	    temp=temp->next;
  81      }
  82      return NULL;
  83  }
  84  
  85  void FreqList::addElement(int newEl) {
  86      Node *temp;
  87      ++numElements;
  88      temp = findElement(newEl);
  89      if(temp == NULL) {
  90  	//element not found. New element to be added
  91  	addAtEnd(newEl, 1, ++orderOfElement);
  92  	return;
  93      }
  94      else {
  95  	if(temp->next != NULL) {
  96  	    temp->next->frequency += 1;
  97  	}
  98  	else
  99  	    printf("Hmmph!\n");
 100  	return;
 101      }
 102  }
 103  
 104  void FreqList::insertSorted(int val, int freq, int order) {
 105      Node *p = dummySorted;
 106      while(p->next != NULL) {
 107  	if(freq < p->next->frequency ) {
 108  	    p = p->next;
 109  	}
 110  	else if(freq == p->next->frequency) {
 111  	    if(order > p->next->order) {
 112  		p = p->next;
 113  	    }
 114  	    else {
 115  		break;
 116  	    }
 117  	}
 118  	else {
 119  	    break;
 120  	}
 121      }
 122      addAfter(p, val, freq, order);
 123  }
 124  
 125  void FreqList::createSorted() {
 126      int val, freq, order;
 127      Node *temp = dummy;
 128      while(temp->next != NULL) {
 129  	val = temp->next->element;
 130  	freq = temp->next->frequency;
 131  	order = temp->next->order;
 132  	insertSorted(val, freq, order);
 133  	temp = temp->next;
 134      }
 135  }
 136  
 137  void FreqList::printSorted() {
 138      Node *temp = dummySorted;
 139      while(temp->next != NULL) {
 140  	printf("%d[%d]{%d} ", temp->next->element, temp->next->frequency, \
 141  	       temp->next->order);
 142  	temp = temp->next;	
 143      }
 144      printf("\n");
 145  }
 146  
 147  
 148  void FreqList::addAfter(Node *p, int val, int freq, int order) {
 149      Node *temp = new Node;
 150      temp->element = val;
 151      temp->frequency = freq;
 152      temp->order = order;
 153  
 154      temp->next = p->next;
 155      p->next = temp;
 156  }
 157  
 158  void FreqList::Print() {
 159      Node *temp = dummy;
 160      while(temp->next != NULL) {
 161  	printf("%d[%d]{%d} ", temp->next->element, temp->next->frequency, \
 162  	       temp->next->order);
 163  	temp = temp->next;
 164      }
 165      printf("\n");
 166  } 
 167  
 168  int main()
 169  {
 170      int arr[] = {12,12,23,45,23,9,23,45};
 171      int num;
 172      FreqList *freqList = new FreqList();
 173  
 174      srand((unsigned)time(0));
 175  
 176  
 177      for(int i=0; i<8000; i++)
 178      {   
 179          num = (rand()%10)+1;
 180          //printf("Step: %d El: %d ", i, arr[i] );
 181          freqList->addElement(num);
 182      }   
 183      freqList->Print();
 184      freqList->createSorted();
 185      freqList->printSorted();
 186      return 0;
 187  }
 188  
 189