📄 xcommon.h
字号:
#ifndef __XCOMMON_H_0917__
#define __XCOMMON_H_0917__
#include <list>
#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <strstream>
#include <io.h>
#ifdef _AFXDLL
#include <afxwin.h>
#else
#include <windows.h>
#endif
using namespace std;
const int _1K = 1024;
const int _2K = 2048;
const int _4K = 4096;
const int _6K = 1024*6;
const int _7K = 1024*7;
const int _8K = 4096*2;
const int _32K = 4096*8;
const int MAX_LINE = 4096*20;
const int FILE_NAME_LENGTH = 100;
#define SJIS_LONGVOWEL 0x815b
const int MAX_LINE_IN_AVL = 2048;
//type define begin
enum ABOUTBLANKOUTPUT {SAME,REMOVE_BLANK};
enum REMAINFLAG {REMAIN,REMOVE};
enum REMOVEBLANK {KP_BLK,REM_BLK};
enum DIRECTION {UPWARD,DOWNWARD};
enum WORKMODE {E_MODE,J_MODE};
enum MATCH_FLAG {MULTIPLE,SINGLE,NOTHING} ;
enum BOUND {BOUND_GLOBAL,BOUND_PART};
class CPair;
template<class T> class BBT2;
typedef unsigned long ulong;
typedef unsigned int uint;
typedef char * charp;
typedef char * DATA_TYPE; // Type of node's data
typedef int BALANCE;
typedef unsigned short int uint16;
typedef unsigned char uchar;
typedef vector<char*> VECTOR;
typedef vector<char*>::iterator VECTOR_IT;
typedef vector<char*>::const_iterator CONST_VECTOR_IT;
typedef BBT2<CPair> CReplaceTree;
inline int CommonCompare(const void* a,const void* b);
void __cdecl remdup(void * base,unsigned int& cnt,int(__cdecl*comp)(const void*,const void*) = CommonCompare);
char* ExtractColumn(const char *InLine,int col,char *OutLine,const char *delimiter);
int SortWord(char *InLine,char* indelimiter,char* outdelimiter,WORKMODE mode=E_MODE,short RemoveDup = false);
struct PTRMAP
{
char *left;
char *right;
char *m_pHead;
char attr;
PTRMAP():left(NULL),right(NULL),m_pHead(NULL),attr(0){}
PTRMAP(const char* l,const char* r,const char* h,const char a)
{
left = strdup(l);
right = strdup(r);
m_pHead = strdup(h);
attr = a;
}
virtual void ReadLine(const char* szLine);
char *GetCol(int iCol)
{
return iCol?right:left;
}
void FreeBuffer()
{
if(left)
{
delete []left;
left = NULL;
}
if(right)
{
delete []right;
right = NULL;
}
if(m_pHead)
{
delete []m_pHead;
m_pHead = NULL;
}
}
~PTRMAP()
{
FreeBuffer();
}
};
class COperation
{
public:
void Set(){}
virtual void Operate(void*){}
};
class SimFileMap;
class CCompare
{
public:
virtual __int32 CompareStr(const char * pStr1, const char * pStr2, DWORD match_flag) const;
CCompare(){};
virtual ~CCompare(){};
};
class SimFileMap;
class CWorkFile
{
private:
char name[FILE_NAME_LENGTH];
char extension[FILE_NAME_LENGTH];
char attrib[6];
bool bIsFirstOpen;
ulong msgLineCount;
ulong m_iLineCount;
char m_szTmpBuffer[MAX_LINE];
char m_pSepChar[100];
SimFileMap *m_pMap;
public:
FILE* fp;
CWorkFile();
CWorkFile(const char* Name,const char* Attrib);
char* GetLine(char*);
void SetMap(SimFileMap *Map1);
void SetSepChar(char *buf);
void SetLineCount(ulong iCount){m_iLineCount = iCount;}
ulong GetLineCount(void) { return m_iLineCount;}
char * GetFieldStringByLineNo(__int32 iLineNo, __int32 iFieldNo, char * szBuf);
int open ();
char* GetName(char*);
char* GetName() const;
void running_msg ( const char* InLine, int timer = 1000 );
int ReadUnit(char *buf,int max_line,int max_col=12000);
void rewind ();
void close (){fclose (fp);};
long cdecl file_line_cnt (int mode=0);
void SetMsgCount(){msgLineCount=0;};
CWorkFile& operator=(CWorkFile&);
CWorkFile& operator<<(char*);
CWorkFile& operator<<(int);
};
class SimFileMap
{
public:
virtual int Load(CWorkFile& WK,REMOVEBLANK flag=KP_BLK);
virtual int Load(ifstream& fs,REMOVEBLANK flag=KP_BLK);
virtual int Load(FILE* fp,REMOVEBLANK flag=KP_BLK);
SimFileMap();
SimFileMap(int iInitLineCount);
virtual ~SimFileMap();
char **GetHead(){return m_pHead;}
int GetCount(){return m_iCount;}
char* GetLine(char*);
char* GetLine();
char* GetLine(int);
char* GetLine(char* OutLine,int line_no);
char* GetLineContent(char* OutLine,int line_no);
long GetOffset(int line_no);
void rewind();
int RemainColumn(int n,const char *pszDelimiter);
int LineCount();
int Print_Data(FILE*);
int Print_Data(LPCSTR lpFilename);
int PrintSortData(FILE*,bool flag=true);
int PrintSortData(LPCSTR lpFilename,bool flag=true);
void SortMap();
void ForceSort();
bool IsValidLineNo(int iLineNo);
int SearchPreviousString(const char* Line,int Len,int CurrentLineNo);
int SearchAfterwardString(char *Line,int Len,int CurrentLineNo);
int SearchAfterwardLessString(char *Line,int Len,int CurrentLineNo);
int search_next_str(int start_line,char* next_str,char* end_str);
int BinSearch(char *pszKey,int &nNearLineNo);
int BinSearchLarge(char *pszKey,int &nNearLineNo);
char* replace_line(int line_num,char* new_line);
static void ShowProgress(const char* lpMsg,int iInterval = 2000,int iLen = 50);
int AppendTail(int iLineNo,LPCSTR lpStr);
int AppendTail(LPCSTR lpStr);
int InsertLine(int iLineNo,LPCSTR lpStr);
int DeleteLine(int iLineNo);
bool Swap(SimFileMap & Map);
int ReplaceLastLine(LPCSTR lpStr);
int GetLastLine(LPSTR lpStr);
int EmptyLine(int iLineNo)
{
delete []m_pHead[iLineNo];
m_pHead[iLineNo] = NULL;
return 1;
}
virtual void Flush()
{
FreeMainArray();
m_iCount = 0;
}
virtual void Input(LPCSTR lpStr);
void Swap(int iS,int iD)
{
char *pTemp = m_pHead[iS];
m_pHead[iS] = m_pHead[iD];
m_pHead[iD] = pTemp;
}
protected:
int m_iCount;
char **m_pHead;
int m_iCurrentPos;
int *m_pOffsetArray;
char ***m_pSearchArray;
int m_iMaxCount; //The max value I allocated buffer
private:
void FreeMainArray()
{
if(m_pHead == NULL)
return;
for(int i=0;i<m_iCount;i++)
{
if(m_pHead[i])
{
delete []m_pHead[i];
m_pHead[i] = NULL;
}
}
}
void FreeStruct()
{
if(m_pHead)
{
delete []m_pHead;
m_pHead = NULL;
}
if(m_pSearchArray)
{
delete []m_pSearchArray;
m_pSearchArray = NULL;
}
if(m_pOffsetArray)
{
delete []m_pOffsetArray;
m_pOffsetArray = NULL;
}
}
void ExpandMainArray(int iIncrement = 2000);
};
class CPtrMap
{
public:
char* m_pKey;
char* m_pOther;
public:
CPtrMap(){m_pKey = NULL;m_pOther = NULL;}
CPtrMap(char* a,char* b)
{
m_pKey = strdup(a);
m_pOther = strdup(b);
}
CPtrMap(CPtrMap& d)
{
m_pKey = strdup(d.m_pKey);
m_pOther = strdup(d.m_pOther);
}
virtual ~CPtrMap(){EmptyContent();}
virtual void Merge(CPtrMap& m){}
int compare(CPtrMap& d){return strcmp(m_pKey,d.m_pKey);}
CPtrMap& operator =(CPtrMap& d)
{
EmptyContent();
m_pKey = strdup(d.m_pKey);
m_pOther = strdup(d.m_pOther);
return *this;
}
void OutputToFile(FILE *fp)
{
fprintf(fp,"%s\t%s\n",m_pKey,m_pOther);
//fprintf(fp,"%s\n",m_pOther);
}
private:
virtual void EmptyContent();
};
class CSortPtrMap:public CPtrMap
{
public:
CSortPtrMap():CPtrMap()
{
strcpy(OutDelimter," ");
}
CSortPtrMap(char* a,char* b):CPtrMap(a,b)
{
strcpy(OutDelimter," ");
}
virtual void Merge(CPtrMap& m)
{
char tmpbuf[8000];
sprintf(tmpbuf,"%s%c%s",m_pOther,*OutDelimter,m.m_pOther);
free(m_pOther);
m_pOther=strdup(tmpbuf);
}
virtual void OutputToFile(FILE *fp)
{
fprintf(fp,"%s\t%s\n",m_pKey,m_pOther);
}
virtual int compare(CPtrMap& d)
{
return strcmp(m_pKey,d.m_pKey);
}
void SetDelimter(char *pDelimter) {OutDelimter[0]=*pDelimter;}
private:
//char tmpbuf[8000];
char OutDelimter[8];
};
template <class T> class BBT2;
template <class T> class BBT2//Balance Binary Tree
{
public:
class BBT_NODE
{
public:
T data;
BBT_NODE(T &t){data=t; left_childptr=NULL; right_childptr=NULL; bal_fact=0;}
BBT_NODE( ){ left_childptr=NULL; right_childptr=NULL; bal_fact=0;}
~BBT_NODE(){}
short int bal_fact;
BBT_NODE *left_childptr;
BBT_NODE *right_childptr;
};
typedef BBT_NODE * NODE_PTR;
private:
NODE_PTR root_ptr;
unsigned int TOTAL_NODE_NUM;
void delete_all_node(NODE_PTR );
void traverse_Preorder(void (*f)(T&),NODE_PTR );
void traverse_Postorder(void (*f)(T&),NODE_PTR );
void traverse_Inorder(void (*f)(T&),NODE_PTR );
void traverse_Preorder_and_delete(void (*f)(T&),NODE_PTR tree_ptr);
public:
void PreTraverse(COperation &op,NODE_PTR node_ptr) //Preorder traverse the tree and operate on every node
{
if(node_ptr)
{
PreTraverse(op,node_ptr->left_childptr);
op.Operate(node_ptr);
PreTraverse(op,node_ptr->right_childptr);
}
}
void InTraverse(COperation &op,NODE_PTR node_ptr) // Inorder traverse the tree and operate on every node
{
if(node_ptr)
{
InTraverse(op,node_ptr->left_childptr);
op.Operate(node_ptr);
InTraverse(op,node_ptr->right_childptr);
}
}
void PostTraverse(COperation &op,NODE_PTR node_ptr) // Postorder traverse the tree and operate on every node
{
if(node_ptr)
{
PostTraverse(op,node_ptr->right_childptr);
op.Operate(node_ptr);
PostTraverse(op,node_ptr->left_childptr);
}
}
void PreTraverseWholeTree(COperation &op){ PreTraverse(op,root_ptr);}
void InTraverseWholeTree(COperation &op){ InTraverse(op,root_ptr);}
void PostTraverseWholeTree(COperation &op){ PostTraverse(op,root_ptr);}
void PreOrder (void (*f)(T&) ){traverse_Preorder (f, root_ptr);}
void PostOrder (void (*f)(T&) ){traverse_Postorder(f, root_ptr);}
void InOrder (void (*f)(T&) ){traverse_Inorder (f, root_ptr);}
void DeleteTree( ){delete_all_node ( root_ptr);}
void PreOrderOutputAll(FILE *fp)
{
PreOrderOutput(fp,root_ptr);
}
void PreOrderOutput(FILE *fp,NODE_PTR tree_ptr)
{
if(tree_ptr)
{
PreOrderOutput(fp,tree_ptr->left_childptr);
(tree_ptr->data).OutputToFile(fp);
PreOrderOutput(fp,tree_ptr->right_childptr);
}
}
BBT2();
BBT2(BBT2<T> &tree){ tree.copy_to(*this);}
~BBT2();
T* add_node(T&t);
void empty(void);
int is_empty() {return root_ptr == NULL;}
unsigned int total_node_num(void){return TOTAL_NODE_NUM;}
T * search_node(T&t);
void copy_to(BBT2<T> &tree);
void move_to(BBT2<T> &tree);
void traverse(void (*)(T&),int order=PREORDER);
void traverse_and_empty(void (*)(T&));
void operator=(BBT2<T>& tree) { empty();tree.copy_to(*this);}
int GetApproximateDeepth();
};
/*
template <class T> inline BBT2<T>::BBT_NODE::BBT_NODE(T &t)
{
data=t;
left_childptr=NULL;
right_childptr=NULL;
bal_fact=0;
}*/
/*
template <class T> inline BBT2<T>::BBT_NODE::~BBT_NODE()
{
data.DEL();
}
*/
template <class T> inline int BBT2<T>::GetApproximateDeepth()
{
NODE_PTR p=root_ptr;
int i=0;
while(p)
{
if(p->bal_fact<0)
p=p->right_childptr;
else
p=p->left_childptr;
i++;
}
return i;
}
template <class T> inline BBT2<T>::BBT2()
{
root_ptr = NULL;
TOTAL_NODE_NUM = 0;
}
template <class T> inline BBT2<T>::~BBT2()
{
empty();
}
template <class T> inline void BBT2<T>::empty(void)
{
delete_all_node(root_ptr);
root_ptr = NULL;
TOTAL_NODE_NUM = 0;
}
template <class T> void BBT2<T>::delete_all_node(NODE_PTR p)
{
if(p)
{
delete_all_node(p->right_childptr);
delete_all_node(p->left_childptr);
delete p;
}
}
template <class T> T * BBT2<T>::add_node(T &new_data)
{
NODE_PTR curr_ptr = root_ptr,
new_ptr, //Pointer to new node
most_recent_ptr = root_ptr, // Most recent node with
// B.F. -1, or +1
most_recent_child_ptr, // Child of most recent node,
new_root_ptr, // New subtree root after rebalancing
most_recents_parent_ptr = NULL,// Parent of most recent node
parent_ptr = NULL; // Node that new node is child of.
short int unbal_flag; // Tree unbalanced after insertion
int rebal_direc; // Rebalancing direction after insertion
if(curr_ptr==NULL) // AVL tree is empty
{
new_ptr =new BBT_NODE(new_data);
++TOTAL_NODE_NUM;
root_ptr = new_ptr;
}
else
{
//
// While location the insertion ponter for
// the new node, see if the node already exists.
// while searching, keep book-keeping of the new
// node's parent, nearest ancestor, a
// curr_ptr = root_ptr;
while(curr_ptr!=NULL)
{
if(curr_ptr->bal_fact != 0)
{
most_recent_ptr = curr_ptr;
most_recents_parent_ptr = parent_ptr;
}
if((rebal_direc=new_data.compare(curr_ptr->data))==0)
{
(curr_ptr->data).Merge(new_data);//DUP(new_data);
return &(curr_ptr->data); // Data already exists
}
if(rebal_direc<0)
{
// search for it in left subtree
parent_ptr=curr_ptr;
curr_ptr = curr_ptr->left_childptr;
}
else
{
// search for it in right subtree
parent_ptr=curr_ptr;
curr_ptr = curr_ptr->right_childptr;
}
}
//end of the while loop
// Data is not found in AVL tree; creat it.
new_ptr =new BBT_NODE(new_data);
++TOTAL_NODE_NUM;
// complying with "ascending order" rule
// insert it as a left or right child of
// the parent node, pointed to by 'parent_ptr'.
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -