воскресенье, 24 марта 2013 г.

Move of multiple items

В этой статье я расскажу о том как реализовать перемещение нескольких элементов контейнера за раз. Такая необходимость, например, возникает, когда пользователь выделяет несколько, в общем случае несмежных, элементов в QTableView и перетаскивает их в пределах таблицы. С единичным выделением, все довольно просто: удалил элемент в старой позиции и вставил в новую; кто-то позаботится о случае с перемещением от меньших индексов к большим, когда после удаления элемента в исходной позиции, нужно будет скорректировать индекс назначения, а кто-то сочтет, что сойдет и так.

Например eсть коллекция: 0 1 2 3 4 5
Нужно переместить элемент из позиции 1 в позицию 3 (индексы считаем с нуля)
Удаляем элемент из позиции 1: 0 2 3 4 5
Вставляем его в позицию 3: 0 2 3 1 4 5
Я бы все-таки ожидал, что элемент из позиции 1 будет вставлен перед элементом в изначальной позиции 3. В таком случае результат выглядел бы как: 0 2 1 3 4 5

Возможно это выглядит всего лишь как вопрос личных предпочтений (я как раз недавно спорил с одним человеком на эту тему), но на самом деле это не так.
Например на первом скриншоте cxerimolio будет вставлено перед ribo и это правильно В то время как на втором скриншоте, к удивлению пользователя cxerizo будет вставлено не перед piro, как того следовало ожидать судя по обозначеной позиции для вставки, а после него. Поэтому в случае forward move нужно корректировать индекс назначения.

