Programmatically Opening the Windows Start Menu

windows-vista-start-menu

Some time ago I was looking for a way to launch the Windows Start Menu programmatically. The simplest way I thought so far was to fake the Ctrl + Escape keystroke so the menu could be tricked as being requested by the user.

I was more than satisfied to discover that a System.Windows.Forms.SendKeys class was readily available from the .NET Framework and that it could be used send keystrokes to other applications.  According to MSDN, all I have to do was call SendKeys.Send("^{ESC}") to achieve my goal.

 

Well, but this didn’t work quite well.

Further reading on MSDN revealed the reason. Sending keystrokes only worked in a focused window, and to focus the Start Menu I needed to get its window handle. A possible, but not so trivial or clean operation to be done in a purely managed world.

Because there is no managed method to activate another application, you can either use this class within the current application or use native Windows methods, such as FindWindow and SetForegroundWindow, to force focus on other applications.

This was going to get quite complex, so I decided for another approach, instead. While googling for the SendKeys class, I found about the SendKeys method of the Windows Script Host (WSH) and decided to give it a try.

 

Using Windows Scripting Host to Send Key Messages to Windows

To use the Windows Script Host in your dot-Net application, all you have to do is include a reference in your project to the Windows Script Host Object Model (found under the COM tab of Visual Studio‘s Add Reference dialog) and then import the IWshRuntimeLibrary namespace to your code with the using directive.

After a bit of testing, it was evident the native SendKeys method behaves differently than the Framework way and didn’t require the windows to be previously focused.

 

So I ended up writing the following code, and decided to share in case someone else finds it useful:

 

using System;

using IWshRuntimeLibrary;

 

namespace cSouza.Utils.Windows

{

 

    /// <summary>

    ///   Provides methods for sending

    ///   keystrokes to an application.

    /// </summary>

    public static class SendKeys

    {

 

        /// <summary>

        ///   Sends one or more keystrokes to the active window

        ///   (as if typed on the keyboard).

        /// </summary>

        /// <param name="keys">

        ///   String value indicating the keystroke(s) you want to send.

        /// </param>

        /// <param name="wait">

        ///   Indicates if execution stops until the sent messages

        ///   have been processd by the target application.

        /// </param>

        public static void Send(string keys, bool wait)

        {

            WshShell shell = new WshShellClass();

            object wObj = wait;

 

            shell.SendKeys(keys, ref wObj);

        }

 

        /// <summary>

        ///   Sends one or more keystrokes to the active window

        ///   (as if typed on the keyboard).

        /// </summary>

        /// <param name="keys">

        ///   String value indicating the keystroke(s) you want to send.

        /// </param>

        public static void Send(string keys)

        {

            Send(keys, false);

        }

 

        /// <summary>

        ///   Sends one or more keystrokes to the active window

        ///   (as if typed on the keyboard) and stops execution

        ///   until the sent messages have been processd by the

        ///   target application

        /// </summary>

        /// <param name="keys">

        ///   String value indicating the keystroke(s) you want to send.

        /// </param>

        public static void SendWait(string keys)

        {

            Send(keys, true);

        }

    }

}

using this class, all we have to do to launch the start menu now is call:

cSouza.Utils.Windows.SendKeys.Send("^{ESC}");

 

I hope you have found this useful. Feel free to use this code as you wish. This is public domain. For more detailed information about how the Windows Script Host SendKeys method works, please read this article, Automate tasks with Windows Script Host’s SendKey method, by Greg Shultz.

Árvore B em Arquivo (em C++)

Novamente, outro post ecológico! Após a apresentação da Árvore AVL, porque não agora Árvores B?

Árvore de maior largura do mundo

Árvores B são estrutura de dados bastante utilizadas em sistemas de arquivos e bancos de dados. São geralmente mais densas em informação por nível em comparação com Árvores AVL, o que significa que possuem geralmente uma altura menor mesmo armazenando um mesmo número de elementos.

Em primeiro lugar, devo especificar que este artigo não se destina a explicar o funcionamento das Árvores B em detalhes. Para isto temos uma variedade de fontes e recursos à nossa disposição; descrições sobre o funcionamento de uma Árvore B são facilmente encontradas na internet.

Uma coisa, no entanto, infelizmente não é: Implementações compreensíveis que também sejam, ao mesmo tempo, completas e funcionais.

