All EoCE related tasks are as done as they will ever be.

Just finished re-writing my stack and queue demonstration programmes, and adding them to my portfolio. This time I won't lose them…

My written responses to 0x0, 0x4, and 0x5 have been finished.

I have realised that I haven't updated my Opus in a while, in spite of some work being done. During this time frame, we've gone over stacks, queues, some stuff with binary trees, and our linked lists knowledge assessments. So, to start, I'll provide a brief description of these newly introduced data structures.

Stack - Very similar to a linked list, but data in it can only be accessed via a pop() which removes and returns the most recently push()ed data (or, optionally, a peek() function, which just returns the most recently push()ed data), and data can only be added to the end (or head, it's all relative, and heads are ends) of the list via the aforementioned push() function.

Queue - Similar to the stack in that it is a restricted linked list, data can only be push()ed at the end of the list, but what differentiates it from the stack is data can only be pop()ed from the beginning of the list. If we describe the stack as a 'first in, last out' structure, then the queue is a 'last in, last out' structure.

Tree - A tree is a data structure that is also similar to linked lists, in that they are composed of nodes, but that is where the similarity ceases to continue. Linked lists, stacks, and queues are all linear in nature. Stacks and queues, however, gain their utility by placing restrictions on what you can do with the data they store. Trees are not, however, linear. Trees let you branch your data out, showing different relationships between the data (such as in a family tree, a pre-Information Age example), and it's these branches that make the tree useful; the branches can be used to effectively sort the information. If information is already sorted, it makes it a bit easier to search for a specific piece of data, or to expand your information set. This is not, however, a requirement to use a tree; not all trees are pre-sorted.

Binary Tree - Like the stack and queue gain utility by limiting the user's ability to use the data within the linked list implementing their structure, the binary tree places certain requirements on its structure as well: a binary tree is a tree whose nodes have no more than two children nodes. Binary trees provide the fundamental structure needed for binary search trees and binary heaps to be implemented (the latter of which, according to Wikipedia, can be used for sorting data, such as using heapsort, or for implementing a priority queue).

I had intended to include more things in this Opus update, such as links to the code for my stack demonstration programme, but I seem to have gotten a little overzealous in cleaning my home folder. I'll rewrite it sometime soon and upload it, along with one for queues and binary trees.

Oh, and another thing we've gone over is Makefiles. Makefiles are, simply put, a set of requirements that get passed to the make(1) command, which, according to the GNU man page exists to “determine automatically which pieces of a large program need to be recompiled, and issue the commands to recompile them”. So, clearly, make can be used to compile programmes where only (relatively) small changes have been made to the source code, but this doesn't entirely do make justice. Makefiles also often feature so called “targets”, such as debug or release, that permit different compiler switches to be used for each target, such as -g for debug, which could be undesirable in a finished product going to market. An oft defined make target is clean, which removes all the object files found pertaining to the project, thereby forcing a complete recompilation of the source code next compilation. The main utility of make is that it allows the programmer to compile his projects without needing to remember each and every compiler switch for each and every set of translation units he wishes to compile, reducing errors significantly, saving time, monitors, and keyboards and reducing fits of rage in the process, contributing to a reduction in stress levels for programmers everywhere and therefore to public health, and by contributing to public health improves our nation as a whole. Clearly make is a beautiful utility.

Save for shuffle() and deal(), my card game objects and functions are implemented, albeit admittedly untested.

Classes:

• Card (Basic Class)
• Cell (Contains a Card (possibly will change to a pointer to a card), and has a function “bool is_empty()”)
• Cascade (Basically a wrapper for a DList<Card> from my ltdl.hpp file)
• Foundation (Basically a wrapper for a Stack<Card> from my ltstack.hpp file. Does *not* have a pop() function defined (although Stack<T> does provide one, it doesn't make sense to allow it in this class))

Functions not Part of Classes:

• colour_opposite(Card, Card)
• mv_card(T1 src, T2 dest) (Overloaded function for all possible pairs of Cell, Cascade, or Foundation, where src is not of type Foundation. It wouldn't make any sense since we can't pull from the foundation stacks in Free Cell)

By this point my doubly and singly linked list templates are as implemented as they will be (doubly contains a simple sort algorithm, node swapping function, append, prepend, insert before and after, clear, find node, grab, delete, remove, and eliminate node, and append list; the singly linked one contains all these but swap_nodes()). append_list(DList<T>* list) is implemented but has thus far remained untested. I may get around to that this weekend; I may not. It's not terribly important because it's functionality can be achieved by finding the head node in the other list, appending that to the current list, setting the current list's tail to the other list's, adding the other list's size to the current list's, set destroy to false in the other list, and call the other list's destructor. C'est très facile. In other news, I have also started implementing my Free Cell game. Some core functions have thus far been defined and I am working out an idea of how I want to render it on the console. I will likely make use of unistd.h to grant access to clear. Why do more work than necessary? The player will only be able to move a single card at a time, as I will not be complicating the mv_card() functions with checking and moving ranges of cards. Basically, my Free Cell game will be little more than a rules enforcer and card display programme. Oh, also, I have implemented (but not tested) my own Stack template. It implements pop, push, and peek functions, and allows for toggling the deallocation of the list when ~Stack() is called. It uses a singly linked list of nodes to provide it's functionality. Encore, c'est très facile.

Sorting in the doubly-linked list is complete. It appears to be a selection sort; all I know for certain is that it is rather inefficient.

My (doubly && templated) linked list programme is nearly complete. Just finished defining and testing swap_links(DLink<T>*, DLink<T>*) and it seems to work fine. The class template is also in it's own header file now, so porting it to use in a library later on down the road will be easier to do. The only thing currently preventing the header from being a good general library is it still does some of the I/O for the demo programme. There are also some link manipulating functions that I'm thinking about overloading. Some of them take an unsigned long as their parameter, but I think it might also be useful to provide a version that takes a DLink<T>* as a parameter, so while running, if you have a pointer to a node you know is in the list you want to remove, you can remove it without having to waste a whole lot of cycles trying to get to it first. The only problem I'm seeing with that, however, is trying to verify (either within the function, or the user verifying before calling the function), that the node is in the list, and doing this verification more efficiently than cycling through the list.

Edit: Possibly using some sort of index value in each node could provide the efficiency needed. However, it would make each insertion, append, and remove/delete function take longer, as the indices of all nodes after the node in question in each of those operations would also need to be updated.

I asked Matt to bludgeon my programme a few times in an attempt to find more errors than I could catch right then. Fixed most of them. Also began reworking my doubly linked list hackery concoction into a bonafide C++ class, even supporting templating the data type of the list (ie, it supports any data type a C++ compiler will compile).

I fixed the error today (well, technically last night at work, but implemented today) in the deletion of the head node. I just made it check whether it was NULL or not before running delete and moved my pointer to the list to the node after the head. It now also behaves correctly on the tail node.

I've been working on the Linked List Demo Programme, and I have some of the functionality implemented, albeit with some potential quirks. My remove process works perfectly fine in the middle of the linked list, but when I go to remove either the tail or head nodes, their value becomes random gibberish. The odd thing about it is the head node still points to a valid node (the end node, after all the stuff in the middle is deleted, which I thought should have been deleted). Attempting to delete either node again, logically enough, results in glibc detecting a double-free error and stops the programme. Below is the detailed view of the head and tail nodes after 3 nodes between them were deleted.

Choice: D
Link[0]->value: 33304624
Link[0]       : 0x1fc3010
Link[0]->prev : 0
Link[0]->next : 0x1fc30d0
Link[0]->begin: 0
Link[0]->end  : 0x1fc30d0

Link[1]->value: 33304576
Link[1]       : 0x1fc30d0
Link[1]->prev : 0
Link[1]->next : 0
Link[1]->begin: 0
Link[1]->end  : 0x1fc30d0

Oh, as far as the working functionality goes, it can build the list (obviously), there are two functions to print the list, the aforementioned detailed view, and the graphical representation we used in class, append (as in add to the end of the list, not insert after a specified node), and exit.

Edit: The double-free error seems only to be affecting the head node… it seems to properly delete the tail node if it gets deleted twice. Very odd.

I suppose I'm a little late to doing a first Opus entry this semester; c'est la vie je suppose. I completed the data types project today, in C++. In order to get it to correctly do the math provided in class and display it via std::cout correctly, I had to create secondary variables to hold the intermediate value and typecast this secondary variable while using std::cout; I haven't quite determined *what* std::cout is doing to the temporary variable to mangle it that it isn't doing to the secondary variable. Below is a little snippet:

signed char sc = 0; signed char sc2 = 0;
std::cout << "              Size of signed char: " << sizeof(sc) << "B" << std::endl;
sc2 = (unsigned char)(sc - 1)/2 + 1;
std::cout << "       Lower bound of signed char: " << (signed int)(sc2) << std::endl;
sc2 = (unsigned char)(sc - 1)/2;
std::cout << "       Upper bound of signed char: " << (signed int)(sc2) << std::endl << std::endl;

This has the corresponding output:

              Size of signed char: 1B
       Lower bound of signed char: -128
       Upper bound of signed char: 127

The data types I covered in this programme include both the signed and unsigned variants of char, short int, int, long, and long long, in addition to bool (again, standard C++ bool, not bool as defined in <stdbool.h> for C99).

Now it's time to continue my work on a spaceship game (ultimately it might resemble something like Space Invaders but with space ships instead of aliens, and random flying asteroids and no shields). Oh, and I seem to be unable to commit changes to my Mercurial repository (in spite of a ~/.hg/hgrc being defined per the Mercurial configuration tutorial for the class && in the repository itself (~/src))… I suppose it's not the most important thing to solve right now however.