# 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
|