tomorrow development

Sunday, January 22, 2012

from high to low: design wsdl for your webservice

I spent a couple of last days to design wsdl for third-party systems in my new project. It got me some painful moments, so i decided to write a post about problems i met and may be some thoughts i gained during the process. I ll try to emphasize them below for more effect.
The idea was that i had an interface (not in C#-syntax or so, but described by words/UML) and i needed to create a wsdl for third-party systems to implement the interface. Show/hide

Friday, January 6, 2012

persistence.xml within "Dynamic Web Project" in eclipse

Being totally newbie at j2ee area, i decided to spent some time looking through the area and to get familiar with appropriate technologies. After reading about odata and servlets, i decided to build a simple servlet to return some odata block. I created Dynamic Web Project and used odata4j to return appropriate producer. But i met some problems that took me 3 days to serve.
In Java (as you probably know) is a standartized API named JPA, that describes a set of notations for ORM (Object-relation mapping). You configure your future mapping with a special file, named persistence.xml (and no other names should be used). All articles i looked through (well, may it was my mistake - i just looked through all manuals) told me to put this file in the /WebContent/META-INF directory. I did it and after deploying to my tomcat (integrated in eclipse) i got
root cause

java.lang.RuntimeException: javax.persistence.PersistenceException: No Persistence provider for EntityManager named TaskPersistanceUnitName
org.odata4j.producer.resources.ODataProducerProvider.newProducerFromFactory(ODataProducerProvider.java:65)
org.odata4j.producer.resources.ODataProducerProvider.getInstance(ODataProducerProvider.java:45)
org.odata4j.producer.resources.ODataProducerProvider.getInstance(ODataProducerProvider.java:15)
com.sun.jersey.core.impl.provider.xml.LazySingletonContextProvider.get(LazySingletonContextProvider.java:83)
com.sun.jersey.core.impl.provider.xml.LazySingletonContextProvider.access$000(LazySingletonContextProvider.java:55)
com.sun.jersey.core.impl.provider.xml.LazySingletonContextProvider$1.getValue(LazySingletonContextProvider.java:72)
com.sun.jersey.server.impl.inject.AbstractHttpContextInjectable$1.getValue(AbstractHttpContextInjectable.java:104)
com.sun.jersey.server.impl.inject.InjectableValuesProvider.getInjectableValues(InjectableValuesProvider.java:46)

I spent several days trying to figure out the reason of such behavior, and finally i read carefully http://javahowto.blogspot.com/2007/06/where-to-put-persistencexml-in-web-app.html
i created folder META-INF inside WebContent/WEB-INF/classes
and got it works

Friday, December 23, 2011

WCF and OData serialization

Even though Microsoft is one of the pioneers of OData protocol, in it's implementation for WCF (Data Services) they just "forgot" (you! bastards!) to implement json $format for it. I figured this couple hours ago while looking througn various options in protocol buffers for my future wcf-based odata service. Googling some time i found implementation for json format serialization http://professionalaspnet.com/archive/2010/06/17/The-query-parameter-_27002400_format_2700_-begins-with-a-system_2D00_reserved-_270024002700_-character-but-is-not-recognized.aspx great thanks to the author. Its pretty simple and readable, i'm going to try extend it to the protobuf engine.

Saturday, October 16, 2010

Un-recursive - part 1

I decided to write a cycle of posts about avoiding recursive calls in your algorythms. Recursion is the thing i hate to implement - it's hard to debug, it cost too much and so on. In this cycle i'm going to start with a common task - Tree Painting in depth - a task that could easyly solved with recursive calls - and show two ways to achieve the goal without recursive calls. After that i ll build parallels between this task and "common" recursive-solved task. Than i will implement quick sort and merge sort. Show/Hide

Tree Painting in Depth is a common task that could easyly be solved with recursive calls. Suppose we have a root node of a tree and a collection of children. Recursive method should paint root node and than calls itself for each child node. Pseudo-code for such method will look like Method(node root) { root.Paint(); for i = 1 to childern.Count { Method(children[i]); } } To avoid recursive calls in this algorythm we can use a stack of nodes to call Paint(). After painting a node we add its children at the beginning of the stack. Look at the implementation of this: We have a class Node

1:  class Node  
2:       {  
3:            public int Number { get; set; }  
4:            public Node[] Children { get; set; }  
5:            public void Paint()  
6:            {  
7:                 Console.WriteLine(Number + " was painted");  
8:            }  
9:       }

Property Number at line 3 is just a name for node and Children is a collection of child nodes. Class Painter will paint a tree, accepting a root node building a stack of nodes which expect to be be called:

1:       class Painter  
2:       {  
3:            public void PaintWithStack(Node root)  
4:            {  
5:                 List<Node> stack = new List<Node>();  
6:                 stack.Add(root);  
7:                 while (stack.Count > 0)  
8:                 {  
9:                      var node = stack[0];  
10:                      node.Paint();  
11:                      stack.RemoveAt(0);  
12:                      if (node.Children != null)  
13:                      {  
14:                           for (int i = node.Children.Length - 1; i >= 0; i--)  
15:                           {  
16:                                stack.Insert(0, node.Children[i]);  
17:                           }  
18:                      }  
19:                 }  
20:            }  
21:       }

A code to test algorytm is provided below. Lines 3-59 just instantiate a tree to paint. We call painter at line 61 to perform the task.

1:  static void Main(string[] args)  
2:            {  
3:                 var tree = new Node  
4:                 {  
5:                      Number = 1,  
6:                      Children = new[] {  
7:                           new Node  
8:                           {  
9:                                Number = 2,  
10:                                Children = new[] {  
11:                                     new Node  
12:                                     {  
13:                                          Number = 5,  
14:                                     },  
15:                                     new Node  
16:                                     {  
17:                                          Number = 6  
18:                                     }  
19:                                }  
20:                           },  
21:                           new Node  
22:                           {  
23:                                Number = 3,  
24:                                Children = new[] {  
25:                                     new Node  
26:                                     {  
27:                                          Number = 7  
28:                                     }  
29:                                }  
30:                           },  
31:                           new Node  
32:                           {  
33:                                Number = 4,  
34:                                Children = new [] {  
35:                                     new Node  
36:                                     {   
37:                                          Number = 8  
38:                                     },  
39:                                     new Node  
40:                                     {  
41:                                          Number = 9,  
42:                                          Children = new []{  
43:                                               new Node  
44:                                               {  
45:                                                    Number = 11  
46:                                               },  
47:                                               new Node  
48:                                               {  
49:                                                    Number = 12  
50:                                               }  
51:                                          }  
52:                                     },  
53:                                     new Node  
54:                                     {  
55:                                          Number = 10  
56:                                     }  
57:                                }  
58:                           }}  
59:                 };  
60:                 Painter p = new Painter();  
61:                 p.PaintWithStack(tree);  
62:                 Console.ReadKey();  
63:            }

Output of this code will

 1 was painted  
 2 was painted  
 5 was painted  
 6 was painted  
 3 was painted  
 7 was painted  
 4 was painted  
 8 was painted  
 9 was painted  
 11 was painted  
 12 was painted  
 10 was painted

which corresponds to the expected output.

Tuesday, September 21, 2010

Randomized Quick-sort

Quick-sort is another type of comparison sorting algorythm. It's much better than other comparing algorythms cause it doesn't require additional space for its work (unlike merge sort for example). It also has a good time of work in average case - O(n lgn) - that is best time for every comparing algorytm as you know. It's also has asymptotic n^2 time of work in worst case, that occurs rarely. Using randomization at the each step of algorytm helps to avoid receiving "pre-defined worst case", when our solution gives us worst time on a particular sequence. Here is an implementation of randomized qucik-sort: Show/Hide

1:  using System;  
2:  using System.Collections.Generic;  
3:  using System.Linq;  
4:  using System.Text;  
5:  namespace QuickSort  
6:  {  
7:       public class SortManager  
8:       {  
9:            public int[] Sort(int[] data)  
10:            {  
11:                 try  
12:                 {  
13:                      SortRange(data, 0, data.Length - 1);  
14:                 }  
15:                 catch (Exception ex)  
16:                 {  
17:                      int a = 1;  
18:                 }  
19:                 return data;  
20:            }  
21:            public void SortRange(int[] data, int startIndex, int endIndex)  
22:            {  
23:                 if (startIndex >= endIndex) return;  
24:                 int rangeLen = endIndex - startIndex + 1;  
25:                 Random rnd = new Random();  
26:                 int randomIndex = rnd.Next(rangeLen - 1) + startIndex;  
27:                 int val = data[randomIndex];  
28:                 data[randomIndex] = data[endIndex];  
29:                 data[endIndex] = val;  
30:                 int temp = 0;  
31:                 int j = startIndex;  
32:                 bool isRangeEqual = true;  
33:                 for (int i = startIndex; i <= endIndex; i++)  
34:                 {  
35:                      if (data[i] != val) isRangeEqual = false;  
36:                      if (data[i] < val)  
37:                      {  
38:                           temp = data[j];  
39:                           data[j] = data[i];  
40:                           data[i] = temp;  
41:                           j++;  
42:                      }  
43:                 }  
44:                 if (isRangeEqual) return;  
45:                 SortRange(data, startIndex, j - 1);  
46:                 SortRange(data, j, endIndex);  
47:            }  
48:       }  
49:  }

Lines 35 and 44 are a small cheat cause i can't understand how it should behaves when all items in the input are equal. I alse add some test to view how it works

1:  using System;  
2:  using System.Text;  
3:  using System.Collections.Generic;  
4:  using System.Linq;  
5:  using NUnit;  
6:  using NUnit.Framework;  
7:  using Karn.PerfomanceLibrary;  
8:  namespace QuickSort.Fixture  
9:  {  
10:       /// <summary>  
11:       /// Summary description for UnitTest1  
12:       /// </summary>  
13:       public class SortManagerTest  
14:       {  
15:            private Observer watches = new Observer();  
16:            public SortManagerTest()  
17:            {  
18:                 //  
19:                 // TODO: Add constructor logic here  
20:                 //  
21:            }  
22:            [Test]  
23:            public void SortCommonOrder()  
24:            {  
25:                 //  
26:                 // TODO: Add test logic     here  
27:                 //  
28:                 var manager = new SortManager();  
29:                 watches.Start("SortCommonOrder");  
30:                 var input = new[] { 9, 13, 2, 6, 19, 8, 24, 49, 3, 33, 27, 16, 11 };  
31:                 int[] data = manager.Sort(input);  
32:                 watches.Stop("SortCommonOrder");  
33:                 Assert.IsTrue(watches["SortCommonOrder"].ElapsedMilliseconds < 100);  
34:                 Assert.IsTrue(input.Length == data.Length);  
35:                 Assert.IsTrue(checkDataSorted(data));  
36:            }  
37:            [Test]  
38:            public void SortEqualOrder()  
39:            {  
40:                 var manager = new SortManager();  
41:                 watches.Start("SortEqualOrder");  
42:                 var input = new[] { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 };  
43:                 int[] data = manager.Sort(input);  
44:                 watches.Stop("SortEqualOrder");  
45:                 Assert.IsTrue(watches["SortEqualOrder"].ElapsedMilliseconds < 100);  
46:                 Assert.IsTrue(input.Length == data.Length);  
47:                 Assert.IsTrue(checkDataSorted(data));  
48:            }  
49:            [Test]  
50:            public void SortSorted()  
51:            {  
52:                 var manager = new SortManager();  
53:                 watches.Start("SortSorted");  
54:                 var input = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 };  
55:                 int[] data = manager.Sort(input);  
56:                 watches.Stop("SortSorted");  
57:                 Assert.IsTrue(watches["SortSorted"].ElapsedMilliseconds < 100);  
58:                 Assert.IsTrue(input.Length == data.Length);  
59:                 Assert.IsTrue(checkDataSorted(data));  
60:            }  
61:            [Test]  
62:            public void SortUnsorted()  
63:            {  
64:                 var manager = new SortManager();  
65:                 watches.Start("SortUnsorted");  
66:                 var input = new[] { 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };  
67:                 int[] data = manager.Sort(input);  
68:                 watches.Stop("SortUnsorted");  
69:                 Assert.IsTrue(watches["SortUnsorted"].ElapsedMilliseconds < 100);  
70:                 Assert.IsTrue(input.Length == data.Length);  
71:                 Assert.IsTrue(checkDataSorted(data));  
72:            }  
73:            bool checkDataSorted(int[] data)  
74:            {  
75:                 if (data.Length <= 1) return true;  
76:                 for (int i = 1; i < data.Length; i++)  
77:                 {  
78:                      if (data[i] < data[i - 1]) return false;  
79:                 }  
80:                 return true;  
81:            }  
82:       }  
83:  }

