Friday, 23 November 2012

How does it work?

What is it?

The program is an employee time scheduler for employers. It was made with the idea that Ron’s mother needed software that allowed her to keep track of all of her employees. Thus we created a simple time keeping solution.
Our solution allows the user to add employees by adding data files to the folder 'docs' – It has to only contain the name of the employee and a return to a new line. The rest will be taken care by the program. Deletion is also as simple as just deleting the desired employees data file.
When you launch the program you are able to see all of the employees of your company and their `status` - if they are Check In or Checked Out. (Currently in the `Office` working or not)
Then it allows the user to
                    change the status of the employee by just writing in their ID. This also stores the time of the status change in the data file.
                    print out all of the times the employees were at work by typing 88

The Code


As a main data structure we used a fixed size array of Structs to hold employee data, each Struct contains variables for employee details, name time etc.

The main function calls the function listContents and passes a reference of the variable numberOfEmployees to it. The listContents method returns char **, this is a pointer to char array, which in turn is a string containing the file names of the files where the employee data is stored. Due to the fact that number of employees was passed as a reference we are able to modify it so the rest of the program knows how many employees there are. This is done by reading the files from the specified directory, checking the file is valid,  if not valid it returns a NULL pointer, otherwise, using the dirent library we read in all of the files in the directory. We had use a conditional statement to make sure we were only reading correct files, not system links ( . and .. ). When adding file names to the array we had to malloc space for each character array created.

After the arrays of filenames have been returned, the function readEmployeeFile is called. This function opens up each file that has been added to the array created in the previous function. This then initialises and sets up the array that is used to store our employee Structs. After reading the file, it parses the data from the file and creates a Struct from the data contained and adds this to the array.
After all of this initialisation, main then calls mainMenu function. This is a continuous loop that displays the menu to the user using the terminal and waits for user input. If the user enters 99, the program terminates. If the user enters 88, the program lists all employees with how long they have been “clocked in”. This is achieved by looping through the array of Structs and printing out the information contained in each Struct. If the user enters a user ID, the program first checks if it is valid input and if the employee exists. If these checks fail it prompts the user to re-enter a valid choice. If the user selects a valid ID then the function changeStatus is called.
This function firstly checks to see if the user has clocked in already, then updates the time variable in its corresponding Struct, and writes the time to the employee file. It calculates the difference between start time and end time using the time library and prints out to the user how long they were clocked in for. It does this by appending the start time and total worked time to the employee file. If the employee wasn’t “clocked in” the function only adds the start time to the Struct, and the user is now technically “clocked in”.

From JAVA to C: Spot the Difference.

10 weeks ago we were tasked with creating a program in the JAVA programming language, primarily to get ourselves refreshed with some coding after a lazy summer, but also to use as a comparison piece for our final project in this AC21008 programming module. We had an idea that we may have to return to this JAVA program, we were correct, after learning C++ and C we were asked to go back to our week 1 program, and re-write it in the C programming language. Easy, you would think, however C is a very different programming language from JAVA and a lot of our JAVA code had to be either scrapped, or totally re-written to give the same functionality.


Firstly, let’s talk about the main program structure. Our JAVA program had to adhere to the Object Orientated Programming model; Encapsulation, Inheritance and Polymorphism. In JAVA you cannot code in any other way, you MUST use classes otherwise your program is not going to work. Even for the simple “Hello World” program you have to create a class, then run a method contained in the class that prints “hello world” to the screen.
Our JAVA implementation had 4 classes in the final version; Clock, AdminGUI, Controller and Employee. Both Clock and AdminGUI are classes that handle our GUI interface, which could have arguably been merged into one GUI class, however, it’s the Clock and Employee class that contain the main program functionality. The Employee class is used to store data for each employee our program is working with; it contains the fields for the employee’s data, and the setter and getter methods for these fields. Our control class creates objects of type employee, using the accessible methods to set the details of each new employee created, and stores these employees in an array, ready for clocking them in and out, handling their files and working with the time library. The 2 other classes handle the GUI, one makes the basic menu that’s shown to the employees, the main interface of the program and the other creates the admin panel which is used by the manager to review clocking times of the employees. Standard Object Oriented Programming.

Moving to C:

