An assembly is a self-describing logical component. Assemblies are units of deployment, units of security, units of versioning, and units of scope for the types contained within. Although an assembly is typically one executable or one DLL, it could be made up of multiple files. 

How Unmanaged Code Interacts with Managed Code

Three technologies exist that enable the interaction between unmanaged and managed code:

• Platform Invocation Services (PInvoke)
  

   1 static class GameSharp
   2 {
   3     /// The native methods in the DLL's unmanaged code.
   4     internal static class UnsafeNativeMethods
   5     {
   6     const string _dllLocation = "CoreDLL.dll";
   7     [DllImport(_dllLocation)]
   8     public static extern void SimulateGameDLL(int a, int b);
   9     }
  10 }
  Choosing a Calling Convention
  The calling convention of an entry point can be specified using another DllImportAttribute named parameter, called CallingConvention. The choices for this are as follows:
  CallingConvention.Cdecl. The caller is responsible for cleaning the stack. Therefore, this calling convention is appropriate for methods that accept a variable number of parameters (like printf).
  CallingConvention.FastCall. This is not supported by version 1.0 of the .NET Framework.
  CallingConvention.StdCall. This is the default convention for PInvoke methods running on Windows. The callee is responsible for cleaning the stack.
  CallingConvention.ThisCall. This is used for calling unmanaged methods defined on a class. All but the first parameter is pushed on the stack since the first parameter is the this pointer, stored in the ECX register.
  CallingConvention.Winapi. This isn’t a real calling convention, but rather indicates to use the default calling convention for the current platform. On Windows (but not Windows CE), the default calling convention is StdCall.
  Declare always uses Winapi, and the default for DllImportAttribute is also Winapi. As you might guess, this is the calling convention used by Win32 APIs, so this setting doesn’t need to be used in this chapter’s examples.
   1 using System;
   2 using System.Runtime.InteropServices;
   3 
   4 public class LibWrap
   5 {
   6 // C# doesn't support varargs so all arguments must be explicitly defined. 
   7 // CallingConvention.Cdecl must be used since the stack is  
   8 // cleaned up by the caller. 
   9 
  10 // int printf( const char *format [, argument] )
  11 
  12 [DllImport("msvcrt.dll", CharSet=CharSet.Unicode, CallingConvention=CallingConvention.Cdecl)]
  13 public static extern int printf(String format, int i, double d); 
  14 
  15 [DllImport("msvcrt.dll", CharSet=CharSet.Unicode, CallingConvention=CallingConvention.Cdecl)]
  16 public static extern int printf(String format, int i, String s); 
  17 }
  18 
  19 public class App
  20 {
  21     public static void Main()
  22     {
  23         LibWrap.printf("\nPrint params: %i %f", 99, 99.99);
  24         LibWrap.printf("\nPrint params: %i %s", 99, "abcd");
  25     }
  26 }

• Mixed-Mode Programming Using Managed Extensions to C++

• COM Interoperability

      Building COM Objects in C#

list = [ 'abcd', 786 , 2.23, 'john', 70.2 ] tinylist = [123, 'john']  
print list          # Prints complete list 
print list[0] # Prints first element of the list 
print list[1:3] # Prints elements starting from 2nd till 3rd  
print list[2:] # Prints elements starting from 3rd element 
print tinylist * 2 # Prints list two times 
print list + tinylist # Prints concatenated list

tuple = ( 'abcd', 786 , 2.23, 'john', 70.2 ) tinytuple = (123, 'john')  
print tuple           # Prints complete list 
print tuple[0] # Prints first element of the list 
print tuple[1:3] # Prints elements starting from 2nd till 3rd  
print tuple[2:] # Prints elements starting from 3rd element 
print tinytuple * 2 # Prints list two times 
print tuple + tinytuple # Prints concatenated lists

esp is the top of the stack.

ebp is usually set to esp at the start of the function. Local variables are accessed by subtracting a constant offset from ebp. All x86 calling conventions define ebp as being preserved across function calls. ebp itself actually points to the previous frame's base pointer, which enables stack walking in a debugger and viewing other frames local variables to work.

Most function prologs look something like:
push ebp      ; Preserve current frame pointer
mov ebp, esp  ; Create new frame pointer pointing to current stack top
sub esp, 20   ; allocate 20 bytes worth of locals on stack. 


Then later in the function you may have code like (presuming both local variables are 4 bytes)
mov [ebp-4], eax    ; Store eax in first local
mov ebx, [ebp - 8]  ; Load ebx from second local



For example, to completely disassemble a binary:
objdump -Dslx file




Cocoa bindings can be a little confusing, especially to newcomers. Once you have an understanding of the underlying concepts, bindings aren’t too hard. In this article, I’m going to explain the concepts behind bindings from the ground up; first explaining Key-Value Coding (KVC), then Key-Value Observing (KVO), and finally explaining how Cocoa bindings are built on top of KVC and KVO.

