/*
 * Copyright 2007-2012, Axel Dörfler, axeld@pinc-software.de.
 * Distributed under the terms of the MIT License.
 */


#include "SudokuField.h"

#include <new>
#include <stdio.h>
#include <string.h>

#include <Message.h>
#include <OS.h>


const char*
mask(uint32 set)
{
        static char text[64];
        uint32 i = 0;
        for (int32 number = 9; number > 0; number--) {
                text[i++] = set & (1UL << (number - 1)) ? number + '0' : '-';
        }

        text[i] = '\0';
        return text;
}


//      #pragma mark -


SudokuField::field::field()
        :
        hint_mask(0),
        valid_mask(~0),
        flags(0),
        value(0)
{
}


//      #pragma mark -


SudokuField::SudokuField(uint32 size)
        :
        fSize(size * size),
        fBlockSize(size)
{
        fFields = new (std::nothrow) field[fSize * fSize];
        fMaxMask = (1UL << fSize) - 1;
}


SudokuField::SudokuField(const BMessage* archive)
{
        if (archive->FindInt32("block size", (int32*)&fBlockSize) != B_OK)
                return;

        fSize = fBlockSize * fBlockSize;
        fMaxMask = (1UL << fSize) - 1;

        uint32 count = fSize * fSize;
        fFields = new (std::nothrow) field[count];
        if (fFields == NULL)
                return;

        for (uint32 i = 0; i < count; i++) {
                struct field& field = fFields[i];

                if (archive->FindInt32("value", i, (int32*)&field.value) != B_OK
                        || archive->FindInt32("valid mask", i,
                                        (int32*)&field.valid_mask) != B_OK
                        || archive->FindInt32("hint mask", i,
                                        (int32*)&field.hint_mask) != B_OK
                        || archive->FindInt32("flags", i, (int32*)&field.flags) != B_OK)
                        break;
        }
}


SudokuField::SudokuField(const SudokuField& other)
        : BArchivable(other)
{
        fSize = other.fSize;
        fBlockSize = other.fBlockSize;
        fMaxMask = other.fMaxMask;

        fFields = new (std::nothrow) field[fSize * fSize];
        if (fFields != NULL)
                memcpy(fFields, other.fFields, sizeof(field) * fSize * fSize);
}


SudokuField::~SudokuField()
{
        delete[] fFields;
}


status_t
SudokuField::InitCheck()
{
        if (fBlockSize == 0)
                return B_BAD_VALUE;
        return fFields == NULL ? B_NO_MEMORY : B_OK;
}


status_t
SudokuField::Archive(BMessage* archive, bool deep) const
{
        status_t status = BArchivable::Archive(archive, deep);
        if (status == B_OK)
                archive->AddInt32("block size", fBlockSize);
        if (status < B_OK)
                return status;

        uint32 count = fSize * fSize;
        for (uint32 i = 0; i < count && status == B_OK; i++) {
                struct field& field = fFields[i];
                status = archive->AddInt32("value", field.value);
                if (status == B_OK)
                        status = archive->AddInt32("valid mask", field.valid_mask);
                if (status == B_OK)
                        status = archive->AddInt32("hint mask", field.hint_mask);
                if (status == B_OK)
                        status = archive->AddInt32("flags", field.flags);
        }

        return status;
}


/*static*/ SudokuField*
SudokuField::Instantiate(BMessage* archive)
{
        if (!validate_instantiation(archive, "SudokuField"))
                return NULL;

        return new SudokuField(archive);
}


void
SudokuField::Reset()
{
        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        struct field& field = _FieldAt(x, y);
                        field.value = 0;
                        field.flags = 0;
                        field.hint_mask = 0;
                        field.valid_mask = fMaxMask;
                }
        }
}


status_t
SudokuField::SetTo(char base, const char* data)
{
        if (data != NULL && strlen(data) < fSize * fSize)
                return B_BAD_VALUE;

        Reset();

        if (data == NULL)
                return B_OK;

        uint32 i = 0;

        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        uint32 value = data[i++] - base;
                        if (value) {
                                struct field& field = _FieldAt(x, y);
                                field.value = value;
                                field.flags = kInitialValue;
                        }
                }
        }

        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        _ComputeValidMask(x, y, false);
                }
        }

        return B_OK;
}


void
SudokuField::SetTo(const SudokuField* field)
{
        if (field == NULL) {
                Reset();
                return;
        }

        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        _FieldAt(x, y) = field->_FieldAt(x, y);
                }
        }
}


void
SudokuField::Dump()
{
        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        if (x != 0 && x % fBlockSize == 0)
                                putchar(' ');
                        printf("%" B_PRIu32, ValueAt(x, y));
                }
                putchar('\n');
        }
}


bool
SudokuField::IsSolved() const
{
        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        if (!_ValidValueAt(x, y))
                                return false;
                }
        }

        return true;
}


bool
SudokuField::IsEmpty() const
{
        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        if (ValueAt(x, y) != 0)
                                return false;
                }
        }

        return true;
}


bool
SudokuField::IsValueCompleted(uint32 value) const
{
        uint32 count = 0;
        for (uint32 y = 0; y < fSize; y++) {
                for (uint32 x = 0; x < fSize; x++) {
                        if (ValueAt(x, y) == value)
                                count++;
                }
        }

        return count == Size();
}


