# A Python Implementation Of the Fixed-Size Queue

"""A homogeneous fixed-size queue."""from array import arrayclass FixedsizeQueue(object):"""    A fixed size queue is a homogeneous FIFO queue that can't grow.    """def __init__(self, max_size, typecode='i'):self.size = 0self.head = 0self.tail = 0self.typecode = typecodeself.max = max_sizeself._data = Nonereturn@propertydef data(self):"""        :return: an array of size self.max, type self.typecode        """if self._data is None:self._data = array(self.typecode, [0 for i in range(self.max)])return self._datadef enqueue(self, item):"""        :param:         - item: the item to add to the queue        :return: True if added, False if full        """if self.size == self.max:return Falseself.data[self.tail] = itemself.size += 1self.tail += 1if self.tail == self.max:self.tail = 0return Truedef dequeue(self):"""        :return: oldest item or None        """if self.size == 0:returnitem = self.data[self.head]self.size -= 1self.head += 1if self.head == self.max:self.head = 0return itemdef reset(self):"""        :postcondition: head, tail and size reset to 0        """self.size = 0self.tail = 0self.head = 0returndef empty(self):"""        :return: True if the queue is empty.        """return self.size == 0def full(self):"""        :return: True if the queue is full.        """return self.size == self.max# end class FixedsizeQueue

# The Fixed-Size Queue

This is an abstract data type given in Udacity's Software Testing course.

#### Description

A First-In-First-Out (FIFO) queue whose size is preset and not allowed to grow and which has a homogeneous type.

#### Reason

The fixed size and type allows for better performance, particularly when removing items from the start of the queue.

# Python Imp Experiments

The importing of classes using imp was tested with:

from unittest import TestCaseimport osimport impimport importerclass TestSource(TestCase):def test_import(self):"""        module source contains class SourceCase with attribute cow set to 'pie'        """path = os.path.dirname(__file__)f, package, description = imp.find_module("source", [path])source = imp.load_module('source', f, package, description)SourceCase = getattr(source, "SourceCase")case_o = SourceCase()expected = importer.source.SourceCase()self.assertEqual(expected.cow, case_o.cow)# this won't work - using imp gets source.SourceCase, but import gets importer.source.SourceCase#self.assertIsInstance(case_o, source.SourceCase)returndef test_subdirectory_import(self):"""        module subsource contains a class Subsource with attribute apropos set to 'nothing'        """top = os.path.dirname(__file__)f, package_path, d = imp.find_module("subdir", [top])f, mod_path, description = imp.find_module('subsource', [package_path])subsource = imp.load_module('subdir.subsource', f, mod_path, description)Subsource = getattr(subsource, "Subsource")source_obj = Subsource()expected = importer.subdir.subsource.Subsource()self.assertEqual(expected.apropos, source_obj.apropos)return# end class TestSource

parameters

• name: module name using dot-notation for sub-directories (e.g. directory.module)
• file: Opened file (module)
• pathname: The path to the file.
• description: The tuple returned by imp.find_module

#### Examples

##### Same Directory

The equivalent of import module:

f, p, d = find_module('module')module = load_module('module', f, p, d)
##### Sub-Directory

The equivalent of import package.module:

path_to_importer = os.path.dirname(__file__)f, p, d = find_module('package', [path_to_importer])f2, p2, d2 = find_module('module', [p])o = load_module('package.module', f2, p2, d2)
##### Close the File

The importer won't close the file, even if there is an exception. To make sure it gets closed:

try:    return load_module('package.module', f2, p2, d2)finally:    if f2:        f2.close()

# What Is Software Testing?

#### What is Acceptability Testing?

An acceptability test is one where a set of inputs is run through the System Under Test (SUT) and checked to make sure the correct outputs are produced.

#### What is a Bug?

• An execution error
• Incorrect output

#### What are the possible sources of bugs?

1. The SUT
2. The Acceptability Test
3. The Specification
4. The System in which the software is run

#### How do you find the source of a bug?

Check the possible sources of bugs in order.
• SUT: syntax, logic, etc.
• Acceptability Test: same as SUT plus the input set
• Specification: Understanding of what the SUT is supposed to do
• System: Unfixable, look for workarounds and ways to report the problem

# Python's imp.find_module

imp.find_module(name [, path])

#### Parameters

##### name
The name of the module (directory or file without extension).
##### Path
• If ommitted checks builtins first, then the sys.path directories
• If given:
• must be a list of directory names
• Searches directories for the module

#### Return

A 3-tuple of (file, pathname, description).
##### File
An opened file or None if the module is a package (directory);
##### Pathname
The path to the file or directory.
##### Description
A 3-tuple of (suffix, mode, type):
• suffix is the file extension (e.g. .py)
• mode is one of r or rb (file was opened as readable text or binary)
• type is one of PY_SOURCE, PY_COMPILED, C_EXTENSION, or PKG_DIRECTORY