Key-Value Coding (KVC)

The first concept you need to understand is Key-Value Coding (KVC), as KVO and bindings are built on top of it.

Objects have certain "properties". For example, a Person object may have an name property and an address property. In KVC parlance, the Person object has a value for the name key, and for the address key. "Keys" are just strings, and "values" can be any type of object[1]. At it’s most fundamental level, KVC is just two methods: a method to change the value for a given key (mutator), and a method to retrieve the value for a given key (accessor). Here is an example:

void ChangeName(Person* p, NSString* newName)

{

    //using the KVC accessor (getter) method

    NSString* originalName = [p valueForKey:@"name"];

    //using the KVC mutator (setter) method.

    [p setValue:newName forKey:@"name"];

    NSLog(@"Changed %@'s name to: %@", originalName, newName);

}

Now let’s say the Person object has a third key: a spouse key. The value for the spouse key is another Person object. KVC allows you to do things like this:

void LogMarriage(Person* p)

{

    //just using the accessor again, same as example above

    NSString* personsName = [p valueForKey:@"name"];

    //this line is different, because it is using

    //a "key path" instead of a normal "key"

    NSString* spousesName = [p valueForKeyPath:@"spouse.name"];

    NSLog(@"%@ is happily married to %@", personsName, spousesName);

}

Cocoa makes a distinction between "keys" and "key paths". A "key" allows you to get a value on an object. A "key path" allows you to chain multiple keys together, separated by dots. For example, this…

[p valueForKeyPath:@"spouse.name"];

… is exactly the same as this…

[[p valueForKey:@"spouse"] valueForKey:@"name"];

That’s all you need to know about KVC for now.

Let’s move on to KVO.

Key-Value Observing (KVO)

Key-Value Observing (KVO) is built on top of KVC. It allows you to observe (i.e. watch) a KVC key path on an object to see when the value changes. For example, let’s write some code that watches to see if a person’s address changes. There are three methods of interest in the following code:

watchPersonForChangeOfAddress: begins the observing

observeValueForKeyPath:ofObject:change:context: is called every time there is a change in the value of the observed key path

dealloc stops the observing

static NSString* const KVO_CONTEXT_ADDRESS_CHANGED = @"KVO_CONTEXT_ADDRESS_CHANGED"

@implementation PersonWatcher

-(void) watchPersonForChangeOfAddress:(Person*)p;

{

    //this begins the observing

    [p addObserver:self

        forKeyPath:@"address"

           options:0

           context:KVO_CONTEXT_ADDRESS_CHANGED];

    //keep a record of all the people being observed,

    //because we need to stop observing them in dealloc

    [m_observedPeople addObject:p];

}

//whenever an observed key path changes, this method will be called

- (void)observeValueForKeyPath:(NSString *)keyPath

                      ofObject:(id)object

                        change:(NSDictionary *)change

                       context:(void *)context;

{

    //use the context to make sure this is a change in the address,

    //because we may also be observing other things

    if(context == KVO_CONTEXT_ADDRESS_CHANGED){

        NSString* name = [object valueForKey:@"name"];

        NSString* address = [object valueForKey:@"address"];

        NSLog(@"%@ has a new address: %@", name, address);

    }       

}

-(void) dealloc;

{

    //must stop observing everything before this object is

    //deallocated, otherwise it will cause crashes

    for(Person* p in m_observedPeople){

        [p removeObserver:self forKeyPath:@"address"];

    }

    [m_observedPeople release]; m_observedPeople = nil;

    [super dealloc];

}

-(id) init;

{

    if(self = [super init]){

        m_observedPeople = [NSMutableArray new];

    }

    return self;

}

@end

This is all that KVO does. It allows you to observe a key path on an object to get notified whenever the value changes.

Cocoa Bindings

Now that you understand the concepts behind KVC and KVO, Cocoa bindings won’t be too mysterious.

Cocoa bindings allow you to synchronise two key paths[2] so they have the same value. When one key path is updated, so is the other one.

For example, let’s say you have a Person object and an NSTextField to edit the person’s address. We know that every Person object has an address key, and thanks to the Cocoa Bindings Reference, we also know that every NSTextField object has a value key that works with bindings. What we want is for those two key paths to be synchronised (i.e. bound). This means that if the user types in the NSTextField, it automatically updates the address on the Person object. Also, if we programmatically change the the address of the Person object, we want it to automatically appear in the NSTextField. This can be achieved like so:

void BindTextFieldToPersonsAddress(NSTextField* tf, Person* p)

{

    //This synchronises/binds these two together:

    //The `value` key on the object `tf`

    //The `address` key on the object `p`

    [tf bind:@"value" toObject:p withKeyPath:@"address" options:nil];

}

