31 августа 2007

Writing a calculator

Самая первая программа, написанная мною, была написана на Basic для Robotron 1715. Это был простейший калькулятор: вводите два операнда и оператор, и получаете результат.

Сейчас пишу вычисление формул, вспоминаю тот калькулятор ;) Задача сейчас такова: есть описание GUI в XML в виде
<control
  name="Button1"
  x="100"
  y="200"
  width="300"
  height="400"
/>


Необходима возможность понимать такие выражения:
<control
  name="Button1"
  x="Button2.x + 100"
  y="Form.height - 200"
  width="Form.width - (Button3.width*2 + 100)"
  height="400"
/>

И чтобы при resize окна (изменении пользователем размеров формы) пересчитались все зависимые от размеров формы координаты.

Как решалась задача:
1. Парсим каждую формулу на лексемы (операнды, операторы и скобки) - получаем выражение в инфиксной форме.
2. Переводим инфиксную форму в постфиксную.
3. Заменяем имена переменных (типа "Form.width" и "Button2.x") на указатели на них.
4. Одна формула может ссылаться на другую, та - на третью, четвертая - на первую и т.п. Поэтому топологической сортировкой выясняем порядок вычисления формул.
5. Вычисляем формулы по порядку, вычисленному в п.4. Формулы в постфиксной форме вычисляются очень просто и быстро.

При изменении размеров формы выполняем только п.5, причем можно вычислять не все формулы, а только прямо или косвенно зависимые от размеров формы.

PS. А мой первый калькулятор был гораздо проще - состоял всего из трех INPUT-ов и четырех IF-ов (на каждый поддерживаемый оператор).

28 августа 2007

Is it simple to write text editor for Windows?

Казалось бы - насколько просто написать небольшой текстовый редактор для Windows?

Вот очень интересный tutorial на эту тему: Design and Implementation of a Win32 Text Editor. Автор описывает как решать ту огромную кучу нюансов, с которыми приходится столкнуться: unicode, разные направления письма, большие тексты, переменная скорость прокрутки при выделении мышью и многое другое.

Жаль, автор не закончил сей труд. Но возможно он еще продолжит.

PS. Там же на сайте можно найти еще много интересного по Windows programming.

25 августа 2007

`this' is just an ordinary pointer

Как вы думаете, насколько надежна такая конструкция:
int Bar();
class Foo
{
int x;
public:
void y()
{
x = Bar();
}
};
На первый взгляд все отлично. До тех пор, пока не увидим всю картину:
Foo* foo;
int Bar()
{
if (...) delete foo;
return ...;
}
void Main
{
foo = new Foo();
foo->y();
}
Ситауция представлена здесь довольно утрированно, но суть понятна: мембер-функция Foo::y() вызывает другую функцию Bar(), которая удаляет объект. Тот самый объект, который Foo::y() знает как this. Далее Foo::y() пытается записать что-то в this->x, который уже не существует.

Реальна ли такая ситуация, или это ошибка архитектуры? Думаю, такая ситуация вполне может иметь место. Ведь мы давно свыклись с тем, что после vector::push_back() может привести в негодность все наши итераторы на этот вектор, и к другим подобным ситуациям. Нужно просто при вызове функции (в нашем случае Bar()) знать, что this может стать недействительным.

Такая ситуация может возникнуть, например, если элементы GUI (controls) реализованы как объекты (привет WTL):
void Button::OnClick()
{
Dialog.Close();
// this больше недействителен!
}
Вобщем, this - это такой же обычный указатель, и логично сделать его умным указателем. Пусть сам о себе заботится.
class Foo : public boost::enable_shared_from_this<Foo>
{
int x;
public:
void y()
{
boost::weak_ptr<Foo> This(shared_from_this());
int bar = Bar();
if (!This->expired()) x = bar;
}
};

boost::shared_ptr<Foo> foo;
int Bar()
{
if (...) foo.reset();
return ...;
}

12 августа 2007

Smart pointer with copy semantic

Умные указатели - вещь полезная не только для уменьшения кода, но и отсутствием головной боли с удалением объектов. Например, следующий класс легко положить в контейнер, для него можно не переопределять копирующий конструктор и оператор присваивания:
class Foo
{
std::vector<Bar> A;
boost::shared_ptr<Bar> B;
};
Члены A и B сами позаботятся о своем копировании: A сделает deep copy своего содержимого в новый объект, B будет вести подсчет ссылок.

Однако, почему-то в популярных (STL и boost) библиотеках нет умного указателя, аналогичного shared_ptr, но не с подсчетом ссылок, а с глубоким копированием. То есть чтобы он указывал на один (или ноль, если SmartPointer=NULL) объект, а не как vector - на массив. Подходящий указатель есть в Loki, благо там все разбито по стратегиям и можно задать любую стратегию копирования (подсчет ссылок, глубокое копирование, ...). Однако лишний раз иметь зависимость от Loki не всем удобно. Писать свой велосипед - еще менее удобнее. Компромисный вариант: использовать std::vector, кладя в него не больше одного элемента. Звучит смешно, но работает.

04 августа 2007

mutable

Интересно, почему не все понимают смысл и полезность ключевого слова mutable. Истинная его ценность состоит в том, чтобы дать возможность в const member-функциях производить такие изменения в объекте, которые не видны снаружи. Все, что видно "снаружи" пользователям объекта - это то, что можно получить через публичный интерфейс. Это нужно для кэширования и ленивых вычислений.

Например, мы пишем адаптер, позволяющий приводить строки типа const char* и std::string к единому интерфейсу вида Data, Size. Для const char* размер можно расчитать через strlen() сразу (не важно, потребуется нам результат вычислений или нет), но можно сделать это только если понадобится:
class StringAdapter
{
public:
explicit StringAdapter(const std::string& String) :
_Data(String.data()), _Size(String.size()), _SizeCached(true) {}

explicit StringAdapter(const char* String) :
_Data(String), _SizeCached(false) {}

const char* Data() const { return _Data; }

size_t Size() const
{
if (!_SizeCached) { _Size = strlen(_Data); _SizeCached = true; }
return _Size;
}

private:
const char* _Data;
mutable size_t _Size;
mutable bool _SizeCached;
};
Без mutable мы бы не смогли внутри Size(), объявленной как const, модифицировать наш кэш.