/*
 * FisheyeListView - View a TreeModel as a list that does not need scrolling
 *
 * Copyright (C) 2009  Enrico Zini <enrico@enricozini.org>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

using GLib;

protected struct FocusInfo
{
	int y;
	int renderer;
}

protected class PrefixInfo
{
	public string prefix;
	public size_t pfx_len;
	public int pos;
	public int layout_pos;

	public PrefixInfo(string prefix, int pos)
	{
		this.prefix = prefix;
		this.pfx_len = prefix.size();
		this.pos = pos;
		this.layout_pos = 0;
	}

	/**
	 * If s and prefix share a prefix, set prefix to the common prefix, and
	 * return true.
	 * Else, return false.
	 */
	public bool refine(string s, int min_prefix_size=1)
	{
		size_t len;
		for (len = 0; prefix[len] != 0 && s[len] != 0 && s[len] == prefix[len]; ++len)
			;
		if (len < min_prefix_size) return false;
		if (len != pfx_len)
		{
			prefix = prefix.substring(0, (int)len);
			pfx_len = len;
		}
		return true;
	}
}

protected struct LabelInfo
{
	string label;
	int index;
}

public class FisheyeListView : Gtk.DrawingArea
{
	protected Gtk.TreeModel model;
	protected Gdk.Pixmap background;
	protected Gdk.Pixmap backing_store;

	// Renderers used at different sizes
	protected const int steps = 5;
	protected Gtk.CellRendererText[] renderers;
	protected int[] renderer_sizes;
	protected int max_renderer_size;

	// Labels to show, extracted from the model
	protected LabelInfo[] label_cache;
	protected int label_count;
	protected bool base_layout_needed;

	// Prefix information
	protected List<PrefixInfo> prefixes;
	protected Pango.Layout prefix_layout;

	protected int cur_el;
	protected weak PrefixInfo cur_pfx;

	// Layout information
	protected int focus_first;
	protected int focus_end;
	protected FocusInfo[] focus_info;
	protected bool focus_locked;
	protected bool focus_layout_needed;
	protected bool is_fisheye;
	protected int focus_step_size;
	protected int focus_area_start;

	// Number of elements in full focus
	protected int _focus_size;
	public int focus_size {
		get { return _focus_size; }
		set {
			_focus_size = value;
			focus_info = new FocusInfo[_focus_size+2*steps+1];
			focus_layout_needed = true;
			queue_draw();
		}
	}

	protected int _label_column;
	public int label_column {
		get { return _label_column; }
		set {
			_label_column = value;
			base_layout_needed = true;
			queue_draw();
		}
	}

	protected string _prefix_filter;
	public string prefix_filter {
		get { return _prefix_filter; }
		set {
			_prefix_filter = value;
			base_layout_needed = true;
			queue_draw();
		}
	}

	//public virtual signal void cursor_changed ();
	public signal void row_activated(Gtk.TreePath path);

	public FisheyeListView()
	{
		model = null;
		backing_store = null;

		label_cache = null;
		label_count = 0;
		prefixes = null;
		prefix_filter = null;

		renderers = new Gtk.CellRendererText[steps];
		renderer_sizes = new int[steps];
		prefix_layout = null;

		// Defaults for properties
		focus_size = 10;
		label_column = 0;

		cur_el = 0;
		cur_pfx = null;
		focus_locked = false;

		add_events(Gdk.EventMask.POINTER_MOTION_MASK
		         | Gdk.EventMask.BUTTON_PRESS_MASK
			 | Gdk.EventMask.BUTTON_RELEASE_MASK);
	}

	public unowned Gtk.TreeModel get_model() { return model; }
	public void set_model (Gtk.TreeModel? model)
	{
		if (this.model != null)
		{
			this.model.row_changed -= on_row_changed;
			this.model.row_deleted -= on_row_deleted;
			this.model.row_has_child_toggled -= on_row_has_child_toggled;
			this.model.row_inserted -= on_row_inserted;
			this.model.rows_reordered -= on_rows_reordered;
		}
		this.model = model;
		this.model.row_changed += on_row_changed;
		this.model.row_deleted += on_row_deleted;
		this.model.row_has_child_toggled += on_row_has_child_toggled;
		this.model.row_inserted += on_row_inserted;
		this.model.rows_reordered += on_rows_reordered;
		base_layout_needed = true;
		queue_draw();
	}

