CSC 2/453, TCS 453
Assignment 2: Unit Tests and Iterators
Introduction:
In this assignment, you will first write unit tests for, and then implement, the Ruby Enumerator API. You must use Ruby and store your project in a DVCS repository.
hashtable iterator functions. These modifications need to be implemented in C. It is highly recommended that these functions are actually called and run for grading as Ruby extensions to the standard Ruby interpreter. This blog post will get you up and running with Ruby C extensions: http://www.rubyinside.com/how-to-create-a-ruby-extension-in-c-in-under-5-minutes-100.html
Every class and module should be prefixed with P2 and every method with p2. (e.g. P2Enumerable, p2each, p2all?, etc.), where P2 means Project 2.
Enumerable Iterator Methods (Required):
You will create your own module, P2Enumerable, in which you will implement most of the Enumerable module, documented at: http://ruby-doc.org/core-
2.2.3/Enumerable.html
Enumerable module includes many iterator methods each of which either operate on a Ruby block (anonymous function) or, if none is given, will return an iterator object (called an
Enumerable). You only need to implement the anonymous function version of each method. Implementing the enumerator returning version
will not get extra credit and is discouraged.
Your implementation of P2Enumerable methods should follow the Principle of Information Hiding, in that the methods should not care about the exact type of the object that is being enumerated as long as the object provides an iterator interface to traverse its content, in the form of an each method (or in your case, p2each). For example, two classes, Array and Hash, define their own each method and then include the Enumerable module for its iterators. As a result, arrays and hashtables are iterated using the same (Enumerable) methods. Similarly, you should not re-implement your methods for each class/datatype.
The code of your iterators must also be DRY. If an iterator method needs the function of another iterator, your code should call the other iterator instead of re-implementing it.
You cannot use any of the methods from Enumerable anywhere in your code and should use p2each (not each) in place of conventional loops. The full list of required, optional, and not required methods is below:
Required: 28 Iterator Methods
all? { |obj| block }
any? { |obj| block }
se
same as map
same as flat_map
l
find_all { |obj
inject(initial) { |memo, ob
inj
minmax
same as select
same as reduce
You should commit after implementing each method. (So minimum of 28 commits)
Optional:
(Extra Credit: Each optional method is worth 1/5th of a required method)
max_b
none? { |obj| block }
one? { |obj| block }
Not Required:
Do not implement these methods:
chunk
each_with_object
slice_after
slice_befoer
slice_when
zip
Tree or Graph Iterator Methods (Required):
Implement a simple binary tree or undirected graph in a class named P2Tree or P2Graph, respectively. Your class should contain two enumerator functions. The first enumerates each node of your tree/graph, i.e. the each method. (Though remember, yours should be named p2each.) The second enumerates each node as in the first, but also provides the level of (if you chose a tree), or the number of neighbors for (if you chose a graph), the current node.
If you chose a tree, your method should be called p2each_with_level, and if you chose a graph, it should be called either p2each_with_neighbor_count or p2each_with_popularity
Your class can have trivial functionality/implementation. It must only support node insertions and, in the case of the tree, does not have to be asymptotically efficient, i.e. no need to sort or balance the tree as it grows.
Unit Tests (Required):
Unit tests are automated tests that are often tied with a continuous integration (CI) server to frequently check correctness of a software module. One or more tests are needed for every method, in our case, every method of the Enumerable module and, for CSC453, every iterator method of Ruby 2. should execute all the code paths in a method implementation.
Good unit tests can be run in an arbitrary order and get the same results (e.g. they leave no side effects). Thorough unit tests will force execution through all/most code paths being tested (e.g. if and switch statements, variable amounts of recursion etc.).
You may use the tests shown in the documentation, but only in addition to your own tests. E.g. each method should be fully tested by your own unit tests. You must attribute the documentation for any tests used.
In your P2Enumerable unit tests, make sure to test them on built-in Ruby types such as Array. To do this you must open up the Array class and either implement p2each, or alias p2each as each.
The unit tests for P2Tree/P2Graph iterators should include direct tests of the two new methods implemented, as well as tests ensuring P2Enumerable methods can be used on your new class. (Remember, all P2Enumerable methods should work on any object with a p2each method.)
These tests should be written separately from the unit tests of P2Enumerable. You may find it convenient to reuse the P2Enumerable tests for the P2Tree/P2Graph methods, but you must first create new, different unit tests separately.
There should be a unit test for every method in P2Tree/Graph and P2Enumerable, and preferably more to be thorough. (Also note that we will be using these unit tests in the next assignment, and having more tests will make it easier to get a better grade on that assignment.)
Hashtable (Required for CSC 453/Extra Credit for others):
The MRI/CRuby implementation relies heavily on hashtables. Check out the source code for
Ruby 2.2 (https://github.com/ruby/ruby/tree/ruby_2_2) and look at the hashtable in st.c. This
C source for this hashtable and write unit tests for each of its major functions. The unit tests must be written in C using assert.h from the GNU standard library. assert.h defines one function (really a macro) that aborts the program if an expression returns false before termination and prints the offending expression with file/line information.
File Structure:
Put the files into five directories as follows (where uid is your csug username):
uid_enum: the implementation of the iterator methods. These methods should be in the module P2Enumerable.
uid_tree or uid_graph: the implementation of the tree or graph class, which should becalledclass P2Treeorclass P2Graph,respectively.
uid_enum_tests: the unit tests for the P2Enumerable module. uid_tree_tests or uid_graph_tests:theunittestsfortheP2Tree/Graph
module.
uid_tree_enum_tests or id_graph_enum_tests:theunittestsforthe
P2Tree/Graph and P2Enumerable integration.
README:
Please include a README document which includes:
1. Name and what course you are signed up for (CSC253/453)
2. Instructions on how to run your program
3. How iteration is stopped
4. Any unique or extra things that you may have done (including C unit tests for undergrads/TCS students)
Makefile:
(https://en.wikibooks.org/wiki/Make)
If your project uses C, it must include
compiling the code the same way. For students only submitting Ruby code there is no need (or real use) for a Makefile.