Think of XML Web services simply as components or Application Programming Interfaces (APIs) exposed on a Web site rather than a DLL residing on your own computer.
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.
Any assemblies with type definitions contain corresponding type information describing them. This information is called metadata (data about data).Reflection is the process of programmatically obtaining type information. Programs can dynamically inspect (“reflect upon”) the metadata for any assemblies, dynamically instantiate objects and invoke members, and even emit metadata dynamically (a technology called Refection Emit). Reflection provides late binding facilities like COM’s IDispatch and IDispatchEx interfaces, type inspection like COM’s ITypeInfo and ITypeInfo2 interfaces, and much more.
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
Good COM server implementation in C#
Building COM Objects in C#
]]>
eg: y = raw_input(‘Enter a number’)
# y is a string
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 listtuple = ( '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
]]>
First of all, I cannot edit the resource file with the default program. Searched with Google, this is a bug of VS. Just replace the slash in absolute including path with double slash;
The second issue is additional lib. In VS2010, multiply lib file names is separate by semicolon, but in VS2009 it is space;
]]>
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.
]]>
prompt> mkdir /path/to/repo:
prompt> cd /path/to/repo
prompt> git init
Initialized empty Git repository in /path/to/repo/.git/
prompt>
... create file(s) for first commit ...
prompt> git add .
prompt> git commit -m 'initial import'
Created initial commit bdebe5c: initial import.
1 files changed, 1 insertions(+), 0 deletions(-)
Note that the commit action only commits to your local repository.
Change one of my github repo name in two steps:
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:
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
prompt>git push origin master
git commit --amend -m "New commit message"
If the commit you want to fix isn’t the most recent one:
-
git rebase --interactive $parent_of_flawed_commitIf you want to fix several flawed commits, pass the parent of the oldest one of them.
-
An editor will come up, with a list of all commits since the one you gave.
- Change
picktoreword(or on old versions of Git, toedit) in front of any commits you want to fix. - Once you save, git will replay the listed commits.
- Change
-
Git will drop back you into your editor for every commit you said you want to reword, and into the shell for every commit you wanted to edit. If you’re in the shell:
- Change the commit in any way you like.
git commit --amendgit rebase --continue
Most of this sequence will be explained to you by the output of the various commands as you go. It’s very easy, you don’t need to memorise it – just remember that git rebase --interactive lets you correct commits no matter how long ago they were.
Today, when I try to push some code to the remote, it told me the there is a permission issue, I finally fixed it by created a new key, add it to my git account and local account. Here is the process of adding to local
If you did not have a key, generate one according this https://help.github.com/articles/generating-ssh-keys
then add the key
$ ssh-add /c/Users/li/.ssh/key
Clone your repository
Create a new repository in a new directory via the following commands.
# Switch to home cd ~ # Make new directory mkdir repo02 # Switch to new directory cd ~/repo02 # Clone git clone ../remote-repository.git .
]]>
10 percent of the code (Hennessy and Patterson, 2002)
Use a vector instead of an array whenever possible.
Vectors provide fast (constant time) element insertion and deletion at the end of the vector, but slow
(linear time) insertion and deletion anywhere else. Insertion and deletion are slow because the operation
must move all the elements “down” or “up” by one to make room for the new element or to fill the
space left by the deleted element. Like arrays, vectors provide fast (constant time) access to any of their
elements.
You should use a vector in your programs when you need fast access to the elements, but do not plan to
add or remove elements often. A good rule of thumb is to use a vector whenever you would have used
an array.
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.
Chapter8
Initializer lists allow initialization of data members at the time of their creation.
An initializer list allows you to provide initial values for data members as they are created, which is more efficient than assigning values to them later.
However, several data types must be initialized in an initializer list. The following table summarizes them:a銆?const data members錛?b銆丷eference data members C銆丱bject data members or Superclasses without default constructors
Initializer lists initialize data members in their declared order in the class definition,not their order in the list.
Chapter9
Pass objects by const reference instead of by value.
The default semantics for passing arguments to functions in C++ is pass-by-value. That means that the function or method receives a copy of the variable, not the variable itself. Thus, whenever you pass an object to a function or method the compiler calls the copy constructor of the new object to initialize it. The copy constructor is also called whenever you return an object from a function or method.
]]>
# include <stdio.h> /* Function to swap values at two pointers */void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */void permute(char *a, int i, int n) { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } } /* Driver program to test above functions */int main() { char a[] = "ABC"; permute(a, 0, 2); getchar(); return 0; } |
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; } |
]]>
紿楀彛
----
鍏跺疄 Mac OS X 鐨勮佺敤鎴蜂滑閮借鐔熸倝浜嗭紝鍜?Windows 涓嶄竴鏍鳳紝榪欎釜緋葷粺閲?#8220;紿楀彛”騫墮潪
鏈閲嶈鐨勬蹇碉紝涓涓▼搴忕殑閫昏緫緇撴瀯鏄細
+---------------------------------------------+
| Application |
| +-------------------------+ +-----------+ |
| | Window | | Menu | |
| | +----------------+ | +-----------+ |
| | | Control | | |
| | | +---------+ | | |
| | | | Control | | | |
| | | +---------+ | | |
| | +----------------+ | |
| +-------------------------+ |
+---------------------------------------------+
涔熷氨鏄錛岃彍鍗曟槸鐙珛浜庣獥鍙ｇ殑瀛樺湪錛屾湁紿楀彛鍜屾帶浠剁殑鍖哄埆銆傝繖鍜?Windows 涓竴鍒囩殑
鏈川閮芥槸紿楀彛鏈夊緢澶х殑鍖哄埆銆?nbsp;
铏界劧 Mac OS X 涓尯鍒?Window, Control 鍜?Menu 榪欏嚑縐嶆蹇碉紝浣嗗茍涓嶄唬琛ㄥ叾璁捐涓?
娌℃湁鑰冭檻鍒板畠浠箣闂寸殑涓鑷存с傚湪 Carbon 涓紝榪欎簺瀹炰綋閮芥槸鐢?FooRef 鐨勫艦寮忔潵琛ㄧず
鐨勶紝Ref 灝辨湁鎸囬拡鐨勬剰鎬濓紝姣斿浣犲垱寤轟簡涓涓獥鍙ｄ箣鍚庯紝灝變細寰楀埌瀵瑰簲鐨?nbsp;
WindowRef錛屽叾瀹炶繖灝辨槸涓涓敤鏉ユ搷綰佃繖涓獥鍙ｇ殑鎸囬拡錛岃屼綘鍒涘緩鎺т歡涔嬪悗錛屽搴旂殑
鏄?ControlRef錛屽垱寤鴻彍鍗曞搴旂殑鑷劧鏄?MenuRef 浜嗭紝榪樻槸寰堝ソ鐞嗚В鐨勫惂銆?nbsp;
鎴戜滑榪欓噷鍏堝彧璋堢獥鍙ｃ傚緢鏄劇劧錛岃鍒涘緩紿楀彛錛岃繕寰楁湁浜涘叾浠栫殑灞炴э紝璁╂垜浠湅鐪?nbsp;
Carbon 鐨?CreateNewWindow 榪欎釜鍑芥暟鐨勫師褰㈡槸鎬庝箞瑕佹眰鐨勶細
OSStatus CreateNewWindow (
WindowClass windowClass,
WindowAttributes attributes,
const Rect *contentBounds,
WindowRef *outWindow
);
WindowClass 鏄竴涓父閲忥紝鎴戜滑鏈甯歌鐨勪竴縐嶆槸 kDocumentWindowClass (涔熸槸涓嬮潰
鎵撶畻瑕佺敤鐨?錛岃繕鏈?kDrawerWindowClass錛岃繖涔熷緢濂界悊瑙ｏ細閭ｇ鍙互浼哥緝鐨?Drawer
鍢涳紝kAlertWindowClass 鍛紵灝辨槸鎴戜滑甯歌鐨勬彁紺烘浜嗐?nbsp;
WindowAttributes 鍒欐槸閽堝鍏蜂綋 WindowClass 鍐嶄綔鏇翠粩緇嗙殑灞炴у畾鍒朵簡錛岃繖涔熸槸涓涓?nbsp;
32 浣嶇殑鏃犵鍙鋒暣鏁幫紝浣嗗拰 WindowClass 鍙兘 n 閫?1 涓嶅悓錛屼綘鍙互鎶婂睘鎬х敤浣嶆垨 (|) 緇?
鍚堣搗鏉ヤ嬌鐢ㄣ傚弽姝ｄ竴鏃朵篃璁頒笉浣忛偅涔堝錛屽氨鍏堣緗負
kWindowStandardDocumentAttributes | kWindowStandardHandlerAttribute 濂戒簡銆傚墠
鑰呬繚璇佹垜浠殑紿楀彛鍏鋒湁鍏朵粬鏍囧噯鐨勬枃妗ｇ獥鍙ｇ浉鍚岀殑鐗規э紝鑰屽悗鑰呯粰紿楀彛鍔犱笂緋葷粺鎻愪緵鐨?
鏍囧噯 event handler錛屼互鑷姩澶勭悊涓鑸殑 event銆備笅闈㈡槸鐢ㄤ簬璁劇疆鐨勪唬鐮侊細
WindowAttributes windowAttrs;
windowAttrs = kWindowStandardDocumentAttributes |
kWindowStandardHandlerAttribute;
鐩村埌榪欓噷錛?#8220;event”閮借繕鏄竴涓緢妯＄硦鐨勬蹇碉紝铏界劧鎴戜滑鍓嶉潰澶氭鎻愬埌浜嗗畠錛屼絾涓轟簡閬?
鍏嶈繃澶氱殑璁茬悊璁猴紝鎴戞嫋鍒扮幇鍦ㄦ墠鏉ヤ粙緇嶅畠銆?nbsp;
Event (浜嬩歡) 鍏跺疄鏄?Carbon 緙栫▼鐨勫熀紜銆傞紶鏍囩偣鍑匯侀敭鐩樿緭鍏ャ佽彍鍗曞懡浠ら兘鏄互
event 鐨勫艦寮忓彂鍑虹殑銆傜獥鍙ｉ渶瑕侀噸緇樸佺Щ鍔ㄥ拰鏀劇緝鏃訛紝涔熶細鍛婄煡浣犵殑搴旂敤紼嬪簭涓涓?nbsp;
event銆傚綋浣犵殑紼嬪簭鍒囨崲鍒板墠绔垨鑰呭悗绔椂錛屼綘涔熶細鏀跺埌 event 鍛婄煡浣犺繖涓俊鎭?
Carbon 紼嬪簭鐨勫伐浣滃氨鏄氳繃鍥炲簲 event 鏉ュ疄鐜頒笌鐢ㄦ埛鍜岀郴緇熶氦浜掋?nbsp;
Carbon 鐨?event 澶勭悊鏄熀浜庡洖璋?(callback) 鏈哄埗鐨勩備綘鍙互瀹氫箟閽堝涓嶅悓 event 綾誨瀷
鐨?event handler錛岀劧鍚庡湪 Carbon Event Manager 涓敞鍐?(Install) 涔嬨傜劧鍚庢瘡褰?nbsp;
event 鍙戠敓鏃訛紝Carbon Event Manager 灝變細璋冪敤浣犳敞鍐岀殑 handler 鍑芥暟銆傛瘡涓?event
handler 閮藉繀欏諱笌涓涓叿浣撶殑 event target 瀵硅薄鍏寵仈璧鋒潵錛屾瘮濡?target 鏄彍鍗曘佺獥鍙ｆ垨
鏁翠釜紼嬪簭銆?nbsp;
搴旂敤紼嬪簭鍖呭惈紿楀彛鍜岃彍鍗曪紝紿楀彛鍖呭惈鎺т歡錛屾帶浠惰繕鑳借繘涓姝ュ寘鍚帶浠躲備竴鏃?event 鍑?
鐜幫紝棣栧厛寰楀埌閫氱煡鐨勬槸鏈閲屽眰鐨?target錛屾瘮濡傜偣鍑?button 鐨?event 棣栧厛鍙戝埌 button 鎺?
浠朵笂銆傚鏋滄渶閲岄潰鐨?target 娌℃湁鐩稿叧鐨?handler錛屽氨鎶?event 浼犳挱鍒版洿澶栧眰鐨勫寘鍚畠鐨?nbsp;
target 涓娿侰arbon 緇欑獥鍙ｅ拰搴旂敤紼嬪簭鐨?event target 鎻愪緵浜嗘爣鍑嗙殑 handler銆傛爣鍑?nbsp;
handler 鍙互璐熻矗澶勭悊綾諱技紿楀彛閽堝榧犳爣鐨勬搷浣滐紝姣斿鎷栨嫿錛屼幾緙╃瓑絳夈傝繖鏍蜂竴鏉ワ紝浣?
灝卞彧闇瑕佸叧蹇冭嚜宸辯殑紼嬪簭閲岄拡瀵規嫋鎷芥垨浼哥緝鐨勭壒孌婂弽鏄狅紝鑰屼笉姣旇垂紲炰簬閭ｄ簺鎵鏈夌▼搴忛兘
閫氱敤鐨勯儴鍒嗕簡銆?nbsp;
褰撶劧錛屽鏋滀綘鎰挎剰錛屼篃鍙互瑕嗙洊鏍囧噯鐨?handler錛屾瘮濡傛湁浜哄彲鑳戒細鍐欎釜閽堝鎷変幾紿楀彛鐨?nbsp;
handler錛岀粰紿楀彛鐨勪幾緙╁鍔犻煶鏁堛傛垜浠繖閲屾病閭ｄ箞澶嶆潅錛岀敤鏍囧噯鐨勫氨濂藉暒銆?nbsp;
絎笁涓弬鏁板氨鏇村ソ鐞嗚В浜嗭紝鏄竴涓寚鍚?Rect 榪欎釜緇撴瀯浣撶殑鎸囬拡錛岃鏄庝簡紿楀彛鍦ㄥ睆騫曞潗
鏍囩郴 [1] 涓殑浣嶇疆鍜屽ぇ灝忋傝繖涓笢瑗垮叾瀹炶繕鏄?QuickDraw 涓殑姒傚康錛屾墍浠ュ湪紼嬪簭涓垜
浠篃璋冪敤 QuickDraw 鐨?API 鏉ュ畬鎴愯緗細
#define kWindowTop 100
#define kWindowLeft 50
#define kWindowRight 800
#define kWindowBottom 600
Rect contentRect;
SetRect(&contentRect, kWindowLeft, kWindowTop,
kWindowRight, kWindowBottom);
璁劇疆鐨勬鏄繖涓煩褰㈠洓涓偣鐨勫潗鏍囥?nbsp;
[1]: 娉ㄦ剰灞忓箷鍧愭爣緋諱腑宸︿笂瑙掓槸 (0, 0)銆?
鏈鍚庝竴涓弬鏁版槸涓涓緭鍑猴紝涔熷氨鏄垜浠渶緇堝垱寤哄嚭鏉ョ殑閭ｄ釜鏂扮獥鍙ｇ殑鎸囬拡浜嗐傛墍浠ワ紝鎴?
浠竴鑸槸榪欐牱鍒涘緩紿楀彛鐨勶細
WindowRef theWindow;
CreateNewWindow(kDocumentWindowClass, windowAttrs,
&contentRect, &theWindow);
絳夌瓑錛岀獥鍙ｆ槸鍒涘緩濂戒簡錛屽瓨鍦?theWindow 鎸囬拡閲岋紝鍙獥鍙ｇ殑鏍囬鍛紵鎴戜滑榪欐牱璁劇疆錛?nbsp;
SetWindowTitleWithCFString(theWindow, CFSTR("Hello Carbon"));
娉ㄦ剰榪欓噷鐨?CFSTR 鏄竴涓畯錛岀敤浜庢妸 C 鐨?const char * 瀛楃涓茶漿鎹負 Core
Foundation 瀹氫箟鐨?CFStringRef 瀛楃涓詫紝瀵逛簬 CFString 鐨勮緇嗕粙緇嶅彲浠ョ湅 Strings
Programming Guide for Core Foundation [2]錛屼笉榪囧叾瀹炵幇鍦ㄦ垜浠煡閬撳畠鍖呮嫭鐨勬槸涓涓?
鏁扮粍鍜屾暟緇勭殑闀垮害錛屾暟緇勭殑鍏冪礌閮芥槸 Unicode 瀛楃 (UniChar)錛屽氨琛屼簡錛屽叿浣撶殑杞崲緇?
鑺傛殏鏃朵笉蹇呰冭檻銆?
[2]: http://developer.apple.com/documentation/CoreFoundation/Conceptual/
CFStrings/CFStrings.html
涓鍒囧畬姣曚箣鍚庯紝鎴戜滑灝卞彲浠ユ樉紺鴻繖涓獥鍙ｄ簡錛?nbsp;
ShowWindow(theWindow);
涓嬮潰鎶婂畬鏁寸殑浠ｇ爜鍒楀嚭 (浣犱篃鍙互鐪嬮檮浠墮噷闈㈢殑)錛?nbsp;
/* hello.c: testing Carbon basics */
#include <Carbon/Carbon.h>
#define kWindowTop 100
#define kWindowLeft 50
#define kWindowRight 800
#define kWindowBottom 600
int main(int argc, char *argv[])
{
WindowRef theWindow;
WindowAttributes windowAttrs;
Rect contentRect;
windowAttrs = kWindowStandardDocumentAttributes |
kWindowStandardHandlerAttribute;
SetRect(&contentRect, kWindowLeft, kWindowTop,
kWindowRight, kWindowBottom);
CreateNewWindow(kDocumentWindowClass, windowAttrs,
&contentRect, &theWindow);
SetWindowTitleWithCFString(theWindow,
CFSTR("Hello Carbon"));
ShowWindow(theWindow);
RunApplicationEventLoop();
return 0;
}
榪欎竴鑺傜殑鍐呭錛屽憙錛岃繕鏄秴鍑轟簡鎴戠殑棰勮錛屼綘瑕佹槸鏈夊叴瓚ｄ笉濡ㄥ啀鐪嬬湅 Carbon Event
Manager Programming Guide錛宔vent 榪樻槸涓涓瘮杈?tricky 鐨勬蹇碉紝鑰屾垜浠鍒板悗闈?
鐢ㄥ埌鐨勬椂鍊欐墠浼氭繁璋堛備笅涓鑺傝鑿滃崟鐨勫垱寤恒?nbsp;
]]>
The original post is http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/
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:
]]>