void
SudokuField::SetHintMaskAt(uint32 x, uint32 y, uint32 hintMask)
{
        _FieldAt(x, y).hint_mask = hintMask;
}


uint32
SudokuField::HintMaskAt(uint32 x, uint32 y) const
{
        return _FieldAt(x, y).hint_mask;
}


bool
SudokuField::HasHint(uint32 x, uint32 y, uint32 value) const
{
        return (_FieldAt(x, y).hint_mask & (1UL << (value - 1))) != 0;
}


void
SudokuField::SetValidMaskAt(uint32 x, uint32 y, uint32 validMask)
{
        _FieldAt(x, y).valid_mask = validMask & fMaxMask;
}


uint32
SudokuField::ValidMaskAt(uint32 x, uint32 y) const
{
        return _FieldAt(x, y).valid_mask;
}


bool
SudokuField::IsValid(uint32 x, uint32 y, uint32 value) const
{
        return (_FieldAt(x, y).valid_mask & (1UL << (value - 1))) != 0;
}


void
SudokuField::SetFlagsAt(uint32 x, uint32 y, uint32 flags)
{
        _FieldAt(x, y).flags = flags;
}


uint32
SudokuField::FlagsAt(uint32 x, uint32 y) const
{
        return _FieldAt(x, y).flags;
}


bool
SudokuField::IsInitialValue(uint32 x, uint32 y) const
{
        return (_FieldAt(x, y).flags & kInitialValue) != 0;
}


void
SudokuField::SetValueAt(uint32 x, uint32 y, uint32 value, bool setSolved)
{
        _FieldAt(x, y).value = value;
        _FieldAt(x, y).hint_mask = 0;
        _UpdateValidMaskChanged(x, y, setSolved);
}


uint32
SudokuField::ValueAt(uint32 x, uint32 y) const
{
        return _FieldAt(x, y).value;
}


bool
SudokuField::_ValidValueAt(uint32 x, uint32 y) const
{
        uint32 value = _FieldAt(x, y).value;
        if (!value)
                return false;

        value = 1UL << (value - 1);
        return (_FieldAt(x, y).valid_mask & value) != 0;
}


void
SudokuField::_ComputeValidMask(uint32 x, uint32 y, bool setSolved)
{
        if (ValueAt(x, y))
                return;

        // check row

        uint32 foundMask = 0;
        for (uint32 i = 0; i < fSize; i++) {
                uint32 value = ValueAt(i, y);
                if (value && _ValidValueAt(i, y))
                        foundMask |= 1UL << (value - 1);
        }

        // check column

        for (uint32 i = 0; i < fSize; i++) {
                uint32 value = ValueAt(x, i);
                if (value && _ValidValueAt(x, i))
                        foundMask |= 1UL << (value - 1);
        }

        // check block

        uint32 offsetX = x / fBlockSize * fBlockSize;
        uint32 offsetY = y / fBlockSize * fBlockSize;

        for (uint32 partY = 0; partY < fBlockSize; partY++) {
                for (uint32 partX = 0; partX < fBlockSize; partX++) {
                        uint32 value = ValueAt(partX + offsetX, partY + offsetY);
                        if (value && _ValidValueAt(partX + offsetX, partY + offsetY))
                                foundMask |= 1UL << (value - 1);
                }
        }

        SetValidMaskAt(x, y, ~foundMask);

        if (setSolved) {
                // find the one set bit, if not more
                uint32 value = 0;
                for (uint32 i = 0; i < fSize; i++) {
                        if ((foundMask & (1UL << i)) == 0) {
                                if (value != 0) {
                                        value = 0;
                                        break;
                                }

                                value = i + 1;
                        }
                }
                if (value != 0)
                        SetValueAt(x, y, value, true);
        }
}


void
SudokuField::_UpdateValidMaskChanged(uint32 x, uint32 y, bool setSolved)
{
        // update row

        for (uint32 i = 0; i < fSize; i++) {
                _ComputeValidMask(i, y, setSolved);
        }

        // update column

        for (uint32 i = 0; i < fSize; i++) {
                if (i == y)
                        continue;

                _ComputeValidMask(x, i, setSolved);
        }

        // update block

        uint32 offsetX = x / fBlockSize * fBlockSize;
        uint32 offsetY = y / fBlockSize * fBlockSize;

        for (uint32 partY = 0; partY < fBlockSize; partY++) {
                for (uint32 partX = 0; partX < fBlockSize; partX++) {
                        if (partX + offsetX == x || partY + offsetY == y)
                                continue;

                        _ComputeValidMask(partX + offsetX, partY + offsetY, setSolved);
                }
        }
}


const SudokuField::field&
SudokuField::_FieldAt(uint32 x, uint32 y) const
{
        if (x >= fSize || y >= fSize)
                debugger("field outside bounds");

        return fFields[x + y * fSize];
}


SudokuField::field&
SudokuField::_FieldAt(uint32 x, uint32 y)
{
        if (x >= fSize || y >= fSize)
                debugger("field outside bounds");

        return fFields[x + y * fSize];
}