#### Raise

ImportError if the module isn't found.

#### Subdirectories

The method doesn't accept dotted notation to indicate that the module is in a sub-package. Instead you have to find the package first then the module:
path = os.path.dirname(__file__)f, p, d = find_module('directory', [path])f_2, p_2, d_2 = find_module('module_name', [p]))

# The State Pattern [HFDP]

#### What is the State Pattern?

• It allows an object to alter its behavior when the internal state changes
• The object will appear to change its class

#### How Does It Work?

• A State interface is created that has all the actions the main class needs.
• A concrete class is created for each state the system can be in (implementing the State)
• Each state knows when a state change happens and sets the container's state class to the new state (object)
• The container always calls state.method()
• The states have to have a reference to the container since they changed its State

#### State Vs Strategy

• User of context in state isn't aware of state objects
• User of Strategy specifies objects to change the algorithm
• Strategy is a more flexible alternative to subclassing (changing the composition changes the behavior)
• State is an alternative to using conditionals

#### Context Transitions Vs State Transitions

• You can decouple the states from the Context by having the Context choose the next state
• If Transitions are fixed, put in Context
• If Transitions are dynamic, put in state (state knows the Transition to the next state)

#### Do States Maintain State?

• No, they choose Transitions
• This means contexts can share the same strategies

# The Template Method Pattern [HFDP]

#### What is the Template Method Pattern?

• Defines the skeleton of an algorithm in a method
• Defers some steps to a subclass
• Lets subclasses change some steps in the algorithm without changing the structure
• The Template Method contains an ordered series of primitive operations -- by (re)defining the primitive operations, subclasses change the algorithm

#### What Are Hooks?

• A Hook is a method defined in the base class with a default or empty operation
• Because it's not abstract, subclasses can ignore it
• Because it's there, subclasses can re-define it without changing the structure of the template
• If the hook returns a boolean for a conditional, it allows subclasses to change the flow of the algorithm

#### Abstract Vs Hooks

• Abstract Methods are requirements
• Hooks are optional

#### What Is the 'Hollywood Principle'?

• Don't call us, we'll call you.
• High-level components call low-level ones, not the other way around

#### Strategy Vs Template

• Strategy composes other objects chosen at runtime
• Template uses sub-classes
• Template provides better code re-use and strictly defines the algorithm
• Strategy provides better decoupling but the algorithm is provided by the composed objects

# Optimization

#### What is Optimization?

Optimization means to find the set of parameters that minimize the cost of a solution to a problem.

#### What is a Global Optimization?

A Global Optimization is the optimal solution out of all possible solutions. [PSOAI]

#### What is a Local Optimization?

A Local Optimization is a solution that may not be the global optimum but is good enough. [PSOAI]

#### What Are the Three Types of Optimization?

• Exhaustive: Try all the combinations.
• Stochastic: Try a random subset and pick the best.
• Learning: Pick random solutions that improve as you go.

#### What Is the First Phase of Optimization?

The first phase is to create a mathematical model of the system.

#### How Do You Create a Model of the System?

• Translate parameters for the solution to numbers.
• Represent solutions as vectors of parameters.
• Create a cost function that maps the global minimizing parameters to the optimal solution. [PSOAI]

#### What is a Solution In Optimization?

A set of parameters that solves the problem with the least cost while still meeting constraints. [IIS]

#### What is the Domain?

The set of valid parameters (those that solve the problem no matter the cost). [IIS]

#### What is the Feasible Domain?

The subset of valid parameters that meet the constraints of the problem. [IIS]

#### What is a Feasible Solution?

A solution that meets all the constraints. [PSOAI]

#### What is the Cost Function?

A function that maps solutions to their cost (maps the best solution to the best outcome and the worst solution to the worst outcome).

# What is a Design Pattern?

#### What is a pattern?

##### Sources
• a recurring design problem that occurs in a specific context whose solution can be re-used [POSAV1 p. 8]
• a 3-part rule giving a relationship between a context, a problem, and a solution [RTP p. 23]
• patterns are discovered general solutions to design problems that provide a language to share them between designers [HFDP p. 32]
• a pattern is a solution to a problem in context [HFDP p. 579]
##### Restatement
A Design Pattern is a re-usable design solution for a given context and problem.

#### What are the parts of a pattern?

• Context, Problem, Solution [POSAV1 p. 8]

#### What is a problem?

• A problem is a set of competing forces that arise in a given context [POSAV1 p. 11]
• The goal and constraints of the context [HFDP p. 579]

#### What are forces?

• goals and constraints [HFDP p. 582]

#### What is a solution?

• A general design that resolves the goal and constraints [HFDP p. 579]
• A static structure of components as well as runtime behavior that balances the forces [POSAV1 p. 11]