This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
Bug Report Egcs 1.1b
- To: egcs-bugs at cygnus dot com
- Subject: Bug Report Egcs 1.1b
- From: Sébastien Bricout <sbricout at mail dot club-internet dot fr>
- Date: Sat, 6 Mar 1999 01:44:31 -0500
Hello,
CPU: 6x86L-PR200+
Debian 2.0
Kernel: 2.2.2-ac7, compiled with gcc-2.7.2.3
Egcs 1.1b, compiled with gcc-2.7.2.3
In the compilation of VDKBuilder snapshot 030299:
chezsb:/usr/src/vdkbuilder-0.1.1/vdkbuilder# make
g++ -c -g -Wall -DVDKBDEBUG -DHAVE_SYNTAX -DHAVE_HINTS -I./ `vdk-config --cflags` -o vdkb_editor.o vdkb_editor.cc
vdkb_editor.cc:44: warning: ANSI C++ forbids declaration `last_pos' with no type/usr/local/include/vdk/vdkbtrees.h: In instantiation of `RedBlackNode<VDKBHint>':
/usr/local/include/vdk/vdkbtrees.h:555: instantiated from `AbstractBinaryTree<VDKBHint,RedBlackNode<VDKBHint> >::find<VDKBHint, RedBlackNode<VDKBHint>>(const
VDKBHint &)'
vdkb_editor.cc:57: instantiated from here
/usr/local/include/vdk/vdkbtrees.h:555: Internal compiler error.
/usr/local/include/vdk/vdkbtrees.h:555: Please submit a full bug report to `egcs-bugs@cygnus.com'.
make: *** [vdkb_editor.o] Error 1
--
Sébastien Bricout
sbricout@club-internet.fr
/*
* ===========================
* VDK Builder
* Version 0.1
* Revision 0.0
* November 1998
* ===========================
*
* Copyright (C) 1998,1999 Mario Motta
* Developed by Mario Motta <mmotta@guest.net>
*
* Based on VDK Library
* Copyright (C) 1998, Mario Motta
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
* 02111-1307, USA.
*
*/
#include <vdkb_editor.h>
#include <vdkb.h>
#include <vdkb_locale.h>
#include <vdkb_utils.h>
#include <vdk/FileDialog.h>
#include <vdk/FileSaveAsDialog.h>
#include <vdkb_search.h>
#include <vdkb_replace.h>
static char buff[512];
/*
search stuff
*/
static last_pos = 0;
static char* match = NULL;
/*
*/
#ifdef HAVE_HINTS
char*
VDKBEditor::HintCallback (char *match, gpointer data)
{
VDKBEditor* editor = (VDKBEditor*) data;
VDKBHint hint,*found = NULL;
hint.match = match;
if(editor->hintDb)
found = editor->hintDb->find(hint);
return found ? (char*) found->text : NULL;
}
#endif
///////////////// signal stuff //////////
DEFINE_SIGNAL_LIST(VDKBEditor,VDKForm);
DEFINE_SIGNAL_MAP(VDKBEditor,VDKForm)
ON_SIGNAL(nbook,switch_page_signal,OnPageChanged),
ON_SIGNAL(messages,select_row_signal,JumpToError),
ON_SIGNAL(closePage,activate_signal,OnClosePage),
ON_SIGNAL(toggleHeader,activate_signal,OnToggleHeader),
ON_SIGNAL(saveas,activate_signal,SaveAs),
ON_SIGNAL(search,activate_signal,Search),
ON_SIGNAL(repeatsearch,activate_signal,RepeatSearch),
ON_SIGNAL(hilite,activate_signal,Hilite)
END_SIGNAL_MAP
//////////////////////////////////////////////////
/*
*/
VDKBEditor::VDKBEditor(VDKForm* owner):
VDKForm(owner)
{
ForceToClose = false;
#ifdef HAVE_HINTS
// load hints database
hintDb = new HintDb;
VDKBuilder *app = (VDKBuilder*) Application();
VDKString user = app->user_home;
sprintf(buff,"%s/.vdkb/lang/%s.%s",
(char*) user,"vdkhints","en");
if (LoadHintDb(buff))
{
#ifdef VDKBDEBUG
printf("\n%s successfully loaded",buff);
fflush(stdout);
#endif
;
}
else
{
#ifdef VDKBDEBUG
printf("\n%s error loading",buff);
fflush(stdout);
#endif
;
}
#endif
}
/*
*/
VDKBEditor::~VDKBEditor()
{
#ifdef HAVE_HINTS
if(hintDb)
delete hintDb;
#endif
}
/*
*/
void
VDKBEditor::Setup()
{
Title = editor_prompts[0];
VDKPaned* paned = new VDKPaned(this);
nbook = new VDKBNotebook(this);
paned->Pack(nbook,1,true,false);
messages = new VDKCustomList(this,1,NULL,GTK_SELECTION_EXTENDED);
paned->Pack(messages,2,false,true);
Add(paned);
bar = new VDKPanelbar(this,3);
bar->Panels()[2]->Justify = GTK_JUSTIFY_RIGHT;
Add(bar,r_justify,false,false,false);
// makes a pop menu
popmenu = new VDKMenu(this);
toggleHeader = new VDKMenuItem(popmenu,editor_prompts[3]);
closePage = new VDKMenuItem(popmenu,editor_prompts[4]);
saveas = new VDKMenuItem(popmenu,editor_prompts[5]);
popmenu->Separator();
search = new VDKMenuItem(popmenu,main_menu_prompts[30]);
sprintf(buff,"%s (F3)",main_menu_prompts[31]);
repeatsearch = new VDKMenuItem(popmenu,buff);
sprintf(buff,"%s (F4)",main_menu_prompts[33]);
undo = new VDKMenuItem(popmenu,buff);
sprintf(buff,"%s (F5)",main_menu_prompts[34]);
redo = new VDKMenuItem(popmenu,buff);
hilite = new VDKMenuItem(popmenu,main_menu_prompts[35]);
// since redo capabilty isn't yet implemented, set them as disabled
redo->Enabled = false;
// hilite enabled in HAVE_SYNTAX only
#ifndef HAVE_SYNTAX
hilite->Enabled = false;
#endif
/*
since popmenu could never be popped
better add it to form items even if VDKMenu::Popup()
does the job. VDKList::add() will ensure won't be added twice
and GC will detect it even if never popped.
*/
AddItem(popmenu);
/*
Signals will come up from one of VDKBText's
contained into VDKBNotebook pages.
Since these signals are not provided by gtk+
put <gtk> arg as false, so will be dispatched by VDK
*/
SignalConnect(nbook,"text_changed",&VDKBEditor::OnTextChanged,false);
SignalConnect(nbook,"line_changed",&VDKBEditor::OnLineChanged,false);
SignalConnect(nbook,"pop_menu",&VDKBEditor::OnPopMenu,false);
SignalConnect(nbook,"repeat_search_text",&VDKBEditor::RepeatSearch,false);
SignalConnect(nbook,"no_more_undo",&VDKBEditor::NoMoreUndo,false);
}
/*
*/
void
VDKBEditor::OnShow(VDKForm*)
{
VDKPoint ownerPos = Owner()->Position;
VDKPoint ownerSize = Owner()->Usize;
VDKPoint p(270,ownerPos.Y()+ownerSize.Y()+60);
Position = p;
VDKPoint size = VDKBuilder::ideDefaults.editor.size;
SetSize(size.X(),size.Y());
}
/*
*/
void VDKBEditor::AddNewUnit()
{
// read defaults
char* cc_ext = (char*) VDKBuilder::ideDefaults.unit.cc_ext;
char* h_ext = (char*) VDKBuilder::ideDefaults.unit.h_ext;
char* unit = (char*) VDKBuilder::ideDefaults.unit.def_name;
int count = VDKBuilder::ideDefaults.unit.count;
VDKBText *text;
// add .cc
sprintf(buff,"%s%d.%s",unit,count,cc_ext);
text = new VDKBText(this,true,buff);
textlist.add(text);
#ifdef HAVE_SYNTAX
text->Hilite = true;
#ifdef HAVE_HINTS
text->InstallHints(VDKBEditor::HintCallback,this);
#endif
#endif
nbook->AddPage(text,buff);
// add .h
sprintf(buff,"%s%d.%s",unit,count,h_ext);
text = new VDKBText(this,true,buff);
#ifdef HAVE_SYNTAX
text->Hilite = true;
#ifdef HAVE_HINTS
text->InstallHints(VDKBEditor::HintCallback,this);
#endif
#endif
textlist.add(text);
nbook->AddPage(text,buff);
// sets active page
nbook->ActivePage = textlist.size()-1;
// finished, update unit count
VDKBuilder::ideDefaults.unit.count += 1;
}
/*
*/
void VDKBEditor::AddText(char* text_name, bool editable,bool hilite)
{
VDKBText *text = new VDKBText(this,editable,text_name);
// add a text to textlist
textlist.add(text);
#ifdef HAVE_HINTS
text->InstallHints(VDKBEditor::HintCallback,this);
#endif
nbook->AddText(text,text->ShortName(),hilite);
}
//////////////////////// signal process ////////////////////
bool
VDKBEditor::JumpToError(VDKObject* )
{
char *tokens = "$%";
int t,z;
int row = messages->Selected.Row();
if(row < 0 || row >= messages->Tuples.size())
return true;
VDKString errmess = messages->Tuples[row][0];
VDKString file;
int line = 0;
char* err = new char[strlen((char*) errmess)+1];
strcpy(err,(char*) errmess);
// change first two ":" with tokens
for(t = 0,z=0; err[t]; t++)
{
if( err[t] == ':')
{
err[t] = tokens[z++];
if(!tokens[z])
break;
}
}
char * p;
if( (p = ExtractWord(err,buff,"","$")) )
file = buff;
if ( (p = ExtractWord(err,buff,"$","%")) )
line = atoi(buff);
if((line == 0) || access((char*) file ,F_OK) || ( ! GoToLine(file,line)) )
{
gdk_beep();
bar->Panels()[0]->Caption = "no error to go";
}
delete err;
return true;
}
/*
*/
bool
VDKBEditor::GoToLine(VDKString& file, int line)
{
int t;
TextListIterator li(textlist);
// activate or load a new text
for(t=0;li;li++,t++)
{
VDKString temp = li.current()->Filename();
if( temp == file)
{
nbook->ActivePage = t;
break;
}
}
// not found, so load a new text
if(t >= textlist.size())
{
AddText((char*) file, true,true);
nbook->ActivePage = t;
}
// finally goes to line
return textlist[t]->GoToLine(line);
}
/*
*/
bool
VDKBEditor::OnTextChanged(VDKObject* )
{
// editor says that some text was changed
// so let's user to know
int activePage = nbook->ActivePage;
char* p = textlist[activePage]->ShortName();
if(textlist[activePage]->Changed)
{
sprintf(buff,"%s%s",editor_prompts[1],p);
bar->Panels()[0]->Caption = buff;
}
int line = textlist[activePage]->CurrentLine;
sprintf(buff,"%s%d",editor_prompts[2],line);
bar->Panels()[2]->Caption = buff;
return true;
}
/*
*/
bool
VDKBEditor::OnPageChanged(VDKObject* )
{
int activePage = nbook->ActivePage;
char* p = textlist[activePage]->ShortName();
if(textlist[activePage]->Changed)
{
sprintf(buff,"%s%s",editor_prompts[1],p);
bar->Panels()[0]->Caption = buff;
}
else
bar->Panels()[0]->Caption = " ";
int line = textlist[activePage]->CurrentLine;
sprintf(buff,"%s%d",editor_prompts[2],line);
bar->Panels()[2]->Caption = buff;
// set to 0 last pos in search.
last_pos = 0;
return true;
}
/*
*/
bool
VDKBEditor::OnLineChanged(VDKObject* )
{
int activePage = nbook->ActivePage;
int line = textlist[activePage]->CurrentLine;
sprintf(buff,"%s%d",editor_prompts[2],line);
bar->Panels()[2]->Caption = buff;
return true;
}
/*
*/
bool
VDKBEditor::CanClose()
{
UpdateFiles();
return true;
/*
// can be closed via mainform only.
if(ForceToClose)
return true;
else
{
Visible = false;
return false;
}
*/
}
/*
*/
void
VDKBEditor::UpdateFiles()
{
TextListIterator li(textlist);
// skip first page that is always
// an uneditable makefile image
li++;
for(;li;li++)
{
// has to be saved ?
if(li.current()->Changed)
{
sprintf(buff,"%s\n%s",
(char*) li.current()->Filename(),
user_messages[user_request_save]);
if(Application()->MessageBox(APPNAME,
buff,
MB_ICONINFORMATION|MB_YESNO,
user_messages[user_ok],
user_messages[user_no]) == IDYES)
{
// never saved
// it's a new unit, changes sentinel in .h
if(access(li.current()->Filename(),F_OK))
{
// ask to user
FileStringArray selections;
VDKFileSaveAsDialog *child =
new VDKFileSaveAsDialog(this,&selections,
file_dialog_prompts[3]);
child->ShowModal();
if(selections.size() > 0)
{
UpdateUnit(li.current(),selections[0]);
li.current()->SaveToFile(selections[0]);
}
}
// or unsaved ?
else
li.current()->SaveToFile((char*) li.current()->Filename());
li.current()->Changed = false;
}
else
// user forced to be considered saved
li.current()->Changed = false;
}
}
}
/*
*/
void
VDKBEditor::FillMessages(VDKBStringList* list)
{
messages->Clear();
messages->Freeze();
VDKBStringListIterator li(*list);
for(;li;li++)
{
char* p = (char*) li.current();
messages->AddRow(&p);
}
messages->Thaw();
if(list->size() > 0)
messages->SelectRow(0,0);
}
/*
*/
bool
VDKBEditor::OnPopMenu(VDKObject* )
{
int activePage = nbook->ActivePage;
if(activePage == 0)
return true;
repeatsearch->Enabled = match != NULL;
popmenu->Popup();
return TRUE;
}
/*
*/
bool
VDKBEditor::OnClosePage(VDKObject* )
{
int activePage = nbook->ActivePage;
VDKBText* text;
if(activePage < 0 || activePage >= textlist.size())
return true;
else
text = textlist[activePage];
//
if(text->Changed)
{
sprintf(buff,"%s\n%s",
(char*) text->Filename(),
user_messages[user_request_save]);
if(Application()->MessageBox(APPNAME,
buff,
MB_ICONINFORMATION|MB_YESNO,
user_messages[user_ok],
user_messages[user_no]) == IDYES)
{
// never saved
if(access(text->Filename(),F_OK))
{
// ask to user
FileStringArray selections;
VDKFileSaveAsDialog *child =
new VDKFileSaveAsDialog(this,&selections,
file_dialog_prompts[3]);
child->ShowModal();
if(selections.size() > 0)
{
UpdateUnit(text,selections[0]);
text->SaveToFile(selections[0]);
}
}
// or unsaved ?
else
text->SaveToFile((char*) text->Filename());
text->Changed = false;
}
}
/* removes text from list and notebook
currently a bug into gtk_notebook_remove_page(int)
when gtk_text is patched by Mailund patch.
this sequence sigsegvs:
1. open a page into editor
2. close the page
3. open it again
4. close it: sigsegv's gtk_note_book_remove_page()
sigh :-(
*/
if(textlist.unlink(activePage))
nbook->RemovePage(activePage);
OnPageChanged(NULL);
return true;
}
/*
*/
void
VDKBEditor::UpdateUnit(VDKBText* text, VDKString& rep_s)
{
// char* cc_ext = (char*) VDKBuilder::ideDefaults.unit.cc_ext;
char* h_ext = (char*) VDKBuilder::ideDefaults.unit.h_ext;
VDKString ext;
VDKString name = text->ShortName();
VDKString replace;
char *z = get_shortfilename(rep_s);
if(z) replace = z;
else return;
if(!name.isNull())
{
// extract name and extension
char *p = get_extension((char*) name);
if(p) { *p = '\0'; p++; ext = p; }
else return;
p = get_extension(replace);
if(p) *p = '\0';
else return;
}
else
return;
// change sentinel
if(!strcmp(ext,h_ext))
{
sprintf(buff,"_%s_h",(char*) name);
VDKString match = buff;
sprintf(buff,"_%s_h",(char*) replace);
replace = buff;
int pos = text->Search(match, 0, true);
if(pos>=0)
{
pos = Replace(text,pos,match,replace);
pos = text->Search(match, pos, true);
}
if(pos>=0)
pos = Replace(text,pos,match,replace);
}
}
int
VDKBEditor::Replace(VDKBText* text, int pos, char* match, char* replace)
{
text->Pointer = pos;
text->ForwardDelete(strlen(match));
text->Pointer = pos;
text->TextInsert(replace);
return pos+strlen(replace);
}
/*
*/
bool
VDKBEditor::OnToggleHeader(VDKObject* )
{
char* cc_ext = (char*) VDKBuilder::ideDefaults.unit.cc_ext;
char* h_ext = (char*) VDKBuilder::ideDefaults.unit.h_ext;
int activePage = nbook->ActivePage;
VDKBText* text;
if(activePage < 0 || activePage >= textlist.size())
return true;
else
text = textlist[activePage];
// look for that
VDKString name = text->Filename();
VDKString ext;
char* p = get_extension((char*) name);
if(p)
{
*p++ = '\0';
ext = p;
sprintf(buff,"%s.%s",(char*) name,
(!strcmp(ext,cc_ext)) || (!strcmp(ext,"c")) ?
h_ext :
cc_ext);
name = buff;
}
else
return true;
// search in list
int t = 0;
bool found = false;
bool exists = !access(name,F_OK);
TextListIterator li(textlist);
for(;li;li++,t++)
{
if(! strcmp(li.current()->Filename(),name))
{
found = true;
break;
}
}
if(found && exists)
{
nbook->ActivePage = t;
return true;
}
else if(! found && exists)
{
AddText(name,true,true);
nbook->ActivePage = textlist.size()-1;
}
else if(! exists)
{
FileStringArray selections;
VDKFileDialog *child = new VDKFileDialog(this,&selections,
file_dialog_prompts[0]);
sprintf(buff,"*.%s",
(!strcmp(ext,cc_ext)) || (!strcmp(ext,"c")) ?
h_ext :
cc_ext);
child->Filter = buff;
child->ShowModal();
if(selections.size() > 0)
AddText(selections[0],true,true);
}
return true;
}
/*
*/
bool
VDKBEditor::SaveAs(VDKObject* )
{
int activePage = nbook->ActivePage;
FileStringArray selections;
VDKFileSaveAsDialog *child =
new VDKFileSaveAsDialog(this,&selections,
file_dialog_prompts[3]);
child->ShowModal();
if(selections.size() <= 0)
return true;
VDKBText* text = textlist[activePage];
text->Filename(selections[0]);
text->SaveToFile((char*) text->Filename());
text->Changed = false;
#ifdef VDKBDEBUG
printf("\nsaved:%s",(char*) text->Filename());
fflush(stdout);
#endif
nbook->Pages[activePage]->TabLabel->Caption = text->ShortName();
return true;
}
/*
*/
bool
VDKBEditor::Search(VDKObject*)
{
char* st = NULL;
int activePage = nbook->ActivePage;
if(activePage == 0)
return true;
VDKBSearchForm *dlg = new VDKBSearchForm(this,&st);
dlg->Setup();
dlg->ShowModal();
// dlg return st to search newly allocated (or NULL)
if(st)
{
last_pos = 0;
if(match)
delete match;
match = new char[strlen(st)+1];
strcpy(match,st);
delete st;
VDKBText* text;
text = textlist[activePage];
last_pos = text->Search(match, last_pos, true);
last_pos = last_pos > 0 ? last_pos + strlen(match): last_pos;
}
return true;
}
/*
*/
bool
VDKBEditor::RepeatSearch(VDKObject*)
{
VDKBText* text;
int activePage = nbook->ActivePage;
if(activePage == 0 || ! match)
return true;
else
text = textlist[activePage];
int pos = text->Search(match, last_pos, true);
sprintf(buff,"%s\n%s",
search_dialog_prompts[19],
search_dialog_prompts[20]);
if(pos >= 0)
last_pos = pos+strlen(match);
else if(Application()->MessageBox(APPNAME,
buff,
MB_ICONINFORMATION|MB_YESNO,
user_messages[user_ok],
user_messages[user_no]) == IDYES)
{
last_pos = 0;
RepeatSearch(NULL);
}
return true;
}
/*
*/
bool
VDKBEditor::NoMoreUndo(VDKObject*)
{
sprintf(buff,"%s",editor_prompts[6]);
bar->Panels()[0]->Caption = buff;
gdk_beep();
return true;
}
/*
*/
void
VDKBEditor::ReplaceText(void)
{
VDKBText* text;
int activePage = nbook->ActivePage;
if(activePage <= 0)
return ;
else
text = textlist[activePage];
VDKBReplaceForm *dlg = new VDKBReplaceForm(this,text);
dlg->Setup();
dlg->ShowModal();
}
/*
*/
/*
*/
bool
VDKBEditor::Hilite(VDKObject* )
{
VDKBText* text;
int activePage = nbook->ActivePage;
if(activePage <= 0)
return true;
else
text = textlist[activePage];
#ifdef HAVE_SYNTAX
VDKBMainForm* ownerform = (VDKBMainForm*) Owner();
ownerform->StartTimer();
sprintf(buff,"%s:%s",editor_prompts[7],text->Filename());
bar->Panels()[0]->Caption = buff;
gtk_editor_hilite_buffer (GTK_EDITOR(text->WrappedWidget()));
bar->Panels()[0]->Caption = editor_prompts[8];
ownerform->StopTimer();
#endif
return true;
}
#ifdef HAVE_HINTS
/*
*/
bool
VDKBEditor::LoadHintDb(char* fn)
{
VDKBHint hint;
char line[1024],c,*p;
char match[128],text[1024];
if(! hintDb)
return false;
FILE *fp = fopen(fn,"r");
if(!fp )
return false;
p = line;
while ((c = fgetc(fp)) != EOF )
{
// only tab is used to format hints
if(c != '\t')
*p++ = c;
if(c == '}')
{
*++p = '\0';
p = line;
if(ExtractWord(line,match,"[","]") &&
ExtractWord(line,text,"{","}") )
{
hint.match = match;
hint.text = text;
hintDb->add(hint);
}
}
}
fclose(fp);
return true;
}
#endif
/*
* ===========================
* VDK Visual Development Kit
* Version 0.5
* November 1998
* ===========================
*
* Copyright (C) 1998, Mario Motta
* Developed by Mario Motta <mmotta@guest.net>
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
* 02111-1307, USA.
*
*/
#ifndef VDKBTREES_H
#define VDKBTREES_H
// --------------------------
// Abstract class template,
// --------------------------
template<class T, class Node>
class AbstractBinaryNode {
public:
AbstractBinaryNode() { }
AbstractBinaryNode(const T& _object,
Node *_parent = 0,
Node *_left = 0,
Node *_right = 0);
virtual ~AbstractBinaryNode() { }
// Subtree arrangement
virtual Node *Clone(Node *_parent) const;
virtual void RemoveSubtree();
virtual Node *LeftRotate(Node *root);
virtual Node *RightRotate(Node *root);
virtual int CheckTreeProperties(const Node *);
virtual int IsLeftChild() const;
virtual int IsRightChild() const;
// Adding a node and deleting
virtual Node *add(const T& x);
virtual Node *unlink(Node *z);
// Find
virtual Node *find(const T& x);
virtual Node *findNearest(const T& x);
// Tree trasverse
virtual Node *Minimum();
virtual Node *Maximum();
virtual Node *Predecessor();
virtual Node *Successor();
// Miscellaneous
virtual T *Object();
public:
T object;
Node *left, *right, *parent;
};
template<class T>
class BinaryNode : public AbstractBinaryNode<T, BinaryNode<T> > {
public:
// Constructors and destructor
BinaryNode() { }
BinaryNode(const T& object,
BinaryNode<T> *parent = 0,
BinaryNode<T> *left = 0,
BinaryNode<T> *right = 0):
AbstractBinaryNode<T, BinaryNode<T> >(object, parent, left, right) { }
virtual ~BinaryNode() { }
};
//////////////////////////////////////////////////////
// Different ways to iterate on the binary tree.
enum BtreeIteratorMode { BtMinKey, BtRootKey, BtMaxKey };
template<class T, class Node>
class AbstractBinaryTree {
public:
AbstractBinaryTree();
AbstractBinaryTree(const AbstractBinaryTree<T, Node>&);
AbstractBinaryTree<T, Node>& operator=(const AbstractBinaryTree<T, Node>&);
virtual ~AbstractBinaryTree();
virtual void add(const T&); // Add a node
virtual void unlink(const T&); // Remove a node
virtual T *find(const T& q);
virtual int IsEmpty() const { return root == 0; }
virtual Node *IteratorRoot() const;
virtual Node *IteratorFind(const T& x) const;
virtual int CheckTreeProperties();
unsigned int size() { return count; }
// Iterator class
class Iterator {
public:
Iterator(const AbstractBinaryTree<T, Node>& _tree,
enum BtreeIteratorMode start = BtMinKey)
{
tree = (AbstractBinaryTree<T, Node> *) (&_tree);
StartAt(start);
}
// Start iterator over at the minimum, maximum or
// root node of the binary tree.
void StartAt(enum BtreeIteratorMode start)
{
ptr = tree->IteratorRoot();
if (start == BtMinKey)
ptr = ptr->Minimum();
else if (start == BtMaxKey)
ptr = ptr->Maximum();
}
virtual ~Iterator() { }
virtual void Previous()
{
if (ptr)
ptr = ptr->Predecessor();
}
virtual void Next()
{
if (ptr)
ptr = ptr->Successor();
}
virtual void Parent()
{
if (ptr)
ptr = ptr->parent;
}
virtual void find(const T& x)
{
ptr = tree->IteratorFind(x);
}
virtual operator int() const
{
return ptr != 0;
}
// Dereferencing operator returns the object of the
// node currently pointed to by the iterator.
virtual T operator*() const { return ptr->object; }
virtual T current() const { return ptr->object; }
virtual Node* current_node() const
{ return ptr; }
// Object returns a pointer to the object of the
// node currently pointed to (as opposed to returning
// a copy of the node, as the dereferencing operator
// above does).
virtual const T *Object() const
{
if (ptr)
return &ptr->object;
return (T*) 0;
}
virtual T *Object()
{
if (ptr)
return &ptr->object;
return 0;
}
virtual void operator++() { Next(); }
virtual void operator++(int) { Next(); }
virtual void operator--() { Previous(); }
virtual void operator--(int) { Previous(); }
protected:
Node *ptr;
AbstractBinaryTree<T, Node> *tree;
};
protected:
Node *root;
unsigned int count;
};
///////////////////////////////////////
template<class T>
class BinaryTree : public AbstractBinaryTree<T, BinaryNode<T> > {
public:
BinaryTree() { }
};
// --------------------------------------------------------
// AbstractBinaryNode implementation.
// --------------------------------------------------------
template<class T, class Node>
AbstractBinaryNode<T, Node>::AbstractBinaryNode(const T& _object,
Node *_parent,
Node *_left,
Node *_right)
{
object = _object;
parent = _parent;
left = _left;
right = _right;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::Clone(Node *_parent) const
{
Node *ret = new Node( *((Node *) this));
if (left)
ret->left = left->Clone(ret);
if (right)
ret->right = right->Clone(ret);
ret->parent = _parent;
return ret;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::LeftRotate(Node *root)
{
Node *ret = root;
Node *y = right;
right = y->left;
if (right)
right->parent = (Node *) this;
y->parent = parent;
if (parent) {
if (this == parent->left)
parent->left = y;
else
parent->right = y;
}
else
ret = y;
y->left = (Node *) this;
parent = y;
return ret;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::RightRotate(Node *root)
{
Node *ret = root;
Node *x = left;
left = x->right;
if (left)
left->parent = (Node *) this;
x->parent = parent;
if (parent) {
if (this == parent->left)
parent->left = x;
else
parent->right = x;
}
else
ret = x;
x->right = (Node *) this;
parent = x;
return ret;
}
template<class T, class Node>
int
AbstractBinaryNode<T, Node>::IsLeftChild() const
{
return (parent && parent->left == (Node *) this);
}
template<class T, class Node>
int
AbstractBinaryNode<T, Node>::IsRightChild() const
{
return (parent && parent->right == (Node *) this);
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::find(const T& x)
{
Node *sc = (Node *) this;
while (sc) {
if (x == sc->object)
return sc;
if (x < sc->object)
sc = sc->left;
else
sc = sc->right;
}
return 0;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::findNearest(const T& x)
{
Node *sc = (Node *) this;
Node *prev = 0;
while (sc) {
prev = sc;
if (x < sc->object)
sc = sc->left;
else
sc = sc->right;
}
return prev;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::add(const T& x)
{
Node *nearest = findNearest(x);
if (x < nearest->object)
nearest->left = new Node(x, nearest);
else
nearest->right = new Node(x, nearest);
return (Node *) this;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::unlink(Node *z)
{
Node *root = (Node *) this;
Node *x, *y;
if (! z)
return root;
if (! z->left || ! z->right)
y = z;
else
y = z->Successor();
if (y->left)
x = y->left;
else
x = y->right;
if (x)
x->parent = y->parent;
if (y->parent) {
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
}
else
root = x;
if (y != z)
z->object = y->object;
delete y;
return root;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::Minimum()
{
Node *sc = (Node *) this;
while (sc && sc->left)
sc = sc->left;
return sc;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::Maximum()
{
Node *sc = (Node *) this;
while (sc && sc->right)
sc = sc->right;
return sc;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::Predecessor()
{
if (left)
return left->Maximum();
Node *x = (Node *) this;
Node *y = parent;
while (y && x == y->left) {
x = y;
y = y->parent;
}
return y;
}
template<class T, class Node>
Node *
AbstractBinaryNode<T, Node>::Successor()
{
if (right)
return right->Minimum();
Node *x = (Node *) this;
Node *y = parent;
while (y && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
template<class T, class Node>
void
AbstractBinaryNode<T, Node>::RemoveSubtree()
{
if (left) {
left->RemoveSubtree();
delete left;
}
if (right) {
right->RemoveSubtree();
delete right;
}
}
template<class T, class Node>
T *
AbstractBinaryNode<T, Node>::Object()
{
return &object;
}
template<class T, class Node>
int
AbstractBinaryNode<T, Node>::CheckTreeProperties(const Node *_parent)
{
if (parent != _parent)
return 0;
if (left) {
if (object < left->object)
return 0;
if (! left->CheckTreeProperties((Node *) this))
return 0;
}
if (right) {
if (right->object < object)
return 0;
if (! right->CheckTreeProperties((Node *) this))
return 0;
}
return 1;
}
// --------------------------------------------------------
// AbstractBinaryTree class template implementation.
// --------------------------------------------------------
template<class T, class Node>
AbstractBinaryTree<T, Node>::AbstractBinaryTree()
{
root = 0;
count = 0;
}
template<class T, class Node>
AbstractBinaryTree<T, Node>::AbstractBinaryTree(const AbstractBinaryTree<T, Node>& x)
{
if (x.root)
root = x.root->Clone(0);
else
root = 0;
count = x.count;
}
template<class T, class Node>
AbstractBinaryTree<T, Node>&
AbstractBinaryTree<T, Node>::operator=(const AbstractBinaryTree<T, Node>& x)
{
if (root) {
root->RemoveSubtree();
delete root;
}
if (x.root)
root = x.root->Clone(0);
else
root = 0;
count = x.count;
return *this;
}
template<class T, class Node>
AbstractBinaryTree<T, Node>::~AbstractBinaryTree()
{
if (root) {
root->RemoveSubtree();
delete root;
}
}
template<class T, class Node>
void
AbstractBinaryTree<T, Node>::add(const T& x)
{
count++;
if (root == 0)
root = new Node(x);
else
root = root->add(x);
}
template<class T, class Node>
Node *
AbstractBinaryTree<T, Node>::IteratorRoot() const
{
return root;
}
template<class T, class Node>
Node *
AbstractBinaryTree<T, Node>::IteratorFind(const T& x) const
{
return (root) ? root->find(x) : 0;
}
template<class T, class Node>
void
AbstractBinaryTree<T, Node>::unlink(const T& _x)
{
count--;
if (! root)
return;
root = root->unlink(root->find(_x));
}
template<class T, class Node>
T *
AbstractBinaryTree<T, Node>::find(const T& q)
{
Node *p = (root) ? root->find(q) : 0;
return (p) ? &p->object : 0;
}
template<class T, class Node>
int
AbstractBinaryTree<T, Node>::CheckTreeProperties()
{
if (root->CheckTreeProperties(0) == 0)
return 0;
return 1;
}
/////////////////////////////
// balanced binary trees
// (using red & black trees)
/////////////////////////////
template<class T, class Node>
class AbstractRedBlackNode : public AbstractBinaryNode<T, Node> {
public:
enum RedBlack { Black, Red } clr;
// Constructors. Node always starts out red.
AbstractRedBlackNode() { clr = Red; }
AbstractRedBlackNode(const T& X,
Node *P = 0,
Node *L = 0,
Node *R = 0):
AbstractBinaryNode<T, Node>(X, P, L, R) { }
AbstractRedBlackNode(const T& X, enum RedBlack Clr, Node *P = 0,
Node *L = 0, Node *R = 0):
AbstractBinaryNode<T, Node>(X, P, L, R), clr(Clr) { }
virtual ~AbstractRedBlackNode() { }
// Tree manipulations used during insertion and deletion
virtual Node *RemoveFixup(Node *x, Node *p);
// Operations defined on binary trees. All run in O(lgN) time.
virtual Node *add(const T& AddMe);
virtual Node *unlink(Node *z);
// Returns 0 if the red-black invariant holds.
virtual int CheckTreeProperties(const Node *);
};
template<class T>
class RedBlackNode : public AbstractRedBlackNode<T, RedBlackNode<T> > {
public:
// Constructors. Node always starts out red.
RedBlackNode() { }
RedBlackNode(const T& X,
RedBlackNode<T> *P = 0,
RedBlackNode<T> *L = 0,
RedBlackNode<T> *R = 0):
AbstractRedBlackNode<T, RedBlackNode<T> >(X, P, L, R) { }
RedBlackNode(const T& X, enum RedBlack Clr, RedBlackNode<T> *P = 0,
RedBlackNode<T> *L = 0, RedBlackNode<T> *R = 0):
AbstractRedBlackNode<T, RedBlackNode<T> >(X, clr, P, L, R) { }
virtual ~RedBlackNode() { }
};
// --------------------------------------------------------
// AbstractRedBlackTree class template.
// --------------------------------------------------------
template<class T, class Node>
class AbstractRedBlackTree : public AbstractBinaryTree<T, Node> {
// The following is accessible only to classes that inherit
// from AbstractRedBlackTree, since they deal directly with RedBlackNodes.
protected:
virtual Node *FindNode(T q) const
{ return (root) ? (Node *) root->find(q) : 0; }
};
template <class T>
class VDKBtree : public AbstractRedBlackTree<T, RedBlackNode<T> > {
public:
VDKBtree() { }
};
template<class T, class Node>
Node *
AbstractRedBlackNode<T, Node>::add(const T& AddMe)
{
Node *root = (Node *) this;
Node *x = (Node *) this;
Node *y = 0;
while (x) {
y = x;
x = (AddMe < x->object) ? x->left : x->right;
}
Node *addme = new Node(AddMe, y);
if (! y)
root = addme;
else {
if (AddMe < y->object)
y->left = addme;
else
y->right = addme;
}
addme->clr = Red;
while (addme != root &&
addme->parent->parent &&
addme->parent->clr == Red) {
Node *y;
if (addme->parent == addme->parent->parent->left) {
y = addme->parent->parent->right;
if (y && y->clr == Red) {
// Case 1: x's uncle is red
addme->parent->clr = Black;
y->clr = Black;
addme->parent->parent->clr = Red;
addme = addme->parent->parent;
}
else {
if (addme == addme->parent->right) {
// Case 2: x is a right child
// Rotate to transform to case 3
addme = addme->parent;
root = addme->LeftRotate(root);
}
// Case 3: x is a left child
addme->parent->clr = Black;
if (addme->parent->parent) {
addme->parent->parent->clr = Red;
root = addme->parent->parent->RightRotate(root);
}
// The while loop will terminate
// on the next iteration.
}
}
else {
y = addme->parent->parent->left;
if (y && y->clr == Red) {
addme->parent->clr = Black;
y->clr = Black;
addme->parent->parent->clr = Red;
addme = addme->parent->parent;
}
else {
if (addme == addme->parent->left) {
addme = addme->parent;
root = addme->RightRotate(root);
}
addme->parent->clr = Black;
if (addme->parent->parent) {
addme->parent->parent->clr = Red;
root = addme->parent->parent->LeftRotate(root);
}
}
}
}
root->clr = Black;
return root;
}
template<class T, class Node>
Node *
AbstractRedBlackNode<T, Node>::RemoveFixup(Node *x, Node *p)
{
Node *root = (Node *) this;
while (x != root && (! x || x->clr == Black)) {
Node *w;
if (x == p->left) {
if (! p)
return root;
w = p->right;
if (! w)
return root;
if (w->clr == Red) {
w->clr = Black;
p->clr = Red;
root = p->LeftRotate(root);
w = p->right;
if (! p || ! w)
return root;
}
if ( ((! w->left) || w->left->clr == Black) &&
((! w->right) || w->right->clr == Black)) {
w->clr = Red;
x = p;
p = p->parent;
continue;
}
else if ((! w->right) || w->right->clr == Black) {
w->left->clr = Black;
w->clr = Red;
root = w->RightRotate(root);
w = p->right;
if (! p || ! w)
return root;
}
w->clr = p->clr;
if (p)
p->clr = Black;
w->right->clr = Black;
if (p)
root = p->LeftRotate(root);
x = root;
}
else {
if (! p)
return root;
w = p->left;
if (! p || ! w)
return root;
if (w->clr == Red) {
w->clr = Black;
p->clr = Red;
root = p->RightRotate(root);
w = p->left;
if (! p || ! w)
return root;
}
if ( ((! w->right) || w->right->clr == Black) &&
((! w->left) || w->left->clr == Black)) {
w->clr = Red;
x = p;
p = p->parent;
continue;
}
else if ((! w->left) || w->left->clr == Black) {
w->right->clr = Black;
w->clr = Red;
root = w->LeftRotate(root);
w = p->left;
if (! p || ! w)
return root;
}
w->clr = p->clr;
if (p)
p->clr = Black;
w->left->clr = Black;
if (p)
root = p->RightRotate(root);
x = root;
}
}
if (x)
x->clr = Black;
return root;
}
template<class T, class Node>
Node *
AbstractRedBlackNode<T, Node>::unlink(Node *z)
{
Node *root = (Node *) this;
Node *x, *y;
if (! z)
return root;
y = (! z->left || ! z->right) ? z : (Node *) z->Successor();
x = (y->left) ? y->left : y->right;
if (x)
x->parent = y->parent;
if (y->parent) {
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
}
else
root = x;
if (y != z)
z->object = y->object;
if (y->clr == Black) {
if (root)
root = root->RemoveFixup(x, y->parent);
}
delete y;
return root;
}
template<class T, class Node>
int
AbstractRedBlackNode<T, Node>::CheckTreeProperties(const Node *_parent)
{
static int BlackHeight;
if (_parent == 0)
BlackHeight = -1;
// Check binary tree properties.
if (parent != _parent)
return 0;
if (left) {
if (object < left->object)
return 0;
}
if (right) {
if (right->object < object)
return 0;
}
// Now check red-black tree properties.
// If a node is red, then both its children are black
// (NULL nodes are black).
if (clr == Red) {
if ((left && left->clr != Black) ||
(right && right->clr != Black))
return 0;
}
// The black-heights of all leaf nodes are equal.
int bh = 0;
if ((! left) && (! right)) {
// Compute black-height of node
for (Node *sc = (Node *) this; sc; sc = sc->parent)
if (sc->clr == Black)
bh += 1;
if (BlackHeight == -1) {
BlackHeight = bh;
}
else {
if (bh != BlackHeight)
return 0;
}
}
if (left && (! left->CheckTreeProperties((Node *) this)))
return 0;
if (right && (! right->CheckTreeProperties((Node *) this)))
return 0;
return 1;
}
#endif