namespace QuantConnect {

	public class Connection {
		
		private readonly QCAlgorithm algorithm;
		
		// sample API call for MSFT on 2021-01-05 as a reference:
		//"https://data.nasdaq.com/api/v3/datasets/VOL/MSFT/data?start_date=2021-01-05&end_date=2021-01-05&api_key=9xMzJxNYmHaXix2xTpKt"
		
		// base url for API calls
		private readonly string url = "https://data.nasdaq.com/api/v3/datasets/VOL/";
		// API to use in call
		private readonly string apiKey;
		// data point entry to look for in call
		private readonly string entry;
		// index of the entry within the call (so we don't scan for it every time)
		private int entryIndex = -1;
		
		// hash of the current dates stored so they don't have to be refreshed
		private string hash = "null";
		// list of the dates stored under the current hash
		private List<DateTime> dates = new List<DateTime>();
		
		// dictionary of all symbols, containing another dictoriary of date/price equivalents
		Dictionary<String, Dictionary<String, Decimal>> symbolData;
		
		// Connection constructor to import the QCAlgorithm, API key, and entry name
		public Connection(QCAlgorithm algorithm, string apiKey, string entry) {
			this.algorithm = algorithm;
			this.apiKey = apiKey;
			this.entry = entry;
			symbolData = new Dictionary<String, Dictionary<String, Decimal>>();
		}
		
		// used to retrieve a list of all historical IV values for the prior year
		// calls the object cache should the value already exist for that month
		public List<Decimal> Load(string symbol, DateTime date) {
			Print($"Requesting load for: [symbol={symbol}] [date={date.ToString("yyyy'-'MM'-'dd")}]");
			
			// cross reference hash with current time
			// if different then load new dates
			if(hash != $"{date.Year}{date.Month}{date.Day}") {
				hash = $"{date.Year}{date.Month}{date.Day}";
				
				// get all historical dates
				dates = new List<DateTime>();
				DateTime start = new DateTime(date.Year - 1, date.Month, date.Day);
				DateTime end = date;
				for(var dt = start; dt <= end; dt = dt.AddDays(1))
					dates.Add(dt);
			}
			
			return Load(symbol, dates);
		}
		
		private List<Decimal> Load(string symbol, List<DateTime> dates) {
			// if dates is empty then don't run
			if(dates.Count() == 0)
				return new List<Decimal>();
			
			// define storage key
			string key = GetStorageKey(symbol, entry);
			
			// if no dates exist within the dictionary, add default
			if(!symbolData.ContainsKey(symbol)) {
				symbolData[symbol] = new Dictionary<String, Decimal>();
				
				// if symbol does not exist in cache, do nothing
				if(!algorithm.ObjectStore.ContainsKey(GetStorageKey(symbol, entry))) {
					Print($"Cannot find key in object store, loading all dates from API: [key={key}]");
				}
				
				// found key in cache, load into map
				else {
					Print($"Found key in cache, loading all dates found: [key={key}]");
					
					string cached = algorithm.ObjectStore.Read(key);
					string[] cacheArray = cached.Split(',');
					
					for(int i = 0; i < cacheArray.Count(); i += 2) {
						// out of bounds catch
						if(i + 1 >= cacheArray.Count())
							break;
							
						// push data point into map
						decimal value = -1.0m; 
						if(!Decimal.TryParse(cacheArray[i + 1], out value))
							continue;
						symbolData[symbol][cacheArray[i]] = value;
						//algorithm.Log($"Loaded from cache: [symbol={symbol}] [date=[{cacheArray[i]}]] [value={cacheArray[i + 1]}]");
					}
					
					Print($"Loaded all dates into map for: [key={key}]");
				}
			}
			
			// create output list
			List<Decimal> values = new List<Decimal>();
			
			// set the start date to the first date in the list
			DateTime start = dates[0];
			
			// loop through every date
			foreach(DateTime current in dates) {
				// generate a storage key for the date
				string date = current.ToString("yyyy'-'MM'-'dd");
				// create a boolean to determine if the object exists in the cache
				bool exists = symbolData[symbol].ContainsKey(date);
				
				// if object does not exist in cache move to next date
				if(exists) {
					decimal value = symbolData[symbol][date];
					
					// if value is default (-1.0m) then ignore it
					if(value != -1.0m)
						values.Add(value);
					
					if(start != current) {
						// submit request for duration between start and dt
						Print($"Requesting range from NASDAQ API: [symbol={symbol}] [start_date={start.ToString("yyyy'-'MM'-'dd")}] " +
							$"[end_date={current.ToString("yyyy'-'MM'-'dd")}]");
						values.AddRange(Request(symbol, start, current));
					}
					
					start = current;
				}
			}
			
			// do final reuqest validation if the start date doesn't equal the final date in the list
			if(start != dates[dates.Count() - 1]) {
				Print($"Requesting range from NASDAQ API: [symbol={symbol}] [start_date={start.ToString("yyyy'-'MM'-'dd")}] " +
						$"[end_date={dates[dates.Count() - 1].ToString("yyyy'-'MM'-'dd")}]");
				values.AddRange(Request(symbol, start, dates[dates.Count() - 1]));
			}
			
			return values;
		}
		
