Merging 2 word 2007(open xml) documents

I had to merge 2 word documents once.

They were both in word 2007(open xml) format.

I searched online everywhere for a way to merge them.

All the links were about using the altChunk element. I have a problem with that. The entire document gets put in there and that is a lot of unneeded data(like header and footer etc.).

So I did it another way:

1. cloned the second document's body

2. cloned all it's children and added them to the first document's main part

	static void MergeDocs(string doc1Path,string doc2Path)
	{
	using (var doc2FileStream = File.Open(doc2Path, FileMode.Open))
	{
	using (WordprocessingDocument doc2 = WordprocessingDocument.Open(doc2FileStream, true))
	{
	var doc2Body = (Body)doc2.MainDocumentPart.Document.Body.CloneNode(true);
	using (var doc1FileStream = File.Open(doc1Path, FileMode.Open))
	{
	using (WordprocessingDocument doc1 = WordprocessingDocument.Open(doc1FileStream, true))
	{
	var mainPart = doc1.MainDocumentPart;
	foreach (var elem in doc2Body.ChildElements)
	{
	if (!(elem is SectionProperties))
	mainPart.Document
	.Body
	.InsertAfter(elem.CloneNode(true), mainPart.Document.Body.Elements<paragraph>().Last());
	}
	mainPart.Document.Save();
	}
	}
	}
	}
	}

view raw MergeDocs hosted with ❤ by GitHub

Radix tree implementation in C#

Update: you can find the entire source code here 

This is my implementation of a radix tree data structure. This is a data structure very similar to a trie. Basically instead of having each one of your nodes hold a char you have each one of your nodes store a string or as wikipedia puts it, it is a trie where "each node with only one child is merged with its child".

As I understand it the names radix tree and crit bit tree are only applied to trees storing integers and Patricia trie is retained for more general inputs.

As usual I am outputting the code for each class.

First, the node:

	/// <summary>
	/// represents a node in the radix tree
	/// stores:
	/// a label - string that the tree holds
	/// a list of the node's subnodes - a list of other objects of this type
	/// </summary>
	public class Node
	{
	public Node()
	{
	Label = "";
	SubNodes = new List<Node>();
	}
	public Node(string l)
	{
	Label = l;
	SubNodes = new List<Node>();
	}
	public string Label;
	public List<Node> SubNodes;
	}

view raw C# radix tree node hosted with ❤ by GitHub

