// Author:  Douglas Wilhelm Harder
// Copyright (c) 2009 by Douglas Wilhelm Harder.  All rights reserved.

/***************************************************
 * Return true if the matrix is lower triangular,
 * false otherwise.
 *
 * Run time:   O( min( M, N ) )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_lower_triangular() const {
	for ( int i = 0; i < minMN - 1; ++i ) {
		if ( row_index[i] != row_index[i + 1] && column_index[row_index[i + 1] - 1] > i ) {
			return false;
		}
	}

	return true;
}

/***************************************************
 * Return true if the matrix is upper triangular,
 * and false otherwise.
 *
 * Run time:   O( min( M, N ) )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_upper_triangular() const {
	for ( int i = 1; i < minMN; ++i ) {
		if ( row_index[i] != row_index[i + 1] && column_index[row_index[i]] < i ) {
			return false;
		}
	}

	return row_index[minMN] == row_index[M];
}

/***************************************************
 * Return true if the matrix is strictly lower
 * triangular, and false otherwise.
 *
 * Run time:   O( min( M, N ) )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_strict_lower_triangular() const {
	if ( is_lower_triangular() ) {
		for ( int i = 0; i < minMN; ++i ) {
			if ( diagonal[i] != 0 ) {
				return false;
			}
		}

		return true;
	} else {
		return false;
	}
}

/***************************************************
 * Return true if the matrix is strictly upper
 * triangular, and false otherwise.
 *
 * Run time:   O( min( M, N ) )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_strict_upper_triangular() const {
	if ( is_upper_triangular() ) {
		for ( int i = 0; i < M; ++i ) {
			if ( diagonal[i] != 0 ) {
				return false;
			}
		}

		return true;
	} else {
		return false;
	}
}

/***************************************************
 * Return true if the matrix is a diagonal matrix,
 * false otherwise.
 *
 * Run time:   O( 1 )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_diagonal() const {
	return row_index[M] == 0;
}

/***************************************************
 * Return true if the matrix is symmetric,
 * false otherwise.
 *
 *                     2
 * Run time:   O( M + n /M )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_symmetric() const {
	if ( M != N ) {
		return false;
	}

	// If there is an odd number of entries, return false
	if ( row_index[M] & 1 == 1 ) {
		return false;
	}

	// Count the number of entries below the
	// diagonal and at the end, make sure that
	// this contains half the entries.

	int count = 0;

	for ( int i = 1; i < M; ++i ) {
		// For each row, look at each entry up to the diagonal

		for ( int j = row_index[i]; j < row_index[i + 1]; ++j ) {
			// If we are beyond the digaonal (j > i), then break

			if ( column_index[j] > i ) {
				break;
			}

			++count;

			// We now are looking for A(i,j) so now look at
			// row j and look back to see if we can find A(i,j).

			for ( int k = row_index[column_index[j] + 1] - 1; k >= row_index[column_index[j]]; --k ) {
				// If the column matches, check if the entries are equal
				//   - Break (continue with the next entry) if they are equal, and
				//   - Return false if they differ

				if ( column_index[k] == i ) {
					if ( off_diagonal[k] == off_diagonal[j] ) {
						break;
					} else {
						return false;
					}
				}

				// If we did not match, no entry exists so return false.

				if ( column_index[k] < i ) {
					return false;
				}
			}
		}
	}

	return 2*count == row_index[M];
}

/***************************************************
 * Determine if a matrix is anti-symmetric.
 *
 *                     2
 * Run time:   O( M + n /M )
 * Memory:     O( 1 )
 ***************************************************/

template <int M, int N>
bool Matrix<M, N>::is_antisymmetric() const {
	if ( M != N ) {
		return false;
	}

	// If there is an odd number of entries, return false
	if ( row_index[M] & 1 == 1 ) {
		return false;
	}

	for ( int i = 0; i < M; ++i ) {
		if ( diagonal[i] != 0 ) {
			return false;
		}
	}

	// Count the number of entries below the
	// diagonal and at the end, make sure that
	// this contains half the entries.

	int count = 0;

	for ( int i = 1; i < M; ++i ) {
		// For each row, look at each entry up to the diagonal

		for ( int j = row_index[i]; j < row_index[i + 1]; ++j ) {
			// If we are beyond the digaonal (j > i), then break

			if ( column_index[j] > i ) {
				break;
			}

			++count;

			// We now are looking for A(i,j) so now look at
			// row j and look back to see if we can find A(i,j).

			for ( int k = row_index[column_index[j] + 1] - 1; k >= row_index[column_index[j]]; --k ) {
				// If the column matches, check if the entries are equal
				//   - Break (continue with the next entry) if they are equal, and
				//   - Return false if they differ

				if ( column_index[k] == i ) {
					if ( off_diagonal[k] == -off_diagonal[j] ) {
						break;
					} else {
						return false;
					}
				}

				// If we did not match, no entry exists so return false.

				if ( column_index[k] < i ) {
					return false;
				}
			}
		}
	}

	return 2*count == row_index[M];
}