Tuesday, March 24, 2015

Basic Data Stuctures : AVL Tress

Now to AVL trees, another neat data structure to store lists if information.. This my friends is a courtesy of communism (gasp!) yes, AVL trees were invented by Georgy Adelson-Velsky and E. M. Landis for the history lesson and graphics you can check it the information at WikipediA - AVL Tree.

Microsoft .Net has an AVL tree class SortetSet<T> but it is always nice to understand the origins of the logic behind.

What is an AVL tree


And AVL tree is much like a Balanced Binary Search Tree. A Binary Search Tree (BST) has the following properties:


  • Each node has a value;
  • Each node has a left node which stores only values of lesser value than the node's value.
  • Each node has a right node which stores only values of greater value than the node's value


An AVL tree is a self-balancing BST with the following properties:


  • The heights of the two children sub-trees of any node differ at most one.
  • Search, Insert and Delete methods all take O(log n) time in both the average and worse cases
  • Insert and Delete may require the tree to be re-balanced by one or more rotations.

Without further ado: the code


You will find comments in the code detailing the steps needed to balance and rotate nodes.

//define the binary Node class BinaryNode    {

        public int data { get; set; }
        //This node will store nodes with lesser value than the data field
        public BinaryNode left;
       //this node will store nodes with greater values than the data field
        public BinaryNode right;
       
       //Initialize the Node
        public BinaryNode(int data)
        {
            this.data = data;
            left = null;
            right = null;
            visited = false;
        }       

    }

   //this class manages the AVL tree, as you can see is based on as BST    class BinaryTree

    {
        public BinaryNode head; //the tree
       //to keep track of how many nodes we have in the tree
        public int counter;  

        public bool isBalanced()
        {
            int left = height(head.left);
            int right = height(head.right);

            //in a balanced tree the difference in height between
           // the left sub-tree height and the right sub-tree it is at most one
            return Math.Abs(left - right) <= 1 ? true : false;
        }

        public int height(BinaryNode n)
        {
            if (n == null)
            {
               //if the value is null, return -1 and the node will be subtracted from the total
                return -1;
            }           

            int theleft = height(n.left)+1;
            int theright = height(n.right)+1;

            //the height of a node is the MAX value of the sub-trees
            return Math.Max(theleft , theright  );

        }

        //Class Constructor
        public BinaryTree(BinaryNode n)
        {
            head = n;
        }

       
        public BinaryNode Delete( BinaryNode root, BinaryNode n)
        {
           

            if (n == null | root == null)
            {
                return null; 
            }

            if (n.data < root.data)
            {
                root.left = Delete(root.left, n);
            }
            if (n.data > root.data)
            {
                root.right = Delete(root.right, n);
            }

            // when deleting a node, then you need to shift Nodes around       
  
            if (root.data == n.data)f
            {
                if (root.left == null && root.right == null)
                {

                    root = null;
                    return root;
               
                }
                else 
                {
                    // Rotate nodes
                    if (root.left  == null)    
                {

                        BinaryNode temp = root;
                        root = root.right;
                        temp = null;

                        return root;
                    }
                    else if (root.right == null)
                    {
                        BinaryNode temp = root;
                        root = root.left;
                        temp = null;
                    }
                    else
                    {
                        //rotate to right?... but we may need to go check the depth..
                        BinaryNode min = GetMin(root.right);
                        root.data = min.data;
                        root.right = Delete(root.right,min);                       
                    }

                }
            }    

            return root;
        }

       //This function will return the lowest node in a sub-tree
        private BinaryNode GetMin(BinaryNode root)
        {
            if (root.left == null)
            {
                return root;
            }

            return GetMin(root.left);
        }

        private int HeightDifference(BinaryNode Node)
        {
            return height(Node.left) - height(Node.right);
         }

       //Balancing a node
        private BinaryNode Balance(BinaryNode Node)
        {

           // AVL Steps:
           // 1.- Find the height difference between sub-trees
           // 2.- If  -1 <= difference <= 1 then you are good, otherwise, you need to rotate
           // 3.- Nodes at the top have higher values than the bottom, so the root should store the highest 
           //      height, while leaf nodes at bottom would store a height of 1
           

            int heightDifference= HeightDifference(Node);
       
            //if the balance factor is > 1 it means the left is deeper than the right
           if (heightDifference> 1)
           {
               //if the node to the left is deeper, then rotate to the left twice
               if (HeightDifference(Node.left) > 0 )
               {
                   //rotate left left
                   Node = RotateLL(Node); 
               }
               else  //there is nothing under it
               {
                   //rotate left - right
                   Node = RotateLR(Node); 
               }
           }
           else if (heightDifference< -1)  // a negative value means the right is deeper than the left
           {
               //now let's check the depth of the right node
               if (HeightDifference(Node.right) > 0) // the right is deeper lets rotate right then left
               {
                   //rotate right - left
                   Node = RotateRL(Node); 
               }
               else //there is nothing under
               {
                    //rotate right - right
                   Node = RotateRR(Node);
               }

           }
           
            return Node;
        }

      //Rotating Nodes, there are 4 cases: right-right, right-left, left-left and left-right
      // right-right: all nodes are to the right of the parent, the pivot becomes the new parent and
      // the original parent becomes the child of the pivot
      // left-left: all nodes are to the left of the parent
      // right-left: pivot is the right child of the parent
      // left-right: pivot is the left child of the parent

        private BinaryNode RotateRR(BinaryNode Node)
        {
            BinaryNode Pivot = Node.right;
            Node.right = Pivot.left;
            Pivot.left = Node;
            return Pivot;
        }

        private BinaryNode RotateLL(BinaryNode Node)
        {
            BinaryNode Pivot = Node.left;

            Node.left = (Pivot == null ? null : Pivot.right);
            Pivot.right = Node;
            return Pivot;
        }

        private BinaryNode RotateLR(BinaryNode Node)
        {
            BinaryNode Pivot = Node.left;
            Node.left = RotateRR(Pivot);

            return RotateLL(Node);
        }     
  
        private BinaryNode RotateRL(BinaryNode Node)
        {
            BinaryNode Pivot = Node.right;
            Node.right = RotateLL(Pivot);
            return RotateRR(Node);
        }

       // Insert with balance
        public void Insert(BinaryNode root, BinaryNode n)
        {
            if (root == null)
            {
                root = n;
                counter++;
            }
            else
            {                                 
                if (root.data > n.data)
                {
                    if (root.left == null)
                    {
                        root.left = n;
                        counter++;
                    }
                    else
                    {
                        Insert(root.left, n);
                       //After inserting, then balance the tree
                        Balance(root.left);
                    }

                }
                else
                {
                    if (root.right == null)
                    {
                        root.right = n;
                        counter++;
                    }
                    else
                    {
                        Insert(root.right, n);
                       //After inserting, then balance the tree
                        Balance(root.right);
                    }
                }
            }
        }

       // This method searches for the value in the tree
        public BinaryNode Find(BinaryNode root, BinaryNode n)
        {
            BinaryNode found;

            if (n == null | root == null)
            {
                return null;
            }

            if (root.data == n.data)
            {
                return root;
            }

            if (root.data > n.data)
            {
                found = Find(root.left, n);
            }
            else
            {
                found = Find(root.right, n);
            }

            return found;

        }

       //use this method to display the data in order
        public void InOrderTransversal()
        {
            BinaryNode temp = head;
            DisplayInOrder(temp);
        }
        
        //use this method to display the data in order
        public void DisplayInOrder(BinaryNode n)
        {
            if (n == null)
            {
                return;
            }

            DisplayInOrder(n.left);
            Console.WriteLine("{0}", n.data);
            DisplayInOrder(n.right);

        }
    }


