Feeds:
Posts
Comments

Some important properties of those known “primitive” types …. ( c# )

  Value Type
typeof(int)
Nullable Type
typeof(int?)
String
typeof(string)
IsClass     True
IsByRef      
IsGenericType   True  
IsPrimitive True    
IsValueType True True  
BaseType ValueType ValueType object

Generally many people sort “string” to the “primitive type” group and think it a “unusual” class…
While here we can see that from a strict , exact .NET definition vision “string” is by no means primitive , though it possesses most popular usage and is granted a “keyword” privilege like int , double in .NET world.

Advertisements

Heap Sort

Very very ridiculously ,  I some days ago threw an ariticle about an “enhenced version of heap sort”, which after a scrupulous review betrayed a silly implementation of sorting that can’t be farther from the truth of heap sort, due to damn unawareness of my mistake until scrutinizing some source code interspersed throughout  the web.   Any way, I could’nt hold my own overreached improvement , but rewrite it in the classical manner.  As though failing in an innovaton ,  I still insist on pubishing my rectified code.   

It is an introspection.

 Against my original thougt of stupor ,  heap sort is not so awlful that each time the part to be adjusted shall be adjusted from node of last node’s parent to the top node sequentially!  Since we should use such method to initial the whole target array as a strict heap,  after this only adjustment of root note is required ,  if neccessary ( that’s why in classical algorithm  use a max heap as the ADT to support an ascending order of array , which amazed me at first !  ) .      

/*
using strategy of “filtering through the direction from up to down” to adjust a heap starting at heapStart position
*/

void filterDown(  int *heap ,   int start  ,  int heapEnd )

 int  leftChild , rightChild , leftChildVal , rightChildVal , current , startVal , targetChild ;
  // value of the “start” position , which should be compared down its branch nodes
    startVal = *( heap + start );
    current = start;

    /* firstly test current’s children state.
    if current node’s left child ‘s index exceeds the heap’s upper bound,
    which means that it has no child ,
    then there is no need to filter down from current node   */
    for(  leftChild = current * 2 + 1;
       leftChild <= heapEnd;
     *( heap + current ) = * ( heap + targetChild ),
     current = targetChild,
     leftChild = current * 2 + 1  )
    {
  
     // judge who is the winner to compare with the target start value
     // if left child doesn’t meat the end
     if( leftChild < heapEnd )  
     {
       
        rightChild = leftChild + 1;
     leftChildVal =  * ( heap + leftChild );
     rightChildVal = * ( heap + rightChild );
     targetChild = leftChildVal >= rightChildVal ? leftChild : rightChild;  
  
     }
     else
      targetChild = leftChild;
   if( startVal >= * ( heap + targetChild )  )
    break;

    }

    /*  when startValue meets its “just” position, note that all nodes alongside this   critical  comparation path have  leveled up by one step, so current blank position is expected to fill “startValue”   */
    *( heap + current ) = startVal;
}

void Swap( int *a , int *b )
{
 int temp = *a;
 *a = *b;
 *b = temp;
}

// main funtion
void heap_sort( int *arr , int length )
{
 // current array length for each iteration
 int i ,
  curHeapEnd = length-1 ,
  from = ( length – 1 ) / 2;
 // build the whole array as a heap
 for ( i=from;i>=0;i– )
  filterDown( arr , i ,  curHeapEnd );
    for( i=curHeapEnd;i>0;i– )
 {   
  Swap( arr , arr + curHeapEnd );
  filterDown( arr, 0 , –curHeapEnd );
 }
 
}

In asp.net 2.0’s GridView  web control ,  you can convert  each column’s header part into customable one.  However ,  I find the little technic getting rare  discussion , for  most developers put attention to customization  of normal rows :  changing a BoundField into TemplateField ,  craming  item cell with dropdown list , button , etc by typing code in the blank of ItemTemplate .   The significance of controlling header template and style freely lies in that we can enhence the user experience when they are dealing with matters of sorting.  In most cases it is really tangent to the core business ,   however,  what if your client is a diehard of such case:  when cliking field header ,  he needs not only the perfect sorted result , but certain  obvious symbol to provide details  about current round of sorting: which cloumn is sorted just now and whether it sorts ascendingly or in  the  inverting  direction.   A good approach is adding a small arrow, which denotes current sort direction ,  before the header text of the field to be sorted.    However ,   neither default “HeaderText” property  nor “HeaderImageUrl”  leads to the goal.    We must get the ultimate control of header to make its appearance versatile!

Let’s follow these steps to reach the end:

 1.   Convert a BoundField , or any other kind of dotnet-built-in field into a TemplateField.     Only by using  this step  can  “HeaderTemplate” be accessed thus enabling us to customize the header part.   For example , if we have:

  <asp:BoundField DataField=”Name” HeaderText=”Name” SortExpression=”Name” />     

