temelia/src/sparse_matrix.c

/*!
 Temelia - Sparse matrix implementation source file

 Copyright (C) 2008 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/sparse_matrix.h"
#include "include/vector.h"
#include "include/red_black_tree.h"
#include <stdlib.h>

struct _sparse_matrix_t
{
	/*! tree of rows with not null keys */
	red_black_tree_t *rows;

	/*! tree of columns with not null keys */
	red_black_tree_t *columns;

	/*! number of rows */
	int n_rows;

	/*! number of columns */
	int n_columns;

	/*! maximum not null keys */
	int size;

	/*! number of not null keys */
	int not_null;

	/*! type of sparse matrix: row dense, column dense or both */
	int type;
};

struct _sparse_matrix_key_t
{
	int index;
	void *key;
};

sparse_matrix_key_t sparse_matrix_key_new(void *user_key, int index)
{
	sparse_matrix_key_t key;

	LOGGER("[sparse matrix key new] user_key %p, index %d\n", user_key, index);
	key = (sparse_matrix_key_t) _new(sizeof(struct _sparse_matrix_key_t));

	_ASSERT(key, ==, NULL, NULL_POINTER, NULL);

	key->key = user_key;
	key->index = index;

	return key;
}

void sparse_matrix_key_delete(sparse_matrix_key_t key)
{
	_ASSERT(key, ==, NULL, NULL_POINTER,);

	_delete(key);
}

sparse_matrix_key_t sparse_matrix_key_duplicate(sparse_matrix_key_t key)
{
	_ASSERT(key, ==, NULL, NULL_POINTER, NULL);

	return sparse_matrix_key_new(key->key, key->index);
}

int sparse_matrix_key_get_index(sparse_matrix_key_t key)
{
	_ASSERT(key, ==, NULL, NULL_POINTER, -1);

	return key->index;
}

void *sparse_matrix_key_get_key(sparse_matrix_key_t key)
{
	_ASSERT(key, ==, NULL, NULL_POINTER, NULL);

	return key->key;
}

void sparse_matrix_key_set_index(sparse_matrix_key_t key, int index)
{
	_ASSERT(key, ==, NULL, NULL_POINTER,);

	key->index = index;
}

void sparse_matrix_key_set_key(sparse_matrix_key_t key, void *user_key)
{
	_ASSERT(key, ==, NULL, NULL_POINTER,);

	key->key = user_key;
}

static int __sparse_matrix_key_simple_compare(void *key1, void *key2,
		void *context)
{
	return ((sparse_matrix_key_t) key1)->index
			- ((sparse_matrix_key_t) key2)->index;
}

/*
 * @brief Inserts into red black tree, identified by index, the given key.
 */
static int _sparse_matrix_insert(red_black_tree_t *tree, int index, void *key);

/*
 * @brief Removes key from red black tree.
 */
static void _sparse_matrix_remove(red_black_tree_t *tree, int index);

/*
 * @brief Iterates over black tree, calling the user handler with particular
 * parameters for-each node of the tree.
 */
static void _sparse_matrix_iterate(red_black_tree_t tree, void key_handler(
		void *key, int row, int column, void *context), void *context,
		int index, int order);

/*
 * @brief Returns the key in tree with given index.
 */
static void * _sparse_matrix_get_key_at(red_black_tree_t tree, int index);

/*
 * @brief Simple wrapper over sparse_matrix_key_delete(), used in iteration
 * for library allocated keys.
 */
static void _sparse_matrix_key_delete(void *key, void *context);

/*
 * @brief For-each called key, inserts it into context ( a valid [red_black_tree_t *])
 */
static void _sparse_matrix_key_duplication(void *key, void *context);

#define INIT_SPARSE_MATRIX(x, n, i)\
do\
{\
	x = (red_black_tree_t *) _new(n * sizeof(red_black_tree_t));\
	for (i = 0 ; i < n ; i++)\
		x[i] = NULL;\
} while (0)

#define DESTROY_SPARSE_MATRIX(x, n , i)\
do\
{\
	for (i = 0 ; i < n ; i++)\
	{\
		if (x[i])\
		{\
			red_black_tree_preorder(x[i], _sparse_matrix_key_delete, NULL);\
			red_black_tree_delete(x[i]);\
		}\
	}\
	_delete(x);\
} while (0)

