# Sketch - A Python-based interactive drawing program
# Copyright (C) 1996, 1997, 1998 by Bernhard Herzog
#
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Library General Public
# License as published by the Free Software Foundation; either
# version 2 of the License, or (at your option) any later version.
#
# This library 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
# Library General Public License for more details.
#
# You should have received a copy of the GNU Library General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


# Functions to manipulate selection info

#
# Representation
#
# The set of currently selected objects in Sketch is represented as a
# list of tuples. Each of the tuples has the form:
#
#	(PATH, OBJ)
#
# where OBJ is a selected object and PATH is a tuple of ints describing
# the path through the hierarchy of objects to OBJ, usually starting
# from the document at the top of the hierarchy. Each item in PATH is
# the index of the next object in the path. For example, the second
# object in the first layer has the PATH (0, 1) (indexes start from 0).
#
# This representation serves two purposes:
#
#	1. storing the path to the object allows fast access to the
#	parents of the selected object.
#
#	2. it allows sorting the list by path, which results in a list
#	with the objects lowest in the stack of objects at the front.
#
#	A sorted list is important when changing the stacking order of
#	objects, since the indices, i.e. the path elements, may change
#	during the operation.
#
#	Sorting the list also allows to make sure that each selected
#	object is listed exactly once in the list.
#
# This representation, if the list is sorted, is called the _standard
# representation_.
#
# Alternative Representations:
#
# There are several alternative representations that are mainly useful
# in the methods of compound objects that rearrange the children. In
# those methods, the path is usually taken relative to self. Where
# selection info has to be passed to children, to rearrange their
# children, the first component of the path is stripped, so that the
# path is relative to the child.
#
# All of the alternative representations are lists of tuples sorted at
# least by the first item of the tuples.
#
# Tree:
#
# An alternative representation of the selection info is a list of
# tuples of the form:
#
#	(INDEX, LIST)
#
# where INDEX is just the first part of the PATH of the standard
# representation and LIST is a list of selection info in standard
# representation but with each PATH stripped of its first component
# which is INDEX. That is, LIST is selection info in standard form
# relative to the compound object given by INDEX.
#
# Tree2:
#
# Just like Tree1, but if LIST would contain just one item with an empty
# PATH (an empty tuple), LIST is replaced by the object.
#
# Sliced Tree:
#
# A variant of Tree2, where consecutive items with an object (i.e.
# something that is no list) are replaced by a tuple `(start, end)'
# where start is the lowest INDEX and end the highest. Consecutive items
# are items where the INDEX parts are consecutive integers.
#
#
# Creating Selection Info:
#
# Selecting objects is done for instance by the GraphicsObject method
# SelectSubobject. In a compound object, when it has determined that a
# certain non compound child obj is to be selected, this method
# constructs a selection info tuple by calling build_info:
#
#	info1 = build_info(idx1, obj)
#
# idx is the index of obj in the compound object's list of children.
# info1 will then be just a tuple: ((idx1,) obj) This info is returned
# to the caller, its parent, which is often another compound object.
# This parent then extends the selection info with
#
#	info2 = prepend_idx(idx2, info)
#
# This results in a new tuple new_info: ((idx2, idx1), obj). idx2 is, of
# course, the index of the compound object in its parent's list of
# children.
#
# Finally, the document object receives such a selection info tuple from
# one of its layers, prepends that layer's index to the info and puts it
# into the list of selected objects.
#


from types import TupleType, ListType

def build_info(idx, obj):
    return ((idx,), obj)

def prepend_idx(idx, info):
    # prepend idx to the path of info.
    if type(info) == TupleType:
	return ((idx,) + info[0], info[1])

    if type(info) == ListType:
	idx = (idx,)
	for i in range(len(info)):
	    tmp = info[i]
	    info[i] = (idx + tmp[0], tmp[1])
	return info

    # assume info is an instance object
    return ((idx,), info)

def select_all(objects):
    return map(None, map(lambda *t: t, range(len(objects))), objects)

def select_range(min, objects):
    return map(None, map(lambda *t: t, range(min, min + len(objects))),
	       objects)

def get_parent(info):
    path, obj = info
    if len(path) > 1:
	parent = obj.parent
	if parent is not None:
	    return (path[:-1], parent)
    return None


def list_to_tree(infolist):
    # convert standard representation to Tree1 representation
    dict = {}
    for info in infolist:
	path, obj = info
	idx = path[0]
	info = (path[1:], obj)
	try:
	    dict[idx].append(info)
	except KeyError:
	    dict[idx] = [info]
    result = dict.items()
    result.sort()
    for idx, info in result:
	info.sort()
    return result

def list_to_tree2(infolist):
    # convert standard representation to Tree2 representation
    dict = {}
    for info in infolist:
	path, obj = info
	idx = path[0]
	path = path[1:]
	if path:
	    info = (path, obj)
	else:
	    info = obj
	try:
	    dict[idx].append(info)
	except KeyError:
	    dict[idx] = [info]
    result = dict.items()
    result.sort()
    for i in range(len(result)):
	idx, info = result[i]
	if len(info) == 1 and type(info[0]) != TupleType:
	    result[i] = (idx, info[0])
	else:
	    info.sort()
    return result

def list_to_tree_sliced(infolist):
    # convert standard representation to sliced tree representation
    result = []
    slice_start = slice_end = -1
    last_obj = None
    for idx, list in list_to_tree2(infolist):
	if type(list) != ListType:
	    # list is a child
	    if idx == slice_end:
		slice_end = idx + 1
	    else:
		if slice_start > -1:
		    if slice_end > slice_start + 1:
			result.append((slice_start, slice_end))
		    else:
			result.append((slice_start, last_obj))
		slice_start = idx
		slice_end = idx + 1
		last_obj = list
	else:
	    # list is a list of children of child
	    if slice_start > -1:
		if slice_end > slice_start + 1:
		    result.append((slice_start, slice_end))
		else:
		    result.append((slice_start, last_obj))
	    slice_start = -1
	    slice_end = -1
	    last_obj = None
	    result.append((idx, list))
    else:
	if slice_start > -1:
	    if slice_end > slice_start + 1:
		result.append((slice_start, slice_end))
	    else:
		result.append((slice_start, last_obj))
    return result



def tree_to_list(tree):
    result = []
    for idx, info in tree:
	idx = (idx,)
	for path, obj in info:
	    result.append((idx + path, obj))
    return result


def common_prefix(list):
    # Return the longest path that all items in LIST have in common.
    # LIST is in standard representation. Since that is a sorted list,
    # we just have to compare the first and last elements.
    if not list:
	return ()
    if len(list) == 1:
	return list[0][0]
    first = list[0][0]
    last = list[-1][0]
    if len(first) > len(last):
	length = len(last)
	first = first[:length]
    else:
	length = len(first)
	last = last[:length]
    for i in range(length):
	if first[i] != last[i]:
	    return first[:i]
    return first