I will always remember the first lecture we received from Karen about the C programming language, “As programmers you will feel like your arms have been chopped off”. She wasn’t joking! The first thing on the list of removed functionality in C was Classes. Wait, what? No Classes? At all! After relying so heavily on them in JAVA and slightly in C++ we had to change our approach to our C program. Enter, the Struct. A Struct is used in C for grouping together variables of the same or different types, which can then all be referenced using the name of the Struct used,  perfect for creating a Struct for our Employee’s. It should be noted that we could have exclusively used files to store all the data we needed, with each file containing an employee, their details and the code would just modify the files based on input, but this would have been messy and the Struct contains everything we need. Our JAVA program used an array to store employee objects; in the end our C program did the same, an array holding Structs. We did initially start with a linked list of Structs, but we had to scrap that plan, it ended up being far too complicated and we realised that we don’t actually have to add new employees when the program is running.  The arrays are defined in the code so it is of a fixed size, however, if more employees are required, the array size can be changed without issue and the new employees loaded from file as per normal.

This takes us nicely onto the next concept we have to deal with, memory use. In JAVA the language itself manages memory use for us, if we create an object, it knows how much memory space is needed and then discards it when the object drops out of scope. C does this to a certain extent, variables declared at global scope and static variables defined in functions all get memory allocated at program execution and have their memory freed once the program is complete, the program knows how much space these will take up as they are fixed. All well and good, but what if we want to return an array from a function? For example, in our C code we have a method that counts how many user files are contained in the program folder and uses an array of pointers to store the file names for use in other functions. This method returns an array of pointers that can change in size, depending on how many files are in the folder. In JAVA we could initialise the array in the method, fill it up then return it no problem at all. In C, it’s a different story. This array is not of a static type and can change in size when the program is executed. The program has no idea how much memory space it will need when executed so we have to do it ourselves in the code. This is where we use the malloc command in C to assign enough memory for our array. The size required is counted first, then we malloc the required space, fill the array up then return it. Conversely, we have to take note of how much memory our method is creating so we can then free it once we no longer need it. In our code we only every use one non static array, and the space for it is only created once the program is executed, then this memory is given back to the OS once our program stops. However, if we were using a large data base program, with multiple malloc calls we would have to free up any memory that is no longer required using the free command. If you don’t do this, you will end up with a memory leak; we have assigned space but are no longer using it, causing the program to slowly fill up your computer’s memory until it either gets so slow or the computer crashes. If you malloc it, you free it, end of story.

The final major difference between our JAVA and C implementation is the fact that our C program has no GUI. In JAVA we used the Swing library which was easy enough to work out how to use ourselves. Almost like CSS in HTML coding, our basic terminal program was the HTML and we plugged in the Swing GUI on top, similar to how a style sheet works. However to implement our program in C we would have had to use the GTK+ library, just looking at the code for it was enough to give us nightmares, it is pretty complex, for example the GNOME desktop environment for Linux is written using GTK. This wasn’t too much of an issue though, the C programming language is not designed for creating fancy front end programs, more for creating backend functionality, such as OS Kernels, device drivers and embedded systems for example. The terminal implementation we generated in C feels nice and clean cut though, it tells what you need to know, and most of us have been using Linux, which is very much a Command Line Interface OS, rather than the GUI driven Microsoft Windows.

All in all we have managed to create the same functionality, in C as we did in JAVA. We feel that our C version is far more efficient than our JAVA implementation. It does the same job with less space and less lines of code. Even after presenting we have noted areas that could be improved, for example implementing functionality to add and delete employees using the program, rather than editing files.
The complete Program in C, but without the file tree.
The files needed to run this program include a folder in the same directory as the program called "docs". In this folder, create one textfile per employee. THe name of the textfile may be anything random, as what counts is the first line of the textfile, which must be the employees full name.
After you've saved and closed the textfile, run the program, and it will take over from that point onwards. The program will read the name in the file and add the employees times at work. To add more employees, just create new textfiles in the docs folder, to delete employees, just cut or delete the textfile from the docs folder.

#define ANNOUNCE printf("Line %d\n", __LINE__);
#include <stdlib.h>
#include <dirent.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <time.h>
#include <memory.h>


char fileNameToBeOpened[50] = " ";    // Name of file to be opened
char oldFile[365];                       // The old file, one place for each day of the year
char** fileNames;                     // A pointer to filenames.