Then the actual tree

	public class Tree
	{
	/// <summary>
	/// store the tree's root
	/// </summary>
	private Node _root;
	/// <summary>
	/// construct a new tree with it's root
	/// </summary>
	public Tree()
	{
	_root = new Node("");
	}
	/// <summary>
	/// insert a word into the tree
	/// </summary>
	/// <param name="word"></param>
	public void Insert(string word)
	{
	InsertRec(word, _root);
	}
	/// <summary>
	/// recursively traverse the tree
	/// carry the word you want inserted until a proper place for it is found and it can be inserted there
	/// if a node already stores a substring of the word(substrnig with the same first letter as the word itself)
	/// then that substring must be removed from the word and it's children checked out next
	/// hence the name wordPart - part of a word
	/// </summary>
	/// <param name="wordPart">the part of the word that is to be inserted that is not already included in any of the tree's nodes</param>
	/// <param name="curNode">the node currently traversed</param>
	private void InsertRec(string wordPart, Node curNode)
	{
	//get the number of characters that the word part that is to be inserted and the current node's label have
	//in common starting from the first position of both strings
	//matching characters in the two strings = have the same value at the same position in both strings
	var matches = MatchingConsecutiveCharacters(wordPart, curNode);
	//if we are at the root node
	//OR
	//the number of characters from the two strings that match is
	//bigger than 0
	//smaller than the the part of the word that is to be inserted
	//bigger than the the label of the current node
	if ((matches == 0) || (curNode == _root) ||
	((matches > 0) && (matches < wordPart.Length) && (matches >= curNode.Label.Length)))
	{
	//remove the current node's label from the word part
	bool inserted = false;
	var newWordPart = wordPart.Substring(matches, wordPart.Length - matches);
	//search the node's subnodes and if the subnode label's first character matches
	//the word part's first character then insert the word part after this node(call the
	//current method recursively)
	foreach(var child in curNode.SubNodes)
	if (child.Label.StartsWith(newWordPart[0].ToString()))
	{
	inserted = true;
	InsertRec(newWordPart, child);
	}
	if (inserted == false)
	{
	curNode.SubNodes.Add(new Node(newWordPart));
	}
	}
	else if(matches < wordPart.Length)
	{
	//in this case we have to nodes that we must add to the tree
	//one is the node that has a label extracted from the current node's label without the string of
	//matching characters(common characters)
	//the other is the node that has it's label extracted from the current word part minus the string
	//of matching characters
	string commonRoot = wordPart.Substring(0, matches);
	string branchPreviousLabel = curNode.Label.Substring(matches, curNode.Label.Length - matches);
	string branchNewLabel = wordPart.Substring(matches, wordPart.Length - matches);
	curNode.Label = commonRoot;
	var newNodePreviousLabel = new Node(branchPreviousLabel);
	newNodePreviousLabel.SubNodes.AddRange(curNode.SubNodes);
	curNode.SubNodes.Clear();
	curNode.SubNodes.Add(newNodePreviousLabel);
	var newNodeNewLabel = new Node(branchNewLabel);
	curNode.SubNodes.Add(newNodeNewLabel);
	}
	else if (matches == curNode.Label.Length)
	{
	//in this case we don't do anything because the word is already added
	}
	else if (matches > curNode.Label.Length)
	{
	//add the current word part minus the common characters after the current node
	string newNodeLabel = curNode.Label.Substring(curNode.Label.Length, wordPart.Length);
	var newNode = new Node(newNodeLabel);
	curNode.SubNodes.Add(newNode);
	}
	}
	/// <summary>
	/// given a string and a node the number of characters that the string and the node's label have
	/// in common starting from the first character in each is returned
	/// </summary>
	/// <param name="word">a string that is to be compared with the node's label</param>
	/// <param name="curNode">a node</param>
	/// <returns></returns>
	private int MatchingConsecutiveCharacters(string word, Node curNode)
	{
	int matches = 0;
	int minLength = 0;
	//see which string is smaller and save it's lenght
	//when cycling throught the two strings we won't go any further than that
	if (curNode.Label.Length >= word.Length)
	minLength = word.Length;
	else if (curNode.Label.Length < word.Length)
	minLength = curNode.Label.Length;
	if(minLength > 0)
	//go throught the two streams
	for (int i = 0; i < minLength; i++)
	{
	//if two characters at the same position have the same value we have one more match
	if(word[i] == curNode.Label[i])
	matches++;
	else
	//if at any position the two strings have different characters break the cycle
	break;
	}
	//and return the current number of matches
	return matches;
	}
	public bool Lookup(string word)
	{
	return LookupRec(word, _root);
	}
	/// <summary>
	/// look for a word in the tree begining at the current node
	/// </summary>
	/// <param name="wordPart"></param>
	/// <param name="curNode"></param>
	/// <returns></returns>
	private bool LookupRec(string wordPart, Node curNode)
	{
	var matches = MatchingConsecutiveCharacters(wordPart, curNode);
	if ((matches == 0) || (curNode == _root) ||
	((matches > 0) && (matches < wordPart.Length) && (matches >= curNode.Label.Length)))
	{
	var newLabel = wordPart.Substring(matches, wordPart.Length - matches);
	foreach (var child in curNode.SubNodes)
	if (child.Label.StartsWith(newLabel[0].ToString()))
	return LookupRec(newLabel, child);
	return false;
	}
	else if (matches == curNode.Label.Length)
	{
	return true;
	}
	else return false;
	}
	//Find successor: Locates the smallest string greater than a given string, by lexicographic order.
	public string FindSuccessor(string word)
	{
	return FindSuccessorRec(word, _root,string.Empty);
	}
	private string FindSuccessorRec(string wordPart, Node curNode,string carry)
	{
	var matches = MatchingConsecutiveCharacters(wordPart, curNode);
	if ((matches == 0) || (curNode == _root) ||
	((matches > 0) && (matches < wordPart.Length) ))
	{
	var newLabel = wordPart.Substring(matches, wordPart.Length - matches);
	foreach (var child in curNode.SubNodes)
	if (child.Label.StartsWith(newLabel[0].ToString()))
	return FindSuccessorRec(newLabel, child, carry + curNode.Label);
	return curNode.Label;
	}
	else if (matches < curNode.Label.Length)
	{
	return carry + curNode.Label;
	}
	else if (matches == curNode.Label.Length)
	{
	carry = carry + curNode.Label;
	int min = int.MaxValue;
	int index = -1;
	for (int i = 0; i < curNode.SubNodes.Count;i++ )
	if (curNode.SubNodes[i].Label.Length < min)
	{
	min = curNode.SubNodes[i].Label.Length;
	index = i;
	}
	if (index > -1)
	return carry + curNode.SubNodes[index].Label;
	else
	return carry;
	}
	else return string.Empty;
	}
	/// <summary>
	///Find predecessor: Locates the largest string less than a given string, by lexicographic order.
	/// </summary>
	/// <param name="?"></param>
	/// <returns></returns>
	public string FindPredecessor(string word)
	{
	return FindPredecessorRec(word, _root,string.Empty);
	}
	/// <summary>
	/// </summary>
	/// <param name="wordPart"></param>
	/// <param name="curNode"></param>
	/// <returns></returns>
	private string FindPredecessorRec(string wordPart, Node curNode,string carry)
	{
	var matches = MatchingConsecutiveCharacters(wordPart, curNode);
	if ((matches == 0) || (curNode == _root) ||
	((matches > 0) && (matches < wordPart.Length) && (matches >= curNode.Label.Length)))
	{
	var newLabel = wordPart.Substring(matches, wordPart.Length - matches);
	foreach (var child in curNode.SubNodes)
	if (child.Label.StartsWith(newLabel[0].ToString()))
	return FindPredecessorRec(newLabel, child, carry + curNode.Label);
	return carry + curNode.Label;
	}
	else if (matches == curNode.Label.Length)
	{
	return carry + curNode.Label;
	}
	else return string.Empty;
	}
	/// <summary>
	/// Delete: Delete a string from the tree. First, we delete the corresponding leaf.
	/// Then, if its parent only has one child remaining, we delete the parent and merge the two incident edges.
	/// </summary>
	/// <param name="label"></param>
	public void Delete(string label)
	{
	DeleteRec(label, _root);
	}
	/// <summary>
	/// delete a word from the tree means delete the last leaf that makes up the stored word
	/// </summary>
	/// <param name="label"></param>
	/// <param name="curNode"></param>
	public void DeleteRec(string wordPart, Node curNode)
	{
	var matches = MatchingConsecutiveCharacters(wordPart, curNode);
	if ((matches == 0) || (curNode == _root) ||
	((matches > 0) && (matches < wordPart.Length) && (matches >= curNode.Label.Length)))
	{
	var newLabel = wordPart.Substring(matches, wordPart.Length - matches);
	foreach (var child in curNode.SubNodes)
	if (child.Label.StartsWith(newLabel[0].ToString()))
	{
	if (newLabel == child.Label)
	{
	if (child.SubNodes.Count == 0)
	{
	curNode.SubNodes.Remove(child);
	return;
	}
	}
	DeleteRec(newLabel, child);
	}
	}
	}
	}