Thursday, March 12, 2015

Basic Data Structures: Linked Lists

In a return to basics - and plenty of nothing to do - I implemented my own little linked list. Given the state of modern computing I have never really needed to implement a linked list, .Net framework has excellent libraries that manage lists and arrays, however, I guess it is always useful to understand the algorithms and foundations of computer science/

Lets start with what is a linked list:


A linked list is a data structure consisting nodes which together represent a sequence. Each node contains at least data and a reference to the next node. Hours and hours have been spent writing about linked lists, so no point on rehashing it again. For more information, you can use the google machine or check Wikepedia's page on the subject. http://en.wikipedia.org/wiki/Linked_list

Now the code

Declaring the node

Nothing fancy, straight forward thing

 public class Node
    {
        public object data;
        //recursive portion of this.
        public Node next;

        public Node(object data)
        {
            this.data = data;
        }
    }

Linked List


  public class myLinkedList
    {
        public Node head;
        Node current;
        
        public void Add(Node n)
        {
            //self explanatory, but just in case
            // if the top has not been initialized, then do it
            if (head == null)
            {
                head = n;
                current = n;
            }
            else
            {
                //if there something there, then just add the new 
                // node to the end, notice you first set the next property, 
                // then set current
                current.next = n;
                current = current.next;
            }

        }

        public void InsertAtTop(Node n)
        {
            current = head;
            //check to make sure there is something 
            // there
            if (n == null) { return; }

            n.next = current;
            head = n;

        }

        public void Insert(Node n)
        {

            //check to make sure there is something 
            // there
            if (n == null) { return; }

            //this operation would check if where should I add a value on the list.
            current = head;
            //check the first element..
            if ((int)current.data >= (int)n.data)
            {
                n.next = current;
                head = n;
                return;
            }

            //if the first element was ok, then move to the rest
            current = current.next;

            while (current != null)
            {
                if ((int)current.data <= (int)n.data)
                {
                    n.next = current.next;
                    current.next = n;
                    return;
                }
                current = current.next;
            }
            //now if I got here then this should be the last item on the list
            current.next = n;

        }

        public string ReverseAndParse()
        {
            string temp = "";

            current = head;
            while (current.next != null)
            {
                temp = string.Concat(current.data.ToString(), temp);
                current = current.next;
            }

            //add the last item...
            temp = string.Concat(current.data.ToString(), temp);
            return temp;
        }

        public string Parse()
        {
            string temp = "";

            current = head;
            while (current.next != null)
            {
                temp = string.Concat(temp, current.data.ToString());
                current = current.next;
            }

            //add the last item...
            temp = string.Concat(temp, current.data.ToString());
            return temp;
        }

        public void DisplayItems()
        {
            Node n = head;

            while (n.next != null)
            {
                Console.WriteLine("Node : {0}", n.data);
                n = n.next;
            }
            //display the lastone
            Console.WriteLine("Node : {0}", n.data);
        }

        public void RemoveDuplicates()
        {
            current = head;
            while (current.next != null)
            {
                Node n = current;

                while (n.next != null)
                {
                    if (n.next.data.Equals(current.data))
                    {
                        n.next = n.next.next;
                    }
                    else
                    {
                        n = n.next;
                    }
                }
                current = current.next;
            }

        }

        public Node Split(object x, Node node)
        {
            Node ihead = node;
            Node tail = node;



            while (node.next != null)
            {
                Node next = node.next;
                if ((int)node.data < (int)x)
                {
                    node.next = ihead;
                    ihead = node;
                }
                else
                {
                    tail.next = node;
                    tail = node;
                }

                node = next;
            }

            //we need the last record
            if ((int)node.data < (int)x)
            {
                node.next = ihead;
                ihead = node;
            }
            else
            {
                tail.next = node;
                tail = node;
            }


            tail.next = null;
            // bottom.next = top;

            this.head = ihead;
            return ihead;

        }

        public Node addNodes(Node first, Node second, int CarryOver)
        {
            Node n = new Node(CarryOver);
            int value = (int)(first == null ? 0 : (int)first.data) + (second == null ? 0 : (int)second.data) + CarryOver;

            n.data = (value >= 10 ? (value - 10) : value);

            if (first != null || second != null)
            {
                Node New = (addNodes((first.next == null ? null : first.next), (second.next == null ? null : second.next), (value / 10)));
                if (New != null)
                {
                    Add(New);
                }
            }

            return n;

        }

        public Node BreakAndFix()
        {
            current = head;

            // Node breaker = new Node(current.next.next.data);
            Node breaker = current.next.next;


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

            //break it here

            current.next = head.next.next;

            Node slow = head;
            Node fast = head;

            while (fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
                if (slow.Equals(fast))
                {
                    break;
                }
            }

            if (fast == null || fast.next == null)
            {
                return null;
            }

            slow = head;

            while (slow != fast)
            {
                slow = slow.next;
                fast = fast.next;
            }

            return fast;
        }
    }