int numberOfEmployees = 0;              // Holds the number of employees found
time_t timeNow;                          // Needed to calculate the time
double timeElapsed;
struct tm *now ;

char buffer[100] ;

struct employee             //this structure represents one employee
{
  int present;                 //is 0 if the present is away and 1 if present
  char name[50];             //holds the name of this employee
  int startTime;            //holds the starttime for that session
  int startTimes[364];        //holds the start timesof this employee
  int timesPresent[364];    //holds the times the employee was present
};

struct employee employeeArray[20];     //an array of employee structures

//sets the employees status to the new status
void changeStatus(int i)
{
    if(employeeArray[i].present == 1)
    {
        employeeArray[i].present = 0;

        //calculate time elapsed between logging in and logging out
        long currentTime = time (NULL);
        timeElapsed = currentTime - employeeArray[i].startTime;

        //add elapsed time to the file
        char fullFilePath[150] = "docs/";
        strcat(fullFilePath, fileNames[i]);

        FILE *newfile = fopen(fullFilePath, "a"); //open the specified file

        fprintf(newfile,"%d\t", employeeArray[i].startTime); //write current time to new file
        fprintf(newfile,"%lf", timeElapsed); //write elapsed time to new file   
        fprintf(newfile,"\n"); //a line break to the new file

        fclose(newfile); //close and save the file new file

        //get the time in a human readbale format
           timeNow = timeElapsed ;
           int hoursAtWork = timeElapsed/3600; //get the number of hours the worker worked for
           timeElapsed = timeElapsed - (hoursAtWork*3600); //subtract the hours from the time

           int minutesAtWork = timeElapsed/60; //get minutes employe worked for
           timeElapsed = timeElapsed - (minutesAtWork*60); //subtract minut es from time, leaving seconds

           printf("\n---------------------------------------------------");
           printf("\n\t Employee was at work for: %d:%d:%d", hoursAtWork, minutesAtWork, (int)timeElapsed);
    }
    else
    {
        employeeArray[i].present = 1;
        //insert the current time as start time
        employeeArray[i].startTime = time (NULL);
    }
}

//reads a single employee file into memory
void readEmployeeFile()
{
    int i;                          //for for loop
    int x         = 0;               //for small nested loops
    int line      = 0;
    int nameFound = 0;             //set this to 1 if the name is found already (in line 1)
    int tempPresentTime;
    int tempStartTime;
    char tempName[50];
    char tempStartTimeArray[50];   //needed to take the number from the file
    char tempPresentTimeArray[50];   

    int whichTime = 0; //holds which time we read in, 0 for starttime, 1 for timePresent

    //open every single file of every employee in the array
    for(i = 0; i < numberOfEmployees; ++i)
    {
        line      = 0;
        x         = 0;
        nameFound = 0;    //this holds weather the name in the first line has been found

        char fullFilePath[150] = "docs/";
        strcat(fullFilePath, fileNames[i]);

        FILE *file = fopen(fullFilePath, "r"); //open the specified file

        if ( file != NULL ) //check if the file specified exists
        {
            char ch;        //this variable holds the value of one char from the file

            while ( (ch = fgetc(file)) != EOF ) //take char by char from file
            {
                if(nameFound == 0)
                {
                    if(ch != '\n') //add the char to the name of the employee
                    {
                        tempName[x] = ch;
                        tempName[x+1] = '\0';
                        x++;
                    }
                    else //reading in name is completed
                    {
                        x = 0;
                        while(x < 50)
                        {
                            employeeArray[i].name[x] = tempName[x];
                            x++;
                        }
                        nameFound = 1;
                        x = 0;
                    }
                }
                else
                {   
                    //we're reading the rest of the file, which is only the times
                    if(ch == '\n') //if a new line is read
                      {
                          //we assume we now have two ready variables holding the values from the line of the file
                          tempPresentTime = atoi(tempPresentTimeArray);
                          //printf("Employee %s\n", employeeArray[i].name);

                          employeeArray[i].startTimes[line] = tempStartTime;
                          //printf("Temp Start Time: %d\n", employeeArray[i].startTimes[line]);

                          employeeArray[i].timesPresent[line] = tempPresentTime;
                          //printf("Temp present Time: %d\n", employeeArray[i].timesPresent[line]);

                          x         = 0;  //reset
                          whichTime = 0;     //reset
                          line++;            //presume to next line
                      }
                      else
                      {
                          if(ch == '\t')
                          {
                              whichTime = 1; //we now take the time Present

                              //convert the start time to a integer
                              tempStartTime = atoi(tempStartTimeArray);
                              x             = 0;    //reset to start second variable array at 0
                          }
                          if(whichTime == 0)
                          {
                              tempStartTimeArray[x] = ch;
                          }
                          else
                          {
                              tempPresentTimeArray[x] = ch;
                          }
                          x++;
                      }
                }
            }
            fclose(file); //close and save the file old file
        }
        else
        {
            printf("File could not be opened!\n");
            printf("FileName to be opened: %s\n", fullFilePath);
        }
    }
}

