Tuesday, July 16, 2019

Inorder Successor in Binary Search Tree

Below is the code for "Inorder Successor in Binary Search Tree"
Question from GeeksForGeeks: https://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/

Iterative approach:

public class BinarySearchTree
    {
        public Node root;

        public int FindNextSuccessor(int key)
        {
            if (root == null)
                return -1;

            Node current = root;
            int potentialSuccessor = -1;

            while (current != null)
            {
                if (current.key == key)
                {
                    if (current.right == null) //If there is no right then it will be potential sucessor
                        return potentialSuccessor;
                    else
                        return this.GetMinValue(current.right);
                }
                else if (key < current.key) // key will in left sub-tree
                {
                    potentialSuccessor = current.key;
                    current = current.left;
                }
                else // key will be right sub-tree
                {
                    //potentialSuccessor = potentialSuccessor; It will be the parent successor value
                    current = current.right;
                }
            }

            return -1; // Key does't exist
        }

        private int GetMinValue(Node node)
        {
            if (node == null)
                return -1; ;

            Node current = node;

            while (current.left != null)
            {
                current = current.left;
            }

            return current.key;
        }
    }

Recursion approach:

public class BinarySearchTree_Recursion
    {
        public Node root;

        public int FindNextSuccessor(int key)
        {
            if (root == null)
                return -1;

            return this.FindNextSuccessorRec(key, this.root, -1);//Roots potentialSuccessor is -1 if right is null.
        }

        private int FindNextSuccessorRec(int key, Node node, int potentialSuccessor)
        {
            if (node == null)
                return -1;

            if (node.key == key)
            {
                if (node.right == null) //If there is no right then it will be potential sucessor
                    return potentialSuccessor;
                else
                    return this.GetMinValueRec(node.right);
            }
            else if (key < node.key)
            {
                return this.FindNextSuccessorRec(key, node.left, node.key);
            }
            else
            {
                return this.FindNextSuccessorRec(key, node.right, potentialSuccessor);
            }
        }

        private int GetMinValueRec(Node node)
        {
            if (node == null)
                return -1;

            if (node.left == null)
                return node.key;
            else
                return this.GetMinValueRec(node.left);
        }
    }

Driver program:


        static void Main(string[] args)
        {
            BinarySearchTree bst = new BinarySearchTree();

            bst.root = new Node(10);

            bst.root.left = new Node(6);
            bst.root.left.left = new Node(4);
            bst.root.left.left.left = new Node(3);
            bst.root.left.left.right = new Node(5);
            bst.root.left.right = new Node(8);
            bst.root.left.right.left = new Node(7);
            bst.root.left.right.right = new Node(9);

            bst.root.right = new Node(12);
            bst.root.right.left = new Node(11);
            bst.root.right.right = new Node(13);
            bst.root.right.right.right = new Node(14);

            bst.root.right.right.right.right = new Node(18);
            bst.root.right.right.right.right.left = new Node(16);
            bst.root.right.right.right.right.right = new Node(21);
            bst.root.right.right.right.right.left.left = new Node(15);
            bst.root.right.right.right.right.left.right = new Node(17);


            //           10
            //        /     \
            //       6       12
            //     /   \    /  \
            //    4     8  11   13
            //   / \   / \       \
            //  3   5 7   9       14
            //                     \
            //                     18
            //                    /  \
            //                   16   21
            //                  /  \
            //                15    17

            var data10 = bst.FindNextSuccessor(10);
            var data8 = bst.FindNextSuccessor(8);
            var data9 = bst.FindNextSuccessor(9);
            var data4 = bst.FindNextSuccessor(4);
            var data11 = bst.FindNextSuccessor(11);
            var data14 = bst.FindNextSuccessor(14);
            var data15 = bst.FindNextSuccessor(15);
            var data16 = bst.FindNextSuccessor(16);
            var data17 = bst.FindNextSuccessor(17);
            var data18 = bst.FindNextSuccessor(18);
            var data21 = bst.FindNextSuccessor(21);
            var data22 = bst.FindNextSuccessor(22);

            Console.WriteLine("Successor of 10 -->; " + data10);
            Console.WriteLine("Successor of 8  -->; " + data8);
            Console.WriteLine("Successor of 9  -->; " + data9);
            Console.WriteLine("Successor of 4  -->; " + data4);
            Console.WriteLine("Successor of 11 -->; " + data11);
            Console.WriteLine("Successor of 14 -->; " + data14);
            Console.WriteLine("Successor of 15 -->; " + data15);
            Console.WriteLine("Successor of 16 -->; " + data16);
            Console.WriteLine("Successor of 17 -->; " + data17);
            Console.WriteLine("Successor of 18 -->; " + data18);
            Console.WriteLine("Successor of 21 -->; " + data21);
            Console.WriteLine("Successor of 22 -->; " + data22);
        }

