Merge lp:~sgringwe/granite/fastview into lp:~elementary-pantheon/granite/granite

[Scott Ringwelski]

Added a FastView and FastModel class to allow users to quickly search, populate, and sort a TreeView using HashTables.

[Scott Ringwelski (sgringwe)]

Testing with 20,000 items allowed for quick sorting, searching and populating (<1 second). Test with 1,000,000 items took some time to initially populate (6 seconds or so). After it was populated, search was almost instant (1 second to undo search back to ""). Sorting was not attempted, but would likely be very slow due to deep recursive calls on quicksort.

[Victor Martinez (victored)]

This widget is really fast. Judging by the comment in the source code it seems to me that FastModel should be internal. Have you added any improvement since you proposed the merge?

[Scott Ringwelski (sgringwe)]

Hmmm ya, I have.

On Sun, May 13, 2012 at 5:33 PM, Victor Eduardo <email address hidden>wrote:

> This widget is really fast. Judging by the comment in the source code it
> seems to me that FastModel should be internal. Have you added any
> improvement since you proposed the merge?
> --
> https://code.launchpad.net/~sgringwe/granite/fastview/+merge/94295
> You are the owner of lp:~sgringwe/granite/fastview.
>

Unmerged revisions

185. By Scott <email address hidden> on 2012-02-21

users may now quickly add and remove objects from a fastview

184. By Scott <email address hidden> on 2012-02-20

more work on fastview/fastmodel

183. By Scott <email address hidden> on 2012-02-20

fastview stuff

=== modified file 'demo/main.vala'
--- demo/main.vala	2012-02-19 20:14:25 +0000
+++ demo/main.vala	2012-02-22 23:24:19 +0000
@@ -21,6 +21,17 @@
 using Granite.Widgets;
 using Granite.Services;
 
+public class TestObject : GLib.Object {
+	public int id { get; set; }
+	public string name { get; set; }
+	public string address { get; set; }
+	public string phone { get; set; }
+	
+	public TestObject(int id) {
+		this.id = id;
+	}
+}
+
 public class Granite.Demo : Granite.Application
 {
     construct
@@ -204,11 +215,140 @@
         }
         contractor_tab.add(text_view);
         contractor_tab.add(new ContractorView("file:///home/user/file.txt", "text/plain"));
-
+		
+		/* FastModel */
+		var model_tab = new Gtk.VBox (false, 0);
+        notebook.append_page (model_tab, new Gtk.Label ("FastModel"));
+        
+        var types = new List<Type>();
+        types.append(typeof(int));
+        types.append(typeof(string));
+        types.append(typeof(string));
+        types.append(typeof(string));
+        var view = new Granite.Widgets.FastView(types);
+        
+        // add columns
+        view.insert_column_with_attributes(-1, "id", new Gtk.CellRendererText(), "text", 0, null);
+        view.insert_column_with_attributes(-1, "name", new Gtk.CellRendererText(), "text", 1, null);
+        view.insert_column_with_attributes(-1, "address", new Gtk.CellRendererText(), "text", 2, null);
+        view.insert_column_with_attributes(-1, "phone", new Gtk.CellRendererText(), "text", 3, null);
+        
+        for(int i = 0; i < 4; ++i) {
+			view.get_column(i).sizing = Gtk.TreeViewColumnSizing.FIXED;
+			view.get_column(i).fixed_width = 70;
+			view.get_column(i).clickable = true;
+			view.get_column(i).sort_column_id = i;
+		}
+        
+        // set funcs specific to TestObject type
+        view.set_compare_func(view_compare_func);
+        view.set_search_func(view_search_func);
+        view.set_value_func(view_value_func);
+		
+		var scroll = new Gtk.ScrolledWindow(null, null);
+		scroll.set_policy(Gtk.PolicyType.AUTOMATIC, Gtk.PolicyType.AUTOMATIC);
+		scroll.add(view);
+		model_tab.pack_start(scroll, true, true, 0);
+		
+		//var set_model_list = new Gtk.Button.with_label("Populate 20,000 items");
+		//model_tab.pack_end(set_model_list, false, true, 0);
+		//set_model_list.clicked.connect( ()=> {
+			var to_add = new HashTable<int, GLib.Object>(null, null);
+			var to_remove = new HashTable<int, GLib.Object>(null, null);
+			for(int i = 0; i < 20000; ++i) {
+				TestObject to = new TestObject(i);
+				
+				var val = (i + 20000).to_string();
+				to.name = val;
+				to.address = val;
+				to.phone = val;
+				to_add.set(i, to);
+				
+				if(i > 10000)
+					to_remove.set(i, to);
+			}
+			
+			view.set_table(to_add);
+		//});
+		var remove_all = new Gtk.Button.with_label("Remove last 10,000");
+		model_tab.pack_end(remove_all, false, true, 0);
+		remove_all.clicked.connect( ()=> {
+			view.remove_objects(to_remove.get_values());
+		});
+		var add_more = new Gtk.Button.with_label("Add 20,000 to start");
+		model_tab.pack_end(add_more, false, true, 0);
+		add_more.clicked.connect( ()=> {
+			var odds = new List<GLib.Object>();
+			for(int i = 0; i < 20000; ++i) {
+				TestObject to = new TestObject(i);
+				
+				var val = (i).to_string();
+				to.name = val;
+				to.address = val;
+				to.phone = val;
+				odds.append(to);
+			}
+			
+			view.add_objects(odds);
+		});
+			
+		var search_list = new Gtk.Entry();
+		model_tab.pack_start(search_list, false, true, 0);
+		search_list.changed.connect( () => {
+			view.do_search(search_list.get_text());
+		});
+		
         /* window properties */
         win.show_all();
         win.resize(800, 600);
     }
