I really enjoyed the survey of programming topics and paradigms this class offered.
Emulation of multidimensional arrays in C
mdarray.c
#include <stdio.h>
#include <stdlib.h>
#include "mdarray.h"
mdarray newmdarray(int dimct, int *dim)
{
mdarray m;
int i;
int elements = 1;
m.dimct = dimct;
m.dim = malloc(dimct * sizeof(int));
for(i = 0; i < dimct; i++)
{
m.dim[i] = dim[i];
elements = elements * dim[i];
}
m.val = malloc(elements * sizeof(double));
return m;
}
void delmdarray(mdarray m)
{
free (m.dim);
free (m.val);
}
double getEl(mdarray m, int *posn)
{
int count = 0;
int mult = 1;
int i;
for(i = m.dimct-1; i >= 0; i--)
{
count += mult*posn[i];
mult = mult*m.dim[i];
}
return m.val[count];
}
void setEl(mdarray m, int *posn, double d)
{
int count = 0;
int mult = 1;
int i;
/*hey this is easier...*/
for(i = m.dimct-1; i >= 0; i--)
{
count += mult*posn[i];
mult = mult*m.dim[i];
}
/*for(i = 2; i <= m.dimct; i++)
{
mult = posn[m.dimct - i];
for(j = 1; j < i; j++)
{
mult = mult*m.dim[m.dimct-j];
}
count += mult;
}
count += posn[m.dimct-1];
m.val[count] = d;*/
m.val[count] = d;
}
mdarray.h
#include <stdio.h>
#include <stdlib.h>
typedef struct mdarray
{
int dimct;
int *dim;
double *val;
} mdarray;
testmain.c
#include <stdlib.h>
#include <stdio.h>
#include "mdarray.h"
extern mdarray newmdarray(int dimct, int *dim);
extern void delmdarray(mdarray m);
extern double getEl(mdarray m, int *posn);
extern void setEl(mdarray m, int *posn, double d);
int main()
{
mdarray y;
int *dim = malloc(5 * sizeof(int));
int *posn = malloc(5 * sizeof(int));
double answer = 0;
dim[0]=4;
dim[1]=5;
dim[2]=3;
dim[3]=6;
dim[4]=7;
posn[0]=2;
posn[1]=3;
posn[2]=1;
posn[3]=4;
posn[4]=5;
y = newmdarray(5, dim);
setEl(y, posn, 3.14159);
answer = getEl(y, posn);
printf("Got and retrieved the value %f\n", answer);
delmdarray(y);
return 0;
}
Quicksort in C
Emulating recursion using only if and goto for control, an incredibly fast sorting method.
quicksort.c
/*Shawn O'Neil
Quicksort using only goto
Everything works, should be no compiler warnings (other than no reference to main)*/
#include <stdlib.h>
#include <stdio.h>
void QuickSort (int *T, int sz);
typedef struct MyStack
{
int *T, bct, act, ect;
} MyStack;
/*void printStack(MyStack *thestack, int howmany)
{
int i;
printf("stack: ");
for(i = 0; i < howmany; i++)
{
printf("%d, ", thestack[i]);
}
printf("\n");
}*/
void QuickSort (int *T, int sz)
{
int *bef, *aft, *eq, stacksize;
int bct, act, ect, i, piv;
MyStack *stack;
stack = malloc(sz*sizeof(MyStack));
stacksize = 0;
Beginning:
/*printStack(stack, stacksize);*/
bef = malloc(sz * sizeof(int));
aft = malloc(sz * sizeof(int));
eq = malloc(sz * sizeof(int));
bct = 0; act = 0; ect = 0;
if(sz <= 1) goto Done;
piv = rand()%sz;
/*for(i = 0; i < sz; i++)
{
if (T[i] < T[piv]) bef[bct++] = T[i];
else if (T[i] == T[piv]) eq[ect++] = T[i];
else aft[act++] = T[i];
}
*/
i = 0;
ForLoop1:
if(i >= sz) goto OutLoop1;
if (T[i] < T[piv]) goto PutInBefore;
if (T[i] == T[piv]) goto PutInEqual;
if (T[i] > T[piv]) goto PutInAfter;
AfterPutIn:
i++;
goto ForLoop1;
OutLoop1:
/*for(i = 0; i < bct; i++) T[i] = bef[i];*/
i = 0;
ForLoop2:
if(i >= bct) goto OutLoop2;
T[i] = bef[i];
i++;
goto ForLoop2;
OutLoop2:
/*for(i = 0; i < ect; i++) T[bct+i] = eq[i];*/
i = 0;
ForLoop3:
if(i >= ect) goto OutLoop3;
T[bct+i] = eq[i];
i++;
goto ForLoop3;
OutLoop3:
/*for(i = 0; i < act; i++) T[bct+ect+i] = aft[i];*/
i = 0;
ForLoop4:
if(i >= act) goto OutLoop4;
T[bct+ect+i] = aft[i];
i++;
goto ForLoop4;
OutLoop4:
free(bef);
free(aft);
free(eq);
/*QuickSort(T, bct);*/
sz = bct;
stack[stacksize].T = T;
stack[stacksize].bct = bct;
stack[stacksize].ect = ect;
stack[stacksize++].act = act;
goto Beginning;
/*QuickSort(&T[bct + ect], act);*/
TailRecursion:
T = &T[bct + ect];
sz = act;
goto Beginning;
goto EndMethod;
PutInBefore:
bef[bct++] = T[i];
goto AfterPutIn;
PutInEqual:
eq[ect++] = T[i];
goto AfterPutIn;
PutInAfter:
aft[act++] = T[i];
goto AfterPutIn;
EndMethod:
Done:
if(stacksize == 0) goto ReallyDone;
T = stack[--stacksize].T;
bct = stack[stacksize].bct;
ect = stack[stacksize].ect;
act = stack[stacksize].act;
goto TailRecursion;
ReallyDone:
i = 9898;
}
/*int main (int argc, char **argv)
{
int AR[10000], i;
srand (time (NULL));
for (i=0; i < 10000; i++) AR[i] = rand()%1000;
for (i=0; i < 10000; i++) printf ("%d ",AR[i]);
printf ("\n\n");
QuickSort (AR,10000);
for (i=0; i < 10000; i++) printf ("%d ",AR[i]);
printf ("\n");
return EXIT_SUCCESS;
}*/
Diamond Inheritance in C
Emulating diamond inheritance in C with function pointers.
PG3.c
/*
Shawn O'Neil - Emulating Diamond inheritance in C
Golly Gee Gosh I've got to be close. I'm fairly sure I've got it this
time, I don't think I need to follow two pointers in any XtoX data
copy methods, as well as in the Genius2MathMajor data copy for just
the Discipline stuff, at least I really hope not.
*/
#include <stdio.h>
#include <stdlib.h>
#include "PG3.h"
void newNMUStudent(NMUStudent *p)
{
int i;
for(i=0; i < 60; i++)
p->Name[i] = ' ';
for(i = 0; i < 8; i++)
p->DOB[i] = '0';
p->GradYear = 0;
p->WorkatJob=NMUStudentWorkatJob;
p->Study=NMUStudentStudy;
p->Speak=NMUStudentSpeak;
}
void newMathMajor(MathMajor *p)
{
int i;
NMUStudent *g;
p->a = (NMUStudent*)&p->Name; /*p's a pointer should point to the address of its name, is this correct syntax?*/
for(i=0; i < 60; i++)
p->Name[i] = ' ';
for(i = 0; i < 8; i++)
p->DOB[i] = '0';
p->GradYear = 0;
p->WorkatJob=NMUStudentWorkatJob;
p->Study=MathMajorStudy;
p->Speak=MathMajorSpeak;
for(i = 0; i < 60; i++)
p->Discipline[i] = ' ';
}
void newCSMajor(CSMajor *p)
{
int i;
p->a = (NMUStudent*)&p->Name;
for(i=0; i < 60; i++)
p->Name[i] = ' ';
for(i = 0; i < 8; i++)
p->DOB[i] = '0';
p->GradYear = 0;
p->WorkatJob=CSMajorWorkatJob;
p->Study=NMUStudentStudy;
p->Speak=CSMajorSpeak;
p->YearsOfExperience = 0;
}
void newGenius(Genius *p)
{
int i;
p->a1 = (NMUStudent*)&p->Name;
p->a2 = (NMUStudent*)&p->Name;
for(i=0; i < 60; i++)
p->Name[i] = ' ';
for(i = 0; i < 8; i++)
p->DOB[i] = '0';
p->GradYear = 0;
p->WorkatJob=CSMajorWorkatJob;
p->Study=MathMajorStudy;
p->Speak=GeniusSpeak;
p->YearsOfExperience = 0;
for(i=0; i < 60; i++)
p->Discipline[i] = ' ';
p->Salary = 0;
}
void NMUStudentWorkatJob(void) { printf("Would you like fries with that?\n");}
void NMUStudentStudy(void) { printf("Pass the beer.\n");}
void NMUStudentSpeak(void) { printf("When is deer camp?\n");}
void MathMajorStudy(void) { printf("Don't close the library yet!\n");}
void MathMajorSpeak(void) { printf("Int dw f = Int w df!\n");}
void CSMajorWorkatJob(void) {printf("I'm paid to do my homework!\n");}
void CSMajorSpeak(void) {printf("while (1) cout << \"You are a jerk!\"\n");}
void GeniusSpeak(void) {printf("I can do fast Fourier Transforms!\n");}
NMUStudent * MathMajor2NMUStudentPtr (MathMajor *p)
{
NMUStudent *g;
g = (NMUStudent*)p->a;
return g;
}
NMUStudent * CSMajor2NMUStudentPtr (CSMajor *p)
{
NMUStudent *g;
g = (NMUStudent*)p->a;
return g;
}
NMUStudent * Genius2NMUStudentPtr (Genius *p)
{
NMUStudent *g;
g = (NMUStudent*)p->a1;
return g;
}
MathMajor * Genius2MathMajorPtr (Genius *p)
{
MathMajor *g;
g = (MathMajor*)&p->a1;
return g;
}
CSMajor * Genius2CSMajorPtr (Genius *p)
{
CSMajor *g;
g = (CSMajor*)&p->a2;
return g;
}
void NMUStudent2NMUStudent(NMUStudent *l, NMUStudent *m)
{
int i;
for(i=0; i < 60; i++)
l->Name[i] = m->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->DOB[i];
l->GradYear = m->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
}
void MathMajor2NMUStudent(NMUStudent *l, MathMajor *m)
{
int i;
for(i=0; i < 60; i++)
l->Name[i] = m->a->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->a->DOB[i];
l->GradYear = m->a->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
}
void MathMajor2MathMajor(MathMajor *l, MathMajor *m)
{
int i;
l->a = m->a;
for(i=0; i < 60; i++)
l->Name[i] = m->Name[i];;
for(i = 0; i < 8; i++)
l->DOB[i] = m->DOB[i];
l->GradYear = m->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->WorkatJob;
l->Speak = m->Speak;*/
for(i = 0; i < 60; i++)
l->Discipline[i] = m->Discipline[i];;
}
void CSMajor2NMUStudent(NMUStudent *l, CSMajor *m)
{
int i;
for(i=0; i < 60; i++)
l->Name[i] = m->a->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->a->DOB[i];
l->GradYear = m->a->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
}
void CSMajor2CSMajor(CSMajor *l, CSMajor *m)
{
int i;
l->a = m->a;
for(i=0; i < 60; i++)
l->Name[i] = m->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->DOB[i];
l->GradYear = m->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
l->YearsOfExperience = m->YearsOfExperience;
}
void Genius2NMUStudent(NMUStudent *l, Genius *m)
{
int i;
for(i=0; i < 60; i++)
l->Name[i] = m->a1->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->a1->DOB[i];
l->GradYear = m->a1->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
}
void Genius2MathMajor(MathMajor *l, Genius *m)
{
int i;
l->a = m->a1;
for(i=0; i < 60; i++)
l->Name[i] = m->a1->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->a1->DOB[i];
l->GradYear = m->a1->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->WorkatJob;
l->Speak = m->Speak;*/
for(i = 0; i < 60; i++)
l->Discipline[i] = m->Discipline[i];;
}
void Genius2CSMajor(CSMajor *l, Genius *m)
{
int i;
l->a = m->a1;
for(i=0; i < 60; i++)
l->Name[i] = m->a1->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->a1->DOB[i];
l->GradYear = m->a1->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
l->YearsOfExperience = m->YearsOfExperience;
}
void Genius2Genius(Genius *l, Genius *m)
{
int i;
l->a1 = m->a1;;
l->a2 = m->a2;
for(i=0; i < 60; i++)
l->Name[i] = m->Name[i];
for(i = 0; i < 8; i++)
l->DOB[i] = m->DOB[i];
l->GradYear = m->GradYear;
/*l->WorkatJob = m->WorkatJob;
l->Study = m->Study;
l->Speak = m->Speak;*/
l->YearsOfExperience = m->YearsOfExperience;
for(i=0; i < 60; i++)
l->Discipline[i] = m->Discipline[i];
l->Salary = m->Salary;
}
PG3.h
typedef struct NMUStudent
{
char Name[60];
char DOB[8];
int GradYear;
void (*WorkatJob)(void);
void (*Study)(void);
void (*Speak)(void);
} NMUStudent;
typedef struct MathMajor
{
NMUStudent *a;
char Discipline[60];
char Name[60];
char DOB[8];
int GradYear;
void (*WorkatJob)(void);
void (*Study)(void);
void (*Speak)(void);
} MathMajor;
typedef struct CSMajor
{
NMUStudent *a;
int YearsOfExperience;
char Name[60];
char DOB[8];
int GradYear;
void (*WorkatJob)(void);
void (*Study)(void);
void (*Speak)(void);
} CSMajor;
typedef struct Genius
{
NMUStudent *a1;
char Discipline[60];
NMUStudent *a2;
int YearsOfExperience;
int Salary;
char Name[60];
char DOB[8];
int GradYear;
void (*WorkatJob)(void);
void (*Study)(void);
void (*Speak)(void);
} Genius;
void newNMUStudent(NMUStudent *p);
void NMUStudentWorkatJob(void);
void NMUStudentStudy(void);
void NMUStudentSpeak(void);
void newMathMajor(MathMajor *p);
/*void MathMajorWorkatJob(void);*/
void MathMajorStudy(void);
void MathMajorSpeak(void);
void newCSMajor(CSMajor *p);
void CSMajorWorkatJob(void);
/*void CSMajorStudy(void);*/
void CSMajorSpeak(void);
void newGenius(Genius *p);
/*void GeniusWorkatJob(void);*/
/*void GeniusStudy(void);*/
void GeniusSpeak(void);
NMUStudent * MathMajor2NMUStudentPtr (MathMajor *p);
NMUStudent * CSMajor2NMUStudentPtr (CSMajor *p);
NMUStudent * Genius2NMUStudentPtr (Genius *p);
MathMajor * Genius2MathMajorPtr (Genius *p);
CSMajor * Genius2CSMajorPtr (Genius *p);
void NMUStudent2NMUStudent(NMUStudent *l, NMUStudent *m);
void MathMajor2NMUStudent(NMUStudent *l, MathMajor *m);
void MathMajor2MathMajor(MathMajor *l, MathMajor *m);
void CSMajor2NMUStudent(NMUStudent *l, CSMajor *m);
void CSMajor2CSMajor(CSMajor *l, CSMajor *m);
void Genius2NMUStudent(NMUStudent *l, Genius *m);
void Genius2MathMajor(MathMajor *l, Genius *m);
void Genius2CSMajor(CSMajor *l, Genius *m);
void Genius2Genius(Genius *l, Genius *m);
Calculating tree skew in Lisp
I wish we had spent more time with Lisp in this class; this program computes the “skew” of a tree, a measure of its imbalance.
skew.lisp
;; Given a tree written in preorder (I think), tell me the "skew"
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Main method, just opens the files and gives the buffers to the recursion
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun skew ()
(with-open-file (skew-out "skew.out" :direction :output)
(with-open-file (skew-in "skew.in" :direction :input)
(docase skew-in skew-out 0)
))
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Gets each case, and if it was an empty case it ends
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun docase(skew-in skew-out counter)
(let ((tosplit (skew2 () skew-in skew-out))(counter (+ counter 1)))
(if (not (null tosplit))
(progn
(list 'hello (input tosplit))
(format skew-out "Case ~D: The skew factor is ~D~%" counter (input tosplit))
(docase skew-in skew-out counter)
)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Read the input until you get to a blank line
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun skew2 (y skew-in skew-out)
(setf word (read-line skew-in))
;(print y)
(if (equal word "")
;if the word read was "" return
y
;else return
(let
((y (append y (list word))))
(skew2 y skew-in skew-out)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Takes an input and gives it to listsplit, using the first entry as
;; where to split and the rest as what to split
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(DEFUN input (x)
;(print x)
(let
((justsplit (listsplit () (rest x) (first x))))
(+
(computeskew (length (first justsplit)) (length (second justsplit)))
(if (equal (first justsplit) ())
0; (length (second justsplit))
(input (first justsplit))
)
(if (equal (second justsplit) ())
0; (length (first justsplit))
(input (second justsplit))
)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Compute the skew of a node given number of nodes on each side
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(DEFUN computeskew (x y)
(let (( y (abs (- x y)) ))
(if (<= y 1)
0
(- y 1)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; takes an empty, a string, and where to break, and makes two lists out of it
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(DEFUN LISTSPLIT (y x where)
(if (string> where (first x))
(if (equal (first x) ()) ;take an element off of the second list and add it to the first
(list y x) ;if the second list is null, just return the two
(listsplit (append y (list (first x))) (rest x) where) ;else actually take one off the second and add it to the first
)
(list y x) ;return both lists now that they are finished
)
)
skew.in
H
C
B
A
D
M
K
I
J
L
N
D
B
A
C
J
F
K
L
M
N
H
C
B
A
D
I
J
N
K
L
M
A
B
C
D
E
F
G
Mergesort in Prolog
Prolog is weird.
mergesort.pl
split([],[],[]).
split(Z,X,Y):-append(X,Y,Z),length(X,LenX),length(Y,LenY),Diff is LenX - LenY, Diff < 2, Diff > -1.
merger([], Y, Y).
merger(Y, [], Y).
merger([A|X],[B|Y],Z):-A < B, append([A],MID,Z), merger(X, [B|Y], MID).
merger([A|X],[B|Y],Z):-A >= B, append([B], MID, Z), merger([A|X],Y,MID).
mergesort([],[]).
mergesort([A],[A]).
mergesort(A,Z):-length(A,Length),Length > 1,split(A,B,C),mergesort(B,First),mergesort(C,Second),merger(First,Second,Z).