Modules-Methods-Mixins

Modules-Methods-Mixins

Due by midnight on Monday February 10

Objectives

This assignment is designed to let you practice handling and raising exceptions, mixing in a module to a class, and OOP development with Ruby.

Description

  1. Exceptions


    Create a new exception class named IDontFeelLikeItError. This should be a subclass of StandardError. Write a method named unreliable that takes three parameters, a year, month, and day (all numbers). The method should return the name of the weekday of the corresponding date. Now alter your method so that 90% of the time it raises an IDontFeelLikeItError instead. Finally, write a method named reliable that takes the same parameters, but, using unreliable, always returns the correct value (i.e. does not raise an exception). Don't write any code you don't have to — there's plenty in the standard library to help you out. Put your methods in a file named reliability.rb.


  2. Binary Tree


    You should know what a binary tree is, but just in case you need a refresher, check out Binary Search Trees on Wikipedia. I don't want this part of the assignment to be about whether or not you can design the algorithms so feel free to use the algorithms described in the preceding wiki link. Additionally, the following may provide some insight into how to approach the design:


    • A binary search tree (BST) has a key, a left subtree, and a right subtree
    • Both subtrees ARE binary search trees (BSTs)
    • A total linear order is defined over all key values (no duplicate keys allowed!)
    • The key is greater than all keys in the left subtree
    • The key is less than all keys in the right subtree
    • If a BST has both subtrees nil, it is a leaf
    • If a BST is not the subtree of any other BST, it is the root
    • A BST is empty if-and-only-if it is the root AND it is a leaf AND its key is nil
    • A non-empty BST may NOT contain nil keys

    Implement a BinaryTree class in Ruby. You may assume that anything put into the tree will include the Comparable module, and thus be comparable with <, >, etc. Your implementation should have the following methods:


    • BinaryTree.new(value=nil), which creates a new BinaryTree, which is empty by default, but contains value if an argument is given
    • BinaryTree#add(value), which adds value to the tree, returning value. If value is already in the tree (that is, something for which == evalutates to true), it should return true.
    • BinaryTree#delete(value), which deletes the item value from the tree and returns the one that was deleted. Make sure you return the object that was deleted from the tree and not the one passed to the method (unless they are the same object). If the item is not found, the method should return nil. This is probably the trickiest method. Hint: remember that when you delete a node that has children, you need to keep the tree sorted appropriately — you may be interested in using some of the other methods to help you out, as well as perhaps a recursive call.
    • BinaryTree#empty?, which returns true or false, depending on whether the tree contains any values.
    • BinaryTree#include?(value), which returns true or false, depending on whether or not value is in the tree.
    • BinaryTree#max and BinaryTree#min, which return the largest and smallest items in the tree.
    • BinaryTree#height, which returns the height of the tree.
    • BinaryTree#size, which returns the number of items in the tree.
    • BinaryTree#balance, which balances the binary tree. Hint: you may want to do this one last.
    • BinaryTree#each, which should iterate through the items in the tree in infix order. That is, the smallest item first, up through the largest item last.

    Once you have the each method implemented, mix in the Enumerable module. This will give you access to many more methods, which you might (hint, hint) be able to use to write the other methods more easily. You should approach this assignment using a test-driven development approach. Provided for you below is a unit testing file that you can run to check that your implementation is correct.



Grading Criteria

Your code will be graded on style and correctness. Your BinaryTree class should pass all the tests in the given unit test file, without generating any errors. You should implement the unreliable and reliable methods as elegantly as possible.

Submission Checklist

  • binarytree.rb
  • reliability.rb