+    
+    int view_compare_func (int col, Gtk.SortType dir, GLib.Object a_o, GLib.Object b_o) {
+		int rv = 0;
+		
+		TestObject a = (TestObject)a_o;
+		TestObject b = (TestObject)b_o;
+		
+		if(col == 0)
+			rv = a.id - b.id;
+		else if(col == 1)
+			rv = (a.name > b.name) ? 1 : -1;
+		else if(col == 2)
+			rv = (a.address > b.address) ? 1 : -1;
+		else
+			rv = (a.phone > b.phone) ? 1 : -1;
+			
+		if(dir == Gtk.SortType.DESCENDING)
+			rv = (rv > 0) ? -1 : 1;
+			
+		return rv;
+	}
+	
+	void view_search_func (string search, HashTable<int, Object> table, ref HashTable<int, Object> show) {
+		int show_index = 0;
+		
+		for(int i = 0; i < table.size(); ++i) {
+			if(((TestObject)table.get(i)).name.contains(search))
+				show.set(show_index++, table.get(i));
+		}
+	}
+	
+	Value view_value_func (int column, GLib.Object o) {
+		Value val;
+		
+		TestObject to = (TestObject)o;
+		
+		if(column == 0)
+			val = to.id;
+		else if(column == 1)
+			val = to.name;
+		else if(column == 2)
+			val = to.address;
+		else
+			val = to.phone;
+		
+		return val;
+	}
 
     public static int main(string[] args)
     {

=== modified file 'lib/CMakeLists.txt'
--- lib/CMakeLists.txt	2012-02-19 13:58:41 +0000
+++ lib/CMakeLists.txt	2012-02-22 23:24:19 +0000
@@ -68,7 +68,12 @@
     Widgets/ToolButtonWithMenu.vala
     Widgets/PopOver.vala
     Widgets/ContractorView.vala
+<<<<<<< TREE
     Widgets/ContractorMenu.vala
+=======
+    Widgets/FastView.vala
+    Widgets/FastModel.vala
+>>>>>>> MERGE-SOURCE
     Main.vala
     config.vapi
 CUSTOM_VAPIS

=== added file 'lib/Widgets/FastModel.vala'
--- lib/Widgets/FastModel.vala	1970-01-01 00:00:00 +0000
+++ lib/Widgets/FastModel.vala	2012-02-22 23:24:19 +0000
@@ -0,0 +1,200 @@
+using Gtk;
+
+/** Since this class is not publicly facing (the FastView is public part),
+ * this model is low level and optimized. We are not worried about stupid
+ * users here.
+**/
+public class Granite.Widgets.FastModel : GLib.Object, TreeModel, TreeSortable {
+	int stamp; // all iters must match this
+	
+	/* data storage variables */
+	HashTable<int, GLib.Object> rows; // internal id -> user specified object
+	List<Type> columns;
+	
+	private int sort_column_id;
+	private SortType sort_direction;
+	
+	/* user specific function for get_value() */
+	public delegate Value ValueReturnFunc (int column, GLib.Object o);
+	private ValueReturnFunc value_func;
+	
+	public signal void reorder_requested (int column, Gtk.SortType direction);
+
+	/** Initialize data storage, columns, etc. **/
+	public FastModel (List<Type> column_types) {
+		columns = column_types.copy();
+		rows = new HashTable<int, GLib.Object>(null, null);
+		
+		sort_column_id = -2;
+		sort_direction = SortType.ASCENDING;
+		
+		stamp = (int)GLib.Random.next_int();
+	}
+
+	public Type get_column_type (int col) {
+		return columns.nth_data(col);
+	}
+
+	public TreeModelFlags get_flags () {
+		return TreeModelFlags.LIST_ONLY;
+	}
+
+	public bool get_iter (out TreeIter iter, TreePath path) {
+		iter = TreeIter();
+		int path_index = path.get_indices()[0];
+		if(rows.size() == 0 || path_index < 0 || path_index >= rows.size() || rows.get(path_index) == null)
+			return false;
+
+		iter.stamp = this.stamp;
+		iter.user_data = (void*)path_index;
+
+		return true;
+	}
+
+	public int get_n_columns () {
+		return (int)columns.length();
+	}
+
+	public TreePath? get_path (TreeIter iter) {
+		return new TreePath.from_string (((int)iter.user_data).to_string());
+	}
+	
+	public void get_value (TreeIter iter, int column, out Value val) {
+		if(iter.stamp != this.stamp || column < 0 || column >= get_n_columns()) {
+			val = Value(get_column_type(column));
+			return;
+		}
+		
+		if(!((int)iter.user_data >= rows.size())) {
+			var object = rows.get(((int)iter.user_data));
+			val = value_func(column, object);
+		}
+	}
+
+	public bool iter_children (out TreeIter iter, TreeIter? parent) {
+		iter = TreeIter();
+		return false;
+	}
+
+	public bool iter_has_child (TreeIter iter) {
+
+		return false;
+	}
+
+	public int iter_n_children (TreeIter? iter) {
+		if(iter == null)
+			return (int)rows.size();
+
+		return 0;
+	}
+
+	public bool iter_next (ref TreeIter iter) {
+		if(iter.stamp != this.stamp)
+			return false;
+
+		iter.user_data = (void*)(((int)iter.user_data) + 1);
+
+		if(((int)iter.user_data) >= rows.size())
+			return false;
+
+		return true;
+	}
+
+	public bool iter_nth_child (out TreeIter iter, TreeIter? parent, int n) {
+		iter = TreeIter();
+
+		if(n < 0 || n >= rows.size() || parent != null)
+			return false;
+
+		iter.stamp = this.stamp;
+		iter.user_data = (void*)n;
+
+		return true;
+	}
+
+	public bool iter_parent (out TreeIter iter, TreeIter child) {
+		iter = TreeIter();
+
+		return false;
+	}
+	
+	public void append (out TreeIter iter) {
+		iter = TreeIter();
+
+		rows.set((int)rows.size(), new GLib.Object());
+		iter.stamp = this.stamp;
+		iter.user_data = (void*)rows.size;
+	}
+	
+	public void remove (TreeIter iter) {
+		if(iter.stamp != this.stamp)
+			return;
+
+		var path = new TreePath.from_string(((int)iter.user_data).to_string());
+		rows.remove((int)iter.user_data);
+		row_deleted(path);
+		
+		// TODO: swap all indices > this iter's index down to maintain that
+		// the table has row ids 0..n where n is rows.size (consecutive ids)
+	}
+	
+	// Not applicable to this custom treemodel
+	public new void set (TreeIter iter, ...) {
+		return;
+	}
+	
+	public void ref_node (TreeIter iter) {}
+	public void unref_node (TreeIter iter) {}
+
+	/** The beauty of this custom model. This tree model is simply a visual
+	 * representation of a HashTable of objects. Before calling this
+	 * method, the user should set tree_view.set_model(null). After
+	 * calling this, set the tree_view.set_model(fast_model). By doing this
+	 * the treeview will not listen for append events and will recalculate
+	 * and draw when the model is re-added.
+	 * 
+	 * @objects Must be a consecutive ordered hash table with indexes 
+	 * 0-n where n is size of the hashtable (no gaps).
+	**/
+	public void set_table (HashTable<int, GLib.Object> table) {
+		rows = table;
+	}
+	
+	/** Crucial. Must be set by user. Allows for this model to be abstract
+	 * by allowing the user to specify the function that returns values
+	 * based on the object (row) and column. **/
+	public void set_value_func (ValueReturnFunc func) {
+		value_func = func;
+	}
+	
+	/** The following functions are for implementing TreeSortable. We pass
+	 * off responsibility to sort things to the view.
+	**/
+	public bool get_sort_column_id (out int sort_column_id, out SortType order) {
+		sort_column_id = this.sort_column_id;
+		order = this.sort_direction;
+		
+		return true;
+	}
+	
+	public void set_sort_column_id (int column, SortType order) {
+		sort_column_id = column;
+		sort_direction = order;
+		
+		reorder_requested(column, order);
+		sort_column_changed();
+	}
+	
+	/** The following functions are only here to implement TreeSortable **/
+	public bool has_default_sort_func () {
+		return true; // place holder. not used.
+	}
+	
+	public void set_sort_func (int sort_column_id, owned TreeIterCompareFunc sort_func) {
+		// place holder. not used.
+	}
+
+	public void set_default_sort_func (owned TreeIterCompareFunc sort_func) {
+		// place holder. not used.
+	}
+}

=== added file 'lib/Widgets/FastView.vala'
--- lib/Widgets/FastView.vala	1970-01-01 00:00:00 +0000
+++ lib/Widgets/FastView.vala	2012-02-22 23:24:19 +0000
@@ -0,0 +1,151 @@
+using Gtk;
+
+public class Granite.Widgets.FastView : TreeView {
+	FastModel fm;
+	List<Type> columns;
+	HashTable<int, GLib.Object> table; // is not the same object as showing.
+	HashTable<int, GLib.Object> showing; // should never point to table.
+	
+	/* sortable stuff */
+	public delegate int SortCompareFunc (int sort_column_id, Gtk.SortType sort_direction, GLib.Object a, GLib.Object b);
+	private int sort_column_id;
+	private SortType sort_direction;
+	private SortCompareFunc compare_func;
+	
+	// search stuff
+	string last_search;
+	public delegate void ViewSearchFunc (string search, HashTable<int, GLib.Object> table, ref HashTable<int, GLib.Object> showing);
+	private ViewSearchFunc search_func;
+	
+	public FastView (List<Type> types) {
+		columns = types.copy();
+		table = new HashTable<int, GLib.Object>(null, null);
+		showing = new HashTable<int, GLib.Object>(null, null);
+		fm = new FastModel(types);
+		
+		sort_column_id = -2;
+		sort_direction = SortType.ASCENDING;
+		last_search = "";
+		
+		fm.reorder_requested.connect(reorder_requested);
+		
+		set_table(table);
+	}
+	
+	public void set_value_func(FastModel.ValueReturnFunc func) {
+		fm.set_value_func(func);
+	}
+	
+	public void set_table (HashTable<int, GLib.Object> table) {
+		this.table = table;
+		do_search(null);
+	}
+	
+	public void remove_objects (List<GLib.Object> objects) {
+		int index = 0;
+		var new_table = new HashTable<int, Object>(null, null);
+		for(int i = 0; i < table.size(); ++i) {
+			Object o;
+			if((o = table.get(i)) != null && objects.find(o) == null) {
+				new_table.set(index++, o);
+			}
+		}
+		
+		set_table(new_table);
+	}
+	
+	public void add_objects (List<GLib.Object> objects) {
+		foreach(var o in objects) {
+			table.set((int)table.size(), o);
+		}
+		
+		resort();
+	}
+	
+	public void set_search_func (ViewSearchFunc func) {
+		search_func = func;
+	}
+	
+	public void do_search (string? search) {
+		TreePath showing_path;
+		TreeViewColumn showing_col;
+		int cell_x, cell_y;
+		get_path_at_pos(1, 1, out showing_path, out showing_col, out cell_x, out cell_y);
+		
+		set_model(null);
+		showing.remove_all();
+		
+		if(search != null)
+			last_search = search;
+		
+		if(last_search == "") {
+			for(int i = 0; i < table.size(); ++i) {
+				showing.set(i, table.get(i));
+			}
+		}
+		else {
+			search_func(last_search, table, ref showing);
+		}
+		
+		fm.set_table(showing);
+		set_model(fm);
+		
+		if(showing_path != null && showing_col != null)
+			scroll_to_cell(showing_path, showing_col, false, 0f, 0f);
+		else
+			warning("Could not scroll to previous position.\n");
+	}
+	
+	/** Sorting is done in the treeview, not the model. That way the whole
+	 * table is sorted and ready to go and we do not need to resort every
+	 * time we repopulate/search the model
+	**/
+	public void set_sort_column_id (int sort_column_id, SortType order) {
+		reorder_requested(sort_column_id, order);
+	}
+	
+	void reorder_requested (int column, Gtk.SortType direction) {
+		if(column == sort_column_id && direction == sort_direction)
+			return;
+		
+		sort_column_id = column;
+		sort_direction = direction;
+		
+		quicksort(0, (int)(table.size() - 1));
+		do_search(null);
+	}
+	
+	void resort () {
+		quicksort(0, (int)(table.size() - 1));
+		do_search(null);
+	}
+	
+	public void set_compare_func (SortCompareFunc func) {
+		compare_func = func;
+	}
+	
+	// TODO: Is slow.
+	void swap (int a, int b) {
+		GLib.Object temp = table.get(a);
+		table.set(a, table.get(b));
+		table.set(b, temp);
+	}
+	
+	public void quicksort (int start, int end) {
+		GLib.Object pivot = table.get((start+end)/2);
+		int i = start;
+		int j = end;
+		
+		do {
+			while(i < end && compare_func (sort_column_id, sort_direction, table.get(i), pivot) < 0) ++i;
+			while(j > start && compare_func (sort_column_id, sort_direction, table.get(j), pivot) > 0) --j;
+			if(i <= j) {
+				swap(i, j);
+				++i; --j;
+			}
+		} while(i <= j);
+		
+		if(start < j)	quicksort (start, j);
+		if(i < end)		quicksort (i, end);
+	}
+}