Changeset - r10759:b4c7c8262caf
Parent rev.
Child rev.
[Not reviewed]
master
0 6 0
truebrain - 15 years ago 2009-01-15 16:53:18
truebrain@openttd.org
(svn r15092) -Fix [NoAI]: make the library internal class name consistant with their directory name
6 files changed with 30 insertions and 30 deletions:
bin/ai/library/queue/binary_heap/library.nut
3
3
bin/ai/library/queue/binary_heap/main.nut
7
7
bin/ai/library/queue/fibonacci_heap/library.nut
3
3
bin/ai/library/queue/fibonacci_heap/main.nut
8
8
bin/ai/library/queue/priority_queue/library.nut
3
3
bin/ai/library/queue/priority_queue/main.nut
6
6
0 comments (0 inline, 0 general)
bin/ai/library/queue/binary_heap/library.nut
➞
Show inline comments
 
/* $Id$ */
 

			




	
	
	
		
 
class BinaryHeap extends AILibrary {

			




	
	
	
		
 
class Binary_Heap extends AILibrary {

			




	
	
	
		
 
	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }

			




	
	
	
		
 
	function GetName()        { return "Binary Heap"; }

			




	
	
	
		
 
	function GetShortName()   { return "QUBH"; }

			




	
	
	
		
 
	function GetDescription() { return "An implementation of a Binary Heap"; }

			




	
	
	
		
 
	function GetVersion()     { return 1; }

			




	
	
	
		
 
	function GetDate()        { return "2008-06-10"; }

			




	
	
	
		
 
	function CreateInstance() { return "BinaryHeap"; }

			




	
	
	
		
 
	function CreateInstance() { return "Binary_Heap"; }

			




	
	
	
		
 
	function GetCategory()    { return "Queue"; }

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
RegisterLibrary(BinaryHeap());

			




	
	
	
		
 
RegisterLibrary(Binary_Heap());

			




        

    


    
    

    

        

                

