using
System;
using
System. Collections. Generic;
using
System. Text;
using
System. Collections;
using
System. IO;
namespace
ConsoleApplication1
{
public
class Element
{
int row , coulmn , val;
public Element ( int
r , int c , int
v )
{
this. row = r;
this. coulmn = c;
this. val = v;
}
public int Row
{
get
{
return row;
}
}
public int Coulmn
{
get
{
return coulmn;
}
}
public int Val
{
get
{
return val;
}
}
public override string ToString ( )
{
return "[" + row + "," + coulmn +
"] = " + val;
}
}
public
class Rows : IComparable
{
public int row;
public ArrayList Coulmns;
public Rows ( int r )
{
Coulmns = new ArrayList ( );
row = r;
}
// we use this function for sorting
public int CompareTo
( object obj )
{
int y;
if ( obj is int )
{
y = ( int ) obj;
return this.
Compare ( y );
}
Rows mat = obj as Rows;
if ( mat == null )
{
throw new
ArgumentException ( "erorr casting" );
}
else
{
int x = this.
row > mat. row ? 1 : this. row < mat. row
? -1 : 0;
return x;
}
}
//we use this function for binary search
public int Compare ( int i )
{
int x = this. row
> i ? 1 : this. row < i ? -1 : 0;
return x;
}
}
public
class CoulmnElement : IComparable
{
public int coulmn;
public int val;
public CoulmnElement ( int
c , int v )
{
coulmn = c;
val = v;
}
// we use this function for sorting
public int CompareTo
( object obj )
{
int y;
if ( obj is int )
{
y = ( int ) obj;
return this.
Compare ( y );
}
CoulmnElement mat = obj as
CoulmnElement;
if ( mat == null )
{
throw new
ArgumentException ( "error casting element" );
}
else
{
int x = this.
coulmn > mat. coulmn ? 1 : this. coulmn <
mat. coulmn ? -1 : 0;
return x;
}
}
//we use this function for binary search
public int Compare ( int i )
{
int x = this. coulmn
> i ? 1 : this. coulmn < i ? -1 : 0;
return x;
}
}
class
SparseMatrix : IEnumerable
{
int row;
int coulmn;
MatrixType type;
ArrayList Data;
// ///////////////////////////////////////////////////////////////////
enum MatrixType
{
Zero ,
Identity ,
Default ,
}
//
///////////////////////////////////////////////////////////////////
public SparseMatrix ( int
r , int c )
{
Data = new ArrayList ( );
row = r;
coulmn = c;
type = MatrixType. Zero;
}
private SparseMatrix ( int
r , int c , MatrixType t )
{
Data = new ArrayList ( );
row = r;
coulmn = c;
type = t;
}
public static
SparseMatrix Identity ( int r , int c )
{
if ( r != c )
{
throw new
ArgumentException ( "the dimentions of the identity matrix are not
equal" );
}
else
return new
SparseMatrix ( r , c , MatrixType. Identity );
}
public int this [ int i , int j ]
{
get
{
int x , y;
if ( i < 0 || i >= row || j < 0
|| j >= coulmn )
{
Console. WriteLine ( "ERROR>>>>>>>OUT OF
RANGE" );
throw new
ArgumentOutOfRangeException ( "indexer get ln 134" );
//return -1000000;
}
////////////////////////////////////////////////////////////////////
switch ( this.
type )
{
case MatrixType. Zero:
return 0;
case MatrixType. Identity:
if ( i == j )
return 1;
else
return 0;
default:
if ( ( x = Data. BinarySearch ( i ) )
< 0 )
{
return 0;
}
if ( ( y = ( ( Rows ) Data [ x ] ).
Coulmns. BinarySearch ( j ) ) < 0 )
{
return 0;
}
return ( ( CoulmnElement ) ( ( Rows )
Data [ x ] ). Coulmns [ y ] ). val;
}
}
set
{
if ( ( i < 0 || i >= row || j < 0 || j >=
coulmn ) )
{
Console. WriteLine ( "ERROR>>>>>>>OUT OF
RANGE" );
throw new
ArgumentOutOfRangeException ( "indexer set ln 166" );
}
//////////////////////////////////////////////////////////////////////
if ( value
!= 0 )
{
switch ( this.
type )
{
case MatrixType. Zero:
this. type = MatrixType. Default;
Put ( value , i , j );
break;
case MatrixType. Identity:
switch ( i == j )
{
case true:
if ( value
!= 1 )
{
Put ( value , i , j );
this. type = MatrixType. Default;
}
break;
case false:
Put ( value , i , j );
this. type = MatrixType. Default;
break;
}
break;
case MatrixType. Default:
Put ( value , i , j );
break;
}
}
}
}
private void Put ( int v , int i , int j )
{
if ( this. type ==
MatrixType. Identity ) //test for identity
{
//if identity we should build it first
//because we have not build it yet
for ( int
n = 0 ; n < this. row ; n++ )
{
this. Data. Add ( new Rows ( n ) );
( ( Rows ) this. Data [ n ] ). Coulmns.
Add ( new CoulmnElement ( n , 1 ) );
}
}
int x , y;
if ( ( x = Data. BinarySearch ( i ) ) < 0 )
{
//if we don't find the element
//the return value of the binary shearch is
bitwise Not
//of the place where you should insert the new
element
Data. Insert ( ~x , ( object ) new Rows ( i ) );
( ( Rows ) Data [ ~x ] ). Coulmns. Add ( ( object
) new CoulmnElement ( j , v ) );
}
else if ( ( y = ( (
Rows ) Data [ x ] ). Coulmns. BinarySearch ( j ) ) < 0 )
{
( ( Rows ) Data [ x ] ). Coulmns. Insert ( ~y , ( object ) new
CoulmnElement ( j , v ) );
}
else
{
( ( CoulmnElement ) ( ( Rows ) Data [ x ] ). Coulmns [ y ] ). val = v;
}
}
public static bool operator == (
SparseMatrix lhs , SparseMatrix rhs )
{
int x;
if ( !( SparseMatrix. ReferenceEquals ( lhs , rhs ) )
)
{
if ( lhs. type != rhs. type )
{
return false;
}
//////////////
if ( lhs. Data. Count != rhs. Data.
Count )
{
return false;
}
/////////////////
for ( int
i = 0 ; i < lhs. Data. Count ; i++ )
{
if ( ( ( Rows ) lhs. Data [ i ] ).
Coulmns. Count != ( ( Rows ) rhs. Data [ i ] ). Coulmns. Count )
{
return false;
}
//////////////////
x = ( ( Rows ) lhs. Data [ i ] ). Coulmns. Count;
for ( int
j = 0 ; j < x ; j++ )
{
if ( ( ( CoulmnElement ) ( ( Rows ) lhs.
Data [ i ] ). Coulmns [ j ] ). coulmn !=
( ( CoulmnElement ) ( ( Rows ) rhs. Data [ i ] ). Coulmns [ j ] ).
coulmn ||
( ( CoulmnElement ) ( ( Rows ) lhs. Data [ i ] ). Coulmns [ j ] ). val
!=
( ( CoulmnElement ) ( ( Rows ) rhs. Data [ i ] ). Coulmns [ j ] ). val )
{
return false;
}
}
}
}
return true;
}
public static bool operator != (
SparseMatrix lhs , SparseMatrix rhs )
{
return !( lhs == rhs );
}
public SparseMatrix Transpose ( )
{
SparseMatrix s = new SparseMatrix ( this. coulmn , this.
row , this. type );
Rows k;
int i = 0;
int x , y;
foreach ( Rows r in this. Data )
{
foreach ( CoulmnElement e in r. Coulmns )
{
///this block
will be excuted in the first row only
if ( i == 0 )
{
s. Data. Add ( k = new Rows ( e. coulmn
) );
k. Coulmns. Add ( new CoulmnElement ( r.
row , e. val ) );
}
//this block will excuted every time except
the first time
else
{
//this block will be excuted when the element
coulmn
//hasn't been converted to a row yet
//so we built a new row
//and add new element to this row
if ( ( x = s. Data. BinarySearch ( e.
coulmn ) ) < 0 )
{
s.
Data. Insert ( ~x , ( k = new Rows ( e. coulmn
) ) );
k. Coulmns. Add ( new CoulmnElement ( r.
row , e. val ) );
}
else
{
//this block will be excuted when the element coulmn
//has ever been converted to a row
//so we only add an element to this row
( ( Rows ) s. Data [ x ] ). Coulmns. Add ( new
CoulmnElement ( r. row , e. val ) );
}
}
}
i++;
}
return s;
}
// //////////////////////////////////////////
//enuumeration region
public IEnumerator GetEnumerator ( )
{
return ( IEnumerator ) new
SparseMatrixEnum ( this );
}
private class
SparseMatrixEnum : IEnumerator
{
public SparseMatrixEnum ( SparseMatrix sp )
{
this. s = sp;
this. i = 0;
this. j = -1;
}
public object Current
{
get
{
int x = ( ( Rows ) s. Data [ i ] ). row;
int y = ( ( CoulmnElement ) ( ( Rows )
s. Data [ i ] ). Coulmns [ j ] ). coulmn;
int v = ( ( CoulmnElement ) ( ( Rows )
s. Data [ i ] ). Coulmns [ j ] ). val;
return new
Element ( x , y , v );
}
}
public bool MoveNext
( )
{
j++;
if ( i >= s. Data. Count )
{
return false;
}
if ( j >= ( ( Rows ) s. Data [ i ] ).
Coulmns. Count )
{
i++;
j = 0;
if ( i >= s. Data. Count )
{
return false;
}
}
return true;
}
public void Reset ( )
{
i = 0;
j = -1;
}
private SparseMatrix s;
private int i , j;
}
// ///////////////////////////////////////////
public static
SparseMatrix operator + ( SparseMatrix lhs ,
SparseMatrix rhs )
{
int x , y;
Rows k;
SparseMatrix s = lhs. Copy ( );
//foreach ( Element e in rhs )
//{
//
if ( ( x = s. Data. BinarySearch ( e. Row ) ) < 0 )
//
{
// s. Data. Insert ( ~x , k
= new Rows ( e. Row ) );
// k. Coulmns. Add ( new
CoulmnElement ( e. Coulmn , e. Val ) );
//
}
//
else
//
{
// ( ( Rows ) s. Data [ x ]
). Coulmns. Add ( new CoulmnElement ( e. Coulmn , e. Val ) );
//
}
foreach ( Rows r in
rhs. Data )
{
if ( ( x = s. Data. BinarySearch ( r.
row ) ) < 0 )
{
s. Data. Insert ( ~x , k = new Rows ( r.
row ) );
foreach ( CoulmnElement c in r. Coulmns )
{
k. Coulmns. Add ( new CoulmnElement ( c.
coulmn , c. val ) );
}
}
else
{
foreach ( CoulmnElement c in r. Coulmns )
{
if ( ( y = ( ( Rows ) s. Data [ x ] ). Coulmns.
BinarySearch ( c. coulmn ) ) < 0 )
{
( ( Rows ) s. Data [ x ] ). Coulmns. Insert ( ~y , new CoulmnElement ( c. coulmn , c. val ) );
}
else
{
if ( ( ( ( CoulmnElement ) ( ( Rows ) s.
Data [ x ] ). Coulmns [ y ] ). val + c. val ) == 0 )
{
( ( Rows
) s. Data [ x ] ). Coulmns. RemoveAt ( y );
}
else
{
( ( CoulmnElement ) ( ( Rows ) s. Data [ x ] ). Coulmns [ y ] ). val +=
c. val;
}
}
}
if ( ( ( Rows ) s. Data [ x ] ).
Coulmns. Count == 0 )
{
s. Data. RemoveAt ( x );
}
}
}
if ( s. Data. Count == 0 )
{
s. type = MatrixType. Zero;
}
return s;
}
public static
SparseMatrix operator - ( SparseMatrix lhs ,
SparseMatrix rhs )
{
int x , y;
Rows k;
SparseMatrix s = lhs. Copy ( );
foreach ( Rows r in
rhs. Data )
{
if ( ( x = s. Data. BinarySearch ( r.
row ) ) < 0 )
{
s.
Data. Insert ( ~x , k = new Rows ( r. row ) );
foreach ( CoulmnElement c in r. Coulmns )
{
k. Coulmns. Add ( new CoulmnElement ( c.
coulmn , -c. val ) );
}
}
else
{
foreach ( CoulmnElement c in r. Coulmns )
{
if ( ( y = ( ( Rows ) s. Data [ x ] ).
Coulmns. BinarySearch ( c. coulmn ) ) < 0 )
{
( ( Rows ) s. Data [ x ] ). Coulmns. Insert ( ~y , new CoulmnElement ( c. coulmn , -c. val ) );
}
else
{
if ( ( ( ( CoulmnElement ) ( ( Rows ) s.
Data [ x ] ). Coulmns [ y ] ). val - c. val ) == 0 )
{
( ( Rows ) s. Data [ x ] ). Coulmns. RemoveAt ( y );
}
else
{
( ( CoulmnElement ) ( ( Rows ) s. Data [ x ] ). Coulmns [ y ] ). val -=
c. val;
}
}
}
if ( ( ( Rows ) s. Data [ x ] ).
Coulmns. Count == 0 )
{
s. Data. RemoveAt ( x );
}
}
if ( s. Data. Count == 0 )
{
s. type = MatrixType. Zero;
}
}
return s;
}
public static
SparseMatrix operator * ( SparseMatrix lhs ,
SparseMatrix rhs )
{
if ( lhs. coulmn != rhs. row )
{
throw new
ArgumentException ( "this 2 matrix cannot be mul" );
}
else
{
int x;
Rows k;
SparseMatrix s = new SparseMatrix ( lhs.
row , rhs. coulmn , MatrixType. Default );
rhs
= rhs. Transpose ( );
foreach ( Rows r in lhs. Data )
{
s. Data. Add ( k = new Rows ( r. row )
);
foreach ( Rows ro in rhs. Data )
{
int val = 0;
int min = r. Coulmns. Count < ro.
Coulmns. Count ? r. Coulmns. Count : ro. Coulmns. Count;
for ( int
i = 0 ; i < min ; i++ )
{
if ( ( ( CoulmnElement ) r. Coulmns [ i ] ). coulmn
== ( ( CoulmnElement ) ro. Coulmns [ i ] ). coulmn )
{
val += ( ( CoulmnElement ) r. Coulmns [ i ] ). val * ( ( CoulmnElement )
ro. Coulmns [ i ] ). val;
}
}
if ( val != 0 )
{
k. Coulmns. Add ( new CoulmnElement (
ro. row , val ) );
}
}
if ( k. Coulmns. Count == 0 )
{
s. Data. Remove ( k );
}
}
if ( s. Data. Count == 0 )
{
s. type = MatrixType. Zero;
}
return s;
}
}
public SparseMatrix Copy ( )
{
Rows k;
SparseMatrix s = new SparseMatrix ( this. row , this.
coulmn , this. type );
foreach ( Rows r in this. Data )
{
s. Data. Add ( k = new Rows ( r. row )
);
foreach ( CoulmnElement c in r. Coulmns )
{
k. Coulmns. Add ( new CoulmnElement ( c.
coulmn , c. val ) );
}
}
return s;
}
public float
Persentage ( )
{
int count = 0;
foreach ( Element e in
this )
{
count++;
}
return ( float )
count / ( row * coulmn ) * 100;
}
public int MaxElement
( )
{
int max = Int32. MinValue;
foreach ( Element e in
this )
{
if ( e. Val > max )
{
max = e. Val;
}
}
if ( this. Persentage
( ) < 100 )
{
if ( max < 0 )
{
return 0;
}
}
return max;
}
public int MinElement
( )
{
int min = Int32. MaxValue;
foreach ( Element e in
this )
{
if ( e. Val < min )
{
min = e. Val;
}
}
if ( this. Persentage
( ) < 100 )
{
if ( min > 0 )
{
return 0;
}
}
return min;
}
public override string ToString ( )
{
StringBuilder output = new StringBuilder
( );
output. AppendFormat ( "This SparseMatrix of Type {0}\r\n" , this. type );
foreach ( Element e in
this )
{
output. AppendFormat (
"{0}\r\n" , e );
}
return output. ToString ( );
}
public void Printf ( string s )
{
using ( StreamWriter sr = new
StreamWriter ( s ) )
{
sr. WriteLine ( this );
sr. Close ( );
}
}
public void Readf ( string s )
{
using ( StreamReader sr = new
StreamReader ( s ) )
{
int r , c , val;
String line;
string [ ] sep ={ "[" ,
"," , "]=" };
string [ ] f;
while ( ( line = sr. ReadLine ( ) ) != null )
{
f = line. Split ( sep , StringSplitOptions. RemoveEmptyEntries );
r = Int32. Parse ( f [ 0 ] );
c = Int32. Parse ( f [ 1 ] );
val = Int32. Parse ( f [ 2 ] );
this [ r , c ] = val;
}
}
}
public SparseMatrix SubMatrix ( int sRow , int
sCoulmn , int eRow , int
eCoulmn )
{
Rows k;
int x , y , l , z;
SparseMatrix s = new SparseMatrix ( eRow
- sRow + 1 , eCoulmn - sCoulmn + 1 , this. type
);
x = this. Data. BinarySearch ( sRow );
int minRow = x > ~x ? x : ~x;
l = this. Data. BinarySearch ( eRow );
// z = this.Data.BinarySearch(eColumn);
int maxRow = l > ~l ? l : ~l;
// int maxCoulmn=z>~z? z:~z;
if ( minRow < this.
Data. Count )
{
if ( maxRow == this.
Data. Count )
{
maxRow = this. Data. Count-1;
}
for ( int
i = minRow ; i <= maxRow ; i++ )
{
s. Data. Add ( k = new Rows ( ((Rows)this.Data[i]).row-sRow ) );
y = ( ( Rows ) this. Data [ i ] ).
Coulmns. BinarySearch ( sCoulmn );
z = ( ( Rows ) this. Data [ i ] ).
Coulmns. BinarySearch ( eCoulmn );
int maxCoulmn = z > ~z ? z : ~z;
int minCoulmn = y > ~y ? y : ~y;
if ( minCoulmn < ( ( Rows ) this. Data [ i ] ). Coulmns. Count )
{
if ( maxCoulmn == ( ( Rows ) this. Data [ i ] ). Coulmns. Count )
{
maxCoulmn =( ( Rows ) this. Data [ i ]
). Coulmns. Count - 1;
}
for ( int
j = minCoulmn ; j <= maxCoulmn ; j++ )
{
k. Coulmns. Add ( new CoulmnElement ( (
( CoulmnElement ) ( ( Rows ) this. Data [ i ]
). Coulmns [ j ] ). coulmn - sCoulmn , ( ( CoulmnElement ) ( ( Rows ) this. Data [ i ] ). Coulmns [ j ] ). val ) );
}
}
else
{
s. Data. Remove ( k );
}
}
}
else
{
s. type = MatrixType. Zero;
}
return s;
}
// ///////////////////////////////////////////
public int Row
{
get
{
return row;
}
}
public int Coulmn
{
get
{
return coulmn;
}
}
public bool IsSquare
{
get
{
return row == coulmn;
}
}
public bool
IsIdentity
{
get
{
if ( this.
type == MatrixType. Identity )
{
return true;
}
if(this.row!=this.coulmn)
{
return false;
}
if ( this.
Data. Count != this. row )
{
return false;
}
foreach ( Rows r in this. Data )
{
if ( r. Coulmns. Count != 1 )
{
return false;
}
if ( ( ( CoulmnElement ) r. Coulmns [ 0
] ). coulmn != r. row )
{
return false;
}
if ( ( ( CoulmnElement ) r. Coulmns [ 0
] ).val !=1 )
{
return false;
}
}
return true;
}
}
public bool
IsUpperTringle
{
get
{
if ( this.
type == MatrixType. Identity || this. type ==
MatrixType.Zero )
{
return true;
}
if ( this.
row != this. coulmn )
{
return false;
}
foreach ( Rows r in this. Data )
{
if ( ( ( CoulmnElement ) r. Coulmns [ 0
] ). coulmn < r. row )
{
return false;
}
}
return true;
}
}
public bool
IsSymtrric
{
get
{
if ( this.
type == MatrixType. Identity || this. type ==
MatrixType. Zero )
{
return true;
}
if ( this.
row != this. coulmn )
{
return false;
}
if ( this
== this. Transpose ( ) )
{
return true;
}
return false;
}
}
}
class
Program
{
static void Main ( string [ ] args )
{
SparseMatrix s = new SparseMatrix ( 20 ,
20 );
// using ( StreamWriter sr = new StreamWriter(
"TextFile1.txt" ) )
// {
//
String line;
//
// Read and display lines from the file until the end of
//
// the file is reached.
//
//while ( ( line = sr. ReadLine ( ) ) != null )
//
{
// sr. WriteLine ( s
);
//
}
//
sr. Close ( );
// }
// s.Readf("text.txt");
// s.Printf("textfile1.txt");
SparseMatrix wr =new SparseMatrix( 200 ,
20 );
Console. WriteLine ( s );
s [ 15 , 6 ] = 941;
s [ 5 , 6 ] = 9;
s [ 6 , 7 ] = 10;
s [ 7 , 6 ] = 90;
s [ 8 , 6 ] = 966;
s [ 8 , 7 ] = 94;
s [ 8 , 9 ] = 945;
s [ 8 , 10 ] = 92;
s [ 5 , 6 ] = 99;
//////////
wr [ 15 , 6 ] = 941;
wr [ 5 , 6 ] = 9;
wr [ 6 , 7 ] = 100;
wr [ 7 , 6 ] = 90;
wr [ 8 , 6 ] = 966;
wr [ 8 , 7 ] = 94;
wr [ 8 , 9 ] = 945;
wr [ 8 , 10 ] = 92;
wr [ 5 , 6 ] = 99;
Rows a = new Rows ( 5 );
Rows b = new Rows ( 6 );
CoulmnElement q = new CoulmnElement ( 5
, 6 );
CoulmnElement w = new CoulmnElement ( 6
, 6 );
CoulmnElement e = new CoulmnElement ( 7
, 6 );
CoulmnElement r = new CoulmnElement ( 8
, 6 );
b. Coulmns. Add ( q );
b. Coulmns. Add
( w );
b. Coulmns. Add ( e );
b. Coulmns. Add ( r );
Rows c = new Rows ( 7 );
Rows d = new Rows ( 8 );
Console. WriteLine ( s == wr );
//s= s. Transpose ( );
//Console.WriteLine(s[15,6]);
//Console. WriteLine ( s [ 6 , 5] );
//Console. WriteLine ( s [ 6 , 7 ]);
//Console. WriteLine ( s [ 7 , 6 ] );
//Console. WriteLine ( s [ 8 , 6 ] );
//Console. WriteLine ( s [ 8 , 7 ] );
//Console. WriteLine ( s [ 8 , 9 ] );
//Console. WriteLine ( s [ 8 , 10 ] );
//Console. WriteLine ( s [ 15 , 15 ] );
SparseMatrix co = s. Copy ( );
co = co. Transpose ( );
//SparseMatrix gg = s - wr;
// foreach ( Element dd in s )
//{
//
Console. WriteLine ( "{0} " , dd );
//}
// Console. WriteLine ( );
//foreach ( Element dd in co )
//{
//
Console. WriteLine ( "{0} " , dd );
//}
//Console. WriteLine ( );
//foreach ( Element dd in gg )
//{
//
Console. WriteLine ( "{0} " , dd );
//}
Console. WriteLine ( s );
SparseMatrix vv = s. SubMatrix ( 5 , 5 , 7 , 8 );
Console. WriteLine ( s.IsUpperTringle );
}
}
}