public class Node
    {
        public int key;
        public Node left;
        public Node right;

        public Node(int _key)
        {
            key = _key;
            left = right = null;
        }
    }

Monday, November 22, 2010

Asp.net string compare validator for case-insensitivity & textbox trim

We have asp:CompareValidator to validate two elements of type(string, integer, double etc). While comparing two strings, it considers text case-sensitivity. Some times we may need to compare strings without taking care of its case.
I got the same requirement while working in a project, where i need to compare two email addresses.

I have written StringCompareValidator class which extends BaseValidator class, it serves above the need. It does client and server side validations. Use its properties "IgnoreCase", "TrimText", "Operator" and "EnableClientScript" to change the behavior of the validator.

Download its sample website from here. StringCompareValidator.cs class file from here.

Usage:

Place StringCompareValidator class file in App_Code folder and register this control in a page as.
<%@ Register Assembly="App_Code" Namespace="RampValidators" TagPrefix="RampValidators" %>
Using the above validator for textbox controls tbEmail1, tbEmail2 as
<RampValidators:StringCompareValidator ID="StringCompareValidatorReEmail" ControlToValidate="tbEmail2" ControlToCompare="tbEmail1" Text="Email addresses should match." Display="Dynamic" TrimText="false" IgnoreCase="true" Operator="Equal" runat="server" CssClass="required"></RampValidators:StringCompareValidator>

Tuesday, December 29, 2009

How To: Get the width and height of the SWF file using C#

Use the below SwfParser class to get the width and height of the SWF file.
This class requires ICSharpCode.SharpZipLib.dll. You can download it from here or ICSharpCode.
  • Use GetDimensions(String filePath) method whenever you want the dimensions of the swf file that resides on your server. Give the complete file path as a parameter.
  • Use GetDimensions(Stream stream) method whenever you want to find the swf file dimensions from the input stream (Ex: Asp.net file upload control's PostedFile.InputStream object.), it can be of any inputStream. Here you no need to save the file on to the server.
These two methods returns Rectangle object, from this object you can get width and height.

Usage:
//Use when the file resides on your server.
try
{
    SwfParser swfParser = new SwfParser();
    Rectangle rectangle = swfParser.GetDimensions(filePath); 
    int width=rectangle.Width;
    int height=rectangle.Height;
       
}
catch (Exception ex)
{
    return "There is a problem with the swf file.";
}

//Use when you want to use file upload control's input stream.(it may be any input stream)
try
{
    SwfParser swfParser = new SwfParser();
    Rectangle rectangle = swfParser.GetDimensions(uploadedfile.PostedFile.InputStream); 
    int width=rectangle.Width;
    int height=rectangle.Height;         
}
catch (Exception ex)
{
    return "There is a problem with the swf file.";
}

Here is the SwfParser class:
using System;
using System.Text;
using System.IO;
using System.Drawing;
using ICSharpCode.SharpZipLib.Zip.Compression.Streams;

public class SwfParser
{
    public Rectangle GetDimensions(String filePath)
    {
        using (FileStream stream = File.OpenRead(filePath))
        {
            return GetDimensions(stream);
        }
    }

    public Rectangle GetDimensions(Stream stream)
    {        
        Stream inputStream = null;
        byte[] signature = new byte[8];
        byte[] rect = new byte[8];
        stream.Read(signature, 0, 8);
        if ("CWS" == System.Text.Encoding.ASCII.GetString(signature, 0, 3))
        {
            inputStream = new InflaterInputStream(stream);
        }
        else
        {
            inputStream = stream;
        }

        inputStream.Read(rect, 0, 8);
        int nbits = rect[0] >> 3;
        rect[0] = (byte)(rect[0] & 0x07);
        String bits = ByteArrayToBitString(rect);
        bits = bits.Remove(0, 5);
        int[] dims = new int[4];
        for (int i = 0; i < 4; i++)
        {
            char[] dest = new char[nbits];
            bits.CopyTo(0, dest, 0, bits.Length>nbits ? nbits : bits.Length);
            bits = bits.Remove(0, bits.Length > nbits ? nbits : bits.Length);
            dims[i] = BitStringToInteger(new String(dest)) / 20;
        }

        return new Rectangle(0, 0, dims[1] - dims[0], dims[3] - dims[2]);
    }

    private int BitStringToInteger(String bits)
    {
        int converted = 0;
        for (int i = 0; i < bits.Length; i++)
        {
            converted = (converted << 1) + (bits[i] == '1' ? 1 : 0);
        }
        return converted;
    }

    private String ByteArrayToBitString(byte[] byteArray)
    {
        byte[] newByteArray = new byte[byteArray.Length];
        Array.Copy(byteArray, newByteArray, byteArray.Length);
        String converted = "";
        for (int i = 0; i < newByteArray.Length; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                converted += (newByteArray[i] & 0x80) > 0 ? "1" : "0";
                newByteArray[i] <<= 1;
            }
        }
        return converted;
    }
}