//prints all the times found from the file
void printTimes()
{
    int i;
    int j;
    int hoursAtWork;
    int minutesAtWork;

    printf("Times Employees were at work:\n");

    for(i = 0; i < numberOfEmployees; ++i)
    {
        printf("\n\t%s\n", employeeArray[i].name);
        printf("Time Present: \t\tDate:\n");
        j = 0;   

        while(employeeArray[i].startTimes[j] != 0 || employeeArray[i].timesPresent[j] != 0) //while one still has content
        {
               timeNow = employeeArray[i].startTimes[j] ;
               now = localtime( &timeNow ) ;

               timeElapsed = employeeArray[i].timesPresent[j];

            //get the time in a human readbale format
               hoursAtWork   = timeElapsed/3600;                 //get the number of hours the worker worked for
               timeElapsed   = timeElapsed - (hoursAtWork*3600); //subtract the hours from the time
               minutesAtWork = timeElapsed/60;                   //get minutes employe worked for
               timeElapsed   = timeElapsed - (minutesAtWork*60); //subtract minutes from time, leaving seconds

               printf("%d:%d:%d\t\t\t", hoursAtWork, minutesAtWork, (int)timeElapsed);
            printf( "%s" , asctime( now )) ;

            j++;
        }
    }
}

/**
 * A function which returns an array of all user data files.
 *
 * @param  num : Used to return the number of files
 * @return char* to the array that contains the info.
 */
char** listContents(int* num)
{
    DIR * dp;
    dp = opendir("docs");   // The dir where user files will be located.
    struct dirent *dirp;
    char* fileName;

    int count = 0;

    if(dp)
    {
        // Just count how many files are in the dir.
        while((dirp = readdir(dp)) != NULL)
        {
            count++;
        }

        // Remove 2 as, the dir lists '.' and '..' as files.
        count -= 2;
       
        // CHANGE: Use num to return the count
        *num = count;

        // CHANGE : Have to reset the dir (or we could make a new one)
        rewinddir(dp);
       
        // So if actually found any files.
        if(count > 0)
        {
            // Array of pointers to store the file names.
            char* userFiles[count];

            // Restart the read again, but now read the info in the array.
            int i=0;

            while((dirp = readdir(dp)) != NULL)
            {
                fileName = dirp->d_name;

                // CHANGE: You can't use sizeof to get the length of a string, only an array. Use strlen
                if((fileName[0] == '.' && fileName[1] == '.' && strlen(fileName) == 2) || (fileName[0] == '.' && strlen(fileName) == 1))
                {
                    // Do nothing as reading '.' or '..' dirs.
                }
                else
                {
                    // CHANGE: Make a copy of fileCopy. Note we use strlen and strcpy
                    // as we are copying strings
                    char* fileCopy = malloc(strlen(fileName) + 1);
                    strcpy(fileCopy, fileName);
                    // Add the file to the array.
                    userFiles[i] = fileCopy;
                    i++;
                }
            }
           
            // CHANGE: Make a copy of userFiles.
            // note the use of malloc / memcpy.
            // NOTE: This will not recopy the filenames which this array points to.
            char** userFilesCopy = malloc(count * sizeof(char*));
            memcpy(userFilesCopy, userFiles, count * sizeof(char*));
           
            return userFilesCopy;
        }
        else
        {
            // No files found, return null.
            return NULL;
        }
    }
    else
    {
        // No files found, return null.
        return NULL;
    }
}

