Data Structure, Outline:

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.
Data Structures evolve arround:

• Introduction to Algorithms

• ADTs

• Searching and sorting Techniques

• Arrays

• Stacks

• Recursion

• Queues

• Lists and its variations

• Trees

• Hashing

• Graphs

 

Basics of OOP-Summary:

What is Object-Oriented Programming?
 
Object-Oriented Programming (OOP) is different from procedural programming languages (C, Pascal, etc.) in several ways. Everything in OOP is grouped as "objects" (see data abstraction). OOP, defined in the purest sense, is implemented by sending messages to objects. To understand this concept, we first need to know what is an object? An object can be considered a "thing" that can perform a set of activities. The set of activities that the object performs defines the object's behavior. For example, a "StudentStatus" object can tell you its grade point average, year in school, or can add a list of courses taken. A "Student" object can tell you its name or its address.
The object's interface consists of a set of commands, each command performing a specific action. An object asks another object to perform an action by sending it a message. The requesting (sending) object is referred to as sender and the receiving object is referred to as receiver.

 
 
Control is given to the receiving object until it completes the command; control then returns to the sending object.
For example, a School object asks the Student object for its name by sending it a message asking for its name. The receiving Student object returns the name back to the sending object.
 
 
A message can also contain information the sending objects needs to pass to the reveiving object, called the argument in the message. A receiving object always returns a value back to the sending object. This returned value may or may not be useful to the sending object.
For example, the School object now wants to change the student's name. It does this by sending the Student object a message to set its name to a new name. The new address is passed as an argument in the message. In this case, the School object does not care about the return value from the message.

It is very common that a message will cause other messages to be sent, either to itself or to other objects, in order to complete its task. This is called sequential operation. Control will not return to the original sending object untill all other messages have been completed. For example, in the following diagram, Object A sends a message to Object B. For Object B to process that message it sends a message to Object C.Likewise, Object C sends a mesage to Object D. Object D returns to Object C who then returns to Object B who returns to Object A. Control does not return to Object A until all the other messages have completed.

Sequential Operation

How do receiving objects interpret messages from the senders? How are the messages processed?

Method

Each message has code that associated with it. When an object receives a message, code is excercuted. In other words, these messages determine an object's behavior and the code determines how the object carries out each message. The code that is associated with each message is called a method. The message name is also called the method name due to its close association with the method.
When an object receives a message, it determines what method is being requested and passes control to the method. An object has as many methods as it it takes to perform its designed actions.
Refer to the following diagram, name, name:, address and name:address are method names for the Student object (Please see "Object and Message Naming" for more information). When the Student object receive the name message, the name message passes control to the name method defined in Student.

 
 
Methods that operate on specific objects are instance methods and messages that invoke instance methods are called instance message. Methods that operate on specific classes are class methods. This will be discussed in more details in later chapter.
    
   Methods are similar to subroutines, procedures, or functions found in procedural languages (C, Pascal). For example, a method name equates to a subroutine name, and the code for the method equates to the code found in a subroutine. Sending a message to an object is similar to calling a subroutine.
See also "Basic Structure of a Method".
Each object need to keep the information on how to perform its defined behavior. Some objects also contain variables that support their bahavior. These variables are called instance variables. Only the instance method for an object can refer to and change the values stored in the instance variables. The instance methods for other objects cannot refer to this object's data. An object may only access another object's data by sending it messages.This is called encapsulation and assures that there is a secure process for getting to an object's data.

Object's Data

Refer to the following diagram, the instance variables variableOne through variableX can only be accessed by the sender via instance methods methodOne through methodX. The sender can not refer to the variables directly by itslef.

    Unlike procedural progamming where common data areas are often used for sharing information, object-oriented programming discourages direct access to common data (other than the use of global variables) by other programs. Only the object that "owns" the data can change its contant. Other objects can view or change this data by sending message to the "owner."
The instance variable names can be identical to the method names that associate with them. For example, the Student object has methods of name, address, and major as well as instance variables of name, address, and major. Smalltalk distinguishes variable identifier and a method identifier by the identifier's position in the expression. Another important concept of object-oriented programming is inheritance. Inheritance allows a class to have the same behavior as another class and extend or tailor that behavior to provide special action for specific needs.