view raw C# radix tree hosted with ❤ by GitHub

And the test program:

	var tree = new Tree();
	tree.Insert("romane");
	tree.Insert("romanus");
	tree.Insert("romulus");
	tree.Insert("rubens");
	tree.Insert("ruber");
	tree.Insert("rubicon");
	tree.Insert("rubicundus");
	Console.WriteLine("predecessor of the word \"romanes\":" + tree.FindPredecessor("romanes"));
	Console.WriteLine("successor of the word \"rom\":" + tree.FindSuccessor("rom"));
	Console.WriteLine(tree.Lookup("romulus") ? "there" : "not there");
	tree.Delete("romanus");

view raw C# radix tree test hosted with ❤ by GitHub

PHP sitemap using a tree data structure

I was once asked to create a sitemap given a specific table structure.

This was the structure(the table):

The resulting sitemap as I understood it was supposed to look something like this:

The parenthesis after the titles actually hold the value of the id of the node so they weren't in the original design but whatever.

So I implemented this in PHP using a tree data structure where each node held 3 pieces of information:

id - the current node's id as read from the database

parent_id - the current node's parent id as read from the database

title - the title

A real-world implementation would also have to include a link and print out elements but this is good enough for educational purposes.

Each node also holds an array of subnodes.

This is the database information read to create the tree:

CREATE TABLE IF NOT EXISTS `sitepages` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`id_parent` int(11) unsigned NOT NULL,
`title` varchar(100) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=3 ;

INSERT INTO `sitepages` (`id`, `id_parent`, `title`) VALUES
(1, 0, 'Home'),
(2, 1, 'Page 1'),
(3, 0, 'Page 2'),
(4, 1, 'Page 3'),
(5, 3, 'Page 4'),
(6, 1, 'Page 5'),
(7, 4, 'Page 6'),
(8, 7, 'Page 7'),
(9, 5, 'Page 8');

I used to php classes to represent the tree. One to represent a node of the tree and one for the tree itself:

This is for the node:

//a node of a tree that is not binary, each nodes has multiple subnodes 
class Node 
{  
public $id;  
public $id_parent;  
public $childnodes;  
public $title;    

public function __construct($id,$id_parent,$title)  
{   
//in the test script I use mysql_fetch_object which populates the members and then //calls the constuctor with all    
//parameters as null   
//the following checks are here to make sure no members are accidentally overriden
      
if(!isset($this--->id))
  $this->id = $id;

 if(!isset($this->id_parent))  
  $this->id_parent = $id_parent;

 if(!isset($this->title))  
  $this->title = $title;

 if(!isset($this->childnodes))  
  $this->childnodes = array();
}

//check if this node has subnodes or not
public function hasChildren()
{
 if($this->childnodes === null)
  return false;

 if(!isset($this->childnodes))  
  return false;

 if(count($this->childnodes) == 0)
  return false;

 return true;
}
}

This is the tree:

