Big-O

For those who have a degree in computer science, you’ll immediately recognize Big-O notation.  My data structures class required students to figure out the Big-O for best and worst case situations for sort algorithms.  Today, I stumbled across a Big-O cheat sheet web page that is rather interesting:

Know Thy Complexities!

This is handy for students or developers that are about to use an algorithm and want to check how it should perform depending on the data set they are working on.

Each link takes you to a wiki page on the algorithm in question so you can get details without searching around the web. 

My purpose in posting this on my blog is to make people aware of the existence of this handy website and so I can find it again in the future if I need it myself.

 

More Database Basics

So I just completed a post about database basics and at the end I showed how students (and faculty members) can download Oracle or MS SQL Server, install it on their PC and create a database to match the book they are using in database class.  Then I thought about the fact that I haven’t really used Oracle since 2008 and maybe, just maybe I’m out of practice.  There’s nothing worse than creating a post containing untested code or information that might not be valid, so I went out and downloaded Oracle 11g XE (express).  First, I noticed that there was only a windows x32 version and a warning that it doesn’t work on x64.  Being a skillful developer, I ignored that warning and tried it for myself.  There was some sort of error during the installation but it was more of a warning that something was missing.  This did not affect the capabilities of the installed program from what I’ve used already.  I’m sure it involves stored procedures or maybe some capability that I’m not going to use for an entry level class.  So I dragged out my “Database Systems: principles, design, & implementation” book from the early 1800’s (OK, it’s copyrighted in 1990).

Here’s the starting sample database in the book:

and here’s the matching tables with data:


So, I installed Oracle (which took a very long time), then I jumped right into the control panel, which is all new.  In fact, it’s a web interface now instead of a java application.  No problem, I clicked around the menu options until I saw a table designer interface (I’ll leave it up to the student to read up and figure out how to create a table, it’s easy).  So I created all three tables, two foreign key constraints, some not-null constraints and primary keys for the student and class tables.  Yes, I was cringing as I typed the data in and my mind was just screaming (that should be broken out in a separate table!).  But that’s the purpose of this exercise in the book is to start with a somewhat functional but incorrectly designed database and work through the normalization rules to make this into a properly designed database.

So here are the three final tables and their data in Oracle:

Student Table
 
Class Table
Enrollment Table

As you can see, learning Oracle is like riding a bicycle.  Technically, all databases function similarly.  They all have tables, fields, foreign key constraints, etc.  There are some nuances in the way different databases handle cascade deletes and triggers and other capabilities, but the basic functions are nearly identical.

Any student should be able to download the express edition of Oracle and create the three tables above in an afternoon.  It only took me two hours (one and a half of that was install time).  Warning: If you’re an MS SQL Server user like me, try not to hit the F5 key to execute your query in Oracle.  It just refreshes the browser and erases the query you typed in.

Now you should be able to join the student table to the enrollment table to get a list of students and their grades:

Student Grades

 
Now this is learning!

 

Database Basics or The School of Hard Knocks

This blog post is directed to students who are in college taking a database class for computer science or those who are just starting out in database design.  I’m going to give a little background story of my own early experience in database systems and I’m going to talk about how you can get beyond the eye-glazing boredom of learning databases and get into the hands-on world of actually learning about databases.

Some History

I took a database class at the University of Michigan.  I needed about 33 credits of 300 and above classes to complete my BS in Computer Science, so I filled those credits primarily with computer science classes.  As many as I could take.  Most of the specialized classes I took, like modeling and simulation, I blew through without studying.  Technically, I was hungry for information on simulation techniques and it was a fun class for me to take.  When I arrived at database class, our instructor was working from class notes that he developed from the main-frame era (which really wasn’t that long ago from when I took that class, but it was still a bit outdated).  He spent a lot of time on the theory of database design, foreign keys, candidate keys, First Normal Form, etc.  I understood what he was talking about as he was talking in class, but I really had to make up some flash cards for each concept and practice memorizing them to pass the test.  I assumed that databases were just not my thing.  Boy was I wrong!

So MS Access, version 1.0, arrived right around the time I graduated from college and I had a friend that wanted a database built for his business.  It was relatively easy to build, until I discovered that some things didn’t quite work right.  What compounded my problems was the bugginess of version 1.  Still, I assumed that databases were just not my thing.  When I arrived at Pirelli, I was tasked with building a real-time data collection system.  My database was again MS Access.  This was due to restrictions put on me by Pirelli’s IT department, not my choice.  By then, MS Access was up to version 3 and it was a more mature product.  Still, I made the decision up front to avoid using most of Access and just use the tables for storage and use VB version 5 to read and write to the tables.  This database was rather simple since it only collected basic information from the tire building machines in the factory.  The difficult part of that project was keeping up with real-time data.  If I had my choice today, with my current level of experience, I would insist on Oracle or MS SQL server and I might have even suggested experimenting with MapReduce (though, I don’t think they had that much data to store).

So I was recruited into Building Technology Associates by a former professor that just happened to be working as the IT manager at that company.  BTA had a problem.  OK, they had a few problems.  First, they consisted of 3 companies in the same building and two of the three companies had their own database development team that operating independent of each other.  Their second and most critical problem was that nobody in either team had any formal database knowledge when they built either database and both database were built on the premise that a database is just a collection of spreadsheets in one location.  Arrrgghh!! 

