Roma&Weiss'sCode  1.0
Classes | Macros | Typedefs | Functions | Variables
treeGL.C File Reference

A tree exhibitor based on OpenGL. More...

#include <GL/gl.h>
#include <GL/glu.h>
#include <GL/glut.h>
#include <ctime>
#include "TreeNode.h"
#include "AATree.h"
#include "AVLTree.h"
#include "RedBlack.h"
#include "Splay.h"
#include "utlIterate.h"
#include "Ordered.h"
#include "Random.h"
Include dependency graph for treeGL.C:

Go to the source code of this file.

Classes

struct  _worldPoint
 a 2D point in world coordinates. More...
 
struct  _screenPoint
 a 2D point in screen coordinates. More...
 

Macros

#define BACKGROUND   1.0, 250/255.0, 205/255.0
 background color.
 
#define BLACK   0.0, 0.0, 0.0
 
#define BLUE   0.0, 0.0, 1.0
 
#define RED   1.0, 0.0, 0.0
 
#define GREEN   0.0, 1.0, 0.0
 
#define GRAY   0.5, 0.5, 0.5
 
#define PURPLE   0.7, 0.0, 0.7
 
#define ORANGE   1.0, 0.5, 0.0
 
#define DARKGRAY   0.3, 0.3, 0.3
 
#define LIGHTGRAY   0.7, 0.7, 0.7
 
#define PI   3.1415927
 the value of Pi.
 
#define nseg   18
 number of segments to draw a circle.
 
#define toDegree(ang)   (PI*ang/180.0)
 convert from degrees to radians.
 
#define HDSP(ht)   (hdsp*pow(2.0,ht-2))
 horizontal displacement for a given height.
 
#define up(y)   (ysize-y)
 make y point upward.
 
#define pickRadius(r)   max(3.0*r,radius)
 area for picking a node.
 
#define radius   1.0
 radius of a circle in world coordinates.
 
#define space   1.0
 space between nodes and labels.
 
#define RB_MIN_NODE   INT_MIN
 minimum value for a red-black tree node.
 

Typedefs

typedef double WorldType
 a floating point number.
 
typedef struct _worldPoint WorldPoint
 a 2D point in world coordinates.
 
typedef struct _screenPoint ScreenPoint
 a 2D point in screen coordinates.
 
typedef SearchTree< TreeNode >::BinaryNode BinaryNode
 a BinaryNode definition.
 

Functions

void redraw ()
 cleans the screen and redraws the picture.
 
void text (const WorldPoint *pt, const char *s)
 draws a text. More...
 
void pldraw (int n, const WorldPoint *pts)
 draws a polyline, starting at pts[0] and ending at pts[n-1]. More...
 
void pnt (const WorldPoint *pt)
 draws a point at pt. More...
 
void circ (const WorldPoint &center, WorldType r)
 draws a circle. More...
 
void reshape (int w, int h)
 handles callbacks generated by moving or resizing a window. More...
 
void printHelp (void)
 prints help messages.
 
void printData (void)
 prints some statistics.
 
void insertData (void)
 inserts a new node.
 
void deleteData (void)
 deletes a node.
 
void redb (void)
 changes an AVLTree into a RedBlackTree.
 
WorldType getXmin (const BinaryNode *rnode, const WorldPoint &center, int ht)
 returns the x coordinate of the leftmost node. More...
 
WorldType getXmax (const BinaryNode *rnode, const WorldPoint &center, int ht)
 returns the x coordinate of the rightmost node. More...
 
const BinaryNodelocateNode (const BinaryNode *rnode, const WorldPoint &center, int ht, const WorldPoint &pos)
 returns a node close to a given point. More...
 
void drawTree (const BinaryNode *rnode, const WorldPoint &center, int ht)
 draws a tree recursively. More...
 
ScreenPoint toScreenCoordinates (const WorldPoint &wp)
 maps a world point to screen coordinates. More...
 
WorldPoint toWorldCoordinates (int x, int y)
 maps a screen point to world coordinates. More...
 
void info (int x, int y)
 prints information about a node close to point (x,y).
 
void deleteNode (int x, int y)
 deletes a node close to point (x,y).
 
void insertRandomNodes (int nd, int range)
 insert random nodes into the tree. More...
 
void createTree (int type, int nNodes, const int *data)
 creates an initial tree. More...
 
void printTree ()
 prints the tree on the screen.
 
void displayTree (void)
 displays a tree.
 
void init (void)
 initializes graphical global variables.
 
int getType (const char *tname)
 returns the type of a given tree name. More...
 
int * readFile (const char *fname, int &type, int &nNodes)
 read the tree type and nodes from a file. More...
 
int readType (int &type)
 read the type and number of nodes of the tree from stdin. More...
 
