home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1989 / 09 / peterson.lst < prev    next >
File List  |  1989-07-27  |  13KB  |  434 lines
  1. _SETTING PRECEDENCE_
  2. by Mark C. Peterson
  3.  
  4. [LISTING ONE]
  5.  
  6. /* SPARRAY.H - Header file for SPARRAY.C */
  7. /* Copyright (C) 1988, Mark C. Peterson */
  8.  
  9. #ifndef SPARRAY_H
  10. #define SPARRAY_H
  11.  
  12. union VARIABLE {
  13.    long Num;
  14.    void *Ptr;
  15. };
  16.  
  17. typedef struct _SPELEM {
  18.    struct _SPELEM *Higher, *Lower;
  19.    unsigned long Loc;
  20.    union VARIABLE Element;
  21. } SPELEM;
  22.  
  23. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  24.  * Loc          The location of the element within the sparse array.         *
  25.  * Higher       A pointer to a SPELEM with a higher "Loc" of a lower         *
  26.  *              precedence.                                                  *
  27.  * Lower        A pointer to a SPELEM with a lower "Loc" of a lower          *
  28.  *              precedence.                                                  *
  29.  * Element      A union VARIABLE for storage of either a "long" or "void*"   *
  30.  *              element.  "Element" is initialize to a NULL (either 0L or    *
  31.  *              (void*)0) by MakeSpArray() or when an element is removed by  *
  32.  *              RemoveSpElem().                                              *
  33.  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  34.  
  35. typedef struct _SPARRAY {
  36.    SPELEM *SpElem, *Root, *EmptyElem;
  37.    unsigned Size, ElemUsed, HighestUsed;
  38. } SPARRAY;
  39.  
  40. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  41.  * SpElem       An array of SPELEM structures.  The number of SPELEM         *
  42.  *              structures in the array is stored in "Size".                 *
  43.  * Root         A pointer to an SPELEM structure that is the root to the     *
  44.  *              Ptree.                                                       *
  45.  * EmptyElem    A pointer to a chain of SPELEM structures (along the         *
  46.  *              "Higher" pointer) that has been removed from the sparse      *
  47.  *              array.                                                       *
  48.  * Size         The number of SPELEM structures in SpElem array.             *
  49.  * ElemUsed     Keeps track of the number of elements in the sparse array.   *
  50.  *              "ElemUsed" should be checked by the programmer periodically  *
  51.  *              to see if the sparse array is full (i.e "ElemUsed" ==        *
  52.  *              "Size").                                                     *
  53.  * HighestUsed  Used by PlaceElement(). If there are no empty elements       *
  54.  *              ("EmptyElem" == NULL) and "HighestUsed" == "Size" the        *
  55.  *              function returns a NULL.                                     *
  56.  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  57.  
  58. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
  59.  * Note that the only variable that should be changed directly by the  *
  60.  * programmer is the "Element" member in the SPELEM structure.         *
  61.  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  62.  
  63. SPARRAY *MakeSpArray(unsigned NumElem);
  64. /* Creates the SPARRAY structure with "NumElem" number of elements, 
  65.    initializes all the elements to zero, and returns a pointer to the 
  66.    SPARRAY structure. */
  67.  
  68. SPELEM *FindSpElem(SPARRAY *Array, unsigned long Loc);
  69. /* Returns a pointer to the SPELEM structure associated  with "Loc".  
  70.    if "Loc" is not in the sparse array the function returns a NULL. */
  71.  
  72. SPELEM *PlaceSpElem(SPARRAY *Array, unsigned long Loc);
  73. /* Places the "Loc" in the Ptree structure.  Returns a NULL if the sparse
  74.    array is full.
  75.    WARNING:  This function should only be called if FindElement() returns 
  76.    a NULL.  Attempts to place a "Loc" that is already there will corrupt 
  77.    the Ptree. */
  78.  
  79. SPELEM *SpArray(SPARRAY *Array, unsigned long Loc);
  80. /* Attempts to locate "Loc" using FindElement().  If not found the "Loc" 
  81.    is placed using PlaceElement().  Returns a NULL if "Loc" is not found 
  82.    and the sparse array is full. */
  83.  
  84. void ClrSpArray(SPARRAY *Array);
  85. /* Removes all the elements from the sparse array. */
  86.  
  87. void DeleteSpArray(SPARRAY **ArrayRef);
  88. /* Frees the memory allocated by MakeSpArray and sets the SPARRAY pointer
  89.    referenced by ArrayRef to NULL. */
  90.  
  91. void RemoveSpElem(SPARRAY *Array, unsigned long Loc);
  92. /* Removes "Loc" from the sparse array. */
  93.  
  94. #endif
  95.  
  96.  
  97.  
  98.  
  99. [LISITNG TWO]
  100.  
  101. /* SPARRAY.C - Routines for maintaining a sparse array using a Ptree */
  102. /* Copyright (C) 1988, Mark C. Peterson */
  103.  
  104. #include <stdlib.h>
  105. #include "SPARRAY.H"
  106.  
  107. static SPELEM 
  108.    *PruneLower(SPELEM *this, unsigned long Loc),
  109.    *PruneHigher(SPELEM *this, unsigned long Loc);
  110.  
  111. static unsigned 
  112.     ChkPrecGT(unsigned long Loc, unsigned long ThisLoc);
  113. /* Check "Loc" precedence greater than "ThisLoc" precedence. */
  114.  
  115. SPARRAY *MakeSpArray(unsigned NumElem) {
  116.    SPARRAY *Array;
  117.  
  118.    if(Array = calloc(1, sizeof(SPARRAY))) {
  119.       Array->Size = NumElem;
  120.       if(!(Array->SpElem = (SPELEM*)calloc(NumElem, sizeof(SPELEM)))) {
  121.          free(Array);
  122.          Array = (SPARRAY*)0; 
  123.       }
  124.    }
  125.    return(Array); 
  126. }
  127.  
  128. static SPELEM *PruneLower(SPELEM *this, unsigned long Loc) {  
  129.    SPELEM *RetPtr;
  130.  
  131.    while(this->Lower && (this->Lower->Loc > Loc)) this = this->Lower;
  132.    if(RetPtr = this->Lower) this->Lower = PruneHigher(this->Lower, Loc);
  133.    return(RetPtr);
  134. }
  135.  
  136. static SPELEM *PruneHigher(SPELEM *this, unsigned long Loc) {   
  137.    SPELEM *RetPtr;
  138.  
  139.    while(this->Higher && (this->Higher->Loc < Loc)) 
  140.       this = this->Higher;
  141.    if(RetPtr = this->Higher) this->Higher = PruneLower(this->Higher, Loc);
  142.    return(RetPtr);
  143. }
  144.  
  145. static unsigned ChkPrecGT(unsigned long Loc, unsigned long ThisLoc) {
  146.    unsigned long LocPrec, ThisPrec;
  147.  
  148.    while(Loc && ThisLoc) {
  149.       LocPrec = (Loc - 1) ^ Loc;
  150.       ThisPrec = (ThisLoc - 1) ^ ThisLoc;
  151.       if(LocPrec != ThisPrec) return(LocPrec > ThisPrec);
  152.       Loc >>= 1;
  153.       ThisLoc >>= 1;
  154.    }
  155.    return(Loc > ThisLoc);
  156. }
  157.  
  158. SPELEM *PlaceSpElem(SPARRAY *Array, unsigned long Loc) {
  159.    SPELEM **this, *New;
  160.  
  161. /* This section sets up a "New" SPELEM pointer */
  162.    if(!Array->EmptyElem) {
  163.       if(Array->HighestUsed < Array->Size)
  164.          New = &Array->SpElem[Array->HighestUsed++];
  165.       else return((SPELEM*)0);
  166.    }
  167.    else {
  168.       New = Array->EmptyElem;
  169.       Array->EmptyElem = Array->EmptyElem->Higher;
  170.    }
  171.    Array->ElemUsed++;
  172.    New->Higher = New->Lower = (SPELEM*)0;
  173.    New->Loc = Loc;
  174.  
  175. /* This section places the "New" SPELEM pointer into the Ptree */
  176.    this = &Array->Root;
  177.    while(*this) {
  178.       if(ChkPrecGT(Loc, (*this)->Loc)) {
  179.          if((*this)->Loc > Loc) {
  180.             New->Higher = *this;
  181.             New->Lower = PruneLower(*this, Loc);
  182.          }
  183.          else {
  184.             New->Lower = *this;
  185.             New->Higher = PruneHigher(*this, Loc);
  186.          }
  187.          break;
  188.       }
  189.       else this = (*this)->Loc > Loc ? &(*this)->Lower : &(*this)->Higher;
  190.    }
  191.    *this = New;
  192.    return(*this);
  193. }
  194.  
  195. void RemoveSpElem(SPARRAY *Array, unsigned long Loc) {
  196.    SPELEM *Hole, *HigherInter, *LowerInter, **this;
  197.  
  198.    /* Find the element to be removed */
  199.    this = &Array->Root;
  200.    while(*this && ((*this)->Loc != Loc))
  201.       this = (*this)->Loc > Loc ? &(*this)->Lower : &(*this)->Higher;
  202.  
  203.    if(Hole = *this) {
  204.     /* Fill the hole in the Ptree if the element was found */
  205.       LowerInter = Hole->Lower;     /* Lower Interface Pointer */
  206.       HigherInter = Hole->Higher;   /* Higher Interface Pointer */
  207.       while(LowerInter && HigherInter) {
  208.          if(ChkPrecGT(LowerInter->Loc, HigherInter->Loc)) {
  209.             *this = LowerInter;
  210.             this = &LowerInter->Higher;
  211.             LowerInter = LowerInter->Higher;
  212.          }
  213.          else {
  214.             *this = HigherInter;
  215.             this = &HigherInter->Lower;
  216.             HigherInter = HigherInter->Lower;
  217.          }
  218.       }
  219.       if(LowerInter) *this = LowerInter;
  220.       else *this = HigherInter;
  221.  
  222.    /* Link the unused spot into the chain of empty elements along 
  223.       the "Higher" linkage. */
  224.       Hole->Higher = Array->EmptyElem;
  225.       Array->EmptyElem = Hole;
  226.       Array->ElemUsed--;      /* Update the number of elements used */
  227.    }
  228. }
  229.  
  230. SPELEM *FindSpElem(SPARRAY *Array, unsigned long Loc) {
  231.    SPELEM *this;
  232.  
  233.    this = Array->Root;
  234.    while(this && (this->Loc != Loc))
  235.       this = this->Loc > Loc ? this->Lower : this->Higher;
  236.    return(this);
  237. }
  238.  
  239. SPELEM *SpArray(SPARRAY *Array, unsigned long Loc) {
  240.    SPELEM *Found;
  241.  
  242.    Found = FindSpElem(Array, Loc);
  243.    if(!Found) 
  244.       Found = PlaceSpElem(Array, Loc);
  245.    return(Found);
  246. }
  247.  
  248. void ClrSpArray(SPARRAY *Array) {
  249.    unsigned n;
  250.  
  251.    Array->EmptyElem = Array->Root = (SPELEM*)0;
  252.    for(n = 0; n < Array->Size; n++)
  253.       Array->SpElem[n].Element.Num = 0L;
  254.    Array->HighestUsed = Array->ElemUsed = 0;
  255. }
  256.  
  257. void DeleteSpArray(SPARRAY **ArrayRef) {
  258.    SPARRAY *Array;
  259.  
  260.    if(Array = *ArrayRef) {
  261.       free(Array->SpElem);
  262.       free(Array);
  263.       *ArrayRef = (SPARRAY*)0;
  264.    }
  265. }
  266.  
  267.  
  268.  
  269.  
  270. [LISTING THREE]
  271.  
  272.  
  273. /* DIAGARRA.H - Header file for DIAGARRA.C */
  274. /* Copyright (C) 1988, Mark C. Peterson */
  275.  
  276. #ifndef DIAGARRA_H
  277. #define DIAGARRA_H
  278.  
  279. #include "SPARRAY.H"
  280.  
  281. extern unsigned MaxTrav, NumElem, NumLines;
  282. extern unsigned long TotalTrav;
  283. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
  284.  * MaxTrav -   Maximum number of traversals from the root to any     *
  285.  *             number in the Ptree, set by SumSpArray().             *
  286.  * NumElem -   Number of elements in the Ptree, set by SumSpArray(). *
  287.  * NumLines -  Number of lines printed, set by DiagSpArray().        *
  288.  * TotalTrav - Total number of linkages in the Ptree, set by         *
  289.  *             SumSpArray().                                         *
  290.  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  291.  
  292. void DiagSpArray(SPARRAY *this);
  293. /* Diagram the Ptree used by the SPARRAY */
  294.  
  295. void DumpSpArray(SPELEM *this);
  296. /* Dump an ordered listing of the elements of the SPARRAY */
  297.  
  298. void SumSpArray(SPARRAY *Array);
  299. /* Determine various statistics about the Ptree used by the SPARRAY */
  300.  
  301. #endif
  302.  
  303.  
  304.  
  305.  
  306. [LISTING FOUR]
  307.  
  308. /* DIAGARRA.C - Routines for diagraming the Ptree of a SPARRAY */
  309. /* Copyright (C) 1988, Mark C. Peterson */
  310.  
  311. #include <string.h>
  312. #include <stdlib.h>
  313. #include <stdio.h>
  314. #include "DIAGARRA.H"
  315.  
  316. static char String[8000];
  317. unsigned MaxTrav, NumElem, NumTrav, StrLength, NumLines;
  318. unsigned long TotalTrav;
  319.  
  320. static void RecDiagSpArray(SPELEM *this) {
  321.    unsigned NumLength;
  322.  
  323.    NumLength = printf("%ld", this->Loc);
  324.    if(this->Higher) strcat(String, "| ");
  325.    else strcat(String, "  ");
  326.    StrLength += 2;
  327.    memset(String + StrLength, ' ', NumLength);
  328.    StrLength += NumLength;
  329.    String[StrLength] = '\0';
  330.    if(this->Lower) {
  331.       printf("--");
  332.       RecDiagSpArray(this->Lower);
  333.    }
  334.    StrLength -= (NumLength + 2);
  335.    if(this->Higher) {
  336.       printf("\n%s\n", String);
  337.       NumLines++;
  338.       String[StrLength] = '\0';
  339.       printf("%s", String);
  340.       RecDiagSpArray(this->Higher);
  341.    }
  342.    else String[StrLength] = '\0';
  343. }
  344.  
  345. void DiagSpArray(SPARRAY *Array) {
  346.    String[0] = '\0'; 
  347.    NumLines = StrLength = 0;
  348.    if(Array->Root) RecDiagSpArray(Array->Root);
  349.    else printf("<NULL>");
  350. }
  351.  
  352. void DumpSpArray(SPELEM *this) {
  353.    if(this->Lower) DumpSpArray(this->Lower);
  354.    printf("%lu\t", this->Loc);
  355.    if(this->Higher) DumpSpArray(this->Higher);
  356. }
  357.  
  358. static void RecSumSpArray(SPELEM *this) {
  359.    NumElem++;
  360.    if(NumTrav > MaxTrav) MaxTrav = NumTrav;
  361.    TotalTrav += (long)NumTrav;
  362.    if(this->Lower) {
  363.       NumTrav++;
  364.       RecSumSpArray(this->Lower);
  365.       NumTrav--;
  366.    }
  367.    if(this->Higher) {
  368.       NumTrav++;
  369.       RecSumSpArray(this->Higher);
  370.       NumTrav--;
  371.    }
  372. }
  373.  
  374. void SumSpArray(SPARRAY *Array) {
  375.    MaxTrav = NumElem = NumTrav = 0;
  376.    TotalTrav = 0l;
  377.    RecSumSpArray(Array->Root);
  378. }
  379.  
  380.  
  381.  
  382.  
  383. [LISTING FIVE]
  384.  
  385. /* PTREE.C - Program for constructing and diagraming a Ptree */
  386. /* Copyright (C) 1988, Mark C. Peterson */
  387.  
  388. #include <stdio.h>
  389. #include <stdlib.h>
  390. #include "SPARRAY.H"
  391. #include "DIAGARRA.H"
  392.  
  393. #define INPUT_SIZE   15
  394. #define ARRAY_SIZE  100
  395.  
  396. char *InputNum(char *Input, unsigned size) {
  397.    static char PromptStr[] = "\n\nNumber?  ";
  398.  
  399.    printf(PromptStr);
  400.    return(fgets(Input, size, stdin));
  401. }
  402.  
  403. void main(void) {
  404.    char Input[INPUT_SIZE];
  405.    SPARRAY *Array;
  406.    unsigned long Number;
  407.  
  408.    if(Array = MakeSpArray(ARRAY_SIZE)) {
  409.       puts("Enter a number at the prompt.  If it is not in the");
  410.       puts("Ptree it will be added.  If the number is in the");
  411.       puts("Ptree it will be deleted.  To end the program enter a");
  412.       puts("blank line.\n");
  413.  
  414.       while(*InputNum(Input, INPUT_SIZE - 1) != '\n') {
  415.          putchar('\n');
  416.          Number = atol(Input);
  417.          if(FindSpElem(Array, Number)) RemoveSpElem(Array, Number);
  418.          else {
  419.             if(!PlaceSpElem(Array, Number)) {
  420.                puts("Array Full");
  421.                break;
  422.             }
  423.          }
  424.          DiagSpArray(Array);
  425.       }
  426.       DeleteSpArray(&Array);
  427.    }
  428.    else puts("Error making SpArray");
  429. }
  430.  
  431.  
  432.  
  433.  
  434.