Initial population.

1 files changed, 199 insertions, 0 deletions

diff --git a/src/graph/view3D/msort3d.c.pamphlet b/src/graph/view3D/msort3d.c.pamphlet
new file mode 100644
index 00000000..51f01f02
--- /dev/null
+++ b/src/graph/view3D/msort3d.c.pamphlet
@@ -0,0 +1,199 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/graph/view3D msort3d.c}
+\author{The Axiom Team}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{License}
+<<license>>=
+/*
+Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+    - Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+    - 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.
+
+    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+      names of its contributors may be used to endorse or promote products
+      derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "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 COPYRIGHT OWNER
+OR CONTRIBUTORS 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.
+*/
+@
+<<*>>=
+<<license>>
+
+#define _MSORT3D_C
+#include "axiom-c-macros.h"
+#include "useproto.h"
+
+/*****************************************************
+ * Mergesort routine                                 *
+ *                                                   *
+ * This file depends on the file msort.h. There, a   *
+ * data type called linkElement is defined. It is    *
+ * used here and is the main structure being sorted  *
+ * here. You can sort any linked structure, under    *
+ * any name - so long as it has a next field (see    *
+ * below). The define statement, below, renames      *
+ * linkElement to linkThing. All you need to do      *
+ * is change the define statement to rename          *
+ * your structure to linkThing. The first argument   *
+ * you pass to the sort routine is a pointer to      *
+ * the unsorted list. The function returns with      *
+ * that same pointer pointing to a sorted list.      *
+ *                                                   *
+ *  Usage:                                           *
+ *    linkElement *msort(p,min,max,compare)          *
+ *      linkElement *L;                              *
+ *      int min,max;                                 *
+ *      int (*compare)();                            *
+ *                                                   *
+ *    e.g.                                           *
+ *      msort(L,0,N,compare);                        *
+ *                                                   *
+ *    where                                          *
+ *      L is the list of things to be sorted,        *
+ *        it is expected to be a linked list         *
+ *        where the following element is pointed     *
+ *        to by a field called "next"                *
+ *      0 is the index of the first element          *
+ *        (since this routine is called recursively, *
+ *        this field is kept for clarity; it will    *
+ *        always be zero at top level)               *
+ *      N the number of elements in the list         * 
+ *        minus one                                  *
+ *      compare(X,Y) is a comparison function that   *
+ *        returns a -1 if X is less than Y           *
+ *                   0 if X is the same as Y         *
+ *               and 1 if X is greater than Y        *
+ *                                                   *
+ *****************************************************/
+
+
+#include "header.h"
+
+#include "all_3d.H1"
+
+
+#define   linkThing poly
+
+
+
+/**********************
+ * merge(p,q,compare) *
+ **********************/
+
+linkThing *
+#ifdef _NO_PROTO
+merge(p,q,compare)
+     linkThing *p,*q;
+     int (*compare)();
+#else
+merge(linkThing *p, linkThing *q,int (*compare)(linkThing *, linkThing *))
+#endif
+{
+  linkThing *returnVal,*current,*pN,*qN;
+
+  /* return if only one item - take out when insert sort implemented */
+  if (!p) return(q); else if (!q) return(p);
+
+    /* set up the head of the list (first element) */
+  if (compare(p,q) <= 0) {
+    returnVal = current = p;
+    pN = p->next;
+    qN = q;
+  } else {
+    returnVal = current = q;
+    pN = p;
+    qN = q->next;
+  }
+
+    /* merge the two lists */
+  while ((pN != NULL) && (qN != NULL)) {
+    if (compare(pN,qN) <= 0) {   /* pN <= qN */
+      current->next = pN;
+      current = pN;
+      pN = pN->next;
+    } else {
+      current->next = qN;
+      current = qN;
+      qN = qN->next;
+    }
+  }
+
+    /* tag on the tail end */
+  if (pN == NULL) current->next = qN;
+  else current->next = pN;
+
+  return(returnVal);
+
+} /* merge() */
+
+
+
+/*********************************
+ * msort: the top level function *
+ *********************************/
+
+linkThing *
+#ifdef _NO_PROTO
+msort(p,min,max,compare)
+  linkThing *p;
+  int min,max;
+  int (*compare)();
+#else
+msort(linkThing *p,int min,int max,int (*compare)(linkThing *, linkThing *))
+#endif
+{
+  int mid;
+  int i;
+  linkThing *q,*temp,*xxx;
+
+  if (min == max) return p;
+  else {
+    mid = (min + max - 1)/2;
+       /* e.g. [min,max] = [1,6] => mid=3 => q points to 4th */
+    for (i=min,q=p; i<mid; i++,q=q->next);
+    temp = q->next;
+    q->next = 0;
+    xxx = merge(msort(p,min,mid,compare),
+		msort(temp,mid+1,max,compare), compare);
+
+    return(xxx); 
+  }
+
+} /* msort() */
+
+
+
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}