Title image Fall 2018

Due: Thursday, 25 October 2018

Part I: Polymorphism in C

For this part, develop an example of polymorphism and demonstrate how C can implement polymorphic functions and types.

Tasks

  1. Create a generic linked list class in C. First, create a LinkedList struct that has a head pointer and a Node struct that can hold an arbitrary pointer and a next pointer. You are free to use single- or doubly-linked lists. Then implement the following functions.

    • LinkedList *ll_create() creates a new LinkedList struct, initializes it, and returns it.
    • void ll_push(LinkedList *l, void *data) adds a node to the front of the list, storing the given data in the node.
    • void *ll_pop(Linked List *l) removes the node at the front of the list and returns the associated data.
    • void ll_append(LinkedList *l, void *data) adds a node to the end of the list, storing the given data in the node.
    • void *ll_remove(LinkedList *l, void *target, int (*compfunc)(void *, void *)) removes the first node in the list whose data matches target given the comparison function. The function returns the pointer to the data.
    • int ll_size(LinkedList *l) returns the size of the list.
    • void ll_clear(LinkedList *l, void (*freefunc)(void *)) removes all of the nodes from the list, freeing the associated data using the given function.
    • void ll_map(LinkedList *l, void (*mapfunc)(void *)) traverses the list and applies the given function to the data at each node.

    You can test your linked list function using this test function. Compile using:

    gcc -o clltest clltest.c yourLinkedList.c

    Extend the test function so it uses a linked list with a second data type.

Part II: Polymorphism in Selected Languages

For this part, develop examples of polymorphism and demonstrate how the selected languages can implement polymorphic functions, classes, and types.

Tasks

  1. Implement a LinkedList class in your list A language, making use of some form of polymorphism to implement the data structure. Create the same set of functions as above, but adapt the data types, as necessary. If your language enables templates or generics, use them. Create a test function like the C test file that demonstrates you can create linked lists to store two different types of data.

    Your list A language may have a built-in list data type, similar to Python. Can you create similar functionality without using it? If not, then write code that models each of the functions listed for the API and note any additional capabilities the built-in type has. See if you can figure out how the internal data structure is implemented by doing some timing tests and looking at the results. For example, if the built-in structure is a linked list, then searching it should take linear (O(N)) time.

  2. In your list B/C language demonstrate polymorphism using an approach that is natural or built-in to the language. Can you create some type of array or list that can hold multiple types (e.g. in Python you would demonstrate this using the built-in list). In SQL, can you make a field of a table hold different types of data?
  3. Generate a wiki page that shows the examples in your two languages. Explain how the language makes use of polymorphism. If your language has generics or templates, explain how it is implemented. These do not need to be long or detailed explanations, but should identify the benefits and drawbacks of the implementation method.

Extensions

  1. A perfectly acceptable extension for any assignment is to do one or more of the above tasks in a third language.
  2. Implement more than one method of creating a generic implementation of a data structure in one of your languages. Explain how the methods differ and any benefits/drawbacks.
  3. Make a compilable and runnable haiku in the language that helps to demonstrate the concept of polymorphism. poly.py
  4. Implement the delete function for your linked list in C that can remove the node at any position in the list.
  5. Improve your C linked list and make sure it has no memory leaks. You should feel free to add to or modify the existing set of functions if you add functionality/capabilities.

Submission

Submission for this project has three components:

  1. Code: Your linked list implementation in C and the selected languages should be submitted to the fileserver, including code for any extensions. Please make the filename of your source codes meaningful.Note that the quality of your comments counts toward your grade.
  2. README: Submit a README file to the fileserver for your C code and the code for your selected languages. The README file can be a .txt file. No matter what, it should be readable from the terminal (no Word or pdf files). It should be well-organized such that readers can easily understand the usage and the outputs of the C code and the code for your selected languages. In addition, any known bugs should be in the README file. Follow the format and content instructions from the writing guide.
  3. Wiki Report: The non-C language pages for this project should have the following elements.
    • Title of the project and your name. Include your partner's name if you worked with someone for the non-C tasks.
    • A section for each task of part II. Each section should contain appropriate snippets of your sample programs, the outputs, and your explanations.
    • If you complete extensions in your selected languages, please include a section for each extension, providing sample programs, outputs, and explanations. Be sure to indicate credit, if necessary.
    To check whether you've made your write-up well organized, please follow the Organization part in the Wiki section on this writing page.

Please note that it is your responsibility to explicitly indicate the extensions you have undertaken. If you complete extensions for the C tasks, please indicate that explicitly in the code and README file. If you complete an extension in a selected language, please indicate this explicitly in your wiki report. Along with each extension, indicate if you completed it with a partner.