Understanding of bitwise complement (also known as 1’s complement). The equivalent the bitwise complementoperator in C# is "~" (tilde) and in VB.NET “XOR”
In general we use Array.BinarySearch to find the element index in given array. But if you understand about return value of
Array.BinarySearch function, we can build sorted array too. Even Microsoft used the same technic in implementing
System.Collections.SortedList class.
Below is definition from MSDN about Array.BinarySearch return value:
The index of the specifiedvaluein the specifiedarray, ifvalueis found. Ifvalueis not found andvalueis less than one or more elements inarray, a negative number which is the bitwise complement of the index of the first element that is larger thanvalue. Ifvalueis
not found andvalueis greater than any of the elements inarray, a negative number which is the bitwise complement of (the index of the last element plus 1).
It means, it returns the index of found element otherwise it returns the expected index position in bitwise complement.
Let’s see same thing in action. Below sample code (MySortedList class) acts like integer list and sorts its elements in ascending order dynamically whenever new element is added.
Sample Code: MySortedList
class Program
{
static void Main(string[] args)
{
MySortedList list = new MySortedList();
list.Add(10);
list.Add(8);
list.Add(7);
list.Add(7);
list.Add(20);
list.Add(16);
list.Add(1);
foreach (int v in list.Items)
{
Console.WriteLine(v);
}
Console.ReadLine();
}
}
class MySortedList
{
int[] items = new int[0];
public int[] Items
{
get { return items; }
set { items = value; }
}
public void Add(int value)
{
int index = Array.BinarySearch(items, value);
if (index < 0)
index = ~index;
//Increase Items Array Size by 1
int lastIndex = items.Length;
int capacity = items.Length + 1;
int[] dupArray = new int[capacity];
Array.Copy(items, dupArray, items.Length);
items = dupArray;
//Adjusting elements to insert element in its right index
if (index < lastIndex)
{
Array.Copy(items, index, items, index + 1, lastIndex - index);
}
items[index] = value;
}
}
Marked as answer by msharm on Nov 23, 2012 10:36 AM
SortedList creates a collection that stores key/value pairs in sorted order, based on the value of the keys.
using System;
using System.Collections.Generic;
using System.Text;
namespace SortedList
{
class Program
{
static void Main(string[] args)
{
SortedList<string, string> entries = new SortedList<string, string>();
entries["2006-08-23-2834792834723984"] = "event on 23rd";
entries["2006-08-23-2384728374394837"] = "event on 23rd";
entries["2006-08-22-2873498237483838"] = "event on 22nd";
entries["2006-08-16-2384792837483483"] = "event on 16th";
usingSystem;usingSystem.Collections;class SLDemo {staticvoid Main(){// Create a sorted SortedList.
SortedList sl =new SortedList();// Add elements to the table.
sl.Add("name", "mani");
sl.Add("age", "22");
sl.Add("city", "bangalore");// Can also add by using the indexer.
sl["country"]="india";// Get a collection of the keys.
ICollection c = sl.Keys;// Use the keys to obtain the values.
Console.WriteLine("Contents of list via indexer.");foreach(string str in c)
Console.WriteLine(str +": "+ sl[str]);
Console.WriteLine();// Display list using integer indexes.
Console.WriteLine("Contents by integer indexes.");for(int i=0; i < sl.Count; i++)
Console.WriteLine(sl.GetByIndex(i));
Console.WriteLine();// Show integer indexes of entries.
Console.WriteLine("Integer indexes of entries.");foreach(string str in c)
Console.WriteLine(str +": "+ sl.IndexOfKey(str));}}
msharm
Member
6 Points
6 Posts
How to design a class (or data type) which sorts its data either ascending or descending by defau...
Nov 23, 2012 03:45 AM|LINK
Hello,
How to design a class (or data type) which sorts its data either ascending or descending by default.
Can any one help in this question
Arvind Mishr...
Member
193 Points
24 Posts
Re: How to design a class (or data type) which sorts its data either ascending or descending by d...
Nov 23, 2012 04:54 AM|LINK
hello ,
see this...
This can be achieved by using Array.BinarySearch.
Prerequisite to read this FAQ
In general we use Array.BinarySearch to find the element index in given array. But if you understand about return value of Array.BinarySearch function, we can build sorted array too. Even Microsoft used the same technic in implementing System.Collections.SortedList class.
Below is definition from MSDN about Array.BinarySearch return value:
The index of the specifiedvaluein the specifiedarray, ifvalueis found. Ifvalueis not found andvalueis less than one or more elements inarray, a negative number which is the bitwise complement of the index of the first element that is larger thanvalue. Ifvalueis not found andvalueis greater than any of the elements inarray, a negative number which is the bitwise complement of (the index of the last element plus 1).
It means, it returns the index of found element otherwise it returns the expected index position in bitwise complement.
Let’s see same thing in action. Below sample code (MySortedList class) acts like integer list and sorts its elements in ascending order dynamically whenever new element is added.
Sample Code: MySortedList
class Program
{
static void Main(string[] args)
{
MySortedList list = new MySortedList();
list.Add(10);
list.Add(8);
list.Add(7);
list.Add(7);
list.Add(20);
list.Add(16);
list.Add(1);
foreach (int v in list.Items)
{
Console.WriteLine(v);
}
Console.ReadLine();
}
}
class MySortedList
{
int[] items = new int[0];
public int[] Items
{
get { return items; }
set { items = value; }
}
public void Add(int value)
{
int index = Array.BinarySearch(items, value);
if (index < 0)
index = ~index;
//Increase Items Array Size by 1
int lastIndex = items.Length;
int capacity = items.Length + 1;
int[] dupArray = new int[capacity];
Array.Copy(items, dupArray, items.Length);
items = dupArray;
//Adjusting elements to insert element in its right index
if (index < lastIndex)
{
Array.Copy(items, index, items, index + 1, lastIndex - index);
}
items[index] = value;
}
}
rabindra_lal
Member
515 Points
202 Posts
Re: How to design a class (or data type) which sorts its data either ascending or descending by d...
Nov 23, 2012 05:02 AM|LINK
SortedList creates a collection that stores key/value pairs in sorted order, based on the value of the keys.
using System;
using System.Collections.Generic;
using System.Text;
namespace SortedList
{
class Program
{
static void Main(string[] args)
{
SortedList<string, string> entries = new SortedList<string, string>();
entries["2006-08-23-2834792834723984"] = "event on 23rd";
entries["2006-08-23-2384728374394837"] = "event on 23rd";
entries["2006-08-22-2873498237483838"] = "event on 22nd";
entries["2006-08-16-2384792837483483"] = "event on 16th";
foreach (KeyValuePair<string, string> entry in entries)
{
Console.WriteLine("{0} = {1}", entry.Key, entry.Value);
}
}
}
}
2.
for more detail go through this urlhttp://www.youcanlearnseries.com/Programming%20Tips/CSharp/SortedList.aspx
http://www.dotnetperls.com/sort