Como exemplo, não raro encontramos o mesmo problema que tivemos ao encontrar informações sobre Árvores AVL. É dada menos ênfase aos métodos de remoção destas estruturas. Ou então, por vezes encontramos a Árvore B implementada fora de seu contexto: em memória. Árvores B reais servem ao propósito de serem armazenadas em disco; por isso seus nós são geralmente denominados páginas.

Introdução

Imagine que uma Árvore AVL contenha tantos dados que já não caiba mais em memória. Tentando contornar esta situação, podemos definir uma estratégia em que cada nó da Árvore AVL (que armazena no máximo 1 elemento) ocupe uma posição diferente dentro de um mesmo arquivo de dados. Para acessar um filho de um nó, por exemplo, podemos ler em qual posição o filho se encontra, navegar até a posição determinada e o carregarmos em memória. É fácil ver que esta solução resolve o problema da memória, pois a cada vez iremos carregar apenas a informação com o qual queremos trabalhar, e nunca a árvore toda.

Porém, imagine agora que gostaríamos de percorrer a árvore em busca de um elemento qualquer. Imagine também que o elemento em questão não está contido na árvore e que esta árvore tem, em termos gerais, n níveis de altura. Utilizando o algoritmo de busca em árvore binária, teremos de fazer, no mínimo, n leituras em disco para buscar a informação que queremos. Ou melhor, para concluir que não pudemos encontrar a informação que queríamos. Apenas relembrando, não esqueça o fato de que memórias secundárias como o disco rígido são geralmente ordens de magnitude mais lentas do que a memória principal.

Para n pequeno, é evidente que isto não faz diferença – o tempo de acesso a um disco rígido é, geralmente, de alguns milisegundos. Mas lembrando que como estamos falando de árvores realmente grandes, o acesso ao disco pode tornar-se um gargalo considerável.

Nesse contexto, a estrutura AVL torna-se bastante ineficiente. Como então solucionar este problema?

R: Diminuindo o número de seeks necessários para se alcançar uma informação.

A Árvore B (ou B-Tree) emprega uma estrutura paginada ideal para minimizar o acesso em disco. Cada um de seus nós contem não um elemento, mas vários; quantos seu desenvolvedor quiser. A cada acesso, várias, e não apenas uma informação, são lidas de cada vez. Desta maneira a informação torna-se muito mais condensada nos primeiros níveis, e altura da árvore diminui consideravelmente.

 

Citando a Wikipedia:

Em ciência da computação, Árvore B ou B-Tree é uma estrutura de dados árvores que são muito utilizadas em banco de dados e sistema de arquivos.

Para inserir ou remover variáveis de um nó, o nó não poderá ultrapassar sua ordem e nem ser menor que sua ordem dividida por dois. Árvores B não precisam ser rebalanceadas como são freqüentemente as árvores de busca binária com Árvore AVL. Árvores B têm vantagens substanciais em relação a outros tipos de implementações quanto ao tempo de acesso e pesquisa aos nós.

 

Esta é uma apresentação bastante razoável. No entanto, certa cautela precisa ser tomada pois autores diferentes tratam a ordem da Árvore B de maneiras diferentes, como por exemplo no livro Algoritmos – Teoria e Prática. Neste livro, os autores se referem não à ordem da Árvore, mas à seu grau t, definido como o número mínimo de filhos que um nó não-raiz pode possuir. Como consequência, o número mínimo de elementos de uma Árvore poderá ser tomado como t-1 e o máximo como 2t-1. Com isso, acabam efetivamente definindo a ordem da árvore (a que me refiro como sendo o número máximo de filhos de um nó) como 2t e o número máximo de elementos como 2t-1. Apesar de se enquadrar dentro das regras enunciadas acima na definição da Wikipedia, a apresentação de Árvores B desta forma inclui um pequeno problema.

A ordem de das árvores ficará restrita a termos pares (que estejam na forma 2t), o que simplifica os algorítmos de inserção e remoção, mas acabam por não mais descrever à uma Árvore B de ordem geral.

Por esta razão, o código que apresentaremos e documentaremos a seguir se adequa à Árvores B de qualquer ordem.

Propósito

