Category: Generics

Generics

Algorithms FAQs Part 1.

The following are the list of most important FAQs of Algorithms and Data Structures used in most of the programming languages. To improve your




coding skills every programmer has to know the how to implement Algorithms and Data structures in his application.

1. What is an algorithm?
The process of providing solution to a problem is a sequence of steps is called an algorithm.

 

2. What are the properties of an algorithm?  

An algorithm must possess the following properties:
a. It should get input data.
b. It should produce output.
c. The algorithm should terminate.
d. Algorithm should be clear to understand.
e. It should be easy to perform.

3. What are the types of algorithms?
Algorithms are of two types: iterative and recursive algorithms.

4. Define iterative algorithms.
Algorithms which use loops and conditions to solve the problem are called iterative algorithms.

5. Define recursive algorithms.
Algorithms which perform the recursive steps in a divide and conquer method are called recursive algorithms.

6. What is an array?
An array is a sequential collection of same kind of data elements.

7. What is a data structure?

A data structure is a way of organizing data that considers not only the items stored, but also their relationship to each other. Advance knowledge about the relationship between data items allows designing of efficient algorithms for the manipulation of data.

8. Name the areas of application of data structures.

The following are the areas of application of data structures:

a. Compiler design
b. Operating system
c. Statistical analysis package
d. DBMS
e. Numerical analysis
f. Simulation
g. Artificial Intelligence
h. Graphics

9. What are the major data structures used in the following areas: Network data model, Hierarchical data model, and RDBMS?

The major data structures used in the above areas are:
Network data model – Graph
Hierarchical data model – Trees
RDBMS – Array

10. What are the types of data structures?
Data structures are of two types: Linear and non linear data structures.

11. What is a linear data structure?
If the elements of a data structure are stored sequentially, then it is a linear data structure.

12. What is non linear data structure?
If the elements of a data structure are not stored in sequential order, then it is a non linear data structure.

13. What are the types of array operations?

The following are the operations which can be performed on an array:
Insertion, Deletion, Search, Sorting, Merging, Reversing and Traversal.

14. What is a matrix?
An array of two dimensions is called a matrix.

15. What are the types of matrix operations?

The following are the types of matrix operations:
Addition, multiplication, transposition, finding determinant of square matrix, subtraction, checking whether it is singular matrix or not etc.

16.  What is the condition to be checked for the multiplication of two matrices?
If matrices are to be multiplied, the number of columns of first matrix should be equal to the number of rows of second matrix.

 

17.  Write the syntax for multiplication of matrices?Syntax:
for (=0; < value;++)
{
for (=0; < value;++)
{
for (=0; < value;++)
{
arr[var1][var2] += arr[var1][var3] * arr[var3][arr2];
}
}
}

 

18.  What is a string?
A sequential array of characters is called a string.

19.  What is use terminating null character?
Null character is used to check the end of string.

20.  What is an empty string?
A string with zero character is called an empty string.

21.  What are the operations that can be performed on a string?
The following are the operations that can be performed on a string:
finding the length of string, copying string, string comparison, string concatenation, finding substrings etc.

22.  What is Brute Force algorithm?
Algorithm used to search the contents by comparing each element of array is called Brute Force algorithm.

23.  What are the limitations of arrays?
The following are the limitations of arrays:
Arrays are of fixed size.
Data elements are stored in continuous memory locations which may not be available always.
Adding and removing of elements is problematic because of shifting the locations.

24.  How can you overcome the limitations of arrays?
Limitations of arrays can be solved by using the linked list.

25.  What is a linked list?
Linked list is a data structure which store same kind of data elements but not in continuous memory locations and size is not fixed. The linked lists are related logically.

26.  What is the difference between an array and a linked list?
The size of an array is fixed whereas size of linked list is variable. In array the data elements are stored in continuous memory locations but in linked list it is non continuous memory locations. Addition, removal of data is easy in linked list whereas in arrays it is complicated.

27.  What is a node?
The data element of a linked list is called a node.

28.  What does node consist of?
Node consists of two fields:
data field to store the element and link field to store the address of the next node.

29.  Write the syntax of node creation?

Syntax:
struct node
{
data type ;
node *ptr; //pointer for link node
}temp;

 

30.  Write the syntax for pointing to next node?Syntax:
node->link=node1;

32.  What is a data structure? What are the types of data structures? Briefly explain them

The scheme of organizing related information is known as ‘data structure’. The types of data structure are:

Lists: A group of similar items with connectivity to the previous or/and next data items.
Arrays: A set of homogeneous values
Records: A set of fields, where each field consists of data belongs to one data type.
Trees: A data structure where the data is organized in a hierarchical structure. This type of data structure follows the sorted order of insertion, deletion and modification of data items.
Tables: Data is persisted in the form of rows and columns. These are similar to records, where the result or manipulation of data is reflected for the whole table.

33.  Define a linear and non linear data structure.

Linear data structure: A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. Ex: Arrays, Linked Lists

Non-Linear data structure: Every data item is attached to several other data items in a way that is specific for reflecting relationships. The data items are not arranged in a sequential structure. Ex: Trees, Graphs

34.  Define in brief an array. What are the types of array operations?

An array is a set of homogeneous elements. Every element is referred by an index.

Arrays are used for storing the data until the application expires in the main memory of the computer system. So that, the elements can be accessed at any time. The operations are:

– Adding elements
– Sorting elements
– Searching elements
– Re-arranging the elements
– Performing matrix operations
– Pre-fix and post-fix operations

35.  What is a matrix? Explain its uses with an example

A matrix is a representation of certain rows and columns, to persist homogeneous data. It can also be called as double-dimensioned array.

Uses:
– To represent class hierarchy using Boolean square matrix
– For data encryption and decryption
– To represent  traffic flow and plumbing in a network
– To implement graph theory of node representation

36.  Define an algorithm. What are the properties of an algorithm? What are the types of algorithms?

 

Algorithm: A step by step process to get the solution for a well defined problem.
Properties of an algorithm:

– Should be unambiguous, precise and lucid
– Should provide the correct solutions
– Should have an end point
– The output statements should follow input, process instructions
– The initial statements should be of input statements
– Should have finite number of steps
– Every statement should be definitive

37.  Types of algorithms:

– Simple recursive algorithms. Ex: Searching an element in a list
– Backtracking algorithms Ex: Depth-first recursive search in a tree
– Divide and conquer algorithms. Ex: Quick sort and merge sort
– Dynamic programming algorithms. Ex: Generation of Fibonacci series
– Greedy algorithms Ex: Counting currency
– Branch and bound algorithms. Ex: Travelling salesman (visiting each city once and minimize the total distance travelled)
– Brute force algorithms. Ex: Finding the best path for a travelling salesman
– Randomized algorithms. Ex. Using a random number to choose a pivot in quick sort).

38.  What is an iterative algorithm?

The process of attempting for solving a problem which finds successive approximations for solution, starting from an initial guess. The result of repeated calculations is a sequence of approximate values for the quantities of interest.

39.  What is an recursive algorithm?

Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repetition is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.

40.  Explain quick sort and merge sort algorithms.

Quick sort employs the ‘divide and conquer’ concept by dividing the list of elements into two sub elements.

The process is as follows:

1. Select an element, pivot, from the list.
2. Rearrange the elements in the list, so that all elements those are less than the pivot are arranged before the pivot and all elements those are greater than the pivot are arranged after the pivot. Now the pivot is in its position.
3. Sort the both sub lists – sub list of the elements which are less than the pivot and the list of elements which are more than the pivot recursively.

41.  Merge Sort: A comparison based sorting algorithm. The input order is preserved in the sorted output.

Merge Sort algorithm is as follows:

1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Otherwise divide the unsorted list into two lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, merge  both the lists back into one sorted list.

42.  What is Bubble Sort and Quick sort?

Bubble Sort: The simplest sorting algorithm. It involves the sorting the list in a repetitive fashion. It compares two adjacent elements in the list, and swaps them if they are not in the designated order. It continues until there are no swaps needed. This is the signal for the list that is sorted. It is also called as comparison sort as it uses comparisons.

Quick Sort: The best sorting algorithm which implements the ‘divide and conquer’ concept. It first divides the list into two parts by picking an element a ‘pivot’. It then arranges the elements those are smaller than pivot into one sub list and the elements those are greater than pivot into one sub list by keeping the pivot in its original place.

43.  What are the difference between a stack and a Queue?

Stack – Represents the collection of elements in Last In First Out order.
Operations includes testing null stack, finding the top element in the stack, removal of top most element and adding elements on the top of the stack.

Queue – Represents the collection of elements in First In First Out order.

Operations include testing null queue, finding the next element, removal of elements and inserting the elements from the queue.

Insertion of elements is at the end of the queue

Deletion of elements is from the beginning of the queue.

44.  Can a stack be described as a pointer? Explain.

A stack is represented as a pointer. The reason is that, it has a head pointer which points to the top of the stack. The stack operations are performed using the head pointer. Hence, the stack can be described as a pointer.

45.  Explain the terms Base case, Recursive case, Binding Time, Run-Time Stack and Tail Recursion.

Base case: A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.

Recursive Case: A case which returns to the answer which is closer.

Run-time Stack: A run time stack used for saving the frame stack of a function when every recursion or every call occurs.

Tail Recursion: It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.

46.  Is it possible to insert different type of elements in a stack? How?

Different elements can be inserted into a stack. This is possible by implementing union / structure data type. It is efficient to use union rather than structure, as only one item’s memory is used at a time.

47.  Explain in brief a linked list.

A linked list is a dynamic data structure. It consists of a sequence of data elements and a reference to the next element in the sequence. Stacks, queues, hash tables, linear equations, prefix and post fix operations. The order of linked items is different that of arrays. The insertion or deletion operations are constant in number.

48.  Explain the types of linked lists.

The types of linked lists are:

Singly linked list: It has only head part and corresponding references to the next nodes.

Doubly linked list: A linked list which both has head and tail parts, thus allowing the traversal in bi-directional fashion. Except the first node, the head node refers to the previous node.

Circular linked list: A linked list whose last node has reference to the first node.

49.  How would you sort a linked list?

Step 1: Compare the current node in the unsorted list with every element in the rest of the list. If the current element is more than any other element go to step 2 otherwise go to step 3.

Step 2: Position the element with higher value after the position of the current element. Compare the next element. Go to step1 if an element exists, else stop the process.

Step 3: If the list is already in sorted order, insert the current node at the end of the list. Compare the next element, if any and go to step 1 or quit.

 

50.  What is sequential search? What is the average number of comparisons in a sequential search?

 

Sequential search: Searching an element in an array, the search starts from the first element till the last element.

The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array. If the element is in the 1st position, the number of comparisons will be 1 and if the element is in the last position, the number of comparisons will be N.

51.  What are binary search and Fibonacci search?

Binary Search: Binary search is the process of locating an element in a sorted list. The search starts by dividing the list into two parts. The algorithm compares the median value. If the search element is less than the median value, the top list only will be searched, after finding the middle element of that list. The process continues until the element is found or the search in the top list is completed. The same process is continued for the bottom list, until the element is found or the search in the bottom list is completed. If an element is found that must be the median value.

52.  Define Fibonacci Search: Fibonacci search is a process of searching a sorted array by utilising divide and conquer algorithm. Fibonacci search examines locations whose addresses have lower dispersion. When the search element has non-uniform access memory storage, the Fibonacci search algorithm reduces the average time needed for accessing a storage location.

Generics

Algorithms FAQs Part 2.

What is linear search?

Answer: Linear search is the simplest form of search. It searches for the element sequentially starting from the first element. This search has a disadvantage if the element is located at the end. Advantage lies in the simplicity of the search. Also it is most useful when the elements are arranged in a random order.

What is binary search?  

Answer: Binary search is most useful when the list is sorted. In binary search, element present in the middle of the list is determined. If the key (number to search) is smaller than the middle element, the binary search is done on the first half. If the key (number to search) is greater than the middle element, the binary search is done on the second half (right). The first and the last half are again divided into two by determining the middle element.

Explain the bubble sort algorithm.

Answer: Bubble sort algorithm is used for sorting a list. It makes use of a temporary variable for swapping. It compares two numbers at a time and swaps them if they are in wrong order. This process is repeated until no swapping is needed. The algorithm is very inefficient if the list is long.

E.g. List: – 7 4 5 3
1. 7 and 4 are compared

2. Since 4 < 7, 4 is stored in a temporary variable.

3. the content of 7 is now stored in the variable which was holding 4

4. Now, the content of temporary variable and the variable previously holding 7 are swapped.

What is quick sort?  

Answer: Quick sort is one the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are portioned or divided such that elements less than the pivot point are in left and those greater than the pivot are on the right. Now, the elements on the left and right can be recursively sorted by repeating the algorithm.