require("node.class.php");  
class Tree 
{  

private $root;   

//construct a tree with only one root node  public function __construct()  
{   
$this->root = new Node(0,0);
}

//recursively traverse the tree looking for the appropiate parent id
//the node to be inserted($node) must have a parent id equal to one of the ids in the nodes of the tree
//if such an id is found in a node the node is included as a subnode of that node
private function addNodeRecursive(&$nextnode,$node)
{
 if($nextnode == null)
  return false;
 
 if($nextnode->id == $node->id_parent)
 {
  array_push($nextnode->childnodes,$node);
  return true;
 }
 else
 {
  if($nextnode->hasChildren())
  {
   foreach ($nextnode->childnodes as $childnode)
   {
    $this->addNodeRecursive($childnode,$node);
   }
   return false;
  }
  else
   return false;
 }
}

//add a node to the tree
//check if it is a valid node start at the root and recursively traverse the tree looking for the appropiate parent id
public function addNode($node)
{
 if(!($node instanceof Node))
  return;

 $nextnode = $this->root;

 $this->addNodeRecursive($nextnode,$node);
}

//print the tree in sitemap style
public function printSiteMap()
{
 foreach($this->root->childnodes as $childnode)
 {
  $this->printTree($childnode,0);
 }
}

//print the tree recursively
//first print the current node's value and then print the cycle through it's subnodes
public function printTree(&$nextnode,$level)
{
 $this->printNodeAccordingToLevel($nextnode,$level);

 if($nextnode->hasChildren())
 {
  foreach($nextnode->childnodes as $childnode)
  {
   $this->printTree($childnode,$level+1);
  }
 }
}

//add the appropiate number of   before each node value so as to obtain a nicely formatted sitemap
//each node value is indented with respect to the node's level
private function printNodeAccordingToLevel($node,$level)
{
 for($i=0;$i<$level;$i++)    echo " ";    echo $node->title."(".$node->id.")";
 
 echo "
";
}

}

And this is a test just to make sure everything works:

require("tree.class.php");  
$tree = new Tree();  
if(!($conn = mysql_connect("localhost","root",""))) 
{  
echo "Could not connect";  
exit; 
}  
if(!mysql_selectdb("sitemap")) 
{  
echo "No such database";  
exit; 
}  
if($result = mysql_query("SELECT id,id_parent,title FROM sitepages")) 
{  
while ($page = mysql_fetch_object($result,'Node'))   
$tree->addNode($page);
}

$tree->printSiteMap();

Prefix tree(trie) implementation in F#

Update: all the code can be downloaded from here

This is my implementation of a a prefix tree data structure in F#.
This structure is described in more detail in a previous post of mine.
I just describe the F# related stuff in the comments.
I'm sure this is not the best implementation. I am aware this is not the most functional implementation ever.
I am open to all constructive criticism of course.

	open System.Collections.Generic;
	//the trie node type which is stores a char, a bool to mark the end of the node and a list of all it's subnodes
	type TrieNode = TrieNode of (char * bool * TrieNode list) with
	//just a getter the char stored
	member this.Char = match this with TrieNode(c,weh,subnodes) -> c
	//get the first node that is a subnode of the current node and stores the char passed as parameter (c)
	//this returns a list which can be either empty or have one element this is probably not the best option since there will never be
	//more than one element in the list but I am new to F#
	member this.GetChild(c:char) = match this with TrieNode(c,weh,subnodes) -> match List.tryFind (fun (this:TrieNode) -> this.Char = c) subnodes with
	| Some value -> [value]
	| None -> []
	//just return true if a word ends here
	member this.AWordEndsHere = match this with TrieNode(_,weh,_) -> weh
	//just a getter for the the subnodes
	member this.Subnodes = match this with TrieNode(_,_,subnodes) -> subnodes
	//type members cannot be recursive so I implemented this in a module
	//a more functional approach was to implement all methods here I guess ... anyways ...
	module TrieFunctions =
	//this inserts a word passed as a char list
	let rec insertWord (wordChars:char list) = function
	| TrieNode(c, weh, subnodes) as node ->
	if(wordChars.Length > 0) then
	//get the first char in the word and see if there are any child nodes storing that char
	let child = node.GetChild(wordChars.Head)
	if child = [] then
	//if there aren't insert this node and make a new node to pass to the insertion function
	let newnode = TrieNode(wordChars.Head,false,[])
	TrieNode(c,weh,(insertWord wordChars.Tail newnode)::subnodes )
	else
	//otherwise the node that has to be passed to the insertion function is the child node as all other nodes will be
	//added after it and the first char in the word will be added
	TrieNode(wordChars.Head,false,(insertWord wordChars.Tail child.Head)::subnodes )
	else
	//there are no more characters in the word so we must add a node with no subnodes and mark it as a valid end of a word
	TrieNode(c,true,[])
	//turn a string into a char list - ofSeq turns any sequence into a list of it's composing elements
	//and a string is made up of chars
	let stringToCharList(s:string) = List.ofSeq s
	//print the trie - use an accumulator(acc)
	let rec print acc = function
	//if there are no subnodes
	| TrieNode(c, weh, []) ->
	//add the current char node to the accumulator, print if it the end of a word and return unit
	let str = acc + c.ToString()
	if weh then printfn "%s" str
	()
	| TrieNode(c, weh, subnodes) ->
	//add the current char node to the accumulator, print if it the end of a word
	let str = acc + (if c.Equals(' ') then "" else c.ToString())
	if weh then printfn "%s" str
	//iterate through the list of subnodes and call print function for each of them
	List.iter (fun (node : TrieNode) -> print str node) subnodes
	//unlike in C# in F# the type has a default constructor containing the maximum number of parameters
	type Trie(inner : TrieNode) =
	member this.InsertWord(wordChars:char list) = Trie(TrieFunctions.insertWord wordChars inner)
	member this.InsertWord(str:string) = Trie(TrieFunctions.insertWord (TrieFunctions.stringToCharList str) inner)
	member this.Root() = inner
	//and an empty constructor must be declared if you want to have it
	new() = Trie(TrieNode(' ',false,List.empty))
	let trie = Trie()
	.InsertWord("abc")
	.InsertWord("abcd")
	.InsertWord("abcd")
	.InsertWord("abcde")
	.InsertWord("abcdef")
	.InsertWord("ab123cd")
	.InsertWord("abc123d")
	.InsertWord("abc132d")
	TrieFunctions.print "" (trie.Root())