Прежде чем продолжить оговорюсь, что я не буду фокусироваться на реализации Qt модели - той, что наследуется от QAbstractItemModel. Меня интересует только как правильно перемещать элементы в контейнере на уровне бизнес логики, в то время как QAbstractItemModel это всего лишь навсего адаптер между model и view/delegate. Тем не менее бизнес модель должна как-то уведомлять представление о том, что в ней что-то изменилось, поэтому снабдим ее соответствующим сигналом для случая move. Назовем нашу business model "SomeContainer" - это обьект, содержащий в себе коллекцию неких обьектов (в данном примере используются int'ы) и предоставляющий простейший интерфейс для манипуляций над ними.
Вот так будет выглядеть SomeContainer в нашем простейшем случае:

class SomeContainer : public QObject
{
Q_OBJECT

public: //types

typedef std::vector< int > ValueList; //collection of values to be moved
typedef size_t IndexType; //type of indices in ValueList
typedef std::vector< IndexType > IndexList; //collection of indices in ValueList

public: //methods

explicit SomeContainer( QObject *parent = 0);

//! move an item at srcIndex to the position before the item at destIndex
void moveItem( IndexType srcIndex, IndexType destIndex );
//! move multiple items to the position before the item at destIndex
void moveItems( const IndexList& srcIndices, IndexType destIndex );

//auxiliary methods needed for unit testing purpose only
void push_back( int value ) { m_items.push_back( value ); }
int at( IndexType index ) const { return m_items.at( index ); }

signals:

//!notifies that element at index oldIndex has been moved to the position defined by newIndex
void itemMoved( IndexType oldIndex, IndexType newIndex );

private: //fields

ValueList m_items;

};

Теперь можно перейти к написанию функции move для случая с перемещением одного элемента. Как я уже говорил все довольно-таки просто - удаляем элемент, корректируем индекс назначения, вставляем елемент. Что мне не нравится в этом, так это то, что после удаления элемента все элементы массива следующие за удаленным элементом будут перемещаться влево, а перед его вставкой они снова будут перемещаться, но теперь уже вправо. На самом деле достаточно будет только перемещать элементы между исходным индексом и индексом назначения, причем делать это можно единожды. Нужно только правильно выбрать направление сдвига в зависимости от направления перемещения интересующего нас элемента. Это несколько улучшит производительность, поэтому мы сразу же реализуем данную оптимизацию.
Вот так будет выглядеть наша функция moveItem

void SomeContainer::moveItem( IndexType srcIndex, IndexType destIndex )
{
Q_ASSERT( srcIndex > 0 && srcIndex < m_items.size() ); //validity check for the source index
Q_ASSERT( destIndex > 0 && destIndex <= m_items.size() ); //validity check for the destination index
//NOTE: m_item.size() is a valid position for the destination index - the item will be moved to the tail

if ( destIndex > srcIndex ) //in case if destIndex < srcIndex --destIndex is not needed as all the items will be shifted to the right
--destIndex; // ... and the item from srcIndex will automatically be inserted before the item at destIndex

ValueList::iterator srcIt = m_items.begin();
std::advance( srcIt, srcIndex );

ValueList::iterator destIt = m_items.begin();
std::advance( destIt, destIndex );

if ( srcIndex > destIndex )
backwardMove( srcIt, destIt );
else
forwardMove( srcIt, destIt );

emit itemMoved( srcIndex, destIndex );
}

А вот так вот будет выглядеть реализация методов forwardMove и backwardMove. Предположим, что они обьявлены в приватном неймспейсе.

//! moves forward the item pointed by srcIt to the position pointed by destIt
void forwardMove( ValueList::iterator srcIt, ValueList::iterator destIt )
{
ValueList::value_type movedItem = *srcIt;

//shifting all the items in the range [ sourcIndex + 1, destinationIndex ] to the left
ValueList::iterator afterSrcIt = srcIt;
++afterSrcIt;

ValueList::iterator afterDestIt = destIt;
++afterDestIt;

std::copy( afterSrcIt, afterDestIt, srcIt );

//write the moved item into the destination position
*destIt = movedItem;
}

//! moves backward the item pointed by srcIt to the position pointed by destIt
void backwardMove( ValueList::iterator srcIt, ValueList::iterator destIt )
{
ValueList::value_type movedItem = *srcIt;

//shifting all the items in the range [ destinationIndex, sourcIndex - 1 ] to the right
ValueList::iterator afterSrcIt = srcIt;
++afterSrcIt;

//dest < src
std::copy_backward( destIt, srcIt, afterSrcIt );

//write the moved item into the destination position
*destIt = movedItem;
}

Теперь перейдем к перемещению множества элементов за один раз. Просто вызывать moveItem в цикле нельзя. Во-первых, нужно корректировать позицию вставки после перемещения некоторых элементов. Во-вторых нужно также корректировать исходные индексы.
Например, имеется коллекция: 0 1 2 3 4 5 6 7
Нужно переставить элементы из позиций 0 и 1 в позицию перед элементом 6.
Передвигаем 0 в позицию перед 6, получаем: 1 2 3 4 5 0 6 7
Теперь под индексом 1 находится не 1, а 2 и следовательно нам нужно скорректировать исходный индекс 1 соответствующим образом, чтобы следующая перестановка произошла правильно.

Аналогичные сложности возникают и при перемещении назад, не говоря уже о таких случаях как, например перемещение элементов по индексами 0, 5, 3 с сохранением порядка в позицию перед 4. Ситуация еще больше осложняется тем, что нужно еще корректно уведомлять подписчиков на сигнал itemMoved. В случае неправильных уведомлений программа может даже завершиться аварийно из-за того что PersistentModelIndex'ы в QModelView оказались в неправильном состоянии.

Ниже приведен код функции moveItems, а также код двух вспомогательных функторов, необходимых для ее работы. Предполагается что код функторов расположен в приватном неймспейсе.

//We are using templates only for convenience in case if values type of SomeContainer::ValueList is changed in future

template< class T >
struct DecIfInRange
{
DecIfInRange( T minValue, T maxValue )
: m_minValue( minValue ), m_maxValue( maxValue )
{
}

T operator() ( const T& value ) const
{
return value > m_minValue && value <= m_maxValue ? value - 1 : value;
}

T m_minValue;
T m_maxValue;
};

template< class T >
struct IncIfInRange
{
IncIfInRange( T minValue, T maxValue )
: m_minValue( minValue ), m_maxValue( maxValue )
{
}

T operator() ( const T& value ) const
{
return value >= m_minValue && value < m_maxValue ? value + 1 : value;
}

T m_minValue;
T m_maxValue;
};

...
void SomeContainer::moveItems( const IndexList& srcIndices, IndexType destIndex )
{
IndexList src( srcIndices.begin(), srcIndices.end() );

for ( IndexList::iterator it=src.begin(); it != src.end(); ++it )
{
moveItem( *it, destIndex );

IndexList::iterator it2 = it;
++it2;

if ( *it < destIndex )
{
std::transform( it2, src.end(), it2, DecIfInRange< IndexType >( *it, destIndex ) );
}
else if ( *it > destIndex ) //if we move from the right of the destination point the next element should be moved on one index to the right.
{
std::transform( it2, src.end(), it2, IncIfInRange< IndexType >( destIndex, *it ) );
++destIndex;
}
}
}

Вот собственно и вся реализация.
Исходный код примера, а также юнит тесты доступны для загрузки здесь.

суббота, 9 февраля 2013 г.

Git, извлекаем данные из удаленного репозитория в непустой каталог

Мы работаем над довольно большим програмным продуктом весь исходный код которого хранится под SVN. Полная сборка всего приложения с использование IncrediBuild занимает 2 часа. Часто после очередного апдейта, если кто-то изменил что-то в одной из базовых библиотек приходится тратить слишком много времени на то, что все заново собрать. Поскольку наша команда работает только над небольшой частью продукта, мы решили использовать Git для того, что обмениваться кодом между собой без необходимости подтягивать изменения от других команд каждый раз - все что нужно, это время от времени синхронизироваться с SVN. Мы установили свой Git сервер и внесли в репозиторий только нужные нам проекты, отправив все остальные в игнор. Однако столкнулись со следующим затруднением. Когда кто-нибудь из наших разработчиков пытается извлесь файлы из Git в папку где лежат исходники извлеченные из SVN, используюя git init & git remote add + git pull, Git ругается на то, что такие файлы уже существуют в целевом каталоге и отказывается извлечь их.

error: Untracked working tree file 'file_name' would be overwritten by merge.

Проблема решается вызовом git reset --hard FETCH_HEAD. Команда означает, что нужно извлечь все файлы из ревизии FETCH_HEAD в локальную копию со сбросом индекса (staging area) и всех локальных изменений, при этом файлы стоящие в игноре остаются незатронутыми. Таким образом, чтобы извлечь файлы из Git в папку где уже существуют такие файлы, нужно сделать следующие шаги

git init
git remote add <remote_repo>
git fetch <remote_repo> <branch>
git reset --hard FETCH_HEAD

среда, 9 января 2013 г.

Подсветка синтаксиса в less

Есть команда выводящая результаты с подсветкой / раскраской - скажем это yum search, но выхлоп очень большой и нужно использовать пейджер less. Однако текст, прошедший через less становится одноцветным. Как сделать так, чтобы он оставался цветным. Вот ответ:
yum --color=always search your_text | less -R
По умолчанию когда обнаруживается pipe цвета автоматически отключаются. Флаг --color=always говорит, что отключать их не нужно даже в пайпе. Флаг -R сообщает less, что нужно отображать входные цветовые escape последовательности, т.е. подсвечивать текст.

вторник, 25 декабря 2012 г.

Удаление указателей из контейнера и их уничтожение

Предположим что ваш последовательный контейнер хранит указатели и вам нужно удалить и уничтожить обьекты удовлетворяющие некоторому критерию. Если указатели не являются умными, то идиому remove + erase использовать не получится поскольку обьекты будут только удалены, но не будут уничтожены. Удаление поштучно является неплохой идеей для std::list, но это будет накладно для std::vector и std::deque, поскольку контейнеру придется многократно перемещать оставшиеся элементы так, чтоб на месте удаленный элементов не оставалось дыр, т.е. в совокупности понадобится O( N2 ) перемещений.
Ниже описано решение проблемы с использованием std::stable_partition в паре с erase. Идея в том, чтобы сначала переместить всех кандидатов на удаление в конец коллекции (оптимизация под вектор), а затем вызвать erase для всех их.
Алгоритмическая сложность: N сравнений + N перестановок в случае, если std::stable_partition сможет использовать внутренний буффер или N log N перестановок в противном случае.
Сначала обьявим функтор для уничтожения элементов в контейнере
template< class TPointer >
struct DeletePointer
{
void operator () ( TPointer item ) { delete item; }
};
Затем переходим к определению самой функции, удаляющей и уничтожающей элементы контейнера
template< class Collection, class Predicate >
void delete_erase_if( Collection& c, Predicate pred ) {
typename Collection::iterator removeBegin = std::stable_partition( c.begin(), c.end(), std::not1 ( pred ) );
std::for_each( removeBegin, c.end(), DeletePointer< typename Collection::value_type > () );
c.erase( removeBegin, c.end() );
}
Поскольку stable_partition переставлят все элементы, удовлетворяющие предекату, в начало, а нам нужно переставлять их в конец, то нам приходится как-то инвертировать предикат. Для этого в теле функции используется std::not1 из модуля <functional>.
Если ваш модуль подключает библиотеку QtCore то вы можете избавиться от функтора DeletePointer заменив вторую строчку в теле delete_erase_if на вызов qDeleteAll.
К минусам приведенной выше реализации относится то, что функция не принимает указатели на функции в качестве предиката. Для того, чтобы обойти данное ограничение, нужно просто обернуть указатель на функцию-предикат в std::ptr_fun.

понедельник, 24 декабря 2012 г.

Указатель на функцию как параметр шаблона

Предположим, что нужно взять указатель на функцию-член класса и параметризовать ею шаблон. Для этого делаем следующее:

Для удобства обьявляем тип указателя на функцию:
typedef QDateTime ( QDateTime::*DateTimeIncrement ) ( int ) const;
Обьявляем шаблон (функцию или класс), принимающий указатель на функцию как параметр
template <DateTimeIncrement Increment>
QDateTime add( QDateTime dateTime, int delta )
{
return ( dateTime.*Increment )( delta );
}
А потом можно заюзать шаблон...
inline QDateTime addDays( QDateTime dateTime, int delta ) { return add< &QDateTime::addDays >( dateTime, delta ); }
...
QDateTime tomorrow = addDays( QDateTime::currentDateTime(), 1 );

воскресенье, 25 ноября 2012 г.

Linux, как указать программе путь к .so библиотеке

Пока я разрабатывал одну библиотеку, мне нужно было как-то тестировать ее без копирования в соответствующие системные каталоги.
Идеальным выглядело решение, когда исполнительный файл с тестами и тестируемая библиотека лежат в одном каталоге, как в Windows. Проблема была в том, что в Linux это не работало - экзешник не мог найти библиотеку.

Решается это просто. экзешник нужно запускать следующей командой (при условии, что текущим каталогом является тот, где лежит экзешник с библиотекой/библиотеками):

$ LD_LIBRARY_PATH=`pwd` ./executable_name

Если и это не помогает, то попробуйте посмотреть какую именно библиотеку пытается найти ваш экзешник, вызвав команду

$ ldd executable_name

или
$ readelf -d executable_name

Скорее всего просто напросто требуется библиотека с четко прописанной версией в ее названии. Например: libMyLib.so.1 вместо libMyLib.so.1.0.0
Лечится это символическими ссылками:

$ ln -s libMyLib.so.1.0.0 libMyLib.so.1

суббота, 31 марта 2012 г.

Hello RPM

Here I'm giving a brief guidance how to create a simplest RPM file for a QT4 based application. If you want this post to be translated to English just contact me and I will do it upon first request with giving you all possible assistance in urgent case. In return I will expect your help with checking it on grammatical mistakes.

В интернете можно найти много литературы по RPM, о формате .spec файла и о том как пользоваться rpmbuild.
В этом посте я приведу краткое руководство о том как создать простейший RPM пакет не углубляясь в детали. Пост будет особенно интересен тем, кому нужно создать RPM для проекта написанного на Qt.
Итак, у меня есть приложение HelloWorld, написанное на QT 4.8 и доступное для загрузки отсюда. Минимальные требования, для сборки проекта - наличие Qt4.8 и qmake (qt и qt-devel пакеты для Fedora Linux соответственно). 
Комментарии к исходникам:
  1. Когда распакуете архив с исходниками обратите внимание что корневая папка называется "helloworld-1.0". Это первый важный момент. "helloworld" - это название приложения и название пакета, который мы сейчас будем создавать. Нужно чтобы название приложения совпадало с названием пакета. "1.0" - это версия нашего продукта. "-" между названием и версией соответствует соглашению о построении полных названий пакетов. Очень важно чтобы корневая папка именовалась как [название приложения/пакета]-[версия приложения]. Без этого вы получите ошибку на стадии %prep при сборке. От пакетов требуется, чтобы все символы названия были в нижнем регистре поэтому позаботьтесь, чтобы исполнителный файл тоже соответствовал этому требованию.
  2. В файле HelloWorld.pro обратите внимание на строчки:  
    unix {
        target.path = /$(DESTDIR)
        INSTALLS += target
    }
    На основании этой строки qmake сгенерируют инструкцию в Makefile для команды "make install". Назначение макроса DESTDIR я поясню позже. Сейчас же обратите внимание, что он начинается с символа "/". Он необходим, инача qmake допишет в Makefile еще и путь к файлу проекта, что приведет к проблемам на фазе %install.
  3. В корневом каталоге лежит скрипт configure который просто вызывает qmake. Этот скрипт будет автоматически вызываться на стадии %prep и его назначение в том, чтобы подготовить Makefile. Именно поэтому я поместил в него вызов qmake. Проследите, чтобы этот скрипт был помечен как исполняемый файл (chmod +x configure)
Для создания и проверки правильности rpm пакетов вам понадобятся rpmdevtools и rpmlint. Устанавливаем их командой
sudo yum install rpmdevtools rpmlint
Теперь создаем дерево сборки командой
rpmdev-setuptree
В результате у вас появится каталог ~/rpmbuild с дочерними каталогами SPECS, SOURCES, RPMS, SRPMS, BUILD и BUILDROOT. Информацию о назначении каталогов вы найдете на rpm.org.  Полученное дерево каталогов вы можете использовать для построения rpm пакетов для произвольных версий любых программних продуктов.

Скопируйте архив с исходниками в ~/rpmbuild/SOURCES.


Теперь переходим к самому главному. Скачайте spec файл перейдя по следующей ссылке (скачать) и положите его в папку ~/rpmbuild/SPECS.
Перейдите в этот каталог (cd ~/rpmbuild/SPECS) и запустите на исполнение команду
rpmbuild -ba helloworld.spec
В результате в папке RPMS (со смещением на текущую архитектуру) будет лежать ваш RPM с бинарниками, а в папке SRPMS - с исходниками и spec файлом. Если вам нужен только RPM с бинарниками замените -ba  на -bb.

Несколько комментариев к spec файлу:
  1. Поле Name содержит имя rpm файла, который будет сгенерирован. Это имя должно совпадать с названием приложения.
  2. Поле Source0 содержит название нашего архива с исходниками
  3. Обратите внимание на строку 
    make install DESTDIR=$RPM_BUILD_ROOT%{_bindir}
    в разделе %install. Помните, что в HelloWorld.pro мы устанавливали target.path в /$(DESTDIR)? Теперь же мы инициализируем эту переменную путем взятым из контекста сборки и передаем ее команде make install, которая в свою очередь создаст такой каталог (он будет находиться по адресу ~/rpmbuild/BUILDROOT/[полное имя пакета]/usr/bin) и скопирует туда собранный исполняемый файл. 
  4. Строка  %{_bindir}/%{name} в разделе %files инструктирует сборщик, что в результирующий RPM необходимо включить файл с именем helloworld (именно в это значение развернется макрос %name) лежащий со смещением usr/bin (значение макроса %_bindir) относительно $RPM_BUILD_ROOT (т.е. ~/rpmbuild/BUILDROOT/[полное имя пакета]). Без этой строки ваш RPM файл останется пустым.
После запуска команды rpm -i helloworld-1.0-1.fc16.x86_64.rpm программа helloworld будет установлена в папку /usr/bin (значение макроса _bindir)

В данном посте я не затронул тему патчей потому, что я в них сам еще не разобрался. Вернее практически все ясно за исключением того почему нужно класть самые старые исходники в папку с самой последней версией в названии, а потом на все на это накатывать патчи. Как-то немного странно это. Когда все выясню для себя напишу об этом.

Кроме того у описаной процедуры есть недостаток. Если нужно установить несколько файлов из одного пакета в разные места назначения, передача usr/bin через DESTDIR не очень подходит. Возможно лучше было бы захардкодить /usr/bin в  HelloWorld.pro. Другое решение расширить набор входных параметров. В общем тут тоже есь над чем подумать.

Если этот пост был полезен вам, чиркните пару слов. Также буду признателен тем кто будет давать дополнительную полезную информацию на данную тему.