void mainMenu()
{
    int i;   
    int user_Choice = 0;
    int continueLoop = 1;
    while(continueLoop == 1)
    {
        printf("\n---------------------------------------------------\n\n");
        printf("AC21008, Group 11 \n\tClock Main Menu\n\n");
        i = 0; //holds count of the number of employees we have
        for(i = 0; i < numberOfEmployees; i++)
        {
            if(employeeArray[i].present == 1)
            {
                printf("%d) %s \tis in.\n", i+1, employeeArray[i].name);
            }
            else
            {
                printf("%d) %s \tis out.\n", i+1, employeeArray[i].name);
            }
        }

        printf("\nSelect the employees number, to check in or out.\n");
        printf("Select 88, to print times employees were at work\n");
        printf("Select 99, to Quit\n");
        printf("\n--> ");

        //get user input
        scanf("%d", &user_Choice);
        if((user_Choice >= 1 && user_Choice <= numberOfEmployees+1) || user_Choice == 99 || user_Choice == 88) //allow chars or digits only
        {
            // Check if a selected choice is a user.
            if((user_Choice-1) >= 0 && (user_Choice-1) < numberOfEmployees)
            {
                // Clear the screen.
                system("clear");
                changeStatus(user_Choice-1);
            }
            //the other menu choices
            if(user_Choice == 88) // list all times of employees
            {
                //get the latest data from the file
                readEmployeeFile();
                //print the data
                printTimes();
            }
            if(user_Choice == 99)
            {
                printf("\nBye bye!\n");
                continueLoop = 0;
            }                 
        }
        else
        {
            printf("Please select a valid choice!\n");
        }

        if (fgets(&user_Choice, sizeof(&user_Choice), stdin)) //this line clears the buffer
        {
          //we could print the last character in the input, but we dont
        }
    }
}

int main()
{
    // Clear the screen.
    system("clear");
    // Create an array of all the employees.
    fileNames = listContents(&numberOfEmployees);
    // Read all employee files and load in data.
    readEmployeeFile();
    mainMenu();
    return 1;
}

Friday, 2 November 2012

Another week, another language.
This week we started looking at c. Prior to having had my first look at c this week, I was rather scared of c, as it was pronouned to be that really basic language. It turns out that it probably lacks some functionality that we're used to using in our code, but that in general its the same thing as c++, just without the shortcuts.

Looking back at assignments two and three, namely the hash table and the templated hash table, I personally have very differed views. The hash table I had implemented and running in a matter of four hours, and it works fine. Maybe not the most stablke code ever, but fine enough for normed use. THe templated hash table, didnt work at all for me and I shudder thinking back on the piece of crap I submitted... full of errors to the extent that I would call the assignment an error. I really think I'll need to revise templates, as thats the only part I dont understand about the project, but I'll procratinate that to some point in time before the exams.
Back to the untouched, or rather unprogrammed, subject of c. C compares to c++ in many ways, and only really differs in some "details". The quickest way to compare the two is to name what c doesnt have in comparison to c++: classes and members, derived classes and virtual functions, templates (juhuu), inline functions, exceptions, function overloading, new/delete, references, const in constant expressions and c++ standard libraries. Around most lacks, there are workarounds, so you can use struct and global functions instead of classes, macros instead of templates and pointers instead of references.
The next assignment, the binary tree in c, proves these possibilities. We will need pointers and nodes to make the hash table, and that possibility proves the main functionality of c, which provides the most basic functions, just not the fancy bit like templates, which I wont miss a second. Using c may become the next big thing, for "regular" programming. I dont think I'd use c for games or applications, but using c for assignments like the binary tree makes sense, as the functionality of the language allows for it, and the code will be the most efficient with c.
We learned this week that the most fundamental program running our systems are written in c, like drivers, compilers and operating systems. Therefore c, in my point of view, is there to be used for programs that have to be extremely stable and efficient at the same time. This week was unlike other weeks in a second (or fifth) aspect. We had a guest lecture from Dr. Christopher Jefferson. Dr. Jefferson gave us a different approach on templates and highlighted some techniques of using them. Next to the extreme coding speed he presented to us, he later on through his presentation begann talking about his work on the c++ committee. I found it most interesting and thoughful how the c++ committee accepts and rejects ideas. Unlike the common sense may judge, when a new idea is presented, the concept of c++ would never be changed without respecting the possible effect on the existing code. So any changes must be so minor, or happen parallel to the existing versions, that any code will resume working without being affected by the next version of c++. Ever since this presentation, I have the feeling that on the c++ committee, there are probably the brightest people our world has to offer, only judging them from their readiness to reject their own brilliant ideas for the benefit of existing code, however faulty it might be programmed.
This week we also learned about binary trees. I'm not sure what to say I learned, as I effectively saw nothing new on that subject. I have given binary trees a lot of thought last year, when we made a java implementation of a binary tree for a dictionary, using 50000 terms per language and six languages. Loading the data into the binary tree took approximately two seconds, and translating documents took something in the tenthousands of a second. Of course the translations were shit, but the efficiency was stunning. For this project I had already given binary trees a good thought. So we had developped deleting functions for any node in the tree, balancing the tree and of course doing all the simple stuff. If I had to prepare the next giant data structure, I think I would go for a combination of data structures to reach the greatest efficiency possible. Right now, I would go for a combination of a hash table and a binary tree. What I'm thinking of, in the example of a dictionary, is to have a hash table for each possible beginning letter, so 26 buckets, and a binary tree in each bucket. It may not increase efficiency enormously, but the thrill of using two such structures together is high.

