lab08 : Used Car Lot

num ready? description assigned due
lab08 true Used Car Lot Fri 03/01 11:59PM Mon 03/11 11:59PM

In this lab, you’ll have the opportunity to practice:

Note: It is important that you start this lab early so you can utilize our office hours to seek assistance / ask clarifying questions during the weekdays before the deadline if needed.

Introduction

The goal for this lab is to write a program that will manage cars for a used car dealership. All cars have a make, model, year, and price, which can be used to determine the value of cars in relation to each other. All cars will be managed by a Binary Search Tree (BST) where the nodes are sorted by make, then model in lexicographical order. Within each make/model node, the Car objects will be added to a Python List based on insertion order.

In order to manage the cars for this lab, you will define Car, CarInventoryNode and CarInventory classes that organize the Cars in a BST data structure. Cars with the same make/model will be located in the same node, and appended to a list based on insertion order.

You will also write pytests in testFile.py illustrating your behavior works correctly. This lab writeup will provide some test cases for clarity, but the Gradescope autograder will run different tests shown here.

Instructions

You will need to create four files:

There will be no starter code for this assignment, but rather class descriptions and required methods are defined in the specification below.

You should organize your lab work in its own directory. This way all files for a lab are located in a single folder. Also, this will be easy to import various files into your code using the import / from technique shown in lecture.

Car.py

The Car.py file will contain the definition of a Car class. The Car class will hold information about the cars (make, model, year, and price). We will define the Car attributes as follows:

You will write a constructor that allows the user to construct a Car object by passing in values for the make, model, year, and price.

In addition to the constructor of the Car class, the following methods are required to be implemented:

For example:

c = Car("Honda", "CRV", 2007, 8000)
print(c)

Output:

Make: HONDA, Model: CRV, Year: 2007, Price: $8000

CarInventoryNode.py

The CarInventoryNode.py file will contain the definition of a CarInventoryNode class, which is the node for a BST.

The CarInventoryNode class should have the following attributes:

The CarInventoryNode class should define the following methods:

In addition to the construction of the BST in this class, the following methods are required to be implemented:

For example:

car1 = Car("Dodge", "dart", 2015, 6000)
car2 = Car("dodge", "DaRt", 2003, 5000)
carNode = CarInventoryNode(car1)
carNode.cars.append(car2)
print(carNode)

Output: (note the extra newline)

Make: DODGE, Model: DART, Year: 2015, Price: $6000
Make: DODGE, Model: DART, Year: 2003, Price: $5000

Some tips for the implementation:

CarInventoryNodes are ordered by make and model attributes. You can implement comparators (<, ==, >) for CarInventoryNode to help with navigating through the CarInventory, but this is not required.

CarInventory.py

The CarInventory.py file will contain the definition of a CarInventory class. This will manage the CarInventoryNodes and keep track of all the cars a dealership has. The CarInventory is implemented as a BST. The CarInventory will create and manage CarInventoryNode objects based on a car’s make and model attributes. When storing Car objects in the CarInventory, Car objects with the same make and model will be appended to a Python List based on insertion order within the CarInventoryNode object.

In addition to the construction of the BST in this class, the following methods are required to be implemented:

Given an example BST:

bst = CarInventory()

car1 = Car("Nissan", "Leaf", 2018, 18000)
car2 = Car("Tesla", "Model3", 2018, 50000)
car3 = Car("Mercedes", "Sprinter", 2022, 40000)
car4 = Car("Mercedes", "Sprinter", 2014, 25000)
car5 = Car("Ford", "Ranger", 2021, 25000)

bst.add_car(car1)
bst.add_car(car2)
bst.add_car(car3)
bst.add_car(car4)
bst.add_car(car5)

An example of the traversal functions is given below:

assert bst.get_best_car("Nissan", "Leaf") == car1
assert bst.get_best_car("Mercedes", "Sprinter") == car3
assert bst.get_best_car("Honda", "Accord") == None

assert bst.get_worst_car("Nissan", "Leaf") == car1
assert bst.get_worst_car("Mercedes", "Sprinter") == car4
assert bst.get_best_car("Honda", "Accord") == None

assert bst.get_total_inventory_price() == 158000

An example of the inorder() string format is given below:

assert bst.inorder() == \
"""\
Make: FORD, Model: RANGER, Year: 2021, Price: $25000
Make: MERCEDES, Model: SPRINTER, Year: 2022, Price: $40000
Make: MERCEDES, Model: SPRINTER, Year: 2014, Price: $25000
Make: NISSAN, Model: LEAF, Year: 2018, Price: $18000
Make: TESLA, Model: MODEL3, Year: 2018, Price: $50000
"""