	private void on_row_changed(Gtk.TreePath path, Gtk.TreeIter iter) { base_layout_needed = true; }
	private void on_row_deleted(Gtk.TreePath path) { base_layout_needed = true; }
	private void on_row_has_child_toggled(Gtk.TreePath path, Gtk.TreeIter iter) { base_layout_needed = true; }
	private void on_row_inserted(Gtk.TreePath path, Gtk.TreeIter iter) { base_layout_needed = true; }
	private void on_rows_reordered(Gtk.TreePath path, Gtk.TreeIter iter, void* new_order) { base_layout_needed = true; }

	/* Mouse button got pressed over widget */
	/*
	public override bool button_press_event(Gdk.EventButton event)
	{
		stderr.printf("Mouse pressed on %d %s\n", cur_el, label_cache[cur_el]);
		return false;
	}
	*/

	/* Mouse button got released */
	public override bool button_release_event(Gdk.EventButton event)
	{
		if (model == null) return false;
		//stderr.printf("Mouse released on %d %s\n", cur_el, label_cache[cur_el]);

		// Emit row_activated if applicable
		int x = (int)event.x;
		if (x < allocation.width / 3)
		{
			Gtk.TreeIter iter;
			if (model.iter_nth_child(out iter, null, label_cache[cur_el].index))
			{
				Gtk.TreePath path = model.get_path(iter);
				row_activated(path);
			}
		} else if (cur_pfx != null && x > allocation.width * 2 / 3) {
			//stderr.printf("Mouse released on prefix %s\n", cur_pfx.prefix);
			prefix_filter = cur_pfx.prefix;
		}
		return false;
	}

	/* Mouse pointer moved over widget */
	public override bool motion_notify_event(Gdk.EventMotion event)
	{
		int old_cur_el = cur_el;
		int x = (int)event.x;
		int y = (int)event.y;

		if (is_fisheye)
		{
			focus_locked = !focus_layout_needed && x < allocation.width/3 && y >= focus_area_start+focus_info[0].y && y < focus_area_start+focus_info[focus_end - focus_first].y;

			if (!focus_locked || y < focus_area_start+focus_info[0].y || y >= focus_area_start+focus_info[focus_end - focus_first].y)
				cur_el = y * (label_count+1) / allocation.height;
			else
				for (int idx = 0; idx < focus_info.length; ++idx)
					if (y - focus_area_start < focus_info[idx].y + renderer_sizes[focus_info[idx].renderer])
					{
						cur_el = idx + focus_first;
						break;
					}

			if (prefixes != null)
			{
				cur_pfx = prefixes.data;
				for (weak List<PrefixInfo> i = prefixes; i != null && y > i.data.layout_pos; i = i.next)
					cur_pfx = i.data;
			} else {
				cur_pfx = null;
			}

			if (!focus_locked && old_cur_el != cur_el)
				focus_layout_needed = true;
		} else {
			cur_el = y / max_renderer_size;
			if (cur_el >= label_count)
				cur_el = label_count - 1;
		}

		//stderr.printf("MOTION %f %f CE %d\n", event.x, event.y, cur_el);
		if (old_cur_el != cur_el)
		{
			queue_draw();
			old_cur_el = cur_el;
		}
		return false;
	}

	public override bool configure_event (Gdk.EventConfigure event)
	{
		base_layout_needed = true;
		queue_draw();
		return false;
	}

	/* Widget is asked to draw itself */
	public override bool expose_event (Gdk.EventExpose event)
	{
		draw();

   		window.draw_drawable(
			get_style().fg_gc[Gtk.StateType.NORMAL],
			backing_store,
			event.area.x, event.area.y,
			event.area.x, event.area.y,
			event.area.width, event.area.height);

		return false;
	}

	public override void style_set(Gtk.Style? previous_style)
	{
		base_layout_needed = true;
	}
	public override void direction_changed(Gtk.TextDirection previous_direction)
	{
		base_layout_needed = true;
	}

	protected Gtk.CellRendererText make_cell_renderer()
	{
		var res = new Gtk.CellRendererText();
		res.font_desc = get_style().font_desc;
		res.ypad = 0;
		return res;
	}