sparse_matrix_t sparse_matrix_new(int rows_number, int columns_number,
		int size, int type)
{
	int i;
	sparse_matrix_t sparse_matrix;

	LOGGER("[sparse matrix new] rows %d, columns %d, size %d\n", rows_number,
			columns_number, size);

	_ASSERT(rows_number, <=, 0, INVALID_INPUT, NULL);
	_ASSERT(columns_number, <=, 0, INVALID_INPUT, NULL);
	_ASSERT(size, <=, 0, INVALID_INPUT, NULL);
	_ASSERT(size, >, rows_number * columns_number, INVALID_INPUT, NULL);
	_ASSERT(type, ==, 0, INVALID_INPUT, NULL);

	sparse_matrix = (sparse_matrix_t) _new(sizeof(struct _sparse_matrix_t));

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, NULL);

	sparse_matrix->not_null = 0;
	sparse_matrix->size = size;
	sparse_matrix->type = type;

	sparse_matrix->n_rows = rows_number;
	sparse_matrix->n_columns = columns_number;

	if (type & SPARSE_MATRIX_ROW_DENSE)
		INIT_SPARSE_MATRIX(sparse_matrix->rows, rows_number, i);
	else
		sparse_matrix->rows = NULL;

	if (type & SPARSE_MATRIX_COLUMN_DENSE)
		INIT_SPARSE_MATRIX(sparse_matrix->columns, columns_number, i);
	else
		sparse_matrix->columns = NULL;

	return sparse_matrix;
}

sparse_matrix_t sparse_matrix_clone(sparse_matrix_t sparse_matrix)
{
	int i;
	sparse_matrix_t clone;

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(sparse_matrix->type, ==, 0, INVALID_INPUT, NULL);

	clone = sparse_matrix_new(sparse_matrix->n_rows, sparse_matrix->n_columns,
			sparse_matrix->size, sparse_matrix->type);
	clone->not_null = sparse_matrix->not_null;

	// Starting tree duplication
	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
	{
		for (i = 0; i < sparse_matrix->n_rows; i++)
			if (sparse_matrix->rows[i])
				red_black_tree_inorder(sparse_matrix->rows[i],
						_sparse_matrix_key_duplication, &clone->rows[i]);
	}

	if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
	{
		for (i = 0; i < sparse_matrix->n_columns; i++)
			if (sparse_matrix->columns[i])
				red_black_tree_inorder(sparse_matrix->columns[i],
						_sparse_matrix_key_duplication, &clone->columns[i]);
	}

	return clone;
}

void sparse_matrix_delete(sparse_matrix_t sparse_matrix)
{
	int i;

	LOGGER("[sparse matrix delete] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, 0, NULL_POINTER,);
	_ASSERT(sparse_matrix->type, ==, 0, INVALID_INPUT,);

	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
		DESTROY_SPARSE_MATRIX(sparse_matrix->rows, sparse_matrix->n_rows, i);

	if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
		DESTROY_SPARSE_MATRIX(sparse_matrix->columns, sparse_matrix->n_columns, i);
	_delete(sparse_matrix);
}

int sparse_matrix_is_empty(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix is empty] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->not_null == 0;
}

int sparse_matrix_is_full(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix is full] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->not_null == sparse_matrix->size;
}

void sparse_matrix_set_key_at(sparse_matrix_t sparse_matrix, int row,
		int column, void *key)
{
	// By default, increment not_null
	int ok = 1;

	LOGGER(
			"[sparse matrix set key at] sparse matrix %p, row %d, column %d, key %p\n",
			sparse_matrix, row, column, key);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER,);
	_ASSERT(row, <, 0, INVALID_INPUT,);
	_ASSERT(row, >=, sparse_matrix->n_rows, INVALID_INPUT,);
	_ASSERT(column, <, 0, INVALID_INPUT,);
	_ASSERT(column, >=, sparse_matrix->n_columns, INVALID_INPUT,);
	_ASSERT(sparse_matrix->type, ==, 0, INVALID_INPUT,);

	// Lazy initialization
	if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
	{
		if (sparse_matrix->columns[column] == NULL)
			sparse_matrix->columns[column] = red_black_tree_new(
					sparse_matrix_key_new(key, row));
		else if (_sparse_matrix_insert(&sparse_matrix->columns[column], row,
				key) == 0)
			ok = 0;
	}

	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
	{
		if (sparse_matrix->rows[row] == NULL)
			sparse_matrix->rows[row] = red_black_tree_new(
					sparse_matrix_key_new(key, column));
		else if (_sparse_matrix_insert(&sparse_matrix->rows[row], column, key)
				== 0)
			ok = 0;
	}

	if (ok)
		sparse_matrix->not_null++;
}