This is where I really learned how to properly design a database.  This is where reality met up with database theory.  Let me describe what I had to start with:

Database 1:
– Built with MS SQL version 6.5 on a PC running Windows NT 3, unpatched.
– Many foreign key fields were nullable and contained text.
– One foreign key field contained letters, each letter represented a different record from a lookup table (called subsystems) and the programmers used substring in their program to figure out which subsystem applied to each record.
– No relational integrity constraints.

Database 2:
– Built with MS FoxPro 5.0 hosted on the file server.
– Some tables contained old foreign keys that consisted of a unique number, but nullable fields.
– Some tables contained a new foreign key that was based on the millisecond clock and contained a string of characters that could contain an ASCII value between 0 to 255.  Also, nullable.
– No relational integrity constraints.


What I described above was just the beginning of my problems, but sometimes when things are really bad you have to Triage.  So the most important problem to fix first was the foreign keys and the relational integrity.  At first, I wanted to refactor everything (this was before the word “refactor” became as common as it is today).  Unfortunately, things were so bad that we had people dedicated to fixing data issues that was caused by the above database integrity problems coupled with bugs in the software. 

So I set into place a plan to build a new database in Oracle.  The first task I needed to do was determine how the primary keys would be produced.  I needed to make sure that all tables had a primary key and they had to be unique.  The problem was that we had a lot of external software that generated records that would be imported and renumbering keys was a nightmare.  So I invented a scheme involving a 12 character key that consisted of a 4 character unique prefix, issued by the master system and an 8 character locally generated key.  Each piece of software, when first installed would be missing the registry entry that contained the prefix.  So the software would ask for a prefix disk (floppies back then), and we distributed prefix disks with 10 prefixes on each.  We used 0-9, A-Z and the underscore as legal characters in this key scheme (uppercase only).  I had to analyze if we would run out of keys and when would we run out if data was generated continuously 24/7/365.  Since a digit consists of 37 possible characters and there are 8 digits, that gave us 37^8 number of combinations for each user (that’s 3.5 x 10^12 keys total).  If you generate 100 keys every second of every minute of every hour of every day each year, you’ll use up 3.7×10^10 keys.  Which comes out to about 92 years before burning up all the keys and requiring to get a new prefix.  So it’s safe to say that we’re not going to run out of keys soon.  Anyway, I check every few years to see who’s account has burned up the most keys (all the prefixes and keys are stored in the database for web users) and keys are not being used up anywhere near that speed.  My fallback plan is to expand the key size to 32 digits, but that’s only if data increases in speed.

Database 2 had a clever scheme by generating keys using the millisecond timer and just converting to an 8 character key.  Unfortunately, by the time I came on the scene, computers were becoming fast enough to generate keys faster than 1 millisecond.  So importing data that required new keys was causing duplicate keys to be generated.  Also, it was impossible to type a particular key into a query because many of the characters were unprintable. 

My second strict rule was NO NULLABLE FOREIGN KEYS!  Wow.  That caused a couple of ugly data problems to occur.  The person who designed database 2 was still working for the company when I was investigating these databases and I asked him why he didn’t use the integrity constraint capabilities available to FoxPro.  He claimed (I’m not kidding) that he tried it once but it just broke his software, so he deleted all the constraints that he set up.  AHHHHH!!!!!  So my third strict rule was to put the constraints in place and fix the software.  Much of the software had to be re-written to make it work with the new database, but we managed to make some of it work with the new database.  Then we created a converter to convert the old databases into the new Oracle database.  Oh, that was fun.  My determination paid dividends, because after we rolled out the new database, over half of our software problems vanished and our database integrity problems went to near zero.

So How Do you Learn the Lessons Before Meeting a Disaster?

If you are in database class, download MS SQL server express (it’s free) from here.  Install it, and play around with it.  Create some tables by hand.  Setup foreign keys.  Follow your book.  If you’re a professor teaching database class, create some sample problems containing violations of various normalization rules.

When you’re satisfied with your ability to perform basic database tasks with MS SQL, I would recommend putting in the extra effort to learn Oracle.  Once you learn one database, any other database is just a little different from the one you learned.  It’s best to see it up close a personal.  Click here to download the Oracle express version (free for developers).  There is a windows version that you can install that gets you up and running without installing a server.  If you’re familiar with Linux and you happen to have a Linux machine setup already, you can experiment with the Linux version of Oracle and learn all the nuances of connecting to an Oracle server.

If you install these databases on your machine and practice with them as your professor teaches the class, you’ll learn database theory much easier than just memorizing terms out of the book.  Trust me, I know all about foreign keys, Functional Dependencies, Candidate keys and various other terms, now that I know what they really are.

You can also practice with MS Access if you bought the professional version of Office that comes with MS Access.  Or you can purchase MS Access, but I would recommend sticking with one of the most commonly used database servers that I mentioned above.  There are also other servers like NoSQL and MySQL, but they are a bit looser with their rules.  Keep to a database system that has strict rules and learn it.  Then it’s a piece of cake to use one that doesn’t have strict rules.

That’s all for now, I’ll make a note to do a follow-up post with some example MS SQL and Oracle practice databases to help you learn more about database design.

 

More SVG

