November 14, 2012

Interfaces

My teacher keeps talking about interfaces and Coding To The Interface and extending interfaces and implementing interfaces and faces faces faces.  While I'm still confused.. I get that they're sort of abstract classes that tell what the class should do without implementation.  But why are they different from inheritance, why are they better, when should we use either, what is inheritance anyway?  I guess that's a topic for another day.

Okay..

So interfaces are basically what separates the outside world from actual implementation.  Like a car, you can control how fast it goes (gas pedal), how much it turns (steering wheel), and.. that's pretty much it.  You don't need to know anything else.  An interface is a set of requirements (I'm gonna be repeating myself a lot here because I'm reading from at least three different sources, and repetition really helps to solidify the concepts in my poor sleep-deprived brain)

Interfaces provide you the abstract view of a class without showing you how it's implemented - provide methods without bodies.  Here is an example:

interface Doggy {
   void bark (int annoyingFactor);

   void chaseTail (int sillyFactor);

   void vomitOnCarpet (int grossFactor);

   int Size();

   int Age();

We don't need to know how the Doggy barks.  It could be loud, soft, annoying, less annoying, all we know is it barks.  Same with chaseTail, Doggy could be really silly or just a little silly.  And for vomitOnCarpet, we don't need to know what was in the vomit or what made the Doggy vomit.  All we know is all Doggy(s) bark, chaseTail, and vomitOnCarpet.

To implement Doggy, name of class would change to a particular breed of dog, for example Sheltie, and use the implements keyword in the class declaration

class Sheltie implements Doggy {

   // implement Doggy as Sheltie

}

Interfaces are basically a CONTRACT between class and outside world, and the contract is enforced at compile time.  For a class to implement an interface, it must include all the methods in the interface.

And to repeat myself, note that interfaces do NOT contain method bodies.  They also cannot be instantiated.  Don't be silly and try to instantiate a Doggy.  Not gonna work.  Must write a class, Sheltie, or GoldenRetriever, or Rottweiler, that provides a method body for each of the methods declared in the interface (tells you how annoying the implemented Doggy's bark will be, or how silly its chaseTail will be, or how gross vomitOnCarpet will be).

Note that in Java, a class can only inherit from one class but can implement more than one interface.  So Sheltie can implement Doggy but can also implement beAnnoying and beCute

public interface Doggy extends beAnnoying, beCute{
   void barkLoudly (int decibels);

   void chaseTail (int hours);

   void vomitOnCarpet (int grossFactor);

   int Size();

   int Age();

public indicates that the interface can be used by any class in the package.  Thank goodness anyone can use Doggy.

Declared v. Dynamic types: a declared type is set at COMPILE time (by declaration).  Dynamic type is set at RUN time (by new).  If I understand this right, and if I'm applying what I learned from my linked list implementation correctly, a Declared type is an object declared on the Stack while a Dynamic type is something declared on the Heap.  So basically Dynamic types are more annoying to deal with than Declared types.
-- Also, interfaces cannot be Dynamic types!  You can't instantiate them, they must be Declared (ok that's where they tie in)
-- Because the compiler cannot guess Dynamic types
-- A declared type (interface) determines which members can be used
-- But the DECLARED type of a variable can be an interface
      -- Doggy dog; // good dog
      -- dog = new Doggy(); // bad dog (compile-time error)
-- Only classes can be instantiated directly, but variable of type X can refer to an instance of a class that implements X
      -- class Sheltie implements Doggy { ... }
      -- Doggy dog = new Sheltie(); // good dog
      -- It's a bit like widening

Simple Rule (from the cse slides): Interfaces can ONLY be used as declared types.  No dynamic types, no new, no instantiation
-- All dynamic types are classes, and all run-time objects are constructed from a class, not an interface

Good Practice: Code to Interface (this keeps coming up again in the slides):
-- "Coding to the interface" means ALL declared types are interface types
-- All variable declarations and field declarations use interface types
      -- Doggy dog = new Sheltie();
-- All argument and return types in method signatures are interface types

