--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/bin/ai/library/sets/binary_heap/library.nut Tue Jun 10 18:28:39 2008 +0000
@@ -0,0 +1,12 @@
+/* $Id$ */
+
+class BinaryHeap extends AILibrary {
+ function GetAuthor() { return "OpenTTD NoAI Developers Team"; }
+ function GetName() { return "Binary Heap"; }
+ function GetDescription() { return "An implementation of a Binary Heap"; }
+ function GetVersion() { return 1; }
+ function GetDate() { return "2008-06-10"; }
+ function CreateInstance() { return "BinaryHeap"; }
+}
+
+RegisterLibrary(BinaryHeap());
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/bin/ai/library/sets/binary_heap/main.nut Tue Jun 10 18:28:39 2008 +0000
@@ -0,0 +1,130 @@
+/* $Id$ */
+
+/**
+ * Binary Heap.
+ * Peek and Remove always return the current lowest value in the list.
+ * Sort is done on insertion and on deletion.
+ */
+class BinaryHeap
+{
+ _queue = null;
+ _count = 0;
+
+ constructor() {
+ this._queue = [];
+ }
+
+ /**
+ * Insert a new entry in the list.
+ * The complexity of this operation is O(ln n).
+ * @param item The item to add to the list.
+ * @param priority The priority this item has.
+ */
+ function Insert(item, priority);
+
+ /**
+ * Pop the first entry of the list.
+ * This is always the item with the lowest priority.
+ * The complexity of this operation is O(ln n).
+ * @return The item of the entry with the lowest priority.
+ */
+ function Pop();
+
+ /**
+ * Peek the first entry of the list.
+ * This is always the item with the lowest priority.
+ * The complexity of this operation is O(1).
+ * @return The item of the entry with the lowest priority.
+ */
+ function Peek();
+
+ /**
+ * Get the amount of current items in the list.
+ * The complexity of this operation is O(1).
+ * @return The amount of items currently in the list.
+ */
+ function Count();
+
+ /**
+ * Check if an item exists in the list.
+ * The complexity of this operation is O(n).
+ * @param item The item to check for.
+ * @return True if the item is already in the list.
+ */
+ function Exists(item);
+}
+
+function BinaryHeap::Insert(item, priority)
+{
+ /* Append dummy entry */
+ this._queue.append(0);
+ this._count++;
+
+ local hole;
+ /* Find the point of insertion */
+ for (hole = this._count - 1; hole > 0 && priority < this._queue[hole / 2][1]; hole /= 2)
+ this._queue[hole] = this._queue[hole / 2];
+ /* Insert new pair */
+ this._queue[hole] = [item, priority];
+
+ return true;
+}
+
+function BinaryHeap::Pop()
+{
+ if (this._count == 0) return null;
+
+ local node = this._queue[0];
+ /* Remove the item from the list by putting the last value on top */
+ this._queue[0] = this._queue[this._count - 1];
+ this._queue.pop();
+ this._count--;
+ /* Bubble down the last value to correct the tree again */
+ this._BubbleDown();
+
+ return node[0];
+}
+
+function BinaryHeap::Peek()
+{
+ if (this._count == 0) return null;
+
+ return this._queue[0][0];
+}
+
+function BinaryHeap::Count()
+{
+ return this._count;
+}
+
+function BinaryHeap::Exists(item)
+{
+ /* Brute-force find the item (there is no faster way, as we don't have the priority number) */
+ foreach (node in this._queue) {
+ if (node[0] == item) return true;
+ }
+
+ return false;
+}
+
+
+
+function BinaryHeap::_BubbleDown()
+{
+ if (this._count == 0) return;
+
+ local hole = 1;
+ local tmp = this._queue[0];
+
+ /* Start switching parent and child until the tree is restored */
+ while (hole * 2 <= this._count) {
+ local child = hole * 2;
+ if (child != this._count && this._queue[child][1] < this._queue[child - 1][1]) child++;
+ if (this._queue[child - 1][1] >= tmp[1]) break;
+
+ this._queue[hole - 1] = this._queue[child - 1];
+ hole = child;
+ }
+ /* The top value is now at his new place */
+ this._queue[hole - 1] = tmp;
+}
--- a/bin/ai/library/sets/priority_queue/library.nut Tue Jun 10 14:40:32 2008 +0000
+++ b/bin/ai/library/sets/priority_queue/library.nut Tue Jun 10 18:28:39 2008 +0000
@@ -4,7 +4,7 @@
function GetAuthor() { return "OpenTTD NoAI Developers Team"; }
function GetName() { return "Priority Queue"; }
function GetDescription() { return "An implementation of a Priority Queue"; }
- function GetVersion() { return 1; }
+ function GetVersion() { return 2; }
function GetDate() { return "2008-06-10"; }
function CreateInstance() { return "PriorityQueue"; }
}
--- a/bin/ai/library/sets/priority_queue/main.nut Tue Jun 10 14:40:32 2008 +0000
+++ b/bin/ai/library/sets/priority_queue/main.nut Tue Jun 10 18:28:39 2008 +0000
@@ -3,23 +3,21 @@
/**
* Priority Queue
* Peek and Remove always return the current lowest value in the list.
- * Sort is done on insertion. When initial size runs out, array is
- * resized to be twice as big.
+ * Sort is done on insertion only.
*/
class PriorityQueue {
_queue = null;
_count = 0;
- _size = 0;
- constructor(size)
+ constructor()
{
this._count = 0;
- this._queue = array(size * 2);
- this._size = size * 2;
+ this._queue = [];
}
/**
* Insert a new entry in the list.
+ * The complexity of this operation is O(n).
* @param item The item to add to the list.
* @param priority The priority this item has.
*/
@@ -28,6 +26,7 @@
/**
* Pop the first entry of the list.
* This is always the item with the lowest priority.
+ * The complexity of this operation is O(1).
* @return The item of the entry with the lowest priority.
*/
function Pop();
@@ -35,61 +34,49 @@
/**
* Peek the first entry of the list.
* This is always the item with the lowest priority.
+ * The complexity of this operation is O(1).
* @return The item of the entry with the lowest priority.
*/
function Peek();
/**
* Get the amount of current items in the list.
+ * The complexity of this operation is O(1).
* @return The amount of items currently in the list.
*/
function Count();
-}
-
-function PriorityQueue::_checkAndExpand()
-{
- if (this._count != this._size) return;
- /* Create a new array twice the size */
- this._size = this._size * 2;
- local tmpArray = array(this._size);
-
- /* Copy all elements */
- for (local i = 0; i < this._count; i++) {
- tmpArray[i] = this._queue[i];
- }
-
- this._queue = tmpArray;
+ /**
+ * Check if an item exists in the list.
+ * The complexity of this operation is O(n).
+ * @param item The item to check for.
+ * @return True if the item is already in the list.
+ */
+ function Exists(item);
}
function PriorityQueue::Insert(item, priority)
{
- this._checkAndExpand();
+ /* Append dummy entry */
+ this._queue.append(0);
+ this._count++;
- /* Find a place to insert the data */
- if (this._count == 0) {
- this._queue[this._count] = priority;
- this._queue[this._count + 1] = item;
- this._count += 2;
- } else {
- local i;
- for (i = this._count - 2; i >= 0; i -= 2) {
- if (priority > this._queue[i]) {
- /* All items bigger move one place to the right */
- this._queue[i + 2] = this._queue[i];
- this._queue[i + 3] = this._queue[i + 1];
- } else if (item == this._queue[i + 1]) {
- /* Same item, ignore insertion */
- return false;
- } else {
- /* Found place to insert at */
- break;
- }
+ local i;
+ /* Find the point of insertion */
+ for (i = this._count - 2; i >= 0; i--) {
+ if (priority > this._queue[i][1]) {
+ /* All items bigger move one place to the right */
+ this._queue[i + 1] = this._queue[i];
+ } else if (item == this._queue[i][0]) {
+ /* Same item, ignore insertion */
+ return false;
+ } else {
+ /* Found place to insert at */
+ break;
}
- this._queue[i + 2] = priority
- this._queue[i + 3] = item;
- this._count += 2;
}
+ /* Insert new pair */
+ this._queue[i + 1] = [item, priority]
return true;
}
@@ -97,17 +84,31 @@
function PriorityQueue::Pop()
{
if (this._count == 0) return null;
- this._count -= 2;
- return this._queue[this._count + 1];
+
+ local node = this._queue.pop();
+ this._count--;
+
+ return node[0];
}
function PriorityQueue::Peek()
{
if (this._count == 0) return null;
- return this._queue[this._count - 1];
+
+ return this._queue[this._count - 1][0];
}
function PriorityQueue::Count()
{
- return this._count / 2;
+ return this._count;
}
+
+function PriorityQueue::Exists()
+{
+ /* Brute-force find the item (there is no faster way, as we don't have the priority number) */
+ foreach (node in this._queue) {
+ if (node[0] == item) return true;
+ }
+
+ return false;
+}
--- a/bin/ai/regression/regression.nut Tue Jun 10 14:40:32 2008 +0000
+++ b/bin/ai/regression/regression.nut Tue Jun 10 18:28:39 2008 +0000
@@ -1,4 +1,5 @@
-import("sets.priority_queue", "PQ", 1);
+import("sets.priority_queue", "PQ", 2);
+import("sets.binary_heap", "BH", 1);
class Regression extends AIController {
function Start();
@@ -25,26 +26,6 @@
print("--Std--");
print(" abs(-21): " + abs(-21));
print(" abs( 21): " + abs(21));
-
- print("");
- print("--PriorityQueue--");
- local pq = PQ(2);
- pq.Insert(1, 20);
- pq.Insert(2, 40);
- pq.Insert(3, 10);
- pq.Insert(4, 15);
- pq.Insert(5, 60);
- pq.Insert(6, 5);
- print(" Count(): " + pq.Count());
- print(" Peek(): " + pq.Peek());
- print(" Pop(): " + pq.Pop());
- print(" Pop(): " + pq.Pop())
- print(" Pop(): " + pq.Pop())
- print(" Pop(): " + pq.Pop())
- print(" Pop(): " + pq.Pop())
- print(" Pop(): " + pq.Pop())
- print(" Peek(): " + pq.Peek());
- print(" Pop(): " + pq.Pop());
}
function Regression::Base()
@@ -717,6 +698,40 @@
}
}
+function Regression::QueueTest(queue)
+{
+ print(" Count(): " + queue.Count());
+ print(" Peek(): " + queue.Peek());
+ print(" Pop(): " + queue.Pop());
+ queue.Insert(1, 20);
+ queue.Insert(2, 40);
+ queue.Insert(3, 10);
+ queue.Insert(4, 15);
+ queue.Insert(5, 60);
+ queue.Insert(6, 5);
+ print(" Count(): " + queue.Count());
+ print(" Peek(): " + queue.Peek());
+ print(" Pop(): " + queue.Pop());
+ print(" Pop(): " + queue.Pop())
+ print(" Pop(): " + queue.Pop())
+ print(" Pop(): " + queue.Pop())
+ print(" Pop(): " + queue.Pop())
+ print(" Pop(): " + queue.Pop())
+ print(" Peek(): " + queue.Peek());
+ print(" Pop(): " + queue.Pop());
+ print(" Count(): " + queue.Count());
+}
+
+function Regression::Queues()
+{
+ print("");
+ print("--PriorityQueue--");
+ QueueTest(PQ());
+ print("");
+ print("--BinaryHeap--");
+ QueueTest(BH());
+}
+
function Regression::Road()
{
print("");
@@ -1306,6 +1321,7 @@
this.IndustryList();
this.Map();
this.Marine();
+ this.Queues();
this.Road();
this.Sign();
this.Station();
--- a/bin/ai/regression/regression.txt Tue Jun 10 14:40:32 2008 +0000
+++ b/bin/ai/regression/regression.txt Tue Jun 10 18:28:39 2008 +0000
@@ -11,18 +11,6 @@
abs(-21): 21
abs( 21): 21
---PriorityQueue--
- Count(): 6
- Peek(): 6
- Pop(): 6
- Pop(): 3
- Pop(): 4
- Pop(): 1
- Pop(): 2
- Pop(): 5
- Peek(): (null : 0x00000000)
- Pop(): (null : 0x00000000)
-
--AIBase--
Rand(): 753450495
Rand(): 202826571
@@ -5717,6 +5705,38 @@
BuildWaterDepot(): true
BuildDock(): true
+--PriorityQueue--
+ Count(): 0
+ Peek(): (null : 0x00000000)
+ Pop(): (null : 0x00000000)
+ Count(): 6
+ Peek(): 6
+ Pop(): 6
+ Pop(): 3
+ Pop(): 4
+ Pop(): 1
+ Pop(): 2
+ Pop(): 5
+ Peek(): (null : 0x00000000)
+ Pop(): (null : 0x00000000)
+ Count(): 0
+
+--BinaryHeap--
+ Count(): 0
+ Peek(): (null : 0x00000000)
+ Pop(): (null : 0x00000000)
+ Count(): 6
+ Peek(): 6
+ Pop(): 6
+ Pop(): 3
+ Pop(): 4
+ Pop(): 1
+ Pop(): 2
+ Pop(): 5
+ Peek(): (null : 0x00000000)
+ Pop(): (null : 0x00000000)
+ Count(): 0
+
--Road--
Road
IsRoadTile(): false