// C++ Structure 

/*The constructor initializes id to 42 when it's called. It's called an initliazation list.

In your example, it is equivalent to
*/

struct TestStruct {
    int id;
    TestStruct()
    {
        id = 42;
    }
};
You can do it with several members as well

struct TestStruct {
    int id;
    double number; 
    TestStruct() : id(42), number(4.1)
    {
    }
};

/* It's useful when your constructor's only purpose is initializing member variables */

struct TestStruct {
    int id;
    double number; 
    TestStruct(int anInt, double aDouble) : id(anInt), number(aDouble) { }
};

// C++ Structure


// HASH TABLE 

// hash table implementation through 
#include <iostream>
#include <string>
#include <unordered_map>

int main ()
{
  std::unordered_map<std::string,double> mymap = {
     {"mom",5.4},
     {"dad",6.1},
     {"bro",5.9} };

  std::string input;
  std::cout << "who? ";
  getline (std::cin,input);

  std::unordered_map<std::string,double>::const_iterator got = mymap.find (input);

  if ( got == mymap.end() )
    std::cout << "not found";
  else
    std::cout << got->first << " is " << got->second;

  std::cout << std::endl;

  return 0;
}

myMap.erase(key); // To erase a key value

vector<vector<string>> groupAnagrams(vector<string>& strs) {
  unordered_map<string, vector<string>> count;
  int i = 0;
  for (auto s : strs)
  {
    sort(s.begin(), s.end());
    count[s].push_back(strs[i++]);
  }
  vector<vector<string>> res;
  for (auto n : count){
    sort(n.second.begin(), n.second.end());
    res.push_back(n.second);
  }
  return res;
}

// 2d map

int main()
{
    std::map< std::string, std::map< int, double > > my_map ;

    my_map[ "hello" ][ 23 ] = 8.9 ;
}

// 2d map

// HASH TABLE

// MULTI SET DATA STRUCTURE

/*
Multisets are containers that store elements following a specific order, and where multiple elements can have equivalent values. 
Default order is to have higher elements at root.
*/

multiset<int> ms;
ms.rbegin();       // Root Element Value
// MULTI SET DATA STRUCTURE


// MAP DATA STRUCTURE 

/*
This is implemented through a heap or a data structure which requires O(logn) lookup and insertion time,
elements are sorted by their key values, this is not a standard hash table with O(1) lookup 
*/

map <key_type, data_type, [comparison_function]>

// Example Map 
map<int, int> hash;

// Adding key value pair key = 2, value = 200
hash[2] = 200 ; 

//Erasing key
hash.erase(2) ;

//Size
hash.size() ;

/*
What if you just wanted to check to see whether a particular key was in the map to begin with 
(e.g., if you wanted to know whether a student was in the class). 
You might think you could do something like this using the bracket notation, but then what will that return 
if the specified key has no associated value? 

Instead, you need to use the find function, which will return an iterator pointing to the value of the element of the
 map associated with the particular key, or if the key isn't found, a pointer to the iterator map_name.end()!
  The following code demonstrates the general method for checking whether a key has an associated value in a map.
*/

map <string, char> grade_list;
grade_list["John"] = 'A';
if(grade_list.find("Tim") == grade_list.end())
{
    cout<<"Tim is not in the map!"<<endl;
}

//Iterator

map<parameters>::iterator iterator_name;
/*
where parameters are the parameters used for the container class this iterator will be used for.
This iterator can be used to iterate in sequence over the keys in the container. 
Ah, you ask, but how do I know the key stored in the container? Or, even better, what exactly does it mean to 
dereference an iterator over the map container? The answer is that when you dereference an iterator over the map class,
you get a "pair", which essentially has two members, first and second. First corresponds to the key, second to the
value. Note that because an iterator is treated like a pointer, to access the member variables, you need to use the
arrow operator, ->, to "dereference" the iterator. 

For instance, the following sample shows the use of an iterator (pointing to the beginning of a map) to access the
 key and value.
 */
std::map <string, char> grade_list;
grade_list["John"] = 'A';
// Should be John
std::cout<<grade_list.begin()->first<<endl;
// Should be A
std::cout<<grade_list.begin()->second<<endl;
/*
Finally, you might wonder what the cost of using a map is. One issue to keep in mind is that insertion of a 
new key (and associated value) in a map, or lookup of the data associated with a key in a map, can take up 
to O(log(n)) time, where n is the size of the current map. This is potentially a bit slower than some hash tables
 with a good hashing function, and is due to the fact that the map keys are stored in sorted order for use by iterators. 
*/

// MAP DATA STRUCTURE 

//  SET DATA STRUCTURE  //


set< pair<int,int> > :: iterator it ;           // Declaring an Iterator

it = segment.lower_bound(value) ;               // Returns address of element more than or equal to value
low=std::lower_bound (v.begin(), v.end(), 20);  //Returns an iterator pointing to the first element in the range 
                                                //[first,last) which does not compare less than val=20.

it = segment.upper_bound(move_pos) ;            // Returns address of element more than value
up= std::upper_bound (v.begin(), v.end(), 20); //Returns an iterator pointing to the first element in the range 
                                                //[first,last) which compares greater than val.

set.end() -> null element , if element not found then the iterator points to this .

set<int> S;
S.find(2) == S.end() // Element 2 not found
S.find(2) != S.end() // Element 2 found in set

//  SET DATA STRUCTURE  //



// QUEUE AND STACK STL C++ //