We convert it to format as shown below :

   <asp:TemplateField>
       <HeaderTemplate>


       </HeaderTemplate>
          <ItemTemplate>
                 <%# Eval(“Name”) %>
               </ItemTemplate>
       </asp:TemplateField>

  Let’s leave HeaderTemplate blank here for a moment.

 2.  Now we add a  LinkButton to simulate the default sorting field’s hyperlink with postback-javascript.   Add the button  strictly following the rules:

  1.   Set its   “CommandName”   as “Sort” 
  2.   Set its   “CommandArgument”   as corresponding value of “SortExpression”
  3.   Set its   “Text”  as  corresponding value of  “HeaderText”

By applying this 3 “golden rules” to the link button we will get a head appearance completely resambling  the auto-generated header for sorting.   Actually ,  the step 1 and 2 are two  necessary steps ,   step 3  is not so important  that you can replace with any equivalvent text.    Still adhering the sample , after “large step 2” we have:

 <asp:TemplateField>
       <HeaderTemplate>
       <asp:LinkButton runat=”server” Text=”Name” CommandName=”Sort” CommandArgument=”Name” ></asp:LinkButton> 
       </HeaderTemplate>
          <ItemTemplate>
                 <%# Eval(“Name”) %>
               </ItemTemplate>
         </asp:TemplateField>

 If we just stop here, the total workload  is meaningless :  amassing work to realize a no-need-to-develop  function   is unacceptable  to  anyone .   So we come to the start point of ornating a novelty : prefix an image control  to link button ,  acting as the holder of vertical  arrow symbol.   Then the page  syntax  becomes:

 <asp:TemplateField>
       <HeaderTemplate>
        <asp:Image id=”Name” Visible=”false”  runat=”server”  /><asp:LinkButton runat=”server” Text=”Name(CustomHeader)” CommandName=”Sort” CommandArgument=”Name” ></asp:LinkButton> 
       </HeaderTemplate>
          <ItemTemplate>
                 <%# Eval(“Name”) %>
               </ItemTemplate>
           </asp:TemplateField>

Note that such image control should be set invisible by default .  Even for each sorting-enabled field ,  there is no need to show any prompt symbol  if the user do not trigger its header link button.  The control’s visibility and  image url  will be manipulated programmably.  

What should do in  .aspx  context has been introduced.  Now we turn to backend code for seaming a  perfect function.   First we should register a method to gridview’s “RowDataBound” event,  then inject code.  Supposing the gridview’s ID is “gridView” ,   the code segment is as follows: 

    protected void gridView_RowDataBound(object sender, GridViewRowEventArgs e)
    {
         /*
        When the gridview is initialized , no sorting behavior happens,
        hence the SortExpression property is empty
        and the manipulation of arrow  should be skipped
        */

        if (e.Row.RowType == DataControlRowType.Header && gridView.SortExpression!=string.Empty )
        {
            /*
            Assign each arrow image control for its corresponding sorting field with
            the value of “sorting field name” , making it convinient to be found!
            */
            Image arrow = (Image) e.Row.FindControl( gridView.SortExpression );
            arrow.Visible = true;

            if (gridView.SortDirection == SortDirection.Ascending)
                arrow.ImageUrl = “arrowUp.gif”;
            else if (gridView.SortDirection == SortDirection.Descending)
                arrow.ImageUrl = “arrowDown.gif”;
        }

    }

Easy to understand ,  especially with my inline comment ……    Since bored with typing  so many words to exposit  such a simple skill  I  give up explaining  anymore about the backend code.    You can see  a  live sample here:

 sorting header with arrow

When I am reviewing GRE CS SUB material I meet counting sort. Counting sort is “a sort of sort” other than the common comparison sorts. It runs in linear time and uses the combination of indexed-based arrangement strategy and conception of “backet sorting” to determine the sorted order, thus not like comparison-based idea. Counting sort is stable.

However , the original version of counting sort has some unavoidable defects, due to its rigorously “number-index mapping” policy, that is, a number N must correspond with its position element c[N], which seems of convinience in some cases whist confronts limitation. For example, when the target array has negative integers , or even decimals , such sorting has no idea! Because the array index is neither negative nor nonintegral value. As though decimal is indeed out of handling capacity of this sorting , negative integers can be perfectly tackled , if we distend the original version a little. After a bust of thought I reap an enhenced code segment.

Code is rough and complied in VS2005 environment. I am neither a lust nor an expert about program, so have to use such heavy tool to build the light code. Must say, My feeling is Damn.

