Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Региональный поиск дерево отрезков / source / kursovikView
.cpp// kursovikView.cpp : implementation of the CKursovikView class
//
#include "stdafx.h"
#include "kursovik.h"
#include "kursovikDoc.h"
#include "kursovikView.h"
#include "MainFrm.h"
#include "dial1.h"
#include "dial2.h"
#include "dial3.h"
#include "dial4.h"
#include "dial5.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CKursovikView
TTree* node;
CIntv *intv2;
int level_;
CRect ClientTree;
CRect ClientPoints;
CString stw="x";
CPen bluep1(PS_SOLID,1, 0x00323200);
CBrush blueb1( 0x00323200);
CPen bluep2(PS_SOLID,1, 0x00963200);
CBrush blueb2( 0x00963200);
CPen bluep3(PS_SOLID,1, 0x00B86400);
CBrush blueb3( 0x00B86400);
CPen bluep4(PS_SOLID,1, 0x00F0B864);
CBrush blueb4( 0x00F0B864);
CPen bluep5(PS_SOLID,1, 0x00F0F0BB);
CBrush blueb5( 0x00F0F0BB);
CPen redp3(PS_SOLID,1, 0x000000F0);
CPen greentree(PS_SOLID,1,0x0064A032);
IMPLEMENT_DYNCREATE(CKursovikView, CView)
BEGIN_MESSAGE_MAP(CKursovikView, CView)
//{{AFX_MSG_MAP(CKursovikView)
ON_WM_SIZE()
ON_COMMAND(ID_TOOLS_ENTERPOINTS, OnToolsEnterpoints)
ON_COMMAND(ID_TOOLS_ENTEROTREZOK, OnToolsEnterotrezok)
ON_COMMAND(ID_TOOLS_DELETEOTREZOK, OnToolsDeleteotrezok)
ON_COMMAND(ID_TOOLS_SHOWOTREZOK, OnToolsShowotrezok)
ON_COMMAND(ID_EDIT_CUT, clear)
ON_COMMAND(ID_FILE_SAVE_AS, OnFileSaveAs)
ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
ON_COMMAND(ID_TOOLS, OnTools)
//}}AFX_MSG_MAP
// Standard printing commands
ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CKursovikView construction/destruction
void DeleteTree(TTree * parent)
{
if(parent->lchild)
DeleteTree(parent->lchild);
if(parent->rchild)
DeleteTree(parent->rchild);
delete parent;
}
CKursovikView::CKursovikView()
{
elem=0;
level_=1;
temp=false;
intv2=new CIntv[level_+1];
vec=new CPoint[elem+1];
node = new TTree;
node->lchild=NULL;
node->rchild=NULL;
}
CKursovikView::~CKursovikView()
{
delete []vec;
delete []intv2;
DeleteTree(node);
}
BOOL CKursovikView::PreCreateWindow(CREATESTRUCT& cs)
{
return CView::PreCreateWindow(cs);
}
TTree *MakeTree(CIntv *intv,int elem)
{
if((elem)<1) return NULL;
TTree *node = new TTree;
if((elem)>1){
int p;
int l;
CIntv *intvleft,*intvright;
l=elem/2+elem%2;
intvleft=new CIntv[l+1];
for(int i=1;i<=l;i++){
intvleft[i].x=intv[i].x;
intvleft[i].y=intv[i].y;
}
int j=1;
p=elem/2;
intvright=new CIntv[p+2];
for(i=l+1;i<=l+p+1;i++){
intvright[j].x=intv[i].x;
intvright[j].y=intv[i].y;
j++;
}
node->val_1=intv[1].x;
node->val_2=intv[elem].y;
node->color=1;
node->lchild=MakeTree(intvleft,l);
node->rchild=MakeTree(intvright,p);
delete []intvleft;
delete []intvright;
}
else {
if((elem)==1){
node->val_1=intv[1].x;
node->val_2=intv[1].y;
node->color=1;
node->lchild=NULL;
node->rchild=NULL;
}
}
return node;
}
void SearchInTree(TTree *RN,int b,int e)
{
if(b<=RN->val_1&&RN->val_2<=e)RN->color=0;
else{
TTree *l=RN->lchild;
TTree *r=RN->rchild;
if(b<=(RN->val_1+RN->val_2)/2&&l)SearchInTree(l,b,e);
if((RN->val_1+RN->val_2)/2<=e&&r)SearchInTree(r,b,e);
}
}
void DelIntvInTree(TTree *RN)
{
RN->color=1;
TTree *l=RN->lchild;
TTree *r=RN->rchild;
if(l){l->color=1;DelIntvInTree(l);}
if(r){r->color=1;DelIntvInTree(r);}
}
void Point(CDC *dc, CPoint pnt,int State)
{
int rad=3;
dc->SelectObject(&bluep1);
dc->SelectObject(&blueb1);
dc->Ellipse(pnt.x-rad,pnt.y-rad,pnt.x+rad,pnt.y+rad);
dc->SelectObject(&bluep2);
dc->SelectObject(&blueb2);
dc->Ellipse(pnt.x-rad,pnt.y-rad,pnt.x+rad-1,pnt.y+rad-1);
dc->SelectObject(&bluep3);
dc->SelectObject(&blueb3);
dc->Ellipse(pnt.x-rad+1,pnt.y-rad+1,pnt.x+rad-2,pnt.y+rad-2);
dc->SelectObject(&bluep4);
dc->SelectObject(&blueb4);
dc->Ellipse(pnt.x-rad+1,pnt.y-rad+1,pnt.x+rad-3,pnt.y+rad-3);
dc->SelectObject(&bluep5);
dc->SelectObject(&blueb5);
dc->Ellipse(pnt.x-rad+2,pnt.y-rad+2,pnt.x+rad-4,pnt.y+rad-4);
CString buffer;
buffer.Format("%d",State);
dc->SetBkMode(TRANSPARENT);
dc->DrawText(buffer,-1,CRect(pnt.x-30,pnt.y,pnt.x+30,pnt.y+30),
DT_CENTER|DT_VCENTER|DT_SINGLELINE);
}
void Interval(CDC *dc,int x1,int x2,int y,int r)
{
if(r==1)dc->SelectObject(&bluep3);
if(r==0)dc->SelectObject(&redp3);
dc->MoveTo(x1,y);
dc->LineTo(x2,y);
dc->MoveTo(x1,y-3);
dc->LineTo(x1,y+3);
dc->MoveTo(x2,y-3);
dc->LineTo(x2,y+3);
}
void Line(CDC *dc,int x1,int y1,int x2,int y2,int r)
{
int dy=0;
int dx=0;
dc->SelectObject(&greentree);
if(x1>x2) { //налево
dc->MoveTo(x1-dx,y1+dy);
dc->LineTo(x2+dx,y2-dy);
}
else { //направо
dc->MoveTo(x1+dx,y1+dy);
dc->LineTo(x2-dx,y2-dy);
}
}
void Circle(CDC *dc,int val1,int val2,int x,int y,int r,int color)
{
dc->SelectStockObject(WHITE_BRUSH);
if(color==1)
dc->SelectObject(&greentree);
if(color==0)
dc->SelectObject(&redp3);
dc->Ellipse(x-r,y-r,x+r,y+r);
CString buffer1,buffer2,buffer3;
buffer1.Format("%d",val1);
buffer2.Format("%d",val2);
buffer3=buffer1 + "-" + buffer2;
dc->DrawText(buffer3,-1,CRect(x-r,y-r,x+r,y+r),
DT_CENTER|DT_VCENTER|DT_SINGLELINE);
}
void ShowTree(TTree *RN,CDC *dc,int LeftBorder,int RightBorder,int Level)
{
int Center=(LeftBorder+RightBorder)/2;
int y=Level*40+20;
int y2=(Level+1)*40+20;
int rad=15;
Circle(dc,RN->val_1,RN->val_2,Center,y,rad,RN->color);
TTree *l=RN->lchild;
TTree *r=RN->rchild;
if(l) {
Line(dc,Center,y+rad,(LeftBorder+Center)/2,y2,rad);
ShowTree(l,dc,LeftBorder,Center,Level+1);
}
if(r) {
Line(dc,Center,y+rad,(RightBorder+Center)/2,y2,rad);
ShowTree(r,dc,Center,RightBorder,Level+1);
}
}
/////////////////////////////////////////////////////////////////////////////
// CKursovikView drawing
void CKursovikView::OnDraw(CDC* pDC)
{
CKursovikDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
pDC->SelectObject(&bluep3);
pDC->MoveTo(ClientPoints.right-10,ClientPoints.bottom-25);
pDC->LineTo(ClientPoints.left+10,ClientPoints.bottom-25);
if(elem>2){
for(int i=1;i<=elem;i++)
{
vec[i].x=ClientPoints.left+(int)((i)*
(ClientPoints.right-ClientPoints.left-20)/elem);
vec[i].y=ClientPoints.bottom-25;
if(vec[i].x<=ClientPoints.right-10&&
vec[i].x>=ClientPoints.left+10) Point(pDC,vec[i],i);
}
ShowTree(node,pDC,ClientTree.left+10,ClientTree.right-10,1);
for(int k=1;k<level_;k++)
Interval(pDC,vec[intv2[k].x].x,vec[intv2[k].y].x,
vec[2].y-k*9,intv2[k].color);
}
CBrush blb((COLORREF)0x00C0C0C0);
CPen dk_blp(PS_SOLID,2,(COLORREF)0x00606060);
CPen lt_blp(PS_SOLID,2,(COLORREF)0x00E0E0E0);
CRgn border,tree,points;
border.CreateRectRgn(0,0,ClientX,ClientY);
tree.CreateRectRgnIndirect(&ClientTree);
points.CreateRectRgnIndirect(&ClientPoints);
border.CombineRgn(&border,&tree,RGN_XOR);
border.CombineRgn(&border,&points,RGN_XOR);
pDC->FillRgn(&border,&blb);
pDC->SelectObject(dk_blp);
pDC->MoveTo(ClientTree.left-1,ClientTree.bottom+1);
pDC->LineTo(ClientTree.left-1,ClientTree.top-1);
pDC->LineTo(ClientTree.right+1,ClientTree.top-1);
pDC->SelectObject(lt_blp);
pDC->LineTo(ClientTree.right+1,ClientTree.bottom+1);
pDC->LineTo(ClientTree.left-1,ClientTree.bottom+1);
pDC->SelectObject(dk_blp);
pDC->MoveTo(ClientPoints.left-1,ClientPoints.bottom+1);
pDC->LineTo(ClientPoints.left-1,ClientPoints.top-1);
pDC->LineTo(ClientPoints.right+1,ClientPoints.top-1);
pDC->SelectObject(lt_blp);
pDC->LineTo(ClientPoints.right+1,ClientPoints.bottom+1);
pDC->LineTo(ClientPoints.left-1,ClientPoints.bottom+1);
}
/////////////////////////////////////////////////////////////////////////////
// CKursovikView diagnostics
#ifdef _DEBUG
void CKursovikView::AssertValid() const
{
CView::AssertValid();
}
void CKursovikView::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CKursovikDoc* CKursovikView::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CKursovikDoc)));
return (CKursovikDoc*)m_pDocument;
}
#endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CKursovikView message handlers
void CKursovikView::OnSize(UINT nType, int cx, int cy)
{
ClientX=cx;
ClientY=cy;
ClientPoints.left=ClientX/2+10;
ClientPoints.top=10;
ClientPoints.right=ClientX-10;
ClientPoints.bottom=ClientY-10;
ClientTree.left=10;
ClientTree.top=10;
ClientTree.right=ClientX/2-10;
ClientTree.bottom=ClientY-10;
}
void CKursovikView::OnToolsEnterpoints()
{
if(elem<=2){
CIntv *intv,*intvleft,*intvright;
int p,l;
Cdial1 dlg;
if(elem<=2&&dlg.temp==false){
dlg.DoModal();
elem=dlg.m_npoints;
if((dlg.m_npoints<=2||dlg.m_npoints>15)&&dlg.temp==false)
{AfxMessageBox("Ошибка!Количество точек должно быть больше 2 и меньше 15.");elem=0;}
else
{
delete []vec;
vec=new CPoint[elem+1];
intv=new CIntv[elem];
for(int i=1;i<elem;i++){
intv[i].x=i;
intv[i].y=i+1;
}
l=(elem-1)/2+(elem-1)%2;
p=(elem-1)/2;
intvleft=new CIntv[l+1];
for(i=1;i<=l;i++){
intvleft[i].x=intv[i].x;
intvleft[i].y=intv[i].y;
}
int j=1;
intvright=new CIntv[p+2];
for(i=l+1;i<=l+p+1;i++){
intvright[j].x=intv[i].x;
intvright[j].y=intv[i].y;
j++;
}
DeleteTree(node);
node = new TTree;
node->val_1=1;
node->val_2=elem;
node->color=1;
node->lchild=MakeTree(intvleft,l);
node->rchild=MakeTree(intvright,p);
delete []intvright;
delete []intvleft;
delete []intv;
}
}
CClientDC* pDC=new CClientDC(this);
CKursovikView::OnDraw(pDC);
}
}
void CKursovikView::OnToolsEnterotrezok()
{
Cdial2 dlg;
CIntv *intv1;
bool tmp;
if(elem!=0)
{
tmp=true;
dlg.DoModal();
temp=dlg.temp;
if((temp==true)&&((dlg.m_num1<=0)||(dlg.m_num2<=0)||
(dlg.m_num1>elem)||(dlg.m_num2>elem)||
(dlg.m_num1==dlg.m_num2)))
AfxMessageBox("Ошибка!Отрезок неверно задан.");
else{
for(int k=1;k<level_;k++){
if((temp==true)&&(((intv2[k].x==dlg.m_num1)&&(intv2[k].y==dlg.m_num2))
||((intv2[k].x==dlg.m_num2)&&(intv2[k].y==dlg.m_num1))))
{tmp=false;AfxMessageBox("Ошибка!Отрезок уже существует.");}
}
if(temp==true&&tmp==true){
intv1=new CIntv[level_+1];
for(int i=1;i<level_;i++){intv1[i]=intv2[i];}
delete []intv2;
if(dlg.m_num1<dlg.m_num2){
intv1[level_].x=dlg.m_num1;
intv1[level_].y=dlg.m_num2;
intv1[level_].color=1;
}
else{
intv1[level_].x=dlg.m_num2;
intv1[level_].y=dlg.m_num1;
intv1[level_].color=1;
}
level_++;
intv2=new CIntv[level_+1];
for(i=1;i<level_;i++){intv2[i]=intv1[i];}
delete []intv1;
}
}
CClientDC* pDC=new CClientDC(this);
CKursovikView::OnDraw(pDC);
temp=true;
}
}
void CKursovikView::OnToolsDeleteotrezok()
{
Cdial3 dlg;
CIntv *intv;
bool tmp;
if(elem!=0&&temp==true)
{
tmp=true;
if(level_>1){
dlg.DoModal();
for(int k=1;k<level_;k++){
if(((intv2[k].x==dlg.m_num1)&&(intv2[k].y==dlg.m_num2))
||((intv2[k].x==dlg.m_num2)&&(intv2[k].y==dlg.m_num1)))
{
if(intv2[k].color==0)DelIntvInTree(node);
tmp=false;
intv=new CIntv[level_];
for(int i=1;i<k;i++)intv[i]=intv2[i];
for(i=k;i<level_;i++)intv[i]=intv2[i+1];
delete []intv2;
level_--;
intv2=new CIntv[level_+1];
for(i=1;i<level_;i++){intv2[i]=intv[i];}
delete []intv;
this->RedrawWindow();
}
}if(tmp==true&&dlg.temp==true)AfxMessageBox("Ошибка!Такой отрезок отсутствует.");
}else AfxMessageBox("Все отрезки удалены.");
}
}
void CKursovikView::OnToolsShowotrezok()
{
Cdial4 dlg;
bool tmp;
if(elem!=0&&temp==true){
tmp=true;
if(level_>1){
dlg.DoModal();
for(int k=1;k<level_;k++){
if(((intv2[k].x==dlg.m_num1)&&(intv2[k].y==dlg.m_num2))
||((intv2[k].x==dlg.m_num2)&&(intv2[k].y==dlg.m_num1)))
{
tmp=false;
intv2[k].color=0;
DelIntvInTree(node);
if(intv2[k].x>intv2[k].y)
SearchInTree(node,intv2[k].y,intv2[k].x);
if(intv2[k].y>intv2[k].x)
SearchInTree(node,intv2[k].x,intv2[k].y);
for(int i=1;i<k;i++)intv2[i].color=1;
for(i=k;i<level_;i++)intv2[i+1].color=1;
this->RedrawWindow();
}
}if(tmp==true&&dlg.temp==true)AfxMessageBox("Ошибка!Такой отрезок отсутствует.");
}else AfxMessageBox("Все отрезки удалены.");
}
}
void CKursovikView::clear()
{
elem=0;
delete []vec;
delete []intv2;
DeleteTree(node);
this->RedrawWindow();
level_=1;
temp=false;
intv2=new CIntv[level_+1];
vec=new CPoint[elem+1];
node = new TTree;
node->lchild=NULL;
node->rchild=NULL;
}
void CKursovikView::OnFileSaveAs()
{
CFileDialog fileDlg(FALSE);
CString str("Дерево отрезков");str += (TCHAR)NULL;str+="*.toi";str += (TCHAR)NULL;
fileDlg.m_ofn.lpstrFilter = str;
fileDlg.m_ofn.nFilterIndex = 1;
fileDlg.m_ofn.lpstrDefExt = "toi";
TCHAR strName[_MAX_PATH];
strName[0] = (TCHAR)NULL;
fileDlg.m_ofn.lpstrFile = strName;
if (fileDlg.DoModal() == IDOK)
{
CFile f(strName,CFile::modeCreate|CFile::modeWrite);
f.Write(&elem,1);
f.Write(&level_,1);
for(int i=1;i<level_;i++)f.Write(&intv2[i],sizeof(CIntv));
Invalidate();
f.Close();
}
}
void CKursovikView::OnFileOpen()
{
CFileDialog fileDlg(TRUE);
CString str("Дерево отрезков"); str += (TCHAR)NULL; str+="*.toi"; str += (TCHAR)NULL;
fileDlg.m_ofn.lpstrFilter = str;
fileDlg.m_ofn.nFilterIndex = 1;
fileDlg.m_ofn.lpstrDefExt = "toi";
TCHAR strName[_MAX_PATH];
strName[0] = (TCHAR)NULL;
fileDlg.m_ofn.lpstrFile = strName;
if (fileDlg.DoModal() == IDOK)
{
CKursovikView::clear();
CFile f(strName,CFile::modeRead);
f.Read(&elem,1);
CIntv *intv,*intvleft,*intvright;
int p,l;
delete []vec;
vec=new CPoint[elem+1];
intv=new CIntv[elem];
for(int i=1;i<elem;i++){
intv[i].x=i;
intv[i].y=i+1;
}
l=(elem-1)/2+(elem-1)%2;
p=(elem-1)/2;
intvleft=new CIntv[l+1];
for(i=1;i<=l;i++){
intvleft[i].x=intv[i].x;
intvleft[i].y=intv[i].y;
}
int j=1;
intvright=new CIntv[p+2];
for(i=l+1;i<=l+p+1;i++){
intvright[j].x=intv[i].x;
intvright[j].y=intv[i].y;
j++;
}
DeleteTree(node);
node = new TTree;
node->val_1=1;
node->val_2=elem;
node->color=1;
node->lchild=MakeTree(intvleft,l);
node->rchild=MakeTree(intvright,p);
delete []intvright;
delete []intvleft;
delete []intv;
f.Read(&level_,1);
delete []intv2;
intv2=new CIntv[level_+1];
for(i=1;i<level_;i++)f.Read(&intv2[i],sizeof(CIntv));
temp=true;
for(int k=1;k<level_;k++){
if(intv2[k].color==0)
{
if(intv2[k].x>intv2[k].y)
SearchInTree(node,intv2[k].y,intv2[k].x);
if(intv2[k].y>intv2[k].x)
SearchInTree(node,intv2[k].x,intv2[k].y);
}
}
CClientDC* pDC=new CClientDC(this);
CKursovikView::OnDraw(pDC);
Invalidate();
f.Close();
}
}
void CKursovikView::OnTools()
{
if(elem!=0){
int x,y,k,num;
bool h;
num=1;
Cdial5 dlg;
long int tm,tm1;
int res;
tm=elem;
tm1=(elem-2);
for(int g=1;g<elem;g++)tm*=g;
for(g=1;g<elem-2;g++)tm1*=g;
tm1=tm1*2;
res=tm/tm1;
if(elem==13)res=78;
if(elem==14)res=91;
if(elem==15)res=105;
dlg.DoModal();
if(dlg.temp==true&&dlg.m_num<=res&&dlg.m_num>0){
CIntv *intv_,*in_;
in_=new CIntv[dlg.m_num+1];
k=dlg.m_num;
do{
do{x=(int)rand();}while(x>elem||x<1);
do{y=(int)rand();}while(y>elem||y<1);
in_[num].x=x;
in_[num].y=y;
in_[num].color=1;}while(x==y);
num++;
for(int i=1;i<k;i++)
{
h=false;
do{x=(int)rand();}while(x>elem||x<1);
do{y=(int)rand();}while(y>elem||y<1);
if(x!=y){
for(int j=1;j<=num;j++){
if(((in_[j].y==y)&&(in_[j].x==x))||
((in_[j].y==x)&&(in_[j].x==y)))
{
h=true;
}
}
if(h==false){
in_[num].x=x;
in_[num].y=y;
in_[num].color=1;
num++;
}
if(h==true)k++;
}else k++;
}
int count;
count=0;
for(int l=1;l<=dlg.m_num;l++){
for(int j=1;j<=level_;j++){
if(((intv2[j].y==in_[l].y)&&(intv2[j].x==in_[l].x))||
((intv2[j].y==in_[l].x)&&(intv2[j].x==in_[l].y)))
{
in_[l].color=5;
count++;
}
}
}
intv_=new CIntv[level_+1];
for(i=1;i<level_;i++){intv_[i]=intv2[i];}
delete []intv2;
intv2=new CIntv[level_+1+dlg.m_num-count];
for(i=1;i<level_;i++){intv2[i]=intv_[i];}
delete []intv_;
for(l=1;l<=dlg.m_num;l++)
{
if(in_[l].color!=5){intv2[level_]=in_[l];level_++;}
}
CString d,n;
n.Format("%d",dlg.m_num);
d="Сгенерировано "+n+" отрезков:";
for(l=1;l<=dlg.m_num;l++){
n.Format("%d",in_[l].x);
d=d+"["+n+",";
n.Format("%d",in_[l].y);
d=d+n+"]";
}
n.Format("%d",count);
d+=". Из них "+n+" уже существуют";
AfxMessageBox(d);
delete []in_;
temp=true;
}else if(dlg.m_num>=res||dlg.m_num<=0)
{ CString b,c;
b.Format("%d",res);
c="Количество генерируемых отрезков должно быть больше 0 и меньше "+b;
AfxMessageBox(c);}
}
CClientDC* pDC=new CClientDC(this);
CKursovikView::OnDraw(pDC);
}
Соседние файлы в папке source