                    bin/ai/library/queue/binary_heap/main.nut
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -5,7 +5,7 @@

			




	
	
	
		
 
 *  Peek and Pop always return the current lowest value in the list.

			




	
	
	
		
 
 *  Sort is done on insertion and on deletion.

			




	
	
	
		
 
 */

			




	
	
	
		
 
class BinaryHeap

			




	
	
	
		
 
class Binary_Heap

			




	
	
	
		
 
{

			




	
	
	
		
 
	_queue = null;

			




	
	
	
		
 
	_count = 0;

			




	
	
		
 
@@ -55,7 +55,7 @@ class BinaryHeap

			




	
	
	
		
 
	function Exists(item);

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
function BinaryHeap::Insert(item, priority)

			




	
	
	
		
 
function Binary_Heap::Insert(item, priority)

			




	
	
	
		
 
{

			




	
	
	
		
 
	/* Append dummy entry */

			




	
	
	
		
 
	_queue.append(0);

			




	
	
		
 
@@ -71,7 +71,7 @@ function BinaryHeap::Insert(item, priori

			




	
	
	
		
 
	return true;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function BinaryHeap::Pop()

			




	
	
	
		
 
function Binary_Heap::Pop()

			




	
	
	
		
 
{

			




	
	
	
		
 
	if (_count == 0) return null;

			




	
	
	
		
 

			




	
	
		
 
@@ -86,19 +86,19 @@ function BinaryHeap::Pop()

			




	
	
	
		
 
	return node[0];

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function BinaryHeap::Peek()

			




	
	
	
		
 
function Binary_Heap::Peek()

			




	
	
	
		
 
{

			




	
	
	
		
 
	if (_count == 0) return null;

			




	
	
	
		
 

			




	
	
	
		
 
	return _queue[0][0];

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function BinaryHeap::Count()

			




	
	
	
		
 
function Binary_Heap::Count()

			




	
	
	
		
 
{

			




	
	
	
		
 
	return _count;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function BinaryHeap::Exists(item)

			




	
	
	
		
 
function Binary_Heap::Exists(item)

			




	
	
	
		
 
{

			




	
	
	
		
 
	/* Brute-force find the item (there is no faster way, as we don't have the priority number) */

			




	
	
	
		
 
	foreach (node in _queue) {

			




	
	
		
 
@@ -110,7 +110,7 @@ function BinaryHeap::Exists(item)

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 

			




	
	
	
		
 
function BinaryHeap::_BubbleDown()

			




	
	
	
		
 
function Binary_Heap::_BubbleDown()

			




	
	
	
		
 
{

			




	
	
	
		
 
	if (_count == 0) return;

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    bin/ai/library/queue/fibonacci_heap/library.nut
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
	
		
 
/* $Id$ */

			




	
	
	
		
 

			




	
	
	
		
 
class FibonacciHeap extends AILibrary {

			




	
	
	
		
 
class Fibonacci_Heap extends AILibrary {

			




	
	
	
		
 
	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }

			




	
	
	
		
 
	function GetName()        { return "Fibonacci Heap"; }

			




	
	
	
		
 
	function GetShortName()   { return "QUFH"; }

			




	
	
	
		
 
	function GetDescription() { return "An implementation of a Fibonacci Heap"; }

			




	
	
	
		
 
	function GetVersion()     { return 1; }

			




	
	
	
		
 
	function GetDate()        { return "2008-08-22"; }

			




	
	
	
		
 
	function CreateInstance() { return "FibonacciHeap"; }

			




	
	
	
		
 
	function CreateInstance() { return "Fibonacci_Heap"; }

			




	
	
	
		
 
	function GetCategory()    { return "Queue"; }

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
RegisterLibrary(FibonacciHeap());

			




	
	
	
		
 
RegisterLibrary(Fibonacci_Heap());

			




        

    


    
    

    

        

                

                    bin/ai/library/queue/fibonacci_heap/main.nut
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -7,7 +7,7 @@

			




	
	
	
		
 
 *  Insert is implemented as a lazy insert, as it will simply add the new

			




	
	
	
		
 
 *  node to the root list. Sort is done on every Pop operation.

			




	
	
	
		
 
 */

			




	
	
	
		
 
class FibonacciHeap {

			




	
	
	
		
 
class Fibonacci_Heap {

			




	
	
	
		
 
	_min = null;

			




	
	
	
		
 
	_min_index = 0;

			




	
	
	
		
 
	_min_priority = 0;

			




	
	
		
 
@@ -67,7 +67,7 @@ class FibonacciHeap {

			




	
	
	
		
 
	function Exists(item);

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
function FibonacciHeap::Insert(item, priority) {

			




	
	
	
		
 
function Fibonacci_Heap::Insert(item, priority) {

			




	
	
	
		
 
	/* Create a new node instance to add to the heap. */

			




	
	
	
		
 
	local node = Node();

			




	
	
	
		
 
	/* Changing params is faster than using constructor values */

			




	
	
		
 
@@ -86,7 +86,7 @@ function FibonacciHeap::Insert(item, pri

			




	
	
	
		
 
	_count++;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function FibonacciHeap::Pop() {

			




	
	
	
		
 
function Fibonacci_Heap::Pop() {

			




	
	
	
		
 

			




	
	
	
		
 
	if (_count == 0) return null;

			




	
	
	
		
 

			




	
	
		
 
@@ -150,16 +150,16 @@ function FibonacciHeap::Pop() {

			




	
	
	
		
 
	return z.item;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function FibonacciHeap::Peek() {

			




	
	
	
		
 
function Fibonacci_Heap::Peek() {

			




	
	
	
		
 
	if (_count == 0) return null;

			




	
	
	
		
 
	return _min.item;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function FibonacciHeap::Count() {

			




	
	
	
		
 
function Fibonacci_Heap::Count() {

			




	
	
	
		
 
	return _count;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function FibonacciHeap::Exists(item) {

			




	
	
	
		
 
function Fibonacci_Heap::Exists(item) {

			




	
	
	
		
 
	return ExistsIn(_root_list, item);

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
		
 
@@ -169,7 +169,7 @@ function FibonacciHeap::Exists(item) {

			




	
	
	
		
 
 * @param item The item to search for.

			




	
	
	
		
 
 * @return True if the item is found, false otherwise.

			




	
	
	
		
 
 */

			




	
	
	
		
 
function FibonacciHeap::ExistsIn(list, item) {

			




	
	
	
		
 
function Fibonacci_Heap::ExistsIn(list, item) {

			




	
	
	
		
 

			




	
	
	
		
 
	foreach (val in list) {

			




	
	
	
		
 
		if (val.item == item) {

			




	
	
		
 
@@ -190,7 +190,7 @@ function FibonacciHeap::ExistsIn(list, i

			




	
	
	
		
 
/**

			




	
	
	
		
 
 * Basic class the fibonacci heap is composed of.

			




	
	
	
		
 
 */

			




	
	
	
		
 
class FibonacciHeap.Node {

			




	
	
	
		
 
class Fibonacci_Heap.Node {

			




	
	
	
		
 
	degree = null;

			




	
	
	
		
 
	child = null;

			




	
	
	
		
 

			




        

    


    
    

    

        

                

                    bin/ai/library/queue/priority_queue/library.nut
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
	
		
 
/* $Id$ */

			




	
	
	
		
 

			




	
	
	
		
 
class PriorityQueue extends AILibrary {

			




	
	
	
		
 
class Priority_Queue extends AILibrary {

			




	
	
	
		
 
	function GetAuthor()      { return "OpenTTD NoAI Developers Team"; }

			




	
	
	
		
 
	function GetName()        { return "Priority Queue"; }

			




	
	
	
		
 
	function GetShortName()   { return "QUPQ"; }

			




	
	
	
		
 
	function GetDescription() { return "An implementation of a Priority Queue"; }

			




	
	
	
		
 
	function GetVersion()     { return 2; }

			




	
	
	
		
 
	function GetDate()        { return "2008-06-10"; }

			




	
	
	
		
 
	function CreateInstance() { return "PriorityQueue"; }

			




	
	
	
		
 
	function CreateInstance() { return "Priority_Queue"; }

			




	
	
	
		
 
	function GetCategory()    { return "Queue"; }

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
RegisterLibrary(PriorityQueue());

			




	
	
	
		
 
RegisterLibrary(Priority_Queue());

			




        

    


    
    

    

        

                

                    bin/ai/library/queue/priority_queue/main.nut
                

                

                  
                      
                        

                      ➞

                      
                        
                  

                  
                      
                  
                      
                  
                      
                  
                      
                  
                  
                

                

                    Show inline comments
                    
                

        

        

            



	
	
		
 
@@ -5,7 +5,7 @@

			




	
	
	
		
 
 *  Peek and Pop always return the current lowest value in the list.

			




	
	
	
		
 
 *  Sort is done on insertion only.

			




	
	
	
		
 
 */

			




	
	
	
		
 
class PriorityQueue

			




	
	
	
		
 
class Priority_Queue

			




	
	
	
		
 
{

			




	
	
	
		
 
	_queue = null;

			




	
	
	
		
 
	_count = 0;

			




	
	
		
 
@@ -56,7 +56,7 @@ class PriorityQueue

			




	
	
	
		
 
	function Exists(item);

			




	
	
	
		
 
};

			




	
	
	
		
 

			




	
	
	
		
 
function PriorityQueue::Insert(item, priority)

			




	
	
	
		
 
function Priority_Queue::Insert(item, priority)

			




	
	
	
		
 
{

			




	
	
	
		
 
	/* Append dummy entry */

			




	
	
	
		
 
	_queue.append(0);

			




	
	
		
 
@@ -82,7 +82,7 @@ function PriorityQueue::Insert(item, pri

			




	
	
	
		
 
	return true;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function PriorityQueue::Pop()

			




	
	
	
		
 
function Priority_Queue::Pop()

			




	
	
	
		
 
{

			




	
	
	
		
 
	if (_count == 0) return null;

			




	
	
	
		
 

			




	
	
		
 
@@ -92,19 +92,19 @@ function PriorityQueue::Pop()

			




	
	
	
		
 
	return node[0];

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function PriorityQueue::Peek()

			




	
	
	
		
 
function Priority_Queue::Peek()

			




	
	
	
		
 
{

			




	
	
	
		
 
	if (_count == 0) return null;

			




	
	
	
		
 

			




	
	
	
		
 
	return _queue[_count - 1][0];

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function PriorityQueue::Count()

			




	
	
	
		
 
function Priority_Queue::Count()

			




	
	
	
		
 
{

			




	
	
	
		
 
	return _count;

			




	
	
	
		
 
}

			




	
	
	
		
 

			




	
	
	
		
 
function PriorityQueue::Exists(item)

			




	
	
	
		
 
function Priority_Queue::Exists(item)

			




	
	
	
		
 
{

			




	
	
	
		
 
	/* Brute-force find the item (there is no faster way, as we don't have the priority number) */

			




	
	
	
		
 
	foreach (node in _queue) {

			




        

    



    


    



    



      

      





    
    0 comments (0 inline, 0 general)
    





    


  

  







  


    




    








    
        Server instance: code.theleruby.com-48
    
    
        This site is powered by
            Kallithea,
        which is
        © 2010–2022 by various authors & licensed under GPLv3.
            – Support