view raw PrefixTreeF# hosted with ❤ by GitHub

Autocomplete functionality using prefix trees

Update: all the source code for this article can be accessed from here

This is a follow up to my previous post on implementing a prefix tree in C#.

This expands on that idea and uses the data structure to generate a list of autocomplete matches for a given input character sequence.

These are the modifications I brought to the code:

	private List<string> subsequentStrings;
	/// <summary>
	/// Create a prefix tree - the root node should always store ' '
	/// Initializae the list that will store the strings
	/// found during the autocomplete process
	/// </summary>
	public Tree()
	{
	_root = new Node(' ');
	subsequentStrings = new List<string>();
	}

view raw Prefix tree autocomplete functionality part 1 hosted with ❤ by GitHub

	/// <summary>
	/// get the autocomplete matches given the input
	/// </summary>
	/// <param name="query">the input</param>
	/// <returns>the list of autocomplete matches</returns>
	public List<string> GetMatches(string query)
	{
	StringBuilder sbPrevious = new StringBuilder();
	char[] chars = query.ToCharArray();
	Node currentNode = _root;
	Node child = null;
	for (int counter = 0; counter < chars.Length; counter++)
	{
	//form the sequence before the current char
	if(counter < chars.Length - 1)
	sbPrevious.Append(chars[counter]);
	child = currentNode.GetChild(chars[counter]);
	if (child == null)
	break;
	currentNode = child;
	}
	//clear the subsequent string storage
	subsequentStrings.Clear();
	GenerateSubsequentStrings(currentNode, sbPrevious.ToString());
	return subsequentStrings;
	}
	/// <summary>
	/// given a node and the current string generate the autocomplete matches recursively
	/// </summary>
	/// <param name="node">the current node</param>
	/// <param name="subsequentString">the current sequence</param>
	private void GenerateSubsequentStrings( Node node,
	string subsequentString)
	{
	//if there are no more nodes stop the recursion
	if(node == null)
	return;
	//add the current char to the current sequence
	subsequentString = subsequentString + node.Char;
	//if a word ends here add the current sequence to the autocomplete list
	if(node.AWordEndsHere)
	subsequentStrings.Add(subsequentString);
	//foreach child call the method recursively
	foreach (var subnode in node.Subtree)
	GenerateSubsequentStrings(subnode, subsequentString);
	}

view raw autocomplete prefix trees gist 2 hosted with ❤ by GitHub

This is the main program:

	Tree prefixTree = new Tree();
	prefixTree.AddWord("abc");
	prefixTree.AddWord("abcd");
	prefixTree.AddWord("abcde");
	prefixTree.AddWord("abcdef");
	prefixTree.AddWord("ab123cd");
	prefixTree.AddWord("abc123d");
	prefixTree.AddWord("abc132d");
	string word = "abc";
	if (prefixTree.Find(word))
	{
	var matches = prefixTree.GetMatches("abc");
	Console.WriteLine("gasit");
	Console.WriteLine("Autocomplete:");
	if (matches.Count > 0)
	foreach (var m in matches)
	Console.WriteLine(m);

view raw Prefix Tree Autocomplete Gist 3 hosted with ❤ by GitHub

Implementation of the prefix tree(trie) data structure in C#

Update: all the source code for this article can be accessed from here

A prefix tree is a data structure with many uses. I won't go into details about this data structure Wikipedia does a better job than I could. What I will do is post a C# implementation of this data structure and in a following post I will show how to use this data structure when implementing an auto-complete solution.

These are the properties of a prefix tree:

• it stores strings(finite sequences of chars)
• it had nodes :) (doooooooh!)
• each node stores a character
• each node can have a number of subnodes(0,1,2, ... infinity)
• the char stored in a subnode is the one following the char stored by the node in a string
• each node has a flag which is raised if a word ends there(this doesn't mean it can't have subnodes for example a prefix tree can store the words "cat" and "catastrophy" in this case node 3 stores 't' and has a subnode that stores 'a')

And now the code:

The node:

namespace PrefixTree
{
 /// 

 /// this is the class that represents a node in the prefix tree
 /// the tree stores:
 /// 1. a char
 /// 2. references to it's subnodes
 /// 3. a flag which is raised if any word ends with the char stored in this node
 /// 
 class Node
 {

     /// 

     /// char stored by the node
     /// 
     public char Char;
     /// 

     /// references to it's subnodes
     /// 
     public List Subtree;
     /// 

     /// the flag which is raised if any word ends with the char stored in this node
     /// 
     public bool AWordEndsHere;

     /// 

     /// constructor
     /// 
     /// 

     public Node(char c)
     {
         Char = c;
         Subtree = new List();
     }
     /// 

