/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

#ifndef IGBASE_INCL
#define IGBASE_INCL

#include <stddef.h>
#include <stdint.h>
#include "env/TRMemory.hpp"
#include "infra/IGNode.hpp"

class TR_BitVector;

typedef uint64_t IMIndex;

// Number of pre-computed high indices into the interference matrix.
//
#define NUM_PRECOMPUTED_HIGH_INDICES 64

class TR_IGBase {
private:
    // Number of nodes in the graph.
    //
    IGNodeIndex _numNodes;

    // The _interferenceMatrix is a lower triangular bit matrix that summarizes interferences
    // between nodes.  For a node pair (L,H), the corresponding bit should be set if the two
    // nodes interfere.
    //
    // The low and high node indices begin at 0.
    //
    // The bit matrix is implemented with a bit vector, as follows:
    //
    //                       Low Node
    //                        Index
    //
    //                  0  1  2  3  4  5 ...
    //                +---------------------
    //               0| X                         The bit position for a node pair (L,H)
    //               1| 0  X                      can be computed with:
    //   High Node   2| 1  2  X
    //     Index     3| 3  4  5  X                   bit = L + ((H-1)*H)/2
    //               4| 6  7  8  9  X
    //               5|10 11 12 13 14  X
    //               :|
    //               :|
    //
    // The total number of bits required for N nodes = N * (N-1) / 2
    //
    TR_BitVector *_interferenceMatrix;
    static IMIndex _highIndexTable[NUM_PRECOMPUTED_HIGH_INDICES];

    // For graph colouring, attempt to colour the graph using this many colours.
    //
    IGNodeColour _numColours;

    // Actual number of colours that graph was coloured in.
    //
    IGNodeColour _numberOfColoursUsedToColour;

protected:
    IMIndex getNodePairToBVIndex(IGNodeIndex index1, IGNodeIndex index2);
    IMIndex getOrderedNodePairToBVIndex(IGNodeIndex low, IGNodeIndex high);

public:
    TR_ALLOC(TR_Memory::IGBase)

    TR_IGBase()
        : _numNodes(0)
        , _numColours(0)
        , _numberOfColoursUsedToColour(0)
        , _interferenceMatrix(NULL)
    {}

    IGNodeIndex getNumNodes() { return _numNodes; }

    IGNodeIndex setNumNodes(IGNodeIndex n) { return (_numNodes = n); }

    IGNodeIndex incNumNodes() { return (++_numNodes); }

    bool isEmpty() { return (_numNodes == 0); }

    IGNodeColour getNumColours() { return _numColours; }

    IGNodeColour setNumColours(IGNodeColour c) { return (_numColours = c); }

    TR_BitVector *getInterferenceMatrix() { return _interferenceMatrix; }

    void setInterferenceMatrix(TR_BitVector *im) { _interferenceMatrix = im; }

    IGNodeColour getNumberOfColoursUsedToColour() { return _numberOfColoursUsedToColour; }

    IGNodeColour setNumberOfColoursUsedToColour(IGNodeColour c) { return (_numberOfColoursUsedToColour = c); }
};
#endif