	protected void base_layout()
	{
		// Rebuild label cache
		cur_pfx = null;
		prefixes = new List<PrefixInfo>();
		if (model == null)
		{
			label_cache = null;
			label_count = 0;
		} else {
			Gtk.TreeIter iter;
			if (!model.get_iter_first(out iter))
			{
				label_cache = null;
				label_count = 0;
			}
			else
			{
				int count = model.iter_n_children(null);
				label_cache = new LabelInfo[count];

				int lc_idx = 0;
				int model_idx = 0;
				PrefixInfo pi = null;
				int min_prefix_size = _prefix_filter == null ? 1 : (int)_prefix_filter.size() + 1;
				do {
					string val;
					model.get(iter, _label_column, out val, -1);

					// Apply prefix filter
					if (_prefix_filter == null || val.has_prefix(_prefix_filter))
					{
						label_cache[lc_idx].label = val;
						label_cache[lc_idx].index = model_idx;
						if (pi == null || !pi.refine(val, min_prefix_size))
						{
							if (pi != null) prefixes.append(pi);
							pi = new PrefixInfo(val, lc_idx);
						}
						++lc_idx;
					}
					++model_idx;
				} while (model.iter_next(ref iter));
				prefixes.append(pi);
				label_count = lc_idx;
			}
		}
		for (weak List<PrefixInfo> i = prefixes; i != null; i = i.next)
			i.data.layout_pos = i.data.pos * allocation.height / (label_count+1);

		background = new Gdk.Pixmap(window, allocation.width, allocation.height, -1);
		backing_store = new Gdk.Pixmap(window, allocation.width, allocation.height, -1);

		// Recreate the renderers
		renderers[renderers.length-1] = make_cell_renderer();
		renderers[renderers.length-1].set_fixed_height_from_font(1);
		renderers[renderers.length-1].get_size(this, null, null, null, null, out max_renderer_size);
		renderer_sizes[renderers.length-1] = max_renderer_size;

		is_fisheye = label_count * max_renderer_size > allocation.height;

		if (is_fisheye)
		{
			renderers[0] = make_cell_renderer();
			renderers[0].size = Pango.SCALE;
			renderers[0].set_fixed_height_from_font(1);
			int min_renderer_size;
			renderers[0].get_size(this, null, null, null, null, out min_renderer_size);
			renderer_sizes[0] = min_renderer_size;

			focus_step_size = 0;	// Size of the diminishing area
			for (int i = 1; i < renderers.length-1; ++i)
			{
				renderers[i] = make_cell_renderer();
				renderers[i].scale = (double)i / renderers.length;
				renderers[i].set_fixed_height_from_font(1);
				int size;
				renderers[i].get_size(this, null, null, null, null, out size);
				renderer_sizes[i] = size;
				focus_step_size += size;
			}
		}

		// Draw background
		draw_background(background);

		base_layout_needed = false;
		focus_layout_needed = true;
	}

	protected int el_renderer(int idx)
	{
		int fs2 = _focus_size/2;
		int renderer_idx;
		if (idx < cur_el)
			renderer_idx = idx - (cur_el-fs2-steps);
		else
			renderer_idx = (cur_el+fs2+steps) - idx;
		if (renderer_idx < 0)
			return 0;
		if (renderer_idx >= renderer_sizes.length)
			return renderer_sizes.length-1;
		return renderer_idx;
	}

