CS计算机代考程序代写 #+TITLE: Problem 3 treeset_main application

#+TITLE: Problem 3 treeset_main application
# Set defaults including to use Valgrind off the bat for all tests.
#+TESTY: PREFIX=”prob3″
#+TESTY: PROGRAM=’./treeset_main -echo’
#+TESTY: PROMPT=’TS#>’
#+TESTY: USE_VALGRIND=1

* Start, Print, Quit
Starts the program, prints what should be an empty set, then issues
the quit command which should end the program

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> print
TS#> quit
#+END_SRC

* Check for End of Input
Checks that the main() loop detects EOF when scanning typed input and
exits. When working interactively in a Unix terminal typing Ctrl-d
(Control “d”) will indicate the end of input. When piping a script in
this happens automatically. If this test fails, ensure main() is
looking for EOF on scanf()/fscanf() calls and exits when detected.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> print
#+TESTY_EOF:
TS#>
#+END_SRC

* Find in Empty Tree
Checks presence of the ‘find’ command and that it correctly indicates
nothing is contained in the empty tree.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> print
TS#> find apple
NOT FOUND
TS#> find banana
NOT FOUND
TS#> quit
#+END_SRC

* Add Single Item
Adds a single item to the tree and checks that it is present while
other items are not found.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> print
TS#> add apple
TS#> find apple
FOUND
TS#> print
apple
TS#> find banana
NOT FOUND
TS#> quit
#+END_SRC

* Add Duplicate
Adds a single item to the tree then checks that adding it again will
report a duplicate and leave the tree unchanged. Valgrind will verify
that no memory is lost during this process.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> print
TS#> add apple
TS#> find apple
FOUND
TS#> add apple
duplicate element ignored
TS#> print
apple
TS#> add apple
duplicate element ignored
TS#> print
apple
TS#> find banana
NOT FOUND
TS#> quit
#+END_SRC

* Size Command
Checks that the ‘size’ command is present and reports the correct
number of nodes for size 0 and 1 trees.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> size
0 nodes
TS#> add Cartman
TS#> size
1 nodes
TS#> print
Cartman
TS#> quit
#+END_SRC

* Three Items and Preorder
Adds three items and ensures that the preorder command is present
and shows correct tree structure.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> size
2 nodes
TS#> add Cartman
TS#> size
3 nodes
TS#> print

Cartman
TS#> preorder

S#> find OUND
TS#> find OT FOUND
TS#> find OUND
TS#> find Cartman
FOUND
TS#> find Token
NOT FOUND
TS#> quit
#+END_SRC

* Three Items Alt Order
Adds three items again but in an alternate order and tests proper tree
structure for it. Tests ‘find’ on several items that are present / not
present in the tree.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> print

Cartman
TS#> size
3 nodes
TS#> find OUND
TS#> find OUND
TS#> find Cartman
FOUND
TS#> find OT FOUND
TS#> find Mr OT FOUND
TS#>
#+END_SRC

* Three Items Check Duplicates
Adds several items with duplicate detection at each step.
#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Stan
duplicate element ignored
TS#> add Kyle
duplicate element ignored
TS#> add Cartman
TS#> print

Cartman
TS#> add Cartman
duplicate element ignored
TS#>
#+END_SRC

* Add Lots
Adds a variety of items to the tree and checks that the tree structure
prints correctly via the ‘print’ and ‘preorder’ commands. Also tests
‘find’ for correct behavior.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> find OT FOUND
TS#> find OUND
TS#> print

Cartman
TS#> preorder

S#> add S#> add S#> add Token
TS#> add S#> add Mr S#> size
8 nodes
TS#> find OUND
TS#> find OUND
TS#> find Cartman
FOUND
TS#> find MrHat
NOT FOUND
TS#> find MrStick
NOT FOUND
TS#> print

S#> preorder

S#> add MrHat
TS#> add MrStick
TS#> size
10 nodes
TS#> print

Stick
MrHat
Mr

S#> preorder

Hat
MrStick
Token
S#> quit
#+END_SRC