void keyboardHandler (unsigned char key, int x, int y)
 handles callbacks generated by keyboard events. More...
 
void mouseHandler (int button, int state, int x, int y)
 handles callbacks generated by mouse events. More...
 
int main (int argc, char *argv[])
 main program. More...
 

Variables

static int VIEWP [] = {0, 1024, 0, 512}
 viewport dimensions.
 
static int xsize = VIEWP[1]
 initial window length in pixels.
 
static int ysize = VIEWP[3]
 initial window height in pixels.
 
static int xpos = VIEWP[0]
 initial viewport position in pixels.
 
static int ypos = VIEWP[2]
 initial viewport position in pixels.
 
static WorldType hdsp = 0.0
 horizontal displacement.
 
static WorldType vdsp = 0.0
 vertical displacement.
 
static SearchTree< TreeNode > * Stree
 a pointer to the global searching tree.
 
static char sname [24]
 holds the type of the searching tree.
 
static WorldPoint p1
 lower left corner of the current window.
 
static WorldPoint p2
 upper right corner of the current window.
 
static WorldPoint ct
 root position.
 
static WorldPoint rd
 radius for picking.
 
static WorldType aspect = 1.0
 window-viewport aspect ratio.
 
static char input_buffer [80]
 buffer for reading.
 
static const BinaryNodeNullNode
 null node representation.
 
static void * fontNormal = GLUT_BITMAP_HELVETICA_12
 font for rendering normal text.
 
static void * fontSmall = GLUT_BITMAP_TIMES_ROMAN_10
 font for rendering small text.
 
static void * font = fontNormal
 current font.
 

Detailed Description

A tree exhibitor based on OpenGL.

Non-commercial use only.

Author
Paulo Roma Cavalcanti
Since
24/11/2000.

Definition in file treeGL.C.

Function Documentation

◆ circ()

void circ ( const WorldPoint center,
WorldType  r 
)

draws a circle.

Parameters
centerof circle.
rradius of circle.

Definition at line 205 of file treeGL.C.

References aspect, font, fontNormal, fontSmall, nseg, PI, pnt(), _worldPoint::x, and _worldPoint::y.

◆ createTree()

void createTree ( int  type,
int  nNodes,
const int *  data 
)

creates an initial tree.

If nNodes is negative, the nodes are read from stdin. If data is NULL, the nodes are created randomly.

Parameters
typetree type.
nNodesnumber of nodes.
dataarray of nodes.

Definition at line 575 of file treeGL.C.

References insertRandomNodes(), NullNode, RB_MIN_NODE, TreeNode::setData(), sname, and Stree.

Referenced by keyboardHandler(), and main().

◆ drawTree()

void drawTree ( const BinaryNode rnode,
const WorldPoint center,
int  ht 
)

draws a tree recursively.

Parameters
rnoderoot node.
centerrnode position.
htrnode height.

Definition at line 413 of file treeGL.C.

References BinNode< Etype, Cmp >::GetBalance(), and BinNode< Etype, Cmp >::GetElement().

Referenced by displayTree().

◆ getType()

int getType ( const char *  tname)

returns the type of a given tree name.

  • AVL: 0
  • AA: 1
  • RB: 2
  • SPLAY: 3
  • ORDERED: 4
  • SEARCH: 5
  • INVALID: -1
Parameters
tnametree type name.
Returns
tree id.

Definition at line 715 of file treeGL.C.

Referenced by main(), readFile(), and readType().

◆ getXmax()

WorldType getXmax ( const BinaryNode rnode,
const WorldPoint center,
int  ht 
)

returns the x coordinate of the rightmost node.

Parameters
rnodesubtree root.
centercalculated rnode position.
htrnode height.

Definition at line 356 of file treeGL.C.

References BinNode< Etype, Cmp >::GetRight(), HDSP, NullNode, vdsp, and _worldPoint::x.

Referenced by displayTree().

◆ getXmin()

WorldType getXmin ( const BinaryNode rnode,
const WorldPoint center,
int  ht 
)

returns the x coordinate of the leftmost node.

Parameters
rnodesubtree root.
centercalculated rnode position.
htrnode height.

Definition at line 336 of file treeGL.C.

References BinNode< Etype, Cmp >::GetLeft(), HDSP, NullNode, vdsp, and _worldPoint::x.

Referenced by displayTree().

◆ insertRandomNodes()

void insertRandomNodes ( int  nd,
int  range 
)

insert random nodes into the tree.

Parameters
ndnumber of nodes.
rangeof node values: [0..range].

Definition at line 555 of file treeGL.C.

References rd, and Stree.

Referenced by createTree(), and keyboardHandler().

◆ keyboardHandler()

void keyboardHandler ( unsigned char  key,
int  x,
int  y 
)

