Files
Marek Habersack 73c3bfba56 2010-02-03 Marek Habersack <[email protected]>
* 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
2010-02-04 13:53:55 +00:00

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
}
}