		private List<Decimal> Request(string symbol, DateTime start, DateTime end) {
			List<Decimal> values = new List<Decimal>();
			
			string data = algorithm.Download(GetFormattedURL(symbol, start.Year, start.Month, start.Day, end.Year, end.Month, end.Day));
			string[] split = data.Split('\n');
			
			// if no lines then return empty list
			if(split.Count() <= 2)
				return values;
			
			// if the entry index has not been parsed yet, find the index of the value
			if(entryIndex == -1) {
				// parse columns
				string[] columns = split[0].Split(',');
				
				// look for column with matching name
				for(int i = 0; i < columns.Count(); i++) {
					if(columns[i] == entry) {
						entryIndex = i;
						break;
					}
				}
			}

			// output string to append to cache
			string cacheExtension = "";
			string key = GetStorageKey(symbol, entry);
			if(algorithm.ObjectStore.ContainsKey(key))
				cacheExtension = algorithm.ObjectStore.Read(key);

			// loop through all entry points and find every value
			for(int i = 1; i < split.Count() - 1; i++) {
				string[] line = split[i].Split(',');
				
				// if missing date then signal error
				if(line.Count() < 1) {
					algorithm.Error($"Data issue, malformed line: [symbol={symbol}] [count={values.Count()}]");
					return values;
				}
				
				// set date to first data point
				string date = line[0];
				
				// if less entries then entry index then we know there is an error
				if(line.Count() <= entryIndex) {
					algorithm.Error($"Data issue, missing data entry: [symbol={symbol}] [date={date}] [count={values.Count()}]");
					return values;
				}
				
				// retrieve value for date and add it to the cache extension and the dictionary
				decimal value = Convert.ToDecimal(line[entryIndex]);
				symbolData[symbol][date] = value;
				//Print($"Retrieved value from NASDAQ: [symbol={symbol}] [date={date}] [value={value}]");
				values.Add(value);
				
				// add value to the cache
				// get the existing value and append it to the end
				cacheExtension += $"{date},{value},";
				//Print($"Cached retrieved value for entry: [key={key}] [date={date}] [value={value}]");
			}
			
			algorithm.ObjectStore.Save(key, cacheExtension);
			Print($"Successfully cached all values for: [key={key}]");
			
			return values;
		}
		
		private string GetFormattedURL(string symbol, int startYear, int startMonth, int startDay, int endYear, int endMonth, int endDay) {
			string formatted = url;
			formatted += $"{symbol}/data.csv?order=asc&" +
					$"start_date={startYear}-{startMonth}-{startDay}" +
					$"&end_date={endYear}-{endMonth}-{endDay}&api_key={apiKey}";
			return formatted;
		}
		
		private string GetStorageKey(string symbol, string entry) {
			return $"{symbol}-{entry}";
		}
		
		private void Print(Object obj) {
			//Console.Write(obj);
		}
	}
}

namespace QuantConnect.Algorithm.CSharp
{
    public class i_kamanu3 : QCAlgorithm
    {
    	// BACKTESTING PARAMETERS
    	// =================================================================================================================
    	
    	// general settings:
    	
    	// set starting cash
    	private int starting_cash = 100000;
    	
    	// backtesting start date time:
    	// date setting variables
    	private int start_year = 2021;
    	private int start_month = 1;
    	private int start_day = 1;
    	
    	// backtesting end date time:
    	// determines whether there is a specified end date
    	// if false it will go to the current date (if 'true' it will go to the specified date)
    	private bool enable_end_date = false;
    	// date setting variables
    	private int end_year = 2021;
    	private int end_month = 1;
    	private int end_day = 1;
    	
    	
    	// universe settings:
    	
    	// number of symbols you want to be observed by the universe at any given time
    	// updates based on the universe resolution set
    	// recommended universe resolution is daily
    	private int stockCount = 10;
    	
    	// data update resolution
    	// changes how often the data updates and algorithm looks for entry
    	// determines how often the function OnData runs
    	// list of resolutions:
    	// Resolution.Tick; Resolution.Second; Resolution.Minute; Resolution.Hour; Resolution.Daily
    	private readonly Resolution resolution = Resolution.Hour;
    	