What happens under the hood is that the NSTextField starts observing the address key on the Person object via KVO. If the address changes on the Person object, the NSTextField gets notified of this change, and it will update itself with the new value. In this situation, the NSTextField does something similar to this:

- (void)observeValueForKeyPath:(NSString *)keyPath

                      ofObject:(id)object

                        change:(NSDictionary *)change

                       context:(void *)context;

{

    if(context == KVO_CONTEXT_VALUE_BINDING_CHANGED){

        [self setStringValue:[object valueForKeyPath:keyPath]];

    }       

}

When the user starts typing into the NSTextField, the NSTextField uses KVC to update the Person object. In this situation, the NSTextField does something similar to this:

- (void)insertText:(id)aString;

{

    NSString* newValue = [[self stringValue] stringByAppendingString:aString];

    [self setStringValue:newValue];

    //if "value" is bound, then propagate the change to the bound object

    if([self infoForBinding:@"value"]){

        id boundObj = ...; //omitted for brevity

        NSString* boundKeyPath = ...; //omitted for brevity

        [boundObj setValue:newValue forKeyPath:boundKeyPath];

    }

}

For a more complete look at how views propagate changes back to the bound object, see my article: Implementing Your Own Cocoa Bindings.

Conclusion

That’s that basics of how KVC, KVO and bindings work. The views use KVC to update the model, and they use KVO to watch for changes in the model. I have left out quite a bit of detail in order to keep the article short and simple, but hopefully it has given you a firm grasp of the concepts and principles.

Footnotes

[1] KVC values can also be primitives such as BOOL or int, because the KVC accessor and mutator methods will perform auto-boxing. For example, a BOOL value will be auto-boxed into an NSNumber*.

[2] When I say that bindings synchronise two key paths, that’s not technically correct. It actually synchronises a "binding" and a key path. A "binding" is a string just like a key path but it’s not guaranteed to be KVC compatible, although it can be. Notice that the example code uses @"address" as a key path but never uses @"value" as a key path. This is because @"value" is a binding, and it might not be a valid key path.

Firstly, cd to your local git directory, and find out what remote name(s) refer to that URL

$ git remote -v origin  git@github.com:someuser/someproject.git 

Then, set the new URL

$ git remote set-url origin git@github.com:someuser/newprojectname.git 

or in older versions of git, you might need

$ git remote rm origin $ git remote add origin git@github.com:someuser/newprojectname.git 

(origin is the most common remote name, but it might be called something else.)

But if there's lots of people who are working on your project, they will all need to do the above steps, and maybe you don't even know how to contact them all to tell them. That's what #1 is about.

Further reading:

• github - working with remotes
• Git Reference - remotes
• Git Book - Distributed Workflows

Footnotes:

1 The exact format of your URL depends on which protocol you are using, e.g.

• SSH = git@github.com:someuser/someproject.git
• HTTPS = https://someuser@github.com/someuser/someproject.git
• GIT = git://github.com/someuser/someproject.git

# Switch to home
cd ~
# Make new directory
mkdir repo02

# Switch to new directory
cd ~/repo02
# Clone
git clone ../remote-repository.git . 

The name deque is an abbreviation for a double-ended queue. A deque is partway between a vector and a
list, but closer to a vector. Like a vector, it provides quick (constant time) element access. Like a list, it
provides fast (amortized constant time) insertion and deletion at both ends of the sequence. However,
unlike a list, it provides slow (linear time) insertion and deletion in the middle of the sequence.
You should use a deque instead of a vector when you need to insert or remove elements from either end
of the sequence but still need fast access time to all elements. However, this requirement does not apply
to many programming problems; in most cases a vector or queue should suffice.

A set in STL is a collection of elements. Although the mathematical definition of a set implies an
unordered collection, the STL set stores the elements in an ordered fashion so that it can provide reasonably
fast lookup, insertion, and deletion.
Use a set instead of a vector or list if you want equal performance for insertion, deletion,and lookup.
Note that a set does not allow duplication of elements. That is, each element in the set must be unique. If
you want to store duplicate elements, you must use a multiset.

2. find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

#include<stdio.h> int maxSubArraySum(int a[], int size) {    int max_so_far = 0, max_ending_here = 0;    int i;    for(i = 0; i < size; i++)    {      max_ending_here = max_ending_here + a[i];      if(max_ending_here < 0)         max_ending_here = 0;      if(max_so_far < max_ending_here)         max_so_far = max_ending_here;     }     return max_so_far; }    /*Driver program to test maxSubArraySum*/ int main() {    int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};    int max_sum = maxSubArraySum(a, 8);    printf("Maximum contiguous sum is %d\n", max_sum);    getchar();    return 0; }

Over the past couple of years, auto-complete has popped up all over the web. Facebook, YouTube, Google, Bing, MSDN, LinkedIn and lots of other websites all try to complete your phrase as soon as you start typing.