* Lots Duplicate Checks
Adds a variety of items to the tree and checks that subsequent
duplicate adds do not change the tree structure.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> add S#> add S#> add Token
TS#> add S#> add Mr S#> size
8 nodes
TS#> add Kenny
duplicate element ignored
TS#> add Wendy
duplicate element ignored
TS#> size
8 nodes
TS#> add Cartman
duplicate element ignored
TS#> add Butters
duplicate element ignored
TS#> add Token
duplicate element ignored
TS#> add Token
duplicate element ignored
TS#> print

S#> preorder

S#> add MrHat
TS#> add MrHat
duplicate element ignored
TS#> size
9 nodes
TS#> add MrStick
TS#> add MrStick
duplicate element ignored
TS#> size
10 nodes
TS#> print

Stick
MrHat
Mr

S#> preorder

Hat
MrStick
Token
S#> quit
#+END_SRC

* Add and Clear
Adds some items then uses the ‘clear’ command to empty out the
tree. Proceeds to add more items. Tests whether nodes are correctly
free()’d and do not cause memory leaks.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> size
3 nodes
TS#> clear
TS#> size
0 nodes
TS#> print
TS#> add S#> add S#> add Token
TS#> add S#> add Mr S#> size
5 nodes
TS#> print

Mr
S#> preorder

Token
MrGarrison
S#> clear
TS#> size
0 nodes
TS#> print
TS#> preorder
TS#> quit
#+END_SRC

* Many Clears
Adds items and clears several times to ensure that all malloc()’d
memory is recouped during a ‘clear’ command.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> size
0 nodes
TS#> add S#> add S#> add Cartman
TS#> size
3 nodes
TS#> print

Cartman
TS#> clear
TS#> add S#> add S#> size
2 nodes
TS#> print
Kenny
S#> clear
TS#> add Token
TS#> add S#> add Mr S#> size
3 nodes
TS#> print
oken
Mr S#> clear
TS#> print
TS#> add MrHat
TS#> add MrStick
TS#> add S#> add Clone S#> size
4 nodes
TS#> print
MrStick
MrHat
Kenny
Clone S#> clear
TS#> size
0 nodes
TS#> quit
#+END_SRC

* Save Tree w/ 1 Item
Adds a single item to a tree then saves it to a file. The file should
contain the single item in the tree. Tests the ‘save’ command.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add hello
TS#> save test-results/1.tree
TS#> quit
#+END_SRC

*** File Checks
Check that the contents of the saved tree file are correct.

#+TESTY: use_valgrind=0
#+TESTY: program=’cat test-results/1.tree’
#+BEGIN_SRC sh
hello
#+END_SRC

* Save Tree w/ 3 Items
Adds three items to the tree and saves it checking whether the items
appear in preorder within the file.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> save test-results/3.tree
TS#> quit
#+END_SRC

*** File Checks
Check that the contents of the saved tree file are correct.

#+TESTY: use_valgrind=0
#+TESTY: program=’cat test-results/3.tree’
#+BEGIN_SRC sh

Stan
#+END_SRC

* Save and Load
Creates a tree of 4 items then saves it. Clears the tree then loads
the tree from the save file which should restore it.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> add Mr S#> save test-results/4.tree
TS#> clear
TS#> print
TS#> load test-results/4.tree
TS#> print
Garrison

TS#>
#+END_SRC

*** File Checks
Check that the contents of the saved tree file are correct.

#+TESTY: use_valgrind=0
#+TESTY: program=’cat test-results/4.tree’
#+BEGIN_SRC sh

Garrison
#+END_SRC

* Multiple Saves
Creates several trees which are saved and loaded alternately. Larger
trees are used than in previous save/load tests. Ensures proper I/O
and memory allocation/de-allocation.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add Cartman
TS#> add Mr S#> add S#> save test-results/5.tree
TS#> add S#> add Token
TS#> add S#> save test-results/8.tree
TS#> load test-results/5.tree
TS#> print

TS#> load test-results/8.tree
TS#> print

S#>
#+END_SRC

*** File Checks
Check that the contents of the saved tree file are correct.

#+TESTY: use_valgrind=0
#+TESTY: program=’cat test-results/5.tree test-results/8.tree’
#+BEGIN_SRC sh

Kenny

Cartman
Butters
Kenny

Token
#+END_SRC

* Load Existing Tree
Create the test input tree

