Merge pull request #1 from saurabhb17/develop

Added main functions

1 files changed, 220 insertions, 0 deletions

diff --git a/pcbnew/autorouter/queue.cpp b/pcbnew/autorouter/queue.cpp
new file mode 100644
index 0000000..0cf1977
--- /dev/null
+++ b/pcbnew/autorouter/queue.cpp
@@ -0,0 +1,220 @@
+/*
+ * This program source code file is part of KiCad, a free EDA CAD application.
+ *
+ * Copyright (C) 2015 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
+ * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
+ * Copyright (C) 2011 Wayne Stambaugh <stambaughw@verizon.net>
+ *
+ * Copyright (C) 1992-2015 KiCad Developers, see change_log.txt for contributors.
+ *
+ * First copyright (C) Randy Nevin, 1989 (see PCBCA package)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, you may find one here:
+ * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
+ * or you may search the http://www.gnu.org website for the version 2 license,
+ * or you may write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
+ */
+
+
+/**
+ * @file queue.cpp
+ */
+
+#include <fctsys.h>
+#include <common.h>
+
+#include <pcbnew.h>
+#include <autorout.h>
+#include <cell.h>
+
+
+struct PcbQueue /* search queue structure */
+{
+    struct PcbQueue* Next;
+    int              Row;       /* current row                  */
+    int              Col;       /* current column               */
+    int              Side;      /* 0=top, 1=bottom              */
+    int              Dist;      /* path distance to this cell so far        */
+    int              ApxDist;   /* approximate distance to target from here */
+};
+
+static long             qlen = 0;   /* current queue length */
+static struct PcbQueue* Head = NULL;
+static struct PcbQueue* Tail = NULL;
+static struct PcbQueue* Save = NULL;    /* hold empty queue structs */
+
+
+/* Free the memory used for storing all the queue */
+void FreeQueue()
+{
+    struct PcbQueue* p;
+
+    InitQueue();
+
+    while( (p = Save) != NULL )
+    {
+        Save = p->Next;
+        delete p;
+    }
+}
+
+
+/* initialize the search queue */
+void InitQueue()
+{
+    struct PcbQueue* p;
+
+    while( (p = Head) != NULL )
+    {
+        Head    = p->Next;
+        p->Next = Save; Save = p;
+    }
+
+    Tail = NULL;
+    OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
+}
+
+
+/* get search queue item from list */
+void GetQueue( int* r, int* c, int* s, int* d, int* a )
+{
+    struct PcbQueue* p;
+
+    if( (p = Head) != NULL )  /* return first item in list */
+    {
+        *r = p->Row; *c = p->Col;
+        *s = p->Side;
+        *d = p->Dist; *a = p->ApxDist;
+
+        if( (Head = p->Next) == NULL )
+            Tail = NULL;
+
+        /* put node on free list */
+        p->Next = Save; Save = p;
+        ClosNodes++; qlen--;
+    }
+    else /* empty list */
+    {
+        *r = *c = *s = *d = *a = ILLEGAL;
+    }
+}
+
+
+/* add a search node to the list
+ *  :
+ *      1 - OK
+ *      0 - Failed to allocate memory.
+ */
+bool SetQueue( int r, int c, int side, int d, int a, int r2, int c2 )
+{
+    struct PcbQueue* p, * q, * t;
+    int i, j;
+
+    j = 0;                      // gcc warning fix
+
+    if( (p = Save) != NULL )    /* try free list first */
+    {
+        Save = p->Next;
+    }
+    else if( ( p = (PcbQueue*) operator new( sizeof( PcbQueue ), std::nothrow ) ) == NULL )
+    {
+        return 0;
+    }
+
+    p->Row  = r;
+    p->Col  = c;
+    p->Side = side;
+    i = (p->Dist = d) + (p->ApxDist = a);
+    p->Next = NULL;
+
+    if( (q = Head) != NULL ) /* insert in proper position in list */
+    {
+        if( q->Dist + q->ApxDist > i ) /* insert at head */
+        {
+            p->Next = q; Head = p;
+        }
+        else   /* search for proper position */
+        {
+            for( t = q, q = q->Next; q && i > ( j = q->Dist + q->ApxDist ); t = q, q = q->Next )
+                ;
+
+            if( q && i == j && q->Row == r2 && q->Col == c2 )
+            {
+                /* insert after q, which is a goal node */
+                if( ( p->Next = q->Next ) == NULL )
+                    Tail = p;
+
+                q->Next = p;
+            }
+            else  /* insert in front of q */
+            {
+                if( ( p->Next = q ) == NULL )
+                    Tail = p;
+
+                t->Next = p;
+            }
+        }
+    }
+    else /* empty search list */
+    {
+        Head = Tail = p;
+    }
+
+    OpenNodes++;
+
+    if( ++qlen > MaxNodes )
+        MaxNodes = qlen;
+
+    return 1;
+}
+
+
+/* reposition node in list */
+void ReSetQueue( int r, int c, int s, int d, int a, int r2, int c2 )
+{
+    struct PcbQueue* p, * q;
+
+    /* first, see if it is already in the list */
+    for( q = NULL, p = Head; p; q = p, p = p->Next )
+    {
+        if( p->Row == r && p->Col == c && p->Side == s )
+        {
+            /* old one to remove */
+            if( q )
+            {
+                if( ( q->Next = p->Next ) == NULL )
+                    Tail = q;
+            }
+            else if( ( Head = p->Next ) == NULL )
+            {
+                Tail = NULL;
+            }
+
+            p->Next = Save;
+            Save = p;
+            OpenNodes--;
+            MoveNodes++;
+            qlen--;
+            break;
+        }
+    }
+
+    if( !p )            /* not found, it has already been closed once */
+        ClosNodes--;    /* we will close it again, but just count once */
+
+    /* if it was there, it's gone now; insert it at the proper position */
+    bool res = SetQueue( r, c, s, d, a, r2, c2 );
+    (void) res;
+}