Differences

This shows you the differences between two versions of the page.

--- haas:spring2015:data:projects:dll1 [2014/03/23 13:53] – external edit 127.0.0.1
+++ haas:spring2015:data:projects:dll1 [2015/04/15 18:48] (current) – [Errata] wedge
@@ Line 6: / Line 6: @@
 ~~TOC~~
-======Project: DLL1: Doubly-Linked Lists (and Queues)======
+======Project: DLL1======
-=====Overview=====
+=====Errata=====
-We will be extending our sll2 project in dll1 with the addition of doubly-linked lists, as well as the implementation of the queue data structure (using a doubly linked list). You are also to enhance/rewrite/reimplement all existing code based on a singly linked list (node, list, and stack) to make effective use of the doubly linked list.
+This section will document any updates applied to the project since original release:
-=====Update and Upgrade=====
+  * __revision 1__: Implemented a few refinements to unit-obtain (20150415)
-For this project, you'll update your **sll2** project to gain access to the new **upgrade-dll1** option in the Makefile:
-====Step 0. Change into project directory====
+=====Objective=====
-Change to wherever you copied your code (I'm assuming **~/src/data/sll2** in my example):
+In this project, we continue our doubly linked list re-write, completing the remaining library functions.
-<cli>
-lab46:~$ cd src/data/sll2
-lab46:~/src/data/sll2$
-</cli>
-====Step 1. Update to latest release (preserves your code)====
+=====Procedure to Obtain dll1=====
+As this project utilizes the code you wrote in dll0, you must upgrade to dll1 from dll0 (same thing that we did to transition between the sll* projects):
 <cli>
-lab46:~/src/data/sll2$ make update
+lab46:~/src/data/dll0$ make upgrade-dll1
 ...
 </cli>
-====Step 2. Upgrade to dll1 project (copies over your code)====
+=====Project Overview=====
-<cli>
-lab46:~/src/data/sll2$ make upgrade-dll1
-...
-</cli>
-====Step 3. Change into dll1 directory====
+As we started with the last project, we're implementing the remaining functions of our new doubly linked list implementation.
-<cli>
+As such, new function prototypes have been added to the list.h header file:
-lab46:~/src/data/sll2$ cd ../dll1
-lab46:~/src/data/dll1$
-</cli>
-=====Layout=====
+<code>
-This project codebase is largely identical to the sll2 codebase; it merely adds the new files for the doubly linked list and queue functionality. Be sure to check for new files in the following directories:
+unsigned char  rmlist (List **);                  // deallocate empty list
-  * inc - queue.h header and updated node.h header
+unsigned char  obtain (List **, Node **);         // obtain/disconnect node from list
-  * src/queue - source code for the queue operations
-  * testing - queuetest.c file (should work as well as the most recent stacktest)
-=====Queues=====
+unsigned char  compare(List *,  List *, long int *);          // compare two lists for equality
-Queues are frequently considered a peer to the stack data structure, in that the two share many common traits (an underlying linked list) but differ in the restrictions placed upon accessing the linked list.
+unsigned char  empty  (List **);                  // empty an existing list
-It works on a principle of "first-in, first-out" (FIFO), which makes it great to use as a buffer for information (order is preserved).
+unsigned char  sort   (List **, char);            // sort list (according to mode)
+unsigned char  swap   (List **, Node *, Node *);  // swap positions of given nodes in list
+</code>
-Everyone has real-life experience with a queue... every time you have waited in line somewhere; the grocery store, the bank, midnight release of Super Mario Bros. 2... you "enqueue" yourself at the back of the line, and wait- people are dequeued from the front of the line. Eventually, you will get to the front of the line, and when it is your turn, you dequeue.
+These functions will also make use of the status/error codes introduced in dll0. Additional effort has gone into identifying likely codes applied in various conditions. Be sure to reference the provided comments as well as the unit tests for more information.
+====list operation status codes====
+You'll notice the presence of a set of #define's in the list header file. These are intended to be used to report on various states of list status after performing various operations.
-So, with a queue, we only add to the back, and take off from the front. No other aspect of the linked list is modified or accessed under the guise of a queue. This restriction of access creates new possibilities for algorithms, enabling useful functionality.
+They are not exclusive- in some cases, multiple states can be applied. The intent is that you will OR together all pertinent states and return that from the function.
-The basic queue operations are: **enqueue()** and **dequeue()** which will call the necessary underlying list operations (likely **append()** and **getNode()**) while maintaining the **back** and **front** pointers (reflecting some pointer in the underlying list, perhaps **start** and **end**).
+  * **DLL_SUCCESS** - everything went according to plan, no errors encountered, average case
+  * **DLL_MALLOC_FAIL** - memory allocation failed (considered in error)
+  * **DLL_ALREADY_ALLOC** - memory has already been allocated (considered in error)
+  * **DLL_NULL** - result is NULL (probably in error)
+  * **DLL_EMPTY** - result is an empty list (may or may not be in error)
+  * **DLL_DEFAULT_FAIL** - default state of unimplemented functions (default error)
+  * **DLL_FAIL** - some error occurred
-The queue has a **buffer** variable, which unlike the list's **qty** (that keeps track of how many nodes are in the list at any given time), **buffer** mandates a maximum size a queue can be (if the **qty** has reached **buffer**, no new nodes should be added (i.e. **enqueue()**ed)- this is what is known as a **buffer overrun condition**)). For purposes of flexibility, a **buffer** of zero denotes an unbounded queue (it can grow indefinitely, just like a list).
+For example, in the case of "DLL_MALLOC_FAIL", there are actually a total of three states raised:
+  * DLL_FAIL (a problem has occurred)
+  * DLL_MALLOC_FAIL (a problem has occurred when using malloc())
+  * DLL_NULL (no memory allocated, so list cannot be anything but NULL)
-To further test your understanding, you are to implement the queue's **mkqueue()** function this time around.
+ALL THREE states must be returned from the function in question should such an occurrence take place.
+====list library====
+In **src/list/**, you will find the addition of a new set of skeletons of the above prototyped functions, hollowed out in anticipation of being made operational.
-=====Errata=====
+Figure out what is going on, the connections, and make sure you understand it.
-====03/23/2014====
-  * **Update 1**: The issue with stacktest.c would also exist in queuetest.c, so any changes to that need to be forward ported. This has been done.
-  * An attempt to standardize replaced files has been started- any replaced files will be renamed with a **.rev-PREVIOUSREV** extension. So going from rev 0 to rev 1, should now end with **.rev-0**
-=====Submission=====
-To successfully complete this project, the following criteria must be met:
-  * All code must compile cleanly (no warnings or errors)
+Be sure to focus on implementing the functionality from scratch (the more you do this from scratch, vs. referencing old code, the more it will help you).
-  * Code must be nicely and consistently indented (you may use the **indent** tool)
-  * Code must be commented
-  * Resulting libraries must be operational and functionally correct
-    * stack functions must operate as described, conforming to provided function prototypes
-    * code must make use of the other node/list functions as appropriate- do not reinvent the wheel
-    * evaluations of libraries using various unit tests will be an assessment criteria
-  * Track/version the source code in a repository
-  * Submit a copy of your source code to me using the **submit** tool (or **make submit**).
-To submit this program to me using the base Makefile, run the following command at your lab46 prompt:
+====List library unit tests====
+In **testing/list/unit/**, you will find these new files:
-<cli>
+  * **unit-rmlist.c** - unit test for **rmlist()** library function
-lab46:~/src/data/dll1$ make submit
+  * **unit-obtain.c** - unit test for **obtain()** library function
-...
+  * **unit-compare.c** - unit test for **compare()** library function
-Submitting data project "dll1":
+  * **unit-empty.c** - unit test for **empty()** library function
-    -> dll1-20140412-14.tar.gz(OK)
+  * **unit-sort.c** - unit test for **sort()** library function
+  * **unit-swap.c** - unit test for **swap()** library function
-SUCCESSFULLY SUBMITTED
+Enhancements to these unit tests may be provided via dll1 project updates.
-</cli>
+There are also corresponding **verify-FUNCTION.sh** scripts that will output a "MATCH"/"MISMATCH" to confirm overall conformance with the pertinent list functionality.
-You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.
+These are complete runnable programs (when compiled, and linked against the list library, which is all handled for you by the **Makefile** system in place).
-====Saving your work====
+Of particular importance, I want you to take a close look at:
-To submit the project, you will need to create an archive and submit that using the submit tool:
+  * the source code to each of these unit tests
+    * the purpose of these programs is to validate the correct functionality of the respective library functions
+    * follow the logic
+    * make sure you understand what is going on
+    * ask questions to get clarification!
+  * the output from these programs once compiled and ran
+    * analyze the output
+    * make sure you understand what is going on
+    * ask questions to get clarification!
+=====Expected Results=====
+To assist you in verifying a correct implementation, a fully working implementation of the node and list libraries should resemble the following (when running the respective verify script):
+====node library====
+Here is what you should get for node:
 <cli>
-lab46:~/src/data/dll1$ make save
+lab46:~/src/data/dll1$ bin/verify-node.sh
-... make save now issues a pre-emptive make clean ...
+====================================================
-Archiving the project ...
+=    Verifying Doubly-Linked Node Functionality    =
-Compressing the archive ...
+====================================================
-Setting permissions ...
+  [mknode] Total:   5, Matches:   5, Mismatches:   0
-lab46:~/src/data/dll1$ cd ..
+  [cpnode] Total:   6, Matches:   6, Mismatches:   0
-lab46:~/src/data$ ls dll1*gz
+  [rmnode] Total:   2, Matches:   2, Mismatches:   0
-dll2-20140412-14.tar.gz
+====================================================
-lab46:~/src/data$
+ [RESULTS] Total:  13, Matches:  13, Mismatches:   0
+====================================================
+lab46:~/src/data/dll1$
 </cli>
+There were no changes required to the node library between dll0 and dll1, so once you achieved a working implementation, the results should remain the same here.
+====list library====
+Here is what you should get for list:
+<cli>
+lab46:~/src/data/dll1$ bin/verify-list.sh
+====================================================
+=    Verifying Doubly-Linked List Functionality    =
+====================================================
+  [mklist] Total:  11, Matches:  11, Mismatches:   0
+  [cplist] Total:  17, Matches:  17, Mismatches:   0
+  [append] Total:  22, Matches:  22, Mismatches:   0
+  [insert] Total:  22, Matches:  22, Mismatches:   0
+ [display] Total:  12, Matches:  12, Mismatches:   0
+    [find] Total:  28, Matches:  28, Mismatches:   0
+ [compare] Total:  18, Matches:  18, Mismatches:   0
+   [empty] Total:   6, Matches:   6, Mismatches:   0
+  [rmlist] Total:   6, Matches:   6, Mismatches:   0
+  [obtain] Total:  57, Matches:  57, Mismatches:   0
+    [swap] Total:   9, Matches:   9, Mismatches:   0
+    [sort] Total:  42, Matches:  42, Mismatches:   0
+====================================================
+ [RESULTS] Total: 250, Matches: 250, Mismatches:   0
+====================================================
+lab46:~/src/data/dll1$
+</cli>
+=====Submission Criteria=====
+To be successful in this project, the following criteria must be met:
+  * Project must be submit on time, by the posted deadline.
+    * Late submissions will lose 25% credit per day, with the submission window closing on the 4th day following the deadline.
+  * All code must compile cleanly (no warnings or errors)
+    * all requested functions must be implemented in the related library
+    * all requested functionality must conform to stated requirements (either on this project page or in comment banner in source code files themselves).
+  * Executed programs must display in a manner similar to provided output
+    * output formatted, where applicable, must match that of project requirements
+  * Processing must be correct based on input given and output requested
+  * Output must be correct (i.e. the list visualization, where applicable) based on values input
+  * Code must be nicely and consistently indented (you may use the **indent** tool)
+  * Code must be commented
+    * Any "to be implemented" comments **MUST** be removed
+      * these "to be implemented" comments, if still present at evaluation time, will result in points being deducted.
+    * Sufficient comments explaining the point of provided logic **MUST** be present
+  * Track/version the source code in a repository
+  * Submit a copy of your source code to me using the **submit** tool (**make submit** will do this) by the deadline.

Lab46 Wiki

User Tools

Site Tools

Differences

Page Tools