Describe Trees using C++ with an example.

Tree is a structure that is similar to linked list. A tree will have two nodes that point to the left part of the tree and the right part of the tree. These two nodes must be of the similar type.

The following code snippet describes the declaration of trees. The advantage of trees is that the data is placed in nodes in sorted order.

struct TreeNode
{
int item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNode *right; // Pointer to the right subtree.
}

The following code snippet illustrates the display of tree data.

void showTree( TreeNode *root )
{
if ( root != NULL ) { // (Otherwise, there’s nothing to print.)
showTree(root->left); // Print items in left sub tree.
cout << root->item << ” “; // Print the root item.
showTree(root->right ); // Print items in right sub tree.
}
} // end inorderPrint()

Data Structure trees – posted on August 03, 2008 at 22:30 PM by Amit Satpute

Question – What is a B tree?

Answer: A B-tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties :

1. Every node has <= m children.
2. Every node (except root and leaves) has >= m/2 children.
3. The root has at least 2 children.
4. All leaves appear in the same level, and carry no information.
5. A non-leaf node with k children contains k – 1 keys

Question – What are splay trees?

Answer: A splay tree is a self-balancing binary search tree. In this, recently accessed elements are quick to access again

It is useful for implementing caches and garbage collection algorithms.

When we move left going down this path, its called a zig and when we move right, its a zag.

Following are the splaying steps. There are six different splaying steps.
1. Zig Rotation (Right Rotation)
2. Zag Rotation (Left Rotation)
3. Zig-Zag (Zig followed by Zag)
4. Zag-Zig (Zag followed by Zig)
5. Zig-Zig
6. Zag-Zag

Question – What are red-black trees?

Answer :A red-black tree is a type of self-balancing binary search tree.
In red-black trees, the leaf nodes are not relevant and do not contain data.
Red-black trees, like all binary search trees, allow efficient in-order traversal of elements.
Each node has a color attribute, the value of which is either red or black.

Characteristics:
The root and leaves are black
Both children of every red node are black.
Every simple path from a node to a descendant leaf contains the same number of black nodes, either counting or not counting the null black nodes

Question – What are threaded binary trees?

Answer: In a threaded binary tree, if a node ‘A’ has a right child ‘B’ then B’s left pointer must be either a child, or a thread back to A.

In the case of a left child, that left child must also have a left child or a thread back to A, and so we can follow B’s left children until we find a thread, pointing back to A.

This data structure is useful when stack memory is less and using this tree the treversal around the tree becomes faster.

Question – What is a B+ tree?

Answer: It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. all records are stored at the lowest level of the tree; only keys are stored in interior blocks.

Describe Tree database. Explain its common uses.

A tree is a data structure which resembles a hierarchical tree structure. Every element in the structure is a node. Every node is linked with the next node, either to its left or to its right. Each node has zero or more child nodes. The length of the longest downward path to a leaf from that node is known as the height of the node and the length of the path to its root is known as the depth of a node.

Common Uses:

– To manipulate hierarchical data
– Makes the information search, called tree traversal, easier.
– To manipulate data that is in the form of sorted list.

What is binary tree? Explain its uses.

A binary tree is a tree structure, in which each node has only two child nodes. The first node is known as root node. The parent has two nodes namely left child and right child.

Uses of binary tree:

– To create sorting routine.
– Persisting data items for the purpose of fast lookup later.
– For inserting a new item faster

How do you find the depth of a binary tree?

The depth of a binary tree is found using the following process:

1. Send the root node of a binary tree to a function
2. If the tree node is null, then return false value.
3. Calculate the depth of the left tree; call it ‘d1’ by traversing every node. Increment the counter by 1, as the traversing progresses until it reaches the leaf node. These operations are done recursively.
4. Repeat the 3rd step for the left node. Name the counter variable ‘d2’.
5. Find the maximum value between d1 and d2. Add 1 to the max value. Let us call it ‘depth’.
6. The variable ‘depth’ is the depth of the binary tree.

Explain pre-order and in-order tree traversal.

A non-empty binary tree is traversed in 3 types, namely pre-order, in-order and post-order in a recursive fashion.

Pre-order:
Pre-order process is as follows:

– Visit the root node
– Traverse the left sub tree
– Traverse the right sub tree

In-Order:
In order process is as follows:
– Traverse the left sub tree
– Visit the root node
– Traverse the right sub tree

What is a B+ tree? Explain its uses.

B+ tree represents the way of insertion, retrieval and removal of the nodes in a sorted fashion. Every operation is identified by a ‘key’. B+ tree has maximum and minimum bounds on the number of keys in each index segment, dynamically. All the records in a B+ tree are persisted at the last level, i.e., leaf level in the order of keys.

B+ tree is used to visit the nodes starting from the root to the left or / and right sub tree. Or starting from the first node of the leaf level. A bi directional tree traversal is possible in the B+ tree.

Define threaded binary tree. Explain its common uses

A threaded binary tree is structured in an order that, all right child pointers would normally be null and points to the ‘in-order successor’ of the node. Similarly, all the left child pointers would normally be null and points to the ‘in-order predecessor’ of the node.

Uses of Threaded binary tree:

– Traversal is faster than unthreaded binary trees
– More subtle, by enabling the determination of predecessor and successor nodes that starts from any node, in an efficient manner.
– No stack overload can be carried out with the threads.
– Accessibility of any node from any other node
– It is easy to implement to insertion and deletion from a threaded tree.

Explain implementation of traversal of a binary tree.

Binary tree traversal is a process of visiting each and every node of the tree. The two fundamental binary tree traversals are ‘depth-first’ and ‘breadth-first’.

The depth-first traversal are classified into 3 types, namely, pre-order, in-order and post-order.

Pre-order: Pre-order traversal involves visiting the root node first, then traversing the left sub tree and finally the right sub tree.

In-order: In-order traversal involves visiting the left sub tree first, then visiting the root node and finally the right sub tree.

Post-order: Post-order traversal involves visiting the left sub tree first, then visiting the right sub tree and finally visiting the root node.

The breadth-first traversal is the ‘level-order traversal’. The level-order traversal does not follow the branches of the tree. The first-in first-out queue is needed to traversal in level-order traversal.

Explain implementation of deletion from a binary tree.

To implement the deletion from a binary tree, there is a need to consider the possibilities of deleting the nodes. They are:

– Node is a terminal node: In case the node is the left child node of its parent, then the left pointer of its parent is set to NULL. In all other cases, if the node is right child node of its parent, then the right pointer of its parent is set to NULL.

– Node has only one child: In this scenario, the appropriate pointer of its parent is set to child node.

– Node has two children: The predecessor is replaced by the node value, and then the predecessor of the node is deleted.

 

Describe stack operation. 

Stack is a data structure that follows Last in First out strategy.

Stack Operations:-

�  Push – Pushes (inserts) the element in the stack. The location is specified by the pointer.

�  Pop – Pulls (removes) the element out of the stack. The location is specified by the pointer

�  Swap: – the two top most elements of the stack can be swapped

�  Peek: – Returns the top element on the stack but does not remove it from the stack

�  Rotate:- the topmost (n) items can be moved on the stack in a rotating fashion

A stack has a fixed location in the memory. When a data element is pushed in the stack, the pointer points to the current element.

Describe queue operation.

Queue is a data structure that follows First in First out strategy.

Queue Operations:

�  Enqueue- Inserts the element in the queue at the end.

�  Dequeue – removes the element out of the queue from the front

�  Size – Returns the size of the queue

�  Front – Returns the first element of the queue.

�  Empty – to find if the queue is empty.

Discuss how to implement queue using stack.
A queue can be implemented by using 2 stacks:-

�  1. An element is inserted in the queue by pushing it into stack 1

�  2. An element is extracted from the queue by popping it from the stack 2

�  3. If the stack 2 is empty then all elements currently in stack 1 are transferred to stack 2 but in the reverse order

�  4. If the stack 2 is not empty just pop the value from stack 2.

Explain stacks and queues in detail.

A stack is a data structure based on the principle Last In First Out. Stack is container to hold nodes and has two operations – push and pop. Push operation is to add nodes into the stack and pop operation is to delete nodes from the stack and returns the top most node.

A queue is a data structure based on the principle First in First Out. The nodes are kept in an order. A node is inserted from the rear of the queue and a node is deleted from the front. The first element inserted in the first element first to delete.

Question – What are priority queues?
A priority queue is essentially a list of items in which each item is associated with a priority
Items are inserted into a priority queue in any, arbitrary order. However, items are withdrawn from a priority queue in order of their priorities starting with the highest priority item first.

Priority queues are often used in the implementation of algorithms

Question – What is a circular singly linked list?
In a circular singly linked list, the last node of the list is made to point to the first node. This eases the traveling through the list..

Describe the steps to insert data into a singly linked list.
Steps to insert data into a singly linked list:-

Insert in middle
Data: 1, 2, 3, 5
1. Locate the node after which a new node (say 4) needs to be inserted.(say after 3)

2. create the new node i.e. 4

3. Point the new node 4 to 5 (new_node->next = node->next(5))

4. Point the node 3 to node 4 (node->next =newnode)

Insert in the beginning

Data: 2, 3, 5

1. Locate the first node in the list (2)

2. Point the new node (say 1) to the first node. (new_node->next=first)

Insert in the end

Data: 2, 3, 5

1. Locate the last node in the list (5)

2. Point the last node (5) to the new node (say 6). (node->next=new_node)

Explain how to reverse singly link list.

Answer: Reverse a singly link list using iteration:-

1. First, set a pointer ( *current) to point to the first node i.e. current=base

2. Move ahead until current!=null (till the end)

3. set another pointer (* next) to point to the next node i.e. next=current->next

4. store reference of *next in a temporary variable ( *result) i.e current->next=result

5. swap the result value with current i.e. result=current

6. and now swap the current value with next. i.e. current=next

7. return result and repeat from step 2

A linked list can also be reversed using recursion which eliminates the use of a temporary variable.

Define circular linked list.

Answer: In a circular linked list the first and the last node are linked. This means that the last node points to the first node in the list. Circular linked list allow quick access to first and last record using a single pointer.

Describe linked list using C++ with an example.

A linked list is a chain of nodes. Each and every node has at least two nodes, one is the data and other is the link to the next node. These linked lists are known as single linked lists as they have only one pointer to point to the next node. If a linked list has two nodes, one is to point to the previous node and the other is to point to the next node, then the linked list is known as doubly linked list.

To use a linked list in C++ the following structure is to be declared:

 

typedef struct List
{

long Data;
List* Next;
List ()
{

Next=NULL;
Data=0;
}

};
typedef List* ListPtr.

The following code snippet is used to add a node.

void List::AddANode()
{

ListPtr->Next = new List;
ListPtr=ListPtr->Next;

}

The following code snippet is used to traverse the list

void showList(ListPtr listPtr)
{
� while(listPtr!=NULL) {
cout<<listPtr->Data;
}
return temp;
}

 

 

/ / LListItr class; maintains “current position”.

/ I

/ / CONSTRUCTION: With no parameters. The LList class may

/ / construct a LListItr with a pointer to a LListNode.

/ /

/ / ******************PUBLOIPCE RATIONS*********************