void *sparse_matrix_get_key_at(sparse_matrix_t sparse_matrix, int row,
		int column, int preference)
{
	LOGGER("[sparse matrix get key at] sparse matrix %p, row %d, column %d\n",
			sparse_matrix, row, column);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(row, <, 0, INVALID_INPUT, NULL);
	_ASSERT(row, >=, sparse_matrix->n_rows, INVALID_INPUT, NULL);
	_ASSERT(column, <, 0, INVALID_INPUT, NULL);
	_ASSERT(column, >=, sparse_matrix->n_columns, INVALID_INPUT, NULL);

	// Set row dense preference as default
	if (preference != -1 && preference != 1)
	{
		if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
			preference = 1;
		else if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
			preference = -1;
		preference = 0;
	}

	if (preference == 0)
	{
		// No preference given and
		// unknown sparse matrix type
		if (sparse_matrix->columns)
		{
			if (sparse_matrix->columns[column])
				return _sparse_matrix_get_key_at(
						sparse_matrix->columns[column], row);
		}
		else if (sparse_matrix->rows)
		{
			if (sparse_matrix->rows[row])
				return _sparse_matrix_get_key_at(sparse_matrix->rows[row],
						column);
		}
	}

	if (preference == -1)
	{
		if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
			return _sparse_matrix_get_key_at(sparse_matrix->columns[column],
					row);
		return NULL;
	}

	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
		return _sparse_matrix_get_key_at(sparse_matrix->rows[row], column);
	return NULL;
}

void sparse_matrix_remove_key_at(sparse_matrix_t sparse_matrix, int row,
		int column)
{
	LOGGER(
			"[sparse matrix remove key at] sparse matrix %p, row %d, column %d\n",
			sparse_matrix, row, column);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER,);
	_ASSERT(row, <, 0, INVALID_INPUT,);
	_ASSERT(row, >=, sparse_matrix->n_rows, INVALID_INPUT,);
	_ASSERT(column, <, 0, INVALID_INPUT,);
	_ASSERT(column, >=, sparse_matrix->n_columns, INVALID_INPUT,);
	_ASSERT(sparse_matrix->columns, ==, NULL, NULL_POINTER,);
	_ASSERT(sparse_matrix->columns[column], ==, NULL, NULL_POINTER,);
	_ASSERT(sparse_matrix->rows, ==, NULL, NULL_POINTER,);
	_ASSERT(sparse_matrix->rows[row], ==, NULL, NULL_POINTER,);

	if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
		_sparse_matrix_remove(&sparse_matrix->columns[column], row);

	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
		_sparse_matrix_remove(&sparse_matrix->rows[row], column);
}

int sparse_matrix_get_rows_number(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get rows number] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->n_rows;
}

int sparse_matrix_get_columns_number(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get columns number] sparse matrix %p\n",
			sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->n_columns;
}

int sparse_matrix_get_size(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get size] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->size;
}

int sparse_matrix_get_type(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get type] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->type;
}

int sparse_matrix_get_not_null_keys(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get not null keys] sparse matrix %p\n",
			sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, -1);

	return sparse_matrix->not_null;
}

void *sparse_matrix_get_rows(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get rows] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, NULL);

	return sparse_matrix->rows;
}

void *sparse_matrix_get_columns(sparse_matrix_t sparse_matrix)
{
	LOGGER("[sparse matrix get columns] sparse matrix %p\n", sparse_matrix);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER, NULL);

	return sparse_matrix->columns;
}

int _sparse_matrix_transpose_type(int type)
{
	if (type == SPARSE_MATRIX_ROW_DENSE)
		return SPARSE_MATRIX_COLUMN_DENSE;

	else if (type == SPARSE_MATRIX_COLUMN_DENSE)
		return SPARSE_MATRIX_ROW_DENSE;

	return type;
}

