using namespace std; 
  
class Hash 
{ 
    int BUCKET;    // No. of buckets 
  
    // Pointer to an array containing buckets 
    list<int> *table; 
public: 
    Hash(int V);  // Constructor 
  
    // inserts a key into hash table 
    void insertItem(int x); 
  
    // deletes a key from hash table 
    void deleteItem(int key); 
  
    // hash function to map values to key 
    int hashFunction(int x) { 
        return (x % BUCKET); 
    } 
  
    void displayHash(); 
}; 
  
Hash::Hash(int b) 
{ 
    this->BUCKET = b; 
    table = new list<int>[BUCKET]; 
} 
  
void Hash::insertItem(int key) 
{ 
    int index = hashFunction(key); 
    table[index].push_back(key);  
} 
  
void Hash::deleteItem(int key) 
{ 
  // get the hash index of key 
  int index = hashFunction(key); 
  
  // find the key in (inex)th list 
  list <int> :: iterator i; 
  for (i = table[index].begin(); 
           i != table[index].end(); i++) { 
    if (*i == key) 
      break; 
  } 
  
  // if key is found in hash table, remove it 
  if (i != table[index].end()) 
    table[index].erase(i); 
} 
  
// function to display hash table 
void Hash::displayHash() { 
  for (int i = 0; i < BUCKET; i++) { 
    cout << i; 
    for (auto x : table[i]) 
      cout << " --> " << x; 
    cout << endl; 
  } 
} 
  
// Driver program  
int main() 
{ 
  // array that contains keys to be mapped 
  int a[] = {15, 11, 27, 8, 12}; 
  int n = sizeof(a)/sizeof(a[0]); 
  
  // insert the keys into the hash table 
  Hash h(7);   // 7 is count of buckets in 
               // hash table 
  for (int i = 0; i < n; i++)  
    h.insertItem(a[i]);   
  
  // delete 12 from hash table 
  h.deleteItem(12); 
  
  // display the Hash table 
  h.displayHash(); 
  
  return 0; 
}

#include <iostream>
using namespace std;

int main()
{
    cout << "Hello, World!" << endl;
    return 0;
}

#include <iostream>
int main(){
    const char* const hello = "Hello, world!";
    
    const char* bruh = hello;
    
    char* const yeet = hello;
    
    std::cout << bruh << std::endl;
    
    std::cout << yeet << std::endl;
    
    return 0;
}

/*
    Place your bets!
    
    Will the program:
    a.) Print "Hello, world!" twice?
    b.) Compile error on line 5 (bruh initialize line) because the pointer gets implicit cast to non-const?
    c.) Compile error on line 7 (yeet initialize line) because the char gets implicit cast to non-const?
    d.) Both b and c?
    e.) Compile error line 11 (print yeet) because the pointer is constant and can't be incremented
    f.) Print "Hello, world!" then print the pointer address in hexadecimal
    g.) Both b and e?
    h.) Both c and e?
    i.) B, c, and e?
    
*/