Oracle says that "When you define a new interface, you are defining a new reference data type."  So a new interface defines a new classification that determines possible values, allowable operations, meaning of the data, and the way values of that type can be stored.

public Dog isMoreAnnoying (Dog aDog, Dog anotherDog) {
   Doggy toby = (Doggy) aDog;
   Doggy lassie = (Doggy) anotherDog;

   if (toby.Age() < lassie.Age() )
      return aDog;

   else
      return anotherDog;
}

This is a method that returns the more annoying Doggy, for ANY Dog that is instantiated from a class that implements Doggy (don't know if this is right or not.. This is the part about interfaces that confuses me the most, including it in code)
- By casting aDog to a Doggy type, it can invoke the Age() method

If I can implement Doggy in a lot of classes, the objects instantiate from ANY of these classes can be compared with the Age() method, if both objects are of the same class.  This works for any "Doggy" objects, no matter class inheritance.  When Doggy is implemented, the objects can be of their own class and a Doggy type, so they can have behavior from both a superclass and an interface.

Rewriting Interfaces: Don't do it.  All classes that implement Doggy will break because they don't implement the interface anymore.  If I wanted to write a legit Doggy class, I'd want to anticipate as many uses as I can, and extend it when I think of other uses later.

Ugh still don't completely understand all the details but at least I understand it a little better than I did before

November 12, 2012

Code Library

This is a project I've been working on recently

I've been trying to cram a buttload of information into my tiny little brain, and I got the idea to build a code library that would store a lot of pertinent information in a way that would be easy to access.  And it would be another way to delve into C++ (we're learning java in my cse class right now and I'd rather program in c++, despite all the problems c++ comes with)

This was an interesting project.. I'm used to being given an assignment in class and having all the functions and procedures mapped out for me, down to the arguments we were given, what the code was supposed to do and what it was supposed to output.  All the design problems were already done for us, we just had to code the functions or procedures.  This wasn't the case for ALL our assignments but for the majority of them, especially earlier on in the course sequence.

Doing my own project was nice.  No looming deadlines, no tricky documentation required, and no worrying about getting a million points taken off for not clearing my arguments!

It was fun trying to think of a design that would be efficient, yet easy to code.  I decided to create a separate text file for each major topic (Array, Set, Unix/Linux, etc.) and within those topics I have subtopics, denoted by a *.  Within the *Subtopics I have blocks of information, enclosed by <subtopic> information </subtopic> (I got the idea from XML.  I was thinking about enclosing my information blocks in parentheses, or ** or the like but that's not safe enough.  What if I have parentheses inside my information blocks?  Or I decide it's necessary to splatter a bunch of *****'s inside those blocks?)  The main program prompts the user for input, and if the user types in something dumb, the program gently asks for clarification or exits gracefully.  As of now, at this point in my program, for all of the testing I have done so far, the program does not crash, regardless of dumb input from the user (me)

Here's the main program:
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include "InputOutput.h"
using namespace std;

// *** Remember to update the set every time new text files are added!!! ***

int main() {

    bool continueAsking = true;
    while (continueAsking) {

        // create set of all possible topics
        set<string> topics;
        topics.insert("array");
        topics.insert("set");
        topics.insert("input output");
        topics.insert("general tips and tricks");
        topics.insert("nonspecific interview questions");
        topics.insert("contest problems");
        topics.insert("unix linux");

        // receive user input for topic
        cout << "Hello master, what would you like to look for?\n"
             << "You can choose from the following: \n";
        outputSet (topics);
        cout << "\n>> ";
        string topic;
        getline (cin, topic);
        cout << "\n";

        if ( matchSubjectTitle(topic, topics) ) {
            cout << "List of topics regarding " << topic <<  ":\n";
           
            // topic is matched, now output topic subtitles
            string title = topic + ".txt";
            outputSubTopics (title);

            // get subTopic
            cout << "\nPlease enter a topic of interest: \n>> ";
            string subtopic;
            getline (cin, subtopic);
            cout << '\n';

            // find subTopic, output information block
            outputSubTopicBlock (title, subtopic);
            cout << "\nContinue searching?\n>> ";

            string answer;
            getline (cin, answer);
            string answerLower = toLowerCase(answer);
            if (answerLower == "no") {
                continueAsking = false;
            }

            cout << '\n';
        }

        // answer did not match with Subject title
        // give user a chance to try again
        else {

            string answer;
            cout << "Would you like to try again?\n>> ";
            getline (cin, answer);
            string answerLower = toLowerCase(answer);
            if (answerLower == "no") {
                continueAsking = false;
            }

            cout << '\n';
        }
    }

    return 0;
}

Not including the helper file that has all my functions/procedures since it would be too much.

And here is an example of one of the text files:
SET

* Stuff
<stuff>
stuff about stuff
</stuff>
(I'll add actual information here, later)

Ran into a few tricksters while coding this.  I'm still used to osu's made-up c++ language that hid a lot of work from us.  I'm used to sets having a Is_Defined function, but no such luck with c++.  This is what I used for my Is_Defined function:
if ( topics.find(answerLowerCase) != topics.end() ) { return true; }

Every time my program receives user input, it translates it into lowercase, no matter how it came in.  Just makes it easier and a lot more generalized than checking for case errors.  So you could type in array or Array or arRaY, whatever strikes your fancy

And I'm used to one input from file operator that's perfect and does all the work for you.  C++ has a few.. it took me a couple tries to get the right one.  When I tested the main program and asked for "interview questions", it came up blank.  It took me a while to realize that cin >> stuff stops at the space character.  So I used getline (cin, stuff) instead to get the entire line.  But you can't use cin and then getline, something about the cin not getting rid of the space or newline character and the getline function reading the blank space.

Ugh.. I feel a bit crippled by resolve/c++.  I realize that the osu cse faculty put a lot of work into that language, drilling some very important concepts into our little minds, but it's hard to go from resolve to java or c++.

I was at acm's east regional whatever competition last weekend, and one of my group members said she realized she couldn't code without Google (while I couldn't code at ALL.  unfortunately resolve wasn't one of the c, c++, or java languages we were allowed to code in HA.  i basically drew pictures the entire five hours we were there).  And I'm scared of that reality.  I don't want to turn to Google every time I want to sit down and code something.  The code I had above, to find if an item is defined in a set?  I got that off Google.  I understand it but I wouldn't have been able to get that on my own.  I'm hoping fluency is something that comes with a lot of practice

Anyway..

I talked to a smart person about my little side project, and Smart Person told me it would be a good idea to use XML for this.  And I tried, I really did.  For at least a couple hours.  But there's a limit to how much I can learn at one time.. I also have schoolwork that I've been putting off to do this.  So I will save that for a future project.  For now I will keep updating and improving my code library since I think it's something that could be really useful to me.

And now to do ACTUAL schoolwork

November 11, 2012

Tidbits from my Java class

Don't quite understand immutability yet, so I'm gonna try to learn the crap out of it

So, first, of all, we have to understand why this code is crappy:
(Before osu's cse department decides to sue me, this is all info from here)
public class Period implements FixedEpoch {
   private Date start;
   private Date end;

   public Period (Date start, Date end) {
      assert (start.compareTo (end) < 0); // start < end

      this.start = start;
      this.end = end;
   }

   public Date getStart() {
      return start;
   }

   public Date getEnd() {
      return end;
   }

}
So why is this like the worst code ever?

ALIASING!!!!!!!!!
The assignment in the constructor (public Period (Date ..) ) creates an ALIAS - the client and component both have references to the same Date object.

So why is this a problem?

Take this code:
Date t1 = new Date (300);
Date t2 = new Date (500);
Period p = new Period (t1, t2);
t2.setTime (100);


So now, p is modified even though we might not have wanted it to be.  Oh noes!

But there is a solution: "defensive copying", where the constructor creates a copy of the arguments.
For example, here is a better Period class:
public class Period implements FixedEpoch {
   private Date start;
   private Date end;

   public Period (Date start, Date end){
   assert (start.compareTo (end) < 0);
   
      this.start = new Date (start.getTime() );
      this.end = new Date (end.getTime() );
   }

   public Date getStart() {
      return start;
   }

   public Date getEnd() {
      return end;
   }
}

But we can still improve this.  Notice how the check, (assert...) is BEFORE the copy?  Well, when making a defensive copy of constructor argument, you're supposed to FIRST copy and arguments, and THEN check the validity of the parameters.

Why?  Multithreaded code, I'll review that later..

But anyhoo, here's an even BETTER implementation:
public class Period implements FixedEpoch {
   private Date start;
   private Date end;

   public Period (Date start, Date end) {
      this.start = new Date (start.getTime() );
      this.end = new Date (end.getTime() );

      assert (this.start.compareTo (this.end) < 0);
   }

   public Date getStart() {
      return start;
   }

   public Date getEnd() {
      return end;
   }
}

So now this follows the good practice of copying first, then checking

But oh no there's another problem!  --> ALIASING!  Again!  Where???

Notice the return start, return end creates an alias.  We made sure to create new Date objects for start and end, but by calling getStart() or getEnd() the client can still access the internal workings of our Period object.

For example:
Date t1 = new Date (300);
Date t2 = new Date (500);
Period p = new Period (t1, t2);
Date rawr = p.getEnd();



But there is a solution again: defensive copying.  The accessors create a copy of start and end in Period p, and the copy is returned to the client.

Let's try again:
public class Period implements FixedEpoch {
   private Date start;
   private Date end;

   public Period (Date start, Date end) {
      this.start = new Date (start.getTime() );
      this.end = new Date (end.getTime() );

      assert (this.start.compareTo (this.end) < 0);
   }

   public Date getStart() {
      return new Date (start.getTime() );
   }

   public Date getEnd() {
      return new Date (end.getTime() );
   }
}

So we've learned that it's Good Practice to make Defensive Copies.  Alias undermine the privacy of a field, copies prevent aliases to fields.  Blehh aliases
Typical examples of evil aliases are:
   - parameters in constructors and mutators
   - return value from any method
Like the ones we've seen above!

*Note that the benefit we get from creating a safe object costs us in memory and speed.  Creating a new object for each distinct value can get costly

BUT, there are some fields of fields where aliasing is never a concern!  Fields that are primitive!  (int, float, etc.)  Fields that are enumerations!  (suit, colors, etc.)  Fields that are immutable!

What?

Yeah, immutable.  Not mutable.  Where the abstract value can never change.  We want this because aliasing an immutable is safe!  We don't need defensive copies!  (well, not for the class.. we might, inside the internals of the class).

How we do write an immutable class?
Well, don't write mutator methods.
Make all fields private
And if the class has fields that refer to mutable objects:
  - make defensive copies of parameters in constructors and methods
  - make defensive copies for return values from methods
  - like above!
And, note that defensive copies are not needed for fields that are primitive, enumerations, or refer to immutable objects

Think about Period.  It has fields that refer to mutables (Date) so we needed defensive copies.
On the other hand, think about String.  It has methods that look like mutator - toUpperCase(), replace (char, char) but these methods actually return a String

The slides say to declare all fields to be final, and the class to be final.  So I'm not sure why yet but I'll read up on it.  But they DO point out that only the ABSTRACT state needs to be immutable, the concrete state (fields) can change as long as client-side view stays the same.

And the slides also talk about wrapper classes, boxing, and unboxing.. Ugh.  Well all I got was that every primitive type has a corresponding wrapper class.  And boxing.. so boxing goes from primitive to wrapper?  Like Integer integerObject = new Integer(42)
So 42 was the Integer, integerObject is Integer with another layer added on I guess.
And unboxing is opposite, goes from wrapper to primitive.  Like int i = integerObject.intValue();
So integerObject was the wrapper which goes to the primitive int it
And Java does this AUTOMATICALLY

But whatever.  I guess I understand immutability more now.  You basically want it so the client can't inadvertently (or advertently) screw with your code, and so it prevents a lot of bugs that would otherwise be hard to trace.

As Joshua Bloch touts,  a well-designed module is different from a poorly designed module because the well-designed one HIDES its implementation from the user - ENCAPSULATION.  Encapsulation can be also thought of information hiding, and it's useful because it prevents a lot of crap from happening
--> A good way to do this is to make every class or member as inaccessible as possible.  BUT, public classes are allowed to expose constants through public static final fields (this is where names have all capital letters)
--> Basically, should always aim to reduce accessibility as much as possible!!!
Yay.. because this is what immutability is all about.  When you create an instance for an immutable class, it starts as some initial value and STAYS THAT WAY.  It STAYS THAT WAY, does NOT CHANGE.  Establish a class invariant, and stick with it!  Nothing throughout the lifetime of this object will change it.  (Yes I know I'm repeating the same thing over and over again but it took me a while to get this concept straight in my head).
--> Classes should be immutable unless there's a good reason for them to be mutable!  The only disadvantage of immutable classes is the performance, in some cases

Immutability, ladies and gentlemen.


November 08, 2012

Pointer fun

First attempt at writing a linked list:
(First attempt at writing in C++, for that matter)

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class List {
    Node head;
    Node tail;
    int len;

public:

    List() {

        head.data = 0;
        head.next = &tail;

        tail.data = 0;
        tail.next = NULL;

        len = 0;
    }

    void addBeg (int n) {
        Node addMe;

        addMe.data = n;
        addMe.next = head.next;
        head.next = &addMe;

        len++;
    }

    void output () {

        Node *current = &head;

        while (current -> next != NULL) {
           cout << current -> data << endl;
           current = current -> next;
        }

        cout << current -> data;
    }

    int returnLen () {
        return len;
    }

};

int main()
{
    List list;

    list.addBeg(3);
    list.addBeg(2);
    list.addBeg(1);

    list.output();
}

And this is what it outputs:
0
-858993460

Awesome.

So.. one of the reasons this doesn't work is because, in addBeg, a node is being created on the stack (rather than the heap).  So after list.addBeg(2) is called in main and we actually go into the addBeg procedure, newNode is created which we squish between head and tail.  BUT, after the closing brace } in addBeg, since newNode was created on the stack, it gets destroyed and now head points to ridiculousness and we have a memory leak in tail (data still there, but no way to access it).

I have to build a constructor for the Node object so I can call Node* nodeName = new Node in addBeg to create a node on the heap.
So, 2nd try:

#include <iostream>
using namespace std;

class Node {
public:
    Node() {};
    int data;
    Node* next;
};

class List {

    Node head;
    Node tail;
    int len;

public:

    List() {

        head.data = 0;
        head.next = &tail;

        tail.data = 0;
        tail.next = NULL;

        len = 0;
    }

    void addBeg (int n) {

        Node* addMe = new Node();

        addMe -> data = n;
        addMe -> next = head.next;

        head.next = addMe;
        len++;
    }

    void output () {

        Node *current = &head;
        current = current -> next;

        while (current -> next != NULL) {
           cout << current -> data << endl;
           current = current -> next;
        }
    }

    int returnLen () {
        return len;
    }

};

int main() {
    List list;

    list.addBeg(3);
    list.addBeg(2);
    list.addBeg(1);
    list.output();

    return 0;
}
      


And this is what it outputs:
1
2
3

Yes!  That's what I wanted!

I know this still isn't perfect (my brother complained about the sentinel nodes head and tail, and that I declared list on the stack rather than the heap, and that I didn't have a destructor, or a remove first procedure, and that my names were weird), but BLEHH it's my first c++ thing

That was fun!  Pointers make me want to pull my hair out sometimes but I kind of like struggling with problems.  The more you struggle, the better it feels when you actually get it

November 04, 2012

first nerd post!

/* no comment */

LOLZZZZ