Wednesday, September 15, 2010

Count sort - yehhaaa!

Count sort is very good to sort sequence of integer which has small range of values (in comparison with sequence length). Due to two assumptions - our sequence contains only integers and its values range is much less than amount of items in sequence, it's linear in time to the amount of items in input. It's much better than classic algorythms based on comparison, cause it doesn't use comparison in its work, so it overcomes traditional for comparing algorythms O(nlogn). Here is an implementation: Show/Hide

 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 namespace CountSort  
 {  
     public class SortManager  
     {  
         public int[] Sort(int[] data)  
         {  
             int max = 0;  
             int min = 0;  
             // get min and max elements of input array to get borders of counting array  
             GetMaxMin(data, out min, out max);  
             // declare sorting array  
             int[] metaCount = new int[max + 1 - min];  
             // count amount of each item in iput  
             foreach (int d in data)  
             {  
                 metaCount[d - min]++;  
             }  
             // rebuild sorting array to get end position of each item in sorted output  
             for (int i = 1; i < metaCount.Length; i++)  
             {  
                 metaCount[i] += metaCount[i - 1];  
             }  
             int[] returnValue = new int[data.Length];  
             // just fill output array  
             int currentInsertPosition = 0;  
             for (int i = 0; i < metaCount.Length; i++)  
             {  
                 for (; currentInsertPosition < metaCount[i]; currentInsertPosition++)  
                 {  
                     returnValue[currentInsertPosition] = i + min;  
                 }  
             }  
             return returnValue;  
         }  
         void GetMaxMin(int[] data, out int min, out int max)  
         {  
             if (data.Length == 1)  
             {  
                 min = data[0];  
                 max = data[0];  
                 return;  
             }  
             decimal mediana = data.Length / 2;  
             int[] left = new int[(int)Math.Floor(mediana)];  
             int[] right = new int[data.Length - left.Length];  
             for (int i = 0; i < left.Length; i++)  
             {  
                 left[i] = data[i];  
             }  
             for (int i = 0; i < right.Length; i++)  
             {  
                 right[i] = data[i + left.Length];  
             }  
             int leftMin = 0;  
             int leftMax = 0;  
             int rightMin = 0;  
             int rightMax = 0;  
             GetMaxMin(left, out leftMin, out leftMax);  
             GetMaxMin(right, out rightMin, out rightMax);  
             min = leftMin < rightMin ? leftMin : rightMin;  
             max = leftMax > rightMax ? leftMax : rightMax;  
         }  
     }  
 }