Como bem sabemos, o propósito de uma Árvore B é otimizar o acesso e a manipulação da informação armazenada em discos, servindo geralmente como estrutura de índice à outros arquivos de registros no qual o índice pode se tornar muito grande para caber em memória. Neste contexto, atuando como índice, a árvore armazenará uma chave e a posição relativa em arquivo (relative record number ou byte offset) em que o registro se encontra no arquivo de registros.

Definições

Antes de prosseguirmos, enunciaremos primeiro algumas definições para que não haja confusão no decorrer deste artigo:

A ordem m da árvore está definida como o número máximo de filhos que um único nó pode possuir;

Logo, o número máximo de elementos num nó e dado por m-1 e o máximo de filhos por m. Já o número mínimo de elementos que um nó pode possuir é dado pela fórmula floor((m-1) / 2).

A Árvore B está implementada em arquivo, então definimos “Offset” como um typedef para long int. Para representar o equivalente em arquivo para o ponteiro nulo (NULL) utilizaremos o valor constante NULLOFFSET como -1L (menos-um na forma de long int). Esta é uma prática comum pois a posição 0, em arquivo, é uma posição válida, ao contrário de seu equivalente em memória.

Implementação

O código que apresentamos e documentamos a seguir se adequa à Árvores B de quaisquer ordens. A implementação foi feita em C++ no Microsoft Visual Studio, sem utilizar as extensões .NET/CLI (apesar da solução, em si, possuir código misto pois estava atrelada à uma interface gráfica em WinForms).

Clique aqui para ver o código e a documentação completos da Árvore B (BTree) em Arquivo (em C++) gerados pela ferramenta Doxygen. O código é, claro, livre para quaisquer adaptações desde que permaneça sob a Licença MIT e suas informações autorais sejam mantidas. Mas lembre-se de que o código tem fins meramente educativos e não deve ser utilizado num ambiente onde a performance é um fator crítico. Ou, melhor, não deve ser utilizado em outro lugar fora um trabalho acadêmico simples.

Diagrama de Classes

 

O Nó (BTreeNode)

O nó da Árvore B, aqui chamado de BTreeNode, pode conter vários elementos, em contraste com a Árvore AVL, em que pode haver apenas um. A Árvore B pode ser vista como uma generalização da Árvore AVL para ordens superiores, ou a Árvore AVL como uma especialização da Árvore B para ordem 2 (m=2).

Assim, o nó deve conter um vetor de elementos e um vetor de filhos, onde estes filhos, ao invés de conter ponteiros em memória, contem ponteiros em arquivo (Offsets) para os próximos nós.

Representação de uma Árvore B [Wikipedia]

É nesta classe que estão contidos os métodos split() e merge(), que divide um nó em dois e intercala dois nós em um único nó, respectivamente. Estes métodos são chamados durante a operação de Inserção ou de Remoção pela classe principal BTree, que é a classe gerenciadora dos nós. Mais informações serão apresentadas à seguir.

A Lista de Disponíveis (DStack)

Como a estrutura da Árvore B é mantida em arquivo, não basta alocarmos/desalocarmos nós em memória utilizando new e delete como fazíamos na Árvore AVL. Temos que alocar uma posição no arquivo que acomoda a árvore e armazenar o nó nesta posição; ao deletarmos um nó temos que, de algum modo, avisar que a posição que antes acomodava o nó agora está vaga. Para isto, utilizamos outra estrutura em arquivo denominada lista de disponíveis, que é responsável por registrar, na forma de uma lista encadeada, onde estão os registros disponíveis e assim indicar qual a próxima posição vaga no arquivo. Para simplificação, esta lista é, na verdade, geralmente implementada como uma pilha.

Assim, suponha que a pilha está vazia (a posição inicial registrada é NULLOFFSET) e a posição 241 foi desocupada. Então ao chamar o método push(241) a lista de disponíveis deverá caminhar até a posição 241, escrever NULLOFFSET e então registrar que 241 é o começo da pilha.

Agora suponha que 340 foi desocupada. Então o método push(340) irá caminhar até a posição 340, escrever 240, que é o endereço do nó que antes era começo da pilha, e registrar que a pilha começa agora na posição 340. Assim por diante, push(500) caminhará até a posição 500, escreverá o endereço do começo anterior (340) e registrará que a posição inicial é, agora, 500. Assim, os nós vão se encadeando – cada posição disponível carrega uma referência a próxima posição disponível ou a NULLOFFSET se não há nada mais além daquele ponto.