// The answer is in this base 64 string:
// T25seSBjLikKVGhlIGNvbXBpbGVyIGRvZXNuJ3QgYXBwcmVjaWF0ZSB5b3UgbWFraW5nIHRoZSBjaGFyYWN0ZXJzIHRoZSBwb2ludGVyIHJlZmVycyB0byBub24tY29uc3QsIGJ1dCBpdCdzIGZpbmUgd2l0aCB5b3UgY29weWluZyBhIGNvbnN0YW50IHZhbHVlLCBpLmUuIHRoZSBwb2ludGVyLCB0byBhIG5vbi1jb25zdGFudCB2YXJpYWJsZS4KSWYgeW91IHJlcGxhY2UgdGhhdCBsaW5lIHdpdGggY2hhciogY29uc3QgeWVldCA9IGNvbnN0X2Nhc3Q8Y2hhciogY29uc3Q+KGhlbGxvKTsgSXQnbGwgcHJpbnQgIkhlbGxvLCB3b3JsZCEiIHR3aWNlLCB3aGljaCBpcyB2ZXJ5IHN0cmFuZ2UgY29uc2lkZXJpbmcgdGhhdCB5ZWV0IGlzIGEgY29uc3QgcG9pbnRlciwgc28geW91J2QgdGhpbmsgaXQgd291bGQgcHJpbnQgYXMgYSBoZXhhZGVjaW1hbCBiZWNhdXNlIGlmIHlvdSB0cnkgdG8gKCsreWVldCkgd2hpbGUgbG9vcGluZyB0aHJvdWdoIHRoZSBzdHJpbmcsIHlvdSdkIGdldCBhbiBlcnJvciwgYmVjYXVzZSBpdCdzIGNvbnN0IGFuZCBjYW4ndCBiZSBjaGFuZ2VkLgpJbnN0ZWFkIG9mIHVzaW5nIGEgdGVtcGxhdGUgZnVuY3Rpb24gZm9yIG9zdHJlYW06Om9wZXJhdG9yPDwsIHRoZXkgbWFrZSBpdCBhIGZ1bmN0aW9uIHRoYXQgdGFrZXMgdHlwZSBjb25zdCBjaGFyKiwgYW5kIEMrKyBoYXMgbm8gcHJvYmxlbXMgcHJvbW90aW5nIGEgdmFyaWFibGUgdG8gY29uc3RhbnQgd2hlbiBpbXBsaWNpdCBjYXN0aW5nLCBhbmQgaXQgaGFzIG5vIHByb2JsZW1zIGltcGxpY2l0IGNhc3RpbmcgdGhlIGNvbnN0IHBvaW50ZXIgdG8gYSBub3JtYWwgcG9pbnRlciBiZWNhdXNlIGl0J3MgbWFraW5nIGEgY29weS4gVGhlIHBvaW50ZXIgZ2V0cyBjb3BpZWQgYmVjYXVzZSB0aGUgcG9pbnRlciBpcyBwYXNzZWQgYnkgdmFsdWUsIG5vdCByZWZlcmVuY2Uu

#include <string>
#include <iostream>
#include "PlaylistNode.h"
using namespace std;

PlaylistNode::PlaylistNode() {
   uniqueID = "none";
   songName = "none";
   artistName = "none";
   songLength = 0;
   nextNodePtr = 0;
}

PlaylistNode::PlaylistNode(string uniqueID_, string songName_, string artistName_, int songLength_) {
   uniqueID = uniqueID_;
   songName = songName_;
   artistName = artistName_;
   songLength = songLength_;
   nextNodePtr = 0;
}

void PlaylistNode::InsertAfter(PlaylistNode* ptr) {
   this->SetNext(ptr->GetNext());
   ptr->SetNext(this);
}

void PlaylistNode::SetNext(PlaylistNode* ptr) {
   nextNodePtr = ptr;
}

string PlaylistNode::GetID() {
   return uniqueID;
}

string PlaylistNode::GetSongName() {
   return songName;
}

string PlaylistNode::GetArtistName() {
   return artistName;
}

int PlaylistNode::GetSongLength() {
   return songLength;
}

PlaylistNode* PlaylistNode::GetNext() {
   return nextNodePtr;
}

void PlaylistNode::PrintPlaylistNode() {
   cout << "Unique ID: " << uniqueID << endl;
   cout << "Song Name: " << songName << endl;
   cout << "Artist Name: " << artistName << endl;
   cout << "Song Length (in seconds): " << songLength << endl;
}

Playlist::Playlist() {
   head = tail = 0;
}

void Playlist::AddSong(string id, string songname, string artistname, int length) {
   PlaylistNode* n = new PlaylistNode(id, songname, artistname, length);
   if (head == 0) {
      head = tail = n;
   }
   else {
      n->InsertAfter(tail);
      tail = n;
   }
}