	protected void focus_layout()
	{
		if (!is_fisheye || label_count == 0)
		{
			focus_first = 0;
			focus_end = 0;
			focus_layout_needed = false;
			return;
		}

		focus_first = cur_el - _focus_size/2 - steps;
		if (focus_first < 0) focus_first = 0;
		if (focus_first + focus_info.length > label_count)
			focus_first = label_count - focus_info.length;

		int cur_pos = 0;
		int cur_idx = 0;
		int focus_area_pre = 0;
		while (cur_pos < allocation.height && cur_idx < focus_info.length)
		{
			if (focus_first + cur_idx == cur_el)
				focus_area_pre = cur_pos;
			focus_info[cur_idx].y = cur_pos;
			focus_info[cur_idx].renderer = el_renderer(focus_first + cur_idx);
//			stderr.printf("LAYOUT %d+[0-%d-%d] item %d/%d: pos %d rend %d rsz %d\n",
//				focus_first, cur_idx, focus_info.length, focus_first + cur_idx, label_count,
//				cur_pos, focus_info[cur_idx].renderer, renderer_sizes[focus_info[cur_idx].renderer]);
			cur_pos += renderer_sizes[focus_info[cur_idx].renderer];
			++cur_idx;
		}

		focus_info[cur_idx].y = cur_pos;
		focus_info[cur_idx].renderer = 0;
		focus_end = focus_first + cur_idx;

		int anchor_y = cur_el * allocation.height / (label_count+1);
		int focus_area_size = cur_pos;

		focus_area_start = anchor_y - focus_area_pre;
		if (focus_area_start < 0) focus_area_start = 0;
		if (focus_area_start + focus_area_size > allocation.height)
			focus_area_start = allocation.height - focus_area_size;

//		stderr.printf("FA [0 [%d+%d=%d] %d]\n", focus_area_start, focus_area_size, focus_area_start+focus_area_size, allocation.height);

		focus_layout_needed = false;
	}

	protected void draw_background(Gdk.Drawable drawable)
	{
                Gtk.Style style = get_style();

		// Background
		drawable.draw_rectangle(style.bg_gc[Gtk.StateType.NORMAL], true, 0, 0, allocation.width, allocation.height);

		if (!is_fisheye)
			return;

		// Focus movement area
		drawable.draw_rectangle(style.bg_gc[Gtk.StateType.INSENSITIVE], true,
			allocation.width/3, 0, allocation.width/3, allocation.height);

		for (int y = 0; y < allocation.height/2 - 30; y += 30)
		{
			Gtk.paint_arrow(style, (Gdk.Window*)drawable, Gtk.StateType.INSENSITIVE, Gtk.ShadowType.NONE,
				null, this, null, Gtk.ArrowType.UP, false,
				allocation.width/3, y, allocation.width/3, 10);
			Gtk.paint_arrow(style, (Gdk.Window*)drawable, Gtk.StateType.INSENSITIVE, Gtk.ShadowType.NONE,
				null, this, null, Gtk.ArrowType.DOWN, false,
				allocation.width/3, allocation.height-y-30, allocation.width/3, 10);
		}

		// Draw tiny labels
		Gdk.Rectangle expose_area = Gdk.Rectangle();
		expose_area.x = expose_area.y = 0;
		expose_area.width = allocation.width;
		expose_area.height = allocation.height;

		Gdk.Rectangle cell_area = Gdk.Rectangle();
		cell_area.x = 0;
		cell_area.width = allocation.width;
		cell_area.height = renderer_sizes[0];
		if (label_count * cell_area.height >= allocation.height)
		{
			for (int y = 0; y < allocation.height; y += cell_area.height)
			{
				int idx = y * label_count / allocation.height;
				cell_area.y = y;
				renderers[0].text = label_cache[idx].label;
				renderers[0].render((Gdk.Window*)drawable, this, 
						cell_area,
						cell_area,
						expose_area,
						0);
			}
		} else {
			int count = int.min(allocation.height/(2*cell_area.height), label_count);
			for (int idx = 0; idx < count; ++idx)
			{
				cell_area.y = idx * cell_area.height;
				renderers[0].text = label_cache[idx].label;
				renderers[0].render((Gdk.Window*)drawable, this, 
						cell_area,
						cell_area,
						expose_area,
						0);

				cell_area.y = allocation.height-cell_area.y;
				renderers[0].text = label_cache[label_count-idx].label;
				renderers[0].render((Gdk.Window*)drawable, this, 
						cell_area,
						cell_area,
						expose_area,
						0);
			}
		}

		// Draw prefix labels
		prefix_layout = create_pango_layout(null);
		Pango.Rectangle lr;
		prefix_layout.get_extents(null, out lr);
		int label_height = lr.height / Pango.SCALE;
		prefix_layout.set_alignment(Pango.Alignment.RIGHT);
		prefix_layout.set_width(allocation.width*Pango.SCALE/3);
		prefix_layout.set_height(0);
		prefix_layout.set_ellipsize(Pango.EllipsizeMode.END);

		int last_covered = 0;

		for (weak List<PrefixInfo> i = prefixes; i != null; i = i.next)
		{
			if (i.data.layout_pos < last_covered)
				i.data.layout_pos = last_covered;
			prefix_layout.set_text(i.data.prefix, (int)i.data.pfx_len);
			Gtk.paint_layout(style, (Gdk.Window*)drawable, Gtk.StateType.INSENSITIVE, true, null, this, null, allocation.width*2/3, i.data.layout_pos, prefix_layout);
			last_covered = i.data.layout_pos + label_height;
		}
	}