In relation to other courses, I must say that the AI module has drifted off to truth tables and other cryptic, mystical activities no one seems to understand, while the computer systems course is riding in the draft of this module. So in computer systems, for next Wednesday, we're supposed to make a Cellular Automaton in c++ or c. That seems like an assignment we should be getting in this module, and not seldomly do I wonder off into the wrong module site on blackboard to search for the CA assignment sheet. I am not sure where the computer systems module is heading, starting to give us c and c++ assignments now, but ok, any practice is welcome and will benefit us. As long as we don't do the same assignments over and over again.

The complex & the not so Complex

Hi Everyone!

T'is me Rihards. Sorry for the delay on the update - was thinking all week about the talk I am to give tonight on DUCS.

Anyway  - the assignment was difficult in the best way utterly possible! I really mean that. It most defiantly was not easy ( for those that found it too easy - you know you could have amped up the difficulty easily ) .

I learned a lot of things that passed by or did not quite click with me. Programming (doing) is the best way to learn.

I found that the trickiest part in the program was handling all those different type OA hashtables. There were some other tripping stones but they are there always.

~ ~ ~

Polymorphism in OOP:  is basically the ability to create a variable, a method, or an object that has more than one form. Like different template types, parameters and other things

Virtual method: a method whose behavior can be overridden within an inheriting class by a method with the same signature. This usually goes hand in hand with polymorphism. Simply put - you just have to put 'virtual' in front of the method and it can be overwritten by inheriting classes.

Capability Classes: Sorry, I think I missed this one. 

Abstract Data Types: They are classes / collection of data & associated operations made for manipulating data. (Queues, Stacks, Hashmaps (Like the ones we made) )

Separating C++ code into several files: There are ways to make code more  readable and optimal. Splitting it up in several files is one way & after some point its a necessity. You can write a header file (.h) that has all of the includes and other things the program will reuse then include that .h file into the files that do the operations. There's even a special way to compile these kind of programs.

Default algorithms from the algorithms standard library: Iterators, std::find, list :  splice, sort, merge, remove and others.

Set Library: Sets are a type of associative container that stores unique elements, and in which the elements themselves are the keys. Like Queues, Lists, Binary trees. They make refereces to objects just like them thus making lists. Set Library includes all the basics of a set.

Map Library: Maps are a kind of associative container that stores elements formed by the combination of a key value and a mapped value.

Iterator: any object that us pointing to some element in a range of elements (such as an array or a container) and has the ability to iterate through the elements of that range using a set of operators (at least, the increment (++) and dereference (*) operators).

Iterator Example: If you had to iterate through a Hashmap one after another.

Relation to JAVA: We did a lot of these things last year.

~ ~ ~

Lists: One object pointing to the next object.
Stacks: FILO
Queues: LILO

List: I would use them for example for times I don't know the length of the elements needed to be added
Stacks: I would use them to store Undo commands.
Queues: A custom service caller system. So that the first caller calling in get the service the fastest.
Comparison & Contrast: The complexities of Lists, Stacks & Queues in comparison to Hashtables, Arrays & Vectors, I would say are greater. Lists, Stacks & Queues use more resources than the previously taught data structures.

~ ~ ~