An example of the preorder() string format is given below:

assert bst.preorder() == \
"""\
Make: NISSAN, Model: LEAF, Year: 2018, Price: $18000
Make: MERCEDES, Model: SPRINTER, Year: 2022, Price: $40000
Make: MERCEDES, Model: SPRINTER, Year: 2014, Price: $25000
Make: FORD, Model: RANGER, Year: 2021, Price: $25000
Make: TESLA, Model: MODEL3, Year: 2018, Price: $50000
"""

An example of the postorder() string format is given below:

assert bst.postorder() == \
"""\
Make: FORD, Model: RANGER, Year: 2021, Price: $25000
Make: MERCEDES, Model: SPRINTER, Year: 2022, Price: $40000
Make: MERCEDES, Model: SPRINTER, Year: 2014, Price: $25000
Make: TESLA, Model: MODEL3, Year: 2018, Price: $50000
Make: NISSAN, Model: LEAF, Year: 2018, Price: $18000
"""

As part of the debugging process, we are providing you two functions to visually represent the BST to ensure it looks similar to your thought. Make use of these carefully through multiple steps of your methods - For e.g. in inorder, you can print out the visual representation of your subtree in each step of the recursion so that you can validate your theoretical assumption in action. If you want to call this method inside your call, you can do this by running show_tree(self.root) or show_tree(node) or show_tree(car_inventory_object.root). Below is the code snippet for the functions and the corresponding logic to see it in action -

def show_tree(node):
    """
    * -> Indicates the base node
    L -> Indicates the left child of the base node
    R -> Indicates the right child of the base node
    LR -> Indicates the right child of the left child of the base node
    ..... and so on
    """
    import sys
    from io import StringIO
    old_stdout = sys.stdout
    sys.stdout = StringIO()
    if node is None:
        print("No cars in inventory.")
    else:
        print(f"Showing Tree Representation of Children under Node - Make: {node.get_make()}, Model: {node.get_model()}\n")
        _print_tree(node, 0, "")
        print("\nEnd of the car inventory. \n")
    print("\n" + "="*50 + "\n")
    contents = sys.stdout.getvalue()
    sys.stdout = old_stdout
    print(contents)        

def _print_tree(node, level, position):
    if node is not None:
        _print_tree(node.get_right(), level + 1, position + "R")
        print("   " * level + "|----" + f"(Level {level}) {node.get_make()} : {node.get_model()} ({position if position else '*'})")
        _print_tree(node.get_left(), level + 1, position + "L")

if __name__ == "__main__":
    inventory = CarInventory()
    # Adding some cars
    inventory.add_car(Car("Toyota", "Camry", 2020, 25000))
    inventory.add_car(Car("Honda", "Accord", 2019, 23000))
    inventory.add_car(Car("Toyota", "Corolla", 2018, 20000))
    inventory.add_car(Car("Honda", "Civic", 2021, 22000))
    inventory.add_car(Car("Ford", "Fusion", 2017, 18000))
    inventory.add_car(Car("Chevrolet", "Malibu", 2016, 17000))
    # Displaying the inventory
    show_tree(inventory.root)

The output for this should look like this -

Showing Tree Representation of Children under Node - Make: TOYOTA, Model: CAMRY

   |----(Level 1) TOYOTA : COROLLA (R)
|----(Level 0) TOYOTA : CAMRY (*)
      |----(Level 2) HONDA : CIVIC (LR)
   |----(Level 1) HONDA : ACCORD (L)
      |----(Level 2) FORD : FUSION (LL)
         |----(Level 3) CHEVROLET : MALIBU (LLL)

End of the car inventory. 


==================================================

Other than the required methods, feel free to implement any helper methods that you think are useful in your implementation (Gradescope will test the required methods). The automated tests will test your implementation of the required methods by creating a CarInventory containing various CarInventoryNodes containing Cars with different make, model, year, and price attributes. The add_car() method will be run, with does_car_exist(), get_best_car(), get_worst_car(), inorder(), preorder(), and postorder(), etc. being used to verify that the CarInventory is fully functional. You should write similar tests to confirm your BST is working properly.

testFile.py

This file should test all of your classes and required methods using pytest. Think of various scenarios and edge cases when testing your code according to the given descriptions. You should test every class’ method functionality. Even though Gradescope will not use this file when running automated tests (there are separate tests defined for this), it is important to provide this file with various test cases (testing is important!!). Here, examples of various test cases could be different tree structures. We are providing you with a few example tree structures, for which you may write pytests.