     /// gets a reference to this node's subnode that stores the specified char
     /// 
     /// 
the specified char
     /// reference to the subnode that stores the specified char
     public Node GetChild(char c)
     {
         if (Subtree.Count != 0)
             foreach (var node in Subtree)
                 if (node.Char == c)
                     return node;
         return null;
     }
 }
}

The tree:

namespace PrefixTree
{

   /// 

   /// this is the main prefix tree class
   /// 
   class Tree
   {
       private List subsequentStrings;

       private Node _root;
       public Node Root
       {
           get
           {
               return _root;
           }
       }

       /// 

       /// Create a prefix tree - the root node should always store ' '
       /// 
       public Tree()
       {
           _root = new Node(' ');
       }

       /// 

       /// Add a word(series of characters) into the prefix tree
       /// 
       /// 

       public void AddWord(string word)
       {
           char[] chars = word.ToCharArray();
           Node currentNode = _root;
           Node child = null;
           //cycle through the chars in the string
           for (int counter = 0; counter < child =" currentNode.GetChild(word[counter]);" child ="="" newnode =" new" currentnode =" newNode;" currentnode =" child;" counter ="="" awordendshere =" true;">
       /// return wether a string can be found in the tree
       /// 
       /// 
a string
       /// true or false
       public bool Find(string query)
       {
           char[] chars = query.ToCharArray();
           Node currentNode = _root;
           Node child = null;
           //search throughout the child nodes of the current node for the current char
           for (int counter = 0; counter < child =" currentNode.GetChild(chars[counter]);" child ="="" currentnode =" child;">

The main program:

Tree prefixTree = new Tree();
          
prefixTree.AddWord("abc");
prefixTree.AddWord("abcd");
prefixTree.AddWord("abcde");
prefixTree.AddWord("abcdef");
prefixTree.AddWord("ab123cd");
prefixTree.AddWord("abc123d");
prefixTree.AddWord("abc132d");
          
string word = "abc";


if (prefixTree.Find(word))
Console.WriteLine("found");
else
Console.WriteLine("not found");

How to concatenate data from multiple rows into a single rows

I had a problem once. One table had a lot of data in a column on multiple rows. I had to display it in a view but I needed all the data on that column to be displayed in a single cell on a row. This view was supposed to be the data source for a report ... long story ...

Anyway, the basic idea is this:

SELECT some_column = (your select query
 for xml path(''))

this only works in sql server 2008 because earlier versions don't have the "xml" keyword.

Here is an example:

SELECT Documente = (SELECT coalesce(td.Descriere+',','') as [text()] FROM Document d 
   INNER JOIN TipDocument td ON d.TipDocumentId = td.Id  for xml path(''))

Unable to start debugging on the web server error

Just in case you also received this error:

Unable to start debugging on the web server. Debugging failed because
integrated Windows authentication is not enabled. Please see Help for
assistance

Here is what I did to not get it any more

1. Open IIS Manager (Internbet Information Services)
2. Right-click the web site (in case you run it locally you only have
   Default web site) and pick Properties
3. Choose "Directory Security" tab and click Edit on "Anonymous access and
   authentication control"
4. In the opening window, uncheck "Allow Anonymous access" and check
   "Integrated Windows Authentication"

Finding the path to an installed application in C#

Well, you can find the path to a locally installed application by querying the windows registry.

The information is here:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\App Paths\

Example photoshop.exe

I wrote this function in C# to do this for me:

/// 

        /// get the path to a specific application from the registry 
        /// 
        /// name of the application exe
        /// 
        public static string GetApplicationPath(string ExeName)
        {
            try
            {
                RegistryKey OurKey = Registry.LocalMachine;
                OurKey = OurKey.OpenSubKey(@"Software\Microsoft\Windows\CurrentVersion\App Paths\"+ExeName, true);
                if (OurKey != null)
                    return OurKey.GetValue("").ToString();
                else
                    return "";
            }
            catch(Exception ex)
            {
                return "";
            }
        }

Exporting MS SQL data as sql scripts

In PhpMyAdmin exporting data to sql statements not to .mdb files or other databases is very straight forward. When I first had to do this with Sql Management Studio I didn't know how at first.

Then I found out.

Basically, what you have to do is this:

1.right click on a database item

2.go to tasks -> generate scripts in the menu that appears

You now have a wizard that will help you generate scripts for the objects you need. You can either generate one script for all the objects in your database(tables, triggers, stored procedures etc) or one script for just some of the object(you choose which) or each object you choose in it's own script. You can either generate these resulting scripts in files or in new query windows. Everything is configurable from the options window(the wizard step with the title "Choose script options").

Here is an example:

I wanted to just script the triggers in a db. Each in it's own file.

In the options window I set "script triggers" to true and in the following wizard form(with the title "Output options") I chose "file per object".

Reseting visual studio

Visual Studio needs to be reset(in order to change a setting) / is frozen / doesn’t work right

1. Close all instances of VS

2. Click Start > Run...

3. Type "devenv /resetuserdata"

4. Open task manager and wait until devenv.exe process is finished executing

5. Restart VS2005

In Win 7:

search for the folder in which devenv.exe can be found

follow the steps above but instead of typing “devenv /resetuserdata” type “devenv.exe /resetuserdata”

Finding the first non consecutive value in an identity column

This is an interesting SQL problem that presented itself to me once.

You have this table. It has of course a primary key which is an identity column which has a seed of 1.

Then you insert a some data and then delete some data.

The primary key column(let's call it id from now on) will no longer contain only consecutive numbers.

So the question is: "How do you find the first non consecutive value in this column?"

Well, the first thing that came to my mind at the time was making a cursor. That works too but it's not very efficient.

Here is one implementation using a self join which worked for me:

select top 1 t1.id from [table] t1 left join [table] t2 on t1.id+1 = t2.id where t2.id is NULL

Opening compressed databases or .mdf files in SQL Server Management Studio

If when you try to open a database or attaching a .mdf file you get the error:

is compressed but does not reside in a read-only database or filegroup. The file must be decompressed.

So here is the algorithm I followed to solve this issue:

1. only if an existing database gives this error detach the database – right click -> Detach

2. closed all SQL Server Management Studio instances

3. Stop the SQL Server service.. (Start->Run -> services.msc)

4. Selected .mdf file(should be blue if compressed ) Right click properties -> Advanced -> Uncheck "Compress files to save disk space"

5.(re)attach .mdf file

Setting the week's start day in MS SQL

SET DATEFIRST 1 --start day is Monday

SET DATEFIRST 7 --start day is Sunday – default

To test it PRINT @@DATEFIRST

Making ASP.NET write to a file

Select the file right click->”Properties”->click the”Security” Tab->click the “Add” tab->write YOURCOMPUTERNAME/ASPNET replacting YOURCOMPUTERNAME with your computer’s name->check the “full control” checkbox below-> click “OK”

When calling the file from the code write with two “\” where one is found in the path for example c:\\q.xml.

"Converting" an XmlNode to and XmlDocument in C#

private void Output(XmlNode xnodeOutput,bool bOutputToFile)
   {
       try
       {
         
           XmlDocument xdocOutput = new XmlDocument();

           XmlNode xnodeTemp = xdocOutput.ImportNode(xnodeOutput, true);

           XmlElement xWC = xdocOutput.CreateElement("whatever");

           xdocOutput.AppendChild(xnodeTemp);

The first element will never by shown anyway(assuming you do xdocOutput.Save(afile.xml)) so it can have any name.

Encode Sensitive parameters ASP.NET

Use:

Convert.ToBase64String(System.Text.Encoding.Unicode.GetBytes(

To Encode

System.Text.Encoding.Unicode.GetString(Convert.FromBase64String(

To decode

This should work for both GET and POST

Query string delimiters

Don’t use:

“#”

Use:

Anything else

Reason:

Browsers interpret # as end of string

Don’t take my word for it test it in the address bar http://www.google.com#www.microsoft.com

display/hide divs

To display/hide runat="server" divs in asp.net

Don’t use:

Divid.visible = true/false

Use:

Divid.attributes[“style”] = “display:none”/ “display:block”

Reason:

You won’t have javascript access to those divs

C# implementation of the parallel sieve of Erathostenes

Update: all the source code for this article can be downloaded from here

This is my implementation of a parallel sieve of Erathostenes in C#.

I got the algorithm from here.

I know I could have used some of the existing C# functionality to manage threads rather than doing it all myself but I found this more convenient at the time.

Anyone is welcomed to bring any corrections.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace ParalelErathostenes
{
    /// 

    /// Finds prime numbers starting from 2 and up to a given value
    /// 
    class Program
    {

        /*         
        1. Create a list of natural numbers 2, 3, 4, 5, ….., n.  None of which is marked. Each process 
        creates its share of lists. 
        2. Set k to 2, the first unmarked number on the list. Each process does this. 
        3. Repeat: Each process marks its share of list 
        a. Mark all multiples of k between k² and n. 
        b. Find the smallest number greater than k that is unmarked. Set  k to this new 
        value 
        c. Process 0 broadcasts k to rest of processes. 
        Until k² > n. 
        4. The unmarked numbers are primes. 
        5. Reduction to determine number of primes
        */

        /// 

        /// possible status of each thread used by this program
        /// 
        enum ThreadStatus
        {
            DoingStuff = 0,
            Waiting = 1,
            Dead = 2
        };

        /// 

        /// Statuses for all the threads started
        /// 
        static ThreadStatus[] ThreadStatuses;

        /// 

        /// array that stores wether a number is prime or not true = prime, false = not prime
        /// this array should be as long as the maximum number up to which you want to find primes
        /// 
        static bool[] nums;

        /// 

        /// k from the algorithm above
        /// 
        static int k;

        /// 

        /// n from the algorithm above
        /// 
        static int n;

        /// 

        /// nr of threads that compute primes - this is actually the number of worker threads because one 
        /// extra thread will handle just finding the smallest remainig prime and broadcasting it to all the 
        /// other threads
        /// 
        static int nrThreads;

        /// 

        /// changes status of all worker threads to "DoingStuff"
        /// 
        static void MakeWorkerThreadsDoStuff()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                ThreadStatuses[i] = ThreadStatus.DoingStuff;
            }
        }

        /// 

        /// changes status of all worker threads to "Waiting"
        /// 
        static void MakeWorkerThreadsWait()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                ThreadStatuses[i] = ThreadStatus.Waiting;
            }
        }

        /// 

        /// changes status of all worker threads to "Dead"
        /// 
        static void KillWorkerThreads()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                ThreadStatuses[i] = ThreadStatus.Dead;
            }
        }

        /// 

        /// checks wether at least one of the worker threads is still doning something
        /// 
        /// 
        static bool WorkerThreadsDoingStuff()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                if (ThreadStatuses[i] == ThreadStatus.DoingStuff)
                    return true;
            }
            return false;
        }

        /// 

        /// checks wether at least one of the worker threads is waiting(on stand by)
        /// 
        /// 
        static bool WorkerThreadsWaiting()
        {
            for (int i = 1; i < nrThreads + 1; i++)
            {
                if (ThreadStatuses[i] == ThreadStatus.Waiting)
                    return true;
            }
            return false;
        }

        /// 

        /// checks wether the main thread is in wairing mode
        /// 
        /// 
        static bool MainThreadWaiting()
        {
            return (ThreadStatuses[0] == ThreadStatus.Waiting);
        }

        /// 

        /// checks if all threads are done working and waiting
        /// 
        /// 
        static bool AllThreadsDead()
        {
            foreach (var threadStatus in ThreadStatuses)
            {
                if (threadStatus != ThreadStatus.Dead)
                    return false;
            }

            return true;
        }

        /// 

        /// each thread runs this function it marks non prime numbers within it's given range
        /// between start and stop
        /// 
        /// 

        static void MarkNonPrimes(int ThreadNr)
        {

            while (ThreadStatuses[ThreadNr] == ThreadStatus.Waiting)
            {
                Thread.Sleep(1);
            }

            if (ThreadStatuses[ThreadNr] == ThreadStatus.Dead)
                return;
            //stores how many numbers we have to decide are primes or non primes
            int nrOfNumbers = n - k * k;
            //divide that by the number of threads to get the interval within which each thread should 
            //look for primes
            int interval = nrOfNumbers / nrThreads;

            //for this thread and this value of k start at this value
            int startNumber = k * k + interval * (ThreadNr - 1);
            //and end at this value
            int stopNumber = (ThreadNr == nrThreads) ? n : startNumber + interval;

            lock (nums)
            {
                for (int j = startNumber; j < stopNumber; j++)
                {
                    //Mark all multiples of k between k² and n. 
                    if (j % k == 0)
                        nums[j] = false;
                }
            }

            //nothig to do now but wait
            ThreadStatuses[ThreadNr] = ThreadStatus.Waiting;

            MarkNonPrimes(ThreadNr);
        }

        /// 

        /// this is the main thread's function it manages the worker therads and finds the smallest prime
        /// when the worker threads finish marking non primes
        /// 
        static void FindSmallestPrimeAndBroadcast()
        {
            while (WorkerThreadsDoingStuff())
            {
                Thread.Sleep(1);
            }

            //c. Process 0 broadcasts k to rest of processes. 
            for (int i = k + 1; i < n; i++)
            {
                if (nums[i])
                {

                    k = i;

                    break;
                }
            }
            //Until k² > n. 
            if (k * k > n)
            {
                //kill worker threads
                KillWorkerThreads();
                //commit suicide
                ThreadStatuses[0] = ThreadStatus.Dead;
                return;
            }
            //all worker threads can now read the correct new value of k so they can all get to work
            MakeWorkerThreadsDoStuff();

            FindSmallestPrimeAndBroadcast();
        }

        static void Main(string[] args)
        {

            n = 100;
            nrThreads = 10;

            //add one because one main thread is needed to manage all the others
            ThreadStatuses = new ThreadStatus[nrThreads + 1];

            //1. Create a list of natural numbers 2, 3, 4, 5, ….., n.  None of which is marked.
            nums = new bool[n];
            //suppose all these are primes, we will then start marking them as non primes
            for (int i = 2; i < n; i++)
                nums[i] = true;

            //initialize k with 1, start looking for primes bigger than 1, 1 is not a prime
            k = 1;

            //make sure all threads are waiting so they don't run out and find primes on their 
            //own without the main thread regulating them
            MakeWorkerThreadsWait();

            //this is the main thread
            var _mainThread = new System.Threading.Thread(() => FindSmallestPrimeAndBroadcast());
            _mainThread.IsBackground = true;
            _mainThread.Start();

            //worker threads
            for (int i = 1; i < nrThreads + 1; i++)
            {
                //need to declare this as a locol variable so that the value passed to the thread
                //won't be changed causing chaos
                var localI = i;
                var _workerThread = new System.Threading.Thread(() => MarkNonPrimes(localI));

                _workerThread.IsBackground = true;
                _workerThread.Start();
            }

            //wait for all threads to end
            while (!AllThreadsDead())
            //commenting the line above and decommenting the one below really help with debugging
            //because you don't constantly get sidetracked to AllThreadsDead() when pressing F5
            //while (true)
            {
                Thread.Sleep(1);
            }

            //print the primes you found
            for (int i = 0; i < n; i++)
                if (nums[i])
                    Console.WriteLine(i);
        }
    }
}