    	// portfolio allocation
		// percent of portfolio to allocate to overall (evenly divided between securities)
		private readonly decimal portfolioAllocation = 0.5m;
    	
    	
    	// API settings:
    	
    	// NASDAQ API key:
    	private readonly string apiKey = "9xMzJxNYmHaXix2xTpKt";
    	
    	// Data entry from call:
    	// see documentation for details: https://data.nasdaq.com/data/VOL-us-equity-historical-option-implied-volatilities/documentation
    	private readonly string apiDataEntry = "IvMean90";
    	
    	
    	// algorithm parameters:
    	
		// high IV select (selects stocks in the top n percentile of high ivs)
    	// note this value is in decimal form: 0.5 = 50%
    	private readonly decimal highIVPercentile = 0.5m;
    	
    	// drawdown percentile (selects stocks with current iv in bottom n percentile of their yearly max iv)
    	// percent of current IV based on the 12 month historical high IV of a security
    	// note this value is in decimal form: 0.5 = 50%
    	private readonly decimal drawdownIVPercentile = 0.25m;
    	
    	// =================================================================================================================
		
		// creates new universe variable setting
		private List<StockData> universe = new List<StockData>();
		
		// security changes variable
		private SecurityChanges securityChanges = SecurityChanges.None;
		
		// connection object
		private Connection connection;
		
		// month of the current universe
		private int currentMonth = 0;
		
		// determines if universe changed
		private bool load = false;
		
		// iv requirement based on percentile (for log purposes only)
		private decimal ivRequirement = 0.0m;
		
        public override void Initialize()
        {
        	// function to clear ObjectStore cache
        	//ClearCache();
        	
        	// set start date
            SetStartDate(start_year, start_month, start_day);
            // set end date
            if(enable_end_date)
            	SetEndDate(end_year, end_month, end_day);
            // set starting cash
            SetCash(starting_cash);
            
            // add coarse selection for universe
            AddUniverse(CoarseFilterFunction, FineFilterFunction);
            
            // schedule data load for Monday morning before market open
            Schedule.On(DateRules.Every(DayOfWeek.Monday, DayOfWeek.Tuesday, DayOfWeek.Wednesday, DayOfWeek.Thursday, DayOfWeek.Friday), 
            		TimeRules.At(09, 30), LoadSymbols);
            
            // define connection
            connection = new Connection(this, apiKey, apiDataEntry);
        }
        
        // clears cache:
        public void ClearCache() {
        	// clear cache:
			foreach(var key in ObjectStore) {
				ObjectStore.Delete(key.Key);
				Log("Successfully deleted: " + key.Key);
			}
        }

		// filter based on CoarseFundamental
	    public IEnumerable<Symbol> CoarseFilterFunction(IEnumerable<CoarseFundamental> coarse) {
	    	// check if it is the first of the month, otherwise return current universe
	    	if(Time.Month == currentMonth) {
	    		return Universe.Unchanged;
	    	}
	    	
	    	currentMonth = Time.Month;
	    	load = true;
	    	// returns the highest DollarVolume stocks
	    	// returns "totalNumberOfStocks" amount of stocks
	        return (from stock in coarse
        			orderby stock.DollarVolume descending
        			select stock.Symbol);
	    }
	    
	    // filters out all symbols not contained in the NASDAQ exchange
	    // takes the top n
	    public IEnumerable<Symbol> FineFilterFunction(IEnumerable<FineFundamental> fine) {
	    	return (from stock in fine
	    			where stock.SecurityReference.ExchangeId == "NAS"
	    			select stock.Symbol).Take(stockCount);
	    }

        // OnData event is the primary entry point for your algorithm. Each new data point will be pumped in here.
        // Slice object keyed by symbol containing the stock data
        private List<StockData> buffer = new List<StockData>();
        public override void OnData(Slice data) {
        	// if no securities in buffer then return
        	if(buffer.Count() == 0)
        		return;
        		
        	// set holdings for all securities in buffer
        	foreach(StockData sd in buffer)
        		if(!Securities[sd.ticker].Invested)
        			SetHoldings(sd.ticker, portfolioAllocation / buffer.Count(), false, $"[currentiv={sd.current}] [percentile={sd.ivPercentile}] [ivReq={ivRequirement}]");
        			
        	// clear buffer
        	buffer.Clear();
        }
        