Thursday, September 04, 2014

Database Normalization 

This is a brief quick description of database normalization.

Database normalization is the process of organizing information in a relational database into tables to minimize redundancy.

Normalizing a database allows scalability and it is easier to maintain, query and work with.

There are 5 steps to normalize a database, my personal experience is that unless it is absolutely necessary, you are in best shape when you get to step four. Going to step 5 may decrease performance in your database.


There are 5 database normalization steps:

First Normalization Step
Eliminate duplicate columns on tables
Create separate tables for each groups
Identify primary keys for each row

Second Normalization Step
Remove subsets of data that apply to multiple rows of a table
Create  relationships between these new tables using foreign keys

Third Normalization Step
Remove columns that are not dependent on the primary key

Fourth Normalization Step
Every row must have a combination of attributes that can be uniquely identified without any extraneous data - primary key

Fifth Normalization Step
A relation is on Fourth Normalization when there are no rows with any duplicated data

Primary key: is a unique identifier for each record in a table. A primary key can comprise multiple fields, one informational field like email address or social security number,  or it can be generated by the database.

Foreign key: is a field or set of fields in one table that uniquely identifies a row of another number table: car color  or car color and year.

Relationships: a relationship exits between two tables, one has a foreign key referenced to another table.There are 3 relationship types:

  • One to one: one to one relationships can only have one record on each side of the relationship: a car can only have one outside color
  • One to many: one table can have multiple relations to another table: a car can have 2 or more interior colors
  • Many  to  Many: tables can have multiple records related to multiple records on another table: a person can work at multiple companies, you need a third table to relate these kind of relationships