Auto-complete definitely makes for a nice user experience, but it can be a challenge to implement efficiently. In many cases, an efficient implementation requires the use of interesting algorithms and data structures. In this blog post, I will describe one simple data structure that can be used to implement auto-complete: a ternary search tree.

Trie: simple but space-inefficient

Before discussing ternary search trees, let’s take a look at a simple data structure that supports a fast auto-complete lookup but needs too much memory: a trie. A trie is a tree-like data structure in which each node contains an array of pointers, one pointer for each character in the alphabet. Starting at the root node, we can trace a word by following pointers corresponding to the letters in the target word.

Each node could be implemented like this in C#:

class TrieNode
{
public const int ALPHABET_SIZE = 26;
public TrieNode[] m_pointers = new TrieNode[ALPHABET_SIZE];
public bool m_endsString = false;
}

Here is a trie that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

Implementing auto complete using a trie is easy. We simply trace pointers to get to a node that represents the string the user entered. By exploring the trie from that node down, we can enumerate all strings that complete user’s input.

But, a trie has a major problem that you can see in the diagram above. The diagram only fits on the page because the trie only supports four letters {A,B,C,D}. If we needed to support all 26 English letters, each node would have to store 26 pointers. And, if we need to support international characters, punctuation, or distinguish between lowercase and uppercase characters, the memory usage grows becomes untenable.

Our problem has to do with the memory taken up by all the null pointers stored in the node arrays. We could consider using a different data structure in each node, such as a hash map. However, managing thousands and thousands of hash maps is generally not a good idea, so let’s take a look at a better solution.

Ternary search tree to the rescue

A ternary tree is a data structure that solves the memory problem of tries in a more clever way. To avoid the memory occupied by unnecessary pointers, each trie node is represented as a tree-within-a-tree rather than as an array. Each non-null pointer in the trie node gets its own node in a ternary search tree.

For example, the trie from the example above would be represented in the following way as a ternary search tree:

The ternary search tree contains three types of arrows. First, there are arrows that correspond to arrows in the corresponding trie, shown as dashed down-arrows. Traversing a down-arrow corresponds to “matching” the character from which the arrow starts. The left- and right- arrow are traversed when the current character does not match the desired character at the current position. We take the left-arrow if the character we are looking for is alphabetically before the character in the current node, and the right-arrow in the opposite case.

For example, green arrows show how we’d confirm that the ternary tree contains string ABBA:

And this is how we’d find that the ternary string does not contain string ABD:

Ternary search tree on a server

On the web, a significant chunk of the auto-complete work has to be done by the server. Often, the set of possible completions is large, so it is usually not a good idea to download all of it to the client. Instead, the ternary tree is stored on the server, and the client will send prefix queries to the server.

The client will send a query for words starting with “bin” to the server:

And the server responds with a list of possible words:

Implementation

Here is a simple ternary search tree implementation in C#:

public class TernaryTree
{
private Node m_root = null;
private void Add(string s, int pos, ref Node node)
{
if (node == null) { node = new Node(s[pos], false); }
if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
else
{
if (pos + 1 == s.Length) { node.m_wordEnd = true; }
else { Add(s, pos + 1, ref node.m_center); }
}
}
public void Add(string s)
{
if (s == null || s == "") throw new ArgumentException();
Add(s, 0, ref m_root);
}
public bool Contains(string s)
{
if (s == null || s == "") throw new ArgumentException();
int pos = 0;
Node node = m_root;
while (node != null)
{
int cmp = s[pos] - node.m_char;
if (s[pos] < node.m_char) { node = node.m_left; }
else if (s[pos] > node.m_char) { node = node.m_right; }
else
{
if (++pos == s.Length) return node.m_wordEnd;
node = node.m_center;
}
}
return false;
}
}

And here is the Node class:

class Node
{
internal char m_char;
internal Node m_left, m_center, m_right;
internal bool m_wordEnd;
public Node(char ch, bool wordEnd)
{
m_char = ch;
m_wordEnd = wordEnd;
}
}

Remarks

For best performance, strings should be inserted into the ternary tree in a random order. In particular, do not insert strings in the alphabetical order. Each mini-tree that corresponds to a single trie node would degenerate into a linked list, significantly increasing the cost of lookups. Of course, more complex self-balancing ternary trees can be implemented as well.

And, don’t use a fancier data structure than you have to. If you only have a relatively small set of candidate words (say on the order of hundreds) a brute-force search should be fast enough.

Further reading

Another article on tries is available on DDJ (careful, their implementation assumes that no word is a prefix of another):

http://www.ddj.com/windows/184410528

If you like this article, also check out these posts on my blog:

• Skip lists are fascinating!
• Numbers that cannot be computed
• Quicksort killer