	protected void draw()
	{
		if (base_layout_needed)
			base_layout();
		if (focus_layout_needed)
			focus_layout();

		var drawable = backing_store;
                Gtk.Style style = get_style();
		Gdk.Rectangle expose_area = Gdk.Rectangle();
		expose_area.x = expose_area.y = 0;
		expose_area.width = allocation.width;
		expose_area.height = allocation.height;

		// Background
   		drawable.draw_drawable(
			get_style().fg_gc[Gtk.StateType.NORMAL],
			background,
			0, 0, 0, 0,
			allocation.width, allocation.height);

		if (is_fisheye)
		{
			// Paint current prefix
			if (cur_pfx != null)
			{
				prefix_layout.set_text(cur_pfx.prefix, (int)cur_pfx.pfx_len);
				Gtk.paint_layout(style, (Gdk.Window*)drawable, Gtk.StateType.NORMAL, true, null, this, null, allocation.width*2/3, cur_pfx.layout_pos, prefix_layout);
			}

			// Focus lock area
			drawable.draw_rectangle(style.bg_gc[Gtk.StateType.ACTIVE], true,
				0, focus_area_start + focus_info[0].y, allocation.width/3, focus_info[focus_end - focus_first].y);

			// Paint items around focus
			Gdk.Rectangle cell_area = Gdk.Rectangle();
			cell_area.x = 0;
			cell_area.width = expose_area.width;
			for (int idx = 0; idx < focus_info.length; ++idx)
			{
				var renderer = renderers[focus_info[idx].renderer];
				cell_area.y = focus_area_start + focus_info[idx].y;
				cell_area.height = renderer_sizes[focus_info[idx].renderer];

				Gtk.CellRendererState rflags = 0;
				if (idx + focus_first == cur_el)
				{
					rflags |= Gtk.CellRendererState.SELECTED | Gtk.CellRendererState.FOCUSED;
					drawable.draw_rectangle(style.bg_gc[Gtk.StateType.SELECTED], true,
							cell_area.x, cell_area.y, allocation.width, cell_area.height);
				}
			
				renderer.text = label_cache[idx + focus_first].label;
				renderer.render((Gdk.Window*)drawable, this, 
						cell_area,
						cell_area,
						expose_area,
						rflags);

				//Gdk.draw_line(drawable, style.fg_gc[itemState], 0, y0, allocation.width, y0);
			}
		} else {
			// Paint all items sequentially
			var renderer = renderers[renderers.length-1];
			Gdk.Rectangle cell_area = Gdk.Rectangle();
			cell_area.x = 0;
			cell_area.width = allocation.width;
			cell_area.height = max_renderer_size;
			for (int idx = 0; idx < label_count; ++idx)
			{
				cell_area.y = idx * cell_area.height;

				Gtk.CellRendererState rflags = 0;
				if (idx == cur_el)
				{
					rflags |= Gtk.CellRendererState.SELECTED | Gtk.CellRendererState.FOCUSED;
					drawable.draw_rectangle(style.bg_gc[Gtk.StateType.SELECTED], true,
							cell_area.x, cell_area.y, cell_area.width, cell_area.height);
				}

				renderer.text = label_cache[idx].label;
				renderer.render((Gdk.Window*)drawable, this, 
						cell_area,
						cell_area,
						expose_area,
						rflags);
			}
		}
	}

	/*
	 * A relevant annotation from Prefuse:
	 *
	 * For more details on this form of transformation, see Manojit Sarkar and 
	 * Marc H. Brown, "Graphical Fisheye Views of Graphs", in Proceedings of 
	 * CHI'92, Human Factors in Computing Systems, p. 83-91, 1992. Available
	 * online at <a href="http://citeseer.ist.psu.edu/sarkar92graphical.html">
	 * http://citeseer.ist.psu.edu/sarkar92graphical.html</a>. 
	 *
	 * See also http://www.cs.umd.edu/hcil/fisheyemenu/
	 */
}