int *counting_sort( int *a , int number )
{
  int max ,min, cLen , i , j , *b , *c;

if( !a )
  return NULL;

/*
  now the conception is expanded. we use a narrower range to build such a “statistical” array c
  not only use max to limit its upper bound, but also min to limit its lower bound.
  for example , if we have : 6 4 3 5
  then we do not need : 0 1 2 3 4 5 6
  we just construct such a “c” : 0 1 2 3 ( which can effectively cram “3” to “6”, totally 4 number )
  thereby , such function can be expanded to sort arrays with negetive number.
  for example , if we have : 1 3 -2
  we can build c as : 0 1 2 3 4 5 , which can hold -2 -1 0 1 2 3 justly ( from -2 to 3 )

so the key of enhencement is realign the position for each a[i]’s position in c!
  */

max = Max( a , number);
 min = Min( a, number );
 cLen = max – min + 1;
 b = (int*)calloc( number , sizeof(int) );
 c = (int*)calloc( cLen , sizeof(int) );

if( !c || !b )
  return NULL;

/*
  offsets each a[i]’s position
  note that here a[i]’s information will not be stored simply in c[a[i]],
  actually , you should take care of the “min” value as the offset!
 */

 for( i=0;i<number;i++ ) 

c[a[i]-min] += 1;

// set j as the initial position where the element is not 0
  for( j=0;!c[j];j++);
  for( i=j+1; i<cLen;i++ )

   if( c[i] )
  {
  c[i]+=c[j];
  j=i;
  }

/*
  supposing a[i]=k, actually k’s information is not in c[k],but in c[k-min],
 so c[k-min]’s value should be used to adopt k( a[i] ) ‘s real position in b
 */
 for( i=number-1 ; i>=0;i– )
 {
  b[c[a[i]-min]-1] = a[i];
  c[a[i]-min]–;
 }

free(c);

return b;

}

//find the max value in array a
int Max( int *a , int number )
{
int ret = *a, i;
for( i=0; i<number; i++ ,a++ )
if ( *a > ret )
ret = *a;

return ret;
}
//find the min value in array a
int Min( int *a , int number )
{
int ret = *a, i;

for( i=0; i<number; i++ ,a++ )
if ( *a < ret )
ret = *a;

return ret;
}

Then I discuss how to test the code. You pass the address of target array and the length of it as two parameters to function “counting_sort”. Note that such sorting must use an assitant array to restore all the reranged elements. So Result array will be a new one and its pointer is returned.

Traffic Accident

Two days before is Mid-Autumn Day as shall be a pleasant feast to enjoy familial reunion and harmony. However in that day I almost touched the hell and luckily slided over the hell gate. Such thrill was bestowed by the estimable taxi driver. Did he really want to elevate me to the paradise? Maybe, basing on that I witnessed white-smoke-clouded atomosphere that is so like dreamt heaven.

When I lowered my head looking to my mooncake box , a sudden strike hit my forehead, which brought a transient of thorough blank to my brain. After a slice of unconsciousness I levered up my head , seeing the windscreen cracked, a massive of white smoke discharging continuously from the front cover of the car , AND the backside of the front microbus as was forcefully kissed by what I were then in! Might be paradise arrived, since we were immersed in the faery fog ? Hehe, at that time I thought “Even now I am not yet reach at the paradise , I will get there after an explosion, of which the smoke leak is just prelude!” Wioutout cerebration I opened the side door and ramped away the car!

Actually, nothing had happened. Since I am a person of forgiveness and I didn’t wound seriously, and I were in exigency of attending the family party for M-A day, I didn’t ask for compensation of accident. Maybe I were silly maybe not. Anyway , the driver couldn’t escape from the aftermath of his misconduct: he should repair his own car and recompense for that innocent, poor microbus.

Then, expectedly, the police, the owner of microbus, and our hero , who conduct a car running into a static object in a cannot-be-slower speed with his abnormal driving skill, started “a standing meeting” . Such meetings happen everyday and everywhere in a traffic-congestion-marked Shanghai. I really want to be enmeshed BY NO MEANS. Ok everyone, had a good meeting , yet absolutely not an absorbing one  to me.

On the table , I told the story , showing the slight scar on my left eye’s corner reaped from the experience.

“Why not demand compensation from that man?? You are so silly!” My sister shook her head, issuing a belated advise.

“Since no serious result happened and I were anxious to catch here , I gave up to get entangled with the light mishap, seeking a new taxi. ” I answered.

post-73704-1128178563.gif

It has not rained for a long time.  Today a timely invasion of typhoon brings up a darling shower, which not only  cleans up the air , but also assuage my restless  soul .  Gale  foments the cloudburst meanwhile  downpour fosters  storm.  Sky and land now seem melted as a whole, emerging an unbelievable  spectacle .

 The consequential effect is by all means exciting news for the students clan,  for they are vouchsafed several hollidays ,  whereas even the omnipotent tempest  condescends to severe work discipline,  indicating an immense stradegy  for office workers,  for they must  brave the inclemency of naturual alliance  to please their bosses.

When I am to post the piece,  world welcomes a temperary tranquility.  Yet I know, it is not an endless calm, but the one preceding the storm.

Sense Life

A week ago I was informed that my granddad had gotten critical ill,  such piece of awful news drived me to return my hometown  immediately.  Fortunately ,  his health was looking a little better when I saw him.  Yet an elder of weakness with a sequential of hard breathes by no means predicts a hopeful prospect as can truely assure us relatives.   A random  tour of wards with  witnesses  to those recumbent elders brought me the notion that  death without more ado might be better than eking  out a meagre life haunted with endless bodily uncomfort and pain.  When one luckily appears at the world ,   the foreordination of leaving the world  is unavoidable to the party. 

 On earth is it a human being’s woe or not?