git.ozlabs.org Git - ccan/blob - junkcode/iasoule32@gmail.com-polynomial/polynomial_adt.h

   1 /* Polynomial ADT
   2 ** A polynomial module with
   3 ** ability to add,sub,mul derivate/integrate, compose ... polynomials
   4 ** ..expansion in progress ...
   5  * Copyright (c) 2009 I. Soule
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29 **          iasoule32@gmail.com
  30 */
  31
  32 #ifndef __POLYNOMIAL_ADT
  33 #define __POLYNOMIAL_ADT
  34
  35 #include <assert.h>
  36 #include <stdlib.h>
  37 #include <stdio.h>
  38 #include <math.h>
  39
  40 #define max(a, b) (a) > (b) ? (a) : (b)
  41 #define sgn(a)    (a) < 0 ? '+' : '-' //for quadratic factored form
  42
  43 typedef struct node {
  44     int exp;
  45     float coeff;
  46     struct node *next;
  47 }Node;
  48
  49 typedef struct polynomial_adt {
  50     Node *head;
  51     int terms, hp; //hp highest power
  52 }PolyAdt;
  53
  54 /**
  55 * create_adt - create a polynomial on the heap
  56 * @hp: the highest power in the polynomial
  57 */
  58 PolyAdt *create_adt(int hp);
  59
  60 /**
  61 * create_node - creates a Node (exponent, constant and next pointer) on the heap
  62 * @constant: the contant in the term
  63 * @exp:      the exponent on the term
  64 * @next:     the next pointer to another term in the polynomial
  65 *
  66 * This should not be called by client code (hence marked static)
  67 * used to assist insert_term()
  68 */
  69 static inline Node *create_node(float constant, int exp, Node *next) {
  70         Node *nNode = malloc(sizeof(Node));
  71     assert(nNode != NULL);
  72
  73     nNode->exp = exp;
  74     nNode->coeff = constant;
  75     nNode->next = next;
  76     return nNode;
  77 }
  78
  79 /**
  80 * insert_term - inserts a term into the polynomial
  81 * @pAdt: the polynomial
  82 * @c:    constant value on the term
  83 * @e:    the exponent on the term
  84 */
  85 void insert_term(PolyAdt *pAdt, float c, int e);
  86
  87 /**
  88 * polyImage - returns an image (direct) copy of the polynomial
  89 * @orig: the polynomial to be duplicated
  90 */
  91 PolyAdt *polyImage(const PolyAdt *orig);
  92
  93
  94 /**
  95 * add - adds two polynomials together, and returns their sum (as a polynomial)
  96 * @a: the 1st polynomial
  97 * @b: the 2nd polynomial
  98 */
  99 PolyAdt *add(const PolyAdt *a, const PolyAdt *b);
 100
 101 /**
 102 * sub - subtracts two polynomials, and returns their difference (as a polynomial)
 103 * @a: the 1st polynomial
 104 * @b: the 2nd polynomial
 105 * Aids in code reuse by negating the terms (b) and then calls the add() function
 106 */
 107 PolyAdt *subtract(const PolyAdt *a, const PolyAdt *b);
 108
 109 /**
 110 * multiply - multiply two polynomials, and returns their product (as a polynomial)
 111 * @a: the 1st polynomial
 112 * @b: the 2nd polynomial
 113 */
 114 PolyAdt *multiply(const PolyAdt *a, const PolyAdt *b);
 115
 116 /**
 117 * derivative - computes the derivative of a polynomial and returns the result
 118 * @a: the polynomial to take the derivative upon
 119 */
 120 PolyAdt *derivative(const PolyAdt *a);
 121
 122 /**
 123 * integrate - computes the integral of a polynomial and returns the result
 124 * @a: the polynomial to take the integral of
 125 *
 126 * Will compute an indefinite integral over a
 127 */
 128 PolyAdt *integrate(const PolyAdt *a);
 129
 130 /**
 131 * quadratic_roots - finds the roots of the polynomial ax^2+bx+c, a != 0 && b != 0
 132 * @a: the polynomial
 133 * @real: a pointer to float of the real(R) part of a
 134 * @cplx: a pointer to float of the imaginary(I) part of a
 135 *
 136 * Usage:
 137 * Two options can be done by the client
 138 * 1. Either pass NULL to real and cplx
 139 *    this will display the roots by printf
 140 *    quadratic_roots(myPolynomial, NULL, NULL);
 141 *
 142 * 2. Pass in pointers** to type float of the real and complex
 143 *    if the discriminant is >0 cplx = -ve root of X
 144 *    quadratic_roots(myPolynomial, &realPart, &complexPart);
 145 */
 146 void quadratic_roots(const PolyAdt *a, float *real, float *cplx);
 147
 148 /**
 149 * exponentiate - computes polynomial exponentiation (P(x))^n, n E Z*
 150 * @a: the polynomial
 151 * @n: the exponent
 152 * Works fast for small n (n < 8) currently runs ~ O(n^2 lg n)
 153 */
 154 PolyAdt *exponentiate(const PolyAdt *a, int n);
 155
 156 /**
 157 * compose - computes the composition of two polynomials P(Q(x)) and returns the composition
 158 * @p: polynomial P(x) which will x will be equal to Q(x)
 159 * @q: polynomial Q(x) which is the argument to P(x)
 160 */
 161 PolyAdt *compose(const PolyAdt *p, const PolyAdt *q);
 162
 163 /**
 164 * destroy_poly - completely frees the polynomial from the heap and resets all values
 165 * @poly: the polynomial to release memory back to the heap
 166 * Usage:
 167 * destroy_poly(myPoly); //puts polynomial on free list
 168 */
 169 void destroy_poly(PolyAdt *poly);
 170
 171 /**
 172 * display_poly - displays the polynomial to the console in nice format
 173 * @a: the polynomial to display
 174 */
 175 void display_poly(const PolyAdt *a);
 176
 177 #endif