queue< int > Q ;                  // Declaring a Queue 
stack< int > S ;

Q.push(a) ; S.push(a) ;                      // Pushing an Element 

Q.pop() ;	S.pop() ;					// Popping an element

Q.front() ;	S.top() ;						// Element Present at the Top 


// QUEUE AND STACK STL C++  //

// VECTOR STL C++ //

// Initialising a vector of n+1 elements
 vector<int> cntPerfectSquares(n + 1, INT_MAX);
 // Initialising a vector of n*n dimensions
 vector<vector<int>> vec(n, vector<int>(n, INT_MAX));

// Erasing an element from the vector
vec.erase(std::remove(vec.begin(), vec.end(), int_to_remove), vec.end()) ;   

//Adding an element to the vector
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    vector <int> g1;
    vector <int> :: iterator i;
    vector <int> :: reverse_iterator ir;
 
    for (int i = 1; i <= 5; i++)
        g1.push_back(i);
 
    cout << "Output of begin and end\t:\t";
    for (i = g1.begin(); i != g1.end(); ++i)
        cout << *i << '\t';
 
    cout << endl << endl;
    cout << "Output of rbegin and rend\t:\t";
    for (ir = g1.rbegin(); ir != g1.rend(); ++ir)
        cout << '\t' << *ir;
 
    return 0;
 
}

/*
Output:
1 2 3 4 5
5 4 3 2 1
*/

// To check whether vector is empty or not
!myvector.empty()

bool compare(const Interval &a, const Interval &b){
        return a.start < b.start;
}

sort(myvector.begin(), myvector.end(), compare); // sorting a vector of structs
sort(numbers.begin(), numbers.end(), greater<int>());   // sort in descending order vector

{1, 2} // vector of two numbers, vector representation in code

// VECTOR STL C++ //

// String Operations

string s;
reverse(s.begin(), s.end())      // reversing a string

// String Operations

// Converting Number to String in C++ //

string s = to_string(number) ;

string convertInt(int number)
{
   stringstream ss;		//create a stringstream
   ss << number;		//add number to the stream
   return ss.str();		//return a string with the contents of the stream
}

// Converting Number to String in C++ //

atoi(s); stoi(s);    // Converting String to Number C++
to_string(num);      // Converting Number to String

// Initialising an Array with a value //

memset(dp, value, sizeof(dp));

// Initialising an Array with a value //


// Finding Power and Square Root in C++ //

pow(2,N) ;  // 2^N 

sqrt(N) ;

// Finding Power and Square Root in C++ //


// DJIKSTRA IMPLEMENTATION USING SET DATA STRUCTURE //


struct compare
{
	bool operator()(int x,int y)
	{
		if(d[x]!=d[y])
			return d[x] < d[y] ;
		else
		    return x < y ;	
	}
};

set<int,compare> S ;

void djikstra()
{
	S.insert(source) ;
	visited[source] = 1 ;
	d[source] = 0 ;

    while(!S.empty())
    {
         int v = *S.begin() ;
         visited[v] = 1 ;
         S.erase(S.begin())

         for(int i=0;i<edge[v].size();i++)
         {
               int adj_node = edge[v][i].first ;
               int weight = edge[v][i].second ;

               if(!visited[adj_node])
               {
               		if(d[adj_node] > d[v] + weight)
               		{
               			S.erase(adj_node) ;
               			d[adj_node] = d[v] + weight ;
               			S.insert(adj_node) ;
               		}
               }
         }
    }

}


// DJIKSTRA IMPLEMENTATION USING SET DATA STRUCTURE //



// SORTING ARRAY IN ASCENDING AND DESCENDING ORDER //

sort(arr,arr+n) ;                        //  Ascending Order

sort(arr,arr+n,greater<int>())           //  Descending Order

// SORTING ARRAY IN ASCENDING AND DESCENDING ORDER // 


// PRIORITY QUEUE

priority_queue<int, std::vector<int>, std::greater<int> > my_min_heap; // To make a min heap
priority_queue<int> my_min_heap; // To make max heap
my_min_heap.top(); // to get the root element
my_min_heap.top(); // to pop the top element
my_min_heap.push(2); // to insert an element inside the heap
my_min_heap.pop();   // pop the root element of heap
my_min_heap.size(); // size of the heap 

// PRIORITY QUEUE

// TERNARY SEARCH //

/*
>> What is ternary search?

Suppose you have a function f which is decreasing up to a certain point then increases (or vice versa) in the interval [a,b]. In the next paragraph, I assume decreasing first then increasing -- otherwise reverse the < and > signs.

So, now lets say you want to find the point x in [a,b] such that f(x) is a minimum 
(the point of the switch). At the beginning, everything in [a,b] is a candidate. 
Pick numbers thirds along the way, (so pick g = a + (b-a)/3 and h = a + 2*(b-a)/3). 
You will calculate f(g) and f(h). If f(g) < f(h), either g and h are on opposite sides of the 
minimum point, or g and h are both to its right. So, we can be sure that x is not in [h,b] 
and can recurse on [a,h]. Otherwise, we can be sure that x is not in [a,g] and just recurse on [g,b].
*/

min = a;
max = b;
while(max - min > epsilon){
    g = min + (max-min)/3;
    h = min + 2*(max-min)/3;
    if(f(g) < f(h))
        max = h;
    else
        min = g;
}
return (max+min)/2;


// TERNARY SEARCH //

Useful_Information.cpp
Displaying Useful_Information.cpp.