· 5 years ago · Sep 26, 2020, 09:54 AM
1//**************************************************************************
2//
3// Peter Huang, Vincent Nguyen
4// CSE 12, Winter 2016
5// March 8, 2016
6// cs12xcd, cs12xeo
7// Assignment Nine
8//
9// File Name: Tree.c
10// Description: This program is an implementation of a binary tree data
11// structure which will be used to allow variable assignment
12// in the Calculator program. Along with automatic Tree
13// balancing, this program implements the binary tree as
14// a binary tree that is written and read from a disk.
15//
16//*************************************************************************/
17
18#include <stdlib.h>
19#include <string.h>
20#include "Tree.h"
21
22// debug messages
23static const char ALLOCATE[] = " - Allocating]\n";
24static const char COST_READ[] = "[Cost Increment (Disk Access): Reading ";
25static const char COST_WRITE[] = "[Cost Increment (Disk Access): Writing ";
26static const char DEALLOCATE[] = " - Deallocating]\n";
27static const char TREE[] = "[Tree ";
28
29template <class Whatever>
30int Tree<Whatever>::debug_on = 0;
31
32template <class Whatever>
33long Tree<Whatever>::cost = 0;
34
35template <class Whatever>
36long Tree<Whatever>::operation = 0;
37
38#ifndef TRUE
39#define TRUE 1
40#endif
41
42#ifndef FALSE
43#define FALSE 0
44#endif
45
46#define THRESHOLD 2
47
48template <class Whatever>
49ostream & operator << (ostream &, const TNode<Whatever> &);
50
51//***************************************************************************
52// struct TNode
53//
54// Data Fields:
55// data - data to be stored in the TNode
56// height - height of TNode
57// balance - balance of TNode
58// left - offset of left TNode in disk
59// right - offset of right TNode in disk
60// this_position - offset of TNode in disk
61//
62// Public functions:
63// TNode Constructors - initializes data fields, add and read TNode
64// to disk
65// Insert - Inserts a TNode into the Tree
66// Lookup - Searches for a TNode in the Tree
67// Read - Read TNode from disk
68// Remove - Removes a TNode from the Tree
69// ReplaceAndRemoveMax - called when removing a TNode with two children,
70// retains Tree structure
71// SetHeightAndBalance - Updates the height and balance of every TNode
72// in the Tree
73// Write - Update TNode to disk
74// Write_AllTNodes - Writes all TNodes in the Tree to stdout
75//**************************************************************************/
76template <class Whatever>
77struct TNode {
78// friends:
79
80// data fields:
81 Whatever data;
82 long height;
83 long balance;
84 offset left;
85 offset right;
86 offset this_position; // current position
87
88// function fields:
89 TNode () : height (0), balance (0), left (0), right (0),
90 this_position (0) {}
91
92 // to declare the working TNode in Tree's Remove
93 TNode (Whatever & element) : data (element), height (0), balance (0),
94 left (0), right (0), this_position (0) {}
95
96 TNode (Whatever &, fstream *, long &); // to add new node to disk
97 TNode (const offset &, fstream *); // to read node from disk
98
99 unsigned long Insert (Whatever &, fstream *, long &, offset &);
100 // optional recursive Lookup declaration would go here
101 unsigned long Lookup (Whatever &, fstream *) const;
102 void Read (const offset &, fstream *); // read node from disk
103 unsigned long Remove (TNode<Whatever> &, fstream *, long &, offset &,
104 long fromSHB = FALSE);
105 void ReplaceAndRemoveMax (TNode<Whatever> &, fstream *, offset &);
106 void SetHeightAndBalance (fstream *, offset &);
107 void Write (fstream *) const; // update node to disk
108
109 ostream & Write_AllTNodes (ostream &, fstream *) const;
110};
111
112template <class Whatever>
113unsigned long Tree<Whatever> :: Insert (Whatever & element)
114/***************************************************************************
115% Routine Name : Tree<Whatever> :: Insert (public)
116% File : Tree.c
117%
118% Description : If the Tree is empty, inserts element as the root TNode.
119% If the Tree is not empty, delegates to TNode's Insert.
120%
121% Parameters descriptions :
122%
123% name description
124% ------------------ ------------------------------------------------------
125% element Data stored in the TNode to be inserted into the Tree.
126% <return> True if successfully inserted, false if not.
127***************************************************************************/
128{
129 long status = false; // True if successfully inserted, false if not
130
131 // If root node does not exist, insert as root node
132 if (occupancy == 0) {
133 TNode<Whatever>(element, fio, occupancy);
134
135 // Update status
136 status = true;
137 }
138
139 // If root node already exists, delegate to TNode's insert
140 else {
141 TNode<Whatever> rootTNode(root, fio);
142 status = rootTNode.Insert(element, fio, occupancy, root);
143 }
144
145 // Increment number of Operations
146 IncrementOperation();
147
148 return status; // True if successful, false if not
149}
150
151template <class Whatever>
152void TNode<Whatever> :: ReplaceAndRemoveMax (TNode<Whatever> & targetTNode,
153 fstream * fio, offset & PositionInParent)
154/**************************************************************************
155% Routine Name : TNode<Whatever> :: ReplaceAndRemoveMax (public)
156% File : Tree.c
157%
158% Description : Called when removing a TNode with 2 children, maintains
159% Tree structure by replacing the targetTNode with the
160% maximum TNode in its left subtree by replacing
161% targetTNode's data
162%
163% Parameters descriptions :
164%
165% name description
166% ------------------ ------------------------------------------------------
167% targetTNode Reference to the TNode to remove.
168% fio Filestream corresponding to the datafile where the
169% Tree is stored on disk.
170% PositionInParent Reference to the TNode position in the parent TNode used
171% to get to the current TNode's offset in the datafile.
172**************************************************************************/
173{
174 // Go all the way right
175 if (right) {
176 TNode<Whatever> readRightNode(right, fio);
177 readRightNode.ReplaceAndRemoveMax(targetTNode, fio, right);
178
179 // Update height and balance
180 SetHeightAndBalance(fio, PositionInParent);
181 }
182
183 // Replace targetTNode with data of maximum TNode on its left subtree
184 else {
185 targetTNode.data = data;
186 PositionInParent = left;
187 }
188}
189
190template <class Whatever>
191unsigned long TNode<Whatever> :: Remove (TNode<Whatever> & elementTNode,
192 fstream * fio, long & occupancy, offset & PositionInParent,
193 long fromSHB)
194/***************************************************************************
195% Routine Name : TNode<Whatever> :: Remove (public)
196% File : Tree.c
197%
198% Description : Removes a TNode with data matching with the data of
199% elementTNode from the Tree.
200%
201% Parameters descriptions :
202%
203% name description
204% ------------------ ------------------------------------------------------
205% elementTNode Reference to the TNode containing the data that
206% identifies the element to remove.
207% fio Filestream corresponding to the datafile where the
208% Tree is stored on disk.
209% occupancy Reference to the occupancy of the tree to wich the
210% new TNode is being added.
211% PositionInParent Reference to the TNode position in the parent TNode used
212% to get to the current TNode's offset in the datafile.
213% fromSHB True if Remove is called from SetHeightAndBalance,
214% false if it is not.
215% <return> True if element is removed, false if not.
216***************************************************************************/
217{
218 long status = false; // Set to true when element is removed
219
220 // If elementTNode's data is equal to current TNode's data, perform
221 // operations to remove current TNode
222 if (elementTNode.data == data) {
223 // Update data of elementTNode
224 elementTNode.data = data;
225
226 // Case for removing leaf TNode
227 if (!left && !right) {
228 PositionInParent = NULL;
229 }
230
231 // Case for removing TNode with only left child
232 else if (!right) {
233 PositionInParent = left;
234 }
235
236 // Case for removing TNode with only right child.
237 else if (!left) {
238 PositionInParent = right;
239 }
240
241 // Case for removing TNode with two children
242 else {
243 TNode<Whatever> readLeftNode(left, fio);
244 readLeftNode.ReplaceAndRemoveMax(*this, fio, left);
245
246 // Update height and balance
247 if(!fromSHB) {
248 SetHeightAndBalance(fio, PositionInParent);
249 }
250
251 // Else write to disk
252 else {
253 Write(fio);
254 }
255 }
256
257 // Decrement occupancy and update status
258 occupancy--;
259 status = true;
260 }
261
262 // Else use recursion to traverse the Tree
263 else {
264 // If elementTNode's data is greater than current data, go right
265 if (right && elementTNode.data > data) {
266 TNode<Whatever> readRightNode (right, fio);
267 status = readRightNode.Remove(elementTNode, fio,
268 occupancy, right, fromSHB);
269 }
270
271 // If elementTNode's data is less than current data, go left
272 if (left && !(elementTNode.data > data)) {
273 TNode<Whatever> readLeftNode(left, fio);
274 status = readLeftNode.Remove(elementTNode, fio,
275 occupancy, left, fromSHB);
276 }
277
278 // Update height and balance
279 if (!fromSHB) {
280 SetHeightAndBalance(fio, PositionInParent);
281 }
282 }
283
284 return status; // True if successfully removed, false if not
285}
286
287template <class Whatever>
288unsigned long Tree<Whatever> :: Remove (Whatever & element)
289/***************************************************************************
290% Routine Name : Tree<Whatever> :: Remove (public)
291% File : Tree.c
292%
293% Description : Removes a TNode with data matching with element from the
294% Tree by delegating to TNode's Remove.
295%
296% Parameters descriptions :
297%
298% name description
299% ------------------ ------------------------------------------------------
300% element The element to remove.
301% <return> True if element is removed, false if not.
302***************************************************************************/
303{
304 long status = false; // Return value of TNode's Remove
305
306 // Able to remove when Tree is not empty
307 if (occupancy > 0) {
308 // Initialize elementTNode and delegate to TNode's Remove
309 TNode<Whatever> elementTNode(element);
310 TNode<Whatever> readRootNode(root, fio);
311 status = readRootNode.Remove(elementTNode, fio, occupancy, root);
312
313 // Reset root if last element is removed
314 if (occupancy == 0) {
315 ResetRoot();
316 }
317
318 // Update element parameter
319 element = elementTNode.data;
320 }
321
322 // Increment number of Operations
323 IncrementOperation();
324
325 return status; // True if successfully removed, false if not
326}
327
328template <class Whatever>
329unsigned long TNode<Whatever> :: Lookup (Whatever & element,
330 fstream * fio) const
331/***************************************************************************
332% Routine Name : TNode<Whatever> :: Lookup (public)
333% File : Tree.c
334%
335% Description : Searches the Tree for element.
336%
337% Parameters descriptions :
338%
339% name description
340% ------------------ ------------------------------------------------------
341% element The element to lookup.
342% fio Filestream corresponding to the datafile where the
343% Tree is stored on disk.
344% <return> True if element is found, false if not.
345***************************************************************************/
346{
347 long status = false; // True if element has been found, false if not
348
349 // Check if element matches the data
350 if (element == data) {
351 element = data;
352 return true;
353 }
354
355 // Element is not in the Tree
356 else if (!right && !left) {
357 return false;
358 }
359
360 // If element is greater than current data, go right
361 else if (right && element > data) {
362 TNode<Whatever> readRightNode(right, fio);
363 status = readRightNode.Lookup(element, fio);
364 }
365
366 // If element is less than current data, go left
367 else if (left && !(element > data)){
368 TNode<Whatever> readLeftNode(left, fio);
369 status = readLeftNode.Lookup(element, fio);
370 }
371
372 return status; //True if element is found, false if not
373}
374
375
376template <class Whatever>
377void TNode<Whatever> :: SetHeightAndBalance (fstream * fio,
378 offset & PositionInParent)
379/***************************************************************************
380% Routine Name : TNode<Whatever> :: SetHeightAndBalance (public)
381% File : Tree.c
382%
383% Description : Updates height and balance of the current TNode.
384%
385% Parameters descriptions :
386%
387% name description
388% ------------------ ------------------------------------------------------
389% fio Filestream corresponding to the datafile where the
390% Tree is stored on disk.
391% PositionInParent Reference to the TNode position in the parent TNode used
392% to get to the current TNode's offset in the datafile.
393***************************************************************************/
394{
395 Whatever this_data = data; // Temporarily store data of current TNode
396 TNode<Whatever> temp_Left, temp_Right; // Declare temporary TNodes for
397 // access to data
398 long fakeOccupancy = 0; // Passed into Remove and Insert
399 long rightHeight, leftHeight; // Saves height of temp TNodes
400
401 // Initialize temporary left TNode if left TNode exists
402 if (left) {
403 TNode<Whatever> temp_Left(left, fio);
404 leftHeight = temp_Left.height;
405 }
406
407 // Initialize temporary right TNode if right TNode exists
408 if (right) {
409 TNode<Whatever> temp_Right(right, fio);
410 rightHeight = temp_Right.height;
411 }
412
413 // Case for leaf node
414 if (!left && !right) {
415 height = 0;
416 balance = 0;
417 }
418
419 // Case for nonexistent right node
420 else if (!right) {
421 height = 1 + leftHeight;
422 balance = leftHeight + 1;
423 }
424
425 // Case for nonexistent left node
426 else if (!left) {
427 height = 1 + rightHeight;
428 balance = -1 - rightHeight;
429 }
430
431 // Case for taller left node
432 else if ( leftHeight > rightHeight) {
433 height = 1 + leftHeight;
434 balance = leftHeight - rightHeight;
435 }
436
437 // Case for taller right node
438 else {
439 height = 1 + rightHeight;
440 balance = leftHeight - rightHeight;
441 }
442
443 // Rebalance the tree if balance exceeds threshold value
444 if (abs(balance) > THRESHOLD) {
445 // Create a TNode with the data to Remove
446 TNode<Whatever> deleteNode(data);
447 Remove(deleteNode, fio, fakeOccupancy, PositionInParent, true);
448
449 // Reinsert the removed TNode
450 TNode<Whatever> reinsertNode(PositionInParent, fio);
451 reinsertNode.Insert(deleteNode.data, fio, fakeOccupancy,
452 PositionInParent);
453 }
454
455 // Write the data if Tree is balanced
456 else {
457 Write(fio);
458 }
459}
460
461template <class Whatever>
462long Tree <Whatever> :: GetCost ()
463/***************************************************************************
464% Routine Name : Tree<Whatever> :: GetCost (public)
465% File : Tree.c
466%
467% Description : Returns the number of times a read or write is performed
468% on the disk (cost).
469%
470% Parameters descriptions :
471%
472% name description
473% ------------------ ------------------------------------------------------
474% <return> Value of the cost variable.
475***************************************************************************/
476{
477 return cost;
478}
479
480template <class Whatever>
481long Tree <Whatever> :: GetOperation ()
482/***************************************************************************
483% Routine Name : Tree<Whatever> :: GetOperation (public)
484% File : Tree.c
485%
486% Description : Returns the number of times a Tree operation occurs.
487%
488% Parameters descriptions :
489%
490% name description
491% ------------------ ------------------------------------------------------
492% <return> Value of the operation variable.
493***************************************************************************/
494{
495 return operation;
496}
497
498template <class Whatever>
499void Tree <Whatever> :: IncrementCost ()
500/***************************************************************************
501% Routine Name : Tree<Whatever> :: IncrementCost (public)
502% File : Tree.c
503%
504% Description : Increments the cost variable of the Tree.
505***************************************************************************/
506{
507 cost++;
508}
509
510template <class Whatever>
511void Tree <Whatever> :: IncrementOperation ()
512/***************************************************************************
513% Routine Name : Tree<Whatever> :: IncrementOperation (public)
514% File : Tree.c
515%
516% Description : Increments the operation variable of the Tree.
517***************************************************************************/
518{
519 operation++;
520}
521
522template <class Whatever>
523void Tree <Whatever> :: Set_Debug_On (void)
524/***************************************************************************
525% Routine Name : Tree<Whatever> :: Set_Debug_On (public)
526% File : Tree.c
527%
528% Description : Sets debug mode on.
529***************************************************************************/
530{
531 debug_on = true;
532}
533
534template <class Whatever>
535void Tree <Whatever> :: Set_Debug_Off (void)
536/***************************************************************************
537% Routine Name : Tree<Whatever> :: Set_Debug_Off (public)
538% File : Tree.c
539%
540% Description : Sets debug mode off.
541***************************************************************************/
542{
543 debug_on = false;
544}
545
546template <class Whatever>
547void Tree <Whatever> :: ResetRoot ()
548/***************************************************************************
549% Routine Name : Tree<Whatever> :: ResetRoot (public)
550% File : Tree.c
551%
552% Description : Resets the root datafield of the Tree to the end of
553% the disk.
554***************************************************************************/
555{
556 // Seek to the end of the disk and reset the root
557 fio->seekp(0,ios::end);
558 root = fio->tellp();
559}
560
561template <class Whatever>
562unsigned long TNode<Whatever> :: Insert (Whatever & element, fstream * fio,
563 long & occupancy, offset & PositionInParent)
564/***************************************************************************
565% Routine Name : TNode<Whatever> :: Insert (public)
566% File : Tree.c
567%
568% Description : Inserts an element into the Tree.
569%
570% Parameters descriptions :
571%
572% name description
573% ------------------ ------------------------------------------------------
574% element Data stored in the TNode to be inserted into the Tree.
575% fio Filestream corresponding to the datafile where the
576% Tree is stored on disk.
577% occupancy Reference to the occupancy of the tree to wich the
578% new TNode is being added.
579% PositionInParent Reference to the TNode position in the parent TNode used
580% to get to the current TNode's offset in the datafile.
581% <return> True if successfully inserted, false if not.
582***************************************************************************/
583{
584 long status = false; // True if element has been inserted, false if not
585
586 // Duplicate insert in the Tree
587 if (element == data) {
588 // Replace existing data with new data and Write to disk
589 data = element;
590 Write(fio);
591
592 return true;
593 }
594
595 // If element is greater than this TNode's data, go right
596 else if (element > data) {
597 // If spot is empty, insert TNode and update loop condition
598 if (!right) {
599 TNode<Whatever> rightNode(element, fio, occupancy);
600 right = rightNode.this_position;
601
602 status = true;
603 }
604
605 // If spot is not empty, go right and search again.
606 else {
607 TNode<Whatever> readRightNode(right, fio);
608 status = readRightNode.Insert(element, fio, occupancy, right);
609 }
610 }
611
612 // Else go left
613 else {
614 // If spot is empty, insert TNode and update loop condition
615 if (!left) {
616 TNode<Whatever> leftNode (element, fio, occupancy);
617 left = leftNode.this_position;
618
619 status = true;
620 }
621
622 // If spot is not empty, go left and search again.
623 else {
624 TNode<Whatever> readLeftNode(left, fio);
625 status = readLeftNode.Insert(element, fio, occupancy, left);
626 }
627 }
628
629 // Update height and balance
630 SetHeightAndBalance(fio, PositionInParent);
631
632 return status; // True if successfully inserted, false if not
633}
634
635template <class Whatever>
636unsigned long Tree<Whatever> :: Lookup (Whatever & element) const
637/***************************************************************************
638% Routine Name : Tree<Whatever> :: Lookup (public)
639% File : Tree.c
640%
641% Description : Delegates to TNode's Lookup to find an element in the Tree.
642%
643% Parameters descriptions :
644%
645% name description
646% ------------------ ------------------------------------------------------
647% element The element to lookup.
648% <return> True if element is found, false if not.
649***************************************************************************/
650{
651 long status = false; // True if element is found, false if not
652
653 // Delegate to TNode's Lookup
654 if (occupancy > 0) {
655 TNode<Whatever> readRootNode(root, fio);
656 status = readRootNode.Lookup(element, fio);
657 }
658
659 // Increment number of Operations
660 IncrementOperation();
661
662 return status; // True if found, false if not
663}
664
665template <class Whatever>
666void TNode<Whatever> :: Read (const offset & position, fstream * fio)
667/***************************************************************************
668% Routine Name : TNode<Whatever> :: Read (public)
669% File : Tree.c
670%
671% Description : Reads a TNode which is present on the datafile into memory.
672%
673% Parameters descriptions :
674%
675% name description
676% ------------------ ------------------------------------------------------
677% position The offset in the datafile corresponding to the
678% position of the TNode we wish to read into memory.
679% fio Filestream corresponding to the datafile where the
680% Tree is stored on disk.
681***************************************************************************/
682{
683 // Seek to position and read TNode at that position
684 fio->seekg(position);
685 fio->read((char *)this, sizeof(TNode<Whatever>));
686
687 // Debug message
688 if (Tree<Whatever>::debug_on) {
689 cerr << COST_READ << (const char *)(data) << "]\n";
690 }
691
692 // Increment Cost
693 Tree<Whatever>::IncrementCost();
694}
695
696template <class Whatever>
697TNode<Whatever> :: TNode (const offset & position, fstream * fio)
698/***************************************************************************
699% Routine Name : TNode<Whatever> :: TNode (public)
700% File : Tree.c
701%
702% Description : Read Constructor that is called when reading a TNode
703% present on disk into memory.
704%
705% Parameters descriptions :
706%
707% name description
708% ------------------ ------------------------------------------------------
709% position The offset in the datafile corresponding to the
710% position of the TNode we wish to read into memory.
711% fio Filestream corresponding to the datafile where the
712% Tree is stored on disk.
713***************************************************************************/
714{
715 // Call Read function to read the TNode at position
716 TNode :: Read(position, fio);
717}
718
719template <class Whatever>
720TNode<Whatever> :: TNode (Whatever & element, fstream * fio, long & occupancy):
721 data (element), height (0), balance (0), left (0),
722 right (0)
723/***************************************************************************
724% Routine Name : TNode<Whatever> :: TNode (public)
725% File : Tree.c
726%
727% Description : Write Constructor that is called when creating a TNode
728% for the first time.
729% Parameters descriptions :
730%
731% name description
732% ------------------ ------------------------------------------------------
733% element Data stored in the TNode to be inserted into the Tree.
734% fio Filestream corresponding to the datafile where the
735% Tree is stored on disk.
736% occupancy Reference to the occupancy of the tree to wich the
737% new TNode is being added.
738***************************************************************************/
739{
740 // Seek to the end of the file and set this_position
741 fio->seekp(0,ios::end);
742 this_position = fio->tellp();
743
744 // Call Write function to write the TNode
745 TNode :: Write(fio);
746
747 // Increment the occupancy of the Tree
748 occupancy++;
749}
750
751template <class Whatever>
752void TNode<Whatever> :: Write (fstream * fio) const
753/***************************************************************************
754% Routine Name : TNode<Whatever> :: Write (public)
755% File : Tree.c
756%
757% Description : Writes this TNode object to disk at this_position in
758% the datafile.
759%
760% Parameters descriptions :
761%
762% name description
763% ------------------ ------------------------------------------------------
764% fio Filestream corresponding to the datafile where the
765% Tree is stored on disk.
766***************************************************************************/
767{
768 // Seek to this_position and write the TNode to disk
769 fio->seekp(this_position);
770 fio->write((const char *)this, sizeof(TNode<Whatever>));
771
772 // Debug message
773 if (Tree<Whatever>::debug_on) {
774 cerr << COST_WRITE << (const char *)(data) << "]\n";
775 }
776
777 // Increment Cost
778 Tree<Whatever>::IncrementCost();
779}
780
781template <class Whatever>
782Tree<Whatever> :: Tree (const char * datafile) :
783 fio (new fstream (datafile, ios :: out | ios :: in)),
784 occupancy(0), root(0)
785/***************************************************************************
786% Routine Name : Tree<Whatever> :: Tree (public)
787% File : Tree.c
788%
789% Description : Allocates the Tree object and checks the datafile to see
790% if it contains Tree data. If data exists in the datafile,
791% root and occupancy fields are written into memory.
792%
793% Parameters descriptions :
794%
795% name description
796% ------------------ ------------------------------------------------------
797% datafile The file that contains the data in which the Tree
798% Reads from or Writes to.
799***************************************************************************/
800{
801 offset beginning, ending; // Position of beginning and end of the datafile
802 static long counter; // Keeps track of the number of Trees
803 tree_count = ++counter; // Set Tree Number
804
805 // Seek to beginning of datafile
806 fio->seekp(0, ios::beg);
807 beginning = fio->tellp();
808
809 // Seek to end of datafile
810 fio->seekp(0, ios::end);
811 ending = fio->tellp();
812
813 // Check for empty file
814 if (beginning == ending) {
815 // Reserve space for root and occupancy
816 fio->seekp(0, ios::beg);
817 fio->write((const char *)&root, sizeof(root));
818 fio->write((const char *)&occupancy, sizeof(occupancy));
819 root = fio->tellp();
820 }
821
822 // Else if not empty, read root and occupancy from file
823 else {
824 fio->seekg(0, ios::beg);
825 fio->read((char *)&root, sizeof(root));
826 fio->read((char *)&occupancy, sizeof(occupancy));
827 }
828
829 // Debug message
830 if (debug_on) {
831 cerr << TREE << tree_count << ALLOCATE;
832 }
833}
834
835template <class Whatever>
836Tree<Whatever> :: ~Tree (void)
837/***************************************************************************
838% Routine Name : Tree :: ~Tree (public)
839% File : Tree.c
840%
841% Description : Deallocates memory associated with the Tree. It
842% will also delete all the memory of the elements within
843% the table.
844***************************************************************************/
845
846{
847 // Write root and occupancy to the datafile
848 fio->seekp(0, ios::beg);
849 fio->write((const char *)&root, sizeof(root));
850 fio->write((const char *)&occupancy, sizeof(occupancy));
851
852 // Deallocate memory associated with fio
853 delete fio;
854
855 // Debug message
856 if (debug_on) {
857 cerr << TREE << tree_count << DEALLOCATE;
858 }
859}
860
861template <class Whatever>
862ostream & operator << (ostream & stream, const TNode<Whatever> & nnn) {
863 stream << "at height: :" << nnn.height << " with balance: "
864 << nnn.balance << " ";
865 return stream << nnn.data << "\n";
866}
867
868template <class Whatever>
869ostream & Tree<Whatever> :: Write (ostream & stream) const
870/***************************************************************************
871% Routine Name : Tree :: Write (public)
872% File : Tree.c
873%
874% Description : This funtion will output the contents of the Tree table
875% to the stream specificed by the caller. The stream could be
876% cerr, cout, or any other valid stream.
877%
878% Parameters descriptions :
879%
880% name description
881% ------------------ ------------------------------------------------------
882% stream A reference to the output stream.
883% <return> A reference to the output stream.
884***************************************************************************/
885
886{
887 long old_cost = cost;
888
889 stream << "Tree " << tree_count << ":\n"
890 << "occupancy is " << occupancy << " elements.\n";
891
892 fio->seekg (0, ios :: end);
893 offset end = fio->tellg ();
894
895 // check for new file
896 if (root != end) {
897 TNode<Whatever> readRootNode (root, fio);
898 readRootNode.Write_AllTNodes (stream, fio);
899 }
900
901 // ignore cost when displaying nodes to users
902 cost = old_cost;
903
904 return stream;
905}
906
907template <class Whatever>
908ostream & TNode<Whatever> ::
909Write_AllTNodes (ostream & stream, fstream * fio) const {
910 if (left) {
911 TNode<Whatever> readLeftNode (left, fio);
912 readLeftNode.Write_AllTNodes (stream, fio);
913 }
914 stream << *this;
915 if (right) {
916 TNode<Whatever> readRightNode (right, fio);
917 readRightNode.Write_AllTNodes (stream, fio);
918 }
919
920 return stream;
921}