Wednesday, March 19, 2014

Registering .Net Dlls' for use in VB6 32 applications

You have that legacy application that is not willing to go away and you need to use functionality from code you created in .Net.

You need to register the dll for VB6 to be able to find it.

Best thing to do is to create a batch file with the following code:

1) Make the call from you application folder, so you need to move your cursor to that folder
2) Unregister the dll - this is really important as windows registry can get really messy and totally confused if you have multiple versions of the same dll
3) Register the new dll. NOTE: Use the /codebase switch otherwise it just won't happen

Here is the batch file code:

cd C:\Program Files\YourApplication\
C:\windows\microsoft.net\framework\v2.0.50727\Regasm.exe /u YourNewcode.dll
C:\windows\microsoft.net\framework\v2.0.50727\Regasm.exe ReportLogic.dll /codebase

If your application is used by multiple users, you can add code to run the batch file when users load your application.

.Net Fundamentals - Generic Collections - ArraList - List


The .Net Framework collection provides data structures to store and manipulate collections of items as part of the System.Collections namespace.

Array lists are used to store a bunch of items together, you can store items of different data types or items of the same type:

To create a list of items of the same type in C#:
   ArrayList EndOfQuarterList = new ArrayList();
 
  EndOfQuarterList .Add("March");
  EndOfQuarterList .Add("June");
  EndOfQuarterList .Add("September");
  EndOfQuarterList .Add("December");

