inversion_tree.cpp

// The MIT License (MIT)

// Copyright (c) 2016 Daniel Fu

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

//
// Created by 理 傅 on 2017/1/1.
//

#include "inversion_tree.h"
#include <iostream>

inversionTree inversionTree::newInversionTree(int dataShards,
                                              int parityShards) {
    inversionTree tree;
    tree.m_root.m_children.resize(dataShards + parityShards, nullptr);
    tree.m_root.m_matrix = matrix::identityMatrix(dataShards);
    return tree;
}

matrix inversionTree::GetInvertedMatrix(std::vector<int> &invalidIndices) {
    if (invalidIndices.size() == 0) {
        return m_root.m_matrix;
    }

    return m_root.getInvertedMatrix(invalidIndices, 0);
}

int inversionTree::InsertInvertedMatrix(std::vector<int> &invalidIndices,
                                        matrix &matrix, int shards) {
    // If no invalid indices were given then we are done because the
    // m_root node is already set with the identity matrix.
    if (invalidIndices.size() == 0) {
        return -1;
    }

    if (!matrix.IsSquare()) {
        return -2;
    }

    // Recursively create nodes for the inverted matrix in the tree until
    // we reach the node to insert the matrix to.  We start by passing in
    // 0 as the parent index as we start at the m_root of the tree.
    m_root.insertInvertedMatrix(invalidIndices, matrix, shards, 0);

    return 0;
}

matrix inversionNode::getInvertedMatrix(std::vector<int> &invalidIndices,
                                        int parent) {
    // Get the child node to search next from the list of m_children.  The
    // list of m_children starts relative to the parent index passed in
    // because the indices of invalid rows is sorted (by default).  As we
    // search recursively, the first invalid index gets popped off the list,
    // so when searching through the list of m_children, use that first invalid
    // index to find the child node.
    int firstIndex = invalidIndices[0];
    auto node = m_children[firstIndex - parent];

    // If the child node doesn't exist in the list yet, fail fast by
    // returning, so we can construct and insert the proper inverted matrix.
    if (node == nullptr) {
        return matrix{};
    }

    // If there's more than one invalid index left in the list we should
    // keep searching recursively.
    if (invalidIndices.size() > 1) {
        // Search recursively on the child node by passing in the invalid
        // indices with the first index popped off the front.  Also the parent
        // index to pass down is the first index plus one.
        std::vector<int> v(invalidIndices.begin() + 1, invalidIndices.end());
        return node->getInvertedMatrix(v, firstIndex + 1);
    }

    // If there aren't any more invalid indices to search, we've found our
    // node.  Return it, however keep in mind that the matrix could still be
    // nil because intermediary nodes in the tree are created sometimes with
    // their inversion matrices uninitialized.
    // std::cout << "return cached matrix:" << std::endl;
    return node->m_matrix;
}

void inversionNode::insertInvertedMatrix(std::vector<int> &invalidIndices,
                                         struct matrix &matrix, int shards,
                                         int parent) {
    // As above, get the child node to search next from the list of m_children.
    // The list of m_children starts relative to the parent index passed in
    // because the indices of invalid rows is sorted (by default).  As we
    // search recursively, the first invalid index gets popped off the list,
    // so when searching through the list of m_children, use that first invalid
    // index to find the child node.
    int firstIndex = invalidIndices[0];
    auto node = m_children[firstIndex - parent];

    // If the child node doesn't exist in the list yet, create a new
    // node because we have the writer lock and add it to the list
    // of m_children.
    if (node == nullptr) {
        // Make the length of the list of m_children equal to the number
        // of shards minus the first invalid index because the list of
        // invalid indices is sorted, so only this length of errors
        // are possible in the tree.
        node = std::make_shared<inversionNode>();
        node->m_children.resize(shards - firstIndex, nullptr);
        m_children[firstIndex - parent] = node;
    }

    // If there's more than one invalid index left in the list we should
    // keep searching recursively in order to find the node to add our
    // matrix.
    if (invalidIndices.size() > 1) {
        // As above, search recursively on the child node by passing in
        // the invalid indices with the first index popped off the front.
        // Also the total number of shards and parent index are passed down
        // which is equal to the first index plus one.
        std::vector<int> v(invalidIndices.begin() + 1, invalidIndices.end());
        node->insertInvertedMatrix(v, matrix, shards, firstIndex + 1);
    } else {
        node->m_matrix = matrix;
    }
}