text: //------------------------------------------------------------------------------
  // GB_build: build a matrix
  //------------------------------------------------------------------------------
  
  // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2022, All Rights Reserved.
  // SPDX-License-Identifier: Apache-2.0
  
  //------------------------------------------------------------------------------
  
  // CALLED BY: GrB_Matrix_build_*, GrB_Vector_build_*,
  //            GxB_Matrix_build_Scalar, GxB_Vector_build_Scalar
  // CALLS:     GB_builder
  
  // GrB_Matrix_build_* and GrB_Vector_build_* always build a non-iso matrix.
  // X is non-iso, and T is non-iso on output.  dup can be a valid binary
  // operator, NULL, or the special binary operator GxB_IGNORE_DUP.
  // For a non-iso build, dup may be NULL, which indicates that duplicates are
  // not expected.  If any duplicates do appear, an error is reported.
  // If dup is GxB_IGNORE_DUP, then duplicates are discarded.  If (i,j,x1)
  // appears as the (k1)th tuple, and (i,j,x2) as the (k2)th tuple, and
  // k1 < k2, then the first tuple is ignored and C(i,j) is equal to x2.
  
  // GxB_Matrix_build_Scalar and GxB_Vector_build_Scalar always build an iso
  // matrix:  X is iso, only the first entry X [0] is used, and dup does not
  // appear (it is passed here as GxB_IGNORE_DUP).  The matrix T is iso on
  // output.  For an iso build, duplicates are discarded.
  
  // For all of these cases, the tuples must be checked for duplicates.  They
  // might be sorted on input, so this condition is checked and exploited if that
  // condition is found.  All of these conditions are checked in GB_builder.
  
  // GB_build constructs a matrix C from a list of indices and values.  Any
  // duplicate entries with identical indices are assembled using the binary dup
  // operator provided on input, or discarded if dup is NULL or GxB_IGNORE_DUP.
  // All three types (x,y,z for z=dup(x,y)) must be identical.  The types of dup,
  // X, and C must all be compatible.
  
  // Duplicates are assembled using T(i,j) = dup (T (i,j), X (k)) into a
  // temporary matrix T that has the same type as the dup operator.  The
  // GraphBLAS spec requires dup to be associative so that entries can be
  // assembled in any order.  There is no way to check this condition if dup is a
  // user-defined operator.  It could be checked for built-in operators, but the
  // GraphBLAS spec does not require this condition to cause an error so that is
  // not done here.  If dup is not associative, the GraphBLAS spec states that
  // the results are not defined.
  
  // SuiteSparse:GraphBLAS provides a well-defined order of assembly, however.
  // For a CSC format, entries in [I,J,X] are first sorted in increasing order of
  // row and column index via a stable sort, with ties broken by the position of
  // the tuple in the [I,J,X] list.  If duplicates appear, they are assembled in
  // the order they appear in the [I,J,X] input.  That is, if the same indices i
  // and j appear in positions k1, k2, k3, and k4 in [I,J,X], where k1 < k2 < k3
  // < k4, then the following operations will occur in order:
  
  //      T (i,j) = X (k1) ;
  //      T (i,j) = dup (T (i,j), X (k2)) ;
  //      T (i,j) = dup (T (i,j), X (k3)) ;
  //      T (i,j) = dup (T (i,j), X (k4)) ;
  
  // This is a well-defined order but the user should not depend upon it since
  // the GraphBLAS spec does not require this ordering.  Results may differ in
  // different implementations of GraphBLAS.
  
  // However, with this well-defined order, the SECOND operator will result in
  // the last tuple overwriting the earlier ones.  This is relied upon internally
  // by GB_wait.
  
  // After the matrix T is assembled, it is typecasted into the type of C, the
  // final output matrix.  No typecasting is done during assembly of duplicates,
  // since mixing the two can break associativity and lead to unpredictable
  // results.  Note that this is not the case for GB_wait, which must typecast
  // each tuple into its output matrix in the same order they are seen in the
  // [I,J,X] pending tuples.
  
  // On input, C must not be NULL.  C->type, C->vlen, C->vdim and C->is_csc must
  // be valid on input and are unchanged on output.  C must not have any existing
  // entries on input (GrB_*_nvals (C) must return zero, per the specification).
  // However, all existing content in C is freed.
  
  // The list of numerical values is given by the void * X array and its type,
  // xtype.  The latter is defined by the actual C type of the X parameter in
  // the user-callable functions.  However, for user-defined types, there is no
  // way of knowing that the X array has the same type as dup or C, since in that
  // case X is just a void * pointer.  Behavior is undefined if the user breaks
  // this condition.
  
  // C is returned as hypersparse or non-hypersparse, depending on the number of
  // non-empty vectors of C.  If C has very few non-empty vectors, then it is
  // returned as hypersparse.  Only if the number of non-empty vectors is
  // Omega(nh) is C returned as non-hypersparse, which implies nvals is Omega(n),
  // where n = # of columns of C if CSC, or # of rows if CSR.  As a result, the
  // time taken by this function is just O(nvals*log(nvals)), regardless of what
  // format C is returned in.
  
  // The input arrays I, J, and X are not modified.
  
  #define GB_FREE_ALL GrB_Matrix_free (&T) ;
  #include "GB_build.h"
  
  GrB_Info GB_build               // build matrix
  (
      GrB_Matrix C,               // matrix to build
      const GrB_Index *I,         // row indices of tuples
      const GrB_Index *J,         // col indices of tuples (NULL for vector)
      const void *X,              // values, size 1 if iso
      const GrB_Index nvals,      // number of tuples
      const GrB_BinaryOp dup,     // binary op to assemble duplicates (or NULL)
      const GrB_Type xtype,       // type of X array
      const bool is_matrix,       // true if C is a matrix, false if GrB_Vector
      const bool X_iso,           // if true the C is iso and X has size 1 entry
      GB_Context Context
  )
  {
  
      //--------------------------------------------------------------------------
      // check inputs
      //--------------------------------------------------------------------------
  
      // check C
      GrB_Info info ;
      ASSERT (C != NULL) ;
      if (GB_nnz (C) > 0 || GB_PENDING (C))
      { 
          // The matrix has existing entries.  This is required by the GraphBLAS
          // API specification to generate an error, so the test is made here.
          // However, any existing content is safely freed immediately below, so
          // this test is not required, except to conform to the spec.  Zombies
          // are excluded from this test.
          GB_ERROR (GrB_OUTPUT_NOT_EMPTY,
              "Output already has %s", "existing entries") ;
      }
  
      // check I
      GB_RETURN_IF_NULL (I) ;
      if (I == GrB_ALL)
      { 
          GB_ERROR (GrB_INVALID_VALUE, "Row indices cannot be %s", "GrB_ALL") ;
      }
  
      // check J
      if (is_matrix)
      {
          GB_RETURN_IF_NULL (J) ;
          if (J == GrB_ALL)
          { 
              GB_ERROR (GrB_INVALID_VALUE, "Column indices cannot be %s",
                  "GrB_ALL") ;
          }
      }
      else
      { 
          // only G*B_Vector_build_* calls this function with J == NULL
          ASSERT (J == NULL) ;
      }
  
      // check X
      GB_RETURN_IF_NULL (X) ;
  
      if (nvals == GxB_RANGE || nvals == GxB_STRIDE || nvals == GxB_BACKWARDS)
      { 
          GB_ERROR (GrB_INVALID_VALUE, "nvals cannot be %s",
              "GxB_RANGE, GxB_STRIDE, or GxB_BACKWARDS") ;
      }
  
      if (nvals > GB_NMAX)
      { 
          // problem too large
          GB_ERROR (GrB_INVALID_VALUE, "Problem too large: nvals " GBu
              " exceeds " GBu, nvals, GB_NMAX) ;
      }
  
      //--------------------------------------------------------------------------
      // check the types
      //--------------------------------------------------------------------------
  
      // C and X must be compatible
      if (!GB_Type_compatible (xtype, C->type))
      { 
          GB_ERROR (GrB_DOMAIN_MISMATCH,
              "Value(s) of type [%s] cannot be typecast to matrix of type"
              " [%s]\n", xtype->name, C->type->name) ;
      }
  
      //--------------------------------------------------------------------------
      // check the dup operator
      //--------------------------------------------------------------------------
  
      GrB_BinaryOp dup2 ;
      bool discard_duplicates = (dup == NULL || dup == GxB_IGNORE_DUP) ;
  
      if (discard_duplicates)
      { 
  
          //----------------------------------------------------------------------
          // discard all duplicates
          //----------------------------------------------------------------------
  
          dup2 = NULL ;
  
      }
      else
      { 
  
          //----------------------------------------------------------------------
          // "sum" up duplicates using the binary dup operator
          //----------------------------------------------------------------------
  
          dup2 = dup ;
          GB_RETURN_IF_FAULTY (dup) ;
  
          if (GB_OP_IS_POSITIONAL (dup))
          { 
              // dup operator cannot be a positional op
              GB_ERROR (GrB_DOMAIN_MISMATCH, "Positional op z=%s(x,y) "
                  "not supported as dup op\n", dup->name) ;
          }
  
          ASSERT_BINARYOP_OK (dup, "dup for assembling duplicates", GB0) ;
  
          // check types of dup
          if (dup->xtype != dup->ztype || dup->ytype != dup->ztype)
          { 
              // all 3 types of z = dup (x,y) must be the same.  dup must also be
              // associative but there is no way to check this in general.
              GB_ERROR (GrB_DOMAIN_MISMATCH, "All domains of dup "
                  "operator for assembling duplicates must be identical.\n"
                  "operator is: [%s] = %s ([%s],[%s])", dup->ztype->name,
                  dup->name, dup->xtype->name, dup->ytype->name) ;
          }
  
          // the type of C and dup must be compatible
          if (!GB_Type_compatible (C->type, dup->ztype))
          { 
              GB_ERROR (GrB_DOMAIN_MISMATCH,
                  "Operator [%s] for assembling duplicates has type [%s],\n"
                  "cannot be typecast to entries in output of type [%s]",
                  dup->name, dup->ztype->name, C->type->name) ;
          }
      }
  
      //--------------------------------------------------------------------------
      // free all content of C
      //--------------------------------------------------------------------------
  
      // the type, dimensions, hyper_switch, bitmap_switch and sparsity control
      // are still preserved in C.
      GB_phbix_free (C) ;
  
      //--------------------------------------------------------------------------
      // build the matrix T
      //--------------------------------------------------------------------------
  
      // T is always built as hypersparse.  Its type is the same as the z output
      // of the z=dup(x,y) operator if dup is present, or xtype if dup is NULL.
      // If C->type differs from T->type, it is typecasted by
      // GB_transplant_conform.
  
      // X must be treated as read-only, so GB_builder is not allowed to
      // transplant it into T->x.
  
      int64_t *no_I_work = NULL ; size_t I_work_size = 0 ;
      int64_t *no_J_work = NULL ; size_t J_work_size = 0 ;
      GB_void *no_X_work = NULL ; size_t X_work_size = 0 ;
      struct GB_Matrix_opaque T_header ;
      GrB_Matrix T = NULL ;
      GB_CLEAR_STATIC_HEADER (T, &T_header) ;
      GrB_Type ttype = (discard_duplicates) ? xtype : dup->ztype ;
  
      GB_OK (GB_builder (
          T,              // create T using a static header
          ttype,          // the type of T
          C->vlen,        // T->vlen = C->vlen
          C->vdim,        // T->vdim = C->vdim
          C->is_csc,      // T has the same CSR/CSC format as C
          &no_I_work,     // I_work_handle, not used here
          &I_work_size,
          &no_J_work,     // J_work_handle, not used here
          &J_work_size,
          &no_X_work,     // X_work_handle, not used here
          &X_work_size,
          false,          // known_sorted: not yet known
          false,          // known_no_duplicates: not yet known
          0,              // I_work, J_work, and X_work not used here
          is_matrix,      // true if T is a GrB_Matrix
          (int64_t *) ((C->is_csc) ? I : J),  // size nvals
          (int64_t *) ((C->is_csc) ? J : I),  // size nvals, or NULL for vector
          (const GB_void *) X,                // values, size nvals or 1 if iso
          X_iso,          // true if X is iso
          nvals,          // number of tuples
          dup2,           // operator to assemble duplicates (may be NULL)
          xtype,          // type of the X array
          Context
      )) ;
  
      //--------------------------------------------------------------------------
      // return an error if any duplicates found when they were not expected
      //--------------------------------------------------------------------------
  
      int64_t tnvals = GB_nnz (T) ;
      if (dup == NULL && nvals != tnvals)
      { 
          // T has been successfully built by ignoring the duplicate values, via
          // the implicit SECOND dup operator.  If the # of entries in T does not
          // match nvals, then duplicates have been detected.  In the v2.0 C API,
          // this is an error condition.  If the user application wants the C
          // matrix returned with duplicates discarded, use dup = GxB_IGNORE_DUP
          // instead. 
          GB_FREE_ALL ;
          GB_ERROR (GrB_INVALID_VALUE, "Duplicates appear (" GBd ") but dup "
              "is NULL", ((int64_t) nvals) - tnvals) ;
      }
  
      //--------------------------------------------------------------------------
      // determine if T is iso, for non-iso build
      //--------------------------------------------------------------------------
  
      // GxB_Matrix_build_Scalar and GxB_Vector_build_Scalar always build an iso
      // matrix T, so this test is skipped (X_iso is true in that case).
      // GrB_Matrix_build_[TYPE] and GrB_Vector_build_[TYPE] may have just
      // created an iso-valued matrix T, but this is not yet known.  X_iso is
      // false for these methods.  Since it has not yet been conformed to its
      // final sparsity structure, the matrix T is hypersparse, not bitmap.  It
      // has no zombies or pending tuples, so GB_iso_check does need to handle
      // those cases.  T->x [0] is the new iso value of T.
  
      if (!X_iso && GB_iso_check (T, Context))
      { 
          // All entries in T are the same; convert T to iso
          GBURBLE ("(post iso) ") ;
          T->iso = true ;
          GB_OK (GB_convert_any_to_iso (T, NULL, Context)) ;
      }
  
      //--------------------------------------------------------------------------
      // transplant and typecast T into C, conform C, and free T
      //--------------------------------------------------------------------------
  
      ASSERT (GB_IS_HYPERSPARSE (T)) ;
      ASSERT (!GB_ZOMBIES (T)) ;
      ASSERT (!GB_JUMBLED (T)) ;
      ASSERT (!GB_PENDING (T)) ;
      return (GB_transplant_conform (C, C->type, &T, Context)) ;
  }
  
  