Add a parser for linear equations

(Also add the antlr jar and C runtime)

1 files changed, 489 insertions, 0 deletions

diff --git a/impl/antlr/libantlr3c-3.4/src/antlr3basetree.c b/impl/antlr/libantlr3c-3.4/src/antlr3basetree.c
new file mode 100644
index 0000000..bbc81e7
--- /dev/null
+++ b/impl/antlr/libantlr3c-3.4/src/antlr3basetree.c
@@ -0,0 +1,489 @@
+#include    <antlr3basetree.h>
+
+#ifdef	ANTLR3_WINDOWS
+#pragma warning( disable : 4100 )
+#endif
+
+// [The "BSD licence"]
+// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
+// http://www.temporal-wave.com
+// http://www.linkedin.com/in/jimidle
+//
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions
+// are met:
+// 1. Redistributions of source code must retain the above copyright
+//    notice, this list of conditions and the following disclaimer.
+// 2. Redistributions in binary form must reproduce the above copyright
+//    notice, this list of conditions and the following disclaimer in the
+//    documentation and/or other materials provided with the distribution.
+// 3. The name of the author may not be used to endorse or promote products
+//    derived from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+static void				*	getChild			(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);
+static ANTLR3_UINT32		getChildCount		(pANTLR3_BASE_TREE tree);
+static ANTLR3_UINT32		getCharPositionInLine
+(pANTLR3_BASE_TREE tree);
+static ANTLR3_UINT32		getLine				(pANTLR3_BASE_TREE tree);
+static pANTLR3_BASE_TREE    
+getFirstChildWithType
+(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type);
+static void					addChild			(pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child);
+static void					addChildren			(pANTLR3_BASE_TREE tree, pANTLR3_LIST kids);
+static void					replaceChildren		(pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE t);
+
+static	void				freshenPACIndexesAll(pANTLR3_BASE_TREE tree);
+static	void				freshenPACIndexes	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset);
+
+static void					setChild			(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child);
+static void				*	deleteChild			(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i);
+static void				*	dupTree				(pANTLR3_BASE_TREE tree);
+static pANTLR3_STRING		toStringTree		(pANTLR3_BASE_TREE tree);
+
+
+ANTLR3_API pANTLR3_BASE_TREE
+antlr3BaseTreeNew(pANTLR3_BASE_TREE  tree)
+{
+	/* api */
+	tree->getChild				= getChild;
+	tree->getChildCount			= getChildCount;
+	tree->addChild				= (void (*)(pANTLR3_BASE_TREE, void *))(addChild);
+	tree->addChildren			= addChildren;
+	tree->setChild				= setChild;
+	tree->deleteChild			= deleteChild;
+	tree->dupTree				= dupTree;
+	tree->toStringTree			= toStringTree;
+	tree->getCharPositionInLine	= getCharPositionInLine;
+	tree->getLine				= getLine;
+	tree->replaceChildren		= replaceChildren;
+	tree->freshenPACIndexesAll	= freshenPACIndexesAll;
+	tree->freshenPACIndexes		= freshenPACIndexes;
+	tree->getFirstChildWithType	= (void *(*)(pANTLR3_BASE_TREE, ANTLR3_UINT32))(getFirstChildWithType);
+	tree->children				= NULL;
+	tree->strFactory			= NULL;
+
+	/* Rest must be filled in by caller.
+	*/
+	return  tree;
+}
+
+static ANTLR3_UINT32	
+getCharPositionInLine	(pANTLR3_BASE_TREE tree)
+{
+	return  0;
+}
+
+static ANTLR3_UINT32	
+getLine	(pANTLR3_BASE_TREE tree)
+{
+	return  0;
+}
+static pANTLR3_BASE_TREE
+getFirstChildWithType	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 type)
+{
+	ANTLR3_UINT32   i;
+	ANTLR3_UINT32   cs;
+
+	pANTLR3_BASE_TREE	t;
+	if	(tree->children != NULL)
+	{
+		cs	= tree->children->size(tree->children);
+		for	(i = 0; i < cs; i++)
+		{
+			t = (pANTLR3_BASE_TREE) (tree->children->get(tree->children, i));
+			if  (tree->getType(t) == type)
+			{
+				return  (pANTLR3_BASE_TREE)t;
+			}
+		}
+	}
+	return  NULL;
+}
+
+
+
+static void    *
+getChild		(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
+{
+	if	(      tree->children == NULL
+		|| i >= tree->children->size(tree->children))
+	{
+		return NULL;
+	}
+	return  tree->children->get(tree->children, i);
+}
+
+
+static ANTLR3_UINT32
+getChildCount	(pANTLR3_BASE_TREE tree)
+{
+	if	(tree->children == NULL)
+	{
+		return 0;
+	}
+	else
+	{
+		return	tree->children->size(tree->children);
+	}
+}
+
+void	    
+addChild (pANTLR3_BASE_TREE tree, pANTLR3_BASE_TREE child)
+{
+	ANTLR3_UINT32   n;
+	ANTLR3_UINT32   i;
+
+	if	(child == NULL)
+	{
+		return;
+	}
+
+	if	(child->isNilNode(child) == ANTLR3_TRUE)
+	{
+		if  (child->children != NULL && child->children == tree->children)
+		{
+			// TODO: Change to exception rather than ANTLR3_FPRINTF?
+			//
+			ANTLR3_FPRINTF(stderr, "ANTLR3: An attempt was made to add a child list to itself!\n");
+			return;
+		}
+
+        // Add all of the children's children to this list
+        //
+        if (child->children != NULL)
+        {
+            if (tree->children == NULL)
+            {
+                // We are build ing the tree structure here, so we need not
+                // worry about duplication of pointers as the tree node
+                // factory will only clean up each node once. So we just
+                // copy in the child's children pointer as the child is
+                // a nil node (has not root itself).
+                //
+                tree->children = child->children;
+                child->children = NULL;
+                freshenPACIndexesAll(tree);
+                
+            }
+            else
+            {
+                // Need to copy the children
+                //
+                n = child->children->size(child->children);
+
+                for (i = 0; i < n; i++)
+                {
+                    pANTLR3_BASE_TREE entry;
+                    entry = child->children->get(child->children, i);
+
+                    // ANTLR3 lists can be sparse, unlike Array Lists
+                    //
+                    if (entry != NULL)
+                    {
+                        tree->children->add(tree->children, entry, (void (ANTLR3_CDECL *) (void *))child->free);
+                    }
+                }
+            }
+		}
+	}
+	else
+	{
+		// Tree we are adding is not a Nil and might have children to copy
+		//
+		if  (tree->children == NULL)
+		{
+			// No children in the tree we are adding to, so create a new list on
+			// the fly to hold them.
+			//
+			tree->createChildrenList(tree);
+		}
+
+		tree->children->add(tree->children, child, (void (ANTLR3_CDECL *)(void *))child->free);
+		
+	}
+}
+
+/// Add all elements of the supplied list as children of this node
+///
+static void
+addChildren	(pANTLR3_BASE_TREE tree, pANTLR3_LIST kids)
+{
+	ANTLR3_UINT32    i;
+	ANTLR3_UINT32    s;
+
+	s = kids->size(kids);
+	for	(i = 0; i<s; i++)
+	{
+		tree->addChild(tree, (pANTLR3_BASE_TREE)(kids->get(kids, i+1)));
+	}
+}
+
+
+static    void
+setChild	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i, void * child)
+{
+	if	(tree->children == NULL)
+	{
+		tree->createChildrenList(tree);
+	}
+	tree->children->set(tree->children, i, child, NULL, ANTLR3_FALSE);
+}
+
+static void    *
+deleteChild	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 i)
+{
+	if	( tree->children == NULL)
+	{
+		return	NULL;
+	}
+
+	return  tree->children->remove(tree->children, i);
+}
+
+static void    *
+dupTree		(pANTLR3_BASE_TREE tree)
+{
+	pANTLR3_BASE_TREE	newTree;
+	ANTLR3_UINT32	i;
+	ANTLR3_UINT32	s;
+
+	newTree = tree->dupNode	    (tree);
+
+	if	(tree->children != NULL)
+	{
+		s	    = tree->children->size  (tree->children);
+
+		for	(i = 0; i < s; i++)
+		{
+			pANTLR3_BASE_TREE    t;
+			pANTLR3_BASE_TREE    newNode;
+
+			t   = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);
+
+			if  (t!= NULL)
+			{
+				newNode	    = t->dupTree(t);
+				newTree->addChild(newTree, newNode);
+			}
+		}
+	}
+
+	return newTree;
+}
+
+static pANTLR3_STRING
+toStringTree	(pANTLR3_BASE_TREE tree)
+{
+	pANTLR3_STRING  string;
+	ANTLR3_UINT32   i;
+	ANTLR3_UINT32   n;
+	pANTLR3_BASE_TREE   t;
+
+	if	(tree->children == NULL || tree->children->size(tree->children) == 0)
+	{
+		return	tree->toString(tree);
+	}
+
+	/* Need a new string with nothing at all in it.
+	*/
+	string	= tree->strFactory->newRaw(tree->strFactory);
+
+	if	(tree->isNilNode(tree) == ANTLR3_FALSE)
+	{
+		string->append8	(string, "(");
+		string->appendS	(string, tree->toString(tree));
+		string->append8	(string, " ");
+	}
+	if	(tree->children != NULL)
+	{
+		n = tree->children->size(tree->children);
+
+		for	(i = 0; i < n; i++)
+		{   
+			t   = (pANTLR3_BASE_TREE) tree->children->get(tree->children, i);
+
+			if  (i > 0)
+			{
+				string->append8(string, " ");
+			}
+			string->appendS(string, t->toStringTree(t));
+		}
+	}
+	if	(tree->isNilNode(tree) == ANTLR3_FALSE)
+	{
+		string->append8(string,")");
+	}
+
+	return  string;
+}
+
+/// Delete children from start to stop and replace with t even if t is
+/// a list (nil-root tree). Num of children can increase or decrease.
+/// For huge child lists, inserting children can force walking rest of
+/// children to set their child index; could be slow.
+///
+static void					
+replaceChildren		(pANTLR3_BASE_TREE parent, ANTLR3_INT32 startChildIndex, ANTLR3_INT32 stopChildIndex, pANTLR3_BASE_TREE newTree)
+{
+	ANTLR3_INT32	replacingHowMany;		// How many nodes will go away
+	ANTLR3_INT32	replacingWithHowMany;	// How many nodes will replace them
+	ANTLR3_INT32	numNewChildren;			// Tracking variable
+	ANTLR3_INT32	delta;					// Difference in new vs existing count
+
+	ANTLR3_INT32	i;
+	ANTLR3_INT32	j;
+
+	pANTLR3_VECTOR	newChildren;			// Iterator for whatever we are going to add in
+	ANTLR3_BOOLEAN	freeNewChildren;		// Whether we created the iterator locally or reused it
+
+	if	(parent->children == NULL)
+	{
+		ANTLR3_FPRINTF(stderr, "replaceChildren call: Indexes are invalid; no children in list for %s", parent->getText(parent)->chars);
+		return;
+	}
+
+	// Either use the existing list of children in the supplied nil node, or build a vector of the
+	// tree we were given if it is not a nil node, then we treat both situations exactly the same
+	//
+	if	(newTree->isNilNode(newTree))
+	{
+		newChildren = newTree->children;
+		freeNewChildren = ANTLR3_FALSE;		// We must NO free this memory
+	}
+	else
+	{
+		newChildren = antlr3VectorNew(1);
+		if	(newChildren == NULL)
+		{
+			ANTLR3_FPRINTF(stderr, "replaceChildren: out of memory!!");
+			exit(1);
+		}
+		newChildren->add(newChildren, (void *)newTree, NULL);
+
+		freeNewChildren = ANTLR3_TRUE;		// We must free this memory
+	}
+
+	// Initialize
+	//
+	replacingHowMany		= stopChildIndex - startChildIndex + 1;
+	replacingWithHowMany	= newChildren->size(newChildren);
+	delta					= replacingHowMany - replacingWithHowMany;
+	numNewChildren			= newChildren->size(newChildren);
+
+	// If it is the same number of nodes, then do a direct replacement
+	//
+	if	(delta == 0)
+	{
+		pANTLR3_BASE_TREE	child;
+
+		// Same number of nodes
+		//
+		j	= 0;
+		for	(i = startChildIndex; i <= stopChildIndex; i++)
+		{
+			child = (pANTLR3_BASE_TREE) newChildren->get(newChildren, j);
+			parent->children->set(parent->children, i, child, NULL, ANTLR3_FALSE);
+			child->setParent(child, parent);
+			child->setChildIndex(child, i);
+		}
+	}
+	else if (delta > 0)
+	{
+		ANTLR3_UINT32	indexToDelete;
+
+		// Less nodes than there were before
+		// reuse what we have then delete the rest
+		//
+		for	(j = 0; j < numNewChildren; j++)
+		{
+			parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);
+		}
+
+		// We just delete the same index position until done
+		//
+		indexToDelete = startChildIndex + numNewChildren;
+
+		for	(j = indexToDelete; j <= (ANTLR3_INT32)stopChildIndex; j++)
+		{
+			parent->children->remove(parent->children, indexToDelete);
+		}
+
+		parent->freshenPACIndexes(parent, startChildIndex);
+	}
+	else
+	{
+		ANTLR3_UINT32 numToInsert;
+
+		// More nodes than there were before
+		// Use what we can, then start adding
+		//
+		for	(j = 0; j < replacingHowMany; j++)
+		{
+			parent->children->set(parent->children, startChildIndex + j, newChildren->get(newChildren, j), NULL, ANTLR3_FALSE);
+		}
+
+		numToInsert = replacingWithHowMany - replacingHowMany;
+
+		for	(j = replacingHowMany; j < replacingWithHowMany; j++)
+		{
+			parent->children->add(parent->children, newChildren->get(newChildren, j), NULL);
+		}
+
+		parent->freshenPACIndexes(parent, startChildIndex);
+	}
+
+	if	(freeNewChildren == ANTLR3_TRUE)
+	{
+		ANTLR3_FREE(newChildren->elements);
+		newChildren->elements = NULL;
+		newChildren->size = 0;
+		ANTLR3_FREE(newChildren);		// Will not free the nodes
+	}
+}
+
+/// Set the parent and child indexes for all children of the
+/// supplied tree.
+///
+static	void
+freshenPACIndexesAll(pANTLR3_BASE_TREE tree)
+{
+	tree->freshenPACIndexes(tree, 0);
+}
+
+/// Set the parent and child indexes for some of the children of the
+/// supplied tree, starting with the child at the supplied index.
+///
+static	void
+freshenPACIndexes	(pANTLR3_BASE_TREE tree, ANTLR3_UINT32 offset)
+{
+	ANTLR3_UINT32	count;
+	ANTLR3_UINT32	c;
+
+	count	= tree->getChildCount(tree);		// How many children do we have 
+
+	// Loop from the supplied index and set the indexes and parent
+	//
+	for	(c = offset; c < count; c++)
+	{
+		pANTLR3_BASE_TREE	child;
+
+		child = tree->getChild(tree, c);
+
+		child->setChildIndex(child, c);
+		child->setParent(child, tree);
+	}
+}
+