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;

}

}

}

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

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


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

Есть команда выводящая результаты с подсветкой / раскраской - скажем это yum search, но выхлоп очень большой и нужно использовать пейджер less. Однако текст, прошедший через less становится одноцветным. Как сделать так, чтобы он оставался цветным. Вот ответ:

yum --color=always search your_text | less -R

По умолчанию когда обнаруживается pipe цвета автоматически отключаются. Флаг --color=always говорит, что отключать их не нужно даже в пайпе. Флаг -R сообщает less, что нужно отображать входные цветовые escape последовательности, т.е. подсвечивать текст.