1 /*
2 * Copyright 2009 Evangelos Katsikaros <vkatsikaros at yahoo dot gr>
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it either under the terms of the GNU Lesser General Public
6 * License version 2.1 as published by the Free Software Foundation
7 * (the "LGPL") or, at your option, under the terms of the Mozilla
8 * Public License Version 1.1 (the "MPL"). If you do not alter this
9 * notice, a recipient may use your version of this file under either
10 * the MPL or the LGPL.
11 *
12 * You should have received a copy of the LGPL along with this library
13 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15 * You should have received a copy of the MPL along with this library
16 * in the file COPYING-MPL-1.1
17 *
18 * The contents of this file are subject to the Mozilla Public License
19 * Version 1.1 (the "License"); you may not use this file except in
20 * compliance with the License. You may obtain a copy of the License at
21 * http://www.mozilla.org/MPL/
22 *
23 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
24 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
25 * the specific language governing rights and limitations.
26 */
27
28 /*
29 initial toy for redblack trees
30 */
31
32 #include <2geom/toys/path-cairo.h>
33 #include <2geom/toys/toy-framework-2.h>
34
35 #include <2geom/orphan-code/redblacktree.h>
36 #include <2geom/orphan-code/redblacktree.cpp>
37
38 #include <time.h>
39 using std::vector;
40 using namespace Geom;
41 using namespace std;
42
43
44 class RedBlackToy: public Toy
45 {
46 PointSetHandle handle_set;
47 Geom::Point starting_point; // during click and drag: start point of click
48 Geom::Point ending_point; // during click and drag: end point of click (release)
49 Geom::Point highlight_point; // not used
50
51 Geom::RedBlackTree rbtree_x;
52 RedBlack* search_result;
53 RedBlack temp_deleted_node;
54
55 // colors we are going to use for different purposes
56 colour color_rect, color_rect_guide; // black(a=0.6), black
57 colour color_select_area, color_select_area_guide; // red(a=0.6), red
58
59 int alter_existing_rect;
60 int add_new_rect;
61
62 Rect rect_chosen; // the rectangle of the search area
63 Rect dummy_draw; // the "helper" rectangle that is shown during the click and drag (before the mouse release)
64 int mode; // insert/alter, search, delete modes
65
66 // printing of the tree
67 int help_counter; // the "x" of the label of each node
68 static const int label_size = 15 ; // size the label of each node
69
70 // used for the keys that switch between modes
71 enum menu_item_t
72 {
73 INSERT = 0,
74 DELETE,
75 SEARCH,
76 TOTAL_ITEMS // this one must be the last item
77 };
78 static const char* menu_items[TOTAL_ITEMS];
79 static const char keys[TOTAL_ITEMS];
80
81
82
draw(cairo_t * cr,std::ostringstream * notify,int width,int height,bool save,std::ostringstream * timer_stream)83 void draw(cairo_t *cr, std::ostringstream *notify, int width, int height, bool save, std::ostringstream *timer_stream) {
84 cairo_set_line_width( cr, 1 );
85
86 // draw the rects that we have in the handles
87 for( unsigned i=0; i<handle_set.pts.size(); i=i+2 ){
88 Rect r1( handle_set.pts[i], handle_set.pts[i+1] );
89 cairo_rectangle( cr, r1 );
90 }
91 cairo_set_source_rgba( cr, color_rect);
92 cairo_stroke( cr );
93
94 // draw a rect if we click & drag (so that we know what we are going to create)
95 if(add_new_rect){
96 dummy_draw = Rect( starting_point, ending_point );
97 cairo_rectangle( cr, dummy_draw );
98 if( mode == 0){
99 cairo_set_source_rgba( cr, color_rect_guide);
100 }
101 else if( mode == 1){
102 cairo_set_source_rgba( cr, color_select_area_guide );
103 }
104 cairo_stroke( cr );
105 }
106
107 // draw a rect for the search area
108 cairo_rectangle( cr, rect_chosen );
109 cairo_set_source_rgba( cr, color_select_area);
110 cairo_stroke( cr );
111
112 Toy::draw( cr, notify, width, height, save,timer_stream );
113 draw_tree_in_toy( cr ,rbtree_x.root, 0);
114 help_counter=0;
115 }
116
mouse_moved(GdkEventMotion * e)117 void mouse_moved(GdkEventMotion* e){
118 if( !( alter_existing_rect && mode == 1 ) ){
119 Toy::mouse_moved(e);
120 }
121
122 if(add_new_rect){
123 ending_point = Point(e->x, e->y);
124 }
125 }
126
mouse_pressed(GdkEventButton * e)127 void mouse_pressed(GdkEventButton* e) {
128 Toy::mouse_pressed(e);
129 if(e->button == 1){ // left mouse button
130 if( mode == 0 ){ // mode: insert / alter
131 if(!selected) {
132 starting_point = Point(e->x, e->y);
133 ending_point = starting_point;
134 add_new_rect = 1;
135 }
136 else
137 {
138 // TODO find the selected rect
139 // ideas : from Handle *selected ???
140 //std::cout <<find_selected_rect(selected) << std::endl ;
141 alter_existing_rect = 1;
142 }
143 }
144 else if( mode == 1 ){ // mode: search
145 if(!selected) {
146 starting_point = Point(e->x, e->y);
147 ending_point = starting_point;
148 add_new_rect = 1;
149 }
150 else{
151 alter_existing_rect = 1;
152 }
153 }
154 else if( mode == 2) { // mode: delete
155 }
156 }
157 else if(e->button == 2){ //middle button
158 }
159 else if(e->button == 3){ //right button
160 }
161 }
162
mouse_released(GdkEventButton * e)163 virtual void mouse_released(GdkEventButton* e) {
164 Toy::mouse_released(e);
165 if( e->button == 1 ) { //left mouse button
166 if( mode == 0) { // mode: insert / alter
167 if( add_new_rect ){
168 ending_point = Point(e->x, e->y);
169 handle_set.push_back(starting_point);
170 handle_set.push_back(ending_point);
171 insert_in_tree_the_last_rect();
172 add_new_rect = 0;
173 }
174 else if( alter_existing_rect ){
175 //TODO update rect (and tree)
176 // delete selected rect
177 // insert altered
178 alter_existing_rect = 0;
179 }
180 }
181 else if( mode == 1 ){ // mode: search
182 if( add_new_rect ){
183 ending_point = Point(e->x, e->y);
184 rect_chosen = Rect(starting_point, ending_point);
185
186 // search in the X axis
187 Coord a = rect_chosen[0].min();
188 Coord b = rect_chosen[0].max();
189 search_result = rbtree_x.search( Interval( a, b ) );
190 if(search_result){
191 std::cout << "Found: (" << search_result->data << ": " << search_result->key()
192 << ", " << search_result->high() << " : " << search_result->subtree_max << ") "
193 << std::endl;
194 }
195 else{
196 std::cout << "Nothing found..."<< std::endl;
197 }
198 add_new_rect = 0;
199 }
200 else if(alter_existing_rect){
201 // do nothing
202 alter_existing_rect = 0;
203 }
204 }
205 else if( mode == 2) { // mode: delete
206
207 }
208 }
209 else if(e->button == 2){ //middle button
210 }
211 else if(e->button == 3){ //right button
212
213 }
214 }
215
216
key_hit(GdkEventKey * e)217 void key_hit(GdkEventKey *e)
218 {
219 char choice = std::toupper(e->keyval);
220 switch ( choice )
221 {
222 case 'A':
223 mode = 0;
224 break;
225 case 'B':
226 mode = 1;
227 break;
228 case 'C':
229 mode = 2;
230 break;
231 }
232 //redraw();
233 }
234
insert_in_tree_the_last_rect()235 void insert_in_tree_the_last_rect(){
236 unsigned i = handle_set.pts.size() - 2;
237 Rect r1(handle_set.pts[i], handle_set.pts[i+1]);
238 // insert in X axis tree
239 rbtree_x.insert(r1, i, 0);
240 rbtree_x.print_tree();
241 };
242
draw_tree_in_toy(cairo_t * cr,Geom::RedBlack * n,int depth=0)243 void draw_tree_in_toy(cairo_t* cr, Geom::RedBlack* n, int depth = 0) {
244 if(n){
245 if(n->left){
246 draw_tree_in_toy(cr, n->left, depth+1);
247 }
248 help_counter += 1;
249 //drawthisnode(cr, x*10, depth*10);
250 if(n->isRed){
251 cairo_set_source_rgba (cr, color_select_area_guide);
252 }
253 else{
254 cairo_set_source_rgba (cr, color_rect_guide);
255 }
256
257 cairo_stroke(cr);
258
259 Geom::Point text_point = Point( help_counter*15, depth*15 );
260 char label[4];
261 sprintf( label,"%d",n->data ); // instead of std::itoa(depth, label, 10);
262
263 draw_text(cr, text_point, label);
264 ////////////////////////////////////////////////////////////////
265 if(n->right){
266 draw_tree_in_toy(cr, n->right, depth+1);
267 }
268 }
269 };
270
271 /*
272 int find_selected_rect(PointHandle * selected){
273
274 for( unsigned i=0; i<handle_set.pts.size(); i=i+2 ){
275 if( handle_set.pts[i] == selected || handle_set.pts[i+1] == selected ){
276 return i;
277 }
278 }
279
280 return -1;
281 };
282 */
283
284
285 public:
RedBlackToy()286 RedBlackToy(): color_rect(0, 0, 0, 0.6), color_rect_guide(0, 0, 0, 1),
287 color_select_area(1, 0, 0, 0.6 ), color_select_area_guide(1, 0, 0, 1 ),
288 alter_existing_rect(0), add_new_rect(0), mode(0), help_counter(0)
289 {
290 if(handles.empty()) {
291 handles.push_back(&handle_set);
292 }
293 Rect rect_chosen();
294 Rect dummy_draw();
295 }
296
297
298 };
299
300
301
main(int argc,char ** argv)302 int main(int argc, char **argv) {
303 std::cout << "---------------------------------------------------------"<< std::endl;
304 std::cout << "Let's play with the Red Black Tree! ONLY Insert works now!!!"<< std::endl;
305 std::cout << " Key A: insert/alter mode "<< std::endl;
306 std::cout << " * Left click and drag on white area: create a rectangle"<< std::endl;
307 std::cout << " *NOT READY: Left click and drag on handler: alter a rectangle"<< std::endl;
308 std::cout << " Key B: search mode "<< std::endl;
309 std::cout << " * Left click and drag on white area: \"search\" for nodes that intersect red area"<< std::endl;
310 std::cout << " NOT READY: Key C: delete mode "<< std::endl;
311 std::cout << " * Left click on handler: delete for a rectangle"<< std::endl;
312 std::cout << "---------------------------------------------------------"<< std::endl;
313 init(argc, argv, new RedBlackToy);
314 return 0;
315 }
316
317 const char* RedBlackToy::menu_items[] =
318 {
319 "Insert / Alter Rectangle",
320 "Search Rectangle",
321 "Delete Reactangle"
322 };
323
324 const char RedBlackToy::keys[] =
325 {
326 'A', 'B', 'C'
327 };
328