Последовательная замена множества уникальных значений на другие без возникновения дубликатов

[mazzy]

Цитата:

Сообщение от gl00mie

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

ЕСЛИ же говорить о математической постановке задачи именно с множествами (не пользуясь хаками нарушения уникальности внутри транзакции),
ТО возникает интересный вопрос - бывают ли такие множества, когда замену произвести нельзя?

Для вырожденных случаев можно легко привести пример таких множеств.
Например, множество {1, 2} нельзя последовательно заменить на множество {2, 1} с сохранением уникальности на каждом шаге.

Как должен вести себя алгоритм для таких множеств с математической точки зрения?
Как определить, что множества именно такие?

[gl00mie]

Цитата:

Сообщение от mazzy

Для вырожденных случаев можно легко привести пример таких множеств. Например, множество {1, 2} нельзя последовательно заменить на множество {2, 1} с сохранением уникальности на каждом шаге.
Как должен вести себя алгоритм для таких множеств с математической точки зрения? Как определить, что множества именно такие?

На счет математической стороны вопроса - не знаю У меня соответствие исходных и конечных значений не задано жестко, поэтому заменять можно произвольным образом, кроме того, обожаемые мной Set'ы в Аксапте всегда отсортированы, так что там {1, 2} и {2, 1} тождественны. Для тождественных множеств исходных и конечных значений метод возвращает пустой список - заменять ничего не нужно. К слову, щас подумал еще о том, что пары, где исходное и конечное значение совпадают, тоже не следовало бы включать в результирующий список; у меня этот случай отлавливался в другом месте.

[mazzy]

Цитата:

Сообщение от gl00mie

обожаемые мной Set'ы в Аксапте всегда отсортированы, так что там {1, 2} и {2, 1} тождественны.

М-м-м? Т.е. множества еще и упорядочены?

все равно что-то не то.
адаптировал метод класса в job'ик. плюс добавил человеческий вывод в инфолог.

задал множества {1,2} и {2,3}
получил срабатывание assert + странные результаты.


и все-таки: почему последовательно, а не в одной транзакции?
может все-таки добавить поле с новым значением, и тупо заменить у каждой записи?

/// <summary>
///     возвращает список пар [исходное значение, новое значение] для последовательной замены исходных значений на
///     новые таким образом, чтобы на любом шаге замены в изменяемом множестве значений не возникало дубликатов
///     может использоваться, к примеру, для перебивки значений поля таблицы, на котором висит уникальный индекс
/// </summary>
/// <param name="_setOfValues2Replace">
///     множество значений, подлежащих замене
///     должно быть непустым и иметь простой значимый (не ссылочный) базовый тип
/// </param>
/// <param name="_setOfNewValues">
///     множество новых значений, на которые надо заменить исходные
///     может полностью или частично пересекаться со значениями, подлежащими замене
///     должно иметь тот же базовый тип и число элементов, что и _setOfValues2Replace
/// </param>
/// <returns>
///     список контейнеров [исходное значение, новое значение] для последовательной замены в нужном порядке
///     либо пустой список, если замена невозможна (к примеру, множества исходных и новых значений тождественны)
/// </returns>
/// <remarks>
///     ACHTUNG!!! исходные множества изменяются!
/// </remarks>
/// <exception cref="Exception::Error">
///     выбрасывается, если входные параметры не соответствуют предусловиям
/// </exception>
static void DEV_getListOfValueReplacementPairs(Args args)
{
    Set _setOfValues2Replace = new Set(Types::Integer);
    Set _setOfNewValues = new Set(Types::Integer);

    Set         setOfUniqueNewValues;
    Set         setOfCommonValues;
    SetIterator setIterNew;
    SetIterator setIterOld;
    anytype     oldValue;
    anytype     newValue;
    Types       baseType;
    Counter     nElements;
    List        ret;
    ;
    //////////////////
    /**/
    _setOfValues2Replace.add(1);      _setOfNewValues.add(2);
    _setOfValues2Replace.add(2);      _setOfNewValues.add(1);
    /*
    _setOfValues2Replace.add(0);      _setOfNewValues.add(1);
    _setOfValues2Replace.add(1);      _setOfNewValues.add(2);
    _setOfValues2Replace.add(3);      _setOfNewValues.add(3);
    _setOfValues2Replace.add(7);      _setOfNewValues.add(4);
    _setOfValues2Replace.add(9);      _setOfNewValues.add(5);
    _setOfValues2Replace.add(15);     _setOfNewValues.add(6);
    _setOfValues2Replace.add(20);     _setOfNewValues.add(7);
    */

    //////////////////

    if (_setOfValues2Replace)
    {
        baseType    = _setOfValues2Replace.typeId();
        nElements   = _setOfValues2Replace.elements();
    }
    // проверка предусловий
    if (!(      _setOfNewValues
        &&      _setOfValues2Replace
        &&      nElements   >  0
        &&      nElements   == _setOfNewValues.elements()
        &&      baseType    == _setOfNewValues.typeId()
        &&  (   baseType    == Types::Date
            ||  baseType    == Types::Enum
            ||  baseType    == Types::Guid
            ||  baseType    == Types::Int64
            ||  baseType    == Types::Integer
            ||  baseType    == Types::Real
            ||  baseType    == Types::RString
            ||  baseType    == Types::String
            ||  baseType    == Types::Time
            ||  baseType    == Types::UtcDateTime
            ||  baseType    == Types::VarString
            )
       ))
    {
        throw error( Error::wrongUseOfFunction( funcname() ) );
    }
    ret = new List( Types::Container );
    setOfCommonValues = Set::intersection( _setOfValues2Replace, _setOfNewValues );
    if (setOfCommonValues.elements() < nElements)
    {
        if (!setOfCommonValues.empty())
        {
            setOfUniqueNewValues = Set::difference( _setOfNewValues, setOfCommonValues );
            setIterNew = new SetIterator( setOfUniqueNewValues );
            setIterOld = new SetIterator( setOfCommonValues );
            while (setIterNew.more())
            {
                if (!setIterOld.more())
                {
                    break;
                }
                oldValue = setIterOld.value();
                newValue = setIterNew.value();
                ret.addEnd( [ oldValue, newValue ] );
                _setOfNewValues.remove( newValue );
                _setOfValues2Replace.remove( oldValue );
                setOfUniqueNewValues.remove( newValue );
                if (_setOfNewValues.in( oldValue ))
                {
                    setOfUniqueNewValues.add( oldValue );
                    setIterNew.begin();
                }
                else
                {
                    setIterNew.next();
                }
                setIterOld.next();
            }
            Debug::assert( _setOfValues2Replace.elements() == setOfUniqueNewValues.elements() );
        }
        else
        {
            setIterNew = new SetIterator( _setOfNewValues );
        }
        // оставшиеся на замену значения никак не пересекаются с новыми
        setIterNew.begin();
        setIterOld = new SetIterator( _setOfValues2Replace );
        while (setIterNew.more() && setIterOld.more())
        {
            oldValue = setIterOld.value();
            newValue = setIterNew.value();
            ret.addEnd( [ oldValue, newValue ] );
            setIterNew.next();
            setIterOld.next();
        }
        Debug::assert( ret.elements() == nElements );
    }

    info(ret.definitionString());
    info(ret.xml());
}