To create a list of items of different types in VB:

   Dim MixAndMatch as ArrayList = new ArrayList()

  MixAndMatch.Add("First Item")
  MixAndMatch.Add(10)
  MixAndMatch.Add(3.1416)

  But what if we need a more complex ArrayList? you would need to create a Generic List, this object allows easy creation and manipulation of structured data.

  For example, we need to manage financial information at end of every quarter

   C#:
    class QuarterlyInformation
    {
        private string _Name;
        private byte _Month;
        private double _Income;      
        private double _Expenses;
   
        public string Name
        {
            get { return _Name; }
            set { _Name = value; }
        }      

        public byte Month
        {
            get { return _Month; }
            set { _Month = value; }
        }      

        public double Income
        {
            get { return _Income; }
            set { _Income = value; }
        }
   
        public double Expenses
        {
            get { return _Expenses; }
            set { _Expenses = value; }
        }

        public double ProfitAndLoss()
        {
            return _Income - _Expenses;
        }

        public QuarterlyInformation(string Name, byte Month, double Income, double Expenses)
        {
            this.Name = Name;
            this.Month = Month;
            this.Income = Income;
            this.Expenses = Expenses;
        }
    }

     static void Main(string[] args)
        {
            //handle my quarterly information

            List<QuarterlyInformation> Financials = new List<QuarterlyInformation>();

            Financials.Add(new QuarterlyInformation("March", 3, 100, 50));
            Financials.Add(new QuarterlyInformation("June", 6, 500, 250));
            Financials.Add(new QuarterlyInformation("September", 9, 350, 100));
            Financials.Add(new QuarterlyInformation("December", 12, 100, 50));

            foreach (QuarterlyInformation item in Financials)
            {
                Console.WriteLine("Profit and Loss {0}:", item.ProfitAndLoss());
            }
        }
 
     
       To summarize, generic lists are a great tool to create strong typed collections of objects


Thursday, March 17, 2011

Abrir un Folder con vb .Net

Para abrir un folder usando Vb. Net solo tienes que usar el siguiente codigo

Process.Start("Explorer.exe",Folder_path)

Tuesday, September 19, 2006

Add an error handler routine to your Code

It is important to catch and handle errors on your programs. Yes we are all perfect and our systems do not generate errors, but our users are not perfect and since they do not know what they are doing, we should provide them with some tools to tell us what they did wrong.

This is an VB6 error handler routine

Public Sub HandleError(ErrNumber As Double, Description As String, CurrentModule As String, CurrentControl As String, CurrentRoutine As String)

On Error GoTo OOPS

'Writes error messages to a log file and displays a message

Dim ErrorMsg As String
Dim FileNum As Integer
Dim fileName As String

'Parse the error message
ErrorMsg = "Error : " & Trim(Str(ErrNumber)) & " " & Description & " at " & CurrentModule

If Len(Trim(CurrentControl)) > 0 Then ErrorMsg = ErrorMsg & "." & CurrentControl
If Len(Trim(CurrentRoutine)) > 0 Then ErrorMsg = ErrorMsg & "." & CurrentRoutine

'Display a message box
MsgBox ErrorMsg

'Save the error to a file so you can track errors
FileNum = FreeFile

fileName = App.Path & "\" & App.EXEName & ".err"

Open fileName For Append As #FileNum
Print #FileNum, ErrorMsg
Close #FileNum

ExitHere:
Exit Sub
OOPS:

MsgBox "Error : " & Err.Number & " " & Error$ & " at basGlobal.HandleError"
Resume ExitHere
End Sub



Assuming you want to add an error handler to one of your command buttons on a form:

Private Sub cmdAdd_Click()

On Error GoTo OOPS

Dim Type As String
Dim SQL As String

... your code here

ExitHere:
Exit Sub

OOPS:
HandleError Err, Error$, Me.Name, "cmdAdd", "Click"
Resume ExitHere

End Sub


You can get fancy and create an error handler class that can keep a collection of your errors, etc.
But most important keep it simple otherwise you will have to debug your error handler too.

My next posting will have an error handler class in .Net

Tuesday, September 12, 2006

Mapinfo Professional Geocode with Oracle

I have been working on project that integrates MapInfo, oracle and .Net web development.

How to import MapInfo tables to Oracle.

1.- In your oracle database, create a table space "MapInfo", user: MapInfo password:MapInfo

2.- Create a ODBC Machine Data source pointing to your Oracle Database "MapInfo Oracle" . Make sure the user name has access to your "MapInfo" Table space.

3.- Open MapInfo

4.- go to --> Tools --> Easy loader

5.- click on ODBC, select the machine source tab and select your "MapInfo Oracle" connection

Username: mapinfo
password: mapinfo

6.- Select the mapinfo source directory which would usually be at C:\Program Files\MapInfo Data\US_ExchangeInfoPlus or where ever map info was installed.

7.- You have to select one table at the time:

usnpaxx
uswcpt
uswcreg

on the server table select the appropiate processing option to create the table, append or replace.

8.- Click on update.

Your Oracle database will be updated with MapInfo tables.