Mark Peterson is a contract computer programmer in the Hartford, Conn.-area. He can be reached by calling 203-754-1162, or on CompuServe at 70441,3353.
Programmers now bask in the luxury of huge expanses of computer memory. To take full advantage of the situation, they need high-speed algorithms capable of managing random access to correspondingly huge amounts of data. One solution involves the use of binary trees (B-trees) or some extension such as B+ trees. Another solution that I prefer, the precedence tree (Ptree), is both simple and elegant.
Traditional methods of B-tree construction tend to degenerate into linear lists or other unbalanced states. There are routines for balancing a B-tree, but they are often time-consuming, at times having to traverse through every element in the tree. In addition, these routines tend to be code intensive. One reason is the many different tree configurations possible for the same set of numbers (see Figure 1). The final configuration is dependent upon the order in which the numbers are entered. And as you'll soon see, inefficiencies are created by this order of entry.
In addition to the Ptree, this article explores the use of pointer references to create elegant code. The majority of code for the article is contained in five listings. SPARRAY (see Listings One and Two) constructs and maintains a sparse array utilizing a Ptree. DIAGARRA (see Listings Three and Four) diagrams the Ptree of the sparse array and provides statistics. PTREE.C (see Listing Five) inserts numbers into and deletes them from a Ptree and utilizes DIAGARRA to observe the different configurations. All code is written in ANSI standard C.
The Ptree builds an ordered B-tree in such a way that only one configuration is possible for a given set of numbers. This is done by either placing numbers in the middle of an existing tree or as a new leaf to create a tree. This technique resolves inefficiencies due to order of entry and creates a configuration that is always reasonably balanced. Furthermore, these trees tend to become more balanced as more numbers are entered.
The entry of sequential lists of numbers, which creates a linear list using traditional methods, instead creates a perfectly balanced B-tree using techniques of precedence. Also, a Ptree uses only one chain of traversals from the root to a given leaf for placement of a new number in the tree. Removal of an old number is accomplished with a single pass through the Ptree along two chains without recursion. Highspeed construction with a tendency toward perfect balance means a lightning-fast algorithm.
One problem with ordered B-trees is the many different possible states for a given set of numbers. The reason is that traditional binary-tree implementations only place new numbers as additional leaves. This produces configurations that vary depending upon the order in which the numbers are entered (see Figure 1). Note that most of the configurations in Figure 1 are not balanced. Therefore, if construction of the tree is left to chance, which is the traditional method, the odds of ending up with an efficient tree are not good.
The net result is that efficiency liabilities created by the order of entry are additive and never resolved without balancing the tree. For example, if the first numbers entered form a linear list, such as 0, 1, 2, and 3, all successive searches and placements must first traverse this list (see Figure 2).
An ordered B-tree containing all possible numbers for a given number of bits is referred to as a full B-tree. Only two configurations are perfectly balanced for a full 4-bit B-tree. One configuration is shown in Figure 3; the other is the trivial exchange of 1 and 0.
A close look at the bit patterns shows a convergence, meaning that a traversal in the proper direction on a binary search results in a number with a bit pattern more closely resembling the number being sought. In this case, this is a leading convergence where the matching of bit patterns occurs from the most significant bit to the least. B-trees configured with the matching bit pattern occurring from the least significant bit to the most (a lagging convergence) cannot be ordered. Diagraming the tree so that lower numbers are to the right and higher numbers are down not only makes it easier to see this leading convergence but is also easier to implement.
Note that the numbers closer to the root contain more factors of 2 than those that are further away. This point is key to the Ptree algorithm. The Ptree algorithm compares the number being placed with the number in the current position, using the factors of 2 to determine which has precedence (that is, which should be positioned closer to the root). The number with the greater factors of 2 has higher precedence. If the two numbers initially have the same factors of 2, they are bit-shifted to the right until one has more or becomes 0. By definition, 0If the two numbers initially have the same factors of 2, they are bit-shifted to the right until one has more or becomes 0. has the lowest precedence. As an example, Figure 4 compares the precedence of the numbers 11 and 15. Because 11 has more factors of 2 (after bit shifting), it has precedence over 15. Figure 4 also compares the numbers 12 and 28. Because 12 bit-shifts to 0 before 28 does, it has precedence over 28.
11 = 1011, 15 = 1111 (each has no factors of 2)
5 = 0101, 7 = 0111 (each has no factors of 2)
2 = 1001, 15 = 0011 (2 has one factor, 3 has none)
--------------------------------------------------------
12 = 01100, 28 = 11100 (each has two factors of 2)
6 = 00110, 14 = 01110 (each has one factor of 2)
3 = 00011, 7 = 00111 (each has no factors of 2)
1 = 00001, 3 = 00011 (each has no factors of 2)
0 = 00000, 1 = 00001
This added dimension of precedence checking creates a B-tree that is "rigid" (Figure 5) with only one possible configuration for a given set of numbers. This configuration is always reasonably balanced.
When I say "reasonably balanced," I mean that the Ptree algorithm strikes a compromise between perfection and practicality. Keeping a tree perfectly balanced ensures the fastest search time but requires a great deal of trouble to maintain. Ignoring balance invites rampant linear listing. The compromise produces a reasonable balance.
There is some listing for certain sets of numbers that are separated by orders of 2 -- for example the numbers 0, 1, 3, 5, 9, 17, 33, 65, and so on, form a linear list. The maximum length of this linear list is dependent on the largest number capable of being entered into the tree. That is, if the tree can hold only 32-bit numbers, the maximum length of any linear list is 32. This, however, is a very fragile state because entered numbers not conforming to this pattern break down the list into a more balanced state.
A quick algorithm for comparing the factors of 2 in a pair of numbers is to XOR each number with itself minus 1 and compare the results (see Chk-PrecGT( ) in Listing Two). Subtracting 1 from a number turns all the trailing binary 0s(the factors of 2) to 1s and the least significant binary 1 to a 0, leaving the rest of the binary digits untouched. When this result is exclusively-OREd with the original number, all the unchanged leading binary digits become 0s, leaving a result that is representative of the factors of 2.
The (x - 1) ^ x representative numbers shown in Figure 6 can then be compared to see which x has more factors of 2. The expression 0- 1 is undefined because the numbers involved are whole numbers (positive integers) and therefore the calculated (x- 1) ^ x of 0 is 0 by definition.
The definition of a Ptree states that all numbers either greater or less than a given number will have a lower precedence. This means that putting a number in the Ptree usually requires placement somewhere in the middle of the tree rather than at the end by adding another leaf. This requires that the Ptree be "normalized" after insertions and deletions. To demonstrate, consider the insertion of the value 64 into the Ptree in Figure 7. Because 64 contains five factors of 2 and 108 (the root value) only contains two such factors, 64 has a higher precedence and should therefore be the new root.
After linking 108 to the left side of 64, the tree is no longer ordered because several numbers on the "greater" side of 64 are actually less (Figure 8). These lesser numbers must be "pruned" away from the left side of the tree and relinked to the right side.
Traversals are made through the tree using PruneLower( ) and PruneHigher( ). Because 108 was linked to the "higher" (left) side of 64, PruneLower( ) is called first. If the new linkage had been made to the "lower" (right) side of 64, PruneHigher( ) would have been called first. PruneLower( ) traverses along the lower linkages until it reaches a section that is less than the reference value 64. PruneLower( ) breaks this linkage and makes a call to PruneHigher( ). PruneHigher( ) traverses along the higher linkages of this section of lower numbers until it reaches a section greater than 64. It breaks that linkage and makes a call to PruneLower( ). This process continues until a leaf is reached. Prior to return from the recursion, the Ptree is divided into sections of numbers higher and lower than 64. The return from the recursion relinks these sections to their proper locations to create an ordered B-tree (see Figure 9).
As shown in Figure 10, the removal of 64 from the Ptree creates a hole that must be filled. The removal effectively leaves two sets of numbers corresponding to the left and right sides of the tree. In essence, there are two subtrees: one with values greater than 64 and another with values less than 64. The two sections need to be joined along an interface line, as shown in Figure 11. A number on the interface line from the greater section is compared with one on the interface line of the lower section and linked according to precedence. Linkages unrelated to the interface line are unaffected. The result is the original Ptree configuration (see Figure 7. The use of pointer references allows this to be done as a single, iterative-style pass through the Ptree without recursion.
The SPARRAY structure (Listing Two) is a sparse array that handles elements up to the limit of unsigned long. For most compilers this equates to an addressing capability of 4,294,967,296 locations. SPARRAY uses a Ptree to manage the elements in the sparse array.
MakeSpArray( ) and DeleteSpArray( ) are used to allocate memory dynamically. MakeSpArray( ) returns a null pointer if there is insufficient memory, and DeleteSpArray( ) sets the pointer referenced by RefPtr to NULL to prevent further usage of the memory space after deletion.
FindSpElem( ) is a standard binary search routine that returns a null pointer if the element is not found. The function reads:
The next section uses a binary search similar to FindSpElem( ) with two exceptions: a check is made for precedence, and this is a pointer reference rather than a pointer. The use of a pointer reference (as opposed to a pointer) allows setting the new linkage based on previous events. In other words, the linkage can be set "in context" rather than explicitly checking the new linkage to see if it is a higher, lower, or a new root pointer. The algorithm reads as follows:
RemoveSpElem( ) first sets the pointer reference this to the linkage pointing to the element to be removed by starting at the root and performing a binary search. The use of the pointer reference again allows for removal of either higher, lower, or the root linkage without explicit code. If the element is not found, a null pointer is returned; otherwise, the hole in the Ptree is filled. There are, in this case, only four possible linkages:
Of these four cases, there are only two variables in contention: Higher Inter->Lower and LowerInter->Higher.
To further illustrate the linkages, consider Figure 11. Here, Hole is set to 64, HigherInter to the number on the higher side of 64 (in this case, 108), and LowerInter to the number on the lower side of 64 (46), and the reference pointer to this is set to whatever was pointing to 64 (in this case, Array->Root). The values 46 and 108 are compared, and because 108 has the higher precedence, the pointer to 64 (Array->Root) is now set to 108, this is set to the address of the lower side of 108 (82), and Higher is set to 82. Then, 82 and 46 are compared, and because 82 has precedence, the pointer referenced by this maintains the original linkage. In other words:
since: this = &HigherInter->Lower and: HigherInter = HigherInter->Lower then: *this = HigherInter means: HigherInter->Lower = HigherInter->Lower
Next, 73 is compared to 46, and because 46 has precedence, the pointer referenced by this is set to 46. This links 46 to the lower side of 82. The pointer reference this is now set to the address of LowerInter->Higher, and LowerInter is set to LowerInter->Higher (62). The process continues until either LowerInter or HigherInter is set to a null pointer and the final linkage made accordingly. The last part of the routine links Hole into the beginning of the chain of empty elements and updates the number of elements used.
Listing Two contains routines for diagraming the Ptree and providing statistics. Listing Three has the user program for manually entering and deleting numbers from the Ptree and observing the configuration.
The Ptree algorithm rapidly constructs ordered B-tree configurations that are always reasonably balanced by striking a winning compromise between perfection and practicality. In this scenario, linear listing is virtually nonexistent. Sequential entry, which results in a linear list using standard B-tree construction methods, produces perfectly balanced trees using the Ptree algorithm. Although the code in this article is written for a sparse array, the Ptree algorithm can easily be applied to any application requiring an ordered B-tree.
All source code for articles in this issue is available on a single disk. To order, send $14.95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063; or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue number and format (MS-DOS, Macintosh, Kaypro).
_SETTING PRECEDENCE_
by Mark C. Peterson
[LISTING ONE]
</entry>
Copyright © 1989, Dr. Dobb's Journal
/* SPARRAY.H - Header file for SPARRAY.C */
/* Copyright (C) 1988, Mark C. Peterson */
#ifndef SPARRAY_H
#define SPARRAY_H
union VARIABLE {
long Num;
void *Ptr;
};
typedef struct _SPELEM {
struct _SPELEM *Higher, *Lower;
unsigned long Loc;
union VARIABLE Element;
} SPELEM;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Loc The location of the element within the sparse array. *
* Higher A pointer to a SPELEM with a higher "Loc" of a lower *
* precedence. *
* Lower A pointer to a SPELEM with a lower "Loc" of a lower *
* precedence. *
* Element A union VARIABLE for storage of either a "long" or "void*" *
* element. "Element" is initialize to a NULL (either 0L or *
* (void*)0) by MakeSpArray() or when an element is removed by *
* RemoveSpElem(). *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
typedef struct _SPARRAY {
SPELEM *SpElem, *Root, *EmptyElem;
unsigned Size, ElemUsed, HighestUsed;
} SPARRAY;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* SpElem An array of SPELEM structures. The number of SPELEM *
* structures in the array is stored in "Size". *
* Root A pointer to an SPELEM structure that is the root to the *
* Ptree. *
* EmptyElem A pointer to a chain of SPELEM structures (along the *
* "Higher" pointer) that has been removed from the sparse *
* array. *
* Size The number of SPELEM structures in SpElem array. *
* ElemUsed Keeps track of the number of elements in the sparse array. *
* "ElemUsed" should be checked by the programmer periodically *
* to see if the sparse array is full (i.e "ElemUsed" == *
* "Size"). *
* HighestUsed Used by PlaceElement(). If there are no empty elements *
* ("EmptyElem" == NULL) and "HighestUsed" == "Size" the *
* function returns a NULL. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* Note that the only variable that should be changed directly by the *
* programmer is the "Element" member in the SPELEM structure. *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
SPARRAY *MakeSpArray(unsigned NumElem);
/* Creates the SPARRAY structure with "NumElem" number of elements,
initializes all the elements to zero, and returns a pointer to the
SPARRAY structure. */
SPELEM *FindSpElem(SPARRAY *Array, unsigned long Loc);
/* Returns a pointer to the SPELEM structure associated with "Loc".
if "Loc" is not in the sparse array the function returns a NULL. */
SPELEM *PlaceSpElem(SPARRAY *Array, unsigned long Loc);
/* Places the "Loc" in the Ptree structure. Returns a NULL if the sparse
array is full.
WARNING: This function should only be called if FindElement() returns
a NULL. Attempts to place a "Loc" that is already there will corrupt
the Ptree. */
SPELEM *SpArray(SPARRAY *Array, unsigned long Loc);
/* Attempts to locate "Loc" using FindElement(). If not found the "Loc"
is placed using PlaceElement(). Returns a NULL if "Loc" is not found
and the sparse array is full. */
void ClrSpArray(SPARRAY *Array);
/* Removes all the elements from the sparse array. */
void DeleteSpArray(SPARRAY **ArrayRef);
/* Frees the memory allocated by MakeSpArray and sets the SPARRAY pointer
referenced by ArrayRef to NULL. */
void RemoveSpElem(SPARRAY *Array, unsigned long Loc);
/* Removes "Loc" from the sparse array. */
#endif
[LISTING TWO]
/* SPARRAY.C - Routines for maintaining a sparse array using a Ptree */
/* Copyright (C) 1988, Mark C. Peterson */
#include <stdlib.h>
#include "SPARRAY.H"
static SPELEM
*PruneLower(SPELEM *this, unsigned long Loc),
*PruneHigher(SPELEM *this, unsigned long Loc);
static unsigned
ChkPrecGT(unsigned long Loc, unsigned long ThisLoc);
/* Check "Loc" precedence greater than "ThisLoc" precedence. */
SPARRAY *MakeSpArray(unsigned NumElem) {
SPARRAY *Array;
if(Array = calloc(1, sizeof(SPARRAY))) {
Array->Size = NumElem;
if(!(Array->SpElem = (SPELEM*)calloc(NumElem, sizeof(SPELEM)))) {
free(Array);
Array = (SPARRAY*)0;
}
}
return(Array);
}
static SPELEM *PruneLower(SPELEM *this, unsigned long Loc) {
SPELEM *RetPtr;
while(this->Lower && (this->Lower->Loc > Loc)) this = this->Lower;
if(RetPtr = this->Lower) this->Lower = PruneHigher(this->Lower, Loc);
return(RetPtr);
}
static SPELEM *PruneHigher(SPELEM *this, unsigned long Loc) {
SPELEM *RetPtr;
while(this->Higher && (this->Higher->Loc < Loc))
this = this->Higher;
if(RetPtr = this->Higher) this->Higher = PruneLower(this->Higher, Loc);
return(RetPtr);
}
static unsigned ChkPrecGT(unsigned long Loc, unsigned long ThisLoc) {
unsigned long LocPrec, ThisPrec;
while(Loc && ThisLoc) {
LocPrec = (Loc - 1) ^ Loc;
ThisPrec = (ThisLoc - 1) ^ ThisLoc;
if(LocPrec != ThisPrec) return(LocPrec > ThisPrec);
Loc >>= 1;
ThisLoc >>= 1;
}
return(Loc > ThisLoc);
}
SPELEM *PlaceSpElem(SPARRAY *Array, unsigned long Loc) {
SPELEM **this, *New;
/* This section sets up a "New" SPELEM pointer */
if(!Array->EmptyElem) {
if(Array->HighestUsed < Array->Size)
New = &Array->SpElem[Array->HighestUsed++];
else return((SPELEM*)0);
}
else {
New = Array->EmptyElem;
Array->EmptyElem = Array->EmptyElem->Higher;
}
Array->ElemUsed++;
New->Higher = New->Lower = (SPELEM*)0;
New->Loc = Loc;
/* This section places the "New" SPELEM pointer into the Ptree */
this = &Array->Root;
while(*this) {
if(ChkPrecGT(Loc, (*this)->Loc)) {
if((*this)->Loc > Loc) {
New->Higher = *this;
New->Lower = PruneLower(*this, Loc);
}
else {
New->Lower = *this;
New->Higher = PruneHigher(*this, Loc);
}
break;
}
else this = (*this)->Loc > Loc ? &(*this)->Lower : &(*this)->Higher;
}
*this = New;
return(*this);
}
void RemoveSpElem(SPARRAY *Array, unsigned long Loc) {
SPELEM *Hole, *HigherInter, *LowerInter, **this;
/* Find the element to be removed */
this = &Array->Root;
while(*this && ((*this)->Loc != Loc))
this = (*this)->Loc > Loc ? &(*this)->Lower : &(*this)->Higher;
if(Hole = *this) {
/* Fill the hole in the Ptree if the element was found */
LowerInter = Hole->Lower; /* Lower Interface Pointer */
HigherInter = Hole->Higher; /* Higher Interface Pointer */
while(LowerInter && HigherInter) {
if(ChkPrecGT(LowerInter->Loc, HigherInter->Loc)) {
*this = LowerInter;
this = &LowerInter->Higher;
LowerInter = LowerInter->Higher;
}
else {
*this = HigherInter;
this = &HigherInter->Lower;
HigherInter = HigherInter->Lower;
}
}
if(LowerInter) *this = LowerInter;
else *this = HigherInter;
/* Link the unused spot into the chain of empty elements along
the "Higher" linkage. */
Hole->Higher = Array->EmptyElem;
Array->EmptyElem = Hole;
Array->ElemUsed--; /* Update the number of elements used */
}
}
SPELEM *FindSpElem(SPARRAY *Array, unsigned long Loc) {
SPELEM *this;
this = Array->Root;
while(this && (this->Loc != Loc))
this = this->Loc > Loc ? this->Lower : this->Higher;
return(this);
}
SPELEM *SpArray(SPARRAY *Array, unsigned long Loc) {
SPELEM *Found;
Found = FindSpElem(Array, Loc);
if(!Found)
Found = PlaceSpElem(Array, Loc);
return(Found);
}
void ClrSpArray(SPARRAY *Array) {
unsigned n;
Array->EmptyElem = Array->Root = (SPELEM*)0;
for(n = 0; n < Array->Size; n++)
Array->SpElem[n].Element.Num = 0L;
Array->HighestUsed = Array->ElemUsed = 0;
}
void DeleteSpArray(SPARRAY **ArrayRef) {
SPARRAY *Array;
if(Array = *ArrayRef) {
free(Array->SpElem);
free(Array);
*ArrayRef = (SPARRAY*)0;
}
}
[LISTING THREE]
/* DIAGARRA.H - Header file for DIAGARRA.C */
/* Copyright (C) 1988, Mark C. Peterson */
#ifndef DIAGARRA_H
#define DIAGARRA_H
#include "SPARRAY.H"
extern unsigned MaxTrav, NumElem, NumLines;
extern unsigned long TotalTrav;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* MaxTrav - Maximum number of traversals from the root to any *
* number in the Ptree, set by SumSpArray(). *
* NumElem - Number of elements in the Ptree, set by SumSpArray(). *
* NumLines - Number of lines printed, set by DiagSpArray(). *
* TotalTrav - Total number of linkages in the Ptree, set by *
* SumSpArray(). *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void DiagSpArray(SPARRAY *this);
/* Diagram the Ptree used by the SPARRAY */
void DumpSpArray(SPELEM *this);
/* Dump an ordered listing of the elements of the SPARRAY */
void SumSpArray(SPARRAY *Array);
/* Determine various statistics about the Ptree used by the SPARRAY */
#endif
[LISTING FOUR]
/* DIAGARRA.C - Routines for diagraming the Ptree of a SPARRAY */
/* Copyright (C) 1988, Mark C. Peterson */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "DIAGARRA.H"
static char String[8000];
unsigned MaxTrav, NumElem, NumTrav, StrLength, NumLines;
unsigned long TotalTrav;
static void RecDiagSpArray(SPELEM *this) {
unsigned NumLength;
NumLength = printf("%ld", this->Loc);
if(this->Higher) strcat(String, "| ");
else strcat(String, " ");
StrLength += 2;
memset(String + StrLength, ' ', NumLength);
StrLength += NumLength;
String[StrLength] = '\0';
if(this->Lower) {
printf("--");
RecDiagSpArray(this->Lower);
}
StrLength -= (NumLength + 2);
if(this->Higher) {
printf("\n%s\n", String);
NumLines++;
String[StrLength] = '\0';
printf("%s", String);
RecDiagSpArray(this->Higher);
}
else String[StrLength] = '\0';
}
void DiagSpArray(SPARRAY *Array) {
String[0] = '\0';
NumLines = StrLength = 0;
if(Array->Root) RecDiagSpArray(Array->Root);
else printf("<NULL>");
}
void DumpSpArray(SPELEM *this) {
if(this->Lower) DumpSpArray(this->Lower);
printf("%lu\t", this->Loc);
if(this->Higher) DumpSpArray(this->Higher);
}
static void RecSumSpArray(SPELEM *this) {
NumElem++;
if(NumTrav > MaxTrav) MaxTrav = NumTrav;
TotalTrav += (long)NumTrav;
if(this->Lower) {
NumTrav++;
RecSumSpArray(this->Lower);
NumTrav--;
}
if(this->Higher) {
NumTrav++;
RecSumSpArray(this->Higher);
NumTrav--;
}
}
void SumSpArray(SPARRAY *Array) {
MaxTrav = NumElem = NumTrav = 0;
TotalTrav = 0l;
RecSumSpArray(Array->Root);
}
[LISTING FIVE]
/* PTREE.C - Program for constructing and diagraming a Ptree */
/* Copyright (C) 1988, Mark C. Peterson */
#include <stdio.h>
#include <stdlib.h>
#include "SPARRAY.H"
#include "DIAGARRA.H"
#define INPUT_SIZE 15
#define ARRAY_SIZE 100
char *InputNum(char *Input, unsigned size) {
static char PromptStr[] = "\n\nNumber? ";
printf(PromptStr);
return(fgets(Input, size, stdin));
}
void main(void) {
char Input[INPUT_SIZE];
SPARRAY *Array;
unsigned long Number;
if(Array = MakeSpArray(ARRAY_SIZE)) {
puts("Enter a number at the prompt. If it is not in the");
puts("Ptree it will be added. If the number is in the");
puts("Ptree it will be deleted. To end the program enter a");
puts("blank line.\n");
while(*InputNum(Input, INPUT_SIZE - 1) != '\n') {
putchar('\n');
Number = atol(Input);
if(FindSpElem(Array, Number)) RemoveSpElem(Array, Number);
else {
if(!PlaceSpElem(Array, Number)) {
puts("Array Full");
break;
}
}
DiagSpArray(Array);
}
DeleteSpArray(&Array);
}
else puts("Error making SpArray");
}