[gl00mie]

Цитата:

Сообщение от mazzy

задал множества {1,2} и {2,3}, получил срабатывание assert + странные результаты.

Пардон, когда переносил код с рабочего приложения для "приукрашивания" комментариями и проч., забыл перенести последнюю версию, в которой не был пропущен вызов setIterOld.next() внутри первого цикла - извечные проблемы с итераторами Поправил код в исходном сообщении. Собственно, можно было бы использовать в данном случае SetEnumerator, но решил оставить итератор для единообразия кода...

[mazzy]

Цитата:

Сообщение от gl00mie

извечные проблемы с итераторами

если честно, то очень хочется использовать рекурсию.
но рекурсия - слишком расточительное удовольствие.

может изменить постановку? может не нужно списка, а достаточно всего лишь одной пары?
Тогда
1. в метод передаются два множества.
2. метод возвращает одну пару для замены (или пустое значение)
3. метод (или вызывающий код) убирает полученную пару из множеств
4. снова вызвать метод

тогда на псевдокоде это будет выглядеть так

[oldKey, newKey] getPair(oldSet, NewSet)
{
    if( oldSet.empty() )
        return []; // нечего менять - поэтому ничего менять не нужно 

    if( newSet.empty() )
        return []; // не на что менять - поэтому ничего менять не нужно 

    seedSet = Set::difference( newSet, oldSet ); // зародыши: новые значения будут браться отсюда
    if( seedSet.empty() )
        return []; // нет новых значений (уже использованы или множества совпадают) - ничего менять не нужно 

    deadSet = Set::difference( oldSet, newSet ); // мертвенькие: они исчезнут
    if( deadSet.empty() )
        return []; // все старые значения уже есть в новых (или множества совпадают) - ничего менять не нужно 

    newKey = seedSet.anyValue(); // любое значение из множества зародышей
    oldKey = deadSet.anyValue(); // любое значение из множества мертвеньких
    return [oldKey, newKey];
}

pair = getPair( oldSet, newSet );
while( pair != [] )
{
    [oldKey, newKey] = pair;
    // do something with oldKey, newKey

    // next iteration
    oldSet.remove(oldKey);
    newSet.remove(newKey);
    pair = getPair( oldSet, newSet );
}

другими словами:
а) если множество старых и множество новых совпадают, то ничего менять не нужно
б) стараемся совпадающее не трогать (чтобы уменьшить число операций с базой)

как-то так.
главное - по ходу множества уменьшаются. Типа псевдорекурсия. И никаких итераторов

в качестве дальнейшей оптимизации можно подумать о совмещении difference+anyValue.
Но не уверен, что реализованный на X++ метод difference получится быстрее, чем в ядре.

============
Спасибо за интересную задачу.
У меня RU6 поставился. Пойду спать