aboutsummaryrefslogtreecommitdiff
path: root/src/graph/view3D/msort3d.c.pamphlet
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
committerdos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
commitab8cc85adde879fb963c94d15675783f2cf4b183 (patch)
treec202482327f474583b750b2c45dedfc4e4312b1d /src/graph/view3D/msort3d.c.pamphlet
downloadopen-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz
Initial population.
Diffstat (limited to 'src/graph/view3D/msort3d.c.pamphlet')
-rw-r--r--src/graph/view3D/msort3d.c.pamphlet199
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}