mirror of
https://github.com/BepInEx/mono.git
synced 2026-11-16 17:10:20 -10:00
* AssemblyInfo.cs: added back InternalsVisibleTo for the test
assembly - it's needed to access CacheItemPriorityQueue
2010-02-03 Marek Habersack <[email protected]>
* OutputCache.cs: DefaultProviderName checks if there was any
provider configured and, if not, returns a built-in provider's
name.
* SqlCacheDependencyAdmin.cs: added
* OutputCacheProviderCollection.cs: added
* OutputCacheProvider.cs: added
* OutputCacheModule.cs: uses the 4.0 extensible output cache
provider model now (also internally in the 2.0 profile)
OutputCacheProvider is retrieved on every request using
HttpApplication.GetOutputCacheProviderName (4.0+). In the 2.0
profile an instance of InMemoryOutputCacheProvider is always
returned.
* InMemoryOutputCacheProvider.cs: default output cache provider
for ASP.NET 4.0, also used internally in the 2.0 profile.
* CachedVaryBy.cs: made the generated key shorter
* CacheItemPriorityQueueDebug.cs: debugging support for
CacheItemPriorityQueue. Most of the code is compiled only when the
DEBUG macro is defined. Debugging support includes recording of
the queue operations sequence which is output to an XML file on
appdomain shutdown. The recorded sequence files can be used to
generate NUnit test cases for the priority queue (see
../Test/tools/README)
* CacheItemPriorityQueue.cs: rewritten using an array based heap
instead of a binary tree based one - implementation is simpler,
faster and more elegant. Heap is initially 32 entries long and
its size is doubled every time it fills up. After reaching a
threshold (8192 entries currently) it is shrunk to the number of
items + 1/3 of item count in order to preserve memory.
* CacheItem.cs: added a Guid field to easier distinguish items
(mostly for debugging purposes)
* CacheDependency.cs: minor performance improvements
* Cache.cs: better handling of timer periods
2010-02-03 Marek Habersack <[email protected]>
* HttpApplication.cs: GetOutputCacheProviderName returns the value
of OutputCache.DefaultProviderName
* HttpRuntime.cs: internal cache is used to hold the dependencies
now.
2010-02-03 Marek Habersack <[email protected]>
* CacheItemPriorityQueueTest_generated.cs: added
* CacheItemPriorityQueueTest.cs: added
2010-02-04 Marek Habersack <[email protected]>
* Helpers.cs: added a helper method for checking of HTML mentions
any .NET exceptions.
2010-02-03 Marek Habersack <[email protected]>
* Makefile: added targets to compile cache priority queue tests
generator and to generate the tests themselves
svn path=/trunk/mcs/; revision=150855
276 lines
5.1 KiB
C#
276 lines
5.1 KiB
C#
using System;
|
|
using System.Collections;
|
|
|
|
namespace BenTools.Data
|
|
{
|
|
public interface IPriorityQueue : ICollection, ICloneable, IList
|
|
{
|
|
int Push(object O);
|
|
object Pop();
|
|
object Peek();
|
|
void Update(int i);
|
|
}
|
|
public class BinaryPriorityQueue : IPriorityQueue, ICollection, ICloneable, IList
|
|
{
|
|
protected ArrayList InnerList = new ArrayList();
|
|
protected IComparer Comparer;
|
|
|
|
#region contructors
|
|
public BinaryPriorityQueue() : this(System.Collections.Comparer.Default)
|
|
{}
|
|
public BinaryPriorityQueue(IComparer c)
|
|
{
|
|
Comparer = c;
|
|
}
|
|
public BinaryPriorityQueue(int C) : this(System.Collections.Comparer.Default,C)
|
|
{}
|
|
public BinaryPriorityQueue(IComparer c, int Capacity)
|
|
{
|
|
Comparer = c;
|
|
InnerList.Capacity = Capacity;
|
|
}
|
|
|
|
protected BinaryPriorityQueue(ArrayList Core, IComparer Comp, bool Copy)
|
|
{
|
|
if(Copy)
|
|
InnerList = Core.Clone() as ArrayList;
|
|
else
|
|
InnerList = Core;
|
|
Comparer = Comp;
|
|
}
|
|
|
|
#endregion
|
|
protected void SwitchElements(int i, int j)
|
|
{
|
|
object h = InnerList[i];
|
|
InnerList[i] = InnerList[j];
|
|
InnerList[j] = h;
|
|
}
|
|
|
|
protected virtual int OnCompare(int i, int j)
|
|
{
|
|
return Comparer.Compare(InnerList[i],InnerList[j]);
|
|
}
|
|
|
|
#region public methods
|
|
/// <summary>
|
|
/// Push an object onto the PQ
|
|
/// </summary>
|
|
/// <param name="O">The new object</param>
|
|
/// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.</returns>
|
|
public int Push(object O)
|
|
{
|
|
int p = InnerList.Count,p2;
|
|
InnerList.Add(O); // E[p] = O
|
|
do
|
|
{
|
|
if(p==0)
|
|
break;
|
|
p2 = (p-1)/2;
|
|
if(OnCompare(p,p2)<0)
|
|
{
|
|
SwitchElements(p,p2);
|
|
p = p2;
|
|
}
|
|
else
|
|
break;
|
|
}while(true);
|
|
return p;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Get the smallest object and remove it.
|
|
/// </summary>
|
|
/// <returns>The smallest object</returns>
|
|
public object Pop()
|
|
{
|
|
object result = InnerList[0];
|
|
int p = 0,p1,p2,pn;
|
|
InnerList[0] = InnerList[InnerList.Count-1];
|
|
InnerList.RemoveAt(InnerList.Count-1);
|
|
do
|
|
{
|
|
pn = p;
|
|
p1 = 2*p+1;
|
|
p2 = 2*p+2;
|
|
if(InnerList.Count>p1 && OnCompare(p,p1)>0) // links kleiner
|
|
p = p1;
|
|
if(InnerList.Count>p2 && OnCompare(p,p2)>0) // rechts noch kleiner
|
|
p = p2;
|
|
|
|
if(p==pn)
|
|
break;
|
|
SwitchElements(p,pn);
|
|
}while(true);
|
|
return result;
|
|
}
|
|
|
|
/// <summary>
|
|
/// Notify the PQ that the object at position i has changed
|
|
/// and the PQ needs to restore order.
|
|
/// Since you dont have access to any indexes (except by using the
|
|
/// explicit IList.this) you should not call this function without knowing exactly
|
|
/// what you do.
|
|
/// </summary>
|
|
/// <param name="i">The index of the changed object.</param>
|
|
public void Update(int i)
|
|
{
|
|
int p = i,pn;
|
|
int p1,p2;
|
|
do // aufsteigen
|
|
{
|
|
if(p==0)
|
|
break;
|
|
p2 = (p-1)/2;
|
|
if(OnCompare(p,p2)<0)
|
|
{
|
|
SwitchElements(p,p2);
|
|
p = p2;
|
|
}
|
|
else
|
|
break;
|
|
}while(true);
|
|
if(p<i)
|
|
return;
|
|
do // absteigen
|
|
{
|
|
pn = p;
|
|
p1 = 2*p+1;
|
|
p2 = 2*p+2;
|
|
if(InnerList.Count>p1 && OnCompare(p,p1)>0) // links kleiner
|
|
p = p1;
|
|
if(InnerList.Count>p2 && OnCompare(p,p2)>0) // rechts noch kleiner
|
|
p = p2;
|
|
|
|
if(p==pn)
|
|
break;
|
|
SwitchElements(p,pn);
|
|
}while(true);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Get the smallest object without removing it.
|
|
/// </summary>
|
|
/// <returns>The smallest object</returns>
|
|
public object Peek()
|
|
{
|
|
if(InnerList.Count>0)
|
|
return InnerList[0];
|
|
return null;
|
|
}
|
|
|
|
public bool Contains(object value)
|
|
{
|
|
return InnerList.Contains(value);
|
|
}
|
|
|
|
public void Clear()
|
|
{
|
|
InnerList.Clear();
|
|
}
|
|
|
|
public int Count
|
|
{
|
|
get
|
|
{
|
|
return InnerList.Count;
|
|
}
|
|
}
|
|
IEnumerator IEnumerable.GetEnumerator()
|
|
{
|
|
return InnerList.GetEnumerator();
|
|
}
|
|
|
|
public void CopyTo(Array array, int index)
|
|
{
|
|
InnerList.CopyTo(array,index);
|
|
}
|
|
|
|
public object Clone()
|
|
{
|
|
return new BinaryPriorityQueue(InnerList,Comparer,true);
|
|
}
|
|
|
|
public bool IsSynchronized
|
|
{
|
|
get
|
|
{
|
|
return InnerList.IsSynchronized;
|
|
}
|
|
}
|
|
|
|
public object SyncRoot
|
|
{
|
|
get
|
|
{
|
|
return this;
|
|
}
|
|
}
|
|
#endregion
|
|
#region explicit implementation
|
|
bool IList.IsReadOnly
|
|
{
|
|
get
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
|
|
object IList.this[int index]
|
|
{
|
|
get
|
|
{
|
|
return InnerList[index];
|
|
}
|
|
set
|
|
{
|
|
InnerList[index] = value;
|
|
Update(index);
|
|
}
|
|
}
|
|
|
|
int IList.Add(object o)
|
|
{
|
|
return Push(o);
|
|
}
|
|
|
|
void IList.RemoveAt(int index)
|
|
{
|
|
throw new NotSupportedException();
|
|
}
|
|
|
|
void IList.Insert(int index, object value)
|
|
{
|
|
throw new NotSupportedException();
|
|
}
|
|
|
|
void IList.Remove(object value)
|
|
{
|
|
throw new NotSupportedException();
|
|
}
|
|
|
|
int IList.IndexOf(object value)
|
|
{
|
|
throw new NotSupportedException();
|
|
}
|
|
|
|
bool IList.IsFixedSize
|
|
{
|
|
get
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
|
|
public static BinaryPriorityQueue Syncronized(BinaryPriorityQueue P)
|
|
{
|
|
return new BinaryPriorityQueue(ArrayList.Synchronized(P.InnerList),P.Comparer,false);
|
|
}
|
|
public static BinaryPriorityQueue ReadOnly(BinaryPriorityQueue P)
|
|
{
|
|
return new BinaryPriorityQueue(ArrayList.ReadOnly(P.InnerList),P.Comparer,false);
|
|
}
|
|
#endregion
|
|
}
|
|
}
|