bool Playlist::RemoveSong(string id) {
   if (head == NULL) {
      cout << "Playlist is empty" << endl;
      return false;
   }
   
   PlaylistNode* curr = head;
   PlaylistNode* prev = NULL;
   while (curr != NULL) {
      if (curr->GetID() == id) {
         break;
      }
      prev = curr;
      curr = curr->GetNext();
   }
   
   if (curr == NULL) {
      cout << "\"" << curr->GetSongName() << "\" is not found" << endl;
      return false;
   }
   else {
      if (prev != NULL) {
         prev ->SetNext(curr->GetNext());
      }
      else {
         head = curr->GetNext();
      }
      if (tail == curr) {
         tail = prev;
      }
      cout << "\"" << curr->GetSongName() << "\" removed." << endl;
      delete curr;
      return true;
   }
}

bool Playlist::ChangePosition(int oldPos, int newPos) {
   if (head == NULL) {
      cout << "Playlist is empty" << endl;
      return false;
   }
   
   PlaylistNode* prev = NULL;
   PlaylistNode* curr = head;
   
   int pos;
   if (head == NULL || head == tail) {
      return false;
   }
   
   for (pos = 1; curr != NULL && pos < oldPos; pos++) {
      prev = curr;
      curr = curr->GetNext();
   }
   if (curr != NULL) {
      string currentSong = curr->GetSongName();
      
      if (prev == NULL) {
         head = curr->GetNext();
      }
      else {
         prev->SetNext(curr->GetNext());
      }
      if (curr == tail) {
         tail = prev;
      }
      
      PlaylistNode* curr1 = curr;
      prev = NULL;
      curr = head;
      for (pos = 1; curr != NULL && pos < newPos; pos++) {
         prev = curr;
         curr = curr->GetNext();
      }
      if (prev == NULL) {
         curr1->SetNext(head);
         head = curr1;
      }
      else {
         curr1->InsertAfter(prev);
      }
      if (curr == NULL) {
         tail = curr1;
      }
      cout << "\"" << currentSong << "\" moved to position " << newPos << endl;
      return true;
   }
   else {
      cout << "Song's current position is invalid" << endl;
      return false;
   }
}

void Playlist::SongsByArtist(string artist) {
   if (head == NULL) {
      cout << "Playlist is empty" << endl;
   }
   else {
      PlaylistNode* curr = head;
      int i = 1;
      while (curr != NULL) {
         if (curr->GetArtistName() == artist) {
            cout << endl << i << "." << endl;
            curr->PrintPlaylistNode();
         }
         curr = curr->GetNext();
         i++;
      }
   }
}

int Playlist::TotalTime() {
   int total = 0;
   PlaylistNode* curr = head;
   
   while (curr != NULL) {
      total += curr->GetSongLength();
      curr = curr->GetNext();
   }
   return total;
}

void Playlist::PrintList() {
   if (head == NULL) {
      cout << "Playlist is empty" << endl;
   }
   else {
      PlaylistNode* curr = head;
      int i = 1;
      while (curr != NULL) {
         cout << endl << i++ << "." << endl;
         curr->PrintPlaylistNode();
         curr = curr->GetNext();
      }
   }
}

//Get data file at https://codecatch.net/post.php?postID=91e87d73
//Iteration 1 of Wing Project. Solution breaks down around n=35

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
using namespace std;

int getSum(map<int, int> list);
void readData(map<int, float>* data);
void lowestPrice();
void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data);
//void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList);
void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data);
float getPrice(map<int, int> set, map<int, float>* data);

template <typename S>
ostream& operator<<(ostream& os, const vector<S>& vector)
{
	// Printing all the elements using <<
	for (auto element : vector) {
	os << element << " ";
	}
	return os;
}

