Sparse Arrays And Matrices

[koricha]

Hello

i need help with a program which allows the user random read access to any entry of the array. If the user attempts to read outside the useful region, your data structure should return a 0. Also It allows the user random write access to the useful region only. In case the user tries to write something in the part of the array that is supposed to be 0, print an error message.

this is the form of the array

[ 0 0 0 0 ... 0 0 1 2 3 4 5 0 0 .... 0 0 ]

i am not sure how to create Sparse Array, also i dont want to use existing libraries

this is what i have so far

#include <iostream>

using namespace std;

class MyArray {
	friend ostream& operator <<(ostream &os, MyArray &array);
	public:
		MyArray(int size);
		MyArray(const MyArray &rhs);
		~MyArray();
		MyArray& operator = (const MyArray& rhs);
		int & operator[] (int index);
		int read_element(int index);
		void write_element(int index, int value);
	private:
		int *storage;
		int size;


};

#include "sparse_array_1d.h"

MyArray::MyArray(int size)
{
	storage = new int [size];
	this -> size = size;
}

MyArray::MyArray(const MyArray &rhs)
{
	size = rhs.size;
	storage = new int[size];
	(*this) = rhs;
}

MyArray::~MyArray()
{
	delete [] storage;
}

int MyArray::read_element(int index)
{
	return storage[index]; 
}


void MyArray::write_element(int index, int value)
{
	storage[index] = value;
}

MyArray& MyArray::operator = (const MyArray &rhs)
{
	int i,min_size;
	if(size < rhs.size)
		min_size = size;
	else
		min_size = rhs.size;
	for(i=0; i<min_size; i++)
		storage[i] = rhs.storage[i];
	return (*this);
}

int & MyArray::operator[] (int index)
{
	if(index < size && index >=0)
		return storage[index];
	return storage[0]; 
}


ostream & operator <<(ostream &os, MyArray &array)
{
	int i;
	os << "[ ";
	for(i=0; i<array.size; i++)
		os << array[i] << " ";
	os << "]" << endl;
	return os;
}

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

using namespace std;

void f(MyArray p, int size) //call-by-value, copy constructor should be called
// Note: what will change if we pass by by ref?
{
	int i;
	for(i=0 ; i<size; i++)
		p[i] = 4*i;

	cout << "p (in f)" << endl;
	cout << p;
}

int main()
{
	int i,size;

	cout << "What array sizes would you like?" << endl;
	cin >> size;
	
	MyArray p1(size),p2(size),p3(size);

	for(i=0 ; i<size; i++){	
		p1[i] = 2*i;
	}

	cout << "p1: " << endl;
	cout << p1;

	p3 = p2 = p1;

	cout << "p2: " << endl;
	cout << p2;

	cout << "p3: " << endl;
	cout << p3;

	for(i=0 ; i<size; i++){	
		p2[i] = 3*i;
	}

	cout << "Check that deep copy was performed" << endl; 
	//Note: how will output be different if I had not 
	//overloaded = and used a shallow copy?

	cout << "p1: " << endl;
	cout << p1;

	cout << "p2: " << endl;
	cout << p2;

	cout << "p3: " << endl;
	cout << p3;

	f(p1, size);

	cout << "p1: " << endl; 
	cout << p1;

	return 0;
}

[therockon7throw]

Hi

I dont think you have any problem, you've already done the job
You may also overload the operator[] for const object, read only

const int& operator[] (int index)const{ 
        if(index < size && index >=0)
	     return storage[index];
	return storage[0] ;
}

You may also overload other operator for example + , -, * , ==, != and son on

[ravenous]

I'm not sure that what you have implemented is a sparse array. I think that the usual way to make a sparse array or matrix is to store the data in an indexed form. The idea is that if you have an array that is 10000 elements in size, but only 100 elements are non-zero, then if you store all the elements specifically you need space for 10000, say, int s. However, if you don't explicitly store the array itself, but pairs of numbers that indicate the index that the number would have in the explicit array, and the value of that element:

class sparse_array
{
public:
   /* Public member functions here */
private:
   struct sparse_element
   {
      size_t index;
      int value;
   };

   std::vector< sparse_element > mySparseData;
};

Then, when you want to get a value from the array, you make a get function like this:

int sparse_array::get( size_t i ) const
{
   /* handle out-of-range indices here */

   /* Get the element from the array */
   std::vector< sparse_element >::const_iterator it_find = std::find( mySparseData.begin(), mySparseData.end(), i );
   return it_find == mySparseData.end() ? 0 : it_find->second;
}

To make std::find work, you would have to overload operator== for the sparse_element struct to compare with int . Otherwise, you could use a manual for loop.

[koricha]

Thank you guys