summaryrefslogtreecommitdiffstats
path: root/src/2geom/orphan-code/redblack-toy.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/2geom/orphan-code/redblack-toy.cpp')
-rw-r--r--src/2geom/orphan-code/redblack-toy.cpp327
1 files changed, 327 insertions, 0 deletions
diff --git a/src/2geom/orphan-code/redblack-toy.cpp b/src/2geom/orphan-code/redblack-toy.cpp
new file mode 100644
index 0000000..01ffa7d
--- /dev/null
+++ b/src/2geom/orphan-code/redblack-toy.cpp
@@ -0,0 +1,327 @@
+/*
+ * Copyright 2009 Evangelos Katsikaros <vkatsikaros at yahoo dot gr>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ */
+
+/*
+ initial toy for redblack trees
+*/
+
+#include <2geom/toys/path-cairo.h>
+#include <2geom/toys/toy-framework-2.h>
+
+#include <2geom/orphan-code/redblacktree.h>
+#include <2geom/orphan-code/redblacktree.cpp>
+
+#include <time.h>
+using std::vector;
+using namespace Geom;
+using namespace std;
+
+
+class RedBlackToy: public Toy
+{
+ PointSetHandle handle_set;
+ Geom::Point starting_point; // during click and drag: start point of click
+ Geom::Point ending_point; // during click and drag: end point of click (release)
+ Geom::Point highlight_point; // not used
+
+ Geom::RedBlackTree rbtree_x;
+ RedBlack* search_result;
+ RedBlack temp_deleted_node;
+
+ // colors we are going to use for different purposes
+ colour color_rect, color_rect_guide; // black(a=0.6), black
+ colour color_select_area, color_select_area_guide; // red(a=0.6), red
+
+ int alter_existing_rect;
+ int add_new_rect;
+
+ Rect rect_chosen; // the rectangle of the search area
+ Rect dummy_draw; // the "helper" rectangle that is shown during the click and drag (before the mouse release)
+ int mode; // insert/alter, search, delete modes
+
+ // printing of the tree
+ int help_counter; // the "x" of the label of each node
+ static const int label_size = 15 ; // size the label of each node
+
+ // used for the keys that switch between modes
+ enum menu_item_t
+ {
+ INSERT = 0,
+ DELETE,
+ SEARCH,
+ TOTAL_ITEMS // this one must be the last item
+ };
+ static const char* menu_items[TOTAL_ITEMS];
+ static const char keys[TOTAL_ITEMS];
+
+
+
+ void draw(cairo_t *cr, std::ostringstream *notify, int width, int height, bool save, std::ostringstream *timer_stream) {
+ cairo_set_line_width( cr, 1 );
+
+ // draw the rects that we have in the handles
+ for( unsigned i=0; i<handle_set.pts.size(); i=i+2 ){
+ Rect r1( handle_set.pts[i], handle_set.pts[i+1] );
+ cairo_rectangle( cr, r1 );
+ }
+ cairo_set_source_rgba( cr, color_rect);
+ cairo_stroke( cr );
+
+ // draw a rect if we click & drag (so that we know what we are going to create)
+ if(add_new_rect){
+ dummy_draw = Rect( starting_point, ending_point );
+ cairo_rectangle( cr, dummy_draw );
+ if( mode == 0){
+ cairo_set_source_rgba( cr, color_rect_guide);
+ }
+ else if( mode == 1){
+ cairo_set_source_rgba( cr, color_select_area_guide );
+ }
+ cairo_stroke( cr );
+ }
+
+ // draw a rect for the search area
+ cairo_rectangle( cr, rect_chosen );
+ cairo_set_source_rgba( cr, color_select_area);
+ cairo_stroke( cr );
+
+ Toy::draw( cr, notify, width, height, save,timer_stream );
+ draw_tree_in_toy( cr ,rbtree_x.root, 0);
+ help_counter=0;
+ }
+
+ void mouse_moved(GdkEventMotion* e){
+ if( !( alter_existing_rect && mode == 1 ) ){
+ Toy::mouse_moved(e);
+ }
+
+ if(add_new_rect){
+ ending_point = Point(e->x, e->y);
+ }
+ }
+
+ void mouse_pressed(GdkEventButton* e) {
+ Toy::mouse_pressed(e);
+ if(e->button == 1){ // left mouse button
+ if( mode == 0 ){ // mode: insert / alter
+ if(!selected) {
+ starting_point = Point(e->x, e->y);
+ ending_point = starting_point;
+ add_new_rect = 1;
+ }
+ else
+ {
+ // TODO find the selected rect
+ // ideas : from Handle *selected ???
+ //std::cout <<find_selected_rect(selected) << std::endl ;
+ alter_existing_rect = 1;
+ }
+ }
+ else if( mode == 1 ){ // mode: search
+ if(!selected) {
+ starting_point = Point(e->x, e->y);
+ ending_point = starting_point;
+ add_new_rect = 1;
+ }
+ else{
+ alter_existing_rect = 1;
+ }
+ }
+ else if( mode == 2) { // mode: delete
+ }
+ }
+ else if(e->button == 2){ //middle button
+ }
+ else if(e->button == 3){ //right button
+ }
+ }
+
+ virtual void mouse_released(GdkEventButton* e) {
+ Toy::mouse_released(e);
+ if( e->button == 1 ) { //left mouse button
+ if( mode == 0) { // mode: insert / alter
+ if( add_new_rect ){
+ ending_point = Point(e->x, e->y);
+ handle_set.push_back(starting_point);
+ handle_set.push_back(ending_point);
+ insert_in_tree_the_last_rect();
+ add_new_rect = 0;
+ }
+ else if( alter_existing_rect ){
+ //TODO update rect (and tree)
+ // delete selected rect
+ // insert altered
+ alter_existing_rect = 0;
+ }
+ }
+ else if( mode == 1 ){ // mode: search
+ if( add_new_rect ){
+ ending_point = Point(e->x, e->y);
+ rect_chosen = Rect(starting_point, ending_point);
+
+ // search in the X axis
+ Coord a = rect_chosen[0].min();
+ Coord b = rect_chosen[0].max();
+ search_result = rbtree_x.search( Interval( a, b ) );
+ if(search_result){
+ std::cout << "Found: (" << search_result->data << ": " << search_result->key()
+ << ", " << search_result->high() << " : " << search_result->subtree_max << ") "
+ << std::endl;
+ }
+ else{
+ std::cout << "Nothing found..."<< std::endl;
+ }
+ add_new_rect = 0;
+ }
+ else if(alter_existing_rect){
+ // do nothing
+ alter_existing_rect = 0;
+ }
+ }
+ else if( mode == 2) { // mode: delete
+
+ }
+ }
+ else if(e->button == 2){ //middle button
+ }
+ else if(e->button == 3){ //right button
+
+ }
+ }
+
+
+ void key_hit(GdkEventKey *e)
+ {
+ char choice = std::toupper(e->keyval);
+ switch ( choice )
+ {
+ case 'A':
+ mode = 0;
+ break;
+ case 'B':
+ mode = 1;
+ break;
+ case 'C':
+ mode = 2;
+ break;
+ }
+ //redraw();
+ }
+
+ void insert_in_tree_the_last_rect(){
+ unsigned i = handle_set.pts.size() - 2;
+ Rect r1(handle_set.pts[i], handle_set.pts[i+1]);
+ // insert in X axis tree
+ rbtree_x.insert(r1, i, 0);
+ rbtree_x.print_tree();
+ };
+
+ void draw_tree_in_toy(cairo_t* cr, Geom::RedBlack* n, int depth = 0) {
+ if(n){
+ if(n->left){
+ draw_tree_in_toy(cr, n->left, depth+1);
+ }
+ help_counter += 1;
+ //drawthisnode(cr, x*10, depth*10);
+ if(n->isRed){
+ cairo_set_source_rgba (cr, color_select_area_guide);
+ }
+ else{
+ cairo_set_source_rgba (cr, color_rect_guide);
+ }
+
+ cairo_stroke(cr);
+
+ Geom::Point text_point = Point( help_counter*15, depth*15 );
+ char label[4];
+ sprintf( label,"%d",n->data ); // instead of std::itoa(depth, label, 10);
+
+ draw_text(cr, text_point, label);
+ ////////////////////////////////////////////////////////////////
+ if(n->right){
+ draw_tree_in_toy(cr, n->right, depth+1);
+ }
+ }
+ };
+
+/*
+ int find_selected_rect(PointHandle * selected){
+
+ for( unsigned i=0; i<handle_set.pts.size(); i=i+2 ){
+ if( handle_set.pts[i] == selected || handle_set.pts[i+1] == selected ){
+ return i;
+ }
+ }
+
+ return -1;
+ };
+*/
+
+
+public:
+ RedBlackToy(): color_rect(0, 0, 0, 0.6), color_rect_guide(0, 0, 0, 1),
+ color_select_area(1, 0, 0, 0.6 ), color_select_area_guide(1, 0, 0, 1 ),
+ alter_existing_rect(0), add_new_rect(0), mode(0), help_counter(0)
+ {
+ if(handles.empty()) {
+ handles.push_back(&handle_set);
+ }
+ Rect rect_chosen();
+ Rect dummy_draw();
+ }
+
+
+};
+
+
+
+int main(int argc, char **argv) {
+ std::cout << "---------------------------------------------------------"<< std::endl;
+ std::cout << "Let's play with the Red Black Tree! ONLY Insert works now!!!"<< std::endl;
+ std::cout << " Key A: insert/alter mode "<< std::endl;
+ std::cout << " * Left click and drag on white area: create a rectangle"<< std::endl;
+ std::cout << " *NOT READY: Left click and drag on handler: alter a rectangle"<< std::endl;
+ std::cout << " Key B: search mode "<< std::endl;
+ std::cout << " * Left click and drag on white area: \"search\" for nodes that intersect red area"<< std::endl;
+ std::cout << " NOT READY: Key C: delete mode "<< std::endl;
+ std::cout << " * Left click on handler: delete for a rectangle"<< std::endl;
+ std::cout << "---------------------------------------------------------"<< std::endl;
+ init(argc, argv, new RedBlackToy);
+ return 0;
+}
+
+const char* RedBlackToy::menu_items[] =
+{
+ "Insert / Alter Rectangle",
+ "Search Rectangle",
+ "Delete Reactangle"
+};
+
+const char RedBlackToy::keys[] =
+{
+ 'A', 'B', 'C'
+};
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 15:56:49 +0000