bool operator==(map<int, int> m1, map<int, int> m2)
{
	if(m1.size() != m2.size())
	return false;

	bool ret = true;

	for(auto it = m1.begin(); it !=m1.end() && ret; it++)
	{
	if(ret && m1.count(it->first) != m2.count(it->first))
	ret = false;

	if(ret && m1.count(it->first) == 1)
	{
	if(m1.at(it->first) != m2.at(it->first))
	ret = false;
	}
	}

	return ret;
}


int main()
{
	map<int, float> data;
	readData(&data);

	vector<map<int, int>> *sumsList;
	sumsList = new vector<map<int, int>>;
	findSums(40, sumsList, &data);

	for(auto el : *sumsList)
	{
	for(auto it = el.begin(); it != el.end(); it++)
	{
	cout << it->first << "->" << it->second << " ";
	}
	cout << getPrice(el, &data) << endl;
	}

	return 0;
}

/* Returns the price of wings given a set of numbers of wings to buy.
	* Returns -1 if the set contains a number that is not possible to buy.
	*/
float getPrice(map<int, int> set, map<int, float>* data)
{
	float price = 0;
	for(auto it = set.begin(); it != set.end(); it++)
	{
	//If data doesn't contain an element of set, return -1
	if(data->count(it->first) == 0)
	return -1;
	
	price += data->at(it->first) * it->second; //pricePerPacket * qtyOfPackets
	}

	return price;
}

/* Adds the elements of list.
	* Suppose mapping is <num, qty>.
	* Returns sum(num*qty)
	*/
int getSum(map<int, int> list)
{
	int sum = 0;
	for(auto it = list.begin(); it != list.end(); it++)
	sum += it->first * it->second;
	return sum;
}

void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data)
{
	map<int, int> currList;

	//Recur when currSum < n
	auto it = data->begin();
	while(it->first <= n && it != data->end())
	{
	findSum(currList, it->first, n, sumsList, data);
	it++;
	}
}

void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data)
{
	//Append x to currList
	if(currList.count(x) == 0)
	currList.emplace(x, 1);
	else
	{
	int val = 1+ currList.at(x);
	currList.erase(x);
	currList.emplace(x, val);
	}

	//Determine current sum, check for return cases
	int currSum = getSum(currList);

	if(currSum > n)
	return;
	else if(currSum == n)
	{

	//Check to make sure no duplicates
	for(auto list : *sumsList)
	{
	if(list == currList)
	return;
	}

	sumsList->push_back(currList);
	return;
	}

	//Recur when currSum < n
	auto it = data->begin();
	while(it->first <= n-x && it != data->end())
	{
	findSum(currList, it->first, n, sumsList, data);
	it++;
	}
}

void readData(map<int, float>* data)
{
	ifstream file ("./data", ifstream::in);

	if(file.is_open())
	{
	int i = 0;
	while(!file.eof())
	{
	float wings, price;
	string skipnl;
	file >> wings;
	file >> price;

	data->emplace(wings, price);

	getline(file, skipnl);
	i++;
	}
	}
}

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <chrono>
using namespace std;

#include <stdio.h>
#include <Windows.h>

int nScreenWidth = 120;			// Console Screen Size X (columns)
int nScreenHeight = 40;			// Console Screen Size Y (rows)
int nMapWidth = 16;				// World Dimensions
int nMapHeight = 16;

float fPlayerX = 14.7f;			// Player Start Position
float fPlayerY = 5.09f;
float fPlayerA = 0.0f;			// Player Start Rotation
float fFOV = 3.14159f / 4.0f;	// Field of View
float fDepth = 16.0f;			// Maximum rendering distance
float fSpeed = 5.0f;			// Walking Speed

