aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/ClientStack
diff options
context:
space:
mode:
authorjjgreens2009-10-14 23:15:03 -0700
committerJohn Hurliman2009-10-15 15:52:53 -0700
commitdf2d5a460f060129e5c09148b9fa4df2f241d8b1 (patch)
treebdec08feae7b1494818830e30120df2bab437cef /OpenSim/Region/ClientStack
parent* Removed some of the redundant broadcast functions in Scene and SceneGraph s... (diff)
downloadopensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.zip
opensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.tar.gz
opensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.tar.bz2
opensim-SC_OLD-df2d5a460f060129e5c09148b9fa4df2f241d8b1.tar.xz
Replaced the update lists with a priority queue implementation in LLClientView
Replaced the update lists with a priority queue implementation in LLClientView. The priority queues are based on the MinHeap implementation also included in this commit within the OpneSim.Framework namespace. Initially setup to exactly mimic the behavior beofre the change which was a first come first serve queue.
Diffstat (limited to 'OpenSim/Region/ClientStack')
-rw-r--r--OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs224
1 files changed, 179 insertions, 45 deletions
diff --git a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
index 82a2cdd..93fdeef 100644
--- a/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
+++ b/OpenSim/Region/ClientStack/LindenUDP/LLClientView.cs
@@ -321,11 +321,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP
321 321
322 private int m_cachedTextureSerial; 322 private int m_cachedTextureSerial;
323 private Timer m_avatarTerseUpdateTimer; 323 private Timer m_avatarTerseUpdateTimer;
324 private List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_avatarTerseUpdates = new List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>(); 324 private PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_avatarTerseUpdates_ =
325 new PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
325 private Timer m_primTerseUpdateTimer; 326 private Timer m_primTerseUpdateTimer;
326 private List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_primTerseUpdates = new List<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>(); 327 private PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock> m_primTerseUpdates_ =
328 new PriorityQueue<double, ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
327 private Timer m_primFullUpdateTimer; 329 private Timer m_primFullUpdateTimer;
328 private List<ObjectUpdatePacket.ObjectDataBlock> m_primFullUpdates = new List<ObjectUpdatePacket.ObjectDataBlock>(); 330 private PriorityQueue<double, ObjectUpdatePacket.ObjectDataBlock> m_primFullUpdates_ =
331 new PriorityQueue<double, ObjectUpdatePacket.ObjectDataBlock>();
329 private int m_moneyBalance; 332 private int m_moneyBalance;
330 private int m_animationSequenceNumber = 1; 333 private int m_animationSequenceNumber = 1;
331 private bool m_SendLogoutPacketWhenClosing = true; 334 private bool m_SendLogoutPacketWhenClosing = true;
@@ -3435,16 +3438,16 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3435 ImprovedTerseObjectUpdatePacket.ObjectDataBlock terseBlock = 3438 ImprovedTerseObjectUpdatePacket.ObjectDataBlock terseBlock =
3436 CreateAvatarImprovedBlock(localID, position, velocity,rotation); 3439 CreateAvatarImprovedBlock(localID, position, velocity,rotation);
3437 3440
3438 lock (m_avatarTerseUpdates) 3441 lock (m_avatarTerseUpdates_.SyncRoot)
3439 { 3442 {
3440 m_avatarTerseUpdates.Add(terseBlock); 3443 m_avatarTerseUpdates_.Enqueue(DateTime.Now.ToOADate(), terseBlock, localID);
3441 3444
3442 // If packet is full or own movement packet, send it. 3445 // If packet is full or own movement packet, send it.
3443 if (m_avatarTerseUpdates.Count >= m_avatarTerseUpdatesPerPacket) 3446 if (m_avatarTerseUpdates_.Count >= m_avatarTerseUpdatesPerPacket)
3444 { 3447 {
3445 ProcessAvatarTerseUpdates(this, null); 3448 ProcessAvatarTerseUpdates(this, null);
3446 } 3449 }
3447 else if (m_avatarTerseUpdates.Count == 1) 3450 else if (m_avatarTerseUpdates_.Count == 1)
3448 { 3451 {
3449 lock (m_avatarTerseUpdateTimer) 3452 lock (m_avatarTerseUpdateTimer)
3450 m_avatarTerseUpdateTimer.Start(); 3453 m_avatarTerseUpdateTimer.Start();
@@ -3454,7 +3457,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3454 3457
3455 private void ProcessAvatarTerseUpdates(object sender, ElapsedEventArgs e) 3458 private void ProcessAvatarTerseUpdates(object sender, ElapsedEventArgs e)
3456 { 3459 {
3457 lock (m_avatarTerseUpdates) 3460 lock (m_avatarTerseUpdates_.SyncRoot)
3458 { 3461 {
3459 ImprovedTerseObjectUpdatePacket terse = (ImprovedTerseObjectUpdatePacket)PacketPool.Instance.GetPacket(PacketType.ImprovedTerseObjectUpdate); 3462 ImprovedTerseObjectUpdatePacket terse = (ImprovedTerseObjectUpdatePacket)PacketPool.Instance.GetPacket(PacketType.ImprovedTerseObjectUpdate);
3460 3463
@@ -3465,8 +3468,8 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3465 (ushort)(Scene.TimeDilation * ushort.MaxValue); 3468 (ushort)(Scene.TimeDilation * ushort.MaxValue);
3466 3469
3467 int max = m_avatarTerseUpdatesPerPacket; 3470 int max = m_avatarTerseUpdatesPerPacket;
3468 if (max > m_avatarTerseUpdates.Count) 3471 if (max > m_avatarTerseUpdates_.Count)
3469 max = m_avatarTerseUpdates.Count; 3472 max = m_avatarTerseUpdates_.Count;
3470 3473
3471 int count = 0; 3474 int count = 0;
3472 int size = 0; 3475 int size = 0;
@@ -3474,30 +3477,30 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3474 byte[] zerobuffer = new byte[1024]; 3477 byte[] zerobuffer = new byte[1024];
3475 byte[] blockbuffer = new byte[1024]; 3478 byte[] blockbuffer = new byte[1024];
3476 3479
3480 Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> updates = new Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
3481
3477 for (count = 0 ; count < max ; count++) 3482 for (count = 0 ; count < max ; count++)
3478 { 3483 {
3479 int length = 0; 3484 int length = 0;
3480 m_avatarTerseUpdates[count].ToBytes(blockbuffer, ref length); 3485 m_avatarTerseUpdates_.Peek().ToBytes(blockbuffer, ref length);
3481 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer); 3486 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer);
3482 if (size + length > Packet.MTU) 3487 if (size + length > Packet.MTU)
3483 break; 3488 break;
3484 size += length; 3489 size += length;
3490 updates.Enqueue(m_avatarTerseUpdates_.Dequeue());
3485 } 3491 }
3486 3492
3487 terse.ObjectData = new ImprovedTerseObjectUpdatePacket.ObjectDataBlock[count]; 3493 terse.ObjectData = new ImprovedTerseObjectUpdatePacket.ObjectDataBlock[count];
3488 3494
3489 for (int i = 0 ; i < count ; i++) 3495 for (int i = 0 ; i < count ; i++)
3490 { 3496 terse.ObjectData[i] = updates.Dequeue();
3491 terse.ObjectData[i] = m_avatarTerseUpdates[0];
3492 m_avatarTerseUpdates.RemoveAt(0);
3493 }
3494 3497
3495 terse.Header.Reliable = false; 3498 terse.Header.Reliable = false;
3496 terse.Header.Zerocoded = true; 3499 terse.Header.Zerocoded = true;
3497 // FIXME: Move this to ThrottleOutPacketType.State when the real prioritization code is committed 3500 // FIXME: Move this to ThrottleOutPacketType.State when the real prioritization code is committed
3498 OutPacket(terse, ThrottleOutPacketType.Task); 3501 OutPacket(terse, ThrottleOutPacketType.Task);
3499 3502
3500 if (m_avatarTerseUpdates.Count == 0) 3503 if (m_avatarTerseUpdates_.Count == 0)
3501 { 3504 {
3502 lock (m_avatarTerseUpdateTimer) 3505 lock (m_avatarTerseUpdateTimer)
3503 m_avatarTerseUpdateTimer.Stop(); 3506 m_avatarTerseUpdateTimer.Stop();
@@ -3660,14 +3663,14 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3660 objectData.TextureAnim = textureanim; 3663 objectData.TextureAnim = textureanim;
3661 } 3664 }
3662 3665
3663 lock (m_primFullUpdates) 3666 lock (m_primFullUpdates_.SyncRoot)
3664 { 3667 {
3665 if (m_primFullUpdates.Count == 0) 3668 if (m_primFullUpdates_.Count == 0)
3666 m_primFullUpdateTimer.Start(); 3669 m_primFullUpdateTimer.Start();
3667 3670
3668 m_primFullUpdates.Add(objectData); 3671 m_primFullUpdates_.Enqueue(DateTime.Now.ToOADate(), objectData, localID);
3669 3672
3670 if (m_primFullUpdates.Count >= m_primFullUpdatesPerPacket) 3673 if (m_primFullUpdates_.Count >= m_primFullUpdatesPerPacket)
3671 ProcessPrimFullUpdates(this, null); 3674 ProcessPrimFullUpdates(this, null);
3672 } 3675 }
3673 } 3676 }
@@ -3690,9 +3693,9 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3690 3693
3691 void ProcessPrimFullUpdates(object sender, ElapsedEventArgs e) 3694 void ProcessPrimFullUpdates(object sender, ElapsedEventArgs e)
3692 { 3695 {
3693 lock (m_primFullUpdates) 3696 lock (m_primFullUpdates_.SyncRoot)
3694 { 3697 {
3695 if (m_primFullUpdates.Count == 0 && m_primFullUpdateTimer.Enabled) 3698 if (m_primFullUpdates_.Count == 0 && m_primFullUpdateTimer.Enabled)
3696 { 3699 {
3697 lock (m_primFullUpdateTimer) 3700 lock (m_primFullUpdateTimer)
3698 m_primFullUpdateTimer.Stop(); 3701 m_primFullUpdateTimer.Stop();
@@ -3709,7 +3712,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3709 outPacket.RegionData.TimeDilation = 3712 outPacket.RegionData.TimeDilation =
3710 (ushort)(Scene.TimeDilation * ushort.MaxValue); 3713 (ushort)(Scene.TimeDilation * ushort.MaxValue);
3711 3714
3712 int max = m_primFullUpdates.Count; 3715 int max = m_primFullUpdates_.Count;
3713 if (max > m_primFullUpdatesPerPacket) 3716 if (max > m_primFullUpdatesPerPacket)
3714 max = m_primFullUpdatesPerPacket; 3717 max = m_primFullUpdatesPerPacket;
3715 3718
@@ -3719,29 +3722,29 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3719 byte[] zerobuffer = new byte[1024]; 3722 byte[] zerobuffer = new byte[1024];
3720 byte[] blockbuffer = new byte[1024]; 3723 byte[] blockbuffer = new byte[1024];
3721 3724
3725 Queue<ObjectUpdatePacket.ObjectDataBlock> updates = new Queue<ObjectUpdatePacket.ObjectDataBlock>();
3726
3722 for (count = 0 ; count < max ; count++) 3727 for (count = 0 ; count < max ; count++)
3723 { 3728 {
3724 int length = 0; 3729 int length = 0;
3725 m_primFullUpdates[count].ToBytes(blockbuffer, ref length); 3730 m_primFullUpdates_.Peek().ToBytes(blockbuffer, ref length);
3726 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer); 3731 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer);
3727 if (size + length > Packet.MTU) 3732 if (size + length > Packet.MTU)
3728 break; 3733 break;
3729 size += length; 3734 size += length;
3735 updates.Enqueue(m_primFullUpdates_.Dequeue());
3730 } 3736 }
3731 3737
3732 outPacket.ObjectData = 3738 outPacket.ObjectData =
3733 new ObjectUpdatePacket.ObjectDataBlock[count]; 3739 new ObjectUpdatePacket.ObjectDataBlock[count];
3734 3740
3735 for (int index = 0 ; index < count ; index++) 3741 for (int index = 0 ; index < count ; index++)
3736 { 3742 outPacket.ObjectData[index] = updates.Dequeue();
3737 outPacket.ObjectData[index] = m_primFullUpdates[0];
3738 m_primFullUpdates.RemoveAt(0);
3739 }
3740 3743
3741 outPacket.Header.Zerocoded = true; 3744 outPacket.Header.Zerocoded = true;
3742 OutPacket(outPacket, ThrottleOutPacketType.State); 3745 OutPacket(outPacket, ThrottleOutPacketType.State);
3743 3746
3744 if (m_primFullUpdates.Count == 0 && m_primFullUpdateTimer.Enabled) 3747 if (m_primFullUpdates_.Count == 0 && m_primFullUpdateTimer.Enabled)
3745 lock (m_primFullUpdateTimer) 3748 lock (m_primFullUpdateTimer)
3746 m_primFullUpdateTimer.Stop(); 3749 m_primFullUpdateTimer.Stop();
3747 } 3750 }
@@ -3763,23 +3766,23 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3763 CreatePrimImprovedBlock(localID, position, rotation, 3766 CreatePrimImprovedBlock(localID, position, rotation,
3764 velocity, rotationalvelocity, state); 3767 velocity, rotationalvelocity, state);
3765 3768
3766 lock (m_primTerseUpdates) 3769 lock (m_primTerseUpdates_.SyncRoot)
3767 { 3770 {
3768 if (m_primTerseUpdates.Count == 0) 3771 if (m_primTerseUpdates_.Count == 0)
3769 m_primTerseUpdateTimer.Start(); 3772 m_primTerseUpdateTimer.Start();
3770 3773
3771 m_primTerseUpdates.Add(objectData); 3774 m_primTerseUpdates_.Enqueue(DateTime.Now.ToOADate(), objectData, localID);
3772 3775
3773 if (m_primTerseUpdates.Count >= m_primTerseUpdatesPerPacket) 3776 if (m_primTerseUpdates_.Count >= m_primTerseUpdatesPerPacket)
3774 ProcessPrimTerseUpdates(this, null); 3777 ProcessPrimTerseUpdates(this, null);
3775 } 3778 }
3776 } 3779 }
3777 3780
3778 void ProcessPrimTerseUpdates(object sender, ElapsedEventArgs e) 3781 void ProcessPrimTerseUpdates(object sender, ElapsedEventArgs e)
3779 { 3782 {
3780 lock (m_primTerseUpdates) 3783 lock (m_primTerseUpdates_.SyncRoot)
3781 { 3784 {
3782 if (m_primTerseUpdates.Count == 0) 3785 if (m_primTerseUpdates_.Count == 0)
3783 { 3786 {
3784 lock (m_primTerseUpdateTimer) 3787 lock (m_primTerseUpdateTimer)
3785 m_primTerseUpdateTimer.Stop(); 3788 m_primTerseUpdateTimer.Stop();
@@ -3797,7 +3800,7 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3797 outPacket.RegionData.TimeDilation = 3800 outPacket.RegionData.TimeDilation =
3798 (ushort)(Scene.TimeDilation * ushort.MaxValue); 3801 (ushort)(Scene.TimeDilation * ushort.MaxValue);
3799 3802
3800 int max = m_primTerseUpdates.Count; 3803 int max = m_primTerseUpdates_.Count;
3801 if (max > m_primTerseUpdatesPerPacket) 3804 if (max > m_primTerseUpdatesPerPacket)
3802 max = m_primTerseUpdatesPerPacket; 3805 max = m_primTerseUpdatesPerPacket;
3803 3806
@@ -3807,14 +3810,17 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3807 byte[] zerobuffer = new byte[1024]; 3810 byte[] zerobuffer = new byte[1024];
3808 byte[] blockbuffer = new byte[1024]; 3811 byte[] blockbuffer = new byte[1024];
3809 3812
3813 Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock> updates = new Queue<ImprovedTerseObjectUpdatePacket.ObjectDataBlock>();
3814
3810 for (count = 0 ; count < max ; count++) 3815 for (count = 0 ; count < max ; count++)
3811 { 3816 {
3812 int length = 0; 3817 int length = 0;
3813 m_primTerseUpdates[count].ToBytes(blockbuffer, ref length); 3818 m_primTerseUpdates_.Peek().ToBytes(blockbuffer, ref length);
3814 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer); 3819 length = Helpers.ZeroEncode(blockbuffer, length, zerobuffer);
3815 if (size + length > Packet.MTU) 3820 if (size + length > Packet.MTU)
3816 break; 3821 break;
3817 size += length; 3822 size += length;
3823 updates.Enqueue(m_primTerseUpdates_.Dequeue());
3818 } 3824 }
3819 3825
3820 outPacket.ObjectData = 3826 outPacket.ObjectData =
@@ -3822,16 +3828,13 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3822 ObjectDataBlock[count]; 3828 ObjectDataBlock[count];
3823 3829
3824 for (int index = 0 ; index < count ; index++) 3830 for (int index = 0 ; index < count ; index++)
3825 { 3831 outPacket.ObjectData[index] = updates.Dequeue();
3826 outPacket.ObjectData[index] = m_primTerseUpdates[0];
3827 m_primTerseUpdates.RemoveAt(0);
3828 }
3829 3832
3830 outPacket.Header.Reliable = false; 3833 outPacket.Header.Reliable = false;
3831 outPacket.Header.Zerocoded = true; 3834 outPacket.Header.Zerocoded = true;
3832 OutPacket(outPacket, ThrottleOutPacketType.State); 3835 OutPacket(outPacket, ThrottleOutPacketType.State);
3833 3836
3834 if (m_primTerseUpdates.Count == 0) 3837 if (m_primTerseUpdates_.Count == 0)
3835 lock (m_primTerseUpdateTimer) 3838 lock (m_primTerseUpdateTimer)
3836 m_primTerseUpdateTimer.Stop(); 3839 m_primTerseUpdateTimer.Stop();
3837 } 3840 }
@@ -3839,15 +3842,15 @@ namespace OpenSim.Region.ClientStack.LindenUDP
3839 3842
3840 public void FlushPrimUpdates() 3843 public void FlushPrimUpdates()
3841 { 3844 {
3842 while (m_primFullUpdates.Count > 0) 3845 while (m_primFullUpdates_.Count > 0)
3843 { 3846 {
3844 ProcessPrimFullUpdates(this, null); 3847 ProcessPrimFullUpdates(this, null);
3845 } 3848 }
3846 while (m_primTerseUpdates.Count > 0) 3849 while (m_primTerseUpdates_.Count > 0)
3847 { 3850 {
3848 ProcessPrimTerseUpdates(this, null); 3851 ProcessPrimTerseUpdates(this, null);
3849 } 3852 }
3850 while (m_avatarTerseUpdates.Count > 0) 3853 while (m_avatarTerseUpdates_.Count > 0)
3851 { 3854 {
3852 ProcessAvatarTerseUpdates(this, null); 3855 ProcessAvatarTerseUpdates(this, null);
3853 } 3856 }
@@ -10578,5 +10581,136 @@ namespace OpenSim.Region.ClientStack.LindenUDP
10578 pack.TextureData.TextureID = textureID; 10581 pack.TextureData.TextureID = textureID;
10579 OutPacket(pack, ThrottleOutPacketType.Task); 10582 OutPacket(pack, ThrottleOutPacketType.Task);
10580 } 10583 }
10584
10585 #region PriorityQueue
10586 private class PriorityQueue<TPriority, TValue>
10587 {
10588 private MinHeap<MinHeapItem>[] heaps = new MinHeap<MinHeapItem>[1];
10589 private Dictionary<uint, LookupItem> lookup_table = new Dictionary<uint, LookupItem>();
10590 private Comparison<TPriority> comparison;
10591 private object sync_root = new object();
10592
10593 internal PriorityQueue() :
10594 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, Comparer<TPriority>.Default) { }
10595 internal PriorityQueue(int capacity) :
10596 this(capacity, Comparer<TPriority>.Default) { }
10597 internal PriorityQueue(IComparer<TPriority> comparer) :
10598 this(new Comparison<TPriority>(comparer.Compare)) { }
10599 internal PriorityQueue(Comparison<TPriority> comparison) :
10600 this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY, comparison) { }
10601 internal PriorityQueue(int capacity, IComparer<TPriority> comparer) :
10602 this(capacity, new Comparison<TPriority>(comparer.Compare)) { }
10603 internal PriorityQueue(int capacity, Comparison<TPriority> comparison)
10604 {
10605 for (int i = 0; i < heaps.Length; ++i)
10606 heaps[i] = new MinHeap<MinHeapItem>(capacity);
10607 this.comparison = comparison;
10608 }
10609
10610 internal object SyncRoot { get { return this.sync_root; } }
10611 internal int Count
10612 {
10613 get
10614 {
10615 int count = 0;
10616 for (int i = 0; i < heaps.Length; ++i)
10617 count = heaps[i].Count;
10618 return count;
10619 }
10620 }
10621
10622 internal bool Enqueue(TPriority priority, TValue value, uint local_id)
10623 {
10624 LookupItem item;
10625
10626 if (lookup_table.TryGetValue(local_id, out item))
10627 {
10628 item.Heap[item.Handle] = new MinHeapItem(priority, value, local_id, this.comparison);
10629 return false;
10630 }
10631 else
10632 {
10633 item.Heap = heaps[0];
10634 item.Heap.Add(new MinHeapItem(priority, value, local_id, this.comparison), ref item.Handle);
10635 lookup_table.Add(local_id, item);
10636 return true;
10637 }
10638 }
10639
10640 internal TValue Peek()
10641 {
10642 for (int i = 0; i < heaps.Length; ++i)
10643 if (heaps[i].Count > 0)
10644 return heaps[i].Min().Value;
10645 throw new InvalidOperationException(string.Format("The {0} is empty", this.GetType().ToString()));
10646 }
10647
10648 internal TValue Dequeue()
10649 {
10650 for (int i = 0; i < heaps.Length; ++i)
10651 {
10652 if (heaps[i].Count > 0)
10653 {
10654 MinHeapItem item = heaps[i].RemoveMin();
10655 lookup_table.Remove(item.LocalID);
10656 return item.Value;
10657 }
10658 }
10659 throw new InvalidOperationException(string.Format("The {0} is empty", this.GetType().ToString()));
10660 }
10661
10662 #region MinHeapItem
10663 private struct MinHeapItem : IComparable<MinHeapItem>
10664 {
10665 private TPriority priority;
10666 private TValue value;
10667 private uint local_id;
10668 private Comparison<TPriority> comparison;
10669
10670 internal MinHeapItem(TPriority priority, TValue value, uint local_id) :
10671 this(priority, value, local_id, Comparer<TPriority>.Default) { }
10672 internal MinHeapItem(TPriority priority, TValue value, uint local_id, IComparer<TPriority> comparer) :
10673 this(priority, value, local_id, new Comparison<TPriority>(comparer.Compare)) { }
10674 internal MinHeapItem(TPriority priority, TValue value, uint local_id, Comparison<TPriority> comparison)
10675 {
10676 this.priority = priority;
10677 this.value = value;
10678 this.local_id = local_id;
10679 this.comparison = comparison;
10680 }
10681
10682 internal TPriority Priority { get { return this.priority; } }
10683 internal TValue Value { get { return this.value; } }
10684 internal uint LocalID { get { return this.local_id; } }
10685
10686 public override string ToString()
10687 {
10688 StringBuilder sb = new StringBuilder();
10689 sb.Append("[");
10690 if (this.priority != null)
10691 sb.Append(this.priority.ToString());
10692 sb.Append(",");
10693 if (this.value != null)
10694 sb.Append(this.value.ToString());
10695 sb.Append("]");
10696 return sb.ToString();
10697 }
10698
10699 public int CompareTo(MinHeapItem other)
10700 {
10701 return this.comparison(this.priority, other.priority);
10702 }
10703 }
10704 #endregion
10705
10706 #region LookupItem
10707 private struct LookupItem {
10708 internal MinHeap<MinHeapItem> Heap;
10709 internal IHandle Handle;
10710 }
10711 #endregion
10712 }
10713 #endregion
10714
10581 } 10715 }
10582} 10716}