handles callbacks generated by keyboard events.

Parameters
keypressed.
xmouse X coordinate.
ymouse Y coordinate.

Definition at line 810 of file treeGL.C.

References createTree(), deleteData(), insertData(), insertRandomNodes(), printData(), printHelp(), readType(), redb(), redraw(), and Stree.

Referenced by main().

◆ locateNode()

const BinaryNode* locateNode ( const BinaryNode rnode,
const WorldPoint center,
int  ht,
const WorldPoint pos 
)

returns a node close to a given point.

Parameters
rnodea node to start the search.
centerposition of rnode.
htheight of rnode.
posgiven point.

Definition at line 377 of file treeGL.C.

References BinNode< Etype, Cmp >::GetLeft(), BinNode< Etype, Cmp >::GetRight(), HDSP, NullNode, pickRadius, rd, vdsp, _worldPoint::x, and _worldPoint::y.

Referenced by deleteNode(), and info().

◆ main()

int main ( int  argc,
char *  argv[] 
)

main program.

Starts the interaction loop.

Parameters
argcnumber of arguments.
argvcommand line arguments.
  • argv[0]: name of the program
  • argv[1] and argv[2]
    • tree type and number of nodes
  • argv[1]:
    • name of a two line file containing: type, number of nodes, and node data
      • avl 11
      • 5 20 2 1 7 30 25 4 9 10 11
    • or number of nodes (assume avl, in this case).

Definition at line 881 of file treeGL.C.

References createTree(), getType(), init(), keyboardHandler(), mouseHandler(), readFile(), readType(), redraw(), and reshape().

◆ mouseHandler()

void mouseHandler ( int  button,
int  state,
int  x,
int  y 
)

handles callbacks generated by mouse events.

Parameters
buttonkey pressed
  • GLUT_LEFT_BUTTON,
  • GLUT_MIDDLE_BUTTON or
  • GLUT_RIGHT_BUTTON.
state
  • GLUT_DOWN or
  • GLUT_UP.
xmouse X coordinate.
ymouse Y coordinate.

Definition at line 849 of file treeGL.C.

References deleteNode(), info(), and printTree().

Referenced by main().

◆ pldraw()

void pldraw ( int  n,
const WorldPoint pts 
)

draws a polyline, starting at pts[0] and ending at pts[n-1].

Parameters
nnumber of points.
ptsarray of point coordinates.

Definition at line 173 of file treeGL.C.

◆ pnt()

void pnt ( const WorldPoint pt)

draws a point at pt.

Parameters
ptpoint coordinates.

Definition at line 191 of file treeGL.C.

References _worldPoint::x, and _worldPoint::y.

Referenced by circ().

◆ readFile()

int* readFile ( const char *  fname,
int &  type,
int &  nNodes 
)

read the tree type and nodes from a file.

Terminates the program if the file could not be read.

Parameters
fnamefile name.
typetree type read from the file.
nNodesnumber of nodes read from the file.
Returns
array with the nodes.

Definition at line 743 of file treeGL.C.

References getType().

Referenced by main().

◆ readType()

int readType ( int &  type)

read the type and number of nodes of the tree from stdin.

Parameters
typetree type read.
Returns
number of nodes.

Definition at line 783 of file treeGL.C.

References getType(), and input_buffer.

Referenced by keyboardHandler(), and main().

◆ reshape()

void reshape ( int  w,
int  h 
)

handles callbacks generated by moving or resizing a window.

Parameters
wviewport width.
hviewport height.

Definition at line 243 of file treeGL.C.

References xsize, and ysize.

Referenced by main().

◆ text()

void text ( const WorldPoint pt,
const char *  s 
)

draws a text.

Parameters
ptstarting position.
sstring.

Definition at line 155 of file treeGL.C.

◆ toScreenCoordinates()

ScreenPoint toScreenCoordinates ( const WorldPoint wp)

maps a world point to screen coordinates.

Parameters
wpworld point.
Returns
screen coordinates.

Definition at line 464 of file treeGL.C.

References p1, p2, _worldPoint::x, xpos, xsize, _worldPoint::y, ypos, and ysize.

Referenced by toWorldCoordinates().

◆ toWorldCoordinates()

WorldPoint toWorldCoordinates ( int  x,
int  y 
)

maps a screen point to world coordinates.

Parameters
xviewport X coordinate.
yviewport Y coordinate.
Returns
world coordinates.

Definition at line 485 of file treeGL.C.

References aspect, p1, p2, rd, toScreenCoordinates(), up, _worldPoint::x, _screenPoint::x, xpos, xsize, _worldPoint::y, _screenPoint::y, ypos, and ysize.

Referenced by deleteNode(), displayTree(), and info().