Para remover, pop() simplesmente deverá ler quem é a posição inicial, e, caso seja diferente de NULLOFFSET, caminhar até esta posição, ler qual é o endereço do próximo nó (ou NULLOFFSET, caso não haja mais nós) e então registrar esta posição como a nova posição inicial.

Clique aqui para visualizar a implementação da lista de disponíveis em C++.

 

A Árvore (BTree)

A classe BTree, ou Árvore B, deve ser responsável por gerenciar seus nós, alocando, dealocando, carregando e descarregando, tentando o máximo possível minimizar a quantidade de nós carregados em memória de cada vez. É nela que estão contidos os métodos de inserção e remoção, que em nossa implementação são recursivos.

Abaixo está uma pequena descrição sobre o funcionamento da inserção e remoção, porém note que seus códigos correspondentes são, na verdade, bem mais elaborados que esta pequena introdução. Felizmente, há comentários no decorrer do código para auxiliar em seu entendimento.

Inserção / Split

O método de inserção da classe BTree pode cair no caso em que não é mais possível armazenar informação num nó pois este está cheio. Quando isto acontece, chama-se o método-membro Split do nó que está cheio, que dividirá o nó em dois e retornará uma referência em arquivo (Offset) ao novo nó criado durante a divisão. O método que controla a inserção está presente na classe BTree, enquanto o split pertence ao BTreeNode.

Remoção / Merge

Analogamente a inserção, o método de remoção da classe BTree poderá cair no caso em que seja necessário remover um elemento de um nó mas efetuar esta operação violaria a regra sobre o número mínimo de elementos que um nó deve conter. Neste caso, a árvore pode encontrar o elemento sucessor (imediatamente seguinte) ao elemento que estamos tentando remover, trocar os dois e então remover o substituto recursivamente, ou, caso não seja possível emprestar de ninguem, realizar uma intercalação entre dois nós mínimos formando um novo nó completo. Esta intercalação é conhecida como merge. O método que controla a remoção está presente na classe BTree, enquanto o merge pertence ao BTreeNode.

 

Código fonte em C++

O código fonte pode ser navegado na íntegra clicando-se aqui. Para fazer download de uma solução Visual Studio 2008 contendo o fonte, clique aqui.

Árvore AVL em C++

Aqui está um código em C++ para uma Árvore AVL visando fins mais educacionais do que práticos. Apesar da teoria ser muito importante, não adianta nada ler pseudo-algorítmos sem saber como a teoria pode ser, de fato, aplicada. Ainda mais quando a maioria dos livros-texto deixa o método de remoção como exercício. Que mania!

A Árvore apresentada abaixo utiliza apenas uma técnica que pode parecer estranha, a primeira vista, para quem está acostumado a tratar com árvores em algoritmo puro. As subárvores esquerda e direita, presentes em cada nó, estão dispostas em um vetor de dois elementos. Isto traz uma vantagem imensa na hora de rotacionar a árvore, pois corta a necessidade de métodos auxiliares pela metade. Ao invés de termos de implementar rotações à esquerda e depois a direita, por exemplo, aproveitamos um mesmo método para realizar a operação de rotação em ambas as direções.

Fora este recurso adicional, o restante da implementação é bem similar aos textbooks que encontramos por aí. O nó não precisa de uma referência adicional ao seu pai (que é desnecessária, por sinal) e guarda apenas seu fator de balancemento (outras implementações guardam sua altura). O código é orientado a objetos (nada de código C disfarçado), e não está sobrecarregado com templates, embora qualquer um possa modificar o código de forma a suportá-los facilmente.

Continue reading →

Função Pseudo-Aleatoria rand() Completa

Quem já precisou gerar números aleatórios relativamente grandes em C/C++ se deparou com uma situação no mínimo frustrante.

Como uma implementação de função pseudo-aleatória gera números apenas até 32,767?

Até perceber que a função rand não gerava números com mais de 16 bits, perdi um bom tempo procurando um erro inexistente em meu programa. O pior é que este problema é específico apenas à algumas implementações da stdlib, que pude confirmar ocorrer no Visual Studio e no Mingw, que utiliza uma versão do gcc.

Para gerar números aleatórios até máximo que um inteiro (de 32 bits) agüenta, podemos utilizar o seguinte código (que gera números num intervalo fechado de i até j):