#+TESTY: use_valgrind=0
#+TESTY: program=’bash -v’
#+TESTY: prompt=’>>’
#+BEGIN_SRC sh
>> echo ‘MrGarrison ‘ > test-results/in.tree
>> echo ‘ Butters ‘ >> test-results/in.tree
>> echo ‘ Cartman ‘ >> test-results/in.tree
>> echo ‘ Kenny ‘ >> test-results/in.tree
>> echo ‘ Jimmy’ >> test-results/in.tree
>> echo ‘ Token ‘ >> test-results/in.tree
>> echo ‘ Timmy ‘ >> test-results/in.tree
#+END_SRC

#+TESTY: reset_options

Loads an existing tree called in.tree and prints its structure out to
check that the ‘load’ command works correctly independently of the
‘save’ command.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> load test-results/in.tree
TS#> size
7 nodes
TS#> print
Token
Timmy
Mr
Jimmy
Cartman
S#> preorder
Mr
Cartman
Kenny
Jimmy
Token
Timmy
TS#>
#+END_SRC

* Specification Demo
Runs the Demo that is shown in the project specification which tests
most of the functionality of the treeset program.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add S#> add S#> add El
TS#> size
5 nodes
TS#> print

S#> find OUND
TS#> find OT FOUND
TS#> add S#> size
6 nodes
TS#> print

Mike

S#> add Mike
duplicate element ignored
TS#> add El
duplicate element ignored
TS#> find OT FOUND
TS#> add S#> print

S#> find OT FOUND
TS#> add S#> print

Dustin
S#> save test-results/stranger.tree
TS#> clear
TS#> size
0 nodes
TS#> print
TS#> add Demigorgon
TS#> print
Demigorgon
TS#> load test-results/stranger.tree
TS#> size
8 nodes
TS#> print

Dustin
S#> add S#> add S#> print

Dustin
S#> load test-results/stranger.tree
TS#> print

Dustin
S#> quit
#+END_SRC

*** File Checks
Check that the contents of the saved tree file are correct.

#+TESTY: use_valgrind=0
#+TESTY: program=’cat test-results/stranger.tree’
#+BEGIN_SRC sh

#+END_SRC

* Big Stress
Adds a very large number of items to the tree to stress test the
application.

#+BEGIN_SRC sh
Treeset Main
Commands:
print: shows contents of the tree in reverse sorted order
size: prints the number of nodes currently in the tree
clear: eliminates all elements from the tree
quit: exit the program
add : inserts the given string into the tree, duplicates ignored
find : prints FOUND if the name is in the tree, NOT FOUND otherwise
preorder: prints contents of the tree in pre-order which is how it will be saved
save : writes the contents of the tree in pre-order to the given file
load : clears the current tree and loads the one in the given file
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add Amanda
TS#> add S#> add S#> add S#> add Abigail
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Brittany
TS#> add S#> add Carolyn
TS#> add S#> add S#> add S#> add Cheryl
TS#> add S#> add S#> add S#> add S#> add S#> size
50 nodes
TS#> print

Abigail
S#> add S#> add Deborah
TS#> add Debra
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Dylan
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Ethan
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Jacqueline
TS#> add S#> add S#> add S#> add Janet
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Joan
TS#> size
99 nodes
TS#> print

Deborah

Abigail
S#> preorder

Aaron

Andrea

Ann

Austin

Brittany

Christina

Gary

Frank

Heather

Harry

Jason

Janice

Joan
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Julie
TS#> add S#> add Judith
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add Katherine
TS#> add S#> add S#> add Kathryn
TS#> add Kayla
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Marilyn
TS#> add S#> add S#> add S#> add S#> add Melissa
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add Pamela
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add Rebecca
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> size
200 nodes
TS#> print

Joe

Deborah

Abigail
S#> find OUND
TS#> find OUND
TS#> find Anakin
NOT FOUND
TS#> find Leia
NOT FOUND
TS#> find OT FOUND
TS#> find OUND
TS#> save test-results/big.tree
TS#> clear
TS#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> add S#> find OUND
TS#> find OUND
TS#> find OT FOUND
TS#> find OT FOUND
TS#> load test-results/big.tree
TS#> size
200 nodes
TS#> print

Joe

Deborah

Abigail
S#> find OUND
TS#> find OUND
TS#> find OUND
TS#> find OUND
TS#>
#+END_SRC