I would dare say that nothing we learning in any other course had any relation with the things we learned in C++. 

Tuesday, 23 October 2012

Int *info = new int [10^6];

Currently it seems that the second assignment is not going to be too complicated, as it is similar to the first hash table assignment, though it’s too early to judge, as I have not yet started to work with templates, and it is known that mystical things may appear when porting your application to support templates.

A quite useful thing that we learnt last week is ‘Templates’, which gives the ability to re-use code, by allowing to pass various data types that aren’t pre-defined. This can replace function overloading. As an example I could mention a function that saves everything passed to it to a file. In this case you could use function overloading or, you could just use templates and have only one function. This principle is the same for classes when trying to implement containers – a class which works with multiple data types, having ‘fields’ with no specific data types specified. An example could be a class which compares, multiplies and divides two fields. To use this class with doubles we would need separate fields for each data type, also function overloading would be necessary. 

Another useful thing that we learnt is pointers, which are just a variable that contains a memory location to a different variable. Pointers can be used in several different ways. I usually use pointers when using a method it is needed to modify an array which is a field, as it is just the easiest way  an array from a method, as returning the pointer of the array is the easiest way to return this data structure. Knowing that a pointer is just an address in the memory we can increment the pointer to get the next element in the memory which may be useful as values that are stored in an array occupy consecutive memory locations. One of the most useful operation that you can do with pointers, in my mind, is passing them to a function. You would use this when there would not be a need to create a new copy of the objects passed to a function, for example a very large array. You also can use pointer to an array to be able to change its size in the constructor, when it is defined as a field. You might use an array of pointers to store pointers to char values that form a string.

Also besides pointers we were taught about references, which basically is just creating another name to a variable, just an alias for a variable. Although during the lectures it was said that pointers and references are similar, I disagree as the differences outweighs similarities. If I would need to decide between using an reference or a pointer I would probably decide to use a pointer as it has a wider range of options. Opposite to references, pointers can be declared without initialization and they can be reassigned, so they point to a different memory address. Either it is my exhausted brain or I really cannot think of an example right now where using a reference would be better than using a pointer.
Regarding the data structure topics that we discussed this week I did not find anything new about the big O notation, as it is just a bit of extensions of primary school knowledge. The big O notation is a way of characterizing a function that represents space / time complexities to a general solution by removing constants & smallest functions, by just taking the dominant function, so it would be possible to compare multiple complexities from different algorithms. 

Comparing the complexities of arrays, vectors, chained hash tables and open addressed hash tables I have to say that in the big O notation they all are the same though each of them might take up more / less time as the big O notation states only the dominating function, so there is no chance to see small differences between these complexities if using big O notation, which would not be good in cases when you have to work on a project that has a small memory or which needs to run for a very precise time.

Of course AC12007 first week contents are similar to the big O notation topic that we had on Thursday, as it is what we learned there.
Although each week is different and it is hard to predict what will happen, I assume that we will finish off C++, get some extra knowledge on things that we might use in our assignment and slowly switch to C.

Sorry for the weird structure of sentences and paragraphs, as I was not able to go through the whole text again.

Thursday, 18 October 2012

So, we have had our first assignment in C++, we had to implement a chained hash table using all the tools we had learned so far. I opted for a Vector of Vectors in my implementation, why I didn't use an Array of Vectors is beyond me, but it made sense at the time! I found it quite easy writing the functions to add, search and print the contents of the hash table, however, the nightmare arose when I got to my delete method, I'm sure each of us had a different solution to what sounded like an easy function! Firstly I had to start thinking in Vectors, which vector do I delete from, which one is my method ACTUALLY deleting from and what do I do to fix it! In the end I opted for the erase() function that is in-built in the vector library, after many "program aborted : core dumped " errors I worked out that my function was trying to delete from a value that was outside my vector, I.e. I was trying to erase a vital piece of memory from some other poor program that was minding its own business! After sorting that issue, the crashing stopped and I thought my method was working as it should, however after adding a value, checking it was there, deleting it, then re-checking my program kept saying that the value was still in the table, oh noes! I spent a ridiculously long time trying to work out what was going on, it was only after several coffees and visits to the smoking area that I had the brainwave, what if the delete WAS working at my search was broken?? Indeed, this was the case, I had defined the boolean it uses in a global scope, so it never got reset to false, ever, what a tube! I'm not sure if any of the rest of the group had a problem like this, but it was a bit of a pain to de-bug! This assignment brought into sharp focus the concept of Errors, my code compiled 90% of the time, once I sorted out my missing semi-colons etc (Syntax errors), but it also crashed at least 50% of the time after compilation, these were down to my delete method trying to delete from locations that it shouldn't (Exception Errors). I also had some bizzare functionality that I hadn't planned for, my first implementation of my user input validation appeared to work, but it turned out it only worked for the first incorrect entry and not for the subsequent inputs (Logical Error). I suppose I could have implemented some Try-Catch blocks around the high risk areas of my program, such as adding or deleting from the hash table, so if by some chance a dodgy value did get through, the program would stop and display a meaningful error, rather than half a terminal of gobbledegook! I only ever used Try-Catch when I was dealing with files in JAVA, but from what I have seen in C++ it is pretty similar. Have to remember to #include stdexcept at the top though, if I remember correctly JAVA didn't need to import a separate library for exception handling. There are 6 different types of errors that can be generated by stdexcept, 2 of which have a further 7 different exceptions, as shown below:





