- EXIT()
- The program will terminate naturally.
Output summary:
<output>:=mission complete
- CLEAR_ALL()
- A simple command that restores all structures to initial state. Therefore, all data in the data dictionary, inventory heap, and spatial data structure(if applicable) will be removed.
Output summary:
<output>:=structures cleared
- CREATE_BASE(name, longitude, latitude)
-
name:case-sensitive string representation of a base
longitude:integer [0,1024], x coordinate of a base
latitude:integer [0,1024], y coordinate of a base
You will add the corresponding object to your dictionary data structure. If
a base/target with the same name already exists, you will print the
corresponding error message. Use name as the key for you data
dictionary. You are only archieving the data and not inserting it into the
map(spatial data structure). This must be an O(lg(n)) operation.
Output summary:
<output>:= <success>|<error>
<success>:=created base
<error>:=already exists|invalid name
- CREATE_TARGET(name, longitude, latitude)
-
name:case-sensitive string representation of a target
longitude:integer [0,1024], x coordinate of a target
latitude:integer [0,1024], y coordinate of a target
A target object with name, longitude, and latitude will be added to the dictionary data structure. Print an error message if there is already a base or target with the same name already added to the dictionary. Add it to the data dictionary but not the spatial data structure. This must be an O(lg(n)) operation.
Output summary:
<output>:= <success>|<error>
<success>:=created target
<error>:=already exists | invalid name
- DELETE_DATA(name)
-
name:case-sensitive string representation of a base/target
You will remove the base/target with the name from your dictionary data structure. If it does not exist, print the corresponding error message. Also, if it is currently on the map, you may not delete the base/target. Therefore, print the corresponding error message. This must be an O(lg(n)) operation.
Output summary:
<output>:= <success>|<error>
<success>:=deleted data
<error>:=does not exist|currently mapped
- MAP_DATA(name)
-
name:case-sensitive string representation of a base/target
You will find the base/target with name specified in your data
dictionary and add it to your spatial data structure. If it does not exist,
print the corresponding error message. Also, if the base/target is
currently on the map,
print the second message. Finally, if there is any other base/target at
those coordinates, print the final message. This must be an O(lg(n))
operation.
Output summary:
<output>:= <success>|<error>
<success>:=mapped <type>
<type>:= base\n | target\n
<error>:=does not exist|already mapped|spatial intersection
- CLEAR_COORDINATE(longitude,latitude)
-
longitude:integer[0,1024], represents the x coordinate
latitude:integer[0,1024], represents the y coordinate
You should search your spatial data structure with the specified coordinates. If there is either a base or a target at that location, remove it from your spatial data structure only. This must be an O(lg(n)) operation.
Output summary:
<output>:= <success>|<error>
<success>:=coordinate cleared
<error>:=coordinate empty
- ADD_ITEM(itemName, effectiveness, name)
-
itemName:case-sensitive string representation of an item
effectiveness:non-negative integer metric (lower valued items are used first). This is a measure of a weapon's ability to solely destroy its target, with little to no collateral damage. Thus, in the weapons cache(inventory), lower metrics will be higher priority.
name:case-sensitive string representation of a base
These are instantly added to a mapped base's inventory (Fibonacci Heap). Insert should be O(1). If the name specified is not the name of a base in your data dictionary you will print the first message. If the base exists, but is not currently on the map, print the second message.
Output summary:
<output>:= <success>|<error>
<success>:=item added
<error>:=base invalid|base not mapped|inventory added
- TRANSFER_ITEM(name1, name2)
-
name1:case-sensitive string representation of a base
name2:case-sensitive string representation of a base
This transfers one item from name1 to name2. So, the min element of the
Fibonacci heap (of name1) will be removed and then inserted to the inventory
of the second argument.
The children of the min element will be brought up one level in the exact
position their parent was located. There will be a consolidation
stage perfomed.
Also, you will need to update the min element with the next smallest element in the root list.
An error message will be printed
if either of the bases do not exist or if either base in not mapped. Also,
if the first base has an empty inventory, print the final
message.
Should be log(n) amortized runtime.
Output summary:
<output>:= <success>|<error>
<success>:=item transfer complete
<error>:=first base invalid|second base invalid|first base not mapped|second base not mapped|can't transfer anything
- TRANSFER_ALL(name1, name2)
-
name1:case-sensitive string representation of a base
name2:case-sensitive string representation of a base
Put the heap of name1 into the heap of name2. See examples of Union. The first argument's heap should be empty if this operation is successful. Error messages follow TRANSER_ITEM.
You will not consolidate the structure to have at most one binomial heap of a given degree. This should be done in constant time.
Output summary:
<output>:= <success>|<error>
<success>:=everything transfered
<error>:=first base invalid|second base invalid|first base not mapped|second base not mapped|can't transfer anything
- TRANSFER_ALL_WITH_CONSOLIDATE(name1, name2)
-
name1:case-sensitive string representation of a base
name2:case-sensitive string representation of a base
Put the heap of name1 into the heap of name2. See examples
of Merge. The first argument's heap should be empty if this
operation is successful. Error messages follow TRANSER_ITEM.
You will consolidate the structure to have at most one binomial heap of a given degree.
Output summary:
<output>:= <success>|<error>
<success>:=everything transfered
<error>:=first base invalid|second base invalid|first base not mapped|second base not mapped|can't transfer anything
- CONSOLIDATE(name1)
-
name1:case-sensitive string represention of a base
Explicit call to consolidate the heaps of the mapped base with specified
name. You must maintain the heap property for each binomial heap of a given
degree. The first error will be displayed if the base is not in the data
dictionary. If the base is not on the map currently, print the second error
message. If the heap is empty, you will print the final error message.
You will consolidate the structure to have at most one binomial heap of a given degree.
Output summary:
<output>:= <success>|<error>
<success>:=consolidated heap
<error>:=first base invalid|first base not mapped|can't consolidate
- PRINT_HEAP(name)
-
name:case-sensitive string representation of a base
You will print each key in the heap in the following manner: enclosed in
parentheses, print each node's value in the root list. If that node has
any children, print them immeadiately next to that node in parenthesis.
This process will be applied recursively.
Therefore, on one line you will be displaying the entire heap. Color is
used in the example to make the nesting more apparent. We will be testing
each individual binomial heap for the heap property. Also, we will verify
that there are at most one heap of each degree. Note: this display is
followed by a new line ("\n").
The heap is to be printed in the following manner:
a) output left parenthesis
b) beginning with the min value in the f-heap,
for each binomial heap in the forest,
output the root value
output the roots of its child subtrees enclosed in parentheses
repeat recursively until all subtrees have been printed
c) output right parenthesis
d) output a new line ("\n")
The output corresponding the the sample f-heap below has been colored to
help you identify the correspondence between subtrees and nested roots.
No such coloring is necessary for your print function.
This is a standard linear respresentation of a forest of general trees
that can be used to serialize such structures. It will allow us to verify
that your fibonacci heap satisfies the constraints for such structures,
regardless of the specific ordering of values in the f-heap.
SAMPLE FIBONACCI HEAP
7-----------52--------------18
| |
| |
24-----17---30 |
| | 41---39
| | |
26--46 23 |
| |
| 44
|
35
( 7 ( 24 ( 26 (
35 ) 46 ) 17 ( 23 ) 30) 52 18 ( 41
( 44 ) 39 ) )
You must have at least one value within each set of parentheses. This will be called on the MIN element. This means printing will begin with the min element.
Output summary:
<output>:= <success>|<error>
<success>:=<PrintRow>
<PrintRow>:=( PrintEachNode )
<PrintEachNode>:=<NodeDisplay> <PrintEachNode>| <NodeDisplay>
<NodeDisplay>:= <value of node> <PrintRow>| <value of node>
<error>:=no items
- PRINT_DICTIONARY()
-
An asciibetical traversal of your data dictionary will be done. Display each object on a new line as follows:
<type of object>: <name> at (longitude,latitude)
This should display all bases and targets entered into the dictionary. Do not display deleted objects. If empty, print the corresponding message.
Example:
base: Balogna at (7,4)
target: Rome at (4,5)
base: Saratoga at (23,54)
Iterators will make this task much easier to accomplish.
Output summary:
<output>:= <success>|<error>
<success>:=**as described**
<error>:=dictionary empty
- PRINT_SPATIAL()
-
You will display each object in the order its corresponding key appears in the spatial data structure. Display each object on a new line as follows:
<type of object>: <name> at (longitude,latitude)
This will verify your comparator's correctness. Do not display
deleted objects. If empty, print the corresponding message.
Example:
target: Rome at (4,5)
base: Balogna at (7,4)
base: Saratoga at (23,54)
Note the changes in ordering.
Output summary:
<output>:= <success>|<error>
<success>:=**as described**
<error>:=no spatial data