/ / boo1 isValid( j –> True if not NULL

/ / void advance ( j –> Advance (if not already NULL)

/ / Object retrieve( ) –> Return item in current position

/ / ******************ERRORS********************************

/ / Throws BadIterator for illegal retrieve.

 

template <class Object>

class LListItr

{

public:

LListItr( ) : current( NULL ) { 1

 

boo1 isValid( j const

{ return current ! = NULL; )

 

void advance ( j

{ if( isValid( j j current = current->next; 1

 

const Object & retrieve( ) const

{ if( !isValid( j j throw BadIterator( ) ;

return current->element; }

 

private:

LListNode<Object> *current; / / Current position

 

LListItr( LListNode<Object> *theNode )

: current ( theNode ) {

 

friend class LList<Object>; / / Grant access to constructor

};

 

 

 

/ / LList class.

/ /

/ / CONSTRUCTION: with no initializer.

/ / Access is via LListItr class.

/ /

/ / ******************PUBLIoC~ ERATIoNs******************X**

/ / boo1 isEmpty( ) –> Return true if empty; else false

/ / void makeEmpty( ) –> Remove all items

/ / LListItr zeroth( ) –> Return position to prior to first

10 / / LListItr first( ) –> Return first position

11 / / void insert( x, p ) –> Insert x after position p

12 / / void remove( x ) –> Remove x

13 / / LListItr find( x ) –> Return position that views x

14 / / LListItr findprevious( x )

15 / / –> Return position prior to x

16 / / ******************ERR~R~*****~****************************

17 / / No special errors.

18

19 template <class Object>

20 class LList

21 I

22 public:

23 LList( ) ;

24 LList( const LList & rhs ) ;

25 -LList( ) ;

26

27 boo1 isEmpty( const;

28 void makeEmpty( ) ;

29 LListItr<Object> zeroth( ) const;

30 LListItr<Object> first ( ) const;

31 void insert( const Object & x, const ~~istItr<Object&> p ) ;

32 LListItr<Object> find( const Object & x ) const;

33 LListItr<Object> findprevious( const Object & x ) const;

34 void remove( const Object & x ) ;

35

36 const LList & operator=( const LList & rhs ) ;

37

38 private:

39 LListNode<Object> *header;

};

 

/ / Construct the list.

template <class Object>

LList<Object>: :LList ( )

{

header = new LListNode<Object>;

1

7

/ / Test if the list is logically empty.

/ / Return true if empty, false, otherwise.

10 template <class Object>

11 boo1 LList<Object>: :isEmpty( ) const

12 {

13 return header->next == NULL;

14 1

15

16 / / Return an iterator representing the header node.

17 template <class Object>

18 LListItr<Object> LList<Object>::zeroth( ) const

19 I

20 return LListItr<Object>( header ) ;

21 1

22

23 / / Return an iterator representing the first node in the list.

24 / / This operation is valid for empty lists.

25 template <class Object>

26 LListItr<Object> LList<Object>::first( ) const

27 {

28 return LListItr<Object>( header->next ) ;

29 };

 

/ / Simple print function.

template <class Object>

void printlist( const LList<Object> & theList )

(

if( theList.isEmptyi ) )

6 cout << “Empty list” << endl;

else

8 }

LListItr<Object> itr = theList.first( ) ;

10 for( ; itr.isValid( ) ; itreadvance( ) )

11 cout << itr.retrieve( ) << ” “;

12 {

13 cout << endl;

14 }

 

/ / Return iterator corresponding to the first node matching x.

/ / Iterator is not valid if item is not found.

template <class Object>

LListItr<Object> LList<Object>::find( const Object & x ) const

{

6 LListNode<Object> *p = header->next;

7

8 while( p ! = NULL && p->element ! = x )

9 p = p->next;

10

11 return LListItr<Object>( p ) ;

12 }

/ / Remove the first occurrence of an item X .

template <class Object>

void LList<Object>::remove( const Object & x

{

LListNode<Object> *p = findprevious( x ) .current;

6

if( p->next ! = NULL )

8 I

LListNode<Object> *oldNode = p->next;

10 p->next = p->next->next; / / Bypass

11 delete oldNode;

12 }

13 1

Figure 17.13 The remove routine for the LList class.

/ / Return iterator prior to the first node containing item x.

template <class Object>

LListItr<Object>

LList<Object>: : f indprevious ( const Object & x ) const

{

LListNode<Object> *p = header;

7

8 while( p-znext ! = NULL && p->next->element ! = x )

p = p->next;

10

11 return LListItr<Object>( p ) ;

12 }

Figure 17.14 The f indprevious routine-similar to the find routine-for use

with remove.

/ / Insert item x after p.

template <class Object>

void LList<Object>::

insert( const Object & x, const LListItr<Object> & p )

{

if ( p.current ! = NULL )

p.current->next = new LListNodecObject>( x,

8 p.current->next ) ;

}

Figure 17.15 The insertion routine for the LList class.

 

/ / Make the list logically empty.

template <class Object>

void LList<Object>: :makeEmpty( )

I

while( !isEmptyi ) )

6 remove ( first ( ) .retrieve ( ) ) ;

1

8

/ / Destructor.

10 template <class Object>

11 LList<Object>::-LList( )

12 (

13 makeErnpty ( ) ;

14 delete header;

15 1

Figure 17.16 The makeEmpty method and the LLis t destructor.

/ / Copy constructor.

template <class Object>

LList<Object>::LList( const LList<Object> & rhs )

{

header = new LListNodeiObject>;

*this = rhs;

}

8

/ / Deep copy of linked lists.

10 template <class Object>

11 const LList<Object> &

12 LList<Object>::operator=( const ~~ist<Object&> rhs i

13 {

14 if ( this ! = &rhs )

15 (

16 makeEmpty ( ) ;

17

18 LListItr<Object> ritr = rhs.first( ) ;

19 LListItr<Object> itr = zeroth( ) ;

20 for( ; ritr.isValid( ) ; ritr.advance( ) , itr.advance( )

21 insert( ritr.retrieve( ) , itr ) ;

22 {

23 return *this;

24 }

Figure 17.17 Two LLis copy routines: operator= and copy constructor.

 

Q: Implement a Algorithm to check if the link list is in Ascending order?

A: template

bool linklist::isAscending() const{

nodeptr ptr = head;

while(ptr->_next)

{

if(ptr->_data > ptr->_next->_data)

return false;

ptr= ptr->_next;

}

return true;

}

 

Q: Write an algorithm to reverse a link list?

A: template

void linklist::reverselist()

{

nodeptr ptr= head;

nodeptr nextptr= ptr->_next;

while(nextptr)

{

nodeptr temp = nextptr->_next;

nextptr->_next = ptr;

ptr = nextptr;

nextptr = temp;

}

head->_next = 0;

head = ptr;

}

Generics

Algorithms FAQs Part 3.

Q: Implement Binary Heap in C++?

A: BinaryHeap.h

————

#ifndef BINARY_HEAP_H_

#define BINARY_HEAP_H_

#include “dsexceptions.h”

#include “vector.h”

// BinaryHeap class

//

// CONSTRUCTION: with an optional capacity (that defaults to 100)

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x ) –> Insert x

// deleteMin( minItem ) –> Remove (and optionally return) smallest item

// Comparable findMin( ) –> Return smallest item

// bool isEmpty( ) –> Return true if empty; else false

// bool isFull( ) –> Return true if full; else false

// void makeEmpty( ) –> Remove all items

// ******************ERRORS********************************

// Throws Underflow and Overflow as warranted

template

class BinaryHeap

{

public:

explicit BinaryHeap( int capacity = 100 );

bool isEmpty( ) const;

bool isFull( ) const;

const Comparable & findMin( ) const;

void insert( const Comparable & x );

void deleteMin( );

void deleteMin( Comparable & minItem );

void makeEmpty( );

private:

int currentSize; // Number of elements in heap

vector array; // The heap array

void buildHeap( );

void percolateDown( int hole );

};

#endif

BinaryHeap.cpp

————–

#include “BinaryHeap.h”

/**

* Construct the binary heap.

* capacity is the capacity of the binary heap.

*/

template

BinaryHeap::BinaryHeap( int capacity )

: array( capacity + 1 ), currentSize( 0 )

{

}

/**

* Insert item x into the priority queue, maintaining heap order.

* Duplicates are allowed.

* Throw Overflow if container is full.

*/

template

void BinaryHeap::insert( const Comparable & x )

{

if( isFull( ) )

throw Overflow( );

// Percolate up

int hole = ++currentSize;

for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )

array[ hole ] = array[ hole / 2 ];

array[ hole ] = x;

}

/**

* Find the smallest item in the priority queue.

* Return the smallest item, or throw Underflow if empty.

*/

template

const Comparable & BinaryHeap::findMin( ) const

{

if( isEmpty( ) )

throw Underflow( );

return array[ 1 ];

}

/**

* Remove the smallest item from the priority queue.

* Throw Underflow if empty.

*/

template

void BinaryHeap::deleteMin( )

{

if( isEmpty( ) )

throw Underflow( );

array[ 1 ] = array[ currentSize– ];

percolateDown( 1 );

}

/**

* Remove the smallest item from the priority queue

* and place it in minItem. Throw Underflow if empty.

*/

template

void BinaryHeap::deleteMin( Comparable & minItem )

{

if( isEmpty( ) )

throw Underflow( );

minItem = array[ 1 ];

array[ 1 ] = array[ currentSize– ];

percolateDown( 1 );

}

/**

* Establish heap order property from an arbitrary

* arrangement of items. Runs in linear time.

*/

template

void BinaryHeap::buildHeap( )

{

for( int i = currentSize / 2; i > 0; i– )

percolateDown( i );

}

/**

* Test if the priority queue is logically empty.

* Return true if empty, false otherwise.

*/

template

bool BinaryHeap::isEmpty( ) const

{

return currentSize == 0;

}

/**

* Test if the priority queue is logically full.

* Return true if full, false otherwise.

*/

template

bool BinaryHeap::isFull( ) const

{

return currentSize == array.size( ) – 1;

}

/**

* Make the priority queue logically empty.

*/

template

void BinaryHeap::makeEmpty( )

{

currentSize = 0;

}

/**

* Internal method to percolate down in the heap.

* hole is the index at which the percolate begins.

*/

template

void BinaryHeap::percolateDown( int hole )

{

/* 1*/ int child;

/* 2*/ Comparable tmp = array[ hole ];

/* 3*/ for( ; hole * 2 <= currentSize; hole = child )

{

/* 4*/ child = hole * 2;

/* 5*/ if( child != currentSize && array[ child + 1 ] < array[ child ] )

/* 6*/ child++;

/* 7*/ if( array[ child ] < tmp )

/* 8*/ array[ hole ] = array[ child ];

else

/* 9*/ break;

}

/*10*/ array[ hole ] = tmp;

}

TestBinaryHeap.cpp

——————

#include

#include “BinaryHeap.h”

#include “dsexceptions.h”

// Test program

int main( )

{

int numItems = 10000;

BinaryHeap h( numItems );

int i = 37;

int x;

try

{

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

h.insert( i );

for( i = 1; i < numItems; i++ )

{

h.deleteMin( x );

if( x != i )

cout << “Oops! ” << i << endl;

}

for( i = 37; i != 0; i = ( i + 37 ) % numItems )

h.insert( i );

h.insert( 0 );

h.insert( i = 999999 ); // Should overflow

}

catch( Overflow )

{ cout << “Overflow (expected)! ” << i << endl; }

return 0;

}

Q: Implement Binary Search Tree in C++?

A: BinarySearchTree.h

———————-

#ifndef BINARY_SEARCH_TREE_H_

#define BINARY_SEARCH_TREE_H_

#include “dsexceptions.h”

#include // For NULL

// Binary node and forward declaration because g++ does

// not understand nested classes.

template

class BinarySearchTree;

template

class BinaryNode

{

Comparable element;

BinaryNode *left;

BinaryNode *right;

BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )

: element( theElement ), left( lt ), right( rt ) { }

friend class BinarySearchTree;

};

// BinarySearchTree class

//

// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds

//

// ******************PUBLIC OPERATIONS*********************

// void insert( x ) –> Insert x

// void remove( x ) –> Remove x

// Comparable find( x ) –> Return item that matches x

// Comparable findMin( ) –> Return smallest item

// Comparable findMax( ) –> Return largest item

// boolean isEmpty( ) –> Return true if empty; else false

// void makeEmpty( ) –> Remove all items

// void printTree( ) –> Print tree in sorted order

template

class BinarySearchTree

{

public:

explicit BinarySearchTree( const Comparable & notFound );

BinarySearchTree( const BinarySearchTree & rhs );

~BinarySearchTree( );

const Comparable & findMin( ) const;

const Comparable & findMax( ) const;

const Comparable & find( const Comparable & x ) const;

bool isEmpty( ) const;

void printTree( ) const;

void makeEmpty( );

void insert( const Comparable & x );

void remove( const Comparable & x );

const BinarySearchTree & operator=( const BinarySearchTree & rhs );

private:

BinaryNode *root;

const Comparable ITEM_NOT_FOUND;

const Comparable & elementAt( BinaryNode *t ) const;

void insert( const Comparable & x, BinaryNode * & t ) const;

void remove( const Comparable & x, BinaryNode * & t ) const;

BinaryNode * findMin( BinaryNode *t ) const;

BinaryNode * findMax( BinaryNode *t ) const;

BinaryNode * find( const Comparable & x, BinaryNode *t ) const;

void makeEmpty( BinaryNode * & t ) const;

void printTree( BinaryNode *t ) const;

BinaryNode * clone( BinaryNode *t ) const;

};

#endif

BinarySearchTree.cpp

——————–

#include “BinarySearchTree.h”

#include

/**

* Implements an unbalanced binary search tree.

* Note that all “matching” is based on the < method.

*/

/**

* Construct the tree.

*/

template

BinarySearchTree::BinarySearchTree( const Comparable & notFound ) :

root( NULL ), ITEM_NOT_FOUND( notFound )

{

}

/**

* Copy constructor.

*/

template

BinarySearchTree::

BinarySearchTree( const BinarySearchTree & rhs ) :

root( NULL ), ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )

{

*this = rhs;

}

/**

* Destructor for the tree.

*/

template

BinarySearchTree::~BinarySearchTree( )

{

makeEmpty( );

}

/**

* Insert x into the tree; duplicates are ignored.

*/

template

void BinarySearchTree::insert( const Comparable & x )

{

insert( x, root );

}

/**

* Remove x from the tree. Nothing is done if x is not found.

*/

template

void BinarySearchTree::remove( const Comparable & x )

{

remove( x, root );

}

/**

* Find the smallest item in the tree.

* Return smallest item or ITEM_NOT_FOUND if empty.

*/

template

const Comparable & BinarySearchTree::findMin( ) const

{

return elementAt( findMin( root ) );

}

/**

* Find the largest item in the tree.

* Return the largest item of ITEM_NOT_FOUND if empty.

*/

template

const Comparable & BinarySearchTree::findMax( ) const

{

return elementAt( findMax( root ) );

}

/**

* Find item x in the tree.

* Return the matching item or ITEM_NOT_FOUND if not found.

*/

template

const Comparable & BinarySearchTree::

find( const Comparable & x ) const

{

return elementAt( find( x, root ) );

}

/**

* Make the tree logically empty.

*/

template

void BinarySearchTree::makeEmpty( )

{

makeEmpty( root );

}

/**

* Test if the tree is logically empty.

* Return true if empty, false otherwise.

*/

template

bool BinarySearchTree::isEmpty( ) const

{

return root == NULL;

}

/**

* Print the tree contents in sorted order.

*/

template

void BinarySearchTree::printTree( ) const

{

if( isEmpty( ) )

cout << “Empty tree” << endl;

else

printTree( root );

}

/**

* Deep copy.

*/

template

const BinarySearchTree &

BinarySearchTree::

operator=( const BinarySearchTree & rhs )

{

if( this != &rhs )

{

makeEmpty( );

root = clone( rhs.root );

}

return *this;

}

/**

* Internal method to get element field in node t.

* Return the element field or ITEM_NOT_FOUND if t is NULL.

*/

template

const Comparable & BinarySearchTree::

elementAt( BinaryNode *t ) const

{

if( t == NULL )

return ITEM_NOT_FOUND;

else

return t->element;

}

/**

* Internal method to insert into a subtree.

* x is the item to insert.

* t is the node that roots the tree.

* Set the new root.

*/

template

void BinarySearchTree::

insert( const Comparable & x, BinaryNode * & t ) const

{

if( t == NULL )

t = new BinaryNode( x, NULL, NULL );

else if( x < t->element )

insert( x, t->left );

else if( t->element < x )

insert( x, t->right );

else

; // Duplicate; do nothing

}

/**

* Internal method to remove from a subtree.

* x is the item to remove.

* t is the node that roots the tree.

* Set the new root.

*/

template

void BinarySearchTree::

remove( const Comparable & x, BinaryNode * & t ) const

{

if( t == NULL )

return; // Item not found; do nothing

if( x < t->element )

remove( x, t->left );

else if( t->element < x )

remove( x, t->right );

else if( t->left != NULL && t->right != NULL ) // Two children

{

t->element = findMin( t->right )->element;

remove( t->element, t->right );

}

else

{

BinaryNode *oldNode = t;

t = ( t->left != NULL ) ? t->left : t->right;

delete oldNode;

}

}

/**

* Internal method to find the smallest item in a subtree t.

* Return node containing the smallest item.

*/

template

BinaryNode *

BinarySearchTree::findMin( BinaryNode *t ) const

{

if( t == NULL )

return NULL;

if( t->left == NULL )

return t;

return findMin( t->left );

}

/**

* Internal method to find the largest item in a subtree t.

* Return node containing the largest item.

*/

template

BinaryNode *

BinarySearchTree::findMax( BinaryNode *t ) const

{

if( t != NULL )

while( t->right != NULL )

t = t->right;

return t;

}

/**

* Internal method to find an item in a subtree.

* x is item to search for.

* t is the node that roots the tree.

* Return node containing the matched item.

*/

template

BinaryNode *

BinarySearchTree::

find( const Comparable & x, BinaryNode *t ) const

{

if( t == NULL )

return NULL;

else if( x < t->element )

return find( x, t->left );

else if( t->element < x )

return find( x, t->right );

else

return t; // Match

}

/****** NONRECURSIVE VERSION*************************

template

BinaryNode *

BinarySearchTree::

find( const Comparable & x, BinaryNode *t ) const

{

while( t != NULL )

if( x < t->element )

t = t->left;

else if( t->element < x )

t = t->right;

else

return t; // Match

return NULL; // No match

}

*****************************************************/

/**

* Internal method to make subtree empty.

*/

template

void BinarySearchTree::

makeEmpty( BinaryNode * & t ) const

{

if( t != NULL )

{

makeEmpty( t->left );

makeEmpty( t->right );

delete t;

}

t = NULL;

}

/**

* Internal method to print a subtree rooted at t in sorted order.

*/

template

void BinarySearchTree::printTree( BinaryNode *t ) const

{

if( t != NULL )

{

printTree( t->left );

cout << t->element << endl;

printTree( t->right );

}

}

/**

* Internal method to clone subtree.

*/

template

BinaryNode *

BinarySearchTree::clone( BinaryNode * t ) const

{

if( t == NULL )

return NULL;

else

return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );

}

TestBinarySearchTree.cpp

————————

#include

#include “BinarySearchTree.h”

// Test program

int main( )

{

const int ITEM_NOT_FOUND = -9999;

BinarySearchTree t( ITEM_NOT_FOUND );

int NUMS = 4000;

const int GAP = 37;

int i;

cout << “Checking… (no more output means success)” << endl;

for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )

t.insert( i );

for( i = 1; i < NUMS; i+= 2 )

t.remove( i );

if( NUMS < 40 )

t.printTree( );

if( t.findMin( ) != 2 || t.findMax( ) != NUMS – 2 )

cout << “FindMin or FindMax error!” << endl;

for( i = 2; i < NUMS; i+=2 )

if( t.find( i ) != i )

cout << “Find error1!” << endl;

for( i = 1; i < NUMS; i+=2 )

{

if( t.find( i ) != ITEM_NOT_FOUND )

cout << “Find error2!” << endl;

}

BinarySearchTree t2( ITEM_NOT_FOUND );

t2 = t;

for( i = 2; i < NUMS; i+=2 )

if( t2.find( i ) != i )

cout << “Find error1!” << endl;

for( i = 1; i < NUMS; i+=2 )

{

if( t2.find( i ) != ITEM_NOT_FOUND )

cout << “Find error2!” << endl;

}

return 0;

}

 

 

Vector : The Vector ADT extends the notion of� array by storing a sequence of arbitrary objects An element can be accessed, inserted or removed by specifying its rank (number of elements preceding it) An exception is thrown if an incorrect rank is specified (e.g., a negative rank)

 

The Stack ADT stores arbitrary objects Insertions and deletions follow the last-in first-out scheme.

The Queue ADT stores arbitrary objects Insertions and deletions follow the first-in first-out scheme Insertions are at the rear of the queue and removals are at the front of the queue Main queue operations:

enqueue(object): inserts an element at the end of the queue object

dequeue(): removes and returns the element at the front of the queue

 

A singly linked list is a concrete data structure consisting of a sequence of nodes

Each node stores

􀂄 element

􀂄 link to the next node

 

A doubly linked list provides a natural implementation of the List ADT Nodes implement Position and store:

􀂄 element

􀂄 link to the previous node

􀂄 link to the next node

 

A tree is an abstract model of a hierarchical structure A tree consists of nodes with a parent-child relation

 

Root: node without parent (A)

Internal node: node with at least one child (A, B, C, F)

External node (a.k.a. leaf): node without children (E, I, J, K, G, H, D)

Ancestors of a node: parent, grandparent, grand-grandparent, etc.

Depth of a node: number of ancestors

Height of a tree: maximum depth of any node (3)

Descendant of a node: child, grandchild, grand-grandchild, etc.

Subtree: tree consisting of a node and its descendants

 

 

A binary tree is a tree with the following properties:

􀂄 Each internal node has two children

􀂄 The children of a node are an ordered pair

We call the children of an internal node left child and right child

Alternative recursive definition: a binary tree is either

􀂄 a tree consisting of a single node,

or

􀂄 a tree whose root has an ordered pair of children, each of which is a

binary tree

 

Notation

n number of nodes

e number of

external nodes

i number of internal

nodes

h height

 

Properties:

􀂄 i + 1

􀂄 = 2− 1

􀂄 h ≤ i

􀂄 h ≤ (− 1)/2

􀂄 e ≤ 2h

􀂄 h ≥ log2 e

􀂄 h ≥ log2 (+ 1) – 1

 

A priority queue stores a collection of items

An item is a pair (key, element)

Main methods of the Priority Queue ADT

􀂄 insertItem(k, o) inserts an item with key k and element o

􀂄 removeMin() removes the item with smallest key and returns its element.

 

A heap is a binary tree storing keys at its internal nodes and satisfying the

following properties:

􀂄 Heap-Order: for every internal node v other than the root,

key(v) ≥ key(parent(v))

􀂄 Complete Binary Tree: let be the height of the heap

􀂊 for i = 0, . , − 1, there are 2nodes of depth i

􀂊 at depth − 1, the internal nodes are to the left of the external nodes

The last node of a heap is the rightmost internal node of depth – 1

 

A hash function maps keys of a given type to integers in a fixed interval [0, − 1]

Example:

h(x) = mod is a hash function for integer keys

The integer h(x) is called the hash value of key x

A hash table for a given key type consists of

􀂄 Hash function h

􀂄 Array (called table) of size N

When implementing a dictionary with a hash table, the goal is to store item (ko) at index i h(k)

 

A hash function is usually specified as the composition of two

functions:

Hash code map:

h1: keys → integers

Compression map:

h2: integers → [0, − 1]

The hash code map is applied first, and the compression map is applied next on the result, i.e.,

h(x) = h2(h1(x))

The goal of the hash function is to �disperse� the keys in an apparently random way.

 

The dictionary ADT models a searchable collection of key element items

The main operations of a dictionary are searching, inserting, and deleting items

Multiple items with the same key are allowed

 

 

Merge-sort on an input

sequence with n

elements consists of

three steps:

􀂄 Divide: partition into

two sequences S1 and S2

of about n/2 elements

each

􀂄 Recur: recursively sort S1

and S2

􀂄 Conquer: merge S1 and

S2 into a unique sorted

Sequence

 

 

Algorithm mergeSort(S, C)

Input sequence with n

elements, comparator C

Output sequence sorted

according to C

if S.size() 1

(S1, S2) ← partition(Sn/2)

mergeSort(S1, C)

mergeSort(S2, C)

← merge(S1, S2)

 

 

Quick-sort is a randomized

sorting algorithm based

on the divide-and-conquer

paradigm:

􀂄 Divide: pick a random

element (called pivot) and

partition into

􀂊 elements less than x

􀂊 elements equal x

􀂊 elements greater than x

􀂄 Recur: sort and G

􀂄 Conquer: join Land G

 

We represent a set by the sorted sequence of its elements

􀂊 By specializing the auxliliary methods the generic merge algorithm can be used to perform basic set operations:

􀂄 union

􀂄 intersection

􀂄 subtraction

􀂊 The running time of an operation on sets and should be at most O(nA nB)

 

Quick-select is a randomized selection algorithm based on the prune-and-search paradigm:

􀂄 Prune: pick a random element x(called pivot) and partition into

􀂊 elements less than x

􀂊 elements equal x

􀂊 elements greater than x

􀂄 Search: depending on k, either answer is in E, or we need to recurse in either or G

 

Big O:

F(n) (- O(g(n)) if there exists c > 0 and an integer n0 > 0 such that f(n) <= c*g(n) for all n >= n0.

 

Big Omega

F(n) (- O(g(n)) if there exists c > 0 and an integer n0 > 0 such that f(n) >= c*g(n) for all n >= n0.

 

Big theta

F(n) (- O(g(n)) if there exists c > 0 and an integer n0 > 0 such that f(n) = c*g(n) for all n >= n0.

.NET

ASP.NET 4.0

I will be blogging on ASP.NET and publishing on the following topics of ASP.NET 4.0

Introduction to ASP.NET

  • Agenda :
    • Brief on HTML
    • Difference between HTML and XML
    • Why XML is important.
    • Static Web Pages vs Dynamic Web Pages.
    • TAG affect how text is displayed on Web Page. E.g. <b> text </b> <i> italic</i> è text italic.

<b color=blue> this</b> this

Difference between Web Forms   and ASP.NET MVC 3.0

                        Web Forms                                MVC
  •   Web Forms are based on ASP.NET and it is high   level programming framework.
ASP.NET   MVC is also based on ASP.NET and it is low level programming technology.
  •   Web Forms are similar to User Interface   controls of windows App. It is event based controls.
ASP.NET   MVC uses HTML controls and requires knowledge of JS plugins.
  •   Web Forms Controls encapsulate HTML, JS and   CSS. They databind Charts, Grid, Tables etc.
ASP.NET   MVC directly use HTML controls hence require deep knowledge of HTML and HTTP.   They have total control of HTML markup.
  •   The unit testing is not part of the framework,   needs to be manually incorporated.
ASP.NET   MVC supports unit testing, TDD and Agile.
  •   Browser differences are handled by the Web   Forms
Browser   differences and OS compatibility needs to be care by the developer.

What is ASP.NET

ASP.NET is free framework using C# and VB. Visual studio provides Visual Web Developer for free to develop standalone website. The Intellisense of Visual Studio helps to understand the libraries used for developing website. Visual Studio has powerful debugging tool. ASP.NET is part of .NET, Website Spark is a development program to develop website and it is free software.

HTML XML
How text is   displayed Provides information about the text
HTML is parsed and interpreted by browser and then   displayed. Using XML to provide a data for information requested and provides   the data as response in XML.
 
Static Web Pages Dynamic Web Pages
A plain HTML page which doesn’t change   during interaction with the user is Static Web Page. An .aspx page is analyzed and CLR   executes code in it by server to generate dynamic page. Finally the response   data is converted to HTML page for each request.

Working with the Server

  • Server does everything for every user request.
  • Dynamic Page forces Server to do everything lead to poor performance.
  • Server manages the HTTP state session.

The .aspx page is a dynamic page follows the request and response model. And it has unique session for each request.

Client information and session information to recognize the request originate information for the server.

When 1st request is sent, server creates session and is managed by server. Session management require server resources. Time out limit is set by the web application, after limit the session expires. So before the session expires an interaction between the client and server should be made.

1st request à Parser à compile à IL code in Assembly Cache à Memory Execute http runtime.

2nd request ——————————————————————àMemory Execute http runtime.

Server Controls

Server Control : Server control is configured before hand during design time. The  request for the web page makes the dynamic page to execute the program logic at the server and deliver it as HTML control to client. E.g. gridView control, calendar control.

Code Behind: VB/C# code in another page with extension .cs is code behind of web page.

Inline Code: Javascript code and HTML tags are inline code in web page.

ASP.NET Framework which is composed of WebMatrix, WebForms, ASP.NET MVC is required to build websites, web application.

State Management and AutoPostback

Web pages are HTTP based and are stateless, the stateless nature is a problem.

ASP.NET maintains the HTTP state automatically. set EnableViewState to true in properties window to enable Postback.

What is ViewState ? ViewState  is a hidden value containing state information.

Autopostback – When a  whole page is sent back to server with new option selected is a AutopostBack property.

ASP.NET supports client side scripting.

Validation controls: A special control under validation section in toolbox; Select required control in it and drop  them on the web design. Select the control to validate. Only works with Server controls. So Validation controls to works with HTML convert html control to Server control.

.NET

C# Generics

  1. Introduction
  2. Infrastructure for Generics
  3. Generic Types and Inheritance
  4. Contravariant and Covariant Generic Types
  5. Verifiability and Constraints

C# Generics

Generics is mechanism offered by the common language runtime (CLR) and programming languages that provides one more form of code reuse : algorithm reuse

Microsoft design guidelines that generic parameter variables should either be called T or least start with an uppercase T. The uppercase T stands for type, just as I stands for interface as in IEnumerable.

Generics provide the following big benefits to developers:

– Source code protection : The developer using a generic algorithm doesn’t need to have access to the algorithm’s source code.

– Type safety : When a generic algorithm is used with a specific type, the compiler and the CLR understand this and ensure that only objects compatible with the specified data type are used with the algorithm. Attempting to use an object of an incompatible type will result in either a compiler error or a runtime exception being thrown.

– Cleaner code : The code is easier to maintain, since the compiler enforces type safety, fewer casts are required the code.

– Better Performance : Generic algorithm can be created to work with a specific value type and the CLR no longer has to do any boxing and casts are unnecessary. The CLR doesn’t have to check the type safety of the generated code and this enhances the performance of the algorithm.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
public static class MyApp {
public static void Main() {
ValueTypePerfTest();
ReferenceTypePerfTest();
}
private static void ValueTypePerfTest() {
const Int32 count = 10000000;
using (new OperationTimer(“List<Int32>”)) {
List l = new List(Count);
for (Int32 n = 0; n < count; n++) {
l.Add(n) ;
Int32 x = l[n];
}
l = null; // Make sure this gets GC’d
}
using (new OperationTimer(“ArrayList of Int32”)) {
ArrayList a = new ArrayList();
for (Int32 n = 0; n < count; n++) {
a.Add(n);
Int32 x = (Int32) a[n];
}
a = null; // Make sure this gets GC’d
}
}
private static void ReferenceTypePerfTest () {
const Int32 count = 10000000;
using (new OperationTimer(“List<String>”)) {
List<String> l = new List<String>();
for (Int32 n = 0; n < count; n++) {
l.Add(“X”) ;
String x = l[n];
l = null; // Make sure this gets GC’d
}
using ( new OperationTimer(“ArrayList of String”)) {
ArrayList a = new ArrayList();
for (Int32 n = 0; n < count; n++) {
a.Add(“X”);
String x = (String) a[n];
}
a = null; // Make sure this gets GC’d
}
}
}
// This class is useful for doing operations performance timing
internal sealed class OperationTimer : IDisposable {
private Int64 m_startTime;
private String m_text;
private Int32 m_collectionCount;
public OperationTimer(String text) {
PrepareForOperation();
m_text = text;
m_collectionCount = GC.CollectionCount(0) ;
// This should be the last statement in this
// method to keep timing as accurate as possible
m_startTime = Stopwatch.GetTimestamp();
}
public void Dispose() {
Console.WriteLine(“(0,6:###.00) seconds (GCs={1,3}) {2}”,
(StopWatch.GetTimestamp() – m_startTime) /
(Double) StopWatch.Frequency, GC.CollectionCount(0) –
m_collectionCount, m_text);
}
private static void PrepareForOperation() {
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
}
}

When I run this program

.20 seconds (GCs = 0) List<Int32>

3.30 seconds (GCs = 45) ArrayList of Int32

.50 seconds (GCs = 6) List<String>

.58 seconds (GCs = 6) ArrayList of String

The output here shows that using the generic List with Int32 type is much faster than using the non-generic ArrayList algorithm with Int32. Also using the value type – Int32 with ArrayList causes a lot of boxing operations to occur which results in 45 GC where as List algorithm requires 0 GC.

So it doesn’t appear that the generic List algorithm is of any benefit here. But it gives a cleaner code and compile time type safety.

Generics inside FCL

Microsoft recommends that developers use the generic collection classes and now discourages use of the non-generic collection classes for several reasons. First, the non-generic collection classes are not generic and so you don’t get the type safety, cleaner code, and better performance that you get when you use generic collection classes. Second the generic classes have a better object model than non-generic classes. For example, fewer methods are virtual, resulting in better performance, and new members have been added to the generic collections to provide new functionality.

The FCL ships with many generic interface definitions so that the benefits of generics can be realized when working with interface as well. The commonly used interfaces are contained in the System.Collections.Generic namespace.

Infrastructure for Generics

Microsoft had to provide the following for Generics to work properly.

– Create new IL instructions that are aware of type arguments

– Modify the format of existing metadata tables so that type names and methods with generic parameters could be expressed.

– Modify the various programming languages to support the new syntax, allowing developers to define and reference generic types and methods

– Modify the compilers to emit the new IL instructions and the modified metadata format.

– Modify the just-in-time(JIT) compiler to process the new type argument aware IL instructions that produce the correct native code.

– Create new reflection members so that developers can query types and members to determine if they have generic parameters. Created new methods using Reflection had to be defined so that developers could create generic type and method definitions at runtime.

– Modify the debugger to show and manipulate generic types, members, fields and local variables.

– Modify the Microsoft VS Intellisense feature to show specific member prototypes when using a generic type or a method with a specific data type.

Open and Closed Types

The CLR creates an internal data structure for each and every type in use by an application. These data structures are called type objects. A type with generic type parameters is still considered a type and the CLR will create an internal type object for each of these. This applies to reference types, value types, interface types and delegate types. A type with generic type parameters is called Open type and the CLR doesn’t allow any instance of an open type to be constructed .

When code references a generic type it can specify a set of generic type arguments. If actual data types are passed in for all of the type arguments, the type is called a closed type, and the CLR does allow instances of a closed type to be constructed.

For e.g.

using System;

using System.Collections;

using System.Collections.Generic;

// A partially specified open type

internal sealed class DictionaryStringKey<TValue> : Dictionary<String, TValue> {

}

public static class MyApp {

public static void Main() {

Object o = null;

//Dictionary<,> is an open type having 2 new type parameters

Type t = typeof(Dictionary<,>);

// try to create an instance of this type ( fails)

o = CreateInstance(t);

Console.WriteLine();

//DictionaryStringKey<,> is an open type having 1 type parameter

t = typeof(DictionaryStringKey<>);

// Try to create an instance of this type fails

o = CreateInstance(t)

Console.WriteLine();

// DictionaryStringKey<Guid> is a closed type

t = typeof(DictionaryStringKey<Guid>);

// Try to create an instance of this type succeeds

o = CreateInstance(t)

Console.WriteLine(“Object types=”+o.GetType());

}

private static Object CreateInstance(Type t) {

Object o = null;

try {

o = Activator.CreateInstance(t);

Console.Write(“Created instance of (0)”,t.ToString());

}

catch ( ArgumentException e ) {

Console.WriteLine(e.Message);

}

return 0;

}

}

When we execute this code, we get the following output:

Cannot create an instance of System.Collections.Generic.Dictionary 2[TKey, TValue] because Type.ContainsGenericParameters is true.

Cannot create an instance of DictionaryStringKey 1[TValue] because Type.ContainsGenericParameters is true.

Created an instance of DictionaryStringKey `1[System.Guid]

Object Type = DictionaryStringKey `1[System.Guid]

In the output we see that the names end with a backtick (`) followed by a number, it is type’s arity which indicates the number of type parameters required by the type.

Generic Types and Inheritance

A generic type is a type, and it can be derived from any other type. When you use generic type and specify type arguments, you are defining a new type object in the CLR, and the new type object is derived from whatever type generic type was derived from. I.e. List <T> is derived from Object, List<String> and List<Guid> are also derived from Object. Similarly, DictionaryStringKey<TValue> is derived from DictionaryStringKey<String, TValue> , DictionaryStringKey<Guid> is also derived from Dictionary<String, Guid>. Consider an example below

internal class Node {

protected Node m_next;

public Node(Node next) {

m_next = next;

}

}

internal sealed class TypedNode<T> : Node {

public T m_data;

public TypedNode(T data) : this(data, null) {

}

public TypedNode(T data, Node next) : base(next) {

m_data = data;

}

public override String ToString() {

return m_data.ToString() = (( m_next ! = null) ? m_next.ToString() : String.Empty);

}

}

Now the main code will be as follows

private static void DifferentDataLinkedList() {

Node head = new TypedNode<Char>(‘,’);

head = new TypedNode<DateTime>(DateTime.Now, head);

head = new TypedNode<String>(“Today is”, head)’;

Console.WriteLine(head.ToString());

}

Generic Type Identity

C# does offer a way to use simplified syntax to refer to a generic closed type while not affecting type equivalence at all; you can use the good old using directive at the top of your source code file. Here is an example:

using DateTimeList = System.Collections.Generic.List<System.DateTime>;

Using directive is really just defining a symbol called DateTimeList. As the code compiles, the compiler substitutes all occurrences of DateTimeList with System.Collections.Generic.List<System.DateTime>. This just allows developers to use a simplified syntax without affecting the actual meaning of the code, and therefore, type identity and equivalence are maintained. So now when the following line executes the sameType will initialized to true.

Boolean sameType = (typeof(List<DateTime>) == typeof(DateTimeList));

Code Explosion

When a method that uses generic type parameters is JIT-compiled, the CLR takes the method IL, substitutes the specified type arguments, and then creates native code that is specific to that method operating on the specified data types. The CLR keeps generating the native code for every method/type combination. This is referred to as code explosion.

Fortunately, CLR has some optimizations built into it to reduce code explosion. First, if a method is called for a particular type argument, and later the method is called again using the same type argument, the CLR will compile the code for this method/type combination just once. So if assembly uses List<DateTime>, and a completely different assembly also uses List<DateTime>, the CLR will compile the methods for List<DateTime>. This reduces the code explosion. The CLR has another optimization: the CLR considers all reference type arguments to be identical and the code can be shared. For example, the code compiled by the CLR for List<String>’s method can be used for List<Stream>’s methods, since String and Stream are both reference types. In fact, for any reference type, the same code will be used. But if the type argument is a value type, the CLR must produce native code specifically for that value type. The reason is the value types can vary in size.

Generic Interfaces

CLR supports Generic Interface to avoid boxing and loss of compile time type safety. A reference or value type can implement a generic interface by specifying type arguments, or a type can implement a generic interface by leaving the type arguments unspecified.

The definition of a generic interface in the System.Collections.Generic namespace that is part of FCL :

public interface IEnumerator<T> : IDisposable, IEnumerator {

T Current { get; }

}

Eg of Generic Interface

internal sealed class Triangle : IEnumerator<Point> {

private Point[] m_vertices;

// IEnumerator<Point>’s Current property is of type Point

public Point Current { get {….}}

…..

}

Now the Generic class that implements Generic Interface

internal sealed class ArrayEnumerator<T> : IEnumerator<T> {

private T[] m_array;

// IEnumerator<T>’s Current property is of type T

public T Current { get {…} }

….

}

Generic Delegates

The CLR supports generic delegates to ensure that any type of object can be passed to a callback method in a type-safe way. Furthermore generic delegates allow a value type instance to be passed to a callback method without any boxing. “Delegates,” a delegate is really just a class definition with four methods: a constructor, an invoke method, a BeginInvoke method, and an EndInvoke method. When you define a delegate type that specifies type parameters, the compilers emits the delegate class’s methods and the type parameters are applied to any methods having parameters/return values of the specified type parameter.

For example, if you define a generic delegate like this:

public delegate TReturn CallMe<TReturn, TKey, TValue>(TKey key, TValue value);

The compiler turns that into a class that logically looks like this:

public sealed class CallMe<TReturn, TKey, TValue> : MulticastDelegate {

public CallMe(Object object, IntPtr method);

public virtual TReturn Invoke(TKey key, TValue value);

public virtual TReturn IAsyncResult BeginInvoke(TKey key, TValue value,

AsyncCallback callback, Object object);

public virtual TReturn EndInvoke(IAsyncResult result);

}

It is recommended that one should use the generic Action and Func delegates that come predefined in the Framework Class Library wherever possible.

Contravariant and Covariant Generic Types

Each of a delegate’s generic type parameters can be cast to a variable of generic delegate type where the generic parameter type differs, A generic type parameter can be of the following:

Invariant : A generic type parameter that cannot be changed.

Contravariant : A generic type parameter that can change from a class to a class derived from it. The contravariant can appear as only input parameters with in keyword

Covariant : A generic type parameter that can change from a class to one of its base classes. In C#, you indicate covariant generic type parameters with the out keyword which can appear only in output positions such as a method’s return type.

public delegate TResult Func<in T, out TResult>(T arg);

In this generic type parameter T is marked with the in keyword making it contravariant; and the generic type parameter TResult is marked with the out keyword, making it covariant .

If I have variable declared as follows:

Func<Object, ArgumentException> fn1 = null;

I can cast it to another Func type, where the generic type parameters are different:

Func<String, Exception> fn2 = fn1; // no explicit cast is required here

Exception e = fn2(“ “);

Here fn1 refers to a function that accepts an Object and returns an ArgumentException. The fn2 variable wants to refer to a method that takes a String and returns an Exception. Since you can pass a String to a method that wants an Object, and since you can take the result of a method that returns an ArgumentException and treat it as an Exception, the code above compiler and is known at compile time to preserve type safety.

Note: Variance is not possible for value types because boxing would be required. Also variance is not allowed on a generic type parameter if an argument of that type is passed to a method using the out or ref keyword. And CLR would throw a following exception if it find this kind of statement :

Invalid variance: They type parameter ‘T’ must be invariantly valid on ‘SomeDelegate<T>.Invoke(ref T)’. ‘T’ is contravariant.”

delegate void SomeDelegate<in T>(ref T t);

When using delegates that take generic arguments and return values, it is recommended to always specify the in and out keywords for contravariance and covariance whenever possible as doing this has no ill effects and enables your delegate to be used in more scenarios.

Here is an example of an interface with a contravariant generic type parameter:

public interface IEnumerator<out T> : IEnumerator {

Boolean MoveNext();

T Current { get; }

}

Since T is contravariant, it is possible to have the following code compile and run successfully:

// This method accepts an IEnumerable of my reference type

Int32 Count(IEnumerable<Object> collection) {…}

….

//The call below passes an IEnumerable<String> to count

Int32 c = count(new[] { “Grant” });

for this reason the compiler team forces you to be explicit when declaring a generic type parameter. Then if you attempt to use this type parameter in a context that doesn’t match how you declared it, the compiler issues an error letting you know that you are attempting to break the contract. If you then decide to break the contract by adding in or out on generic type parameters, you should expect to have to modify some of the code sites that were using the out contract.

Generic Methods

When you define a generic class, struct, or interface, any methods defined in these types can refer to a type parameter specified by the type. A type parameter can be used as a method’s parameter, a method’s return value, or as a local variable defined inside the method. However, the CLR also supports the ability for a method to specify its very own type parameters. And these type parameters can also be used for parameters, return values, or local variables.

internal sealed class GenericType<T> {

private T m_value;

public GenericType( T value) { m_value = value; }

public TOutput Converter<TOutput> () {

TOutput result = (TOutput) Convert.ChangeType(m_value, typeof(TOutput));

return result;

}

}

In this example, you can see that the GenericType class defines its own type parameter(T), and the Converter method defines its own type parameter(TOutput). This allows a GenericType to be constructed to work with any type. The converter method can convert the object referred to by the m_value field to various types depending on what type argument is passed to it when called. The ability to have type parameters and method parameters allows for phenomenal flexibility.

A reasonably good example of a generic method is the two method

private static void swap<T>(ref T o1, ref T o2) {

T temp = o1;

o1 = o2;

o2 = temp;

}

Code can now call swap like this

private static void CallingSwap() {

Int32 n1 = 1, n2 =2;

Console.WriteLine(“n1={0}, n2={1}”, n1, n2);

Swap<Int32>(ref n1, ref n2);

Console.WriteLine(“n1={0}, n2={1}”, n1, n2);

String s1 = “Aidan”, s2 = “Grant”;

Console.WriteLine(“s1={0}, s2={1}”, s1, s2);

Swap<String>(ref s1, ref s2);

Console.WriteLine(“s1={0}, s2={1}”, s1, s2);

}

The variable you pass as an out /ref argument must be the same type as the method’s parameter to avoid a potential type safety exploit.

e.g.

public static class InterLocked {

public static T Exchange<T>(ref T location1, T value) where T: class;

public static T CompareExchange<T>(

ref T location1, T value, T comparand) where T: class;

}

Generic Methods and Type Inference

To help improve code creation, readability, and maintainability, the C# compiler offers type inference when calling a generic method. Type inference means that the compiler attempts to determine the type to use automatically when calling a generic method.

Here is some code that demonstrates type inference:

private static void CallingSwapUsingInference() {

Int32 nl = 1, n2 =2;

Swap(ref n1, ref n2);// Calls Swap<Int32>

String s1 = “Aidan”;

Object s2 = “Grant”;

Swap(ref s1, ref s2);// Error, type can’t be inferred

}

In this code, first call to Swap compiler infers n1 and n2 are Int32 and hence it will invoke Swap with Int32 type parameter. In the second call compiler sees that s1 is String and s2 is Object. Since s1 and s2 are variables of different data types, the compiler can’t accurately infer the type to use for swap’s type argument,and it issues invalid type arguments error for method ‘Swap<T>(ref T, ref T)’ .

Another type is a type that can be defined with multiple methods with one of its methods taking a specific data type and another taking a generic type parameter as shown below in the code

private static void Display(String s) {

Console.WriteLine(s);

}

private static void Display<T>(T o) {

Display(o.ToString()); //Calls Display(String)

}

Here are some ways to call the Display method

Display(“Jeff”); // Calls Display(String)

Display(123); // Calls Display<T>(T)

Display<String>(“Adrian”); // Calls Display<T>(T)

The C# compiler always prefers a more explicit match over a generic match, and therefore, it generates a call to the non-generic Display method that takes a String. For the second call, the compiler can’t call the non-generic Display method that takes a String, so it must call the generic Display method. By the way, it is fortunate that the compiler always prefers the more explicit match; if the compiler had preferred the generic method, because the generic display method calls Display again there would have been infinite recursion.

Verifiability and Constraints

A constraint is a way to limit the number of types that can be specified for a generic argument, Limiting the number of types allows you to do more with those types. Here is a new version of the Min method that specifies a constraint:

public static T Min<T o1, To2> where T : IComparable<T> {

if (o1.CompareTo(o2) < 0) return o1;

return o2;

}

The C# where token tells the compiler that any type specified for T must implement the generic IComparable interface of the same type(T). Because of this constraint, the compiler now allows the method to call the CompareTo method since this method is defined by the IComparable<T> interface.

Now when code references a generic type or method, the compiler is responsible for ensuring that a type argument that meets the constraints is specified.

For e.g.

private static void CallMin() {

Object o1 = “Jeff”, o2 = “Richter”;

Object oMin = Min<Object>(o1, o2); //Error

}

The compiler issues the error because system.Object doesn’t implement the IComparable<Object> interface. In fact, system.Object doesn’t implement any interfaces at all.

The CLR doesn’t allow overloading based on the type parameter names or constraints you can overload types or methods based only on arity. The following e.g. shows that

// It is OK to define the following types

internal sealed class AType {}

internal sealed class AType <T>{}

internal sealed class AType <T1, T2>{}

//error : conflicts with AType<T> that has no constraints

internal sealed class AType<T> where T: IComparable<T> {}

//Error: conflicts with AType<T1, T2>

internal sealed class AType <T3, T4>{}

internal sealed class AnotherType {

private static void M() {}

private static void M<T>() {}

private static void M<T1, T2>() {}

//Error: conflicts with M<T> that has no constraints

private static void M<T>() where T : IComparable<T> {}

//Error

private static void M<T3, T4>() {}

}

In fact, the overriding method is not allowed to specify any constraints on its type parameters at all. However, it can change the names of the type parameters. similarly, when implementing an interface method, the method must specify the same number of type parameters as the interface method and these type parameters will inherit the constraints specified on them by the interface’s method.

E.g.

internal class Base {

public virtual void M<T1, T2>()

where T1 : struct

where T2 : class {

}

}

internal sealed class Derived : Base {

public override void M<T3, T4>()

where T3 : EventArgs //Error

where T4: class //Error

{ }

}

Notice that you can change the names of the type parameters as in the example from T1 to T3 and T2 to T4; however you cannot change constraints.

A type parameter can be constrained using a primary constraint, a secondary constraint, and constructor constraint.

Primary Constraint

A primary constraint can be reference type that identifies a class that is not sealed. You cannot specify one of the following special reference types: System.Object, System.Array, System.Delegate, System.MulticastDelegate, System.Valuetype, System.Enum or System.Void

When specifying a reference type constraint, you are promising the compiler that a specified type argument will either be of the same type or of a type derived from the the constant type. For e.g.

internal sealed class PrimaryConstraintOfStream<T> where T : Stream {

public void M(T stream) {

stream.Close(); //OK

}

};

In this class definition the type parameter T has a primary constraint of Stream. This tells the compiler that code using PrimaryConstraintOfStream must specify a type argument of Stream or a type derived from stream. If a type parameter doesn’t specify a primary constraint, System.Object is assumed. However, the C# compiler issues an error message if you explicitly specify System.Object in your source code.

There are two special primary constraints: class and struct. The class constraint promises the compiler that a specified type argument will be reference type. Any class type, interface type delegate type or array type satisfies this constraint. For e.g.

internal sealed class PrimaryConstraintOfClass<T> where T : class {

public void M() {

T temp = null; // Allowed because T must be a reference type

}

}

In this example setting temp to null is legal because T is known to be a reference type, and all reference type variables can be set to null. If T were unconstrained, the code above would not compile because T could be a value type, and value type variables cannot be set to null.

The struct constraint promises the compiler that a specified type argument will be a value type. Any value type, including enumerations, satisfies this constraint. However, the compiler and the CLR treat any System.Nullable<T> value type as a special type and nullable types do not satisfy this constraint. The reason is because the Nullable<T>type constrains its type parameter to struct, and the CLR wants to prohibit a recursive type such as Nullable<Nullable<T>>

e.g.

internal sealed class PrimaryConstraintOfStruct<T> where T : struct {

public static T Factory() {

//Allowed because all value types implicitly

// have a public parameterless constructor

return new T();

}

}

In this example, newing up a T is legal because T is known to be a value type and all value types implicitly have a public, parameterless constructor. If T were unconstrained, constrained to a reference type or constrained to class, the above code would not compile because some reference types do not have public, parameterless constructors

Secondary Constraint

A type parameter can specify zero or more secondary constraints where a secondary constraint represents an interface type. When specifying an interface type constraint, you are promising the compiler that a specified type argument will be a type argument must specify a type that implements all of the interface constraints

There is another kind of secondary constraint called a type parameter constraint. This kind of constraint is used much less often than interface constraint. It allows a generic type of method to indicate that there must be a relationship between specified type arguments. A type parameter can have zero or more type constraints applied to it. Here is a generic method that demonstrates the use of a type parameter constraint:

private static List<TBase> ConvertIList<T, TBase>(IList<T> list) where T : TBase {

List<TBase> baseList = new List<TBase>(list.count);

for (Int32 index = 0; index < list.Count; index++) {

baseList.Add(list[index]);

}

return baseList;

}

The convertIList method specifies two types parameters in which the T parameter is constrained by the TBase type parameter. This means that whatever type argument is specified for T, the type argument must be compatible with whatever type arguments is specified for TBase. Here is a method showing some legal and illegal calls to convertIList:

private static void CallingConvertIList(){

//Construct and initialize a List<String> (which implements IList<String>)

IList<String> ls = new List <String>();

ls.Add(“A String”);

//Convert the IList<String> to an IList<Object>

IList<Object> lo = ConvertIList<String, Object>(ls);

//Convert the IList<String> to an IList<IComparable>

IList<IComparable> lc = ConvertIList<String, IComparable>(ls);

//Convert the IList<String> to an IList<IComparable<String>>

IList<IComparable<String>> lcs = ConvertIList<String, IComparable<String>>(ls);

//Convert the IList<String> to an IList<IComparable>

IList<String> ls2 = ConvertIList<String, String>(ls);

//Convert the IList<String> to an IList<Exception>

IList<Exception> le = ConvertIList<String, Exception>(ls); //Error

In the first call to ConvertIList, the compiler ensures that String is compatible with Object. Since String is derived from Object, the first call adheres to the type parameter constraint. In the second call to ConvertIList, the compiler ensures that String is compatible with IComparable. Since String implements the IComparable interface, the second call adheres to the type parameter constraint. In the third call to ConvertIList, the compiler ensures that String is compatible with IComparable<String> Since String implements the IComparable<String> interface, the third call adheres to the type parameter constraint. In the fourth call to ConvertIList, the compiler knows that String is compatible with itself. In the fifth call to ConvertIList, the compiler ensures that string is compatible with Exception. Since String is not compatible with Exception, the fifth call doesn’t adhere to they type parameter constraint, and the compiler issues the following message: “error CS0311: The type string cannot be used as type parameter ‘T’ in the generic type or method ‘Program.ConvertIList<T,TBase>(System.Collections.Generic.IList<T>)’. There is no implicit reference conversion from string to System.Exception”.

Constructor Constraints

A type parameter can specify zero constructor constraints or one constructor constraint. When specifying a constructor constraint, you are promising the compiler that a specified type argument will be a non-abstract type that implements a public, parameterless constructor. Note that the C# compiler considers it an error to specify a constructor constraint with the struct constraint because it is redundant; all value types implicitly offer a public, parameterless constructor.

e.g.

internal sealed class ConstructorConstraint<T> where T : new() {

public static T Factory() {

// Allowed because all value types implicitly

// have a public, parameterless constructor and because

// the constraint requires that any specified reference

// type also have a public, parameterless constructor

return new T();

}

}

In the above example, newing up a T is legal because T is known to be a type that has a public, parameterless constructor. This is certainly true of all value types, and the constructor constraint requires that it be true of any reference type specified as a type argument.

Casting Generic Type

Casting a generic type variable to another type is illegal unless you are casting to a type compatible with a constraint:

private static void CastingGenericTypeVariable1<T>(T obj) {

Int32 x = (Int32) obj; //Error

String s = (String) obj; //Error

}

The compiler issues an error on both lines above because T could be any type, and there is no guarantee that the casts will succeed. You can modify this code to get it to compile by casting to Object first:

private static void CastingAGenericTypeVariable2<T>(T obj ) {

Int32 x = (Int32) (object) obj; // No Error

String s = (String) (Object) obj; // No Error

}

If a casting of reference type needs to be done we can use ‘as’ operator. For e.g.

private static void CastingAGenericTypeVariable3<T>(T obj) {

String s = obj as String; // No error

}

Default value for Generic Type Variable:

Setting a generic type variable to null is illegal unless the generic type is constrained to a reference type.

private static void SettingAGenericTypeVariableToNull<T>() {

T temp = null; //C50403 – Cannot convert null to type parameter T

}

Since T is unconstrained, it could be a value type, and setting a variable of a value type to null is not possible. If T were constrained to a reference type, setting temp to null would compile and run just fine. C# team felt that it would be useful to give developers the ability to set a variable to a default value. So the C# compiler allows you to use the default keyword to accomplish this

private static void SettingAGenericTypeVariableToDefaultValue<T>(){

T temp = default(T); // OK

}

The use of the default keyword above tells the C# compiler and the CLR’s JIT compiler to produce code to set temp to null if T is a reference type and to set temp to all-bits-zero if T is a value type.

Comparison of Generic Type variables:

Comparing a generic type variable to null by using the == or != operator is legal regardless of whether the generic type is constrained:

private static void ComparingAGenericTypeVariableWithNull<T>(T obj) {

if(obj == null) { /* Never executes for value type */ }

}

Since T is unconstrained, it could be a reference type or a value type. If T is a value type, obj can never be null. The C# compiler does not issue an error, instead, it compiles the code just fine. When this method is called using a type argument that is a value type, the JIT compiler sees that the if statement can never be true, and the JIT compiler will not emit the native code for the if test or the code in the braces. If I had used the != operator, the JIT compiler would not emit the code for the if test and it will emit the code inside the if’s braces.

By the way, if T had been constrained to a struct, the compiler would have thrown an error.

Comparing two Generic Type variables

Comparing two variables of the same generic type is illegal if the generic type parameter is not known to be a reference type:

private static void ComparingTwoGenericTypeVariables<T>(T o1, T o2) {

if(o1 == o2) { } //Error

}

In this example T is unconstrained, and whereas it is legal to compare two reference type variables with one another, it is not legal to compare two value type variables with one another unless the value type overloads the == operator.

By the way, if T had been constrained to a struct, the compiler would have thrown an error.

Avoid Generic Type as Operands

The operators such as +, –, *, and / can’t be applied to variables of a generic type because the compiler doesn’t know the type at compile time. This means that you can’t use any of these operators with variables of a generic type. So it is impossible to write a mathematical algorithm that works on an arbitrary numeric data type.

Digg This
.NET

Types and Common Type System

What is Type in .NET Framework

The .NET Framework is built around types. A type in .NET is a class, structure, interface, enumeration, or delegate. A type is the fundamental unit of programming in .NET. In C#, a type can be declared using the class, structure, and interface keywords. Every piece of code that you write in .NET, even the main program for your application, must be a member of some type.

In .NET there are two main classifications of types and every type is derived from a Root Reference Type named System.Object (directly or indirectly through another base type).

  • Value Type
      • User Defined Value Types (Structures)
      • Enumeration
  • Reference Type
      • User Defined Types (Classes)
      • Array
      • Delegate

    The runtime requires every type to ultimately derive from System.Object type. This means that the following code is identical

    // Implicitly derived from Object
    class Employee {
    ….
    }
    //Explicitly derived from Object
    class Employee : System.Object {
    ….
    }

    Every instance in .NET is derived from System.Object, so it is guaranteed that every object of every type has a minimum set of methods. Explicitly, System.Object class offers the public listed methods given below

    Public class Object {
    public virtual bool Equals(object);
    public virtual int GetHashCode();

    public virtual string ToString();

    public Type GetType();

    // static
    public static bool Equals(object, object);

    //protected
    ~Object();  // Finalize
    protected object MemberwiseClone();
    }

    Public Methods Description
    Equals Returns true if two objects have the same value
    GetHashCode Returns a hash code for the objects type. A type should override this method if its objects are to be used as a key in a hash table collection. The method should provide a good distribution for its objects.
    ToString returns the full name of the type. However it is common to override this method so that it returns a String object containing a representation of the object state. For e.g. the core types such as Boolean and Int32, override this method to return a string representation of their values.
    Gettype Returns an instance of a type derived object that identifies the type of the object used to call GetType. The returned Type object can be used with the reflection classes to obtain metadata information about the object’s type.
    Protected Methods Description
    MemberwiseClone This nonvirtual method creates a new instance of the type and sets the new object’s instance to be identical to this object’s instance fields. A reference to the instance is returned.
    Finalize This virtual method is called when the garbage collector determines that object is garbage before memory for the object is reclaimed. Types that require cleanup when collected should override this method.

    The advantage of deriving from System.Object means that code is verify If all of your code is a member of a type, as long as you can guarantee type safety—in other words, as long as you can guarantee that it is impossible to coerce an object of one type into behaving like another type that it is not assignment compatible with you can go a long way toward guaranteeing that the code is safe. In addition to making it easy to write code that is more secure, less error prone, and easier to debug,

    Microsoft also wants to enable an unprecedented level of  cross-language interoperability in the .NET Framework. One of the key enabling technologies in the .NET Framework that makes this possible is the Common Type System (CTS). The CTS provides a common set of types for all CLR-compliant languages. With the CTS, Microsoft has created a type system that all CLR-compliant programming languages share. Table 3–1 shows a list of the types supported by the CTS. The definitions of all of these types can be found in the System namespace in the Framework libraries,

    Figure below  Widely Used Types in the .NET Framework  (REFERENCE mdsn)

    Common Types System
    Common Types System

    Type

    Inheritance

    Properties and Fields

    Methods

    Total

    System.Int32

    0

    8438

    6756

    15194

    System.String

    0

    2406

    6484

    8890

    System.Object

    2779

    456

    2947

    6182

    System.IntPtr

    0

    397

    1661

    2058

    System.Boolean

    0

    943

    1096

    2039

    System.EventHandler

    0

    4

    1766

    1770

    System.IComparable

    1158

    0

    0

    1158

    System.IConvertible

    1139

    0

    0

    1139

    System.IFormattable

    1135

    0

    0

    1135

    System.Enum

    1120

    0

    0

    1120

    System.Type

    5

    48

    659

    712

    System.Runtime.Serialization.ISerializable

    617

    0

    0

    617

    System.IDisposable

    602

    0

    0

    602

    System.Single

    0

    86

    505

    591

    System.ICloneable

    574

    0

    0

    574

    System.ValueType

    535

    0

    3

    538

    System.Int16

    0

    345

    139

    484

    System.Collections.IEnumerable

    472

    1

    9

    482

    System.Byte[]

    0

    46

    375

    421

    System.ComponentModel.IComponent

    353

    0

    42

    395

    System.MulticastDelegate

    346

    0

    0

    346

    System.UInt32

    0

    105

    227

    332

    System.IAsyncResult

    13

    3

    315

    331

    System.Byte

    0

    213

    112

    325

    System.UIntPtr

    0

    0

    314

    314

    System.AsyncCallback

    0

    0

    307

    307

    System.Int64

    0

    66

    234

    300

    System.Collections.ICollection

    261

    2

    34

    297

    System.Object[]

    0

    21

    256

    277

    System.Int32&

    0

    0

    267

    267

    System.Array

    233

    0

    32

    265

    System.Attribute

    222

    0

    37

    259

    System.Double

    0

    25

    218

    243

    System.Reflection.Emit.OpCode

    0

    222

    20

    242

    System.Globalization.CultureInfo

    0

    6

    227

    233

    System.Windows.Forms.IWin32Window

    171

    0

    16

    187

    System.String[]

    0

    29

    152

    181

    System.Int32[]

    0

    10

    171

    181

    System.Drawing.Rectangle

    0

    16

    164

    180

    System.Char

    0

    36

    142

    178

    System.DateTime

    0

    40

    134

    174

    System.Exception

    22

    6

    145

    173

    System.IO.Stream

    23

    3

    146

    172

    Figure below shows  Mapping the Basic CLR Types

    System Types Visual Basic .NET Managed C++ C#
    System.Boolean Boolean bool bool
    System.SByte N/A byte sbyte
    System.Int16 Short short short
    System.Int32 Integer long int
    System.Int64 Long __int64 long
    System.Byte Byte byte byte
    System.UInt16 N/A unsigned short ushort
    System.UInt32 N/A unsigned long uint
    System.UInt64 N/A unsigned __int64 ulong
    System.Single Single float float
    System.Double Double double double
    System.Char Char char char
    System.String String System::String string
    System.DateTime Date N/A N/A
    System.Decimal Decimal N/A decimal

    Microsoft has defined a subset of the CTS and features supported by the CLR that all languages must support as a minimum. This subset is known as the Common Language Specification (CLS). For compiler vendors, supporting the CLS means that your language can use any CLS-compliant class library or framework.

    The CTS defines the full set of types supported by the CLR and available internally to any .NET programming language, the CLS defines the subset of the CTS that you must restrict yourself to and a set of rules that compiler and framework developers must adhere to, in order to ensure that their software is usable by all CLR-compliant programming languages.

    Some examples of the rules in the CLS are as follows:

    • A type is CLS compliant if its public interfaces, methods, fields, properties, and events contain only CLS-compliant types or are marked explicitly as not CLS compliant.
    • A CLS Consumer can completely use any CLS-compliant type.
    • A CLS Extender is a CLS consumer tool, and it can also extend (inherit from) any CLS-compliant base class, implement any CLS-compliant interface, and use any CLS-compliant custom attribute on any type, method, field, parameter, property, or event.

    The CLR requires all objects to be created using the new operator, The following statement shows Empl instance creation:

    Empl e = new Empl(“ConstructorParam1”);

    The new operator is encounter by CLR, CLR asks new to perform following operations:

    1. CLR calculates the required bytes by all instance fields defined in the type and all of its base types up to and including System.Object.
    2. It allocates memory for the object by allocating the number of bytes required for the specified type from the managed heap, this allocated memory is initialized to zero.
    3. It initializes the object’s type object pointer and sync block index members.
    4. The type’s instance constructor is called, passing it any arguments specified in the call to new. Most compilers automatically emit code in a constructor to a call a base class’s constructor. Each constructor is responsible for initializing the instance fields defined by the type whose constructor is called. Eventually System.Object’s constructor is called, and this constructor method does nothing but return.

    After new has performed all of these operations, it returns the reference to the newly created object. Also the developer need not to have worry about delete operator anymore, The CLR uses a garbage-collected environment that automatically detects when objects are no longer being used or accessed and frees the object’s memory automatically.

    Casting Between Types

    At runtime, the CLR always knows what type an object is. As we already know that an object’s exact type can identified by calling the GetType method. Because this method is non virtual, it is impossible for a type to spoof another type.

    CLR allows you to cast an object to its type or to any of its base types without requiring you to specify the casting syntax since it is considered implicit conversions. However the developer does need to explicitly cast an object to any of its derived type since such a cast could fail at runtime. The following code shows it why:

    // This type is implicitly derived from System.Object.

    internal class Empl {

    ……

    }

    public sealed class Program{

                public static void Main() {

                // No cast needed since new returns an Empl object

                // and object is a base type of Employee.

                Object o = new Employee();

                // Cast required since Empl is derived from object.

                // Other languages ( such as VB) might not require

                // this cast to compile

                Empl e = (Employee) e;

    }

    At runtime, the CLR checks casting operations to ensure that casts are always to the object’s actual type or any of its base types. For e.g. the following code will compile, but at runtime, an invalidCastException will be thrown :

    internal class Empl {

    ……

    }

    public sealed class Program{

    public static void Main() {

                // construct a Manager object and pass it to PromoteEmployee.

    // A manageer IS-A Object: PromoteEmployee runs OK

    Manager m = new Manager();

    PromoteEmployee(m) ;

    // Construct a DateTime object and pass it to PromoteEmployee.

    // A DateTime is NOT derived from Employee. PromoteEmployee

    // throws a System.InvalidCastException exception.

    DateTime newYears = new DateTime(2010, 1, 1);

    PromoteEmployee(newYears);

    }

    public static void PromoteEmployee(Object o) {

    // At this point, the compiler doesn’t know exactly what type of object o refers to.

    // so compiler allows that code to compile. However, at runtime, the CLR does know

    //what type o refers to (each time the cast is performed) and it checks whether the

    //object’s type is Employee or any type that is derived from Employee.

    Employee e = (Employee)o;

    }

    }

    Because Manager is derived from Employee, the CLR performs the cast and allows PromoteEmployee to continue executing. However, inside PromoteEmployee, the CLR checks the cast and detects that o refers to a DateTime object and is therefore not an Employee or any type derived from Employee. At this point, the CLR can’t allow the cast and throws a System.InvalidCastException.

    If the CLR had allowed the cast the code is unpredictable leading to application crash caused by the ability of types to easily spoof other types. This possibility of conversion is known as Type Spoofing, which is the cause of many security breaches and compromises an application’s stability and robustness. Type safety is therefore an extremely important part of the CLR.

    The “is” & “as” operators for casting objects:

    The C# language is to use the is operator. The is operator checks whether an object is compatible with a given type, and the result of the evaluation is a Boolean : true or false. The “is” operator never throw exception, it always evaluates to any Boolean value.

    Object o = new Object();

Boolean b1 = (o is Object); // b1 is true

b1 = (o is Employee);//b1 is now false

if the object reference is null, the is operator always returns false because there is no object available to verify its existence.

The is operator implemented as follows

if (o is Employee) {

Employee e = (Employee) o;

// Use e within the remainder of the “if” statement.

}

The CLR’s type checking improves security, but it certainly comes at a performance cost, bcoz in the above example CLR verifies the type referred to by the variable o and CLR must ascend the hierarchy tree verifying each base type against the specified type (Employee).

The above statement can be simplified by using “as” operator:

Employee e = o as Employee;

if (e != null) {

// Use e within the ‘if’ statement.

}

In the above code, the CLR verifies whether o is compatible with the Employee type it will be an instance of Employee else it will be null. Then CLR after evaluation returns true if it is compatible and false if e is incompatible because e is now null. similar to “is” operator “as” operator also never emits an exception.

using directive

The C# provide a keyword “using” to avoid using namespace qualified types in the specified region/block  of code, the following e.g. shows how using keyword can be used to avoid by the developer from typing full  qualified type name and enhance readability.

using System.IO;

using System.Text;

public sealed class Program {

public static void Main() {

FileStream fs = new FileStream(….);

StringBuilder sb = new StringBuilder();

}

}

The C# using directive instructs the compiler to try prepending different prefixes to a type name until a match is found.

In the above example, if the C# compiler cannot find the specified type in the source files or in any referenced assemblies, it prepends System.IO. to the type name and verifies the type. If the compiler didn’t find suitable type then it verifies with the next using directive i.e. System.Text. so in this way FileStream is prepended with System.IO and StringBuilder is prepended with System.Text. The compiler automatically expands the code to match correct types during compilation. So using directive really saves a lot of time and improves readability.

Generally any type that is specified in the source code usually starts matching with the core types found in the  Framework Class Library inside MSCorLib.dll

The namespace are usually used for resolving the ambiguity problem faced when two vendors of the third party libraries have same type names, then we should use fully qualified type name composed of namespace and type name.

Creating a namespace is simply a matter of specifying a namespace declaration into your code as follows (in C#)

namespace CompanyName {

public sealed class A {                           //typedef: CompanyName.A

}

namespace X {

public sealed class B { … }                   //typedef Company.X.B

}

}

The comment  on the right of the class definitions above indicates the real name of the type the compiler will emit into the type definition metadata table; this is the real name of the type from the CLR’s point of view.

When the CLR starts running in a windows process, it automatically creates a special type object for the System.Type type defined in MSCorlib.dll. The user-defined type objects are instances of this type and hence their type object pointer members are initialized to refer to the System.Type type object.

Also System.type type object is an object by itself and has a type object pointer member in it, and it’s member refers to itself because the System.Type type object is itself an “instance” of a type object. And System.Object’s GetType method returns the address stored in the specified object’s type object pointer member. In other words the GetType method returns a pointer to an object’s type object, and this is how you can determine the true type of any object in the system.

Generics

Generic Programming in .Net 4.0

Generic Programming is a methodology for the development of reusable software libraries and API’s which are highly efficient and composable. The Generic Programming helps develop multiple libraries which can be combined seamlessly without any modification to any of the interface for e.g. In STL Algorithms are combined easily to work with containers without any modification to container data structures. This is done using iterators with help of Generic Programming.

The Generic language are very fragile, the class, interfaces, objects function definitions are implemented seamlessly with very small footprint. Due to this logic of the generic definition are bit difficult to understand and cannot be expressed easily. Currently the template programming in C++ is all about language tricks. STL embodies generic programming completely.

The main idea of Generic Programming is develop / generate an invariant code base that can be reused potentially for infinite set of types. There are two general models of Generic Programming

1. Universal Type Container Model.
2. Type Parameter Model.

Universal Type Container Model contains one universal object/type. All objects/types are stored in uniform and opaque manner using universal Type. For e.g. .Net uses Object and COM uses IUnknown is analogous to Universal Type.

Type Parameter Model uses late binding of type information with the runtime object. Values may vary from one invocation to the next, these are factored out into parameters. Therefore this model is known as parameterized Types.Model. If developer is using C++/CLI or now it is C++0x you can use either CLR generic mechanism or the template Keyboard.

Here in this article I will be talking only on generic programming. Generic instantiation is done by the CLR at run time. e.g. List. The token that follow the name are type arguments. Also it is important to know that there is no special relationship between derived and base class, between two instances of a generic type bound to independent args. For e.g. you cannot assign one generic instance to the other generic instance without explicitly programming for that. Nor does the string instantiation of the stack have access permission to the non public member of the integer instantiation of the stack.
generic ref class Iter
{
    property T Current
         {
         T get();
         }
};
template ref class Iter
{
     property T current
          {
          T get();
          }
};

The above generic code declarations results in type independent interface design. The class or typename keyword is a identifier that serves as a placeholder within the template organic definition.

template public ref class List { }
template public ref List { }

In case we want to have specialization function for template class. We do this by providing a specialized definition for a member function using an explicit specialization definition. for e.g.

template String^ List::small()

Even though the List is instantiated from generic class Template definition, each object of type List invokes your specialization of the member function small.

An explicit specialization for a class template can be defined only after the general class template has been declared. When defining a member of a fully specialized class template such as List we don’t precede its definition with the special template <> marking. Rather we indicate the specialization by explicitly writing the actual type shown below

String ^ List::small { }

Partial Template Specialization : If a class template has more than one template parameter we can specialize the class Template for one or a set of particular parameterized types i.e. you provide a template that has some of the template arguments being replaced by actual types or values e.g.

template ref class Buff { …… };

The general rule is that when class template partial specialization are declared, the compiler chooses template definition that is the most specialized for the instantiation. When no partial specialization is available, the generic template definition is used.

Overload Function Resolution: The first step in overload function resolution is just to build the set of candidate functions. The candidate function set consists of the functions that have the same name as the called function and for which a declaration is visible at the point of the call. The first visible function is the non-template instance. I add that to the candidate list.

What about the function template?

When a function template is visible, an instantiation of that template is treated as a candidate function if a function can be instantiated using the function call arguments. In my example, the function argument is s2, which is of type String. Template argument deduction binds String to T, and the template instantiation max(String^,String^) is added to the set of candidate functions.

A function template instantiation is entered in the set of candidate functions only if template argument deduction succeeds. However, it is not an error if template argument deduction fails; it just means that no function instantiation is added to the set of candidate functions. What if template argument deduction succeeds but the template is explicitly specialized for the template arguments deduced, as in my case? Then it is the explicit specialization that is entered in the set of candidate functions in the place of the function that would be instantiated from the generic template definition.

There are, therefore, two candidate functions for the call:

  1. The specialized template instantiation
  2. The non-template instance.
// candidate functions
// specialized template …
template<> String^ max( String^ s1, String^ s2 );
// non-template instance
String^ max( String^, String^ );

The next step of function overload resolution selects the set of viable functions from the set of candidate functions. For a candidate function to qualify as a viable function, type conversions must exist to convert each actual argument type to the type of the corresponding formal parameter. In the example, both candidate functions are viable.

The last step of resolving an overloaded function consists of ranking the type conversions applied to the arguments to select the best viable function. For the example, both functions appear equally good. Should this, therefore, be treated as an ambiguous call since both are equally viable? The answer is that the call is not ambiguous. The non-template max is invoked because it’s given precedence over the template instantiation. The reasoning behind this is that an explicitly implemented function is in a sense more real than an instance created from a general blueprint.

Surprisingly, in solving the case of the pernicious string literal, I’ve eliminated any chance of my earlier String specialization from ever being invoked, so I can eliminate it. I only need the general template declaration and the overloaded non-template instance:

// our final overloaded set to support String template
T max( T t1, T t2 ) { /* … */ }
String^ max( String^, String^ );

That may or may not seem complicated, but it sure is powerful—far beyond the scope of what the common language runtime (CLR) generic facility can support in terms of both language integration and flexibility.

Template specialization is a fundamental aspect of C++ template design. It allows for optimal performance, overcoming constraints on individual or families of class types, and for flexible design patterns that have proven invaluable in real-world code. In my next column, I will drill down into C# or C++/CLI support for both template and generic functions.

Digg This