| Overall Statistics |
|
Total Trades 2182 Average Win 6.11% Average Loss -0.75% Compounding Annual Return 1662.453% Drawdown 38.300% Expectancy 0.425 Net Profit 38206.760% Sharpe Ratio 3.233 Loss Rate 84% Win Rate 16% Profit-Loss Ratio 8.17 Alpha 3.389 Beta 0.05 Annual Standard Deviation 1.045 Annual Variance 1.092 Information Ratio 2.742 Tracking Error 1.31 Treynor Ratio 67.699 Total Fees $24587517.55 |
using QuantConnect.Data;
using QuantConnect.Data.Custom;
using QuantConnect.Indicators;
using QuantConnect.Securities;
using System;
using System.Collections.Generic;
using QuantConnect.Data.Market;
using System.Linq;
using MathNet.Numerics.Statistics;
using QuantConnect.Data.Consolidators;
#if PETTER
using System.Windows.Media;
using LiveCharts.Wpf;
#endif
namespace QuantConnect.Algorithm.CSharp
{
public partial class MirrorAlgorithm : QCAlgorithm
{
private enum Charting
{
Disabled,
FullResolution,
DailyEquityOnly,
ProfitPerDelay,
}
private const Charting _charting = Charting.DailyEquityOnly;
private static readonly bool _useStoploss = false;
private const decimal _leverage = 1;
private const decimal maxLeverage = 2;
private static MirrorAlgorithm _instance;
public override void Initialize()
{
SetCash(100000);
SetStartDate(2016, 1, 4); //2017, 1, 4
//SetEndDate(2016, 10, 1);
try
{
ActualInitialization();
}
catch (Exception e)
{
ReportException(e, this);
}
}
public static void ReportException(Exception e, QCAlgorithm algo)
{
algo.Error(algo.Time + ": " + e.Message + "\n" + e.StackTrace);
algo.Log(algo.Time + ": " + e.Message + "\n" + e.StackTrace);
}
#if PETTER
private SignalView _signalView;
#endif
private void ActualInitialization()
{
_instance = this;
var res = Resolution.Minute;
var first = AddEquity("OASM", res, leverage: maxLeverage);
first.SlippageModel = new ConstantSlippageModel(0.75m / 100);
AddTradable(first);
Schedule.On(DateRules.EveryDay(), TimeRules.At(0, 0, 1), AtMidnight);
//TODO: keeping this disabled unless we figure out it's a good idea
//Schedule.On(DateRules.EveryDay(), TimeRules.Every(TimeSpan.FromSeconds(5)), CheckForSensitiveEvents);
SetBenchmark(first.Symbol);
#if PETTER
if (_charting != Charting.Disabled)
_signalView = SignalView.ShowInNewThread(CreateSignalViewOptions());
#endif
}
#if PETTER
private SignalView.SetupOptions CreateSignalViewOptions()
{
var options = new SignalView.SetupOptions();
options.AxisGenerator = CreateExtraAxes;
return options;
}
private IEnumerable<Axis> CreateExtraAxes()
{
yield return new Axis()
{
MinValue = -210,
MaxValue = 210,
Sections = new SectionsCollection
{
new AxisSection
{
Value = 0,
SectionWidth = 1,
Stroke = new SolidColorBrush(Color.FromRgb(248, 213, 72))
},
new AxisSection
{
Value = 100,
SectionWidth = 1,
Fill = new SolidColorBrush
{
Color = Color.FromRgb(0, 255, 0),
Opacity = .8
}
},
new AxisSection
{
Value = -100,
SectionWidth = 1,
Fill = new SolidColorBrush
{
Color = Color.FromRgb(255, 0, 0),
Opacity = .8
}
}
}
};
}
#endif
private void AtMidnight()
{
#if PETTER
if (_charting != Charting.Disabled && _charting != Charting.ProfitPerDelay)
{
_signalView.SetXLabel(Time.ToShortDateString());
_signalView.PlotEquity((double)Portfolio.TotalPortfolioValue);
}
#endif
}
public override void OnEndOfAlgorithm()
{
#if PETTER
if (_signalView != null)
_signalView.JoinThread();
#endif
}
private void CheckForSensitiveEvents()
{
/*_sensitiveEvents.Update();
if (_sensitiveEvents.InSensitiveZone && _components[0].Exchange.ExchangeOpen && _components[0].HoldStock)
{
ClosePosition();
}*/
}
public override void OnData(Slice slice)
{
foreach (var kv in slice.Bars)
{
Tradable tradable;
if (_tradables.TryGetValue(kv.Key, out tradable))
{
tradable.OnData(kv.Value);
}
}
}
private void AddTradable(Security sec)
{
_tradables[sec.Symbol] = new Tradable(sec);
}
private readonly Dictionary<Symbol, Tradable> _tradables = new Dictionary<Symbol, Tradable>();
private sealed class Tradable
{
private readonly Security _security;
private readonly RollingWindow<double> _priceWindow = new RollingWindow<double>(2000);
private readonly VirtualEquity _equity;
private bool _stopped;
private decimal _peakEquity;
private decimal _floorStopEquity;
public Tradable(Security sec)
{
_security = sec;
_equity = new VirtualEquity(sec)
{
Slippage = 0,
TradeFeeFraction = 0,
};
}
public void OnData(TradeBar bar)
{
_peakEquity = Math.Max(_peakEquity, _equity.GetEquity());
if (_stopped)
{
_floorStopEquity = Math.Min(_floorStopEquity, _equity.GetEquity());
if (_equity.GetEquity() >= _floorStopEquity * 1.05m)
_stopped = false;
}
_priceWindow.Add((double)bar.Close);
FindMirrors();
if (_useStoploss && _equity.GetEquity() < 0.95m * _peakEquity)
{
_stopped = true;
_floorStopEquity = _equity.GetEquity();
_instance.Liquidate(_security.Symbol);
}
}
private double GetPrice(int i)
{
if (i < _priceWindow.Count)
return _priceWindow[i];
return _priceWindow[_priceWindow.Count - 1];
}
private void FindMirrors()
{
double estimate = 0;
int maxWidth = 10;
for (int width = 2; width <= maxWidth; ++width)
{
double squaredErrorSum = 0;
double min = double.MaxValue;
double max = -double.MaxValue;
for (int i = 0; i < width; ++i)
{
double target = GetPrice(i);
double source = GetPrice(i + width);
min = Math.Min(target, min);
min = Math.Min(source, min);
max = Math.Max(target, max);
max = Math.Max(source, max);
double error = target - source;
squaredErrorSum += error * error;
}
double changeSince = GetPrice(0) / GetPrice(width) - 1;
double dissimilarity = Math.Sqrt(squaredErrorSum / width) / (max - min + double.Epsilon);
double sigmoid = 1 / (1 + Math.Exp(1 / dissimilarity));
estimate += changeSince * 2 * (sigmoid - 0.5);
}
estimate /= (maxWidth - 1);
if (Math.Abs(estimate) > 0.02)
{
_instance.SetHoldings(_security.Symbol, Math.Sign(estimate) * _leverage);
}
}
}
}
}/*
* QUANTCONNECT.COM - Democratizing Finance, Empowering Individuals.
* Lean Algorithmic Trading Engine v2.0. Copyright 2014 QuantConnect Corporation.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
using QuantConnect.Indicators;
using System;
namespace QuantConnect.Algorithm.CSharp
{
/// <summary>
/// This indicator computes the n-period population standard deviation.
/// </summary>
public class StandardDeviationOverflowSafe : Variance
{
/// <summary>
/// Initializes a new instance of the StandardDeviation class with the specified period.
///
/// Evaluates the standard deviation of samples in the lookback period.
/// On a dataset of size N will use an N normalizer and would thus be biased if applied to a subset.
/// </summary>
/// <param name="period">The sample size of the standard deviation</param>
public StandardDeviationOverflowSafe(int period)
: this("STD" + period, period)
{
}
/// <summary>
/// Initializes a new instance of the StandardDeviation class with the specified name and period.
///
/// Evaluates the standard deviation of samples in the lookback period.
/// On a dataset of size N will use an N normalizer and would thus be biased if applied to a subset.
/// </summary>
/// <param name="name">The name of this indicator</param>
/// <param name="period">The sample size of the standard deviation</param>
public StandardDeviationOverflowSafe(string name, int period)
: base(name, period)
{
}
/// <summary>
/// Gets a flag indicating when this indicator is ready and fully initialized
/// </summary>
public override bool IsReady
{
get { return Samples >= Period; }
}
/// <summary>
/// Computes the next value of this indicator from the given state
/// </summary>
/// <param name="input">The input given to the indicator</param>
/// <param name="window">The window for the input history</param>
/// <returns>A new value for this indicator</returns>
protected override decimal ComputeNextValue(IReadOnlyWindow<IndicatorDataPoint> window, IndicatorDataPoint input)
{
double val = Math.Sqrt((double)base.ComputeNextValue(window, input));
return (decimal)val.Clamp(_min, _max);
}
private static readonly double _max = (double)decimal.MaxValue * 0.01;
private static readonly double _min = (double)decimal.MinValue * 0.01;
}
}using System;
using System.Collections.Generic;
using System.Reflection;
namespace QuantConnect.Algorithm.CSharp
{
public static class Xtend
{
public static FieldInfo GetPrivateField(Type type, string name)
{
return type.GetField(name, BindingFlags.NonPublic | BindingFlags.Instance);
}
public static FieldInfo GetPrivateField<MyType>(this MyType dummy, string name)
{
return GetPrivateField(typeof(MyType), name);
}
public static object GetPrivateFieldValue(Type type, object instance, string name)
{
var fieldInfo = GetPrivateField(type, name);
if (fieldInfo == null)
throw new InvalidOperationException("Unable to find field with name " + name);
return fieldInfo.GetValue(instance);
}
public static object GetPrivateFieldValue<MyType>(this MyType instance, string name)
{
return GetPrivateFieldValue(typeof(MyType), instance, name);
}
public static T Clamp<T>(this T val, T min, T max) where T : IComparable
{
XMath.Clamp(ref val, min, max);
return val;
}
public static void Shuffle<T>(this IList<T> list, Random rng)
{
int n = list.Count;
while (n > 1)
{
n--;
int k = rng.Next(n + 1);
T value = list[k];
list[k] = list[n];
list[n] = value;
}
}
public static int Argmax(this IList<int> list)
{
int maxIndex = list.Count - 1;
var max = list[maxIndex];
for (int index = list.Count - 2; index >= 0; --index)
{
var x = list[index];
if (x > max)
{
maxIndex = index;
max = x;
}
}
return maxIndex;
}
public static int Argmin(this IList<int> list)
{
int minIndex = list.Count - 1;
var min = list[minIndex];
for (int index = list.Count - 2; index >= 0; --index)
{
var x = list[index];
if (x < min)
{
minIndex = index;
min = x;
}
}
return minIndex;
}
public static int Argmax(this IList<double> list)
{
int maxIndex = list.Count - 1;
var max = list[maxIndex];
for (int index = list.Count - 2; index >= 0; --index)
{
var x = list[index];
if (x > max)
{
maxIndex = index;
max = x;
}
}
return maxIndex;
}
public static int Argmin(this IList<double> list)
{
int minIndex = list.Count - 1;
var min = list[minIndex];
for (int index = list.Count - 2; index >= 0; --index)
{
var x = list[index];
if (x < min)
{
minIndex = index;
min = x;
}
}
return minIndex;
}
}
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace QuantConnect.Algorithm.CSharp
{
public static class XMath
{
public static bool IsPowerOfTwo(ulong x)
{
return (x & (x - 1)) == 0;
}
public static int Log2(int v)
{
int r = 0xFFFF - v >> 31 & 0x10;
v >>= r;
int shift = 0xFF - v >> 31 & 0x8;
v >>= shift;
r |= shift;
shift = 0xF - v >> 31 & 0x4;
v >>= shift;
r |= shift;
shift = 0x3 - v >> 31 & 0x2;
v >>= shift;
r |= shift;
r |= (v >> 1);
return r;
}
public static void Clamp<T>(ref T val, T min, T max) where T : IComparable
{
if (min.CompareTo(val) > 0)
val = min;
else if (max.CompareTo(val) < 0)
val = max;
}
}
}using MathNet.Numerics.Statistics;
using QuantConnect.Indicators;
using QuantConnect.Orders;
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuantConnect.Algorithm.CSharp
{
sealed class SlippageMeasurement
{
private const int _numOrderTypes = 7;
private readonly QCAlgorithm _algo;
private sealed class OrderInfo
{
public OrderType Type;
public int Dir;
public decimal PriceAtIssue;
public decimal VolumeFilled;
public decimal DollarVolumeFilled;
public decimal AverageFillPrice
{
get
{
return DollarVolumeFilled / VolumeFilled;
}
}
public decimal SlippageInPrice
{
get
{
return -Dir * (AverageFillPrice - PriceAtIssue);
}
}
public decimal SlippageAsFraction
{
get { return SlippageInPrice / PriceAtIssue; }
}
}
private readonly ConcurrentDictionary<int, OrderInfo> _orders = new ConcurrentDictionary<int, OrderInfo>();
private readonly ConcurrentQueue<OrderEvent> _orderEvents = new ConcurrentQueue<OrderEvent>();
private readonly RollingWindow<OrderInfo>[] _statWindow;
public SlippageMeasurement(QCAlgorithm algo, int windowSize)
{
_algo = algo;
_statWindow = new RollingWindow<OrderInfo>[(_numOrderTypes + 1) * 3 + 1]; //(orderType + anyOrderType) * (direction + anyDirection) + any
for (int i = 0; i < _statWindow.Length; ++i)
{
_statWindow[i] = new RollingWindow<OrderInfo>(windowSize);
}
}
private RollingWindow<OrderInfo> GetStatWindow(int orderType = -1, int dir = 0)
{
if (orderType < -1)
throw new ArgumentException("orderType");
if (orderType < 0 && dir < 0)
return _statWindow[0];
return _statWindow[1 + (1 + orderType) * 3 + (1 + dir)];
}
public void NewOrder(Order order)
{
if (order == null)
throw new ArgumentNullException("order");
decimal priceAtIssue = _algo.Securities[order.Symbol].Price;
if (order is StopMarketOrder)
priceAtIssue = ((StopMarketOrder)order).StopPrice;
else if (order is StopLimitOrder)
priceAtIssue = ((StopLimitOrder)order).LimitPrice;
else if (order is LimitOrder)
priceAtIssue = ((LimitOrder)order).LimitPrice;
NewOrder(order.Id, order.Direction == OrderDirection.Buy? 1 : -1, priceAtIssue, order.Type);
}
public void NewOrder(OrderTicket order)
{
if (order == null)
throw new ArgumentNullException("order");
decimal priceAtIssue = _algo.Securities[order.Symbol].Price;
if (order.OrderType == OrderType.StopMarket)
{
priceAtIssue = order.SubmitRequest.StopPrice;
}
else if (order.OrderType == OrderType.Limit || order.OrderType == OrderType.StopLimit)
{
priceAtIssue = order.SubmitRequest.LimitPrice;
}
NewOrder(order.OrderId, Math.Sign(order.Quantity), priceAtIssue, order.OrderType);
}
public void NewOrder(int orderId, int direction, decimal priceAtIssue, OrderType type)
{
if ((int)type >= _numOrderTypes)
throw new ArgumentException("Order type " + type.ToString() + " has too high enum value", "type");
_orders[orderId] = new OrderInfo()
{
Type = type,
Dir = direction,
PriceAtIssue = priceAtIssue,
};
}
private void OnFill(int orderId, decimal quantity, decimal actualPrice)
{
OrderInfo orderInfo;
if (_orders.TryGetValue(orderId, out orderInfo))
{
orderInfo.VolumeFilled += quantity;
orderInfo.DollarVolumeFilled += quantity * actualPrice;
}
}
private void OnOrderClosed(int orderId)
{
OrderInfo orderInfo;
if (_orders.TryRemove(orderId, out orderInfo))
{
if (orderInfo.VolumeFilled > 0)
{
RecordOrder(orderInfo);
}
}
}
public void OnOrderEventAsync(OrderEvent ev)
{
_orderEvents.Enqueue(ev);
}
public void Process()
{
OrderEvent ev;
while (_orderEvents.TryDequeue(out ev))
{
if (ev.Status == OrderStatus.PartiallyFilled || ev.Status == OrderStatus.Filled)
{
OnFill(ev.OrderId, ev.AbsoluteFillQuantity, ev.FillPrice);
}
if (ev.Status.IsClosed())
{
OnOrderClosed(ev.OrderId);
}
}
}
private void RecordOrder(OrderInfo orderInfo)
{
GetStatWindow().Add(orderInfo);
GetStatWindow((int)orderInfo.Type).Add(orderInfo);
GetStatWindow(-1, orderInfo.Dir).Add(orderInfo);
GetStatWindow((int)orderInfo.Type, orderInfo.Dir).Add(orderInfo);
}
public override string ToString()
{
var builder = new StringBuilder();
builder.AppendLine("Slippage % Mean VW Std:");
PrintStatLine("All", builder, GetStatWindow());
PrintStatLine("Buy", builder, GetStatWindow(-1, 1));
PrintStatLine("Sell", builder, GetStatWindow(-1, -1));
for (int i = 0; i < _numOrderTypes; ++i)
{
var type = (OrderType)i;
PrintStatLine(type.ToString(), builder, GetStatWindow(i));
}
for (int i = 0; i < _numOrderTypes; ++i)
{
var type = (OrderType)i;
for (int dir = -1; dir < 1; ++dir)
{
if (dir == 0)
dir = 1;
PrintStatLine(type.ToString() + (dir == 1? " Buy" : " Sell"), builder, GetStatWindow(i, dir));
}
}
return builder.ToString();
}
private static double GetMean(IEnumerable<OrderInfo> window)
{
return window.Select(x => (double)x.SlippageAsFraction).Average();
}
private static double GetVolumeWeighted(IEnumerable<OrderInfo> window)
{
double totalDollarVolume = window.Sum(x => (double)x.DollarVolumeFilled);
double volumeWeighted = totalDollarVolume > 0 ? window.Select(x => (double)x.SlippageAsFraction * (double)x.DollarVolumeFilled).Sum() / totalDollarVolume : 0;
return volumeWeighted;
}
private static double GetStandardDeviation(IEnumerable<OrderInfo> window)
{
return window.Select(x => (double)x.SlippageAsFraction).StandardDeviation();
}
private static void PrintStatLine(string caption, StringBuilder builder, IEnumerable<OrderInfo> window)
{
if (!window.Any())
return;
builder.Append(caption);
builder.Append(": ");
builder.Append(GetMean(window).ToString("P3"));
builder.Append(" ");
builder.Append(GetVolumeWeighted(window).ToString("P3"));
builder.Append(" ");
builder.Append(GetStandardDeviation(window).ToString("P3"));
builder.AppendLine();
}
public double GetMeanSlippage()
{
return GetMean(GetStatWindow());
}
public double GetVolumeWeightedSlippage()
{
return GetVolumeWeighted(GetStatWindow());
}
public double GetStandardDeviationOfSlippage()
{
return GetStandardDeviation(GetStatWindow());
}
}
}using QuantConnect.Orders.Slippage;
using System;
using QuantConnect.Orders;
using QuantConnect.Securities;
namespace QuantConnect.Algorithm.CSharp
{
class OrderTypeDependentSlippageModel : ISlippageModel
{
public ISlippageModel LimitOrderSlippage { get; set; }
public ISlippageModel MarketOrderSlippage { get; set; }
public ISlippageModel MarketOnCloseOrderSlippage { get; set; }
public ISlippageModel MarketOnOpenOrderSlippage { get; set; }
public ISlippageModel StopLimitOrderSlippage { get; set; }
public ISlippageModel StopMarketOrderSlippage { get; set; }
public OrderTypeDependentSlippageModel(ISlippageModel defaultModel)
{
LimitOrderSlippage = defaultModel;
MarketOrderSlippage = defaultModel;
MarketOnCloseOrderSlippage = defaultModel;
MarketOnOpenOrderSlippage = defaultModel;
StopLimitOrderSlippage = defaultModel;
StopMarketOrderSlippage = defaultModel;
}
public void SetMarketSlippageModel(ISlippageModel model)
{
MarketOrderSlippage = model;
MarketOnCloseOrderSlippage = model;
MarketOnOpenOrderSlippage = model;
StopMarketOrderSlippage = model;
}
public void SetLimitSlippageModel(ISlippageModel model)
{
LimitOrderSlippage = model;
StopLimitOrderSlippage = model;
}
public decimal GetSlippageApproximation(Security asset, Order order)
{
switch (order.Type)
{
case OrderType.Limit:
return LimitOrderSlippage.GetSlippageApproximation(asset, order);
case OrderType.Market:
return MarketOrderSlippage.GetSlippageApproximation(asset, order);
case OrderType.MarketOnClose:
return MarketOnCloseOrderSlippage.GetSlippageApproximation(asset, order);
case OrderType.MarketOnOpen:
return MarketOnOpenOrderSlippage.GetSlippageApproximation(asset, order);
case OrderType.StopLimit:
return StopLimitOrderSlippage.GetSlippageApproximation(asset, order);
case OrderType.StopMarket:
return StopMarketOrderSlippage.GetSlippageApproximation(asset, order);
default:
throw new NotImplementedException("Slippage specialization not implemented for order type " + order.Type.ToString());
}
}
}
}using QuantConnect.Securities;
using System;
namespace QuantConnect.Algorithm.CSharp
{
public sealed class VirtualEquity
{
public interface ISecurity
{
decimal GetPrice();
Security GetSecurityIfSupportedOtherwiseThrow();
}
private class SecurityAdapter : ISecurity
{
private readonly Security _sec;
public SecurityAdapter(Security sec)
{
_sec = sec;
}
public decimal GetPrice()
{
return _sec.Price;
}
public Security GetSecurityIfSupportedOtherwiseThrow()
{
return _sec;
}
}
public decimal TradeFeeFraction { get; set; }
private readonly ISecurity _security;
private decimal _entryFee;
private decimal _entryPrice;
private decimal _position;
private decimal _equityBase = 1;
public VirtualEquity(ISecurity sec)
{
_security = sec;
TradeFeeFraction = 0.005m;
}
public VirtualEquity(Security sec) : this(new SecurityAdapter(sec))
{
}
public decimal Slippage
{
get; set;
}
public decimal Position
{
get { return _position; }
set { SetPosition(value); }
}
public Security Security { get { return _security.GetSecurityIfSupportedOtherwiseThrow(); } }
public decimal GetEquity()
{
if (_position == 0)
return _equityBase;
return Math.Max(0, _equityBase * (1 + _position * (_security.GetPrice() / _entryPrice - 1) - Slippage - _entryFee - GetTradeFee()));
}
public decimal GetReturn()
{
return GetEquity() - 1;
}
private decimal GetTradeFee()
{
if (_security.GetPrice() == 0)
return TradeFeeFraction;
return Math.Min(TradeFeeFraction, TradeFeeFraction / _security.GetPrice());
}
public void SetPosition(decimal weight)
{
var old = _equityBase;
_equityBase = GetEquity();
_position = weight;
_entryPrice = _security.GetPrice();
_entryFee = GetTradeFee();
}
public void ResetEquity(bool keepPosition = true)
{
var oldPos = _position;
SetPosition(0);
_equityBase = 1;
if (oldPos != 0 && keepPosition)
{
_equityBase += Slippage;
SetPosition(oldPos);
}
}
}
}using System;
using System.Collections.Generic;
//found and copied from random site on Internetz
namespace QuantConnect.Algorithm.CSharp
{
public sealed class PriorityQueue<T> where T : IComparable<T>
{
private readonly List<T> _data = new List<T>();
public PriorityQueue()
{
_data = new List<T>();
}
public void Enqueue(T item)
{
_data.Add(item);
int ci = _data.Count - 1; // child index; start at end
while (ci > 0)
{
int pi = (ci - 1) / 2; // parent index
if (_data[ci].CompareTo(_data[pi]) >= 0) break; // child item is larger than (or equal) parent so we're done
T tmp = _data[ci]; _data[ci] = _data[pi]; _data[pi] = tmp;
ci = pi;
}
}
public T Dequeue()
{
// assumes pq is not empty; up to calling code
int li = _data.Count - 1; // last index (before removal)
T frontItem = _data[0]; // fetch the front
_data[0] = _data[li];
_data.RemoveAt(li);
--li; // last index (after removal)
int pi = 0; // parent index. start at front of pq
while (true)
{
int ci = pi * 2 + 1; // left child index of parent
if (ci > li) break; // no children so done
int rc = ci + 1; // right child
if (rc <= li && _data[rc].CompareTo(_data[ci]) < 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead
ci = rc;
if (_data[pi].CompareTo(_data[ci]) <= 0) break; // parent is smaller than (or equal to) smallest child so done
T tmp = _data[pi]; _data[pi] = _data[ci]; _data[ci] = tmp; // swap parent and child
pi = ci;
}
return frontItem;
}
public T Peek()
{
T frontItem = _data[0];
return frontItem;
}
public int Count
{
get { return _data.Count; }
}
public override string ToString()
{
string s = "";
for (int i = 0; i < _data.Count; ++i)
s += _data[i].ToString() + " ";
s += "count = " + _data.Count;
return s;
}
internal bool IsConsistent()
{
// is the heap property true for all data?
if (_data.Count == 0) return true;
int li = _data.Count - 1; // last index
for (int pi = 0; pi < _data.Count; ++pi) // each parent index
{
int lci = 2 * pi + 1; // left child index
int rci = 2 * pi + 2; // right child index
if (lci <= li && _data[pi].CompareTo(_data[lci]) > 0) return false; // if lc exists and it's greater than parent then bad.
if (rci <= li && _data[pi].CompareTo(_data[rci]) > 0) return false; // check the right child too.
}
return true; // passed all checks
}
}
}