and of course some test for you:

 using System;  
 using System.Collections.Generic;  
 using System.Linq;  
 using System.Text;  
 using NUnit;  
 using NUnit.Framework;  
 namespace CountSort.Fixture  
 {  
     public class SortManagerTest  
     {  
         [Test]  
         public void TestFromZero()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 1, 3, 0, 2, 1, 4, 3, 0, 2, 4, 2, 4, 3, 2, 1, 0 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         [Test]  
         public void TestFromLessZero()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 1, 3, 0, -1, 2, 1, 4, 3, 0, -1, -2 ,2, 4, 2, 4, -2, 3, -1, 2, 1, 0 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         [Test]  
         public void TestFromGreatZero()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 1, 3, 5, 1, 2, 1, 4, 3, 5, 11, 2, 2, 4, 2, 4, 2, 3, 1, 2, 1, 6 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         [Test]  
         public void TestWithSpaces()  
         {  
             SortManager manager = new SortManager();  
             int[] data = new[] { 3, 3, 1, 1, 3, 5, 3, 1, 5, 6, 3, 1 };  
             int[] sorted = manager.Sort(data);  
             checkSort(data, sorted);  
         }  
         void checkSort(int[] input, int[] output)  
         {  
             // check both arrays have equal amount of items  
             Assert.AreEqual(output.Length, input.Length);  
             // check for sort  
             for (int i = 1; i < output.Length; i++)  
             {  
                 Assert.IsTrue(output[i - 1] <= output[i]);  
             }  
             // check no new items in output  
             for (int i = 0; i < output.Length; i++)  
             {  
                 bool isInInput = false;  
                 foreach (int inp in input)  
                 {  
                     if (output[i] == inp)  
                     {  
                         isInInput = true;  
                         break;  
                     }  
                 }  
                 Assert.IsTrue(isInInput);  
             }  
             // check no items lost  
             for (int i = 0; i < input.Length; i++)  
             {  
                 bool isInOutput = false;  
                 foreach (int outp in output)  
                 {  
                     if (input[i] == outp)  
                     {  
                         isInOutput = true;  
                         break;  
                     }  
                 }  
                 Assert.IsTrue(isInOutput);  
             }  
             // check sum  
             int sumInput = 0;  
             for (int i = 0; i < input.Length; i++)  
             {  
                 sumInput += input[i];  
             }  
             int sumOutput = 0;  
             for (int i = 0; i < output.Length; i++)  
             {  
                 sumOutput += output[i];  
             }  
             Assert.AreEqual(sumInput, sumOutput);  
         }  
     }  
 }