In this blog post I’m going to talk about SVG again.  One of the great advantages that SVG has over Silverlight is that it is built into the browser.  That means that you can use it anywhere in the browser window.  Plug-ins are restricted to the box where they are plugged in.  Click on the following link for a sample of what I did off the top of my head in a couple of hours:

SVG Demo


First, you’ll notice that I painted some yellow circles behind the text.  The text is not part of SVG, but part of the web page HTML itself.  I just set the z-index to a negative number to force it behind the text.  Second, you can see some annotation text and red text that points to “stuff” just to show that images can be created and plotted anywhere.  Unfortunately, there is a pixel difference between different browsers (probably in the font style), so your images might not line up with text in all browsers. 

The last demonstration is a bar chart that I threw together just to demonstrate something useful that can be plotted on the screen.  The gray grid is nothing more than horizontal and vertical lines painted first, then the 3d looking boxes are painted over using rectangles and polygons (see picture below):

As indicated in the text above this chart, I designed one bar and put the code in a method call that I call repeatedly with different parameters.  I just feed the method with the height of the red, yellow then green boxes.  In addition I fed the horizontal and vertical positions. 

The Code

First, I’m going to just spit this out from the code-behind page and ignore all conventions regarding business layer, presentation layer, etc.  This is just a demonstration to show feasibility and ease of development.  So I made up a “Print” method that I use over and over to spit the html out to the browser:

public static class UI
{
    public static void Print(string psText)
    {
        HttpContext.Current.Response.Write(psText);
    }


….

There is also a header and footer method inside the UI class:

public static void Header()
{
    string lsHTML;

    HttpContext.Current.Response.Cache.SetExpires(DateTime.UtcNow.AddDays(-1));
    HttpContext.Current.Response.Cache.SetLastModified(DateTime.UtcNow.AddDays(0));
    HttpContext.Current.Response.Cache.SetCacheability(HttpCacheability.NoCache);


    lsHTML = @”
        <!DOCTYPE html>
        <head>
        <meta http-equiv=’Content-type’ content=’text/html;charset=UTF-8′ /> 
        </head>
        <body>
        “
;

    Print(lsHTML);
}


public static void Footer()
{
    Print(“</body>“);
    Print(“</html>“);
}


} // end of UI class

Now, it’s time to move on to the meat (I made it tiny font to fit the page, sorry if you wear glasses like I do):

using System;
using System.Collections.Generic;


namespace SVGDemo
{
    public partial class svg_demo1 : System.Web.UI.Page
    {
        protected void Page_Load(object sender, EventArgs e)
        {
            Render();
        }
        private void Render()
        {
            UI.Header();


            UI.Print(@”
                <svg xmlns=’http://www.w3.org/2000/svg’ version=’1.1′ width=’1000′ height=’1000′>
                “
);

            SVGBarChart laSVGBarChart = new SVGBarChart(570, 300);
            laSVGBarChart.AddDataPoints(“5,50,40 10,30,80 15,25,95 25,10,75 30,5,15 30,25,15“);
            laSVGBarChart.Render();
           
            UI.Print(@”
                </svg>”
);

            UI.Footer();
        }
    }


    public class SVGBarChart
    {
        public int BarChartLeft = 570;
        public int BarChartBottom = 300;
        public List<SVGBarChartItem> Items = new List<SVGBarChartItem>();