# Example 1:
bst = CarInventory()
car1 = Car("Nissan", "Leaf", 2018, 18000)
car2 = Car("Tesla", "Model3", 2018, 50000)
car3 = Car("Mercedes", "Sprinter", 2022, 40000)
car4 = Car("Mercedes", "Sprinter", 2014, 25000)
car5 = Car("Ford", "Ranger", 2021, 25000)
bst.add_car(car1)
bst.add_car(car2)
bst.add_car(car3)
bst.add_car(car4)
bst.add_car(car5)
show_tree(bst.root)

# Showing Tree Representation of Children under Node - Make: NISSAN, Model: LEAF

#    |----(Level 1) TESLA : MODEL3 (R)
# |----(Level 0) NISSAN : LEAF (*)
#    |----(Level 1) MERCEDES : SPRINTER (L)
#       |----(Level 2) FORD : RANGER (LL)

# End of the car inventory. 


# ==================================================


# Example 2:
bst1 = CarInventory()
car1 = Car("toyota", "prius", 2022, 25000)
car2 = Car("Honda", "ODYSSEY", 2009, 30000)
car3 = Car("Ferrari", "testarossa", 1990, 100000)
car4 = Car("Chevrolet", "Equinox", 2011, 10000)
bst1.add_car(car1)
bst1.add_car(car2)
bst1.add_car(car3)
bst1.add_car(car4)
show_tree(bst.root)

# Showing Tree Representation of Children under Node - Make: TOYOTA, Model: PRIUS

# |----(Level 0) TOYOTA : PRIUS (*)
#    |----(Level 1) HONDA : ODYSSEY (L)
#       |----(Level 2) FERRARI : TESTAROSSA (LL)
#          |----(Level 3) CHEVROLET : EQUINOX (LLL)

# End of the car inventory. 


# ==================================================


# Example 3:
bst2 = CarInventory()
car5 = Car("toyota", "prius", 2022, 25000)
car6 = Car("Honda", "ODYSSEY", 2009, 30000)
car7 = Car("Ferrari", "testarossa", 1990, 100000)
car8 = Car("Chevrolet", "Equinox", 2011, 10000)
bst2.add_car(car8)
bst2.add_car(car7)
bst2.add_car(car6)
bst2.add_car(car5)
show_tree(bst.root)

# Showing Tree Representation of Children under Node - Make: CHEVROLET, Model: EQUINOX

#          |----(Level 3) TOYOTA : PRIUS (RRR)
#       |----(Level 2) HONDA : ODYSSEY (RR)
#    |----(Level 1) FERRARI : TESTAROSSA (R)
# |----(Level 0) CHEVROLET : EQUINOX (*)

# End of the car inventory. 


# ==================================================


# Example 4:
bst = CarInventory()
car1 = Car("toyota", "prius", 2022, 25000)
car2 = Car("Honda", "ODYSSEY", 2009, 30000)
car3 = Car("Chevrolet", "Equinox", 2011, 10000)
car4 = Car("Toyota", "Sienna", 2007, 35000)
car5 = Car("Toyota", "Corolla", 2006, 10000)
car6 = Car("toyota", "camry", 2007, 11000)
car7 = Car("TOYOTA", "raV4", 2008, 12000)
bst.add_car(car1)
bst.add_car(car2)
bst.add_car(car3)
bst.add_car(car4)
bst.add_car(car5)
bst.add_car(car6)
bst.add_car(car7)
show_tree(bst.root)

# Showing Tree Representation of Children under Node - Make: TOYOTA, Model: PRIUS

#    |----(Level 1) TOYOTA : SIENNA (R)
#       |----(Level 2) TOYOTA : RAV4 (RL)
# |----(Level 0) TOYOTA : PRIUS (*)
#       |----(Level 2) TOYOTA : COROLLA (LR)
#          |----(Level 3) TOYOTA : CAMRY (LRL)
#    |----(Level 1) HONDA : ODYSSEY (L)
#       |----(Level 2) CHEVROLET : EQUINOX (LL)

# End of the car inventory. 


# ==================================================