So we see that std:exception is the parent class, with sub-classes of it thrown depending on the type of error that is encountered. I spent a lot of time lurking in the logic_failure -> out_of_range section, not sure about the rest of the guys!
Going back to the files in JAVA, I find it far easier to implement in C++, there was just something really awkward about creating a file reader or writer object, then creating a new reader/writer then you could actually work with your file, it was messy and I always ended up overwriting when I should have been appending and vice versa. the C++ implementation is neat, tidy and a breath of fresh air from JAVA. You import the fstream library then call it on what ever file you wish to open. Depending on how you call the fstream object you can perform different tasks as shown below:

• ios::out - opens to write output.
• ios::in - opens to read input.
• ios::app - opens to append output at the end of an existing file.
• ios::trunc - truncate the existing file.
• ios::ate - open without truncating, data can be written anywhere.
• ios::binary - treat the file as binary format rather than text, so the data may be stored in a nontext format.


This also brings us nicely to the concept of Object Orientated Programming, in JAVA, it was forced, like I mentioned about the file reading. A lot of things in JAVA seemed very clunky, but once you got your head around the fact that everything had to work in classes it kind of made sense. Now that we have been working in C++ I can see why we were shown JAVA first. If we had done it in reverse, I think that classes and OOP would have been far more difficult to grasp, with lots of bad habits getting in our way. Its now well and truly burned in our minds : Encapsulation, Inheritance and Polymorphism. With inheritance in C++ you can create a base class with its own constructor, then you can make a new class that inherits all of the methods from the base class. For example, you could have a base class called Animal, then create sub classes for dog and cat. The base class Animal would have a constructor for say age, weight and colour which would be inherited by dog and cat, but the dog could have new parameter, such as bark and the cat could have another such as temperament (will it scratch your eyeballs out with no warning?). The classes for this could look as such : Class Animal then you would have Class Dog : Public Animal and Class Cat : Public Animal. This is pretty similar to JAVA, you just had the word EXTENDS instead of the ":" giving Public Class Dog EXTENDS Animal for example. Inheritance in C++ also introduced us to the concept of "overloading" Here we could have a function in a class that had the same name such as bark(), but, you could have ANOTHER function, with the same name, but with different parameters such as bark(parameter 1) and bark(parameter 1, parameter 2). This was an awesome concept when it was shown, I personally had never heard of overloading before so this was quite interesting to look up. Overriding was also introduced at this point, similar to Overloading but instead of having different arguments for each type, you have an IDENTICAL function in the sub class, same name, parameters, arguments etc. So when this function is called it completely ignores the function from the base class and uses the function from the sub class instead. 

All in all it has been a VERY busy week, we had our first assignment to hand in for C++ and we also had our first assignment to hand in for Algorithms and AI, that was a nasty nasty assignment and I, and may others, felt very under prepared to answer it, especially since it is worth 10% of our module grade, I will be happy if I even passed it, nevermind the distinctions which seemed so easy to achieve in first year. However, I can see some nice overlapping coming up, we have covered Space Complexity, Time Complexity and Big O Notation in AC12007 already, so, hopefully this module will solidify what we have learned(or tried to) already.

Apologies for this being uploaded slightly late.

Duncan