Configuring WCF services to work with both HTTP and HTTPS

1) Write two endpoints for the service, one is for http and another for https.
<services>
    <service behaviorConfiguration="MyServiceBehavior" name="JK.MyService">
      
      <endpoint address="" behaviorConfiguration="WebBehavior" binding="webHttpBinding" bindingConfiguration="webBinding" contract="JK.IMyService">
        <identity>
          <dns value="localhost" />
        </identity>
      </endpoint>

      <endpoint address="" behaviorConfiguration="WebBehavior" binding="webHttpBinding" bindingConfiguration="webBindingHTTPS" contract="JK.IMyService">
        <identity>
          <dns value="localhost" />
        </identity>
      </endpoint>     
      
    </service>
  </services>
2) Enable both httpGetEnabled="True" httpsGetEnabled="true" in serviceBehaviors.
<behaviors>
    
    <serviceBehaviors>      
      <behavior name="MyServiceBehavior">
        <serviceMetadata httpGetEnabled="True" httpsGetEnabled="true"/>
        <serviceDebug includeExceptionDetailInFaults="true" />
      </behavior>      
    </serviceBehaviors>
    
    <endpointBehaviors>
      <behavior name="WebBehavior">
        <webHttp/>
      </behavior>
    </endpointBehaviors>
    
  </behaviors>
3) Write two bindings configurations for http and https. For http give security mode="None" and for https give mode="Transport".
<bindings>
    <webHttpBinding>

      <binding name="webBinding">
        <security mode="None">
          <transport clientCredentialType="None" />
        </security>
      </binding>

      <binding name="webBindingHTTPS">
        <security mode="Transport">
          <transport clientCredentialType="None" />
        </security>
      </binding>

    </webHttpBinding>
  </bindings>
Below are the complete configuration settings in web.config:
<system.serviceModel>
  
  <services>
    <service behaviorConfiguration="MyServiceBehavior" name="JK.MyService">
      
      <endpoint address="" behaviorConfiguration="WebBehavior" binding="webHttpBinding" bindingConfiguration="webBinding" contract="JK.IMyService">
        <identity>
          <dns value="localhost" />
        </identity>
      </endpoint>

      <endpoint address="" behaviorConfiguration="WebBehavior" binding="webHttpBinding" bindingConfiguration="webBindingHTTPS" contract="JK.IMyService">
        <identity>
          <dns value="localhost" />
        </identity>
      </endpoint>

      <endpoint address="mex" binding="mexHttpBinding" contract="IMetadataExchange" />
      
    </service>
  </services>
    
  <behaviors>
    
    <serviceBehaviors>      
      <behavior name="MyServiceBehavior">
        <serviceMetadata httpGetEnabled="True" httpsGetEnabled="true"/>
        <serviceDebug includeExceptionDetailInFaults="true" />
      </behavior>      
    </serviceBehaviors>
    
    <endpointBehaviors>
      <behavior name="WebBehavior">
        <webHttp/>
      </behavior>
    </endpointBehaviors>
    
  </behaviors>
  
  <bindings>
    <webHttpBinding>

      <binding name="webBinding">
        <security mode="None">
          <transport clientCredentialType="None" />
        </security>
      </binding>

      <binding name="webBindingHTTPS">
        <security mode="Transport">
          <transport clientCredentialType="None" />
        </security>
      </binding>

    </webHttpBinding>
  </bindings>
  
</system.serviceModel>

Sunday, December 20, 2009

Getting the password of the IIS users IUSR_MachineName and IWAM_MachineName


Copy the following code into a .vbs file and run it on the machine you wish to get the account details from.


Dim IIsObject
Set IIsObject = GetObject ("IIS://localhost/w3svc")
WScript.Echo "UserName = " & IIsObject.Get("AnonymousUserName") & vbCrlf & _
"UserPass = " & IIsObject.Get("AnonymousUserPass") & vbCrlf & vbCrlf &_
"WAMUser = " & IIsObject.Get("WAMUserName") & vbCrlf & _
"WAMPass = " & IIsObject.Get("WAMUserPass")
Set IIsObject = Nothing