sparse_matrix_t sparse_matrix_transpose(sparse_matrix_t sparse_matrix)
{
	int i;
	sparse_matrix_t transpose;

	transpose = sparse_matrix_new(sparse_matrix->n_columns,
			sparse_matrix->n_rows, sparse_matrix->size,
			_sparse_matrix_transpose_type(sparse_matrix->type));
	transpose->not_null = sparse_matrix->not_null;

	// Starting tree duplication
	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
	{
		for (i = 0; i < sparse_matrix->n_rows; i++)
			if (sparse_matrix->rows[i])
				red_black_tree_inorder(sparse_matrix->rows[i],
						_sparse_matrix_key_duplication, &transpose->columns[i]);
	}

	if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
	{
		for (i = 0; i < sparse_matrix->n_columns; i++)
			if (sparse_matrix->columns[i])
				red_black_tree_inorder(sparse_matrix->columns[i],
						_sparse_matrix_key_duplication, &transpose->rows[i]);
	}

	return transpose;
}

void sparse_matrix_iterate(sparse_matrix_t sparse_matrix, void key_handler(
		void *key, int row, int column, void *context), void *context,
		int order)
{
	int i;

	LOGGER(
			"[sparse matrix iterate] sparse matrix %p, key_handler %p, context %p, order %d\n",
			sparse_matrix, key_handler, context, order);

	_ASSERT(sparse_matrix, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	switch (order)
	{
	case -1:
	{
		if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
		{
			for (i = 0; i < sparse_matrix->n_rows; i++)
				if (sparse_matrix->rows[i])
					_sparse_matrix_iterate(sparse_matrix->rows[i], key_handler,
							context, i, order);
		}
	}
		break;
	case 1:
	{
		if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
		{
			for (i = 0; i < sparse_matrix->n_columns; i++)
				if (sparse_matrix->columns[i])
					_sparse_matrix_iterate(sparse_matrix->columns[i],
							key_handler, context, i, order);
		}
	}
		break;
	default:
		_ASSERT(1, ==, 1, INVALID_INPUT,);
	}
}

#define GENERATE_RESIZE(trees, old_val, new_val)\
do\
{\
	for (i = new_val; i < old_val; i++)\
	{\
		red_black_tree_preorder(trees[i], _sparse_matrix_key_delete, NULL);\
		red_black_tree_delete(trees[i]);\
		trees[i] = NULL;\
	}\
	\
	if (old_val < new_val)\
	{\
		trees = _realloc(trees, columns * sizeof(red_black_tree_t));\
		_ASSERT(trees, ==, NULL, NULL_POINTER,);\
	\
		for (i = old_val; i < new_val; i++)\
			trees[i] = NULL;\
	}\
	old_val = new_val;\
}\
while(0)\

void sparse_matrix_resize(sparse_matrix_t sparse_matrix, int rows, int columns,
		int size)
{
	int i;

	LOGGER("[sparse matrix resize] matrix %p, rows %d, columns %d, size %d\n",
			sparse_matrix, rows, columns, size);
	_ASSERT(sparse_matrix, ==, NULL, INVALID_INPUT,);

	_ASSERT(rows, <=, 0, INVALID_INPUT,);
	_ASSERT(columns, <=, 0, INVALID_INPUT,);
	_ASSERT(size, >, sparse_matrix->size, INVALID_INPUT,);

	sparse_matrix->size = size;
	// Columns
	if (sparse_matrix->type & SPARSE_MATRIX_COLUMN_DENSE)
		GENERATE_RESIZE(sparse_matrix->columns, sparse_matrix->n_columns, columns);
	else
		sparse_matrix->n_columns = columns;

	// Rows
	if (sparse_matrix->type & SPARSE_MATRIX_ROW_DENSE)
		GENERATE_RESIZE(sparse_matrix->rows, sparse_matrix->n_rows, rows);
	else
		sparse_matrix->n_rows = rows;
}

static int _sparse_matrix_key_compare(void *key1, void *key2, void *context)
{
	sparse_matrix_key_t v1 = (sparse_matrix_key_t) key1;
	sparse_matrix_key_t v2 = (sparse_matrix_key_t) key2;

	if (v1->index == v2->index)
	{
		// Hack for key stored update operation
		if (v1->key == context)
			v2->key = context;
		else if (v2->key == context)
			v1->key = context;
		else
			_ASSERT(1, ==, 1, INVALID_INPUT, -1);
	}

	// Order after their indices
	return v1->index - v2->index;
}

static int _sparse_matrix_insert(red_black_tree_t *tree, int index, void *key)
{
	int result;
	sparse_matrix_key_t pair = sparse_matrix_key_new(key, index);

	_ASSERT(pair, ==, NULL, NULL_POINTER, -1);

	result = red_black_tree_insert(tree, pair, _sparse_matrix_key_compare, key,
			1) != NULL;

	// Key already exists
	if (result == 0)
		sparse_matrix_key_delete(pair);

	return result;
}

static int __sparse_matrix_remove(void *key1, void *key2, void *context)
{
	int result = ((sparse_matrix_key_t) key1)->index
			- ((sparse_matrix_key_t) key2)->index;
	if (result == 0 && key1 != key2)
	{
		if (((sparse_matrix_key_t) key1)->key)
			*(void **) context = key1;
		else if (((sparse_matrix_key_t) key2)->key)
			*(void **) context = key2;
	}
	return result;
}

static void _sparse_matrix_remove(red_black_tree_t *tree, int index)
{
	void *context = NULL;
	sparse_matrix_key_t pair = sparse_matrix_key_new(NULL, index);

	/*
	 * This is a true hack. When you don't have a reference to the key
	 * you can create a new one, pair in this example, then
	 * remove as key as usually. Deleting only your new key
	 * will result in a memory leak (the old key is not freed).
	 * Declare a context and save the old key there, while iterating in tree.
	 *
	 * See __sparse_matrix_remove how you can do this.
	 */
	red_black_tree_remove(tree, pair, __sparse_matrix_remove, &context, 1);
	sparse_matrix_key_delete(pair);

	if (context)
		sparse_matrix_key_delete(context);
}

static void __sparse_matrix_iterate(void *key, void *context)
{
	vector_t vector = (vector_t) context;
	sparse_matrix_key_t real_key = (sparse_matrix_key_t) key;
	int order;
	int index;
	void *real_context;
	void (*key_handler)(void *key, int row, int column, void *context);

	order = *(int *) vector_get_key_at(vector, 3);
	index = *(int *) vector_get_key_at(vector, 2);
	real_context = (void*) vector_get_key_at(vector, 1);
	key_handler = (void(*)(void *, int, int, void *)) vector_get_key_at(vector,
			0);

	if (order == -1)
		key_handler(real_key->key, index, real_key->index, real_context);
	else if (order == 1)
		key_handler(real_key->key, real_key->index, index, real_context);
}

static void _sparse_matrix_iterate(red_black_tree_t tree, void key_handler(
		void *key, int row, int column, void *context), void *context,
		int index, int order)
{
	vector_t vector = vector_new(16);

	_ASSERT(vector, ==, NULL, NULL_POINTER,);

	vector_push_back(vector, key_handler);
	vector_push_back(vector, context);
	vector_push_back(vector, &index);
	vector_push_back(vector, &order);

	red_black_tree_inorder(tree, __sparse_matrix_iterate, vector);

	vector_delete(vector);
}

static void _sparse_matrix_key_delete(void *key, void *context)
{
	sparse_matrix_key_delete(key);
}

static void * _sparse_matrix_get_key_at(red_black_tree_t tree, int index)
{
	red_black_tree_t node;
	sparse_matrix_key_t key;

	_ASSERT(tree, ==, NULL, NULL_POINTER, NULL);

	key = sparse_matrix_key_new(NULL, index);
	node = red_black_tree_search(tree, key, __sparse_matrix_key_simple_compare,
			NULL);
	sparse_matrix_key_delete(key);

	return node ? sparse_matrix_key_get_key(red_black_tree_get_key(node))
			: NULL;
}

static void _sparse_matrix_key_duplication(void *key, void *context)
{
	sparse_matrix_key_t m_key = (sparse_matrix_key_t) key;
	red_black_tree_t *m_tree = (red_black_tree_t *) context;

	// Lazy initialization on transposing sparse matrix
	if (*m_tree == NULL)
		*m_tree = red_black_tree_new(sparse_matrix_key_duplicate(m_key));
	else
		red_black_tree_insert(m_tree, sparse_matrix_key_duplicate(m_key),
				__sparse_matrix_key_simple_compare, NULL, 1);
}