← Back to branch summary

~ubuntu-branches/ubuntu/utopic/deap/utopic-proposed

« back to all changes in this revision

Viewing changes to examples/sortingnetwork.py

  • Committer: Package Import Robot
  • Author(s): Daniel Stender, Miriam Ruiz, Daniel Stender, Jakub Wilk
  • Date: 2014-07-06 00:03:41 UTC
  • mfrom: (1.1.2)
  • Revision ID: package-import@ubuntu.com-20140706000341-s7gij1ki3d8xz6t9
Tags: 1.0.1-1
http://bugs.debian.org/675200
[ Miriam Ruiz ]
* New Upstream Release. Closes: #675200
* Upgraded Standards-Version from 3.9.2 to 3.9.5
* Switched to dh_python2
* Upgraded debian/compat to 9
* Added build-arch and build-indep targets to debian/rules
* Using awk to remove connection from the documentation to google analytics
* Using jquery.js and underscore.js from libjs-jquery and libjs-underscore
* Added patches/doc.patch

[ Daniel Stender ]
* deb/control:
  + Added myself to Uploaders.
  + Added version to b-p on python-all.
  + Updated Homepage.
  + Wrapped and sorted.
* deb/copyright:
  + Changed copyright file towards DEP-5.
  + Updated Source URI (project source moved to Github).
  + Added email addresses for copyright holders.
  + Dropped license for eap/toolbox.py (not included anymore).
  + Extended copyrights to 2014.
  + Added myself to copyrights for deb/*.
  + Specified license location.
* Added watch file [initial version by Jackson Doak].

[ Jakub Wilk ]
* Use canonical URIs for Vcs-* fields.

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/sortingnetwork.py
1
 
#    This file is part of DEAP.
2
 
#
3
 
#    DEAP is free software: you can redistribute it and/or modify
4
 
#    it under the terms of the GNU Lesser General Public License as
5
 
#    published by the Free Software Foundation, either version 3 of
6
 
#    the License, or (at your option) any later version.
7
 
#
8
 
#    DEAP is distributed in the hope that it will be useful,
9
 
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
 
#    GNU Lesser General Public License for more details.
12
 
#
13
 
#    You should have received a copy of the GNU Lesser General Public
14
 
#    License along with DEAP. If not, see <http://www.gnu.org/licenses/>.
15
 
 
16
 
try:
17
 
    from itertools import product
18
 
except ImportError:
19
 
    def product(*args, **kwds):
20
 
        # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
21
 
        # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
22
 
        pools = map(tuple, args) * kwds.get('repeat', 1)
23
 
        result = [[]]
24
 
        for pool in pools:
25
 
            result = [x+[y] for x in result for y in pool]
26
 
        for prod in result:
27
 
            yield tuple(prod)
28
 
            
29
 
class SortingNetwork(list):
30
 
    """Sorting network class.
31
 
    
32
 
    From Wikipedia : A sorting network is an abstract mathematical model
33
 
    of a network of wires and comparator modules that is used to sort a
34
 
    sequence of numbers. Each comparator connects two wires and sort the
35
 
    values by outputting the smaller value to one wire, and a larger
36
 
    value to the other.
37
 
    """
38
 
    def __init__(self, dimension, connectors = []):
39
 
        self.dimension = dimension
40
 
        for wire1, wire2 in connectors:
41
 
            self.addConnector(wire1, wire2)
42
 
    
43
 
    def addConnector(self, wire1, wire2):
44
 
        """Add a connector between wire1 and wire2 in the network."""
45
 
        if wire1 == wire2:
46
 
            return
47
 
        
48
 
        if wire1 > wire2:
49
 
            wire1, wire2 = wire2, wire1
50
 
        
51
 
        try:
52
 
            last_level = self[-1]
53
 
        except IndexError:
54
 
            # Empty network, create new level and connector
55
 
            self.append([(wire1, wire2)])
56
 
            return
57
 
        
58
 
        for wires in last_level:
59
 
            if wires[1] >= wire1 and wires[0] <= wire2:
60
 
                self.append([(wire1, wire2)])
61
 
                return
62
 
        
63
 
        last_level.append((wire1, wire2))
64
 
    
65
 
    def sort(self, values):
66
 
        """Sort the values in-place based on the connectors in the network."""
67
 
        for level in self:
68
 
            for wire1, wire2 in level:
69
 
                if values[wire1] > values[wire2]:
70
 
                    values[wire1], values[wire2] = values[wire2], values[wire1]
71
 
    
72
 
    def assess(self, cases=None):
73
 
        """Try to sort the **cases** using the network, return the number of
74
 
        misses. If **cases** is None, test all possible cases according to
75
 
        the network dimensionality.
76
 
        """
77
 
        if cases is None:
78
 
            cases = product(range(2), repeat=self.dimension)
79
 
        
80
 
        misses = 0
81
 
        ordered = [[0]*(self.dimension-i) + [1]*i for i in range(self.dimension+1)]
82
 
        for sequence in cases:
83
 
            sequence = list(sequence)
84
 
            self.sort(sequence)
85
 
            misses += (sequence != ordered[sum(sequence)])
86
 
        return misses
87
 
    
88
 
    def draw(self):
89
 
        """Return an ASCII representation of the network."""
90
 
        str_wires = [["-"]*7 * self.depth]
91
 
        str_wires[0][0] = "0"
92
 
        str_wires[0][1] = " o"
93
 
        str_spaces = []
94
 
 
95
 
        for i in xrange(1, self.dimension):
96
 
            str_wires.append(["-"]*7 * self.depth)
97
 
            str_spaces.append([" "]*7 * self.depth)
98
 
            str_wires[i][0] = str(i)
99
 
            str_wires[i][1] = " o"
100
 
        
101
 
        for index, level in enumerate(self):
102
 
            for wire1, wire2 in level:
103
 
                str_wires[wire1][(index+1)*6] = "x"
104
 
                str_wires[wire2][(index+1)*6] = "x"
105
 
                for i in xrange(wire1, wire2):
106
 
                    str_spaces[i][(index+1)*6+1] = "|"
107
 
                for i in xrange(wire1+1, wire2):
108
 
                    str_wires[i][(index+1)*6] = "|"
109
 
        
110
 
        network_draw = "".join(str_wires[0])
111
 
        for line, space in zip(str_wires[1:], str_spaces):
112
 
            network_draw += "\n"
113
 
            network_draw += "".join(space)
114
 
            network_draw += "\n"
115
 
            network_draw += "".join(line)
116
 
        return network_draw
117
 
    
118
 
    @property
119
 
    def depth(self):
120
 
        """Return the number of parallel steps that it takes to sort any input.
121
 
        """
122
 
        return len(self)
123
 
    
124
 
    @property
125
 
    def length(self):
126
 
        """Return the number of comparison-swap used."""
127
 
        return sum(len(level) for level in self)
128