Inheritance

 
Let's use the following application as an example. Both Graduate class and Undergraduate class have similar bahavior such as managing a name, an address, a major, and a GPA. Rather than put this bahavior in both of these classes, the bahavior is placed in a new class called Student. Both Graduate and Undergraduate become subclass of the Student class, and both inherit the Student behavior.

Both Graduate and Undergraduate classes can then add additional behavior that is unique to them. For example, Graduate can be either Master's program or phD program. On the other hand, Undergraduate class might want to keep track of either the student is Freshman, Sophmore, Junior or Senior.
Classes that inherit from a class are called subclasses. The class a subclass inherits from are called superclass. In the example, Student is a superclass for Graduate and Undergraduate. Graduate and Undergraduate are subclasses of Student.

Another benefit of separating implementaion from behavior is polymorphism. Polymorphism allows two or more objects respond to the same message. A method called name could also be implemented for an object of the class Course. Even though the implementation of this name message may return a course number and a course title, its protocol is the same as the name message to the Student object.

Polymorphism

Polymorphism allows a sending object to communicate with different objects in a consistant manner without worrying about how many different implementations of a message.
 
An analogy of polymorphism to daily life is how students response to a school bell. Every student knows the significant of the bell. When the bell (message) rings, however, it has its own meaning to different students (objects). Some students go home, some go to the library, and some go to other classes. Every student responds to the bell, but how they response to it might be different.
 
Another example of polymorphism is the function of printing. Every printable object must know how to print itself. The message is the same to all the different objects: print, but the actual implementation of what they must do to print themselves varies.
 
The sending object does not have to know how the receiving object implement the message. Only the receiving objects worries about that. Assume that there is a printPage method in a Document object that has the responsibility of printing a page. To print the page, the printPage method sends the print message to each object on the page. The Document does not need to know what types of objects are on the page, only that each object supports the behavior of printing.

New objects can be added to the page without affecting the printPage method. This method still sends the print message and the new object provides its own print method in response to that message.
Polymorphism allows the sending object to communicate with receiving objects without having to understand what type of object it is, as long as the receiving objects support the messages.

What is An Object?

Reusability

The Power of Reuse is:

One of the most important features of object-oriented programming is the ability to modify existing solution to solve new problems. If a particular kind of problem has been solved using the OOP approach, a similar but slightly different problem can usually be solved by making some changes in the object-message protocal that already exist.
Most of the time, this requires adding new messages. Other cases may require adding new objects and new messages to which those objects respond.

Reusability is probably the most important and the strongest feature of Smalltalk. Although procedural languages can be reuse too, Smalltalk makes programming for reuse much easier.

Polymorphism

Another benefit of separating implementaion from behavior is polymorphism. Polymorphism allows two or more objects respond to the same message. A method called name could also be implemented for an object of the class Course. Even though the implementation of this name message may return a course number and a course title, its protocol is the same as the name message to the Student object. Polymorphism allows a sending object to communicate with different objects in a consistant manner without worrying about how many different implementations of a message.

Difference b/w Class & Object:

What Is the Difference Between a  Class and Object?

Edward Yourdan defines a class as, “A collection of one or more objects with a uniform set of attributes and services, including a description of how to create new objects in the class.”

Grady Booch defines an object as, “An object has state, behavior, and identity; The structure and behavior of similar objects are defined in their common class; The terms instance and object are interchangeable.”

From these two definitions we can see that there is a difference between a class and an object.  A class is the definition, or blueprint, for an object.  Classes don’t real ever exist, they are plans.  We use the class to create an object which has identity.  That is, an object exists, has values in its properties and can execute behaviors.

This difference between a class and an object is a subtle but very important one. It is analogous to visiting an architect to have a new house built.  The architect will draw up plans for the house that show all the rooms and elevations etc. However, you cannot move into the plans and live there.  The plans must be used to build a house.  The house is an object while the plans are a class.