int rand_int(const int i, const int j)
{
    return i + ( ((rand() << 15) | rand()) % (j – i + 1) );
}

O que o código acima faz é gerar dois números aleatórios, deslocar um 15 bits para a esquerda (o primeiro bit em um inteiro deverá ser de sinal) e mesclar os dois num mesmo número de 32 bits. Analogamente, é possível formar números aleatórios de 32, 64, ou quantos mais bits se desejar deslocando distâncias suficientes e combinando todos números em um só.

Mais detalhes sobre implementações e aprimoramentos da função pseudo-aleatória podem ser encontrados neste site. É possível até gerar distribuições razoavelmente distribuídas com alguns truques apenas utilizando a função rand().

Outro detalhe interessante é que a sequência aleatória gerada pela função rand(), ao menos nas implementações em que testei, parece se repetir sempre a cada 2,147,483,648 chamadas. Ou seja, a função é capaz de gerar 231 (cerca de 2 bilhões) números aparentemente aleatórios até que o primeiro número seja gerado novamente e a sequência passada recomece exatamente em mesma ordem. Isto é natural de algorítmos para geração de números aleatórios pois um algorítmo é, por definição, um conjunto de passos específicos e finitos, portanto sempre possuindo uma saída previsível sem espaço para incertezas. Daí os algorítmos serem denominados, na verdade, pseudo-aleatórios, pois obedecem um conjunto de regras complexas, mas finitas, para gerar suas saídas.

System.Windows.Forms.Cursor.Position

I’ve found several places mentioning the use of the Windows native method GetCursorPos(POINT lpPoint) as a way to get the mouse cursor position outside a System.Windows.Form in C#. But why not use the built-in .NET Framework method, System.Windows.Forms.Cursor.Position instead? A quick look using Reflector show us that Cursor.Position is merely a managed call to another method,

UnsafeNativeMethods.GetCursorPos(lpPoint);

which is, in turn, the exact unsafe native method I mentioned previously.

[DllImport(“user32.dll”, CharSet=CharSet.Auto, ExactSpelling=true)]
public static extern bool GetCursorPos([In, Out] NativeMethods.POINT pt);

Thus, using Cursor.Position and GetCursorPos returns the same results, but the former is the clearly prefered option as it is a built-in method and is therefore a more portable option. Plus it provides additional permission checks to ensure your application has the right privileges to run prior to execution.

So, unless you are trying to avoid adding a reference to Windows.Forms in your project, there is no reason to use interop when System.Windows.Forms.Cursor.Position is an option.

System.Windows.Forms.Textbox AppendLine

appendline

Ever wanted to append a new line of text to a TextBox, tried searching IntelliSense for a AppendLine method but just couldn’t find it?

With the following code, one can add the missing AppendLine(string text) method for appending a new line of text to a System.Windows.Forms.TextBox by using the new Extension Methods of C# 3.0

using System;
using System.Windows.Forms;

namespace cSouza.Utils.WinForms
{
   
public static class TextBoxExtender
    {
       
/// <summary>
        ///  Appends a new line of text to the current text of the TextBox.
        /// </summary>
        /// <param name="text">The text to append to the current contents of the TextBox</param>
       
public static void AppendLine(this TextBox textBox, String text)
        {
            if (textBox.Text.Length > 0)
                textBox.AppendText(Environment.NewLine)
;
            textBox.AppendText(text)
;
       
}

        /// <summary>
        ///  Inserts a new line to the current text of the TextBox.
        /// </summary>
        /// <param name="text">The text to append to the current contents of the TextBox</param>
       
public static void AppendLine(this TextBox textBox)
        {
            textBox.AppendText(Environment.NewLine)
;
       
}
    }
}

To use AppendLine() on a TextBox object, just add this class to your project and import its namespace. To do this, create a new empty class, copy and paste this code inside it and then import the cSouza.Utils.WinForms namespace (with the using directive) wherever needed. Feel free to change the namespace name to something else if you wish.

Once this class becomes reachable from your code, you’ll notice that AppendLine() will start showing up on IntelliSense right after you type in the name of a TextBox object, just like a standard method would.

For more information about the new Extension Methods of C# 3.0, you can read a nice article written by Vipul Patel on developer.com by clicking here.