# Example 5:
bst = CarInventory()
car1 = Car("toyota", "prius", 2022, 25000)
car1A = Car("TOYOTA", "PRIUS", 2022, 30000)
car2 = Car("Honda", "ODYSSEY", 2009, 30000)
car3 = Car("Chevrolet", "Equinox", 2011, 10000)
car4 = Car("Toyota", "Sienna", 2007, 35000)
car5 = Car("Toyota", "Corolla", 2006, 10000)
car6 = Car("toyota", "camry", 2007, 11000)
car7 = Car("TOYOTA", "raV4", 2008, 12000)
car8 = Car("toyota", "yaris", 2005, 2000)
car9 = Car("toyota", "4runner", 2007, 10000)
bst.add_car(car8)
bst.add_car(car4)
bst.add_car(car7)
bst.add_car(car6)
bst.add_car(car1A)
bst.add_car(car5)
bst.add_car(car3)
bst.add_car(car2)
bst.add_car(car1)
bst.add_car(car9)
show_tree(bst.root)

# Showing Tree Representation of Children under Node - Make: TOYOTA, Model: YARIS

# |----(Level 0) TOYOTA : YARIS (*)
#    |----(Level 1) TOYOTA : SIENNA (L)
#       |----(Level 2) TOYOTA : RAV4 (LL)
#             |----(Level 4) TOYOTA : PRIUS (LLLR)
#                |----(Level 5) TOYOTA : COROLLA (LLLRL)
#          |----(Level 3) TOYOTA : CAMRY (LLL)
#                   |----(Level 6) TOYOTA : 4RUNNER (LLLLRR)
#                |----(Level 5) HONDA : ODYSSEY (LLLLR)
#             |----(Level 4) CHEVROLET : EQUINOX (LLLL)

# End of the car inventory. 


# ==================================================

# Example 6:
bst = CarInventory()
car1 = Car("toyota", "prius", 2022, 25000)
car2 = Car("Honda", "ODYSSEY", 2009, 30000)
car3 = Car("Ferrari", "testarossa", 1990, 100000)
car4 = Car("ferrari", "monza", 2020, 500000)
car5 = Car("Chevrolet", "Equinox", 2011, 10000)
bst.add_car(car1)
bst.add_car(car5)
bst.add_car(car2)
bst.add_car(car4)
bst.add_car(car3)
show_tree(bst.root)

# Showing Tree Representation of Children under Node - Make: TOYOTA, Model: PRIUS

# |----(Level 0) TOYOTA : PRIUS (*)
#       |----(Level 2) HONDA : ODYSSEY (LR)
#             |----(Level 4) FERRARI : TESTAROSSA (LRLR)
#          |----(Level 3) FERRARI : MONZA (LRL)
#    |----(Level 1) CHEVROLET : EQUINOX (L)

# End of the car inventory. 


# ==================================================

Hint: use the traversal methods (inorder, preorder and/or postorder) to test the above tree structures

A note about Gradescope tests: Gradescope will use your functions to correctly check the state of your Cars and CarInventory with many scenarios. In order to test if everything is in the correct state, these tests use your CarInventory’s preorder / inorder / postorder traversals and add_car methods, as well as getting the string representation of your Cars (using your __str__ overloaded method in Car) to run other tests such as CarInventory’s does_car_exist, get_best_car, get_worst_car, get_total_inventory_price, etc. It is important to ensure your preorder / inorder / postorder traversals, Car’s __str__ method, and CarInventory’s add_car methods work correctly first or else many of the other tests may not pass.

Of course, feel free to reach out / post questions on Piazza as they come up!

How to best approach this lab

This lab contains a lot of implementation details, and different parts of the lab intertwine and depend on each other. Here are some suggestions on the order of approaching the lab:

  1. Implement the Car class, and especially double check that your comparators are working
  2. Implement the CarInventoryNode class. You should go through and test your __str__ overloading before moving on
  3. Start with add_car, and then the BST traversal methods. You should test to see if your add_car is working by inserting several Cars into the BST, and using the traversals to verify your results; is a new CarInventoryNode being created if the Car didn’t exist in the BST, and if the node did already exist, is the Car being inserted to the list of cars in the node?
  4. Once you’ve made sure your add_car is working, you can then move on to does_car_exist, get_best_car and get_worst_car.
  5. Testing is extremely important to help debug any issues you may experience. Be sure to write thorough tests with various edge cases to make sure your program works as expected.

Submission

Once you’re done with writing your class definitions and tests, submit the following files to Gradescope’s Lab08 assignment:

There will be various unit tests Gradescope will run to ensure your code is working correctly based on the specifications given in this lab.

If the tests don’t pass, you may get some error message that may or may not be obvious at this point. Don’t worry - if the tests didn’t pass, take a minute to think about what may have caused the error. If your tests didn’t pass and you’re still not sure why you’re getting the error, feel free to ask your TAs or Learning Assistants.