Monday, September 13, 2010

Merge implementation with predicate

I study algorythms carefully during last two weeks and as you probably know, many algorythm tasks require implementation of sorting procedure. There is a huge amount of various sorting algorythms, such as Quick Sort, Heap Sort and so on. But one of the easiest to implement is a Merge Sort. You can find its description somewhere. I implemented it several times - for ascending sorting, for descending sorting and so on, so finally i take time to implement it with any predicate you like. Here is an implementation:

There is one class SortManager with method Sort, that calls itself recursively on input parts:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace MergePredicate { public class SortManager { public int[] Sort(int[] data, Func<int, int, bool> predicate) { if (data.Length <= 1) return data; decimal mediana = data.Length / 2; // left part of our input for first recursion call int[] leftPart = new int[(int)Math.Floor(mediana)]; // right part int[] rightPart = new int[data.Length - (int)Math.Floor(mediana)]; // fill left part with data for (int i = 0; i < leftPart.Length; i++) { leftPart[i] = data[i]; } // fill right part for (int i = leftPart.Length; i < data.Length; i++) { rightPart[i - leftPart.Length] = data[i]; } // sort both parts int[] leftSorted = Sort(leftPart, predicate); int[] rightSorted = Sort(rightPart, predicate); return MergeByPredicate(leftSorted, rightSorted, predicate); } /// <summary> /// Main procedure - merge both sorted arrays in one /// </summary> /// <param name="leftSorted"></param> /// <param name="rightSorted"></param> /// <param name="predicate"></param> /// <returns></returns> public int[] MergeByPredicate(int[] leftSorted, int[] rightSorted, Func<int, int, bool> predicate) { // returned merged array int[] data = new int[leftSorted.Length + rightSorted.Length]; // cursors over both parts int i = 0; int j = 0; while (i + j < data.Length) { // we are in the end of right part if (j == rightSorted.Length) { while (i < leftSorted.Length) { data[i + j] = leftSorted[i]; i++; } } // or in the end of left part if (i == leftSorted.Length) { if (j < rightSorted.Length) { data[i + j] = rightSorted[j]; j++; } } // left part of both conditions we need not to get out of the bound of data while (i < leftSorted.Length && predicate(leftSorted[i], rightSorted[j])) { data[i + j] = leftSorted[i]; i++; } while (j < rightSorted.Length && i < leftSorted.Length && predicate(rightSorted[j], leftSorted[i])) { data[i + j] = rightSorted[j]; j++; } } return data; } } }
I also added some tests if you want to see it's working. I use NUnit as Test Tool cause i have no Visual Studio Testing tool at home. Last note: be carefull about predicate to compare values. It should work as if predicate(a, b) == false then predicate(b, a) == true so dont pass predicate like (a, b) => a < b cause it won't pass condition if a = b (cause a < b == false and b < a == false) instead use (a, b) => a <= b The third test method provides a predicate to separate array on odd and non-odd numbers, for you to evaluate the power of predicate merge ;-) using System; using System.Collections.Generic; using System.Linq; using System.Text; using NUnit; using NUnit.Framework; using MergePredicate; namespace MergePredicate.Fixture { public class MergePredicateTest { [Test] public void TestDescendingSort() { SortManager manager = new SortManager(); var data = new [] { 3, 12, 6, 9, 43, 1, 33, 23, 12, 38, 7, 19 }; Func<int, int, bool> predicate = (a, b) => a <= b; var output = manager.Sort(data, predicate); checkSorting(data, output, predicate); } [Test] public void TestAscendingSort() { SortManager manager = new SortManager(); var data = new[] { 3, 12, 6, 9, 43, 1, 33, 23, 12, 38, 7, 19 }; Func<int, int, bool> predicate = (a, b) => a >= b; var output = manager.Sort(data, predicate); checkSorting(data, output, predicate); } [Test] public void TestOddnessSort() { SortManager manager = new SortManager(); var data = new[] { 3, 12, 6, 9, 43, 1, 33, 23, 12, 38, 7, 19 }; Func<int, int, bool> predicate = (a, b) => { if (a % 2 != 0 && b % 2 == 0) return false; return true; }; var output = manager.Sort(data, predicate); checkSorting(data, output, predicate); } void checkSorting(int[] data, int[] sortedData, Func<int, int, bool> predicate) { Assert.AreEqual(data.Length, sortedData.Length); if (sortedData.Length > 1) { for (int i = 1; i < sortedData.Length; i++) { Assert.IsTrue(predicate(sortedData[i - 1], sortedData[i])); } } foreach (int sorted in sortedData) { bool sortedIsInInitial = false; foreach (int initial in data) { if (sorted == initial) { sortedIsInInitial = true; break; } } Assert.IsTrue(sortedIsInInitial); } } } }

Hi there!