With this project, we will explore three different lessons involving binary search trees,
and then as the pièce de résistance, a single implementation that successfully
combines all three lessons.
We will start you with a basic implementation of a binary search tree to maintain a set of
distinct values, supporting insertions, deletions, and searches. The three desired
improvements are as follows:
● Split/Join: This complementary behaviors are used to split a single binary
search tree into two different search trees containing respectively values less
than or greater than a given parameter, or (re)combining two distinct binary
search trees that are known to be less than and greater than some key value.
● Rank-based queries: By having each node maintain the size of its subtree,
we can add support two additional queries, one that can tell you the rank of
any existing key (i.e., the smallest key has rank 1, the second smallest has
rank 2), and a second method that does the dual which is to find the key for a
given rank (e.g. what is the third smallest key?)
● Treap balancing: By assigning each node an additional randomly-generated
number, we can intentionally rebalance a search tree as a min-heap on those
additional values. While this doesn’t actually guarantee a balanced tree, it
does remove the risk of imbalanced trees being dependent on the user’s
insertion order.
In later sections, we will further describe each of these tasks, as well as the challenges
in simultaneously supporting them all in a single implementation.
Codebase
We are providing a zip file, BST.zip, that contains a variety of files. Most notably, we are
intentionally providing you with four different templates for your solution, because we did
not want any potential problems with your final integration to stop you from being
credited for success on each of the individual advancements.
● BST_join.py – this file should be modified to provide working
implementations of the split and join functions.
● BST_rank.py – this file should be modified to provide working
implementations of the rank-base methods keyToRank(key) and
rankToKey(r).
● BST_treap.py — this file should be modified to provide treap balancing. There
are no new methods, but the existing implementations of insert and delete
must be modified to ensure that the treap property is satisfied by the end of
each operation.
● BST.py — this file should be used for your final challenge of having a single
implementation that provides all of the new features. While we expect you
may borrow code from your other files to use in this file, there are some
significant modification that will be necessary to combine all features.
● driver.py — This is a driver that makes it easier for you to script a series of
heap operations as a text file, including the additional validation/visualization.
This is presumably the main file that you should execute for this project. More
details on this below.
● inputs/ — A few demonstration files to show input for the driver. While these
are some good test cases, you should surely be developing many further
tests of your own code (and I will be doing so for grading your code).
● cs1graphics.py — our visualization is based on a python graphics package
written here at SLU. Since non-standard package, I’m including it in this
distribution.
Most important is understanding the expected data representation for the quake heap,
and in particular how objects reference each other.
Binary Search Tree Representation
As a starting point, we are providing you with a working implementation of a generic
binary search tree that supports insertions, deletions, and containment queries. We
have chosen an abstraction of a TreeSet class which ensures that there are no
duplicate keys within the tree; our given implementation is designed so that nothing is
changed if it finds a “new” key already exists.
We have intentionally provided a very lightweight representation of a tree as a collection
of nodes, with each node having a reference to its key and to its left child and right child
(or None if no such child exists); additional _size field is added for the rank-based
queries, and a _treap field is added to store a randomly-generated priority value for
treaps. You are not to rename or add any other fields to the Node structures, as
our testing/visualization depend on these fields.
One noteworthy issue of our design is that a node does not have a reference to its
parent. While it may seem like a great convenience for nodes to have that information,
doing so adds unwanted complexity to a search tree implementation. It is not just that
nodes use extra memory, but once you commit to maintaining parent pointers than
every time you make a structural change to your tree, you have to make sure to
properly update those pointers in a consistent way. Later this semester, we will also
explore another advanced topic and see additional drawbacks of maintaining parent
pointers.
Of course, to implement most search tree functions, you often do need to navigate from
a node to its parent. Our solution to this is to temporarily build a list of nodes on the
path from a root to a particular node of the tree while originally walking down to that
node from the root. Since walking a path searching for a key is a basic part of almost all
search tree operations, we have provided a nonpublic method, _tracePath(key), that
performs the walk and which builds the list of nodes encountered on the search path.
You should review our own use of that utility in the original implementation of methods
look, insert, and delete.
Driver
We provide a driver that uses simple text commands to invoke various actions upon one
or more trees. You can either interact with the driver manually by typing those
commands, can have a text file prepared with commands and redirect that file to
standard input, or give the name of the text file as a command line option when starting
Python, in which case it will read input from that file rather than standard input.
The docstring at the top of the driver.py file provides an overview of all of the text-based
commands that are accepted. One key issue is that to support testing of join and split,
the driver need to be able to manage multiple trees. So all trees must be named with
unique strings when using the driver. For example, you might create two trees named A
and B and then each time you do an insertion you indicate which tree you wish to do
(commands such as “I A 25” vs “I B 25” to insert key 25 into a tree). Then a command
such as join can be used to combine A and B and a separating key, to form a new tree
C (command such as “J A 30 B C”
Another key aspect is that you are doing different implementations in files BST_join.py,
BST_rank.py, BST_treap.py, BST.py. A single run of the driver must use one particular
implementation for all trees and the driver requires that the very first command received
be a single string that is either TJ, TR, TT, TA (shorthand for tree join, tree rank, tree
treap, or tree all).
For convenience our driver also provide some basic validation testing and visualization
of search trees (using our cs1graphics module). Please see the documentation at the
beginning of the driver as well as the sample inputs provided in the codebase. Note well
that the internal validation is setup to only test the functionality expected by the above
TJ/TR/TT/TA indicators. For all four, it will verify that a tree satisfies the binary search
tree property, in that keys in a left subtree of a node must all have keys less than that of
the node. But if you are doing an implementation that supports the rank-based queries,
then it also validates whether your stored _size field for a node accurately accounts for
the size of the subtree rooted at that node, and similar if implementing a treap that the
treap property is satisfied. Note that the testing/visualization can only operate on a
single tree at a time (using the aforementioned names for the trees).
Advice: split/join
In the basic version, the join function is by far the easiest of the two. You are given a
new key and two trees, with the first tree known to have keys less than the given key,
and the second tree known to have keys greater than the given key. (Note: our software
does not check this condition, so it is up to the user to make sure not to join trees that
violate the condition.) So a join creates a new tree with a root node to hold the newest
key, and that node’s left and right children should be the roots of the two given trees.
This should run in constant time, as the new tree is essentially stealing the internal
structures of the two originals; for the sake of consistency in the object-oriented
framework, the roots of the two original trees should be reset to None so that those tree
instances can no longer be used to make modifications to the structure of the join.
The split function will take more care. The key is to examine the search path for the
given key (which may or may not be an element of the tree), and then to cut and paste
pieces back together depending on which portions are found to be less than or equal to
the key, and which are strictly greater. There are lots of possible scenarios to consider,
so be careful and do lots of testing.
Advice: rank-based query
The first task is to augment the basic tree in order to have each node maintain a _size
field that is the total number of nodes (including itself) in its subtree. For a basic search
tree, notice that when a (non-duplicative) insertion occurs, the newly created node
becomes a new descendent of all nodes on the search path, so all of their sizes must
be updated. Deletions are slightly more complicated, because of our replacement
strategy when deleting a node with two children. But once the location of the actual
node that is to be deleted from the tree structure is found, then all of its ancestors have
their subtree size reduced by one.
Once you are confident that your tree nodes are accurately maintaining their subtree
sizes, then you can approach the logic of the rankToKey and KeyToRank functions. In
both cases, as you traverse a search path, you can look at the sizes of the left and right
subtrees of each node and should be able to determine precisely how many total nodes
are left of (thus less than) a particular key and how many are right of (thus greater than)
a particular key. For example, if you are trying to find the key with rank 10 and the root
of the tree has six nodes in its left subtree, and thus has rank seven itself, than clearly
the node with rank 10 must be in the right subtree of the root (and in fact the third
smallest node in that subtree).
Advice: treaps
Our starter code for the Node constructor for treaps creates a floating-point field, _treap,
as a uniformly random number in range [0,1).
To perform an insertion on a treap, first allow the generic version of insert to do its job in
adding a new node in the proper search tree location. The only challenge once that is
done is that the new node may have a treap value that is less than its parent, and in that
case you must perform a tree rotation to make that node become the parent of its
current parent (while making sure to properly keep the rest of the search tree valid).
This “upheap bubbling” must continue until the new node either reaches a location in
which it has a parent with lesser treap value, or until it becomes the root of the tree.
For deletions, notice that deleting a leaf will not create any treap violation because no
new child/parent relationships are formed. Similarly, our approach for deleting a node
with one child essentially cuts that child out of the path, but its parent was already
known to have smaller treap value than its surviving child, and so the treap property
remains intact. The only challenging case is when a node with two children is removed.
Our existing code base chooses to locate the successor of the node to be deleted and
than effectively “moves” that entry to the location in the tree of the element that was
supposed to be deleted, and then remedies the removal of the node below. However,
to properly implement a treap, the “moved” element’s treap value should also move and
the problem is that it now might be in an illegal location.
As an example (taken from input/basicTestTreap.txt), consider the state of the following
treap just before we delete key 45.
Given that the node with 45 has two, our deletion implementation finds the successor
(that storing key 50), and effectively “moves” the 50 element to where 45 is currently,
and then deletes the node that had been holding 50. Deleting that other node is quite
easy, but the element with 50 had treap value 0.584 and that should stay with the
element yet we cannot leave that treap value where 45 used to be because that is
larger than the treap values of its children (namely the 0.268 held by 37 and 0.185 held
by 100). Therefore we must “bubble” the node downward, and in particular we want to
promote the node with value 100 because it has the smaller of the two children’s treap
values and thus is allowed to be the parent of 37. So we “rotate” the edge between the
new 50 and 100 so that 100 becomes the right child of 35, 50 becomes the LEFT child
of 100. Note that the subtree rooted at 70 gets moved in this transition, becoming the
new right child of the node storing 50 (notice it is in the search tree location for keys that
are smaller than 100 but greater than 50).
However, this process continues, as the new location of 50 still has a treap value 0.584
that is larger than both of its new children (the 0.268 held by 37 and the 0.573 held by
70). In this case, another rotation must take place, this time with the left child 37 that
has the smaller treap value. If all goes well in this example, you will eventually reach
the following treap.
Advice: combining all features
Even more care will be needed when you try to combine the above functionality into a
single implementation.
● For example, while it was great to implement split and join, if you are also
trying to support the rank-based queries, you must make sure that you
accurately maintained all subtree sizes while doing the reconstruction
involved in a split or join operation.
● For a treap, even after the standard form of an insertion or deletion and the
change that causes to subtrees on the path, any further rotations that are
used to restructure the tree will impact the size of subtrees along the path.
So it is necessary to recompute all the subtree sizes for impacted nodes, but
you still want this implementation to run in time proportional to the path
height, so you can’t actually afford to traverse all of those subtrees; you must
infer the new sizes only for those nodes who’s children were changed.
● It turns out that combining ”split” with treaps is actually quite trivial because
if you look at the natural algorithm for how you glued pieces of the split path
back together, you should find that things that used to be below a node due to
a treap value will remain below such a node even after you put the pieces
back together. So this is good news in that you shouldn’t have to update the
split code to maintain the treap property.
But unfortunately, the join function does become more complicated with
treaps. In the generic version, a join was easy because you just make the
new key the root and repurpose the existing two trees to form the left and
right subtrees. But for treaps, that newly created root node has a randomly
selected treap value and that value might not compare well to those of its
children. In particular, if it is larger than either of its children, you must
preform the downward bubbling process (akin to the one used in the special
case of deletion).
We hope that you will be able to use much of the code from your earlier
implementations in the final BST.py implementation, but some significant refactoring will
be warranted. So this is why we are having you still submit (hopefully working) versions
of those other three implementations to get credit for your successes, and to make this
final combined implementation its own file.
Examples and Illustrations
Our codebase includes an inputs/ folder that provides several interesting test cases that
can be used with our driver. Rather than clutter this page with lots and lots of
discussion and illustrations, we will provide additional illustrations as a separate
page.
Submit your four py files to the program02 folder in your class git repo. You should also
submit a brief readme.txt file providing a summary of your work. Most notably, please
give your own assessment as to what you believe to be your level of success for each
of the four challenges.
BST/BST_rank.py
from random import random # for use as treap priority
class TreeSet:
“””
A set of distinct values from a totally ordered domain.
“””
#########################################################
class _Node:
“””Inner class to represent one node of a tree.”””
def __init__(self, key, left=None, right=None):
self._key = key
self._left = left
self._right = right
self._size = 1 # for later use
def getKey(self):
return self._key
def setKey(self, k):
self._key = k
def getLeft(self):
return self._left
def setLeft(self, left):
self._left = left
def getRight(self):
return self._right
def setRight(self, right):
self._right = right
def __str__(self):
“””String representation for visualization.
Can include newlines if desired.
“””
return(f'{self._key}\n{self._size}’)
#########################################################
def __init__(self):
self._root = None
def _tracePath(self, key):
“””Return list of nodes visited during search for key.”””
path = []
walk = self._root
while walk:
path.append(walk)
if key == walk.getKey():
break
elif key < walk.getKey():
walk = walk.getLeft()
else:
walk = walk.getRight()
return path
def look(self, key):
"""Return True if key exists in set, else False."""
path = self._tracePath(key)
return path and path[-1].getKey() == key
def insert(self, key):
"""Insert key into set (if not already there).
Return True if new, False if existing.
"""
if self._root is None:
self._root = TreeSet._Node(key)
return True
else:
path = self._tracePath(key)
last = path[-1]
if key != last.getKey():
# element is new
newNode = TreeSet._Node(key)
if key < last.getKey():
last.setLeft(newNode)
else:
last.setRight(newNode)
return True
else:
return False
def delete(self, key):
"""Delete key from set, if it exists.
Return True if deleted, False if not found.
"""
path = self._tracePath(key)
if path and path[-1].getKey() == key:
# found a match to delete
last = path[-1]
if last.getRight() and last.getLeft():
# there are two children. So rather than delete this actual node
# let's find a replacement key as the smallest thing in right subtree
walk = last.getRight()
while walk:
path.append(walk)
walk = walk.getLeft()
last.setKey(path[-1].getKey()) # higher node steals key from lower node
last = path[-1] # and now our task is to delete the lower node
# goal is now to delete "last" node, which has at most one child
# replacement is the one child, or None if zero children
if last.getLeft() is None:
replacement = last.getRight() # might also be None
else:
replacement = last.getLeft()
if len(path) == 1:
# we are deleting the tree root
self._root = replacement
else:
# we are deleting a nonroot
parent = path[-2]
if parent.getLeft() is last:
parent.setLeft(replacement)
else:
parent.setRight(replacement)
return True
else:
return False
def keyToRank(self, key):
"""Return the rank of the existing key.
Rank is defined akin to Python indexing, with the smallest element
having rank 0, the second smallest having rank 1, and so forth.
Return -1 if the key is not found.
"""
pass
def rankToKey(self, r):
"""Return the key having rank r amongst the current set.
Raise ValueError if it is not that 0 <= r < size of set.
"""
raise ValueError('invalid rank ' + str(r))
BST/BST.py
from random import random # for use as treap priority
class TreeSet:
"""
A set of distinct values from a totally ordered domain.
"""
#########################################################
class _Node:
"""Inner class to represent one node of a tree."""
def __init__(self, key, left=None, right=None):
self._key = key
self._left = left
self._right = right
self._size = 1 # for later use
self._treap = random() # for later use
def getKey(self):
return self._key
def setKey(self, k):
self._key = k
def getLeft(self):
return self._left
def setLeft(self, left):
self._left = left
def getRight(self):
return self._right
def setRight(self, right):
self._right = right
def __str__(self):
"""String representation for visualization.
Can include newlines if desired.
"""
return(f'{self._key}\n{self._size}\n{self._treap:0.3f}')
#########################################################
def __init__(self):
self._root = None
def _tracePath(self, key):
"""Return list of nodes visited during search for key."""
path = []
walk = self._root
while walk:
path.append(walk)
if key == walk.getKey():
break
elif key < walk.getKey():
walk = walk.getLeft()
else:
walk = walk.getRight()
return path
def look(self, key):
"""Return True if key exists in set, else False."""
path = self._tracePath(key)
return path and path[-1].getKey() == key
def insert(self, key):
"""Insert key into set (if not already there).
Return True if new, False if existing.
"""
if self._root is None:
self._root = TreeSet._Node(key)
return True
else:
path = self._tracePath(key)
last = path[-1]
if key != last.getKey():
# element is new
newNode = TreeSet._Node(key)
if key < last.getKey():
last.setLeft(newNode)
else:
last.setRight(newNode)
return True
else:
return False
def delete(self, key):
"""Delete key from set, if it exists.
Return True if deleted, False if not found.
"""
path = self._tracePath(key)
if path and path[-1].getKey() == key:
# found a match to delete
last = path[-1]
if last.getRight() and last.getLeft():
# there are two children. So rather than delete this actual node
# let's find a replacement key as the smallest thing in right subtree
walk = last.getRight()
while walk:
path.append(walk)
walk = walk.getLeft()
last.setKey(path[-1].getKey()) # higher node steals key from lower node
last = path[-1] # and now our task is to delete the lower node
# goal is now to delete "last" node, which has at most one child
# replacement is the one child, or None if zero children
if last.getLeft() is None:
replacement = last.getRight() # might also be None
else:
replacement = last.getLeft()
# replacement is the one child, or None if zero children
if len(path) == 1:
# we are deleting the tree root
self._root = replacement
else:
# we are deleting a nonroot
parent = path[-2]
if parent.getLeft() is last:
parent.setLeft(replacement)
else:
parent.setRight(replacement)
return True
else:
return False
def keyToRank(self, key):
"""Return the rank of the existing key.
Rank is defined akin to Python indexing, with the smallest element
having rank 0, the second smallest having rank 1, and so forth.
Return -1 if the key is not found.
"""
pass
def rankToKey(self, r):
"""Return the key having rank r amongst the current set.
Raise ValueError if it is not that 0 <= r < size of set.
"""
raise ValueError('invalid rank ' + str(r))
def split(self, k):
"""Return two new TreeSet instances.
The first should contain all elements of this set that are less than or
equal to k, and the second all those strictly greater than k (though one or
both of those could be an empty TreeSet instance).
As a side effect of this call, the current tree should be emptied.
"""
left = TreeSet() # initially empty
right = TreeSet() # initially empty
# more work here...
return left,right
# The following is a static method as it is not invoked as a method of a tree
@staticmethod
def join(t1, k, t2):
"""
Return a new TreeSet instance that joins existing t1 and t2 with new key k.
The caller is responsible for ensuring that all elements of
TreeSet t1 are strictly less than k, and that all elements of
TreeSet t2 are strictly greater than k.
As a side effect both t1 and t2 should be emptied.
"""
pass
BST/cs1graphics.py
"""cs1graphics.py
Copyright 2008-2014, David Letscher, Michael H. Goldwasser, Christopher Porter
Go to www.cs1graphics.org for more information.
This is Version 1.2 release (23 July 2014)
"""
# 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 3 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, see .
# If you are interested in doing further development of cs1graphics,
# please contact the authors to receive the Developer’s Guide.
# Configuration Options:
# ———————-
# By default, cs1graphics uses true multi-threading. However, the
# default Python/Tk implementation shipped on many versions of Apple’s
# OSX operating system does not allow for such support. The following
# flag should be changed to False to switch to a slightly more limited
# model of threading. This behavior can also be triggered
# programmatically by calling configureNativeThreading(False) prior to
# issuing any graphics commands.
_nativeThreading = False
# By default, cs1graphics uses the common “computer science”
# coordinate system, with the origin in the top-left corner of a
# window, and with the y-axis oriented so that positive values are
# below the origin. To get a traditional “mathematics” coordinate
# system, with the origin in the bottom-left and the positive y-axis
# oriented above the origin, the following flag can be changed to
# True. This behavior can also be triggered programmatically by
# calling configureMathMode(True) prior to issuing any graphics
# commands.
_mathMode = False
# cs1graphics allows for a layer to be recursively nested within
# itself, for some cool effects. The rendering of such recursion is
# artificially capped with the following recursive limit. This limit
# may also be changed programmatically with the
# configureSetRecursionLimit function.
_RECURSIVE_LIMIT = 10
# The following dictionary of flags should only be used by developers
# to adjust the level of verbosity when debugging various aspects of
# the system.
_DEBUG = {
‘wait’ : 0,
‘mainLoop’ : 0,
‘processEvents’ : 0,
‘Events’ : 0,
‘Tkinter’ : 0,
‘Front’ : 0,
‘Middle’ : 0,
‘RenderedH’ : 0,
‘UpdateManager’ : 0,
‘processCommands’ : 0,
}
_dashMultiplier = 2 # oddity about whether pattern should be (a,b) or (a,b,a,b)
import copy as _copy
import math as _math
import random as _random
import time as _time
import threading as _threading
import atexit as _atexit
import os as _os
import sys as _sys
import traceback as _traceback
from array import array as _array
# change in module names for Python 2 vs 3
try:
import Queue as _Queue
except ImportError:
import queue as _Queue # Python 3
try:
import thread as _thread
except ImportError:
import _thread as _thread # Python 3
try:
import Tkinter as _Tkinter
except ImportError:
try:
import tkinter as _Tkinter # Python 3
except ImportError:
raise ImportError(‘cs1graphics requires that Tkinter be installed’)
try:
import Image as _Image
import ImageDraw as _ImageDraw
import ImageTk as _ImageTk
_pilAvailable = True
except ImportError:
_pilAvailable = False
# Library
_tkroot = None
_ourRandom = _random.Random()
_ourRandom.seed(1234) # initialize the random seed so that behaviors are reproducible
# support for Python 2.x/3.x.
# We want to use isinstance(foo, basestring) in either case
try:
unicode
except NameError:
basestring = unicode = str
# Global Configuration Controls
def configureNativeThreading(flag=False):
“””Configures cs1graphics to run in native multi-threaded mode when flag is True.
By default, the library uses a multi-threaded model in which case
all rendering is managed by a secondary thread, and EventHandlers
are immediately activated once registered without blocking the
primary thread.
However, on systems that do not support accessing Tkinter from a
secondary thread, the model can be changed to be single-threaded,
with all rendering in the primary thread and EventHandlers
activated only when the end of the main thread is reached, or an
explicit (blocking) call to startEventHandling() is made.
Note: This command must be executed prior to the use of any core
library functionality.
Note: As an alternative, your cs1graphics installation can be
configured with the default mode set using the variable
_nativeThread in the preamble of file cs1graphics.py.
“””
if _graphicsManager._state != ‘Initial’:
raise GraphicsError(‘configuration must occur prior to other use of the library’)
global _nativeThreading
_nativeThreading = True
def configureMathMode(flag=True):
“””Forces cs1graphics to use standard math coordinate system when flag is True.
By default, cs1graphics uses a standard computer graphics
coordinate system with the origin at the top-left and the positive
y-axis oriented downward.
If this function is invoked, it causes canvases to use a standard
mathematics coordinate system with the origin at bottom-left and
the positive y-axis oriented upward. In math mode, a positive
rotation is conventionally counterclockwise rather than clockwise.
NOTE: This command must be executed prior to the use of any core
library functionality.
Note: As an alternative, your cs1graphics installation can be
configured with the default coordinate system set using the
variable _mathMode in the preamble of file cs1graphics.py.
“””
if _graphicsManager._state != ‘Initial’:
raise GraphicsError(‘configuration must occur prior to other use of the library’)
global _mathMode
_mathMode = flag
def configureSetRecursionLimit(limit):
“””Changes the limit on recursion for drawable inclusion.
In cases such as when adding a layer to itself, the drawing
process is intentionally capped with some maximum recursive depth
to avoid an infinite recursion. By default, that limit is 10.
This function allows that to be changed.
“””
if _graphicsManager._state != ‘Initial’:
raise GraphicsError(‘configuration must occur prior to other use of the library’)
if not isinstance(limit, int):
raise TypeError(‘limit should be an integer’)
if limit < 1:
raise ValueError('limit must be positive')
global _RECURSIVE_LIMIT
_RECURSIVE_LIMIT = limit
class GraphicsError(Exception):
def __init__(self, message, recoverable=False):
super(GraphicsError, self).__init__()
self._recoverable = recoverable
# Data structures
# special purpose comparator for chains, since Python3 no longer allows for us to use default < for chain tuples that include a class instance.
def _chainCompare(a, b):
return _chainCompareRecurse(a, b, 0)
def _chainCompareRecurse(a, b, k):
"""Compare implicit slices a[k:] and b[k:]"""
if len(a) == k:
return len(b) > k
elif len(b) == k:
return False
elif a[k][0] < b[k][0]:
return True
elif b[k][0] < a[k][0]:
return False
elif a[k][1] == b[k][1]:
return _chainCompareRecurse(a, b, k+1)
else:
# arbitrary tie-breaker for our model of chains with multiple inheritance
return str(a[k][1]) < str(b[k][1])
class _OrderedMap:
"""Implements an ordered map.
Although we do not formally require the keys to be hashable, the
expectation is that they should not be mutated.
By default, ordering is based on < operator, but the user
can provide a non-standard boolean function for comparing keys.
This implementation is based upon an underlying treap.
"""
def _less(a, b):
"""Generic version of comparison function."""
return a < b
_less = staticmethod(_less)
def __init__(self, less=None):
"""Create an empty map.
less is a boolean function with callingsignature less(keyA, keyB)
that returns True if keyA is strictly less than keyB.
If not sent, the default < operator is used.
"""
self._root = None
self._size = 0
if less is not None:
self._less = less
def __len__(self):
"""Return the size of the map."""
return self._size
def _trace(self, key):
"""Walk path looking for given key.
Return the node that has the key, if any.
Otherwise return the last true node visited.
In case of an empty map, None is returned.
"""
if len(self) > 0:
walk = self._root
while walk is not None and \
(self._less(key, walk.key) or self._less(walk.key, key)):
# no match thus far
trail = walk
if self._less(key, walk.key):
walk = walk.left
else:
walk = walk.right
if walk is not None:
result = walk
else:
result = trail
else:
result = None
return result
def __delitem__(self, key):
“””Remove the entry assoicated with the key.
KeyError results if key does not exist.
“””
temp = self.find(key)
if temp is None:
raise KeyError(repr(key))
self.remove(temp)
def __getitem__(self, key):
“””Return the value associated with the key.
KeyError results if key does not exist.
“””
temp = self.find(key)
if temp is None:
raise KeyError(repr(key))
else:
return temp.value()
def __setitem__(self, key, value):
“””Associate key to value.
If key exists, old value is overwritten with new.
If key does not exist, it is added to the map.
“””
self.insert(key, value) # ignore return value
def find(self, key):
“””Return an iterator to the key’s position, if found.
None is returned if key not found.
“””
walk = self._trace(key)
if walk is not None and not \
(self._less(key, walk.key) or self._less(walk.key, key)):
return _OrderedMap.iterator(walk)
else:
return None
def __contains__(self, key):
“””Return True if key in the map.”””
return self.find(key) is not None
def first(self):
“””Return iterator to the first element of the map.
None is returned if map is empty.
“””
if len(self) > 0:
return _OrderedMap.iterator(self._root.subtreeMin())
else:
return None
def last(self):
“””Return iterator to the last element of the map.
None is returned if map is empty.
“””
if len(self) > 0:
return _OrderedMap.iterator(self._root.subtreeMax())
else:
return None
def __iter__(self):
“””Return generator for (key,value) pairs.”””
walk = self.first()
while walk is not None:
yield (walk.key(), walk.value())
walk = walk.next()
def closestBefore(self, key, strict=True):
“””Return iterator to position at or before the key.
With strict=True (the default), the search looks for an item
that has a key strictly smaller than the given one.
With strict=False, it will return an exact match if possible, and
otherwise the closest before.
Will return None in the case that no earlier key is found.
“””
walk = self._trace(key)
if walk is None:
return None
if self._less(walk.key, key):
# this is strictly smaller than key, so it must be it
return _OrderedMap.iterator(walk)
elif not (strict or self._less(key, walk.key)):
# use the exact match
return _OrderedMap.iterator(walk)
elif walk.left is not None:
# found an exact match, and it has lesser children
return _OrderedMap.iterator(walk.left.subtreeMax())
else:
# start walking upward
while walk is not None and not self._less(walk.key, key):
walk = walk.parent
if walk is not None:
return _OrderedMap.iterator(walk)
else:
return None
def closestAfter(self, key, strict=True):
“””Return iterator to position at or after the key.
With strict=True (the default), the search looks for an item
that has a key strictly larger than the given one.
With strict=False, it will return an exact match if possible, and
otherwise the closest after.
Will return None in the case that no later key is found.
“””
walk = self._trace(key)
if self._less(key, walk.key):
# this is strictly larger than key, so it must be it
return _OrderedMap.iterator(walk)
elif not (strict or self._less(walk.key, key)):
# use the exact match
return _OrderedMap.iterator(walk)
elif walk.right is not None:
# found an exact match, and it has greater children
return _OrderedMap.iterator(walk.right.subtreeMin())
else:
# start walking upward
while walk is not None and not self._less(key, walk.key):
walk = walk.parent
if walk is not None:
return _OrderedMap.iterator(walk)
else:
return None
def insert(self, key, value=None):
“””Associate key to value.
If key exists, old value is overwritten with new.
If key does not exist, it is added to the map.
Return an iterator to the key’s position.
“””
walk = self._trace(key)
if walk is None:
self._size += 1
self._root = _OrderedMap._node(key, value)
return _OrderedMap.iterator(self._root)
else:
if self._less(key, walk.key):
walk.left = _OrderedMap._node(key, value, walk)
walk = walk.left
self._insertRebalance(walk)
self._size += 1
elif self._less(walk.key, key):
walk.right = _OrderedMap._node(key, value, walk)
walk = walk.right
self._insertRebalance(walk)
self._size += 1
else:
# key exists; overwrite old value
walk.val = value
return _OrderedMap.iterator(walk)
def _insertRebalance(self, walk):
while walk.parent is not None and walk.priority < walk.parent.priority:
self._rotateUp(walk)
def remove(self, posn):
"""Remove the item at the given iterator."""
if not isinstance(posn, self.iterator):
raise TypeError("Must provide valid iterator for remove")
self._size -= 1
walk = posn._nd
if walk.left is None or walk.right is None:
self._easyDelete(walk)
else:
# use predecessor as sub for the current node
sub = walk.left.subtreeMax()
# fix pointer from above
if self._root is walk:
self._root = sub
elif walk is walk.parent.left:
walk.parent.left = sub
else:
walk.parent.right = sub
# relocate sub and remove walk
if sub is not walk.left:
# clean up below
sub.parent.right = sub.left
if sub.left is not None:
sub.left.parent = sub.parent
# sub takes over left child of walk
sub.left = walk.left
walk.left.parent = sub
# sub takes over right child of walk
sub.right = walk.right
walk.right.parent = sub
# sub gets new parent
sub.parent = walk.parent
# restore heap property from sub downward
downward = True
while downward:
child = sub.left
if sub.right is not None and (child is None or sub.right.priority < child.priority):
child = sub.right
if child is not None and child.priority < sub.priority:
self._rotateUp(child)
else:
downward = False
def _rotateUp(self, walk):
"""Rotate node walk up one level.
Assumes that walk is not the root (but parent may be)
"""
parent = walk.parent
grand = parent.parent
walk.parent = grand
parent.parent = walk
if parent.left is walk:
parent.left = walk.right
if walk.right is not None:
walk.right.parent = parent
walk.right = parent
else:
parent.right = walk.left
if walk.left is not None:
walk.left.parent = parent
walk.left = parent
if grand is None:
self._root = walk
else:
if grand.left is parent:
grand.left = walk
else:
grand.right = walk
def _easyDelete(self, walk):
"""Assumes that walk is a node that has at most one child."""
if walk.left is None:
child = walk.right
else:
child = walk.left
if child is not None:
child.parent = walk.parent
if walk.parent is None:
self._root = child
else:
if walk is walk.parent.left:
walk.parent.left = child
else:
walk.parent.right = child
walk.parent = walk.left = walk.right = None # disconnect, to be safe
###################################################
######### nested class _OrderedMap._node ##########
class _node:
__slots__ = ('key', 'val', 'parent', 'left', 'right', 'priority') # optimization
"""Simple struct to represent node of the treap"""
def __init__(self, key, value=None, parent = None, leftChild = None, rightChild = None):
self.key = key
self.val = value
self.parent = parent
self.left = leftChild
self.right = rightChild
self.priority = _ourRandom.random()
def subtreeMin(self):
"""Return leftmost node of subtree."""
walk = self
while walk.left is not None:
walk = walk.left
return walk
def subtreeMax(self):
"""Return rightmost node of subtree."""
walk = self
while walk.right is not None:
walk = walk.right
return walk
def predecessor(self):
"""Returns node of predecessor. Returns None if this is minimum."""
if self.left is not None:
return self.left.subtreeMax()
else:
walk = self
while walk.parent is not None and walk.parent.left is walk:
walk = walk.parent
return walk.parent
def successor(self):
"""Returns node of successor. Returns None if this is maximum."""
if self.right is not None:
return self.right.subtreeMin()
else:
walk = self
while walk.parent is not None and walk.parent.right is walk:
walk = walk.parent
return walk.parent
######### end of class _OrderedMap._node ##########
######################################################
######### nested class _OrderedMap.iterator ##########
class iterator:
"""Encapsulation of a position in the map"""
def __init__(self, node):
self._nd = node
def __repr__(self):
return "Iterator[key="+repr(self.key())+' value='+repr(self.value())+"]"
def __eq__(self, other):
"""Return True if iterators represent the same position."""
return self._nd == other._nd
def __ne__(self, other):
"""Return True if iterators do not represent the same position."""
return not self._nd == other._nd
def key(self):
"""Return key of element at this position."""
return self._nd.key
def value(self):
"""Return value of element at this position."""
return self._nd.val
def prev(self):
"""Return iterator to the previous element of the map.
Return None if there is no predecessor."""
other = self._nd.predecessor()
if other is not None:
return _OrderedMap.iterator(other)
else:
return None
def next(self):
"""Return iterator to the next element of the map.
Return None if there is no successor."""
other = self._nd.successor()
if other is not None:
return _OrderedMap.iterator(other)
else:
return None
######### end of class _OrderedMap.iterator ##########
class _Hierarchy:
"""Used to maintain minimal information to track which objects are
currently contained (directly or indirectly) on a Canvas, and to
track the parent/child relationships between those objects.
Technically, each object is noted as an (object,cls) pair where
cls is the class whose _draw was called. Typically, this will be
the object's class, but could be a parent class for some.
Furthermore, each object typically has only one such entry in the
hierarchy, but with multiple inheritence (e.g. Button), there
might be three or more different entries, one due to the original
Button._draw call, but two subsequent due to the underlying
Rectangle._draw and Text._draw calls.
"""
def __init__(self):
self._objects = {} # map from obj to set of all (obj,cls) pairs
self._relationships = {} # map from (obj.cls) pair to [parentSet, childrenDict, maxSerial]
# where parentSet is set of (obj,cls) tuples,
# childrenDict is dictionary mapping from (child,cls) -> serialFloat,
# and maxSerial is an upper bound on the serials currently in use
def __contains__(self, drawable):
“””Determines whether the drawable is contained in the current hierarchy.”””
return drawable in self._objects
def newCanvas(self, canvas):
“””Adds canvas as new top-level container in the hierarchy.”””
self._objects[canvas] = set()
self._objects[canvas].add( (canvas,Canvas) )
self._relationships[ (canvas, Canvas) ] = [set(), {}, 0]
def addLink(self, parentTuple, childTuple):
“””Connect child to parent.
parentTuple and childTuple should both be of form (object,cls)
and that parentTuple is already in this hierarchy.
“””
self._objects.setdefault(childTuple[0], set()).add(childTuple)
relate = self._relationships[parentTuple]
relate[2] += 1 # update serial
relate[1][childTuple] = relate[2] # new child with updated serial
self._relationships.setdefault(childTuple, [set(), {}, 0])[0].add(parentTuple)
def removeLink(self, parentTuple, childTuple):
“””Removes the child from the parent (including the cleansing of any descendents).”””
# remove child from parent’s list of children
parentsChildren = self._relationships[parentTuple][1]
del self._relationships[parentTuple][1][childTuple]
# remove parent from child’s list of parents
childsParents = self._relationships[childTuple][0]
childsParents.remove(parentTuple)
if not childsParents: # empty set
self._recursiveRemove(childTuple)
def findChildTuple(self, parentTuple, child):
“””For when we know the child, but not the child’s appropriate “class” tag
(because _draw was not necessarily from that class)
“””
for k in self._relationships[parentTuple][1].keys():
if k[0] == child:
return k
def getSerial(self, parentTuple, childTuple):
return self._relationships[parentTuple][1][childTuple]
def _recursiveRemove(self, objTuple):
# remove association from self._objects
objSet = self._objects[objTuple[0]]
objSet.remove(objTuple)
if not objSet: # empty set
del self._objects[objTuple[0]]
# remove association from self._relationships
entry = self._relationships.pop(objTuple)
children = entry[1]
for c in children.keys():
childsParents = self._relationships[c][0]
childsParents.remove(objTuple)
if not childsParents: # no more parents
self._recursiveRemove(c)
def reviseChildren(self, drawTuple, childSequence):
“””Compares the newSequence of drawable’s children to sequence currently on record.
Returns list of (child,serial) pairs for those children that require updated serial numbers.
“””
raise NotImplementedError(‘reviseChildren not yet written’) # TODO
def computeUpwardChains(self, drawable, counts = None):
if counts is None:
counts = {}
if isinstance(drawable, tuple):
tuples = [ drawable ]
else:
tuples = self._objects[drawable]
results = []
for t in tuples:
self._computeUpwardChainsRecurse(results,t,counts)
if _DEBUG[‘Middle’] >= 2:
print(‘ComputeUpwardChains(‘+str(drawable)+’,’+str(counts)+’) returning:’)
for c in results:
print(‘ ‘+str(tuple(c)))
return results
def _computeUpwardChainsRecurse(self, results, drawTuple, count):
prevCount = count.get(drawTuple,0)
if prevCount < _RECURSIVE_LIMIT:
parents = self._relationships[drawTuple][0]
if parents:
count[drawTuple] = 1 + prevCount
for p in parents:
oldSize = len(results)
self._computeUpwardChainsRecurse(results, p, count)
for k in range(oldSize, len(results)):
results[k].append(drawTuple)
count[drawTuple] -= 1 # decrement count, to avoid side effects
if count[drawTuple] == 0:
del count[drawTuple]
else:
results.append( [drawTuple] ) # "drawTuple" must represent a canvas
def computeDownwardChains(self, drawTuple):
"""Computes all downward chians from the given starting point.
Returns pre-order list of (chain, countDict) pairs
Allows for cycles in chain, up to the globally determined recursive limit.
"""
results = []
self._computeDownwardChainsRecurse(results, drawTuple, {})
if _DEBUG['Middle'] >= 2:
print(‘ComputeDownwardChains(‘+str(drawTuple)+’) returning:’)
for c in results:
print(‘ ‘+str(tuple(c)))
return results
def _computeDownwardChainsRecurse(self, results, drawTuple, count):
“””
Returns a pre-order list of all downward chains (including all prefixes).
Furthermore this version is given a dictionary of counts, mapping from
drawTuple -> frequency that is presumed to have occurred
outside the context of this call (zero if not present).
Semantic is that there is a total cap on the number of
occurrences of any given element, including the previous
counts.
Note: this function must guarantee that count is restored to
its previous state by the end of a given call so that there
are no lasting side effect (except perhaps by having non-keys
end up as keys with a count of zero).
“””
prevCount = count.get(drawTuple, 0)
count[drawTuple] = 1 + prevCount
results.append( ([drawTuple], dict(count)) )
for child in self._relationships[drawTuple][1].keys():
if count.get(child, 0) < _RECURSIVE_LIMIT:
oldSize = len(results)
self._computeDownwardChainsRecurse(results, child, count)
for k in range(oldSize, len(results)):
results[k][0].insert(0, drawTuple)
count[drawTuple] -= 1 # decrement count to avoid lasting effect
if count[drawTuple] == 0:
del count[drawTuple]
class _RenderedHierarchy:
class Node:
__slots__ = ('_chain', '_children', '_sortedChildren', '_prev', '_next', '_parent', # optimization
'_depth', '_transformation', '_cumulativeTransformation', '_renderedDrawable')
def __init__(self):
self._chain = None
self._children = dict()
self._sortedChildren = _OrderedMap()
self._prev = None
self._next = None
self._parent = None
self._depth = None
self._transformation = _Transformation()
self._cumulativeTransformation = _Transformation()
self._renderedDrawable = None
def __init__(self):
self._root = self.Node()
self._first = None
self._last = None
self._nodeLookup = dict()
self._nodeLookup[tuple()] = self._root
def add(self, chain, depth, transformation, renderedDrawable):
"""Add a new chain to the hierarchy and return the new node.
The parent chain must be present.
"""
parentChain = chain[:-1]
parentNode = self._nodeLookup[parentChain]
# Create the new node
newNode = self.Node()
newNode._chain = chain
newNode._depth = depth
newNode._transformation = transformation
if parentChain and parentChain[-1][0] is chain[-1][0] and parentChain[-1][1] is not chain[-1][1]:
# do not reapply local transform if parent call to _draw is reflected in the chain
# (recognized by same object ID, but with different class; this allows recursive layer)
newNode._cumulativeTransformation = parentNode._cumulativeTransformation * _Transformation()
else:
# standard case
newNode._cumulativeTransformation = parentNode._cumulativeTransformation * transformation
newNode._renderedDrawable = renderedDrawable
newNode._parent = parentNode
# Link new node into structure
self._nodeLookup[chain] = newNode
parentNode._children[chain[-1]] = newNode
parentNode._sortedChildren[depth] = newNode
self._addThreads(newNode, parentNode)
return newNode
def remove(self, chain):
"""Remove a node and all of its children.
A list of RenderedDrawables to be deleted is returned.
"""
node = self._nodeLookup[chain]
parentChain = chain[:-1]
parentNode = self._nodeLookup[parentChain]
# Remove parent references and threads
parentNode._children.pop(chain[-1])
del parentNode._sortedChildren[node._depth]
self._removeThreads(node, parentNode)
# Find all of the RenderedDrawables to delete
deleted = list()
queue = [node]
while len(queue) > 0:
n = queue.pop()
self._nodeLookup.pop(n._chain)
if n._renderedDrawable is not None:
deleted.append(n._renderedDrawable)
queue.extend(n._children.values())
return deleted
def prev(self, node):
“””Find the previous leaf node.
Precondition: node is a leaf node
If there is no previous node it returns None
“””
return node._prev
def next(self, node):
“””Find the next leaf node.
Precondition: node is a leaf node
If there is no next node it returns None
“””
return node._next
def hasChain(self, chain):
return chain in self._nodeLookup
def getDepth(self, chain):
return self._nodeLookup[chain]._depth
def changeDepth(self, chain, newDepth):
node = self._nodeLookup[chain]
oldDepth = node._depth
if _DEBUG[‘RenderedH’] >= 1.5: print(‘change depth of ‘ + str(chain) + ‘ from ‘ + str(oldDepth) + ‘ to ‘ + str(newDepth))
node._depth = newDepth
parent = node._parent
handle = parent._sortedChildren.find(oldDepth)
prevSib = handle.prev()
nextSib = handle.next()
del parent._sortedChildren[oldDepth]
parent._sortedChildren[newDepth] = node
if (prevSib is not None and newDepth < prevSib.key()) or \
(nextSib is not None and newDepth > nextSib.key()):
# must re-thread relative to siblings
if _DEBUG[‘RenderedH’] >= 2.5:
for (k,v) in iter(parent._sortedChildren):
print( ‘ child: ‘ + str(k) + ‘ ‘ + str(v))
self._removeThreads(node, parent) # detach from old location
self._addThreads(node, parent) # reattach in new location
return (self.first(node), self.last(node)) # Return range of things that need to be changed
else:
return (None, None)
def changeTransform(self, chain, newTransform):
node = self._nodeLookup[chain]
node._transformation = newTransform
if len(chain) > 1 and chain[-2][0] is chain[-1][0] and chain[-2][1] is not chain[-1][1]:
# do not reapply change if parent call to _draw is reflected in the chain
node._cumulativeTransformation = node._parent._cumulativeTransformation * _Transformation()
else:
node._cumulativeTransformation = node._parent._cumulativeTransformation * newTransform
# Propogate to children
toFix = list(node._children.values())
while len(toFix) > 0:
n = toFix.pop()
childTuple = n._chain[-1]
parentTuple = n._parent._chain[-1]
if childTuple[0] is parentTuple[0] and childTuple[1] is not parentTuple[1]:
# do not reapply change if parent call to _draw is reflected in the chain
n._cumulativeTransformation = n._parent._cumulativeTransformation * _Transformation()
else:
n._cumulativeTransformation = n._parent._cumulativeTransformation * n._transformation
toFix.extend(n._children.values())
return (self.first(node), self.last(node)) # Return range of things that need to be changed
def _addThreads(self, newNode, parentNode):
“””Adjust the threads to incorporate a recently added node/subtree.”””
# Find extremes in current threading (might be subtree)
first = self.first(newNode)
last = self.last(newNode)
# establish links from new tree to rest
if len(parentNode._children) == 1:
first._prev = parentNode._prev
last._next = parentNode._next
parentNode._prev = None
parentNode._next = None
else:
p = parentNode
c = newNode
while p is not None and p._sortedChildren.first().value() == c:
c = p
p = p._parent
if p is None:
first._prev = None
last._next = self._first
else:
neighbor = p._sortedChildren.find(c._depth)
first._prev = self.last(p._sortedChildren.find(c._depth).prev().value())
last._next = first._prev._next
# establish links from rest back to new tree
if first._prev is None:
self._first = first
else:
first._prev._next = first
if last._next is None:
self._last = last
else:
last._next._prev = last
def _removeThreads(self, node, parentNode):
“””Adjust the threads to disengage a node/subtree that is being moved/removed.”””
# Fix threading
if len(parentNode._children) == 0: # Parent is now a leaf
parentNode._prev = self.first(node)._prev
parentNode._next = self.last(node)._next
if parentNode._prev is None:
self._first = parentNode
else:
parentNode._prev._next = parentNode
if parentNode._next is None:
self._last = parentNode
else:
parentNode._next._prev = parentNode
else:
first = self.first(node)
last = self.last(node)
if first._prev is None:
self._first = last._next
else:
first._prev._next = last._next
if last._next is None:
self._last = first._prev
else:
last._next._prev = first._prev
class _UpdateManager:
“””This is a structure to manage pending updates until they are
ready to be passed on to the _RenderedManager.
Internally, it is modeled upon the underlying hierarchy, but
compressed so that it only has nodes for those elements with a
pending update. This means that siblings are guaranteed to be
prefix-free of each other, although they may share a commond prefix.
“””
#——————- inner _node class —————–
class _node:
“””A basic inner class for a node in the tree.
status will be maintained either as ‘stable’, ‘remove’, or ‘add’
Frozen nodes will need to mantain two states. A “private” view
that is the state of the object as it would appear if
subsequently unfrozen. The “public” state is a representation
of the state of the object at the time that it was most
recently frozen (and thus how it should currently be rendered,
if needed). That public view is modeled as if its entire
subtree is unfrozen (even if those nodes have corresponding
private nodes that are truly frozen).
Unfrozen nodes only have a public view, which can be a mix of
frozen and unfrozen nodes as needed.
“””
__slots__ = (‘_chain’, ‘_publicChildren’, ‘_privateChildren’, ‘_publicUpdates’,
‘_privateUpdates’, ‘_status’, ‘_special’) # optimization
def __init__(self, chain):
“””New node is presume ‘stable’ unless informed subsequently”””
self._chain = chain
self._publicChildren = _OrderedMap(_chainCompare)
self._privateChildren = None
self._publicUpdates = {}
self._privateUpdates = None
self._status = ‘stable’ # the default
self._special = ” # used for special cases with propogating private/public branches
def isFrozen(self):
“””Is this node representing a directly frozen element.
Note: to be distinguished from indirect freeze of an ancestor
“””
return self._privateUpdates is not None
def doFreeze(self):
“””Freeze a node
_privateUpdates becomes empty dictionary.
existing (public) children must be splintered into
appropriate private/public components.
“””
if self._privateUpdates is None: # i.e., not currently frozen
self._privateUpdates = {}
self._privateChildren = _OrderedMap()
def doUnfreeze(self):
“””For new unfreeze, everything in private is pushed to public.”””
# doing this first step before checking frozen, because a mirrored subtree
# might not look frozen, even though its mirror is. Need to note that so
# that unfreeze is propogated later.
if self._special != ‘remove’:
self._special = ‘unfreeze’ # remove trumps unfreeze
if self.isFrozen():
self._publicUpdates.update(self._privateUpdates)
self._privateUpdates = None
# any private updates must be converted to public
rest = self._privateChildren
self._privateChildren = None # hide this before re-inserting updates
self._resolveMirror(rest)
def _resolveMirror(self, privateMap):
“””Send updates to public branch that were buffered in private mirror.”””
# the key is that anything that happened in private branch
# must have happened subsequent to the time that a mirror
# was originally created. When getting rid of the mirror,
# we must carefully propogate a set of updates back to the
# public branch to reflect the sequence of events.
#
# Special care is needed in the case that unfreezes
# occurred or that remove/add pairs took place, since
# those events should cause changes to the state of the
# public branch.
if _DEBUG[‘UpdateManager’] >= 2:
print(“Within _resolveMirror on node ” + str(self))
for (chain, child) in list(privateMap):
if _DEBUG[‘UpdateManager’] >= 3:
print(“Resolving child ” + str(child) + ” with status ” + child._status + ” and special ” + child._special)
if child._special == ‘remove’: # anything else here was after the remove
self._updateRecurse(chain, ‘remove’, {}, privateMap)
if child._status == ‘stable’: # must have been re-added subsequently
self._updateRecurse(chain, ‘add’)
elif child._special == ‘unfreeze’: # must propogate
self._updateRecurse(chain, ‘unfreeze’)
if child._status == ‘add’:
self._updateRecurse(chain, ‘add’, child._publicUpdates)
elif child._publicUpdates:
self._updateRecurse(chain, ‘update’, child._publicUpdates)
if child._publicChildren:
self._resolveMirror(child._publicChildren) # recurse, with updates sent to this node
if child.isFrozen():
self._updateRecurse(chain, ‘freeze’)
if child._privateUpdates:
self._updateRecurse(chain, ‘update’, child._privateUpdates)
if child._privateChildren:
self._resolveMirror(child._privateChildren) # recurse, with updates sent to this node
def setProperties(self, properties):
“””Properties can be any dictionary of kev/value pairs.
This assumes that frozen status is current”””
if self.isFrozen():
self._privateUpdates.update(properties)
else:
self._publicUpdates.update(properties)
def setBorn(self):
“””Schedule an element as newly born.
We presume that frozen status was already set before this call.
“””
if self._status == ‘remove’:
self._status = ‘stable’ # rendered already existed
else:
self._status = ‘add’
def setDead(self, parentMap):
“””Schedule an element to die.
If it has not previously been rendered, then the node is
deleted entirely as it becomes irrelevant.
If it was previously rendered, it is scheduled to die, but
all other pending updates are flushed since they become
irrelevant.
parentMap should be the _children map containing this node
as a value.
“””
if self._status == ‘add’:
# we can go ahead and kill this right away, as well as all descendents
# (which by definition should be new)
del parentMap[self._chain]
else:
# cannot kill yet, since rendering already exists.
# But we can clear all pending properties/updates and
# effectively unfreze.
self._status = self._special = ‘remove’ # note well that we set _special as well
self._publicUpdates = {}
self._publicChildren = _OrderedMap()
self._privateUpdates = None
self._privateChildren = None
def _updateRecurse(self, chain, style, properties={}, parentMap=None):
“””Note that parentMap need only be sent when style is ‘remove’.”””
if _DEBUG[‘Middle’] >= 3:
print(‘_UpdateManager._node._updateRecurse called with\n ‘ + ‘\n ‘.join([str(x) for x in (self,chain,style,properties)]))
print(‘ Node is currently ‘ + (‘frozen’ if self.isFrozen() else ‘unfrozen’))
if self._chain == chain:
# exact match; make the changes
if style == ‘remove’:
self.setDead(parentMap)
elif style == ‘freeze’:
self.doFreeze()
elif style == ‘unfreeze’:
self.doUnfreeze()
else:
# either ‘update’ or ‘add’
if style == ‘add’:
self.setBorn()
self.setProperties(properties)
else:
# figure out how to recurse; all updates go to private branch if frozen
if self.isFrozen():
children = self._privateChildren
else:
children = self._publicChildren
before = children.closestBefore(chain, False)
if before is not None:
val = before.key()
if chain[:len(val)] == val: # prefix or exact match
before.value()._updateRecurse(chain, style, properties, children)
return
else:
after = before.next()
else:
after = children.first()
# if we reach this point, we need to make a new child,
# check for other children that should be contained under
# new child, then recurse (on what will be base case)
child = _UpdateManager._node(chain)
if _DEBUG[‘Middle’] >= 2.5:
print(“created new _UpdateManager._node: ” + str(child) + ” for chain ” + str(chain))
while after is not None and after.key()[:len(chain)] == chain:
relocate = after
after = relocate.next()
child._publicChildren[relocate.key()] = relocate.value() # reinsert under new node (always public)
children.remove(relocate) # and remove from current level
children[chain] = child # add child
child._updateRecurse(chain, style, properties, children)
def _flushRecurse(self, parentMap=None):
if _DEBUG[‘Middle’] >= 3:
print(‘_flushRecurse called on node ‘ + str(self))
print(‘isFrozen currently ‘ + str(self.isFrozen()))
if self._status != ‘stable’ or len(self._publicUpdates) > 0:
# this node needs to be added/removed or has properties to push
yield (self._chain, self._status, self._publicUpdates)
self._publicUpdates = {}
self._status = ‘stable’
# consider all public children, even if current node is frozen
for (key,c) in list(self._publicChildren): # use copy, since calls may mutate
for result in c._flushRecurse(self._publicChildren):
#print (‘ OH HYE, HERE IS THE RESULT ‘ + str(result))
#print (‘\n\n\n’)
yield result
if parentMap is not None and not self.isFrozen():
# this node has no private data, and all public updates will have been pushed
# only issue is remaining (frozen) children. Let’s destroy this node, and promote
# any remaining children in its place.
for (_,c) in self._publicChildren:
parentMap[c._chain] = c # move this node’s remaining children to parent
del parentMap[self._chain] # and then remove this node, since flushed
#——————- end of inner _node class —————–
def __init__(self):
“””An initially empty Hierarchy.
Initialized to have a persistent root with () chain.
“””
self._root = self._node(())
def update(self, chain, style, properties={}):
“””Augment the manager with the given update.
style should be either ‘add’, ‘remove’, ‘freeze’, ‘unfreeze’, or ‘update’
For ‘add’ or ‘update’, properties should be dictionary of key/value pairs.
Empty dicitonary should be used for remove/freeze/unfreeze.
“””
if _DEBUG[‘Middle’] >= 1:
print(‘\n_UpdateManager.update called with\n ‘ + ‘\n ‘.join([str(x) for x in (chain,style,properties)]))
if not isinstance(style, basestring):
raise TypeError(‘style should be a string’)
if style not in (‘add’, ‘remove’, ‘freeze’, ‘unfreeze’, ‘update’):
raise ValueError(‘invalid style designator: ‘ + str(statusFlags))
if not isinstance(properties, dict):
raise TypeError(‘properties should be a dictionary’)
if style in (‘remove’, ‘freeze’, ‘unfreeze’) and len(properties) > 0:
raise ValueError(‘Must send empty dictionary with ‘ + style)
self._root._updateRecurse(chain, style, properties, self._root._publicChildren)
def flush(self):
“””This returns a preorder generator of all updates to be rendered.
In the process, it mutates the UpdateManager to remove nodes
associated with objects that will presumably be deleted from
the rendering.
Objects yielded are (chain, status, properties)
where status is ‘add’, ‘remove’, or ‘stable’ and properties is a dictionary
“””
if _DEBUG[‘Middle’] >= 1:
print(‘_UpdateManager.flush() called’)
return self._root._flushRecurse()
class _GraphicsManager:
def __init__(self):
# Synchornization mechanisms
self._state = ‘Initial’ # ‘Initial’, ‘Running’, ‘Stopped’ or ‘Failed’
self._commandQueue = _Queue.Queue()
self._commandLock = _threading.RLock() # Must be grabbed before working with command queue
# Rendering engine objects
# _frontHierarchy manages the view based on what has been sent to the command queue
self._frontHierarchy = _Hierarchy()
# _middleHierarchy is based on middle layer that has pulled
# stuff off the command queue and sent to update manager.
# When commandQueue is empty, this should match _frontHierarchy
self._middleHierarchy = _Hierarchy()
# _middleProperties is used to cache all of the drawable
# properties for those objects known to the middle layer.
# These are needed for times when the middle layer must
# retransmit them to the update manager when adding a
# secondary chain for existing objects
self._middleProperties = {} # map from Drawable -> dictionary of properties
# _updateMangager lies between the middle and back layer. It
# handles batching changes as well as the semantics for
# freezing canvases or drawables
self._updateManager = _UpdateManager()
# _renderedHierarchy structure is based on what has already
# been flushed through the update manager, and hence what is
# currently rendered at the Tk level
self._renderedHierarchy = _RenderedHierarchy()
# Status
self._openCanvases = []
self._drawParent = None
self._drawChildren = None
# Event handling
# _handlingEvents could be Always, Yes, No or Waiting
if _nativeThreading:
self._handlingEvents = ‘Always’
else:
self._handlingEvents = ‘No’
self._waitingObject = None
self._eventQueue = _Queue.Queue()
self._eventHandlers = dict()
self._objectIdRegistry = dict()
self._lastEvent = None
self._eventLock = _threading.RLock() # TODO lock every event thing up
# Mouse
self._mousePrevPosition = None
self._mouseButtonDown = False
def beginRefresh(self):
self._commandLock.acquire()
def completeRefresh(self, pushUpdates=True):
# In single-threaded, wait until LAST reentrant lock released before pushing
if pushUpdates:
self.addCommandToQueue((‘push updates’,))
if not _nativeThreading:
# Loop to check if queue is empty
while not self._commandQueue.empty():
self.processCommands()
_tkroot.update()
self._commandLock.release()
def addCommandToQueue(self, command):
if self._state == ‘Initial’:
self._state = ‘Running’
if _nativeThreading:
# Start command thread
_thread.start_new_thread(_startCommandThread, ())
_atexit.register(_stopCommandThread)
else:
_initLibrary()
_atexit.register(_exitMainThread)
if self._state != ‘Failed’:
if _DEBUG[‘Front’] >= 1:
print(‘addCommandToQueue: ‘ + str(command) + ‘ from thread ‘ + repr(_threading.currentThread()))
self._commandQueue.put(command)
def _closeAll(self):
pass # TODO
def processCommands(self):
if _DEBUG[‘processCommands’] >= 1 and not _nativeThreading:
print(‘\n’)
print(‘processCommands called\n’)
MAX_TIME = 0.1
start_time = _time.time()
try:
while (_time.time() – start_time) <= MAX_TIME and self._state == 'Running' and not self._commandQueue.empty():
command = self._commandQueue.get(False)
try:
self.processCommand(command)
except GraphicsError:
raise
except KeyboardInterrupt:
raise
except GraphicsError:
raise
except: # TODO: too general?
# Note: could happen for an empty queue
print('Unknown graphics error has occured. Graphics manager is shutting down.')
print('Program must be restarted to use graphics.')
print('If problem is repeatable, please report to bugs@cs1graphics.org.')
self._state = 'Failed'
self._closeAll()
if max(_DEBUG.values()) > 0: # exit upon first error
_traceback.print_exc(file=_sys.stdout)
_sys.exit()
def serializeDepth(self, original, parentTuple, leafTuple):
serial = -self._middleHierarchy.getSerial(parentTuple, leafTuple) # negated to get painter’s ordering
if isinstance(parentTuple[0], (Canvas,Layer)):
depthKey = (original, serial)
else: # user-defined
depthKey = (None, serial)
return depthKey
def processCommand(self, command):
if _DEBUG[‘processCommands’] >= 1:
print(‘Manager executing: ‘ + str(command) + ‘ from thread ‘ + repr(_threading.currentThread()))
# Rendering
if command[0] == ‘push updates’:
self._pushUpdates()
# Canvases
elif command[0] == ‘create canvas’:
chain = ((command[1],Canvas),)
self._updateManager.update(chain, ‘add’, command[2])
self._middleHierarchy.newCanvas(command[1])
if command[2][‘frozen’]:
self._updateManager.update(chain, ‘freeze’)
elif command[0] == ‘close canvas’:
_tkroot.update()
# existing object is frozen
elif command[0] == ‘freeze’:
for chain in self._middleHierarchy.computeUpwardChains(command[1]):
self._updateManager.update(tuple(chain), ‘freeze’)
# existing object is unfrozen
elif command[0] == ‘unfreeze’:
for chain in self._middleHierarchy.computeUpwardChains(command[1]):
self._updateManager.update(tuple(chain), ‘unfreeze’)
# New objects
elif command[0] == ‘object added’:
containerTuple = command[1]
drawableTuple = command[2]
if _DEBUG[‘processCommands’] >= 1:
print(‘_middleHierarchy.addLink: ‘ + str(containerTuple) + ‘ ‘ + str(drawableTuple))
self._middleHierarchy.addLink(containerTuple, drawableTuple)
downwardChains = self._middleHierarchy.computeDownwardChains(drawableTuple)
for d,count in downwardChains:
leafTuple = d[-1]
properties = dict(self._middleProperties[leafTuple[0]]) # intentional copy
isFrozen = properties[‘frozen’]
if len(d) > 1:
# we know the parent for all such chains
parentTuple = d[-2]
else:
parentTuple = containerTuple
properties[‘depth’] = self.serializeDepth(properties[‘depth’], parentTuple, leafTuple)
for u in self._middleHierarchy.computeUpwardChains(containerTuple, count):
tc = tuple(u + d)
if _DEBUG[‘Middle’] >= 1.5:
print(‘\nAdding chain to updateManager: ‘ + repr(tc))
print(“Effective depth ” + str(properties[‘depth’]))
self._updateManager.update(tc, ‘add’, properties)
if isFrozen:
self._updateManager(tc, ‘freeze’)
elif command[0] == ‘object removed’:
parent = command[1]
child = command[2]
for c in self._middleHierarchy.computeUpwardChains(parent):
c.append( child )
self._updateManager.update(tuple(c), ‘remove’)
if _DEBUG[‘processCommands’] >= 1:
print(‘_middleHierarchy.removeLink: ‘ + str(parent) + ‘ ‘ + str(child))
self._middleHierarchy.removeLink(parent,child)
# Drawables
elif command[0] == ‘update’:
#print ( ‘The following is command[1] ‘ + str(command[1]))
#print ( ‘The following is command[2] ‘ + str(command[2]))
self._middleProperties.setdefault(command[1],{}).update(command[2])
if command[1] in self._middleHierarchy:
for chain in self._middleHierarchy.computeUpwardChains(command[1]):
if ‘depth’ in command[2]:
parentTuple = chain[-2]
childTuple = chain[-1]
command[2][‘depth’] = self.serializeDepth(command[2][‘depth’], parentTuple, childTuple)
if _DEBUG[‘processCommands’] >= 1:
print(‘Updating Effective Depth: %s’ % str(command[2][‘depth’]))
self._updateManager.update(tuple(chain), ‘update’, command[2])
elif command[0] == ‘load image’:
good = True
try:
i = _Tkinter.PhotoImage(file=command[1])
except _Tkinter.TclError:
good = False
if good:
self._resultQueue.put( (i, i.width(), i.height()) )
else:
self._resultQueue.put(None)
elif command[0] == ‘convert image’:
self._resultQueue.put(_convertImage(command[1]))
elif command[0] == ‘get text size’:
self._resultQueue.put(_getTextSize(command[1], command[2]))
elif command[0] == ‘save to file’:
rc = self._renderedHierarchy.getNode( ((command[1],Canvas),) )._renderedDrawable
rc.saveToFile(command[2], command[3])
self._resultQueue.put(None)
def _pushUpdates(self):
# Loop through update manager, adjust the rendered hierarchy and rendering
if _DEBUG[‘Middle’] >= 1:
print(“_pushUpdates called”)
for (chain, status, properties) in self._updateManager.flush():
if _DEBUG[‘Middle’] >= 2:
print(‘_pushUpdates: ‘ + str(status)+’ ‘+str(chain)+’ ‘+str(properties))
if self._renderedHierarchy.hasChain(chain):
print(‘ Rendered Depth is ‘ + str(self._renderedHierarchy.getNode(chain)._depth))
if status == ‘add’:
assert not self._renderedHierarchy.hasChain(chain)
current = self._renderedHierarchy.add(chain, properties[‘depth’], properties[‘transformation’], None)
current._renderedDrawable = self._createRendered(chain, properties)
if not isinstance(current._renderedDrawable, _RenderedCanvas) and current._renderedDrawable is not None:
node = current._next
while node is not None and node._renderedDrawable is None:
node = node._next
if node is not None and node._chain[0] == chain[0]: # TODO: correct treatment of forest???
if _DEBUG[‘Middle’] >= 1: print(‘Putting ‘+str(current._renderedDrawable)+’ above ‘+str(node._renderedDrawable))
current._renderedDrawable.putAbove(node._renderedDrawable)
else:
if _DEBUG[‘Middle’] >= 1: print(‘Putting ‘+str(current._renderedDrawable)+’ at bottom’)
current._renderedDrawable.putAbove(None)
elif status == ‘remove’:
removed = self._renderedHierarchy.remove(chain)
for renderedDrawable in removed:
renderedDrawable.remove()
elif status == ‘stable’:
# Update transformation
if ‘transformation’ in properties:
(first, last) = self._renderedHierarchy.changeTransform(chain, properties[‘transformation’])
current = first
while True:
if current._renderedDrawable is not None:
current._renderedDrawable.update({‘transformation’: current._transformation})
if current == last:
break
current = current._next
del properties[‘transformation’] # will not need to update this below
# Update depth
if ‘depth’ in properties:
(first, last) = self._renderedHierarchy.changeDepth(chain, properties[‘depth’])
if first is not None: # something changed
if _DEBUG[‘Middle’] >= 2: print(‘first, last = ‘+str( (first._renderedDrawable,last._renderedDrawable) ))
# first goal is finding an adequate anchor below this group
below = last._next
while below is not None and below._renderedDrawable is None:
below = below._next
# now place series of objects in line after each other
current = last
while current != first._prev:
if current._renderedDrawable is not None:
if below is not None and below._chain[0] == chain[0]:
if _DEBUG[‘Middle’] >= 1:
print(‘Putting ‘+str(current._renderedDrawable)+’ above ‘+str(below._renderedDrawable))
current._renderedDrawable.putAbove(below._renderedDrawable)
else:
if _DEBUG[‘Middle’] >= 1:
print(‘Putting ‘ + str(current._renderedDrawable) + ‘ at bottom’)
current._renderedDrawable.putAbove(None)
below = current
current = current._prev
# Update any other properties (beyond transformation, depth)
if properties:
rd = self._renderedHierarchy.getNode(chain)._renderedDrawable
if rd is not None:
rd.update(properties)
def _createRendered(self, chain, properties):
mapping = {
Canvas : _RenderedCanvas,
Circle : _RenderedCircle,
Ellipse : _RenderedCircle, # note well: using _renderedCircle
Rectangle : _RenderedRectangle,
Polygon : _RenderedPolygon,
Path : _RenderedPath,
Text : _RenderedText,
Image : _RenderedImage,
}
goal = chain[-1][1]
rendered = mapping.get(goal)
if _DEBUG[‘Tkinter’] >= 2: print(‘_createRendered called on chain’ + str(chain) + ‘ using ‘ + str(rendered))
if rendered is not None:
return rendered(chain, properties) # create new instance
else:
return None # nothing to render
def executeFunction(self, command):
# Perform a single command and return a value
# TODO: avoid possible deadlock
self._functionLock.acquire()
self._commandLock.acquire()
self.addCommandToQueue(command)
if not _nativeThreading:
self.processCommands()
_tkroot.update()
self._commandLock.release()
result = self._resultQueue.get()
self._functionLock.release()
return result
def addEventToQueue(self, handler, event):
if self._handlingEvents == ‘Always’:
# Start a new thread and go
#What’s to be expected is reasonable, call the
handler.handle(event)
elif self._handlingEvents == ‘Yes’:
self._eventQueue.put((handler,event))
elif self._handlingEvents == ‘Waiting’ and event._trigger == self._waitingObject:
self._eventQueue.put((handler,event))
else:
pass # Ignore the event
def removeHandler(self, obj, handler):
s = self._eventHandlers.get(obj, set())
if handler in s:
s.remove(handler) #
else:
raise ValueError()
def processEvents(self):
if _DEBUG[‘processEvents’] >= 5:
print (‘Entering process events\n’)
while not self._eventQueue.empty():
(handler, event) = self._eventQueue.get(False)
self._lastEvent = event
if self._handlingEvents == ‘Waiting’:
self._handlingEvents = ‘No’
while not self._eventQueue.empty():
self._eventQueue.get(False)
handler.handle(event)
def wait(self, waiter):
if _DEBUG[‘wait’] >= 1:
print (‘_handlingEvents = ‘ + self._handlingEvents)
print (‘ The following is the currentThread in wait’)
print (_threading.currentThread())
if self._handlingEvents == ‘Always’:
lock = _threading.Lock()
rh = _ReleaseHandler(lock)
self.addHandler(waiter,rh)
lock.acquire()
self.removeHandler(waiter,rh)
return rh._event
elif self._handlingEvents == ‘No’:
if _DEBUG[‘wait’] >= 1: print (‘addHandler is called’)
self.addHandler(waiter, EventHandler())
self.mainLoop(waiter, True)
return self._lastEvent
def mainLoop(self, waiting=None, exitOnAllClosed=True):
if waiting:
#handlingEvents is set to waiting to prevent loop
if _DEBUG[‘mainLoop’] >= 3:
print (‘_handlingEvents is currently: ‘) + self._handlingEvents
self._handlingEvents = ‘Waiting’
if _DEBUG[‘mainLoop’] >= 2:
print (‘ waiting is the following ‘)
print (waiting)
print (‘\n’)
#waitingObject is updated to be waiting (canvas then circle)
self._waitingObject = waiting
#Might want to note states, when they could change, same for _handlingEvents
#A sort of state transition guide
while self._state == ‘Running’ and self._handlingEvents in (‘Yes’, ‘Waiting’):
if _DEBUG[‘mainLoop’] >= 4:
print (‘About to call _tkroot.update()’)
_tkroot.update()
if _DEBUG[‘mainLoop’] >= 4:
print (‘Finished call _tkroot.update()’)
self.processEvents()
if exitOnAllClosed and len(_graphicsManager._openCanvases) == 0:
break
_time.sleep(.1)
# Events Primatives
class Event(object):
“””An event typically triggered by the user interface.”””
def __init__(self):
self._eventType = ”
self._x, self._y = 0, 0
self._prevx, self._prevy = 0,0
self._key = ”
self._button = None
self._trigger = None
def getDescription(self):
“””Return a text description of the event.
Possibilities include:
‘mouse click’, ‘mouse release’, ‘mouse drag’, ‘keyboard, ‘timer’, ‘canvas close’
“””
return self._eventType
def getMouseLocation(self):
“””Return a Point designating the location of the mouse at the time of the event.”””
return Point(self._x, self._y)
def getOldMouseLocation(self):
“””Return a Point designating the location of the mouse at the start of a mouse drag.”””
return Point(self._prevx, self._prevy)
def getTrigger(self):
“””Return a reference to the object that triggered the event.”””
return self._trigger
def getKey(self):
“””Return a string designating the key pressed for a keyboard event.”””
return self._key
def getButton(self):
“””Return number of the mouse button that caused the mouse event (else None).”””
return self._button
class EventHandler(object):
“””A base class for creating new event handlers.
The handle method for this base class does not do anything.
“””
def __init__(self):
“””Create a new event handler.
Children of this class must call this constructor.
“””
pass
def handle(self, event):
“””Handle an event.
Child classes must override this method, but do not need
to call it.
“””
pass
class _ReleaseHandler(EventHandler):
def __init__(self, lock):
self._lock = lock
self._event = None
self._lock.acquire()
def handle(self, event):
if event.getDescription() in [‘keyboard’, ‘mouse click’, ‘canvas close’]:
self._event = event
self._lock.release()
class _EventTrigger(object):
def __init__(self):
super(_EventTrigger, self).__init__()
def wait(self):
“””Wait for an event to occur.
When an event occurs, an Event instance is returned
with information about what has happened.
“””
return _graphicsManager.wait(self)
def addHandler(self, handler):
“””Register an EventHandler instance with this object.”””
if not isinstance(handler, EventHandler):
raise TypeError(‘Only instance of EventHandler (or child class) can handle events’)
try:
_graphicsManager.addHandler(self, handler) # TODO should be a on queue, not thread safe
except ValueError:
raise ValueError(‘Handler is already handling events for this object’)
def removeHandler(self, handler):
“””Unregister an EventHandler instance from this object.”””
if not isinstance(handler, EventHandler):
raise TypeError(‘Parameter is not an instance of EventHandler (or child class)’)
try:
_graphicsManager.removeHandler(self, handler) # TODO should be a on queue, not thread safe
except ValueError:
raise ValueError(‘The handler is not currently associated with this object.’)
def run(self):
self._handler.handle(self._event)
# Graphics Primatives
class Point(object):
“””Stores a two-dimensional point using Cartesian coordinates.”””
def __init__(self, initialX=0, initialY=0):
“””Create a new point instance.
initialX x-coordinate of the point (default 0)
initialY y-coordinate of the point (default 0)
“””
if not isinstance(initialX, (int, float)):
raise TypeError(‘x-coordinate must be a number’)
if not isinstance(initialY, (int, float)):
raise TypeError(‘y-coordinate must be a number’)
self._x = initialX
self._y = initialY
def getX(self):
“””Return the x-coordinate.”””
return self._x
def setX(self, val):
“””Set the x-coordinate to val.”””
if not isinstance(val, (int, float)):
raise TypeError(‘x-coordinate must be a number’)
self._x = val
def getY(self):
“””Return the y-coordinate.”””
return self._y
def setY(self, val):
“””Set the y-coordinate to val.”””
if not isinstance(val, (int, float)):
raise TypeError(‘y-coordinate must be a number’)
self._y = val
def get(self):
“””Return an (x,y) tuple.”””
return self._x, self._y
def scale(self, factor):
“””Scale the coordinates by the given factor.”””
if not isinstance(factor, (int, float)):
raise TypeError(‘scaling factor must be a number’)
self._x *= factor
self._y *= factor
def distance(self, other):
“””Return the distance between this point and the other.”””
if not isinstance(other, Point):
raise TypeError(‘other must be a Point instance’)
dx = self._x – other._x
dy = self._y – other._y
return _math.sqrt(dx * dx + dy * dy)
def normalize(self):
“””Mutate the point, scaling it to distance one from the origin.
If the point currently represents the origin, it is unchanged.
“””
mag = self.distance( Point() )
if mag > 0:
self.scale(1./mag)
def __str__(self):
“””Return a string representation of the point (e.g., ‘<0,0>‘).”””
return ‘<' + str(self._x) + ',' + str(self._y) + '>‘
def __neg__(self):
“””Return a new point that is the negated version of this Point.”””
return Point(-self._x, -self._y)
def __add__(self, other):
“””Return a new point that is the sum of this Point and the other.”””
if not isinstance(other, Point):
raise TypeError(‘both operands must be Point instances’)
return Point(self._x + other._x, self._y + other._y)
def __sub__(self, other):
“””Return a new point that is the oriented difference between the points.”””
if not isinstance(other, Point):
raise TypeError(‘both operands must be Point instances’)
return Point(self._x – other._x, self._y – other._y)
def __mul__(self, operand):
“””Return the result when multiplying the Point by an operand.
When the operand is a scalar (i.e., an int or float), return a
Point that has coordinates equal to the original times the factor.
When operand is another Point, return a scalar that is the dot
product of the two points.
“””
if isinstance(operand, (int, float)): # multiply by constant
return Point(self._x * operand, self._y * operand)
elif isinstance(operand, Point): # dot-product
return self._x * operand._x + self._y * operand._y
else:
raise TypeError(‘unexpected operand for multiplication’)
def __rmul__(self, operand):
“””Return the result when multiplying the Point by an operand.
See __mul__ for details.
“””
return self * operand
def __xor__(self, angle):
“””Return a point instance equal to a rotated version of the original.
angle number of degrees of rotation
Rotation is performed about the origin.
“””
if not isinstance(angle, (int, float)):
raise TypeError(‘angle must be a number’)
angle = _math.pi*angle/180.
return Point(self._x * _math.cos(angle) – self._y * _math.sin(angle),
self._x * _math.sin(angle) + self._y * _math.cos(angle))
class _Transformation(object):
EPSILON = 0.0000001 # arbitrary
#—————————————————————————
# defining closure to wrap the original _draw while identifying proper class
def drawClosure(self):
# Note: cls and internalDraw taken from the closure
if _DEBUG[‘Front’] >= 2: print(str(cls) + ‘ draw wrapper called on ‘ + str(self))
parent = _graphicsManager._drawParent
if not parent:
raise GraphicsError(‘_draw should not be directly called’, True)
siblings = _graphicsManager._drawChildren
if siblings is not None:
siblings.append( (self,cls) )
known = self in _graphicsManager._frontHierarchy # query this before adding to hierarchy
if _DEBUG[‘Front’] >= 1:
print(‘\n_frontHierarchy.addLink: ‘ + str(parent) + ‘ ‘ + str( (self,cls) ))
_graphicsManager._frontHierarchy.addLink(parent, (self,cls))
if not known:
_graphicsManager.addCommandToQueue((‘update’, self, self._getProperties())) # presend all properties
_graphicsManager.addCommandToQueue((‘object added’, parent, (self,cls)))
if not known:
if _DEBUG[‘Front’] >= 2: print(‘about to call original _draw() for ‘ + str(self))
_graphicsManager._drawParent = (self,cls)
internalDraw(self) # the original wrapped function, taken from closure
_graphicsManager._drawParent = parent
if _DEBUG[‘Front’] >= 2: print(str(cls) + ‘ draw wrapper call ending for ‘ + str(self))
# end of closure
#—————————————————————————
setattr(cls, ‘_draw’, drawClosure)
# if _internalDraw exists, then parents are already wrapped as well,
# but we cannot be sure of there is no _internalDraw nor _draw, so let’s recurse
for base in cls.__bases__:
if issubclass(base, Drawable):
_wrapUtility(base)
# Drawable Hierarchy
class Drawable(_EventTrigger):
“””An object that can be drawn to a graphics canvas.”””
def __init__(self, reference=None):
“””Create a Drawable instance.
referencePoint local reference point for scaling, rotating and flipping
(default Point(0,0) )
“””
super(Drawable, self).__init__()
_wrapUtility(self.__class__)
if reference is not None:
if not isinstance(reference, Point):
raise TypeError(‘reference point must be a Point instance’)
else:
reference = Point()
self._reference = reference
self._transform = _Transformation()
self._depth = 50
self._frozen = False
def __deepcopy__(self, memo={}):
“””This provides underlying support for clone().”””
# We use Drawable.__deepcopy__ to do all the real work.
# Subtypes can customize as needed.
temp = self.__class__.__new__(self.__class__)
memo[id(self)] = temp
for k,v in self.__dict__.items():
temp.__dict__[k] = _copy.deepcopy(v, memo)
return temp
# TODO: get rid of this. temporary hack for 3.0 issue and comparing chains
def __lt__(self, other):
return id(self) < id(other)
def isFrozen(self):
"""Returns True if currently frozen; False otherwise."""
return self._frozen
def freeze(self):
"""Freeze the current object (if not already frozen).
For an object that is already rendered, when frozen, any
further changes to it will not be rendered until such time
when unfrozen() is called.
However, if unrendered, when added to a canvas or layer, this
object will be rendered with its most current properties, even
if currently frozen.
"""
if not self._frozen:
self._frozen = True
if self in _graphicsManager._frontHierarchy:
_graphicsManager.beginRefresh()
_graphicsManager.addCommandToQueue(('freeze', self))
_graphicsManager.completeRefresh()
def unfreeze(self):
"""Unfreeze the current object (if currently frozen).
When unfrozen, all changes that were made since the most
recent call to freeze() will be rendered.
"""
if self._frozen:
self._frozen = False
if self in _graphicsManager._frontHierarchy:
_graphicsManager.beginRefresh()
_graphicsManager.addCommandToQueue(('unfreeze', self))
_graphicsManager.completeRefresh()
def move(self, dx, dy):
"""Move the object dx units along X-axis and dy units along Y-axis.
For the default coordinate system, positive dx is rightward and
negative is leftward; positive dy is downard and negative is upward.
"""
if not isinstance(dx, (int,float)):
raise TypeError('dx must be numeric')
if not isinstance(dy, (int,float)):
raise TypeError('dy must be numeric')
self._transform = _Transformation( (1.,0.,0.,1.,dx,dy)) * self._transform
self._update({'transformation': self._transform})
def moveTo(self, x, y):
"""Move the object to align its reference point with (x,y)"""
if not isinstance(x, (int,float)):
raise TypeError('x must be numeric')
if not isinstance(y, (int,float)):
raise TypeError('y must be numeric')
curRef = self.getReferencePoint()
self.move(x-curRef.getX(), y-curRef.getY())
def rotate(self, angle):
"""Rotate the object around its current reference point.
angle number of degrees of clockwise rotation
"""
if not isinstance(angle, (int,float)):
raise TypeError('angle must be numeric')
angle = -_math.pi*angle/180.
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
rot = _Transformation((_math.cos(angle),_math.sin(angle),
-_math.sin(angle),_math.cos(angle),0.,0.))
self._transform = trans*(rot*(trans.inv()*self._transform))
self._update({'transformation': self._transform})
def scale(self, factor):
"""Scale the object relative to its current reference point.
factor scale is multiplied by this number (must be positive)
"""
if not isinstance(factor, (int,float)):
raise TypeError('scaling factor must be a positive number')
if factor <= 0:
raise ValueError('scaling factor must be a positive number')
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
sca = _Transformation((factor,0.,0.,factor,0.,0.))
self._transform = trans*(sca*(trans.inv()*self._transform))
self._update({'transformation': self._transform})
def stretch(self, xFactor, yFactor, angle=0):
"""Stretch the shape in mutltiple direction.
By default the x-axis is scaled by a factor of xFactor and the
y-axis is scaled by a factor of yFactor. The optional
parameter rotates the directions that the streching is performed
along.
"""
if not isinstance(xFactor, (int,float)) or not isinstance(yFactor, (int,float)):
raise TypeError('stretch factor must be a positive number')
if xFactor<=0 or yFactor<=0:
raise ValueError('stretch factor must be a positive number')
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
rot = _Transformation((_math.cos(angle),_math.sin(angle),
-_math.sin(angle),_math.cos(angle),0.,0.))
rotinv = rot.inv()
sca = _Transformation((xFactor,0.,0.,yFactor,0.,0.))
self._transform = trans*(rotinv*(sca*(rot*(trans.inv()*self._transform))))
self._update({'transformation': self._transform})
def flip(self, angle=0):
"""Flip the object reflected about its current reference point.
By default the flip is a left-to-right flip with a vertical axis of symmetry.
angle a clockwise rotation of the axis of symmetry away from vertical
"""
if not isinstance(angle, (int,float)):
raise TypeError('angle must be numeric')
angle = _math.pi*angle/180.
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
rot = _Transformation((_math.cos(angle),_math.sin(angle),
-_math.sin(angle),_math.cos(angle),0.,0.))
rotinv = rot.inv()
invert = _Transformation((-1.,0.,0.,1.,0.,0.))
self._transform = trans*(rotinv*(invert*(rot*(trans.inv()*self._transform))))
self._update({'transformation': self._transform})
def shear(self, shear, angle=0):
"""Shear the object relative to its current reference point.
By default, points with the same y-coordinate as the reference point are left
unchanged. A point d units above the reference point is shifted d * shear
units to the right. The optional angle parameter rotates the axis
that the shearing occurs along.
angle clockwise angle for shear
"""
if not isinstance(shear, (int,float)):
raise TypeError('shear factor must be numeric')
if not isinstance(angle, (int,float)):
raise TypeError('angle must be numeric')
angle = _math.pi*angle/180.
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
rot = _Transformation((_math.cos(angle),_math.sin(angle),
-_math.sin(angle),_math.cos(angle),0.,0.))
rotinv = rot.inv()
sh = _Transformation((1.,-shear,0.,1.,0.,0.))
self._transform = trans*(rotinv*(sh*(rot*(trans.inv()*self._transform))))
self._update({'transformation': self._transform})
def getReferencePoint(self):
"""Return a copy of the current reference point.
Note that mutating that copy has no effect on the Drawable object.
"""
return self._localToGlobal(self._reference)
def adjustReference(self, dx, dy):
"""Move the local reference point relative to its current position.
Note that the object is not moved at all.
"""
if not isinstance(dx, (int,float)):
raise TypeError('dx must be numeric')
if not isinstance(dy, (int,float)):
raise TypeError('dy must be numeric')
p = self._localToGlobal(self._reference)
p = Point(p.getX()+dx, p.getY()+dy)
self._reference = self._globalToLocal(p)
def setDepth(self, depth):
"""Set the depth of the object.
Objects with a higher depth will be rendered behind those with lower depths.
"""
if not isinstance(depth, (int,float)):
raise TypeError('depth must be numeric')
self._depth = depth
self._update({'depth': self._depth})
def getDepth(self):
"""Return the depth of the object."""
return self._depth
def clone(self):
"""Return a duplicate of the drawable object.
The duplicate will have the same properties as the original,
including the sharing of color instances, but the new instance
is not automatically added to those canvases or layers
containing the original.
"""
return _copy.deepcopy(self)
def _localToGlobal(self, point):
if not isinstance(point, Point):
raise TypeError('parameter must be a Point instance')
return self._transform.image(point)
def _globalToLocal(self, point):
if not isinstance(point, Point):
raise TypeError('parameter must be a Point instance')
return self._transform.inv().image(point)
def _beginDraw(self):
"""Deprecated"""
pass
def _completeDraw(self):
"""Deprecated"""
pass
def _objectChanged(self):
"""Deprecated"""
raise NotImplementedError('Deprecated. Please see documentation for _contentsChanged()')
def _draw(self):
"""Cause the object to be drawn (typically, the method is not called directly)."""
raise NotImplementedError('_draw() method must be implemented for each Drawable')
def _contentsChanged(self):
"""Designates that the composition of a (user-defined) Drawable may have changed.
This should be called if an action has taken place that may
effect the composition of _draw for this object, either
because components have been re-ordered, or because components
should be added or replaced.
"""
cacheParent = _graphicsManager._drawParent
cacheChildren = _graphicsManager._drawChildren
_graphicsManager._drawParent = (self, self.__class__) # hopefully this is the correct class
_graphicsManager._drawChildren = []
# important that we call _internalDraw, not _draw
self._internalDraw()
_graphicsManager._frontHierarchy.reviseChildren(self, _graphicsManager._drawChildren)
_graphicsManager._drawParent = cacheParent
_graphicsManager._drawChildren = cacheChildren
def _update(self, properties):
if self in _graphicsManager._frontHierarchy:
_graphicsManager.beginRefresh()
_graphicsManager.addCommandToQueue(('update', self, properties))
_graphicsManager.completeRefresh()
def _getProperties(self):
return {'transformation': self._transform, 'depth': self._depth, 'frozen' : self._frozen}
class Shape(Drawable):
"""A drawable objects that has a border."""
def __init__(self, reference=None):
"""Construct a Shape instance.
reference the initial placement of the shape's reference point.
(default Point(0,0) )
"""
if reference is not None and not isinstance(reference, Point):
raise TypeError('reference point must be a Point instance')
super(Shape, self).__init__()
if reference is not None:
self.moveTo(reference.getX(), reference.getY())
self._borderColor = Color('Black')
self._borderColor._register(self, 'border color')
self._borderWidth = 1
self._dash = (1,0) # solid line
def __deepcopy__(self, memo={}):
temp = Drawable.__deepcopy__(self, memo)
temp._borderColor = self._borderColor # do shallow copy
temp._borderColor._register(temp, 'border color')
return temp
def setBorderColor(self, color):
"""
Set the border color to a copy of the indicated color.
The parameter can be either:
- a string with the name of the color
- an (r,g,b) tuple
- an existing Color instance
"""
if self._borderColor is not color:
old = self._borderColor
if isinstance(color, Color):
self._borderColor = color
else:
try:
self._borderColor = Color(color)
except (TypeError, ValueError):
raise
old._unregister(self, 'border color')
self._borderColor._register(self, 'border color')
self._update({'border color' : self._borderColor})
def getBorderColor(self):
"""Return the color of the object's border."""
return self._borderColor
def setBorderWidth(self, width):
"""Set the width of the border to the indicated width."""
if not isinstance(width, (int,float)):
raise TypeError('border width must be non-negative number')
if width < 0:
raise ValueError('border width cannot be negative')
self._borderWidth = width / self._transform.scale()
self._update({'border width': self._borderWidth})
def getBorderWidth(self):
"""Return the width of the border."""
return self._borderWidth * self._transform.scale()
def setBorderDash(self, dashLength, gapLength=None):
"""Set the border to be a dashed line.
downLength the length of a dash
gapLength the length of interdash space (Default: downLength)
For example,
setBorderDash(3) gives pattern: xxx xxx xxx
setBorderDash(4,1) gives pattern: xxxx xxxx xxxx
setBorderDash(1,4) gives pattern: x x x
Note: gapLength of zero turns this into solid border.
Note: some systems do not properly support dashes with borderWidth greater than 1.
"""
if not isinstance(dashLength, (int,float)):
raise TypeError('dash Length must be numeric')
if dashLength <= 0:
raise ValueError('dash Length must be positive')
if gapLength is None:
gapLength = dashLength
if not isinstance(gapLength, (int,float)):
raise TypeError('space Length must be numeric')
if gapLength < 0:
raise ValueError('space Length must be non-negative')
self._dash = (dashLength, gapLength)
self._update({'dash' : self._dash})
def _getProperties(self):
prop = super(Shape, self)._getProperties()
prop.update({'border width' : self._borderWidth, 'border color' : Color(self._borderColor),
'dash' : self._dash})
return prop
class FillableShape(Shape):
"""A shape that can be filled with an interior color."""
def __init__(self, reference=None):
"""Construct a new FillableShape instance.
The interior color defaults to 'Transparent'.
reference the initial placement of the shape's reference point.
(default Point(0,0) )
"""
if reference is not None and not isinstance(reference, Point):
raise TypeError('reference point must be a Point instance')
super(FillableShape, self).__init__()
if reference is not None:
self.moveTo(reference.getX(), reference.getY())
self._fillColor = Color('Transparent')
self._fillColor._register(self, 'fill color')
def __deepcopy__(self, memo={}):
temp = Shape.__deepcopy__(self, memo)
temp._fillColor = self._fillColor # do shallow copy
temp._fillColor._register(temp, 'fill color')
return temp
def setFillColor(self, color):
"""Set the interior color of the shape to the color.
The parameter can be either:
- a string with the name of the color
- an (r,g,b) tuple
- an existing Color instance
"""
if self._fillColor is not color:
old = self._fillColor
if isinstance(color, Color):
self._fillColor = color
else:
try:
self._fillColor = Color(color)
except (TypeError, ValueError):
raise
old._unregister(self, 'fill color')
self._fillColor._register(self, 'fill color')
self._update({'fill color': self._fillColor})
def getFillColor(self):
"""Return the color of the shape's interior."""
return self._fillColor
def _getProperties(self):
prop = super(FillableShape, self)._getProperties()
prop['fill color'] = Color(self._fillColor)
return prop
# Canvas class
class Canvas(_GraphicsContainer, _EventTrigger):
"""A window that can be drawn upon."""
def __init__(self, w=200, h=200, bgColor=None, title='Graphics canvas', autoRefresh=True):
"""Create a new drawing canvas.
A new canvas will be created.
w width of drawing area (default 200)
h height of drawing area (default 200)
bgColor color of the background (default 'White')
title window title (default 'Graphics Canvas')
autoRefresh whether auto-refresh mode is used (default True)
"""
super(Canvas, self).__init__()
if not bgColor:
bgColor = 'white'
if not isinstance(w, (int,float)):
raise TypeError('width must be numeric')
if not isinstance(h, (int,float)):
raise TypeError('height must be numeric')
if not isinstance(title, basestring):
raise TypeError('title must be a string')
if not isinstance(autoRefresh, bool):
raise TypeError('autoRefresh flag must be a boolean value')
if isinstance(bgColor, Color):
self._backgroundColor = bgColor
else:
try:
self._backgroundColor = Color(bgColor)
except (TypeError,ValueError):
raise
if Color(self._backgroundColor) == Color('transparent'):
raise ValueError('canvas background cannot be transparent')
self._backgroundColor._register(self, 'background color')
if not _mathMode:
self._transform = _Transformation()
else:
self._transform = _Transformation((1,0,0,-1,0,h))
self._width = w
self._height = h
self._title = title
self._canvasOpen = True
self._mouseCoordinates = Point(0,0)
self._animation = None
self._frozen = False # want initial rendering with title/size/color even if not autoRefresh
self._reference = Point() # TODO: hack because of use in getting event coordinates
_graphicsManager._openCanvases.append(self)
_graphicsManager._frontHierarchy.newCanvas(self)
_graphicsManager.beginRefresh()
_graphicsManager.addCommandToQueue(('create canvas', self, self._getProperties()))
_graphicsManager.completeRefresh()
if not autoRefresh: # turn off auto-refresh before continuing
self.setAutoRefresh(False)
# TODO: get rid of this. temporary hack for 3.0 issue and comparing chains
def __lt__(self, other):
return id(self) < id(other)
def _update(self, properties):
_graphicsManager.beginRefresh()
_graphicsManager.addCommandToQueue(('update', self, properties))
_graphicsManager.completeRefresh()
def _getProperties(self):
# Note: using depth of (0,id(self)) to ensure uniqueness among canvases
return { 'width': self._width, 'height': self._height, 'background color': Color(self._backgroundColor),
'title': self._title, 'transformation': self._transform, 'depth': (0,id(self)),
'frozen' : self._frozen }
def getAutoRefresh(self):
"""Queries current state of the auto-refresh mode.
Returns True if auto-refresh is currently set; False otherwise.
"""
return not self._frozen
def refresh(self):
if self._frozen: # otherwise irrelevant
# force a flush and then re-freeeze
self.setAutoRefresh(True)
self.setAutoRefresh(False)
def setAutoRefresh(self, autoRefresh=True):
"""Change the auto-refresh mode.
When True (the default), every change to the canvas or to an
object drawn upon the canvas will be immediately rendered to
the screen.
When False, all changes are recorded internally, yet not shown
on the screen until the next subsequent call to the refresh()
method of this canvas. This allows multiple changes to be
buffered and rendered all at once.
"""
if not isinstance(autoRefresh, bool):
raise TypeError('autoRefresh flag should be a bool')
if autoRefresh == self._frozen: # if autoRefresh != self.getAutoRefresh()
self._frozen = not autoRefresh
cmd = 'unfreeze' if autoRefresh else 'freeze'
_graphicsManager.beginRefresh()
_graphicsManager.addCommandToQueue((cmd, self))
_graphicsManager.completeRefresh()
def setBackgroundColor(self, color):
"""Set the background color.
The parameter can be either:
- a string with the name of the color
- an (r,g,b) tuple
- an existing Color instance
"""
if self._backgroundColor is not color:
oldColor = self._backgroundColor
if Color(color) == Color('transparent'):
raise ValueError('canvas background cannot be transparent')
if isinstance(color, Color):
self._backgroundColor = color
else:
try:
self._backgroundColor = Color(color)
except (TypeError, ValueError):
raise
oldColor._unregister(self, 'background color')
self._backgroundColor._register(self, 'background color')
self._update({'background color' : Color(self._backgroundColor)})
def getBackgroundColor(self):
"""Return the background color as a Color instance."""
return self._backgroundColor
def setWidth(self, w):
"""Reset the canvas width to w."""
if not isinstance(w, (int,float)):
raise TypeError('width must be numeric value')
if w <= 0:
raise ValueError('width must be positive')
self._width = w
self._update( {'width' : w } )
def getWidth(self):
"""Return the width of the canvas."""
return self._width
def setHeight(self, h):
"""Reset the canvas height to h."""
if not isinstance(h, (int,float)):
raise TypeError('height must be numeric value')
if h <= 0:
raise ValueError('height must be positive')
if _mathMode:
delta = self._height - h
self._height = h
self._transform = self._transform * _Transformation( (1,0,0,1,0,delta) )
self._update( {'height' : h , 'transformation' : self._transform} )
else:
self._height = h
self._update( {'height' : h } )
def getHeight(self):
"""Return the height of the canvas."""
return self._height
def setTitle(self, title):
"""Set the title for the canvas window to given string."""
if not isinstance(title, basestring):
raise TypeError('title must be a string')
self._title = title
self._update( {'title' : title } )
def getTitle(self):
"""Return the title of the window."""
return self._title
def open(self):
"""Opens a graphic window (if not already open).
The window can be closed with a subsequent call to close().
"""
if not self._canvasOpen:
self._update( {'visible' : True } )
self._canvasOpen = True
_graphicsManager._openCanvases.append(self)
def close(self):
"""Close the canvas window (if not already closed).
The window can be reopened with a subsequent call to open().
"""
if self._canvasOpen:
self._update( {'visible' : False } )
self._canvasOpen = False
_graphicsManager._openCanvases.remove(self)
def _forceClose(self):
self.setAutoRefresh(True)
self.close()
def add(self, drawable):
"""Add the Drawable object to the canvas."""
if not isinstance(drawable, Drawable):
raise TypeError('only Drawable objects can be added to a Canvas')
if drawable in self._contents:
raise ValueError('object already on the Canvas')
if '_transform' not in vars(drawable):
raise Exception('Drawable instance not properly initialized (was parent constructor called?)')
try:
drawable._draw
except AttributeError:
raise Exception('child class of Drawable must provide a _draw method')
if _DEBUG['Front'] >= 1: print(‘\nCall to Canvas.add with self=’+str(self)+’ drawable=’+str(drawable))
_GraphicsContainer.add(self, drawable)
def remove(self, drawable):
“””Remove the drawable object from the canvas.”””
if drawable not in self._contents:
raise ValueError(‘Object not currently on the Canvas’)
_GraphicsContainer.remove(self,drawable)
def setView(self, lowerLeft, upperRight):
“””Set the coordinates for the lower-left corner and upper-right corners of the canvas.
lowerLeft and upperRight are Point instances storing the coordinates of the corners.
“””
if not isinstance(lowerLeft, Point) or not isinstance(upperRight, Point):
raise TypeError(‘lowerLeft and upperRight must be Point instances’)
if lowerLeft.getX() == upperRight.getX() or lowerLeft.getY() == upperRight.getY():
raise ValueError(‘Lower left and upper right corners must have different x and y coordinates.’)
xScale = float(self.getWidth())/(upperRight.getX()-lowerLeft.getX())
yScale = -float(self.getHeight())/(upperRight.getY()-lowerLeft.getY())
xTrans = -xScale*lowerLeft.getX()
yTrans = self.getHeight() – yScale*lowerLeft.getY()
self._transform = _Transformation( (xScale,0,0,yScale,xTrans,yTrans) )
self._update( {‘transformation’ : self._transform} )
def zoomView(self, factor, fixedPoint=None):
“””Scales the coordinate system for the canvas about the given fixed point.
factor multiplicative zoom factor (must be positive number)
fixedPoint the fixed point for the zoom in local coordinates
(default center of current view)
“””
if not isinstance(factor, (int,float)):
raise TypeError(‘zoom factor must be a positive number’)
if factor <= 0:
raise ValueError('zoom factor must be a positive number')
if fixedPoint is not None:
if not isinstance(fixedPoint, Point):
raise TypeError('fixedPoint must be specified as a Point instance')
else:
fixedPoint = self._transform.inv().image(Point(self.getWidth()/2., self.getHeight()/2.))
self._transform = self._transform * _Transformation( (factor,0,0,factor,
fixedPoint.getX() * (1-factor), fixedPoint.getY()*(1-factor)))
self._update( {'transformation' : self._transform} )
def rotateView(self, angle, fixedPoint=None):
"""Rotates the coordinate system of the canvas about the given fixed point.
angle number of degrees of clockwise rotation
fixedPoint the fixed point for the rotation in local coordinates
(default center of current view)
"""
if not isinstance(angle, (int,float)):
raise TypeError('angle must be numeric')
if fixedPoint is None:
fixedPoint = self._transform.inv().image(Point(self.getWidth()/2., self.getHeight()/2.))
if not isinstance(fixedPoint, Point):
raise TypeError('fixedPoint must be specified as a Point instance')
if not isinstance(fixedPoint, Point):
raise TypeError('fixedPoint must be specified as a Point instance')
translation = _Transformation( (1,0,0,1,fixedPoint.getX(),fixedPoint.getY()) )
angle = -_math.pi*angle/180.
rot = _Transformation((_math.cos(angle),_math.sin(angle),
-_math.sin(angle),_math.cos(angle),0.,0.))
self._transform = self._transform * translation * rot * translation.inv()
self._update( {'transformation' : self._transform} )
def translateView(self, lowerLeft):
"""Translates the viewable portion of the canvas's coordinate system.
lowerLeft the Point in the coordinate system that should be aligned with the
lower-left corner of the Canvas window.
"""
if not isinstance(lowerLeft, Point):
raise TypeError('lowerLeft must be specified as a Point instance')
delta = self._transform.inv().image(Point(0,self.getHeight())) + (-1)*lowerLeft
translation = _Transformation( (1,0,0,1,delta.getX(),delta.getY()) )
self._transform = self._transform * translation
self._update( {'transformation' : self._transform} )
def saveToFile(self, filename):
"""Save a picture of the current canvas to a file.
The filename extension must be a supported file type.
The standard extentions are either .eps or .ps.
If the Python Imaging Library is installed then addition
supported file types are: .gif, , ,
"""
if not isinstance(filename, str):
raise TypeError('filename must be a string')
if '.' not in filename:
raise ValueError('filename extension should indicate file type')
ext = filename.split('.')[-1].lower()
if not _pilAvailable:
choices = ('eps', 'ps')
else:
choices = ('eps', 'ps', 'gif', 'jpg', 'jpeg', 'png')
if ext not in choices:
raise ValueError('Unsupported file type. Choices: ' + ' '.join(choices))
if ext in ('eps','ps'):
epsFilename = filename
else:
fd, epsFilename = _tempfile.mkstemp('.eps')
_os.close(fd)
_graphicsManager.executeFunction( ('save to file', self, epsFilename,
self.getBackgroundColor()) )
if ext not in ('eps','ps'): # Use PIL to convert
image = _Image.open(epsFilename).convert('RGBA')
image.save(filename)
_os.remove(epsFilename)
def getMouseCoordinates(self):
"""Return the current coordinate of the mouse."""
return self._mouseCoordinates
class _RenderedCanvas(object):
def __init__(self, chain, properties):
if _DEBUG['Tkinter'] >= 1:
print (‘Tkinter making rendered canvas’)
self._parent = chain[-1][0]
self._tkWin = _Tkinter.Toplevel()
self._tkWin.protocol(‘WM_DELETE_WINDOW’, self._parent._forceClose)
self._tkWin.title(properties[‘title’])
self._w = properties[‘width’]
self._h = properties[‘height’]
self._canvas = _Tkinter.Canvas(self._tkWin, width=self._w, height=self._h,
highlightthickness=0,
background=Color._getTkColor(properties[‘background color’]))
self._canvas.pack(expand=False, side=_Tkinter.TOP)
self._tkWin.resizable(0,0)
# Setup function to deal with events
# Is this getting called? Seems suspcious
#Essentially makes a function on the fly
callback = lambda event : self._handleEvent(event)
self._canvas.bind(‘
def _handleEvent(self, event):
if _DEBUG[‘Events’] >= 1 and int(event.type) == 4:
print (‘The following is the currentThread in _handleEvent’)
print (_threading.currentThread())
#This will get run repeatedly with mouseover
# Create the event
e = Event()
if not _graphicsManager._mousePrevPosition:
e._prevx, e._prevy = event.x, event.y
else:
e._prevx, e._prevy = _graphicsManager._mousePrevPosition[0], _graphicsManager._mousePrevPosition[1]
_graphicsManager._mousePrevPosition = (int(event.x), int(event.y))
e._x, e._y = event.x, event.y
# Set the mouse coordinates
# TODO must deal with tranformations for top level on all coordinates
self._parent._mouseCoordinates = Point(e._x, e._y)
# Find the shape where the event occurred:
tkIds = self._canvas.find_overlapping(event.x, event.y, event.x, event.y)
if len(tkIds) > 0:
chain = _graphicsManager._objectIdRegistry[(self._canvas, tkIds[-1])]._chain
else:
chain = ((self._parent,Canvas),)
handlers = {} # map from handler to defining (subchain,trigger)
for i in range(len(chain),0,-1):
subchain = chain[:i]
for h in _graphicsManager._eventHandlers.get(subchain[-1][0],set()):
handlers.setdefault(h, subchain) # don’t overwrite higher-level chains
for (h,subchain) in handlers.items():
e._trigger = subchain[-1][0]
transformedEvent = _copy.copy(e)
# QUESTION: does this work when object has nested chains because of nested _draw with inheritance?
cumInv = _graphicsManager._renderedHierarchy.getNode(subchain)._cumulativeTransformation.inv()
local = _graphicsManager._renderedHierarchy.getNode(subchain)._transformation
trans = local.image(e._trigger._reference) # TODO make property; not thread safe
p = local.image(cumInv.image(Point(e._x, e._y)))
transformedEvent._x = p._x – trans._x
transformedEvent._y = p._y – trans._y
#Something should be checking queue to pull stuff and process
_graphicsManager.addEventToQueue(h, transformedEvent)
# Layer class
class Layer(Drawable, _GraphicsContainer):
“””A composite that represents a group of shapes as a single drawable object.
Objects are placed onto the layer relative to the coordinate
system of the layer itself. The layer can then be placed onto a
canvas (or even onto another layer).
“””
def __init__(self):
“””Construct a new Layer instance.
The layer is initially empty.
The reference point of that layer is initially the origin in
its own coordinate system, (0,0).
“””
super(Layer, self).__init__()
self._final = False
def finalize(self):
“””Finalize the layer.
Once finalized, objects can no longer be added or deleted.
“””
self._final = True
def add(self, drawable):
“””Add the Drawable object to the layer.”””
if _DEBUG[‘Front’] >= 1: print(‘\nCall to Layer.add with self=’+str(self)+’ drawable=’+str(drawable))
if self._final:
raise Exception(‘cannot add objects once finalized’)
if not isinstance(drawable, Drawable):
raise TypeError(‘parameter must be an instance of a Drawable object’)
if drawable in self._contents:
raise ValueError(‘object is already on the Layer’)
if ‘_transform’ not in vars(drawable):
raise Exception(‘Drawable not properly initialized (was parent constructor called?)’)
try:
drawable._draw
except KeyboardInterrupt:
raise
except:
raise Exception(‘Drawable class must have a _draw method’)
_GraphicsContainer.add(self, drawable)
def remove(self, drawable):
“””Remove the Drawable object from the layer.
A ValueError is raised if the drawable is not currently in the layer.
“””
if self._final:
raise Exception(‘cannot remove objects once finalized’)
if drawable not in self._contents:
raise ValueError(‘object not currently on the Layer’)
_GraphicsContainer.remove(self,drawable)
def clear(self):
“””Remove all objects from the layer.”””
if self._final:
raise Exception(‘cannot remove objects once finalized’)
_GraphicsContainer.clear(self)
def _draw(self):
for shape in self._contents: # according to inserted order
shape._draw()
class Circle(FillableShape):
“””A circle that can be drawn to a canvas.”””
def __init__(self, radius=10, centerPt=None):
“””Construct a new instance of Circle.
radius the circle’s radius (default 10)
centerPt a Point representing the placement of the circle’s center
(default Point(0,0) )
The reference point for a circle is originally its center.
“””
if not isinstance(radius, (int,float)):
raise TypeError(‘radius must be numeric’)
if radius <= 0:
raise ValueError("radius must be positive")
if centerPt and not isinstance(centerPt, Point):
raise TypeError("circle's center must be specified as a Point")
super(Circle, self).__init__()
if not centerPt:
centerPt = Point()
oldBorderWidth = self.getBorderWidth()
self._transform = _Transformation( (radius,0.,0.,radius,centerPt.getX(),centerPt.getY()) )
self._borderWidth = oldBorderWidth / self._transform.scale()
def setRadius(self, r):
"""Set the radius of the circle to r."""
if not isinstance(r, (int,float)):
raise TypeError('radius must be numeric')
if r <= 0:
raise ValueError("radius must be positive")
factor = float(r)/self.getRadius()
oldBorderWidth = self.getBorderWidth()
self._transform = self._transform * _Transformation((factor,0.,0.,factor,0.,0.))
self._borderWidth = oldBorderWidth / self._transform.scale()
self._update({'transformation': self._transform, 'border width': self._borderWidth})
def getRadius(self):
"""Return the radius of the circle."""
return _math.sqrt(self._transform._matrix[0]**2 + self._transform._matrix[1]**2)
def _draw(self): pass # required for our built-in concrete drawables
class Ellipse(FillableShape):
"""A ellipse that can be drawn to a canvas."""
def __init__(self, w=10, h=10, centerPt=None):
"""Construct a new instance of Circle.
w the ellipse's width (default 10)
h the ellipse's height (default 10)
centerPt a Point representing the placement of the circle's center
(default Point(0,0) )
The reference point for a ellipse is originally its center.
"""
if not isinstance(w, (int,float)):
raise TypeError('width must be numeric')
if w <= 0:
raise ValueError('width must be positive')
if not isinstance(h, (int,float)):
raise TypeError('height must be numeric')
if h <= 0:
raise ValueError('height must be positive')
if centerPt and not isinstance(centerPt, Point):
raise TypeError("center must be specified as a Point")
super(Ellipse, self).__init__()
if not centerPt:
centerPt = Point()
oldBorderWidth = self.getBorderWidth()
self._transform = _Transformation( (.5*w, 0., 0., .5*h, centerPt.getX(), centerPt.getY()) )
self._borderWidth = oldBorderWidth / self._transform.scale()
def getWidth(self):
"""Return the width of the ellipse."""
return 2*_math.sqrt(self._transform._matrix[0]**2 + self._transform._matrix[2]**2)
def getHeight(self):
"""Return the height of the ellipse."""
return 2*_math.sqrt(self._transform._matrix[1]**2 + self._transform._matrix[3]**2)
def setWidth(self, w):
"""Set the width of the ellipse to w."""
if not isinstance(w, (int,float)):
raise TypeError('width must be numeric')
if w <= 0:
raise ValueError("width must be positive")
factor = float(w)/self.getWidth()
oldBorderWidth = self.getBorderWidth()
self._transform = self._transform * _Transformation((factor,0.,0.,1.,0.,0.))
self._borderWidth = oldBorderWidth / self._transform.scale()
self._update({'transformation': self._transform, 'border width': self._borderWidth})
def setHeight(self, h):
"""Set the height of the ellipse to h."""
if not isinstance(h, (int,float)):
raise TypeError('height must be numeric')
if h <= 0:
raise ValueError("height must be numeric")
factor = float(h)/self.getHeight()
oldBorderWidth = self.getBorderWidth()
self._transform = self._transform * _Transformation((1.,0.,0.,factor,0.,0.))
self._borderWidth = oldBorderWidth / self._transform.scale()
self._update({'transformation': self._transform, 'border width': self._borderWidth})
def _draw(self): pass # required for our built-in concrete drawables
class Rectangle(FillableShape):
"""A rectangle that can be drawn to the canvas."""
def __init__(self, w=20, h=10, centerPt=None):
"""
Construct a new instance of a Rectangle.
The reference point for a rectangle is its center.
w the width of the rectangle (default 20)
h the height of the rectangle (default 10)
centerPt a Point representing the placement of the rectangle's center
(default Point(0,0) )
"""
if not isinstance(w, (int,float)):
raise TypeError('width must be numeric')
if w <= 0:
raise ValueError('width must be positive')
if not isinstance(h, (int,float)):
raise TypeError('height must be numeric')
if h <= 0:
raise ValueError('height must be positive')
if centerPt and not isinstance(centerPt, Point):
raise TypeError('center must be specified as a Point')
super(Rectangle, self).__init__() # intentionally not sending center point
if not centerPt:
centerPt = Point(0,0)
oldBorderWidth = self.getBorderWidth()
self._transform = _Transformation( (w, 0., 0., h, centerPt.getX(), centerPt.getY()) )
self._borderWidth = oldBorderWidth / self._transform.scale()
def getWidth(self):
"""Return the width of the rectangle."""
return _math.sqrt(self._transform._matrix[0]**2 + self._transform._matrix[2]**2)
def getHeight(self):
"""Return the height of the rectangle."""
return _math.sqrt(self._transform._matrix[1]**2 + self._transform._matrix[3]**2)
def setWidth(self, w):
"""Set the width of the rectangle to w."""
if not isinstance(w, (int,float)):
raise TypeError('width must be a positive number')
if w <= 0:
raise ValueError("width must be positive")
factor = float(w) / self.getWidth()
oldBorderWidth = self.getBorderWidth()
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
sca = _Transformation((factor,0.,0.,1.,0.,0.))
self._transform = trans*(sca*(trans.inv()*self._transform))
self._borderWidth = oldBorderWidth / self._transform.scale()
self._update({'transformation': self._transform, 'border width': self._borderWidth})
def setHeight(self, h):
"""Set the height of the rectangle to h."""
if not isinstance(h, (int,float)):
raise TypeError('height must be a positive number')
if h <= 0:
raise ValueError("height must be positive")
factor = float(h) / self.getHeight()
oldBorderWidth = self.getBorderWidth()
p = self._localToGlobal(self._reference)
trans = _Transformation((1.,0.,0.,1.)+p.get())
sca = _Transformation((1.,0.,0.,factor,0.,0.))
self._transform = trans*(sca*(trans.inv()*self._transform))
self._borderWidth = oldBorderWidth / self._transform.scale()
self._update({'transformation': self._transform, 'border width': self._borderWidth})
def _draw(self): pass # required for our built-in concrete drawables
class Square(Rectangle):
"""A square that can be drawn to the canvas."""
def __init__(self, size=10, centerPt=None):
"""
Construct a new Square instance.
The reference point for a square is its center.
size the dimension of the square (default 10)
centerPt a Point representing the placement of the rectangle's center
(defaults Point(0,0) )
"""
if not isinstance(size, (int,float)):
raise TypeError('size must be numeric')
if size <= 0:
raise ValueError('size must be positive')
if centerPt and not isinstance(centerPt, Point):
raise TypeError('center must be specified as a Point')
super(Square, self).__init__()
self.setSize(size)
if centerPt is not None:
self.moveTo(centerPt.getX(), centerPt.getY())
def getSize(self):
"""Return the length of a side of the square."""
return self.getWidth()
def setSize(self, s):
"""Set the width and height of the square to s."""
if not isinstance(s, (int,float)):
raise TypeError('size must be numeric')
if s <= 0:
raise ValueError('size must be positive')
# TODO: Could do freeze/unfreeze to make atomic (if not currently frozen)
Rectangle.setWidth(self, s)
Rectangle.setHeight(self, s)
def setWidth(self, w):
"""Set the width and height of the square to w."""
if not isinstance(w, (int,float)):
raise TypeError('width must be numeric')
if w <= 0:
raise ValueError("width must be positive")
self.setSize(w)
def setHeight(self, h):
"""Set the width and height of the square to h."""
if not isinstance(h, (int,float)):
raise TypeError('height must be numeric')
if h <= 0:
raise ValueError("height must be positive")
self.setSize(h)
class Path(Shape):
"""A path that can be drawn to a canvas."""
def __init__(self, *points):
"""Construct a new instance of a Path.
The path is described as a series of points that are connected in order.
These points can be initialized by sending each individual Point
as a separate parameter, or by sending a single parameter
containing a sequence of Points. If no parameters are sent, the
path initially has zero points.
The reference point for a path is initially aligned with the first
point of the path.
"""
super(Path, self).__init__()
if len(points) == 1:
try:
points = tuple(points[0])
except TypeError:
pass # original parameter might be a single Point
for p in points:
if not isinstance(p, Point):
raise TypeError('non-Point specified as parameter')
self._points = list(points)
if len(self._points) >= 1:
self.adjustReference(self._points[0].getX(), self._points[0].getY())
self._final = False
self._arrows = (False,False)
def _getProperties(self):
prop = super(Path, self)._getProperties()
prop[‘points’] = tuple(self._points)
prop[‘arrows’] = self._arrows
return prop
def finalize(self):
“””Finalize the shape.
Once finalized, points can no longer be added, deleted, or modified.
“””
self._final = True
def addPoint(self, point, index=-1):
“””Add a new point to the Path.
point a Point instance
index designates where on the path the new point is placed
(default at the end)
“””
if self._final:
raise Exception(‘cannot add points once finalized’)
if not isinstance(point, Point):
raise TypeError(‘parameter must be a Point instance’)
if index > -1:
self._points.insert(index, point)
else:
self._points.append(point)
if len(self._points) == 1: # first point added
self._reference = Point(point.getX(), point.getY())
self._update({‘points’: tuple(self._points)})
def deletePoint(self, index=-1):
“””Remove the Point at the given index.
By default, deletes the last point.
“””
if self._final:
raise Exception(‘cannot delete points once finalized’)
if not isinstance(index, int):
raise TypeError(‘index must be an integer’)
try:
self._points.pop(index)
except IndexError:
raise IndexError(‘index out of range’)
self._update({‘points’: tuple(self._points)})
def clearPoints(self):
“””Remove all points, setting this back to an empty Path.”””
if self._final:
raise Exception(‘cannot clear points once finalized’)
self._points = list()
self._update({‘points’: tuple(self._points)})
def getNumberOfPoints(self):
“””Return the current number of points.”””
return len(self._points)
def getPoint(self, index):
“””Return a copy of the Point at the given index.
Subsequently mutating that copy has no effect on the Path.
“””
if not isinstance(index, int):
raise TypeError(‘index must be an integer’)
try:
p = self._points[index]
except IndexError:
raise IndexError(‘index out of range’)
return Point(p.getX(), p.getY())
def setPoint(self, point, index=-1):
“””Change the Point at the given index to a new value.
By default, the last point is changed.
“””
if self._final:
raise Exception(‘cannot modify points once finalized’)
if not isinstance(index, int):
raise TypeError(‘index must be an integer’)
if not isinstance(point, Point):
raise TypeError(‘first parameter must be a Point instance’)
try:
self._points[index] = point
except IndexError:
raise IndexError(‘index out of range’)
self._update({‘points’: tuple(self._points)})
def getPoints(self):
“””Return a list of Point instances that are copies of the points on the Path.”””
return list(self._points)
def setArrows(self, forward, reverse=False):
“””Change setting for whether arrows are drawn at beginning and end of path.
If forward is True, will draw an arrow at the last point on the path.
Otherwise, no such arrow is drawn.
If reverse is True, will draw a reverse arrow eminating from
the first point on the path; otherwise (the default), no such
arrow is drawn.
Note: arrows are never displayed for Polygon or ClosedSpline instances
“””
self._arrows = (forward,reverse)
self._update({‘arrows’ : self._arrows})
def _draw(self): pass # required for our built-in concrete drawables
def _addBatchPoints(self, *points):
if len(points) == 1:
try:
points = tuple(points[0])
except TypeError:
pass # original parameter might be a single Point
for p in points:
try:
self.addPoint(p)
except TypeError:
raise
class Polygon(Path,FillableShape):
“””A polygon that can be drawn to a canvas.”””
def __init__(self, *points):
“””Construct a new Polygon instance.
The polygon is described as a series of points that are connected in order.
The last point is automatically connected back to the first to close the polygon.
These points can be initialized by sending each individual Point
as a separate parameter, or by sending a single parameter
containing a sequence of Points. If no parameters are sent, the
polygon initially has zero points.
The reference point for a polygon is initially aligned with the
first point of the polygon.
“””
super(Polygon, self).__init__()
self._addBatchPoints(*points)
def _getProperties(self): # need aspects of both parents
prop = super(Polygon, self)._getProperties()
return prop
def _draw(self): pass # required for our built-in concrete drawables
class Spline(Path):
“””A curved path that can be drawn to a canvas.”””
def __init__(self, *points):
“””
Construct a new instance of a Spline.
The spline is described as a series of points that are connected in order
with curves.
These points can be initialized by sending each individual Point
as a separate parameter, or by sending a single parameter
containing a sequence of Points. If no parameters are sent, the
path initially has zero points.
The reference point for a spline is initially aligned with the first
point of the spline.
“””
#Quick solution, check Polygon same code
#Better solution: path has private method: _batchPoints takes parameter
#points
super(Spline, self).__init__()
try:
self._addBatchPoints(*points)
except TypeError:
raise
def _getProperties(self):
prop = super(Spline, self)._getProperties()
prop[‘smooth’] = True # need key, but value is really irrelevant
return prop
class ClosedSpline(Polygon):
“””A closed curve that can be drawn to a canvas.”””
def __init__(self, *points):
“””Construct a new ClosedSpline instance.
The cuved spline is described as a series of points that are connected in order.
The last point is automatically connected back to the first to close the spline.
These points can be initialized by sending each individual Point
as a separate parameter, or by sending a single parameter
containing a sequence of Points. If no parameters are sent, the
polygon initially has zero points.
The reference point for a closed spline is initially aligned with the
first point of the spline.
“””
super(ClosedSpline, self).__init__()
try:
self._addBatchPoints(*points)
except TypeError:
raise
def _getProperties(self):
prop = super(ClosedSpline, self)._getProperties()
prop[‘smooth’] = True # need key, but value is really irrelevant
return prop
class Text(Drawable):
“””A piece of text that can be drawn to a canvas.”””
def __init__(self, message=”, fontsize=12, centerPt=None):
“””
Construct a new Text instance.
The text color is initially black, although this can be changed by
setColor. The reference point for the text is initially its center.
message a string which is to be displayed (default empty string)
fontsize the font size (default 12)
centerPt where to locate the center of the text (default Point(0,0) )
By default, multiline text will be left-justified, although
this style can be changed by the setJustification method.
“””
if not isinstance(message, basestring):
raise TypeError(‘message must be a string’)
if not isinstance(fontsize, (int,float)):
raise TypeError(‘fontsize must be numeric’)
if fontsize <= 0:
raise ValueError('fontsize must be positive')
if centerPt and not isinstance(centerPt, Point):
raise TypeError('center must be a Point')
super(Text, self).__init__()
self._text = message
self._size = fontsize
self._color = Color('black')
self._color._register(self, 'font color')
if centerPt:
self.move(centerPt.getX(), centerPt.getY())
self._justify = 'left'
def __deepcopy__(self, memo={}):
temp = Drawable.__deepcopy__(self, memo)
temp._color = self._color # do shallow copy
temp._color._register(temp, 'font color')
return temp
def _draw(self): pass # required for our built-in concrete drawables
def _getProperties(self):
prop = super(Text, self)._getProperties()
prop.update( { 'message' : self._text, 'font color' : Color(self._color),
'font size' : self._size, 'justify' : self._justify } )
return prop
def setMessage(self, message):
"""Set the string to be displayed.
message a string
"""
if not isinstance(message, basestring):
raise TypeError('message must be a string')
self._text = message
self._update({'message': message})
def getMessage(self):
"""Return the current string."""
return self._text
def setFontColor(self, color):
"""Set the color of the font.
The parameter can be either:
- a string with the name of the color
- an (r,g,b) tuple
- an existing Color instance
"""
if self._color is not color:
old = self._color
if isinstance(color, Color):
self._color = color
else:
try:
self._color = Color(color)
except (TypeError, ValueError):
raise
old._unregister(self, 'font color')
self._color._register(self, 'font color')
self._update({'font color': Color(self._color)})
def getFontColor(self):
"""Return the current font color."""
return self._color
def setFontSize(self, fontsize):
"""Set the font size."""
if not isinstance(fontsize, (int,float)):
raise TypeError('fontsize must be numeric')
if fontsize <= 0:
raise ValueError('fontsize must be positive')
self._size = fontsize
self._update({'font size': self._size})
def getFontSize(self):
"""Return the current font size."""
return self._size
def scale(self, factor):
"""Scale the object relative to its current reference point.
factor scale is multiplied by this number (must be positive)
"""
if not isinstance(factor, (int,float)):
raise TypeError('scaling factor must be a positive number')
if factor <= 0:
raise ValueError('scaling factor must be a positive number')
super(Text,self).scale(factor) # transform is really irrelevant, but leaving this to support multiple inheritance between Text and some other shape
self._size *= factor
self._update({'font size': self._size})
def rotate(self,angle):
"""Not yet implemented."""
raise NotImplementedError('rotating text is not yet implemented')
def stretch(self,xFactor,yFactor,angle=0):
"""Not yet implemented."""
raise NotImplementedError('stretching text is not yet implemented')
def flip(self,angle=0):
"""Not yet implemented."""
raise NotImplementedError('fliping text is not yet implemented')
def shear(self, shear, angle=0):
"""Not yet implemented."""
raise NotImplementedError('shearing text is not yet implemented')
def getDimensions(self):
"""Return a (width,height) tuple measuring visual dimensions of currently displayed message."""
return _graphicsManager.executeFunction( ('get text size', self._text, self._size) )
def setJustification(self, style):
"""Set the justifcation style for multiline text.
style must be either 'left', 'right', or 'center'
By default, text is center justified.
"""
if not isinstance(style, basestring):
raise TypeError('style must be a string')
if style not in ('left', 'right', 'center'):
raise ValueError("style must be 'left', 'right', or 'center'")
self._justify = style
self._update({'justify': style})
class Image(Drawable):
"""A wrapper for images that can be drawn to a canvas and manipulated."""
def __init__(self, *args):
"""Construct a new Image instance.
If invoked as Image(filename), the image will be constructed
based on the contents of an underlying image file.
gif format should be supported universally; support for
additional image formats (e.g., jpg) will be system dependent.
Install Pythin Image Library (PIL) for more options.
If invoked as Image(width, height), a new image is created
with the given dimensions, and with all pixels are initially
Transparent.
Once it is constructed, the virtual width and height of the
image is fixed, and a coordinate system is used for accessing
individual pixels of the image.
However, the virtual image may be rendered at any size on a
Canvas through use of methods such as scale inherited from Drawable.
The center of the image is initially aligned with Point(0,0).
"""
super(Image, self).__init__()
if not 1 <= len(args) <= 2:
raise TypeError('must either specify a filename or integer width and height')
if len(args) == 2:
for k in (0,1):
if not isinstance(args[k], int):
msg = ('width','height')[k] + ' must be an integer'
raise TypeError(msg)
if args[k] <= 0:
msg = ('width','height')[k] + ' must be positive'
raise ValueError(msg)
self._w = args[0]
self._h = args[1]
self._data = _array('B', [255]) * (3 * self._w * self._h)
self._alpha = _array('B', [0]) * ((self._w * self._h + 7)// 8) # bitfield (all transparent)
self._image = None
if len(args) == 1:
# TODO: add back in base64 encoded strings for initialization? (from KAIST)
if not isinstance(args[0], basestring):
raise TypeError('filename must be a string')
result = _graphicsManager.executeFunction( ('load image', args[0]) )
if result is None:
raise ValueError('unable to load image file: ' + args[0])
self._image, self._w, self._h = result
self._data = self._alpha = _array('B')
def _draw(self): pass # required for our built-in concrete drawables
def _getProperties(self):
prop = super(Image, self)._getProperties()
prop.update( { 'width' : self._w, 'height' : self._h, 'image' : self._image,
'data' : self._data[:], 'alpha' : self._alpha[:] } )
return prop
def getWidth(self):
"""Return the number of pixels per row in the original coordinate space."""
return self._w
def getHeight(self):
"""Return the number of pixels per column in the original coordinate space."""
return self._h
def getPixel(self, x, y):
"""Returns a copy of the color at the specified pixel."""
if not isinstance(x, int):
raise TypeError('x must be integral')
if not 0 <= x < self._w:
raise ValueError('x is invalid index')
if not isinstance(y, int):
raise TypeError('y must be integral')
if not 0 <= y < self._h:
raise ValueError('y is invalid index')
if len(self._data) == 0: # lazy conversion
self._data, self._alpha = \
_graphicsManager.executeFunction( ('convert image', self._image) )
scalar = x + self._w * y
a,b = divmod(scalar, 8)
if self._alpha[a] & (1 << b):
return Color(tuple(self._data[3*scalar:3*(scalar+1)]))
else:
return Color('transparent')
def setPixel(self, x, y, color):
"""Set the specified pixel to the given color.
The parameter can be either:
- a string with the name of the color
- an (r,g,b) tuple
- an existing Color instance (which will be copied)
Note: Images are intentionally implemented so that individual
calls to setPixel are not immediately rendered. You must call
updatePixels() to force all changes to be rendered.
"""
if not isinstance(x, int):
raise TypeError('x must be integral')
if not 0 <= x < self._w:
raise ValueError('x is invalid index')
if not isinstance(y, int):
raise TypeError('y must be integral')
if not 0 <= y < self._h:
raise ValueError('y is invalid index')
try:
c = Color(color)
except (TypeError, ValueError):
raise
scalar = x + self._w * y
a,b = divmod(scalar, 8)
if len(self._data) == 0: # lazy conversion
self._data, self._alpha = \
_graphicsManager.executeFunction( ('convert image', self._image) )
if c == Color('transparent'):
self._alpha[a] &= (255-(1 << b)) # set alpha to zero
else:
rgb = [int(k) for k in c.getColorValue()]
self._data[3*scalar:3*(scalar+1)] = _array('B', rgb)
self._alpha[a] |= (1 << b) # set alpha to one
def updatePixels(self):
"""Re-render the image to reflect current pixel settings."""
self._update({'data': self._data[:], 'alpha' : self._alpha[:]})
# Rendered shapes
class _RenderedDrawable(object):
def __init__(self, chain, properties):
self._chain = chain
self._canvas = _graphicsManager._renderedHierarchy.getNode(chain[:1])._renderedDrawable
self._object = None
def putAbove(self, other):
if other is not None:
if _DEBUG['Tkinter'] >= 2: print(‘calling lift(‘+str(self._object)+’,’+str(other._object)+’)’)
self._canvas._canvas.lift(self._object, other._object)
else: # Put at bottom
if _DEBUG[‘Tkinter’] >= 2: print(‘calling lower(‘+str(self._object)+’)’)
self._canvas._canvas.lower(self._object)
def update(self, properties):
if _DEBUG[‘Tkinter’] >= 2: print(‘Updating _RenderedDrawable’)
pass
def remove(self):
self._canvas._canvas.delete(self._object)
class _RenderedShape(_RenderedDrawable):
def __init__(self, chain, properties):
super(_RenderedShape, self).__init__(chain, properties)
self._width = self._transWidth = self._dash = self._borderColor = None
def update(self, properties):
configs = {} # will eventually send entries to itemconfigure
# deal with silly Tk conventions
if isinstance(self, _RenderedFillableShape):
colorProp = ‘outline’
else:
colorProp = ‘fill’
if ‘border width’ in properties or ‘transformation’ in properties:
# effective width may have changed
w = properties.get(‘border width’, self._width)
if w != self._width:
if w == 0: # changing from nonzero to zero
configs[colorProp] = ”
self._transWidth = 0
elif self._width == 0: # changing from zero to nonzero!
configs[colorProp] = Color._getTkColor(properties.get(‘border color’,self._borderColor))
self._width = w
if w != 0: # recompute transformed width
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
self._transWidth = w * transform.scale()
configs[‘width’] = self._transWidth
if self._dash is not None and self._dash[1] != 0:
a = min(255, max(1, int(round(self._dash[0]*self._transWidth/self._width))))
b = min(255, max(1, int(round(self._dash[1]*self._transWidth/self._width))))
# for some reason, (a,b,a,b) tuple works better than (a,b) tuple for Tkinter
configs[‘dash’] = (a,b) * _dashMultiplier
if ‘border color’ in properties:
self._borderColor = properties[‘border color’]
c = Color._getTkColor(self._borderColor)
if self._width != 0: # border is currently rendered
configs[colorProp] = c
if ‘dash’ in properties and properties[‘dash’] != self._dash:
self._dash = properties[‘dash’]
if self._dash[1] == 0:
configs[‘dash’] = ”
else:
a = min(255, max(1, int(round(self._dash[0]*self._transWidth/self._width))))
b = min(255, max(1, int(round(self._dash[1]*self._transWidth/self._width))))
# for some reason, (a,b,a,b) tuple works better than (a,b) tuple for Tkinter
configs[‘dash’] = (a,b) * _dashMultiplier
self._canvas._canvas.itemconfigure(self._object, **configs)
_RenderedDrawable.update(self, properties)
class _RenderedFillableShape(_RenderedShape):
def __init__(self, chain, properties):
super(_RenderedFillableShape, self).__init__(chain, properties)
self._fillColor = None
def update(self, properties):
if ‘fill color’ in properties:
self._fillColor = properties[‘fill color’]
self._canvas._canvas.itemconfigure(self._object, fill=Color._getTkColor(self._fillColor))
_RenderedShape.update(self, properties)
class _RenderedCircle(_RenderedFillableShape):
def __init__(self, chain, properties):
super(_RenderedCircle, self).__init__(chain, properties)
transform = _graphicsManager._renderedHierarchy.getNode(chain)._cumulativeTransformation
points = []
for i in range(0,360,5):
points.append(Point(1,0) ^ i)
statement = ‘self._object = self._canvas._canvas.create_polygon(‘
for p in points:
statement += str(transform.image(p).getX()) + ‘, ‘ + str(transform.image(p).getY()) + ‘, ‘
statement += ‘smooth=1)’
exec(statement)
_graphicsManager._objectIdRegistry[(self._canvas._canvas,self._object)] = self
_RenderedFillableShape.update(self, properties)
def update(self, properties):
if ‘transformation’ in properties:
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
points = []
for i in range(0,360,5):
points.append(Point(1,0) ^ i)
statement = ‘self._canvas._canvas.coords(self._object’
for p in points:
statement += ‘, ‘ + str(transform.image(p).getX()) + ‘, ‘ + str(transform.image(p).getY())
statement += ‘)’
exec(statement)
_RenderedFillableShape.update(self, properties)
class _RenderedRectangle(_RenderedFillableShape):
def __init__(self, chain, properties):
super(_RenderedRectangle, self).__init__(chain, properties)
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
points = [Point(-.5,-.5), Point(-.5,.5), Point(.5,.5), Point(.5,-.5)]
for i in range(4):
points[i] = transform.image(points[i])
self._object = self._canvas._canvas.create_polygon(points[0].get(), points[1].get(), points[2].get(), points[3].get())
_graphicsManager._objectIdRegistry[(self._canvas._canvas,self._object)] = self
_RenderedFillableShape.update(self, properties)
def update(self, properties):
if ‘transformation’ in properties:
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
points = [Point(-.5,-.5), Point(-.5,.5), Point(.5,.5), Point(.5,-.5)]
for i in range(4):
points[i] = transform.image(points[i])
self._canvas._canvas.coords(self._object, points[0].getX(), points[0].getY(), points[1].getX(), points[1].getY(),
points[2].getX(), points[2].getY(), points[3].getX(), points[3].getY())
_RenderedFillableShape.update(self, properties)
class _RenderedPath(_RenderedShape):
def __init__(self, chain, properties):
super(_RenderedPath, self).__init__(chain, properties)
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
self._points = properties[‘points’]
if len(self._points) > 1:
tkPts = [(transform.image(p).getX(),transform.image(p).getY()) for p in self._points]
else:
tkPts = [(0,0)] * 3
self._object = self._canvas._canvas.create_line(tkPts)
_graphicsManager._objectIdRegistry[(self._canvas._canvas,self._object)] = self
_RenderedShape.update(self, properties)
configs = {}
if ‘smooth’ in properties:
configs[‘smooth’] = 1
if ‘arrows’ in properties:
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
w = transform.scale()*properties[‘border width’]
configs[‘arrowshape’] = str(w*8) + ‘ ‘ + str(w*10) + ‘ ‘ + str(w*3)
pair = properties[‘arrows’]
if pair[0] and pair[1]:
configs[‘arrow’] = ‘both’
elif pair[0]:
configs[‘arrow’] = ‘last’
elif pair[1]:
configs[‘arrow’] = ‘first’
if not self._points: # make effectively invisible TK object with width 0
configs.update( {‘fill’ : None, ‘width’ : 0} )
if configs:
self._canvas._canvas.itemconfigure(self._object, **configs)
def update(self, properties):
_RenderedShape.update(self, properties)
configs = {}
if ‘transformation’ in properties or ‘points’ in properties:
wasEmpty = len(self._points) < 2
self._points = properties.get('points', self._points) # update if given
if len(self._points) > 1:
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
tkCoords = []
for p in self._points:
tkCoords.append(transform.image(p).getX())
tkCoords.append(transform.image(p).getY())
tkCoords = tuple(tkCoords)
if wasEmpty: # need to explicitly (re)set border properties
configs[‘width’] = self._transWidth
configs[‘fill’] = Color._getTkColor(self._borderColor)
else:
tkCoords = 6 * (0,)
self._canvas._canvas.coords(self._object,tuple(tkCoords))
if ‘transformation’ in properties or ‘border width’ in properties:
w = self._transWidth
configs[‘arrowshape’] = str(w*8) + ‘ ‘ + str(w*10) + ‘ ‘ + str(w*3)
if ‘arrows’ in properties:
pair = properties[‘arrows’]
if pair[0] and pair[1]:
configs[‘arrow’] = ‘both’
elif pair[0]:
configs[‘arrow’] = ‘last’
elif pair[1]:
configs[‘arrow’] = ‘first’
else:
configs[‘arrow’] = ‘none’
if not self._points: # make effectively invisible TK object with width 0
configs.update( {‘fill’ : None, ‘width’ : 0} )
if configs:
self._canvas._canvas.itemconfigure(self._object, **configs)
class _RenderedPolygon(_RenderedFillableShape):
def __init__(self, chain, properties):
super(_RenderedPolygon, self).__init__(chain, properties)
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
self._points = properties[‘points’]
if len(self._points) > 1:
tkPts = [(transform.image(p).getX(),transform.image(p).getY()) for p in self._points]
else:
tkPts = [(0,0)] * 3
self._object = self._canvas._canvas.create_polygon(tkPts)
_graphicsManager._objectIdRegistry[(self._canvas._canvas,self._object)] = self
if ‘smooth’ in properties:
self._canvas._canvas.itemconfigure(self._object, smooth=1)
_RenderedFillableShape.update(self, properties)
if not self._points: # make effectively invisible TK object with width 0
self._canvas._canvas.itemconfigure(self._object, fill=None, width=0)
def update(self, properties):
_RenderedFillableShape.update(self, properties)
configs = {}
if ‘transformation’ in properties or ‘points’ in properties:
wasEmpty = len(self._points) < 2
self._points = properties.get('points', self._points) # update if given
if len(self._points) > 1:
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
tkCoords = []
for p in self._points:
tkCoords.append(transform.image(p).getX())
tkCoords.append(transform.image(p).getY())
tkCoords = tuple(tkCoords)
if wasEmpty: # need to explicitly (re)set border properties
configs[‘width’] = self._transWidth
configs[‘outline’] = Color._getTkColor(self._borderColor)
configs[‘fill’] = Color._getTkColor(self._fillColor)
else:
tkCoords = 6 * (0,)
self._canvas._canvas.coords(self._object,tuple(tkCoords))
if not self._points: # make effectively invisible TK object with width 0
configs.update( {‘fill’ : None, ‘width’ : 0} )
if configs:
self._canvas._canvas.itemconfigure(self._object, **configs)
class _RenderedText(_RenderedDrawable):
normalFactor = 1.0 # re-configured at startup so that 12pt font has approximate height 16-pixels (96 PPI)
def __init__(self, chain, properties):
super(_RenderedText, self).__init__(chain, properties)
transform = _graphicsManager._renderedHierarchy.getNode(chain)._cumulativeTransformation
parentChain = self._getParentChain()
parentTransform = _graphicsManager._renderedHierarchy.getNode(parentChain)._cumulativeTransformation
parentScale = parentTransform.scale()
if not parentTransform.scaleAndTranslate() and parentScale > 0:
raise GraphicsError(‘text cannot be rotated or sheared unless Python Image Library is installed’, True)
center = transform.image(Point(0.,0.))
self._renderedSize = properties[‘font size’]
actualSize = int(round(parentScale * self._renderedSize * _RenderedText.normalFactor))
self._object = self._canvas._canvas.create_text(center.get(), text=properties[‘message’],
anchor=’center’, justify=properties[‘justify’],
fill=Color._getTkColor(properties[‘font color’]),
font=(‘Helvetica’, actualSize, ‘normal’) )
_graphicsManager._objectIdRegistry[(self._canvas._canvas,self._object)] = self
_RenderedDrawable.update(self, properties)
def _getParentChain(self):
“””Determine proper parent chain considering possible inheritance model.”””
parentChain = chain = self._chain
while parentChain and parentChain[-1][0] is chain[-1][0]:
# when subclass of text exists, go back in chain until beyond that object’s entries
parentChain = parentChain[:-1]
return parentChain
def update(self, properties):
if ‘message’ in properties:
self._canvas._canvas.itemconfigure(self._object, text=properties[‘message’])
if ‘font color’ in properties:
self._canvas._canvas.itemconfigure(self._object, fill=Color._getTkColor(properties[‘font color’]))
if ‘justify’ in properties:
self._canvas._canvas.itemconfigure(self._object, justify=properties[‘justify’])
if ‘font size’ in properties:
self._renderedSize = properties[‘font size’]
# will handle the actual resizeing of tkinter in a moment…
if ‘font size’ in properties or ‘transformation’ in properties:
# determine effective size
parentChain = self._getParentChain()
parentTransform = _graphicsManager._renderedHierarchy.getNode(parentChain)._cumulativeTransformation
parentScale = parentTransform.scale()
if parentScale < 0:
# raise GraphicsError('text cannot be reflected unless Python Image Library is installed', True)
raise GraphicsError('text cannot be reflected', True)
actualSize = int(round(parentScale * self._renderedSize * _RenderedText.normalFactor))
self._canvas._canvas.itemconfigure(self._object, font=('Helvetica', actualSize, 'normal'))
if 'transformation' in properties:
# consider translation of text center
parentChain = self._getParentChain()
parentTransform = _graphicsManager._renderedHierarchy.getNode(parentChain)._cumulativeTransformation
if not parentTransform.scaleAndTranslate():
# raise GraphicsError('text cannot be rotated or sheared unless Python Image Library is installed', True)
raise GraphicsError('text cannot be rotated or sheared', True)
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
center = transform.image(Point(0.,0.))
self._canvas._canvas.coords(self._object, center.getX(), center.getY())
_RenderedDrawable.update(self, properties)
class _RenderedImage(_RenderedDrawable):
# need to make sure that this instance buffers the most recently used
# image, transform, and (data,alpha) arrays.
def __init__(self, chain, properties):
super(_RenderedImage, self).__init__(chain, properties)
self._w = properties['width'] # needed for _buildImage
self._h = properties['height']
self._lastData = self._lastAlpha = None
transform = _graphicsManager._renderedHierarchy.getNode(chain)._cumulativeTransformation
center = transform.image(Point(0.,0.))
if properties['data'] or not transform.translateOnly():
# will need to construct image manually
if properties['data']:
data,alpha = properties['data'], properties['alpha']
else:
data,alpha = _convertImage(properties['image'])
self._lastData, self._lastAlpha = data,alpha
img = self._buildImage(data, alpha, transform)
else:
img = properties['image']
self._lastCumulative = transform # used to recognize translationOnly updates
self._lastImage = img # keep reference to avoid garbage collection
self._object = self._canvas._canvas.create_image(center.get(), image=img, anchor='center')
_graphicsManager._objectIdRegistry[(self._canvas._canvas,self._object)] = self
_RenderedDrawable.update(self, properties)
def update(self, properties):
mustRebuild = 'data' in properties
if mustRebuild or 'transformation' in properties:
transform = _graphicsManager._renderedHierarchy.getNode(self._chain)._cumulativeTransformation
delta = transform * self._lastCumulative.inv()
mustRebuild = mustRebuild or not delta.translateOnly()
self._lastCumulative = transform
if not mustRebuild:
# can get away with simple translation with existing image
center = transform.image(Point(0.,0.))
self._canvas._canvas.coords(self._object, center.getX(), center.getY())
if mustRebuild:
if 'data' in properties:
data,alpha = properties['data'], properties['alpha']
elif self._lastData is not None:
data,alpha = self._lastData, self._lastAlpha
else:
data,alpha = _convertImage(self._lastImage)
self._lastData, self._lastAlpha = data,alpha
self._image = self._buildImage(data, alpha, transform)
center = transform.image(Point(0,0))
self._canvas._canvas.itemconfigure(self._object, image=self._image)
_RenderedDrawable.update(self, properties)
def _buildImage(self, data, alpha, transform):
"""Returns a new PhotoImage instance based on the transformed low-level data arrays."""
# TODO: find ways to batch so that there are less individual calls to img.put
minX = maxX = minY = maxY = None
for x,y in ( (self._w,0), (0,self._h), (self._w,self._h), (0,0)): # do origin last!
p = transform.image(Point(x,y))
if minX is None or minX > p.getX():
minX = p.getX()
if maxX is None or maxX < p.getX():
maxX = p.getX()
if minY is None or minY > p.getY():
minY = p.getY()
if maxY is None or maxY < p.getY():
maxY = p.getY()
offset = Point(p.getX()-minX, p.getY()-minY)
rW = int(round(maxX-minX))
rH = int(round(maxY-minY))
img = _Tkinter.PhotoImage(width=rW, height=rH)
img.blank() # TODO: is this necessary for newly constructed image?
for y in range(rH):
for x in range(rW):
result = transform.inv().image(Point(x+minX,y+minY))
# no anti-aliasing in this version
vx = int(round(result.getX()))
vy = int(round(result.getY()))
if 0 <= vx < self._w and 0 <= vy < self._h:
a,b = divmod(self._w * vy + vx, 8)
if alpha[a] & (1 << b):
color = '#%02x%02x%02x'%tuple(data[3*(vx+self._w*vy):3*(1+vx+self._w*vy)])
img.put(data=color, to=(x,y))
return img
# Library initialization and shutdown
def _initLibrary():
if _DEBUG['Tkinter'] >= 2:
print (‘Initializing the Tkinter library’)
global _tkroot
try:
_tkroot = _Tkinter.Tk()
except KeyboardInterrupt:
raise
except:
raise Exception(‘unable to start Tkinter on your system’)
_graphicsManager._state = ‘Failed’
_tkroot.withdraw()
if _DEBUG[‘Tkinter’] > 2:
print (‘actual getting set to _getTextSize’)
actual = _getTextSize(‘X’, 36)[1]
_RenderedText.normalFactor *= 48.0 / actual # this normalizes so that 36-pt font has 48-pixel height (96 PPI)
def _startCommandThread():
_initLibrary()
while _graphicsManager._state == ‘Running’:
_graphicsManager.processCommands()
_graphicsManager.processEvents()
_tkroot.update()
_time.sleep(.01)
def _stopCommandThread():
while len(_graphicsManager._openCanvases) > 0:
_time.sleep(.25)
_graphicsManager._state = ‘Stopped’
_time.sleep(.25)
def _exitMainThread():
# Main loop will return when all open canvases closed
if _graphicsManager._handlingEvents == ‘No’:
_graphicsManager._handlingEvents = ‘Yes’
if len(_graphicsManager._openCanvases) > 0:
print(‘Close canvas windows to end program.’)
_graphicsManager.mainLoop(None, True)
def startEventHandling():
“””
Blocks the main thread and enters event-handling mode.
This can be counteracted by a later call to stopEventHandling().
Note: This should not be called if using native threading.
“””
if not _nativeThreading:
if _graphicsManager._handlingEvents == ‘No’:
_graphicsManager._handlingEvents = ‘Yes’
_graphicsManager.mainLoop()
def stopEventHandling():
“””
Counteracts an earlier call to startEventHandling().
“””
if not _nativeThreading:
if _graphicsManager._handlingEvents == ‘Yes’:
_graphicsManager._handlingEvents = ‘No’
_graphicsManager = _GraphicsManager()
# Utility for Text. This is used once at startup to normalize measure
# and subsequently to support calls to Text.getDimensions()
# it presumes that the lock is already held for the graphics thread
def _getTextSize(message, fontsize):
if _DEBUG[‘Tkinter’] >= 2:
print (‘Tkinter inside _getTextSize’)
tkWin = _Tkinter.Toplevel()
canvas = _Tkinter.Canvas(tkWin)
size = int(round(fontsize * _RenderedText.normalFactor))
i = canvas.create_text(0, 0, text=message, font=(‘Helvetica’, size, ‘normal’) )
bbox = canvas.bbox(i)
canvas.delete(i)
tkWin.withdraw()
return (bbox[2]-bbox[0],bbox[3]-bbox[1])
# Utility for Image Processing
def _convertImage(img):
“””Takes a PhotoImage instance, and produces array pixmap representation.
Formally, returns pair of arrays.
First is array of bytes describing the colors (in row-major
order), and a second array that is used as a bitfield for
transparency representation.
“””
w = img.width()
h = img.height()
a = _array(‘B’, [0]) * (3*w*h)
t = _array(‘B’, [255]) * ((w*h+7)//8) # all True, for lack of better idea
for x in range(w):
for y in range(h):
color = img.get(x,y)
base = 3 * (y*w + x)
a[base:base+3] = _array(‘B’, [int(v) for v in color.split()])
# appears to be no way to differentiate between black and transparent in this context
# If we knew it was transparent, the following is the proper code.
# if color == ‘0 0 0’:
# u,v = divmod(y*w+x,8)
# t[u] &= (255 – (1 << v)) # make transparent
return (a,t)
class Button(Text, Rectangle, EventHandler):
"""A button that can respond to events."""
def __init__(self, message='', centerPt=None):
"""Create a new button.
The width and height of the button automatically adjust
to the size of the displayed text.
message the text to display on the button
centerPt where to place the center of the button
"""
super(Button, self).__init__()
self.setMessage(message) # automatically resizes rectangle
if centerPt is not None:
self.moveTo(centerPt.getX(), centerPt.getY())
self._baseBorderWidth = self._borderWidth
self.setFillColor('white')
self.addHandler(self)
def _resize(self):
w, h = self.getDimensions()
self.setWidth(w+self._size)
self.setHeight(h+self._size)
def handle(self, event):
"""Highlight the button when the button is clicked."""
if _DEBUG['Events'] >= 3:
print(‘Button self handler’)
if event._eventType == ‘mouse click’:
Rectangle.setBorderWidth(self, self._baseBorderWidth + 2)
elif event._eventType == ‘mouse release’:
Rectangle.setBorderWidth(self, self._baseBorderWidth)
def _draw(self):
Rectangle._draw(self)
Text._draw(self)
def setBorderWidth(self, width):
“””
Set the width of the border to the indicated width.
“””
self._baseBorderWidth = width
Rectangle.setBorderWidth(self, width)
def scale(self, factor):
“””Scale the object relative to its current reference point.
factor scale is multiplied by this number (must be positive)
“””
self._baseBorderWidth *= width
super(Button,self).scale(factor)
def setMessage(self, message):
“””Changes the button’s text to message and automatically resizes the button.”””
Text.setMessage(self, message)
self._resize()
def setFontSize(self, fontsize):
“””Changes the button’s text size and automatically resizes the button.”””
Text.setFontSize(self, fontsize)
self._resize()
class TextBox(Text, Rectangle, EventHandler):
“””Widget for text entry.”””
def __init__(self, width=100, height=50, centerPt=None):
“””Construct a box to enter text into.
width the width of the box
height the height of the box
centerPt the location of the boxes center
“””
super(TextBox, self).__init__()
self.setWidth(width)
self.setHeight(height)
if centerPt is not None:
self.moveTo(centerPt.getX(), centerPt.getY())
self.setFillColor(‘white’) # rectangle interior was transparent by default
self.addHandler(self)
def _draw(self):
Rectangle._draw(self) # access the overridden Rectangle version of _draw
Text._draw(self) # access the overridden Text version of _draw
def handle(self, event):
“””When the text box is in focus append any keypress to the display text.”””
if event._eventType == ‘keyboard’:
if event.getKey() == ‘\b’:
self.setMessage(self.getMessage()[:-1])
else:
self.setMessage(self.getMessage() + event.getKey())
class Timer(_EventTrigger):
“””A widget for generating one or more cs1graphics events based on a time delay
By default, a timer generates a single event once started, after a given interval of time passes.
A recurring timer with a given period can be generated by means of an optional parameter to the constructor.
“””
def __init__(self, delay, repeat=False):
“””Generate a new Timer object.
delay the amount of time, in seconds, before the alarm triggers once started
repeat if False (the default), the timer will only generate one event
if True, the timer will be recurring once started, generating periodic events
“””
super(Timer, self).__init__()
self._delay = delay
self._repeat = repeat
self._running = False
self._handlers = list()
def start(self):
if not self._running:
self._forceStart()
def addHandler(self, handler):
if not isinstance(handler, EventHandler):
raise TypeError(‘Only child classes of EventHandler can handle events’)
if handler not in self._handlers:
self._handlers.append(handler)
else:
raise ValueError(‘Handler is already associated to the shape’)
def removeHandler(self, handler):
if handler in self._handlers:
self._handlers.remove(handler)
else:
raise ValueError(‘Cannot remove hander from shape it is not associated to’)
def run(self):
_time.sleep(self._delay)
if self._timer._repeat and self._timer._running:
self._timer._forceStart()
if self._timer._running:
for handler in self._timer._handlers:
e = Event()
e._eventType = ‘timer’
handler.handle(e)
class Monitor(object):
“””Monitor class for thread synchronization.”””
def __init__(self):
“””Create a new monitor instance.”””
self._lock = _threading.Lock()
self._lock.acquire()
def wait(self):
“””Wait for the monitor to be released by another thread.”””
self._lock.acquire()
def release(self):
“””Release a thread that is waiting on the monitor.”””
if self._lock.locked():
self._lock.release()
BST/BST_join.py
from random import random # for use as treap priority
class TreeSet:
“””
A set of distinct values from a totally ordered domain.
“””
#########################################################
class _Node:
“””Inner class to represent one node of a tree.”””
def __init__(self, key, left=None, right=None):
self._key = key
self._left = left
self._right = right
def getKey(self):
return self._key
def setKey(self, k):
self._key = k
def getLeft(self):
return self._left
def setLeft(self, left):
self._left = left
def getRight(self):
return self._right
def setRight(self, right):
self._right = right
def __str__(self):
“””String representation for visualization.
Can include newlines if desired.
“””
return(f'{self._key}’)
#########################################################
def __init__(self):
self._root = None
def _tracePath(self, key):
“””Return list of nodes visited during search for key.”””
path = []
walk = self._root
while walk:
path.append(walk)
if key == walk.getKey():
break
elif key < walk.getKey():
walk = walk.getLeft()
else:
walk = walk.getRight()
return path
def look(self, key):
"""Return True if key exists in set, else False."""
path = self._tracePath(key)
return path and path[-1].getKey() == key
def insert(self, key):
"""Insert key into set (if not already there).
Return True if new, False if existing.
"""
if self._root is None:
self._root = TreeSet._Node(key)
return True
else:
path = self._tracePath(key)
last = path[-1]
if key != last.getKey():
# element is new
newNode = TreeSet._Node(key)
if key < last.getKey():
last.setLeft(newNode)
else:
last.setRight(newNode)
return True
else:
return False
def delete(self, key):
"""Delete key from set, if it exists.
Return True if deleted, False if not found.
"""
path = self._tracePath(key)
if path and path[-1].getKey() == key:
# found a match to delete
last = path[-1]
if last.getRight() and last.getLeft():
# there are two children. So rather than delete this actual node
# let's find a replacement key as the smallest thing in right subtree
walk = last.getRight()
while walk:
path.append(walk)
walk = walk.getLeft()
last.setKey(path[-1].getKey()) # higher node steals key from lower node
last = path[-1] # and now our task is to delete the lower node
# goal is now to delete "last" node, which has at most one child
# replacement is the one child, or None if zero children
if last.getLeft() is None:
replacement = last.getRight() # might also be None
else:
replacement = last.getLeft()
if len(path) == 1:
# we are deleting the tree root
self._root = replacement
else:
# we are deleting a nonroot
parent = path[-2]
if parent.getLeft() is last:
parent.setLeft(replacement)
else:
parent.setRight(replacement)
return True
else:
return False
def split(self, k):
"""Return two new TreeSet instances.
The first should contain all elements of this set that are less than or
equal to k, and the second all those strictly greater than k (though one or
both of those could be an empty TreeSet instance).
As a side effect of this call, the current tree should be emptied.
"""
left = TreeSet() # initially empty
right = TreeSet() # initially empty
# more work here...
return left,right
# The following is a static method as it is not invoked as a method of a tree
@staticmethod
def join(t1, k, t2):
"""
Return a new TreeSet instance that joins existing t1 and t2 with new key k.
The caller is responsible for ensuring that all elements of
TreeSet t1 are strictly less than k, and that all elements of
TreeSet t2 are strictly greater than k.
As a side effect both t1 and t2 should be emptied.
"""
pass
BST/driver.py
"""
A Driver for the TreeSet class.
Those commands can either be provided through standard input or a
separate file indicated as a commandline argument.
The first line must be either TR, TJ, TT, TA and indicates which version of
TreeSet should be used throughout the simultation, where
TR: from BST_rank, which should supports rank-based queries
TJ: from BST_join, which should support split/join
TT: from BST_treap, which should support treap balancing
TA: from BST, which should properly support combination of all of the above
Following the first line, are any number of commands from the following.
Basic methods for creating and manipulating trees:
* T sample
Create a new empty tree with identifier "sample" used for other operations.
* I sample 23
Insert key 23 into tree named "sample"
* D sample 23
Delete key 23 from tree named "sample"
* L sample 23
Look for key 23 in tree named "sample"
The methods to invoke split/join of trees are as follows:
* S sample 23 resultLeft resultRight
Split tree named "sample" using key 23, and name the two resulting trees
"resultLeft" and "resultRight", where the first has all elements less than
or equal to the split key, and the second are those strictly greater.
* J left 23 right result
Join existing trees named "left" and "right" and new key 23 to produce
the new tree named "result". All keys in left should be less than the
new key and all keys in right should be greater than the new key.
The methods to do rank-based queries are as follows:
* K sample 5
Get the key having rank 5 in tree named "sample"
* R sample 23
Get the rank of existing key 23 in tree named "sample"
Additional commands for testing and visualization are as follows:
* C 800 600
Create a new canvas of size 800 x 600 that will be used for visualizations
* P sample 12
Draw a picture of the tree named "sample" with indicated fontsize.
The entire drawing is proportional to the fontsize so it can be made
smaller/larger by adjusting that parameter.
* V sample
Perform validation of tree named "sample"
* W 0.5
Wait the indicated number of seconds before proceeding to the next command.
This could be used with visualizations to illustrate a series of states.
* F filename.eps
Save current canvas image to given postscript file
Additional commands for fixing random number generator:
* G seed
Sets the random number generator seed to given seed (for repeatability of treap choices).
Seed can be any string.
Finally, we note that a blank line in the input will result in a blank line in the output.
All other lines of input that aren't recognized (such as those beginning with '#' character)
will be entirely ignored.
"""
import sys
from random import seed
from time import sleep
source = open(sys.argv[1]) if len(sys.argv) > 1 else sys.stdin
firstline = source.readline().strip()
if firstline not in (‘TA’,’TR’,’TJ’,’TT’):
print(“First line must be one of TR, TJ, TT, TA”)
sys.exit()
elif firstline == ‘TR’:
from BST_rank import TreeSet
elif firstline == ‘TJ’:
from BST_join import TreeSet
elif firstline == ‘TT’:
from BST_treap import TreeSet
else:
from BST import TreeSet
trees = {} # map from the string names for the driver to the underlying trees.
try:
from cs1graphics import *
except:
Canvas = None
canvas = None
def getParams(line):
pieces = line.split()
params = []
for p in pieces:
try:
params.append(int(p))
except:
try:
params.append(float(p))
except:
params.append(p)
return params
######################################################
# validation function
######################################################
# not much can be done other than to make sure that there are no cycles
def validateTree(root,testSize,testTreap):
_validate(root,testSize,testTreap,float(‘-inf’),float(‘inf’),set())
def _validate(root,testSize,testTreap,lower,upper,cache):
if not isinstance(root, TreeSet._Node):
print(‘ ERROR: non-node object’,repr(root),’found in tree’)
return None,None
if root in cache:
print(‘ ERROR: node with key’,root._key,’is an ancestor of itself’)
return None,None
else:
cache.add(root)
if root._key <= lower:
print(f'ERROR: key {root._key} found to the right of key {lower}')
elif root._key >= upper:
print(f’ERROR: key {root._key} found to the left of key {upper}’)
if root.getLeft():
leftS,leftT = _validate(root.getLeft(), testSize, testTreap,
lower,min(upper,root._key),cache)
else:
leftS,leftT = 0,2
if root.getRight():
rightS,rightT = _validate(root.getRight(), testSize, testTreap,
max(lower,root._key), upper, cache)
else:
rightS,rightT = 0,2
if None not in (leftS,rightS):
trueSize = 1 + leftS + rightS
if testSize and trueSize != root._size:
print(f’ERROR: node with key {root._key} has size {trueSize} but reports as {root._size}’)
if testTreap and root._treap > min(leftT,rightT):
print(f’ERROR: node with key {root._key} has treap val {root._treap:.3f} but child with smaller treap val {min(leftT,rightT):.3f}’)
treap = root._treap if testTreap else 0
return trueSize,treap
else:
return None,None
######################################################
# functions to help with visualization
######################################################
LEVEL = 5
PAD = 100
def picture(tree,fontsize):
canvas.clear()
if tree._root:
lay,left,right = buildLayer(tree._root, fontsize, set())
lay.move(left+PAD, PAD)
canvas.add(lay)
rect = Rectangle(w,h)
rect.setFillColor(‘white’)
rect.setDepth(49)
lay.add(rect)
if node in cache:
rect.setBorderColor(‘red’)
label.setFontColor(‘red’)
else:
cache.add(node)
left = node.getLeft()
if left:
temp,subL,subR = buildLayer(left,fontsize,cache)
temp.move(-subR-w/2, LEVEL*fontsize)
lay.add(temp)
totalL += subL+subR
edge = Path(Point(0,0), temp.getReferencePoint())
edge.setDepth(51)
lay.add(edge)
right = node.getRight()
if right:
temp,subL,subR = buildLayer(right,fontsize,cache)
temp.move(+subL+w/2, LEVEL*fontsize)
lay.add(temp)
totalR += subL+subR
edge = Path(Point(0,0), temp.getReferencePoint())
edge.setDepth(51)
lay.add(edge)
return lay,totalL,totalR
######################################################
# the primary text-based driver
######################################################
heap = None
for line in source:
line = line.strip()
p = getParams(line)
if len(p) == 0:
print() # blank line in input gets blank line in output
# CREATE TREE
elif p[0].upper().startswith(‘T’):
if len(p) != 2:
print(“IGNORING command”,line)
print(” Expected format: T “)
else:
label = str(p[1])
trees[label] = TreeSet()
# INSERT INTO TREE
elif p[0].upper().startswith(‘I’):
if len(p) != 3 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: I “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
else:
try:
print(f’Calling {p[1]}.insert({p[2]})…’)
result = trees[p[1]].insert(p[2])
print(f’…returned {result}’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# DELETE FROM TREE
elif p[0].upper().startswith(‘D’):
if len(p) != 3 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: D “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
else:
try:
print(f’Calling {p[1]}.delete({p[2]})…’)
result = trees[p[1]].delete(p[2])
print(f’…returned {result}’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# FIND IN TREE
elif p[0].upper().startswith(‘L’):
if len(p) != 3 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: L “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
else:
try:
print(f’Calling {p[1]}.look({p[2]})…’)
result = trees[p[1]].look(p[2])
print(f’…returned {result}’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# SPLIT TREE
elif p[0].upper().startswith(‘S’):
if len(p) != 5 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: S “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
else:
try:
print(f’Calling {p[1]}.split({p[2]})…’)
result = trees[p[1]].split(p[2])
if len(result) != 2:
print(f’…failed to return two trees’)
else:
left,right = result
if not (isinstance(left,TreeSet) and isinstance(right,TreeSet)):
print(f’…two results should be TreeSet instances’)
else:
trees[str(p[3])],trees[str(p[4])] = left,right
print(f’…done’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# JOIN TREES
elif p[0].upper().startswith(‘J’):
if len(p) != 5 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: J “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
elif p[3] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[3]}’)
else:
try:
print(f’Calling join({p[1]},{p[2]},{p[3]})…’)
result = TreeSet.join(trees[p[1]],p[2],trees[p[3]])
if not isinstance(result, TreeSet):
print(f’…failed to return a TreeSet instance’)
else:
trees[str(p[4])] = result
print(f’…done’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# RANK TO KEY
elif p[0].upper().startswith(‘K’):
if len(p) != 3 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: K “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
else:
try:
print(f’Calling {p[1]}.rankToKey({p[2]})…’)
result = trees[p[1]].rankToKey(p[2])
print(f’…returned {result}’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# KEY TO RANK
elif p[0].upper().startswith(‘R’):
if len(p) != 3 or not isinstance(p[2],int):
print(“IGNORING command”,line)
print(” Expected format: R “)
elif p[1] not in trees:
print(“IGNORING command”,line)
print(f’ unrecognized tree label: {p[1]}’)
else:
try:
print(f’Calling {p[1]}.keyToRank({p[2]})…’)
result = trees[p[1]].keyToRank(p[2])
print(f’…returned {result}’)
except Exception as error:
print(f’…{type(error)} raised: {error})’)
raise error
# WAIT
elif line.upper().startswith(‘W’): # wait
if len(p) != 2 or not isinstance(p[1],(int,float)):
print(“IGNORING command”,line)
print(‘ Expected format: W
# GENERATOR seed
elif line.upper().startswith(‘G’):
if len(p) != 2:
print(“IGNORING command”,line)
print(f’ Expected format: G ‘)
else:
seed(p[1])
BST/inputs/testSplit.txt
TJ
G fixed
C 800 600
T tree
I tree 80
I tree 30
I tree 20
I tree 130
I tree 50
I tree 35
I tree 120
I tree 140
I tree 90
I tree 37
I tree 110
I tree 70
I tree 25
I tree 100
I tree 45
I tree 160
I tree 40
P tree 12
F beforeSplit.eps
V tree
W 2
S tree 38 small large
V small
P small 12
F splitResultLeft.eps
W 2
V large
P large 12
F splitResultRight.eps
BST/inputs/testSplitTreap.txt
TA
G fixed
C 800 600
T tree
I tree 80
I tree 30
I tree 20
I tree 130
I tree 50
I tree 35
I tree 120
I tree 140
I tree 90
I tree 37
I tree 110
I tree 70
I tree 25
I tree 100
I tree 45
I tree 160
I tree 40
P tree 12
F beforeSplitTreap.eps
V tree
W 2
S tree 38 small large
V small
P small 12
F splitTreapResultLeft.eps
W 2
V large
P large 12
F splitTreapResultRight.eps
BST/inputs/testRanks.txt
TR
G fixed
C 600 400
T tree
I tree 50
I tree 30
I tree 20
I tree 40
I tree 35
I tree 100
I tree 37
I tree 70
I tree 110
I tree 80
I tree 90
V tree
P tree 12
F testRanks.eps
K tree 2
K tree 5
K tree 11
R tree 30
R tree 40
R tree 110
W 2
D tree 30
P tree 12
V tree
K tree 1
K tree 6
K tree 9
R tree 20
R tree 70
R tree 100
W 2
D tree 50
D tree 110
D tree 35
P tree 12
V tree
K tree 1
K tree 3
K tree 5
R tree 20
R tree 40
R tree 80
R tree 28
BST/inputs/testJoin.txt
TA
G fixed
C 800 600
T left
T right
I left 30
I left 20
I left 40
I left 35
I left 37
I left 25
P left 12
F joinLeft.eps
W 2
I right 90
I right 50
I right 70
I right 100
I right 80
I right 110
I right 55
I right 65
I right 75
I right 85
I right 95
P right 12
F joinRight.eps
W 2
J left 45 right full
P full 12
F joinResult.eps
V full
BST/inputs/basicTest.txt
TJ
G fixed
C 800 600
T tree
I tree 80
I tree 30
I tree 20
I tree 20
I tree 20
I tree 130
I tree 50
I tree 35
I tree 120
I tree 140
I tree 90
I tree 90
I tree 90
I tree 37
I tree 110
I tree 70
I tree 25
I tree 100
I tree 45
I tree 160
I tree 40
V tree
P tree 12
F afterInsertions.eps
W 2
D tree 140
P tree 12
V tree
F afterDeleting140.eps
W 2
D tree 45
P tree 12
V tree
F afterDeleting45.eps
W 2
D tree 80
P tree 12
V tree
F afterDeleting80.eps
W 2
D tree 100
P tree 12
V tree
F afterDeleting100.eps
W 2
BST/inputs/basicTestTreap.txt
TT
G fixed
C 800 600
T tree
I tree 80
I tree 30
I tree 20
I tree 20
I tree 20
I tree 130
I tree 90
I tree 35
I tree 120
I tree 140
I tree 50
I tree 90
I tree 90
I tree 37
I tree 110
I tree 70
I tree 25
I tree 100
I tree 45
I tree 160
I tree 40
V tree
P tree 12
F afterInsertionsTreap.eps
W 2
D tree 140
P tree 12
V tree
F afterDeleting140Treap.eps
W 2
D tree 45
P tree 12
V tree
F afterDeleting45Treap.eps
W 2
D tree 80
P tree 12
V tree
F afterDeleting80Treap.eps
W 2
D tree 100
P tree 12
V tree
F afterDeleting100Treap.eps
W 2
BST/inputs/basicTestSize.txt
TR
G fixed
C 800 800
T tree
I tree 80
I tree 30
I tree 20
I tree 130
I tree 90
I tree 35
I tree 120
I tree 110
I tree 50
I tree 37
I tree 140
I tree 70
I tree 25
I tree 100
I tree 45
I tree 160
I tree 40
V tree
P tree 12
F afterInsertionsSize.eps
W 2
D tree 140
P tree 12
V tree
F afterDeleting140Size.eps
W 2
D tree 45
P tree 12
V tree
F afterDeleting45Size.eps
W 2
D tree 80
P tree 12
V tree
F afterDeleting80Size.eps
W 2
BST/BST_treap.py
from random import random # for use as treap priority
class TreeSet:
“””
A set of distinct values from a totally ordered domain.
“””
#########################################################
class _Node:
“””Inner class to represent one node of a tree.”””
def __init__(self, key, left=None, right=None):
self._key = key
self._left = left
self._right = right
self._treap = random() # for later use
def getKey(self):
return self._key
def setKey(self, k):
self._key = k
def getLeft(self):
return self._left
def setLeft(self, left):
self._left = left
def getRight(self):
return self._right
def setRight(self, right):
self._right = right
def __str__(self):
“””String representation for visualization.
Can include newlines if desired.
“””
return(f'{self._key}\n{self._treap:0.3f}’)
#########################################################
def __init__(self):
self._root = None
def _tracePath(self, key):
“””Return list of nodes visited during search for key.”””
path = []
walk = self._root
while walk:
path.append(walk)
if key == walk.getKey():
break
elif key < walk.getKey():
walk = walk.getLeft()
else:
walk = walk.getRight()
return path
def look(self, key):
"""Return True if key exists in set, else False."""
path = self._tracePath(key)
return path and path[-1].getKey() == key
def insert(self, key):
"""Insert key into set (if not already there).
Return True if new, False if existing.
"""
if self._root is None:
self._root = TreeSet._Node(key)
return True
else:
path = self._tracePath(key)
last = path[-1]
if key != last.getKey():
# element is new
newNode = TreeSet._Node(key)
if key < last.getKey():
last.setLeft(newNode)
else:
last.setRight(newNode)
return True
else:
return False
def delete(self, key):
"""Delete key from set, if it exists.
Return True if deleted, False if not found.
"""
path = self._tracePath(key)
if path and path[-1].getKey() == key:
# found a match to delete
last = path[-1]
if last.getRight() and last.getLeft():
# there are two children. So rather than delete this actual node
# let's find a replacement key as the smallest thing in right subtree
walk = last.getRight()
while walk:
path.append(walk)
walk = walk.getLeft()
last.setKey(path[-1].getKey()) # higher node steals key from lower node
last = path[-1] # and now our task is to delete the lower node
# goal is now to delete "last" node, which has at most one child
# replacement is the one child, or None if zero children
if last.getLeft() is None:
replacement = last.getRight() # might also be None
else:
replacement = last.getLeft()
if len(path) == 1:
# we are deleting the tree root
self._root = replacement
else:
# we are deleting a nonroot
parent = path[-2]
if parent.getLeft() is last:
parent.setLeft(replacement)
else:
parent.setRight(replacement)
return True
else:
return False
What Will You Get?
We provide professional writing services to help you score straight A’s by submitting custom written assignments that mirror your guidelines.
Premium Quality
Get result-oriented writing and never worry about grades anymore. We follow the highest quality standards to make sure that you get perfect assignments.
Experienced Writers
Our writers have experience in dealing with papers of every educational level. You can surely rely on the expertise of our qualified professionals.
On-Time Delivery
Your deadline is our threshold for success and we take it very seriously. We make sure you receive your papers before your predefined time.
24/7 Customer Support
Someone from our customer support team is always here to respond to your questions. So, hit us up if you have got any ambiguity or concern.
Complete Confidentiality
Sit back and relax while we help you out with writing your papers. We have an ultimate policy for keeping your personal and order-related details a secret.
Authentic Sources
We assure you that your document will be thoroughly checked for plagiarism and grammatical errors as we use highly authentic and licit sources.
Moneyback Guarantee
Still reluctant about placing an order? Our 100% Moneyback Guarantee backs you up on rare occasions where you aren’t satisfied with the writing.
Order Tracking
You don’t have to wait for an update for hours; you can track the progress of your order any time you want. We share the status after each step.
From brainstorming your paper's outline to perfecting its grammar, we perform every step carefully to make your paper worthy of A grade.
Preferred Writer
Hire your preferred writer anytime. Simply specify if you want your preferred expert to write your paper and we’ll make that happen.
Grammar Check Report
Get an elaborate and authentic grammar check report with your work to have the grammar goodness sealed in your document.
One Page Summary
You can purchase this feature if you want our writers to sum up your paper in the form of a concise and well-articulated summary.
Plagiarism Report
You don’t have to worry about plagiarism anymore. Get a plagiarism report to certify the uniqueness of your work.
Free Features $66FREE
Most Qualified Writer
$10FREE
Plagiarism Scan Report
$10FREE
Unlimited Revisions
$08FREE
Paper Formatting
$05FREE
Cover Page
$05FREE
Referencing & Bibliography
$10FREE
Dedicated User Area
$08FREE
24/7 Order Tracking
$05FREE
Periodic Email Alerts
$05FREE
Our Services
Join us for the best experience while seeking writing assistance in your college life. A good grade is all you need to boost up your academic excellence and we are all about it.
On-time Delivery
24/7 Order Tracking
Access to Authentic Sources
Academic Writing
We create perfect papers according to the guidelines.
Professional Editing
We seamlessly edit out errors from your papers.
Thorough Proofreading
We thoroughly read your final draft to identify errors.
Thorough Proofreading
We thoroughly read your final draft to identify errors.
Delegate Your Challenging Writing Tasks to Experienced Professionals
Work with ultimate peace of mind because we ensure that your academic work is our responsibility and your grades are a top concern for us!
We Analyze Your Problem and Offer Customized Writing
We understand your guidelines first before delivering any writing service. You can discuss your writing needs and we will have them evaluated by our dedicated team.
Clear elicitation of your requirements.
Customized writing as per your needs.
We Mirror Your Guidelines to Deliver Quality Services
We write your papers in a standardized way. We complete your work in such a way that it turns out to be a perfect description of your guidelines.
Proactive analysis of your writing.
Active communication to understand requirements.
We Handle Your Writing Tasks to Ensure Excellent Grades
We promise you excellent grades and academic excellence that you always longed for. Our writers stay in touch with you via email.
Thorough research and analysis for every order.
Deliverance of reliable writing service to improve your grades.