int main()
{
	// Create Screen Buffer
	wchar_t *screen = new wchar_t[nScreenWidth*nScreenHeight];
	HANDLE hConsole = CreateConsoleScreenBuffer(GENERIC_READ | GENERIC_WRITE, 0, NULL, CONSOLE_TEXTMODE_BUFFER, NULL);
	SetConsoleActiveScreenBuffer(hConsole);
	DWORD dwBytesWritten = 0;

	// Create Map of world space # = wall block, . = space
	wstring map;
	map += L"#########.......";
	map += L"#...............";
	map += L"#.......########";
	map += L"#..............#";
	map += L"#......##......#";
	map += L"#......##......#";
	map += L"#..............#";
	map += L"###............#";
	map += L"##.............#";
	map += L"#......####..###";
	map += L"#......#.......#";
	map += L"#......#.......#";
	map += L"#..............#";
	map += L"#......#########";
	map += L"#..............#";
	map += L"################";

	auto tp1 = chrono::system_clock::now();
	auto tp2 = chrono::system_clock::now();
	
	while (1)
	{
		// We'll need time differential per frame to calculate modification
		// to movement speeds, to ensure consistant movement, as ray-tracing
		// is non-deterministic
		tp2 = chrono::system_clock::now();
		chrono::duration<float> elapsedTime = tp2 - tp1;
		tp1 = tp2;
		float fElapsedTime = elapsedTime.count();


		// Handle CCW Rotation
		if (GetAsyncKeyState((unsigned short)'A') & 0x8000)
			fPlayerA -= (fSpeed * 0.75f) * fElapsedTime;

		// Handle CW Rotation
		if (GetAsyncKeyState((unsigned short)'D') & 0x8000)
			fPlayerA += (fSpeed * 0.75f) * fElapsedTime;
		
		// Handle Forwards movement & collision
		if (GetAsyncKeyState((unsigned short)'W') & 0x8000)
		{
			fPlayerX += sinf(fPlayerA) * fSpeed * fElapsedTime;;
			fPlayerY += cosf(fPlayerA) * fSpeed * fElapsedTime;;
			if (map.c_str()[(int)fPlayerX * nMapWidth + (int)fPlayerY] == '#')
			{
				fPlayerX -= sinf(fPlayerA) * fSpeed * fElapsedTime;;
				fPlayerY -= cosf(fPlayerA) * fSpeed * fElapsedTime;;
			}			
		}

		// Handle backwards movement & collision
		if (GetAsyncKeyState((unsigned short)'S') & 0x8000)
		{
			fPlayerX -= sinf(fPlayerA) * fSpeed * fElapsedTime;;
			fPlayerY -= cosf(fPlayerA) * fSpeed * fElapsedTime;;
			if (map.c_str()[(int)fPlayerX * nMapWidth + (int)fPlayerY] == '#')
			{
				fPlayerX += sinf(fPlayerA) * fSpeed * fElapsedTime;;
				fPlayerY += cosf(fPlayerA) * fSpeed * fElapsedTime;;
			}
		}

		for (int x = 0; x < nScreenWidth; x++)
		{
			// For each column, calculate the projected ray angle into world space
			float fRayAngle = (fPlayerA - fFOV/2.0f) + ((float)x / (float)nScreenWidth) * fFOV;

			// Find distance to wall
			float fStepSize = 0.1f;		  // Increment size for ray casting, decrease to increase										
			float fDistanceToWall = 0.0f; //                                      resolution

			bool bHitWall = false;		// Set when ray hits wall block
			bool bBoundary = false;		// Set when ray hits boundary between two wall blocks

			float fEyeX = sinf(fRayAngle); // Unit vector for ray in player space
			float fEyeY = cosf(fRayAngle);

			// Incrementally cast ray from player, along ray angle, testing for 
			// intersection with a block
			while (!bHitWall && fDistanceToWall < fDepth)
			{
				fDistanceToWall += fStepSize;
				int nTestX = (int)(fPlayerX + fEyeX * fDistanceToWall);
				int nTestY = (int)(fPlayerY + fEyeY * fDistanceToWall);
				
				// Test if ray is out of bounds
				if (nTestX < 0 || nTestX >= nMapWidth || nTestY < 0 || nTestY >= nMapHeight)
				{
					bHitWall = true;			// Just set distance to maximum depth
					fDistanceToWall = fDepth;
				}
				else
				{
					// Ray is inbounds so test to see if the ray cell is a wall block
					if (map.c_str()[nTestX * nMapWidth + nTestY] == '#')
					{
						// Ray has hit wall
						bHitWall = true;

						// To highlight tile boundaries, cast a ray from each corner
						// of the tile, to the player. The more coincident this ray
						// is to the rendering ray, the closer we are to a tile 
						// boundary, which we'll shade to add detail to the walls
						vector<pair<float, float>> p;

						// Test each corner of hit tile, storing the distance from
						// the player, and the calculated dot product of the two rays
						for (int tx = 0; tx < 2; tx++)
							for (int ty = 0; ty < 2; ty++)
							{
								// Angle of corner to eye
								float vy = (float)nTestY + ty - fPlayerY;
								float vx = (float)nTestX + tx - fPlayerX;
								float d = sqrt(vx*vx + vy*vy); 
								float dot = (fEyeX * vx / d) + (fEyeY * vy / d);
								p.push_back(make_pair(d, dot));
							}

						// Sort Pairs from closest to farthest
						sort(p.begin(), p.end(), [](const pair<float, float> &left, const pair<float, float> &right) {return left.first < right.first; });
						
						// First two/three are closest (we will never see all four)
						float fBound = 0.01;
						if (acos(p.at(0).second) < fBound) bBoundary = true;
						if (acos(p.at(1).second) < fBound) bBoundary = true;
						if (acos(p.at(2).second) < fBound) bBoundary = true;
					}
				}
			}
		
			// Calculate distance to ceiling and floor
			int nCeiling = (float)(nScreenHeight/2.0) - nScreenHeight / ((float)fDistanceToWall);
			int nFloor = nScreenHeight - nCeiling;

			// Shader walls based on distance
			short nShade = ' ';
			if (fDistanceToWall <= fDepth / 4.0f)			nShade = 0x2588;	// Very close	
			else if (fDistanceToWall < fDepth / 3.0f)		nShade = 0x2593;
			else if (fDistanceToWall < fDepth / 2.0f)		nShade = 0x2592;
			else if (fDistanceToWall < fDepth)				nShade = 0x2591;
			else											nShade = ' ';		// Too far away

			if (bBoundary)		nShade = ' '; // Black it out
			
			for (int y = 0; y < nScreenHeight; y++)
			{
				// Each Row
				if(y <= nCeiling)
					screen[y*nScreenWidth + x] = ' ';
				else if(y > nCeiling && y <= nFloor)
					screen[y*nScreenWidth + x] = nShade;
				else // Floor
				{				
					// Shade floor based on distance
					float b = 1.0f - (((float)y -nScreenHeight/2.0f) / ((float)nScreenHeight / 2.0f));
					if (b < 0.25)		nShade = '#';
					else if (b < 0.5)	nShade = 'x';
					else if (b < 0.75)	nShade = '.';
					else if (b < 0.9)	nShade = '-';
					else				nShade = ' ';
					screen[y*nScreenWidth + x] = nShade;
				}
			}
		}

		// Display Stats
		swprintf_s(screen, 40, L"X=%3.2f, Y=%3.2f, A=%3.2f FPS=%3.2f ", fPlayerX, fPlayerY, fPlayerA, 1.0f/fElapsedTime);

		// Display Map
		for (int nx = 0; nx < nMapWidth; nx++)
			for (int ny = 0; ny < nMapWidth; ny++)
			{
				screen[(ny+1)*nScreenWidth + nx] = map[ny * nMapWidth + nx];
			}
		screen[((int)fPlayerX+1) * nScreenWidth + (int)fPlayerY] = 'P';

		// Display Frame
		screen[nScreenWidth * nScreenHeight - 1] = '\0';
		WriteConsoleOutputCharacter(hConsole, screen, nScreenWidth * nScreenHeight, { 0,0 }, &dwBytesWritten);
	}

	return 0;
}