        public SVGBarChart(int piLeft, int piBottom)
        {
            BarChartLeft = piLeft;
            BarChartBottom = piBottom;
        }
        public void AddDataPoints(string psDataPoints)
        {
            // expecting “x,y,z x,y,z”
            string[] laDataPoints = psDataPoints.Split(‘ ‘);

            for (int i = 0; i < laDataPoints.Length; i++)
            {
                string[] laSections = laDataPoints[i].Split(‘,’);

                Items.Add(new SVGBarChartItem(laSections[0].ToInt(), laSections[1].ToInt(),
                    laSections[2].ToInt()));
            }
        }
        public void Render()
        {
            DrawGrid(BarChartLeft – 50, BarChartBottom – 160, Items.Count * 50 + BarChartLeft,

                BarChartBottom + 20);

            for (int i = Items.Count – 1; i > -1; i–)
            {
                Items[i].RenderBar(i * 50 + BarChartLeft, BarChartBottom);
            }
        }
        private void DrawGrid(int piLeft, int piTop, int piRight, int piBottom)
        {
            // horizontal lines
            for (int i = 0; i < (piBottom – piTop) / 10 + 1; i++)
            {
                UI.Print(“<line x1=’” + piLeft + “‘ y1=’” + (piTop + i * 10) + “‘ x2=’” + piRight + “‘ y2=’

                    + (piTop + i * 10) + “‘ stroke=’#aaaaaa’ />“);
            }

            // vertical lines
            for (int i = 0; i < (piRight – piLeft) / 10 + 1; i++)
            {
                UI.Print(“<line x1=’” + (piLeft + i * 10) + “‘ y1=’” + piTop + “‘ x2=’” + (piLeft + i * 10)

                    + “‘ y2=’” + piBottom + “‘ stroke=’#aaaaaa’ />“);
            }
        }
    }


    public class SVGBarChartItem
    {
        int RedHeight;
        int YellowHeight;
        int GreenHeight;


        public SVGBarChartItem(int piRedHeight, int piYellowHeight, int piGreenHeight)
        {
            RedHeight = piRedHeight;
            YellowHeight = piYellowHeight;
            GreenHeight = piGreenHeight;
        }
        public void RenderBar(int piLeft, int piBottom)
        {
            // draw one bar
            int liWidth = 30;
            int liHorizontalOffset = 10;
            int liVerticalOffset = 6;
            int liTop1 = piBottom – GreenHeight – YellowHeight – RedHeight;
            int liTop2 = piBottom – GreenHeight – YellowHeight;
            int liTop3 = piBottom – GreenHeight;


            // top cap
            UI.Print(“<polygon points=’” + piLeft + @”,” + liTop1 + @” ” + (piLeft + liWidth) + @”,” +

                liTop1 + @” ” + (piLeft + liWidth – liHorizontalOffset) + @”,” + (liTop1 – liVerticalOffset)
                + @” ” + (piLeft – liHorizontalOffset) + @”,” + (liTop1 – liVerticalOffset) +
                @” fill=’#cc0000′ />“);

            // red bar front
            UI.Print(“<rect width=’30’ height=’” + (liTop2 – liTop1) + @”‘ x=’” + piLeft + @”‘ y=’” + liTop1

                + @”‘ fill=’#ff0000’ />“);

            // yellow bar front
            UI.Print(“<rect width=’30’ height=’” + (liTop3 – liTop2) + @”‘ x=’” + piLeft + @”‘ y=’” + liTop2

                + @”‘ fill=’#ffff00’ />“);

            // green bar front
            UI.Print(“<rect width=’30’ height=’” + (piBottom – liTop3) + @”‘ x=’” + piLeft + @”‘ y=’” +

                liTop3 + @”‘ fill=’#00ff00’ />“);

            // red bar side
            UI.Print(“<polygon points=’” + piLeft + @”,” + liTop1 + @” ” + piLeft + @”,” + liTop2 + @” ” +

                (piLeft – liHorizontalOffset) + @”,” + (liTop2 – liVerticalOffset) + @” ” + (piLeft –
                liHorizontalOffset) + @”,” + (liTop1 – liVerticalOffset) + @”‘ fill=’#aa0000’ />“);

            // yellow bar side
            UI.Print(“<polygon points=’” + piLeft + @”,” + liTop2 + @” ” + piLeft + @”,” + liTop3 + @” ” +

                (piLeft – liHorizontalOffset) + @”,” + (liTop3 – liVerticalOffset) + @” ” + (piLeft –
                liHorizontalOffset) + @”,” + (liTop2 – liVerticalOffset) + @”‘ fill=’#aaaa00’ />“);

            // green bar side
            UI.Print(“<polygon points=’” + piLeft + @”,” + liTop3 + @” ” + piLeft + @”,” + piBottom + @” ” +

                (piLeft – liHorizontalOffset) + @”,” + (piBottom – liVerticalOffset) + @” ” + (piLeft –
                liHorizontalOffset) + @”,” + (liTop3 – liVerticalOffset) + @”‘ fill=’#00aa00’ />“);
        }
    }
}

First, I threw a “render()” method together and called it from the main call-behind method.  I just did that to keep the main method clean.  Inside the primary render method I print out the header and starting SVG code.  Then I instantiate the SVGBarChart object and fill some sample data.

If you look closely at the SVGBarChart object, you’ll notice that the AddDataPoints method accepts a string but does not do any input checking.  Never do this in a production system!  Always verify your data, even if you are the one writing both the method and the call to the method.  In this instance I assume that the input will be formatted in a string containing groups of 3 numbers separated by commas (each group separated by a space).

The DrawGrid method will spit out the horizontal and vertical lines for the background grid.  This is called from within the SVGBarChart.Render() method.

Each bar is handled from a separate object called SVGBarChartItem.  The main object (SVGBarChart) contains a list of these objects, one per bar.

There is a “ToInt()” method that I did not include in this code.  You can change the code to cast into an integer or download the code here:

SVGDemo zip file

The entire demo project is included in this zip file.  It’s in Visual Studio 2012, but you can just copy the contents of the Default.cs file into your startup website code-behind page.  Be sure and remove all but the top line of the aspx page.  Otherwise, you’ll end up with some unwanted HTML code.

Summary

The whole point of this blog post was to show the power and ease of use of the SVG capabilities of modern browsers.  This code does not need a plug-in and is compatible with Opera, Chrome, Safari, FireFox and IE9 and above.  My go-to source for SVG object syntax is w3c schools (click here).  So start using SVG and let your imagination run wild.


 

SOA, JSON, WCF, REST

SOA

I’m currently working my way through the subject of Service Oriented Architecture, or SOA.  I have a book on the way, but I’m getting a jump on the subject.  In previous blog posts I’ve talked about the necessity to do research.  This is one of those instances where I have applications to do some task and I need to learn the technology to make it happen.  Sometimes it can take a couple weeks to learn a new technology, type in a few test programs and then obtain that “aha” moment.  Once that occurs, then it’s time to design and implement.  In the case of SOA, I haven’t quite reached the implementation “aha” moment yet.  I understand the overall purpose and what I will be using SOA for is to transfer data between iPhone apps, iPad apps and our database.

So I’ve done a bit of digging and I’ve stumbled across a few technologies that I’ve seen in the past but paid no attention to (due to the fact that I had no purpose for them before).  One technology I’m focusing my attention on today is WCF.  WCF is the Windows Communication Foundation and allows two apps to communicate.  Primarily an app (any application) with a service running on a different server.  I plan to run a service on a server in the computer room and make a secured connection (probably SSL) between a mobile device and the server.  The service will be able to read and write data to the database.  This will enable our field personnel to record information with their iPhone or iPad.

WCF

Before I get to the whole design and implementation, I have to test a few technologies to see how I can apply them.  I’ve already tested JSON and I’m satisfied with my knowledge of JSON for now.  At this point, I can design a software specification that indicates how JSON will be used and I can either code this myself or pass on the information to a programmer that will be implementing the actual coding.

I found this very simple example of a client and server test setup for WCF:

A truely simple example to get started with WCF

So I copied the code into a console application and I had to mess around with it a bit to get it to work right.  One thing I changed that was not indicated in the article is that I put the server and contract into a separate project of the same solution.  I had to do that in order to keep the complier from complaining about two entry points.  Technically, I have a solution with two console applications in it.  One is used as a module for the other.  It works, and it’s just a R&D test case.  My next step is to separate these sections and run them on separate PC’s to see if they’ll communicate correctly.  After that, I’ll put the server inside a service component and test it under that condition. 

REST

Representational State Transfer (REST) is not a subject that I am currently familiar with.  That’s my next subject to study.  I will be focusing on this subject next.  Rest is supposed to be lightweight and simpler than RPC.  I will be judging for myself.  Not that I’m skeptical, I just want to see how this works.

JSON

As I mentioned before, I’ve already done some R&D on JSON and I’m impressed.  My plans are to use JSON instead of XML for structured data transfers. 

Summary

My point in this posting is to show that nobody is an expert in every subject.  They best way to become an expert in a subject is to keep your eyes open to what technologies are available.  Sometimes I see an acronym that I’ve never seen before.  It starts to get a lot of hype in magazines and news articles.  So I lookup the definition or wiki on the acronym and see what the actual purpose is.  If it’s something that could revolutionize my projects, then I start to investigate it more (or I’ll relegate a software developer to R&D it and report back to me with a small demo).  Once a demo has been created, then I can evaluate the usage of the new technology and incorporate it into our business plans. 

Other times, I have a problem to solve and I know that other companies are doing this very task (i.e. talking between iPhone apps and their databases).  So I start searching for information on the Internet.  It usually doesn’t take me long to come up with one or more technologies that are candidates to becoming my solution.  After that, I just work my way through each innovation until I’m satisfied with the solution I want to work with.

In this business you can never stop learning new things.

 

JSON

So my latest endeavor is to learn JSON.  I mentioned in an earlier post how I do research all the time.  Well, I stumbled across a subject called SOA (Service Oriented Architecture) and I started to read articles on the Internet and decided that this is a major subject that I wanted to know about.  So I bought a book (and of course, I’m still waiting for the book to arrive).  In the mean time, I discovered this data exchange format called JSON.  One of the first projects I tested reads data from a currency service.  The code and instructions are located here:

Use C# to get JSON Data from the Web and Map it to .NET Class => Made Easy!

It’s from codeproject, and it worked the first time.  One step that was different involved the currency exchange service.  They changed their requirements and they require an id to download their data.  They also have a different link, but it’s easy to get this information by going to their site:

Open Exchange Org

Click the “Get Instant Access” button and look for the little “free” link at the bottom. You can enter your email information and get an account for development purposes for free.  This will then lead you to a webpage that gives you an “App ID” and instructions including the actual link you need to call to receive data in JSON format.


Back to JSON

So I’m looking at how JSON is able to get data from a remote website and use it within my own website.  Then I discovered a weather service that is free and provides a JSON API.  The reason this interested me is that my company does site management for roofing.  What site managers do is they watch the roofing contractors install the roof and they mark of the information on a daily quality report.  The quality report includes information about the local weather.  The purpose of recording all this information is to resolve disputes in the future if a roof system fails.  Here’s a list of weather services that provide JSON data:

Weather services using JSON

and here’s the free one that I’m currently looking at:

Free Weather API for developers

What’s the purpose?

The weather information that can be read from this website can be transferred to my website by clicking a button.  My intention is to be able to read the weather for the current location at a designated date (site managers can create a quality report after they have performed the site inspection, so they might want to record yesterday’s data, for instance), then pre-populate the weather fields in the quality report.  This relieves the site manager from going to a weather service and looking up what the official weather was for that date (site managers don’t carry weather measuring equipment like thermometers and anemometers).

My real purpose in doing these exercises is to be able to communicate between two processes on different computers.  I have developed “Service” type applications that sit on a dedicated machine and poll a database queue waiting for some data to crunch.  The purpose of doing this is to be able to process lengthy data from a website without requiring the web consumer to stay logged in while the data is being processed.  Web users can process huge numbers of data points and come back and check the progress later.  Meanwhile the data is being processed by a machine in the computer room that is running a service type program.  One major inefficiency of polling in general, is that it is wasting time and resource constantly reading the database to see if there is something in the queue.  Over 99% of the time, there is nothing in the queue to process, so this constant querying (usually every 2 seconds) is consuming resources.  Also, the poll time determines how fast the process will respond to a request.  In order to make this all more efficient, it would be better to queue the items needed to be processed, then send a JSON message to the service to indicate that it needs to process a bunch of data.  That way the remote service application doesn’t have to constantly poll the database.


So what is JSON anyway?

JSON is a lot like XML.  It’s a data transmission format.  It’s very clever in that it’s more compact than XML and it can be directly translated into an object in C# or JavaScript (and many other languages).  It’s also language independent.  For example, a service running Python could provide a JSON encoded data string that can be consumed by a C# program.  This means that a mainframe computer system could communicate with an IIS server without requiring a programmer with knowledge of both languages used.  Two programmers could agree on the JSON format between the two machines and they could each create an interface to communicate between machines.

My motto: Never stop learning.


 

Linked Lists – Adding and Deleting

Getting Started

In my last blog post I showed how I setup a basic board game with an array of linked lists.  Now I’m going to show you some straight C code to add a unit to the board.  I used a standard WIN32 console application, just to get past the complex interface code.  My purpose is to show the linked list part. 

First, we’ll need a structure:
 
struct Unit
{
 int Offense;
 int Defense;
 (Unit *) Next;
};

This structure will store the variables that represent the unit offense and defense numbers.  The “Next” variable is a pointer to the next unit node in the linked list.

The game board

The game board is nothing more than a 4×4 array of Unit structure pointers that I declared globally:

Unit * PlayingBoard[4][4];

The problem with this array is that each cell has an unknown value in it.  So we’ll need a function to make sure all cells contain a NULL value to begin with.  I called that function “InitializeBoard()”:

void InitializeBoard()
{
    for (int i=0;i<4;i++)
    {
        for (int j=0;j<4;j++)
        {
            PlayingBoard[i][j] = NULL;
        }
    }
}

Add a Unit

Now, we’ll need a way to add a unit to the board.  I want to set this up so the whole “pointer” arrangement is hidden from the game designer.  I just want to use pointers inside the lowest level functions.  This will prevent someone else from having to do all the allocation and de-allocation when they can just call the low-level functions that create pieces and delete pieces.  So I’m going to use the malloc command in this function to get enough memory to use as my structure.  To make sure I have the exact amount of memory that I need, I used the “sizeof” command with the structure name.

void AddUnit(int pUnitType,int pX,int pY)
{
    int liOffense = 1; // default to soldier
    int liDefense = 1;


    if (pUnitType == 1) // tank
    {
        liOffense = 3;
        liDefense = 5;
    }


    if (pX < 4 && pX > -1 && pY < 4 && pY > -1)
    {
        Unit * p = (Unit *)malloc(sizeof Unit);
        if (p)
        {
            p->Next = PlayingBoard[pX][pY];
            PlayingBoard[pX][pY] = p;
        }
    }
}

Notice how I checked to make sure that the x and y coordinates that were passed in as parameters are within the range of the board.  Don’t assume anything!  I also made sure that the malloc command returned a valid pointer.  If not, then the playing piece will not be added to the board.  There should be a warning message recorded someplace so that it can be checked after testing the game to see if any memory problems had occurred during the game.  If this type of memory problem occurs, then the playing piece won’t show up, but the game will continue to work without crashing.

Delete a Unit

Now, it’s time to delete a unit:

void DeleteUnit(int pX, int pY)
{
    if (pX < 4 && pX > -1 && pY < 4 && pY > -1)
    {
        if (PlayingBoard[pX][pY])
        {
            Unit * p = PlayingBoard[pX][pY];
            PlayingBoard[pX][pY] = p->Next;
            free(p);
        }
    }
}

Again, I checked to make sure that the x and y parameters are inside the actual board.  Then I check to make sure that the element at that grid location is not NULL.  Don’t forget this step, because there might not be a unit at the location that the function wants to delete.  Now for the tricky part.  First we have to assign the top unit (the one linked to the board) to a temporary pointer, that I called “p”.  Then we can assign the board position to the “Next” pointer of that Unit.  This will cause the stack to shift up one.  If “Next” is equal to NULL, then that will just get assigned to the board and no unit is sitting on that board position.  If there is another unit attached to next, then it will get assigned to the board.

The last line will free the temporary pointer to the Unit we’re trying to actually get rid of.  This returns the memory back to the operating system.

Tying it Together
Now, we need to actually write a program that uses all the above pieces.  You’ll need to add a stdlib.h header declaration at the top.  That is where the malloc and free commands reside.  You’ll also need to add any function declarations at the top of your file to make sure they can be called:

#include <stdlib.h>

// function declarations
void InitializeBoard();
void AddUnit(int pUnitType, int pX,int pY);
void DeleteUnit(int pX, int pY);

Then, make sure you call the InitializeBoard() function first.  After this, you can call AddUnit and DeleteUnit for any square on the board.

To download the complete CPP file click here: linked list source code file.

What’s Next?

If you typed in the code above (or copied and pasted), you’ll notice that this is not really a “game” yet.  What it would take to make this into something useful is a few more low level functions.  One function that will be necessary is a complete board clear.  You’ll have to do a while loop on a board cell and call Delete unit until a NULL is detected.  Then do that for every cell.  You could change the DeleteUnit function to return a true/false depending on if the “Next” unit was NULL or not.  That could signify if there are any additional units at that cell.  Then just created a function that calls DeleteUnit until false for each cell.

Other functions needed are a function to render the units on the screen.  This, of course, depends on what you want to be displayed.  If you just want to work on the game engine first and ignore the graphical front end, you can just setup a dumb and dirty text based interface to use symbols to represent each unit on the playing board.  Or you can go for the cool graphics first and get it to look right before you start working on the game AI. 

You’ll need functions to read and write the offense and defense numbers.  Since the top unit is the only unit fighting at a time, then only the top defense and offense matter.  Remember the goal is to keep all the pointer code inside the lowest level units.  Make these units perform the minimum task they need to perform, then do the complicated stuff by calling these functions.

I hope this blog post helps you to learn pointers better. 

 

 

Linked Lists

Basic Unordered Linked Lists

So my last blog posts was about pointers.  I gave a little historical context to the fact that I’m a self-taught pointer maniac.  The past 6 years is the longest stretch I’ve gone without using a pointer.  That is due to the fact that I now program using C# instead of C/C++.  Sometimes I miss pointers.  They’re so powerful.  What I don’t miss about pointers and what I love about C# is the memory management aspect of it all.  That’s why I’m so methodical about assigning nulls and checking before allocating and de-allocating memory.  There are other tests that should be performed as well, and I’m going to talk about it right now.

What happens if your application runs out of memory?  It could happen.  It does happen.  So the C/C++ malloc command has a flag for that, it’s called null.  Yup, you guessed it, when you attempt to allocate a pointer and there is no memory available, the malloc command returns a null pointer.  So always check to make sure the pointer is not null before using it.  Here’s an example from the sample code used in my previous blog post:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer = NULL;
 
    if (!mypointer)

    {
        mypointer = (char *)malloc(1);

        if (!mypointer)
        {
            // perform some sort of error reporting here
            return -1;
        }
    }

    *mypointer=’a’;

    if (mypointer)
    {
        free(mypointer);
        mypointer=NULL;
    }
}


I returned a “-1”, that’s just my return for an error code in this sample.  Your method might not return anything and you might have to exit out of the program entirely.  Anyway, it’s on to linked lists.

What is a Linked List and Why Use them?

So I used to program games as a hobby.  Nothing serious, just a hobby.  I liked to play Avalon board games, mostly World War II style strategy games and I made an attempt at writing a C++ war game with a similar board design.  Here’s what Panzer Blitz looks like:

One of the things I noticed about the hex shaped board locations is that it is really just an array where the odd numbered columns are shifted half way up or down.  Here’s what I’m talking about:


As you can see by the cell numbers the hex board on the left is the same as the shifted square board in the middle and the same as the 4×4 array on the right.  So I used an array to represent the map positions of each piece.

Now, it’s on to the playing pieces.  One of the fun aspects of these types of games is that you can stack pieces.  Here’s a sample picture I found using Google (I’m just trying to avoid dragging out the game and taking photos myself):


This is where pointers become fun.  Yes, I said fun.  But first, it’s time for a little diversion, let me explain what a linked list looks like in an abstract diagram form.

First, I’m going to use structures to store information about each playing piece.  Each tank and soldier (I’m really trying to keep this simple) will have one structure allocated in memory and then I’m going to link them together into little stacks.  Like this:

This is a list of three pieces, two tanks and a soldier.  Inside each structure (not shown) is a variable that is the pointer to the next structure and the last structure points to null.  The variable “P” here is the pointer to the first playing piece in the list.  What I’m going to do here is setup a playing board that has an array of pointers.  Each cell in the array is nothing more than a pointer, then I’ll initialize them all to null.  When I place one or more pieces on the board, I just set one of the array cells to point to the top of the list or stack.  Like this:

Now the basic game structures are setup.  The rendering engine can run through the array and paint the associated background image (which can be stored in a separate array) and if the pointer in this array is not null, then render the top piece offset by the number of pieces in the stack so the height is different depending on the number of pieces. 

When the user drags a stack of pieces, the pointer at the array cell containing the stack can be copied to the new grid location and the old pointer in the array can be set to null.  This will have the effect of moving an entire stack of playing pieces without moving a bunch of data.  Just re-adjusting the cell location of the pointer to the stack.

One of the rules of the game is that the top piece is attacked first.  Once eliminated, then the next piece in the stack is under attack.  So if the top tank in the sample game board above becomes destroyed in game play, then the top tank can be assigned to a temporary pointer, then the game board array cell can point to that tank’s “next” pointer.  Then the first tank can be de-allocated.  Poof, it’s gone:

If the last tank at that grid position is destroyed, then the same exact algorithm can be performed to set the grid to that tank’s “next” pointer and de-allocate that tank.  The “next” pointer just happens to be null, so that board position is now empty and the rendering function will just render the background.

I’m going to wrap this discussion up for now, but next time I’m going to do some example code to demonstrate the basics of how this is all performed.



 

Pointers

Ok, I’m in the mood to do some technical blogging.  I was reading an article recently about the fact that many universities are teaching computer science using languages such as Java that don’t use pointers.  I’m starting to feel like one of those old guys saying things like “back in my day….”.  Here’s the article I was reading a while back: The Perils of JavaSchools.

First, I’m going to give you a bit of history about me.  I spent 6 years of my youth in the Navy as an electronics technician.  During that time I bought a computer that was just small enough to fit in the tech cabinet in the transmitter room (we kept tools and parts in that cabinet and I stored my computer on the bottom shelf).  The computer I bought was an Apple Macintosh.  Oh yeah, “THE” Macintosh.  With a grand total of 128k of memory.  This machine was just enough to wet my appetite for programming.  Of course, I only knew two languages at that time.  The languages I knew were Basic (with line numbers) and 8080 assembly (from a computer board I built by wire-wrapping, I’ll do a post on that later).  Anyway, Basic was very hard to use with line numbers and Apple upgraded the mac to a 512k version within months of my purchase.  So I upgraded my mac and I ran to the Apple store and looked for a new language.  I saw a box of Mac Pascal and the syntax looked very much like Basic, so I bought it.  Oooh, it was really cool and shiny.  Yup, I taught myself Pascal just so I could program games.  I had great ambitions back then.

So I’m writing code for a game I had in mind and suddenly, I discovered that Mac Pascal can only access 32k of global memory.  That was a bummer because I couldn’t store my game board and all the playing pieces in memory.  So I bought some books (yeah, no Google back then, this was 1985 or so) and learned dynamic memory techniques.  This was kind of a no brainer for me due to the fact that I already knew how to program in assembly language for an 8080 processor.  Therefore, I knew all about memory addresses.  The 8080 lacked a lot of features for sophisticated memory addressing, but it did use an H & L register combination to reference memory.

Anyway, back to pointers…

Uber-Simple Pointers

All right, a pointer is basically a memory address.  That’s it.  Nothing more.  The trick is how to work with pointers.  You could just put in a memory address and access the memory, but more than likely, the computer will crash or give you a memory fault.  That’s because the computer uses memory for the operating system and memory to run other things, before your program has a chance to start running.  Only the operating system knows what memory is in use at any given time.  So you have to ask the OS for memory, then the OS will give you an address to the location that you can use. 

Here’s an example of a computer with 10 bytes of memory that is not in use:

Each number represents the address of that memory cell.  To keep this simple, I’m going to ignore the amount of memory allocated at a time and assume that the OS only gives you one cell at a time.  This would not be very useful in reality, but it’s just an example.
So now your program starts and you are about to ask for some memory from the OS.  This is what the memory starts out as:

The gray cells represent the memory cells in use by the OS and your program.  You don’t really care about what memory is in use, because you just want a pointer to one memory cell that you can use.  So you call the “new” or the “malloc” command in C/C++ and you get a pointer to a cell of memory.  A typical program in C++ would look like this:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer;

    mypointer = (char *)malloc(1);
}

Now the character variable “mypointer” is not a character but an address or pointer to a character.  The OS will lookup a blank memory cell, mark it as “in use” and then give your program the address (by use of the malloc() procedure) which is stored in “mypointer”.  So now you’re memory would look like this:

And your variable “mypointer” would contain the address 5.  If you were to print the address by converting the pointer into an integer, you would see the actual address number.  However, you don’t really care what the address number is because “mypointer” will keep that for you and now you can read and write to that address location.  This process is called “allocating memory.”  Now I’m going to add a line of code to put a character into address 5:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer;

    mypointer = (char *)malloc(1);

    *mypointer=’a’;
}

Notice the “*” before the variable “mypointer”?  The star represents “location of” and means that we are putting the character “a” into the memory location that the variable “mypointer” contains.  If you left the star off the beginning of the pointer address, then “mypointer” would be replaced with the ascii value of ‘a’ (technically the compiler should complain that it’s not a number).  Now our memory looks like this:

All right.  I’m almost to the end of the “uber-simple pointer” example.  The final thing you must remember to do is give the memory back to the operating system when you’re finished with it.  Remember, you’re just borrowing the memory, if you don’t give it back, then it can’t be used by any other program running on your computer.  If you keep allocating and don’t give it back, then you’ll create what is called a “memory leak.”  This is where the computer keeps running out of memory because your program is allocating it and not giving it back.

To “de-allocate” memory, you can call the “free” command:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer;

    mypointer = (char *)malloc(1);

    *mypointer=’a’;

    free(mypointer);
}

On last thing.  When you start a program, set your new pointer variables to “null.”  Null is a special memory address (usually zero), that is universally accepted as a pointer that is pointing to nothing.  When you reference a pointer in a function and you’re not sure if it has been allocated yet, you can check to see if it is null first.  Here’s an example:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer = NULL;
 
    if (!mypointer)
        mypointer = (char *)malloc(1);

    *mypointer=’a’;

    if (mypointer)
    {
        free(mypointer);
        mypointer=NULL;
    }
}
Notice how C will recognize a null pointer as a false variable.  This example is so tiny that it’s difficult to see the use in performing such extra work, but a large program might have variables declared in a location that is nowhere near where the pointer is allocated.  Using this technique will prevent you from referencing a memory location that is not allocated.  Such bugs are very difficult to find, but a null pointer error is obvious.  Also, notice how I re-assigned null to “mypointer” when I freed it up.  If this pointer is referenced in code after being freed, then the null value will cause your program to bomb and tell you that you made a mistake and used a freed pointer.

Conclusion

Pointers can get tricky, but if you follow the basic rules that I laid about above, you should be able to work through dynamic structures with ease.  In the future I’ll go over some very basic dynamic structures like linked lists and try to make it as simple and visual as possible.  But for now, good luck with your programming.