Generizität

Definition in der Informatik :

Algorihmen und Datenstrukturen so zu entwerfen und implementieren, dass sie möglichst
 vielvältig verwendbar sind.

""Gemeint sind :""

• verschiedene Anwendungen
• mit vielen Kombinationsmöglichkeiten
• als wiederverwendbare Bibliothek

--> ohne Neuimplemenation

• Code austauschen in Bibliotheken

Beispiel : Kopieren eines Containers

def copyArray(a):
  r =[]
  for k in a
  r.append(k)
return k

class Node :
 def__init__(self,data,next)
    self.data = data
    self.next = next
 return k

def copyArrayToList(a) :
   if len(a) == 0 : return None
   first = last = Node (a[0], None)
   for k in a[1:]  :
   last.next = Node(k, None)
   last = last.next
   return first

def copyListToArray(l):
    r = []
    while l is not in None :
        r.append(l.data)
        l = l.next
    return r

Beobachtung :

Für N Datenstrukuren ist der Implementaionsaufwand <math>O({N^2})</math>. Alle Funktionen machen das gleiche mit uninteressanten Unterschied

Verbesserung durch Verallgemeinerung zweier Aspekte :

*Navigation durch die Quelldaten
*Aufbauen der Zieldatenstruktur

Wie kann man so zwischen einem Array und einer Liste navigieren, so dass man den Unterschied nicht mehr merkt?

--> Vereinheitlichung der Zieldatenstruktur :

standardisierte Funktion "append"

*Array hat sie schon
*Liste : definiere Klasse DoublyLinkedList

class SentinelTag : pass     # keine Daten

class DoublyLinkedNode:
 def__init__(self,data = sentinelTag(), next = None)
    if next is None:
    self.prev = self.next = self
   else :
    self.next = next
    self.prev = next.prev
    next.prev.next = self
    next.prev = self

def isSentinel(self) : return isinstance(self.data, sentinelTag)

class DoublyLinkedList :
  def__init__(self):
    self.sentinel = DoublyLinkedNode()
    self.size = 0

 def__len__(self): return self.size   #len(l)
 def append(self, value):
   DoublyLinkedNode(value, self.sentinel)
 def__iter__(self):
      return ListIterator(self.sentinel.next)

2. Navigation in der Quelldatenstruktur(Iteration) soll für alle Datenstrukturen funktionieren

*Objekt, dass auf ein Element des Containers zeigt
*zum nächsten Element weiter rücken kann
*anzeigt, wenn das Ende der Sequenz erreicht ist 

def genericCopy(quelle, ziele) :
   for k in quelle :
    ziel.append(k)
  return ziel

liste = genericCopy(array, DoublyLinkedList())
Statt copyArrayToList

array2 = genericCopy(array,[])
Statt copyArray

array3 = genericCopy(liste,[])
Statt copyListToArray

was tun " for k in quelle":

iter = quelle__iter__()

try :
    while True :
    k = iter.next()
    ...# Schleifeninhalt
    except StopIteration: pass

class ListIterator:
   def__init__(self, node):
       self.node = node
   def next(self):
       if self.node.isSentinel():
          raise StopIteraion()       #Python Konvention
       v = self.node.data
       self.node = self.node.next    # zeigt Ende der Sequenz
       return v                      # Pythonkonvention, gebe vorigen Wert zurück

   def__iter__(self):
      return ListIterator(self.node) # Pythonkonvention, Kopie des Iterators erzeugen

besser stattdessen :

     self__class__(self.node)

class ReverseListIterator(ListIterator)
  def next(self):
      if self.node isSentinel(): raise StopIteration()
      r = self.node.data
      self.node = self.node.prev
      return r

revarray = genericCopy(list, reverseIter()[]),
revlist = genericCopy(reversed(array), DoublyLinkedList())

Verallgemeinerung auf Funktionen die " etwas tun":

def sumArray(a):
        s = 0
        for k in a :
            s+=a       # s = add(s,k)
      return s 

def maxList(l):
   m = -1111111
   while l is not None [not l is Sentinel(l)]
        m = max(m, l.data)                    # max ist eingebaute Funkion in Python
        l =l.next

Zur Verallgemeinerung werden Funktoren eingerichtet:

*Funktor muss "callable" sein :
  falls f Funktor: v = f(a1, a2)
callable ist z.B. eine Funktion

*Objekt wo __call___ definiert

def doSomethingGeneric(functor, iterator, for k in iterator: intial):
  initial = functor(initial, k)
return initial