        // Loads all Historical IV data into the symbols for the month
        public void LoadSymbols() {
        	if(!load)
        		return;
        	
        	// list to store all current iv values
        	List<Decimal> currentIVs = new List<Decimal>();
        	
        	// load each symbol with historical IV data (note last value is current IV)
        	foreach(StockData sd in universe) {
        		sd.iv = connection.Load(sd.parsed, Time);
        		
        		// if no elements then submit error
        		if(sd.iv.Count() == 0) {
        			Error($"No elements recorded for: {sd.parsed}");
        			continue;
        		}
        		
        		// get and remove last element
        		sd.current = sd.iv[sd.iv.Count() - 1];
        		sd.iv.Remove(sd.iv.Count() - 1);
        		
        		// push to list for storage
        		currentIVs.Add(sd.current);
        		
        		// calculate percentile of current iv:
        		sd.ivPercentile = CalculatePercentile(sd.iv, sd.current);
        		//Debug($"Drawdown IV percentile calculated: [symbol={sd.parsed}] [currentiv={sd.current}] [value={sd.ivPercentile}]");
        	}
        	
        	// calculate high iv percentile requirement
        	decimal requiredHighIV = CalculateValue(currentIVs, highIVPercentile);
        	ivRequirement = requiredHighIV;
        	
        	// filter out all stocks that don't meet the requirements:
        	// 1) current iv is in top nth percentile
        	// 2) current iv is in the bottom nth percentile from its 12 month high
        	var highIVSecurities = (from sd in universe
        				where sd.current >= requiredHighIV
        				where sd.ivPercentile <= drawdownIVPercentile
        				select sd);
        	
        	// push all securities to the buffer
        	foreach(StockData sd in highIVSecurities) {
        		//Debug($"Added symbol to buffer for position entry: [symbol={sd.parsed}] [currentiv={sd.current}] [percentile={sd.ivPercentile}]");
        		buffer.Add(sd);
        	}
        	
        	// update universe to loaded status
        	load = false;
        }
        
        // used to calculate the percentile of a decimal based on the number of elements
        // below its value within the array
        // returns the calculation of:
        // b = elements below
        // t = total elements in list
        // percentile = b / t
        public decimal CalculatePercentile(IEnumerable<Decimal> list, decimal current) {
        	decimal below = 0.0m;
        	foreach(decimal d in list)
        		if(d < current)
        			below++;
        	
        	decimal percentile = below / list.Count();
        	return percentile;
        }
        
        // used to calculate the value of the nth percentile of a list
        // reference: https://stackoverflow.com/questions/8137391/percentile-calculation
        public decimal CalculateValue(IEnumerable<Decimal> list, decimal percentile) {
        	// parse to array
        	var array = list.ToArray();
        	// sort the array
        	Array.Sort(array);
        	
        	// calculate real index, floored index, and fraction
        	decimal realIndex = percentile * (array.Count() - 1);
        	int intIndex = (int)realIndex;
        	decimal fraction = realIndex - intIndex;
        	
        	if(intIndex + 1 < array.Count())
        		return (array[intIndex] * (1 - fraction)) + (array[intIndex + 1] * fraction);
        		
        	else
        		return array[intIndex];
        }
        
        // OnSecuritiesChanged runs when the universe updates current securities
        public override void OnSecuritiesChanged(SecurityChanges changes) {
            securityChanges = changes;
            // remove stocks from list that get removed from universe
            foreach (var security in securityChanges.RemovedSecurities) {
            	List<StockData> stockDatas = universe.Where(x=>x.ticker == security.Symbol).ToList();
            	if (stockDatas.Count >= 1) {
            		// check to see if position is open and if so close position
            		if(Portfolio[stockDatas.First().ticker].Invested) {
            			// closes position
            			Liquidate(stockDatas.First().ticker);
            			Log($"Liquidated {stockDatas.First().parsed} on removal.");
            		}
                	Log($"Removed {stockDatas.First().parsed} from universe.");
            		
            		// removes stock from list if it is removed from the universe
                	universe.Remove(stockDatas.First());
            	}
            }
            
            // add new securities to universe list
            foreach(var security in securityChanges.AddedSecurities) {
            	// create StockData variable for security
            	StockData sd = new StockData();
            	sd.ticker = security.Symbol;
            	// removes QC code
            	sd.parsed = sd.ticker.Split(' ')[0];
    			sd.iv = new List<Decimal>();
    			sd.ivPercentile = Decimal.MaxValue;
    			
            	// add stockdata to universe
            	universe.Add(sd);
            	
            	Log($"Added {sd.parsed} to universe.");
            }
        }
		
		// default class containing all ticker information
		public class StockData {
			// stock ticker
			public string ticker = "";
			public string parsed = "";
			
			// historical IV values
			public List<Decimal> iv;
			
			// current iv value
			public decimal current;
			// iv percentile variables
			public decimal ivPercentile;
		}
    }
}