Difference b/w Overloading & Overriding

Difference between overloading and overriding is as follows...

•  In overloading, there is a relationship between methods available in the same class

•  Overloading does not block inheritance from the superclass whereas overriding blocks inheritance from the superclass.

•  In overloading, separate methods share the same name whereas in overriding,subclass method replaces the superclass.

•  Overloading must have different method signatures whereas overriding  must have same signature.

Inheritance between classes

A key feature of C++ classes is inheritance. Inheritance allows to create classes which are derived from other classes, so that they automatically include some of its "parent's" members, plus its own. For example, we are going to suppose that we want to declare a series of classes that describe polygons like our CRectangle, or like CTriangle. They have certain common properties, such as both can be described by means of only two sides: height and base.

This could be represented in the world of classes with a class CPolygon from which we would derive the two other ones: CRectangle and CTriangle.


The class CPolygon would contain members that are common for both types of polygon. In our case: width and height. And CRectangle and CTriangle would be its derived classes, with specific features that are different from one type of polygon to the other.

Classes that are derived from others inherit all the accessible members of the base class. That means that if a base class includes a member A and we derive it to another class with another member called B, the derived class will contain both members A and B.

In order to derive a class from another, we use a colon (:) in the declaration of the derived class using the following format:

class derived_class_name: public base_class_name
{ /*...*/ };
Where derived_class_name is the name of the derived class and base_class_name is the name of the class on which it is based. The public access specifier may be replaced by any one of the other access specifiers protected and private. This access specifier limits the most accessible level for the members inherited from the base class: The members with a more accessible level are inherited with this level instead, while the members with an equal or more restrictive access level keep their restrictive level in the derived class.

// derived classes #include<iostream> using namespace std; class CPolygon { protected: int width, height; public: void set_values (int a, int b) { width=a; height=b;} }; class CRectangle: public CPolygon { public: int area () { return (width * height); } }; class CTriangle: public CPolygon { public: int area () { return (width * height / 2); } }; int main() { CRectangle rect; CTriangle trgl; rect.set_values (4,5); trgl.set_values (4,5); cout << rect.area() << endl; cout << trgl.area() << endl; return 0; }

20 10

The objects of the classes CRectangle and CTriangle each contain members inherited from CPolygon. These are: width, height and set_values().

The protected access specifier is similar to private. Its only difference occurs in fact with inheritance. When a class inherits from another one, the members of the derived class can access the protected members inherited from the base class, but not its private members.

Since we wanted width and height to be accessible from members of the derived classes CRectangle and CTriangle and not only by members of CPolygon, we have used protected access instead of private.

It can be  summarized in different access types according to who can access them in the following way:

Access	public	protected	private
members of the same class	yes	yes	yes
members of derived classes	yes	yes	no
not members	yes	no	no

Where "not members" represent any access from outside the class, such as from main(), from another class or from a function.

In our example, the members inherited by CRectangle and CTriangle have the same access permissions as they had in their base class CPolygon:

CPolygon::width // protected access CRectangle::width // protected access CPolygon::set_values() // public access CRectangle::set_values() // public access

This is because we have used the public keyword to define the inheritance relationship on each of the derived classes:

class CRectangle: public CPolygon { ... }

This public keyword after the colon (:) denotes the most accessible level the members inherited from the class that follows it (in this case CPolygon) will have. Since public is the most accessible level, by specifying this keyword the derived class will inherit all the members with the same levels they had in the base class.

If we specify a more restrictive access level like protected, all public members of the base class are inherited as protected in the derived class. Whereas if we specify the most restricting of all access levels: private, all the base class members are inherited as private.

For example, if daughter was a class derived from mother that we defined as:

class daughter: protected mother;

This would set protected as the maximum access level for the members of daughter that it inherited from mother. That is, all members that were public in mother would become protected in daughter. Of course, this would not restrict daughter to declare its own public members. That maximum access level is only set for the members inherited from mother.

If we do not explicitly specify any access level for the inheritance, the compiler assumes private for classes declared with class keyword and public for those declared with struct.