Alright. I post my complete project now. I have tested insertion and print and they work. I will add deletion later. So, tell me what you think could be designed better and why.
List header file, "DoubleLinkedList.h":
Code:
#ifndef INC_DoubleLinkedList_h
#define INC_DoubleLinkedList_h
#include<sstream>
usingnamespace std;
//(D)LL in this file stands for (Double) Linked List
typedefunsignedlong N;
class DLL_member{
DLL_member *p,*n;
N key;
public:
DLL_member(N x):key(x),p(0),n(0){}//Constructor. Sole member that has write access to key.
booloperator <= (N x) {return key<=x;}
booloperator > (N x) {return key>x;}
booloperator == (N x) {return key==x;}
N getkey(void) { return key;}
DLL_member* getn(void) { return n;}
DLL_member* getp(void) { return p;}
void setn(DLL_member* x) { n=x; }
void setp(DLL_member* x) { p=x; }
};
class DLL{//head
DLL_member *h;
public:
DLL(DLL_member *x):h(x){}
DLL_member* get(void) { return h;}
void set(DLL_member* x) { h=x; }
DLL_member* find(N);//if seekand exists, returns its address; else if previous exists, return its address; else return 0
int ins(N,DLL_member* m=0);//2nd parameter is optional: address of (already allocated) new member. If omitted, new allocation occurs.
int del(N,bool deallocate=true);//2nd parameter is optional: do or not deallocation. If omitted, it will.
string print(void);
};
#endif//INC_DoubleLinkedList_h
Sparse Array header file, "SparseArray.h"
Code:
#ifndef INC_SparseArray_h
#define INC_SparseArray_h
#include"DoubleLinkedList.h"
//SA in this file stands for Sparse Array
class H_DLL_member:public DLL_member{public:H_DLL_member(N x):DLL_member(x){}};//copies of DLL_member, to include in SA_member
class V_DLL_member:public DLL_member{public:V_DLL_member(N x):DLL_member(x){}};
class SA_member:public H_DLL_member, public V_DLL_member{//member of the array, part of two lists. Count: N*N
//DLL_member h,v;
public:
SA_member(N x,N y):H_DLL_member(x),V_DLL_member(y){}
};
class SA_controller: public DLL_member, public DLL{//leader of either a horizontal or a vertical list. Count: 2*N
public:
SA_controller(N x):DLL_member(x),DLL(0){}
};
class SA{//leader of the entire array. Count: 1
DLL h,v;
public:
SA():h(0),v(0){}
int ins(N,N);
DLL* geth(void) { return &h;}
DLL* getv(void) { return &v;}
//void seth(DLL* x) { h.set(x)}
//void setv(DLL* x) { v.set(x)}
string print(void);
};
Let me post the source of this last file too, as it contains few lines, but htey are quite complicated, and will probably be good examples to tell me what could be simpler
"SparseArray.cpp"
Code:
#include"SparseArray.h"
int SA::ins(N x,N y)
{
SA_controller *temp_ctrl=new SA_controller(y);
if(this->getv()->ins(y,dynamic_cast<DLL_member*>(temp_ctrl))) delete(temp_ctrl);
//make new dll member INSIDE temp_ctrl, IF it doesnt exist. This regards the vertical controller list.
temp_ctrl=new SA_controller(x);
if(this->geth()->ins(x,dynamic_cast<DLL_member*>(temp_ctrl))) delete(temp_ctrl);//Same for horizontal.
//Allocated memory: 2 sa_controllers - unsuccesfull(duplicate) entries.
//Notice how both inserts might have failed, due to already existant members, yet we cannot know the SA_member exists!
//Controller lists are OK now, and surely include v[y] and h[x].
//Possible optimisation: both inserts use find internally. We will use it another time externally here.
//It would make code (much) more complex, but faster to try to use find only twice
SA_member* temp_member=new SA_member(x,y);
if(static_cast<SA_controller*>(this->getv()->find(y))->ins(x,dynamic_cast<DLL_member*>(dynamic_cast<H_DLL_member*>(temp_member))))
{
delete(temp_member);
return 1;
}
//Explanation: find vertical controller, which exists because of previous code. Find returns its DLL_member part, so we
//static_cast it to controller. Then, as controller inherits from dll, we use ins on it, with memory target the horizontal
// dll_member component of the new SA_member we just allocated. If the insert returns error, the member already exists,
//so we exit likewise, after deleting it. Note that if theres no error, the next line won't be too.
static_cast<SA_controller*>(this->geth()->find(x))->ins(y,dynamic_cast<DLL_member*>(dynamic_cast<V_DLL_member*>(temp_member)));
return 0;
}
string SA::print(void)
{
stringstream x;
DLL_member* aux=this->getv()->get();
while(aux)
{
x<<"Now printing list with first node "<<aux->getkey()<<"\n\n";//
x<<static_cast<SA_controller*>(aux)->print();
x<<"\n\n\n";
aux=aux->getn();
}
if(x.str()=="") x<<"List is empty\n";
return x.str();
}
Uh, what happened to the identation? Hope you can read this