| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you 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 System; |
| using System.Collections; |
| using System.Collections.Generic; |
| |
| namespace Org.Apache.REEF.Utilities.Collections |
| { |
| /// <summary> |
| /// A simple priority queue implementation, where the head of the queue is the |
| /// smallest element in the priority queue. |
| /// </summary> |
| public sealed class PriorityQueue<T> : ICollection<T> where T : IComparable<T> |
| { |
| private readonly List<T> _list; |
| |
| public PriorityQueue() |
| { |
| _list = new List<T>(); |
| } |
| |
| /// <summary> |
| /// Gets the enumerator of the priority queue. The Enumerator returns elements |
| /// in no guaranteed order. |
| /// </summary> |
| public IEnumerator<T> GetEnumerator() |
| { |
| return _list.GetEnumerator(); |
| } |
| |
| /// <summary> |
| /// Gets the enumerator of the priority queue. The Enumerator returns elements |
| /// in no guaranteed order. |
| /// </summary> |
| IEnumerator IEnumerable.GetEnumerator() |
| { |
| return _list.GetEnumerator(); |
| } |
| |
| /// <summary> |
| /// Peeks at the head of the priority queue, but does not remove the element |
| /// at the head. |
| /// </summary> |
| /// <exception cref="InvalidOperationException">Thrown when the priority queue is empty</exception> |
| public T Peek() |
| { |
| if (_list.Count == 0) |
| { |
| throw new InvalidOperationException("The PriorityQueue is empty."); |
| } |
| |
| return _list[0]; |
| } |
| |
| /// <summary> |
| /// Adds an element to the priority queue. |
| /// </summary> |
| public void Enqueue(T item) |
| { |
| Add(item); |
| } |
| |
| /// <summary> |
| /// Dequeues an item from the priority queue. Removes the head of the priority queue, which |
| /// is the smallest element in the priority queue. |
| /// </summary> |
| /// <exception cref="InvalidOperationException">Thrown when the priority queue is empty</exception> |
| public T Dequeue() |
| { |
| if (_list.Count == 0) |
| { |
| throw new InvalidOperationException("Cannot remove from an empty PriorityQueue."); |
| } |
| |
| // Removes element and places last to top |
| var ret = _list[0]; |
| _list[0] = _list[_list.Count - 1]; |
| _list.RemoveAt(_list.Count - 1); |
| |
| if (_list.Count == 0) |
| { |
| return ret; |
| } |
| |
| // Percolate down. |
| var idx = 0; |
| var item = _list[0]; |
| var lchildIdx = GetLeftChildIndex(idx); |
| |
| while (lchildIdx < _list.Count) |
| { |
| // Find the smaller child to compare |
| int smallerIdx; |
| var rchildIdx = lchildIdx + 1; |
| |
| if (rchildIdx < _list.Count) |
| { |
| smallerIdx = _list[lchildIdx].CompareTo(_list[rchildIdx]) <= 0 ? lchildIdx : rchildIdx; |
| } |
| else |
| { |
| smallerIdx = lchildIdx; |
| } |
| |
| // Compare with the smaller child, swap down if greater |
| if (item.CompareTo(_list[smallerIdx]) > 0) |
| { |
| _list[idx] = _list[smallerIdx]; |
| _list[smallerIdx] = item; |
| idx = smallerIdx; |
| lchildIdx = GetLeftChildIndex(idx); |
| } |
| else |
| { |
| // Order holds |
| break; |
| } |
| } |
| |
| return ret; |
| } |
| |
| /// <summary> |
| /// <see cref="Enqueue"/>. |
| /// </summary> |
| public void Add(T item) |
| { |
| // Add item |
| _list.Add(item); |
| var idx = _list.Count - 1; |
| |
| // Percolate up |
| while (idx > 0) |
| { |
| var parentIdx = (idx - 1) / 2; |
| |
| // Swap up if parent is greater |
| if (_list[parentIdx].CompareTo(item) > 0) |
| { |
| _list[idx] = _list[parentIdx]; |
| _list[parentIdx] = item; |
| idx = parentIdx; |
| } |
| else |
| { |
| // Order holds |
| break; |
| } |
| } |
| } |
| |
| /// <summary> |
| /// Clears the priority queue. |
| /// </summary> |
| public void Clear() |
| { |
| _list.Clear(); |
| } |
| |
| /// <summary> |
| /// Checks if the list contains an item. |
| /// </summary> |
| public bool Contains(T item) |
| { |
| return _list.Contains(item); |
| } |
| |
| /// <summary> |
| /// Copies the priority queue to a compatible array, starting at the array's |
| /// provided index. |
| /// </summary> |
| public void CopyTo(T[] array, int arrayIndex) |
| { |
| _list.CopyTo(array, arrayIndex); |
| } |
| |
| /// <summary> |
| /// Remove is not supported. |
| /// </summary> |
| /// <exception cref="NotSupportedException">Operation not supported</exception> |
| public bool Remove(T item) |
| { |
| throw new NotSupportedException(); |
| } |
| |
| /// <summary> |
| /// Returns the count of the priority queue. |
| /// </summary> |
| public int Count |
| { |
| get |
| { |
| return _list.Count; |
| } |
| } |
| |
| /// <summary> |
| /// Always returns false. |
| /// </summary> |
| public bool IsReadOnly |
| { |
| get { return false; } |
| } |
| |
| private static int GetLeftChildIndex(int idx) |
| { |
| return (2 * idx) + 1; |
| } |
| } |
| } |