#!/usr/bin/env python
# coding: utf-8

# # Symboltabellen

# ## Einfache Implementationen

# ### Implementation mittels verketteter Liste

# Die erste Implementation ist mittels einer verketteten Liste. 
# Die put Operation stellt fest, ob der Schlüssel bereits in der Liste vorhanden ist. Falls nicht wird er am Anfang eingefügt. Falls der Schlüssel bereits vorhanden ist, wird der Wert überschrieben. 
# 
# Bei der get Methode wird einfach der Wert in der Liste zurückgegeben. 

# In[1]:


class SequentialSearchST:
    
    class Node:
        def __init__(self, key, value, next = None):
            self.key = key
            self.value = value
            self.next = next;
    
    
    def __init__(self):
        self._first = None
        self._numberOfNodesInList = 0
    
    
    def put(self, key, value):
        if self._first == None:
            self._first = SequentialSearchST.Node(key, value)
            self._numberOfNodesInList += 1
        else:
            nodeWithKey = self._findNodeWithKey(key)
            if nodeWithKey == None:
                self._first = SequentialSearchST.Node(key, value, self._first)
                self._numberOfNodesInList += 1
            else:
                nodeWithKey.value = value
    
    def get(self, key):
        nodeWithKey = self._findNodeWithKey(key)
        if nodeWithKey == None:
            return None
        else:
            return nodeWithKey.value
    
    def delete(self, key):
        if self._first == None:
            return
        if (self._first.key == key):
            self._numberOfNodesInList = 0
            self._first = self._first.next
            return
            
        current = self._first
        while (current.next != None):
            if current.next.key == key:
                current.next = current.next.next
                self._numberOfNodesInList -= 1    
                
            current = current.next
        
    
    def contains(self, key):
        return self._findNodeWithKey(key) == None
    
    def isEmpty(self):
        return self.size() == 0
    
    def size(self):
        return self._numberOfNodesInList
    
    def _findNodeWithKey(self, key):
        current = self._first
        while (current != None):
            if current.key == key:
                return current
            current = current.next
        
        return None # not found
    
    def keys(self):
        if (self._first == None):
            yield current.key
        current = self._first
        while (current != None):
            yield current.key
            current = current.next


# ## Implementation mittels Binary Search

# In unserer zweiten Implementation, wir nutzen Binary search. Wir schauen uns als erstes die Implementation von Binary search an. 

# In[2]:


def binarySearch(sequence , value ):
    lo = 0
    hi = len(sequence) - 1
    while lo  <= hi:
        mid = (lo + hi) // 2        
        if  sequence[mid] < value:
            lo = mid + 1
        elif  value  < sequence[mid]:
            hi = mid - 1
        else:
            return mid
    return None


# In[3]:


binarySearch([1, 3,  6, 7, 11, 19], 6)


# In[4]:


binarySearch([1, 3, 7, 11, 19], 18)


# Eine ähnliche Funktion, genannt rank, bildet das Rückgrat unserer nächsten Implementation. Die Funktion rank basiert auf dem Prinzip von Binarysearch und gibt die Anzahl der Schlüssel kleiner als ein gegebener Wert an.

# In[5]:


class BinarySearchST:
    
    def __init__(self):
        self._keys = []
        self._values = []
    
    
    def _rank(self, value):
        lo = 0
        hi = len(self._keys) - 1
        while lo  <= hi:
            mid = (lo + hi) // 2
            if  self._keys[mid] < value:
                lo = mid + 1
            elif  value  < self._keys[mid]:
                hi = mid - 1
            else:
                return mid
        return lo
    
    def get(self, key):
        if self.isEmpty():
            return None
        
        rank = self._rank(key)
        if rank < len(self._keys) and self._keys[rank] == key:
            return self._values[rank]
        else:
            return None
        
    def put(self, key, value):
        rank = self._rank(key)
        if rank < len(self._keys) and self._keys[rank] == key:
            self._values[rank] = value
        else:
            self._keys.insert(rank, key)
            self._values.insert(rank, value)
             
    def delete(self, key):
        rank = self._rank(key)
        if rank < len(self._keys) and self._keys[rank] == key:
            del self._keys[rank] 
            del self._values[rank]
            
    
    def contains(self, key):
        rank = self._rank(key)
        return rank < len(self._keys) and self._keys[rank] == key
    
    def isEmpty(self):
        return self.size() == 0
    
    def size(self):
        return len(self._keys)
    
    def keys(self):
        return self._keys


# ## Clients

# ### Testclient

# Unser erster Client nimmt jeden Buchstaben von einem String als Key und die Position des Buchstabens im String als Wert.

# In[6]:


string = "SEARCHEXAMPLE"
st = SequentialSearchST()
for (pos, char) in enumerate(string):
    st.put(char, pos)


# In[7]:


st.delete('L')


# In[8]:


for key in st.keys():
    print(key, st.get(key))


# ### Frequency client

# Unser zweiter Client zählt, wie oft ein bestimmes Wort in einem Text vorkommt.

# In[9]:


testdataRaw = """ Alice was beginning to get very tired of 
sitting by her sister on the bank, and of having nothing to 
do:  once or twice she had peeped into the book her sister 
was reading, but it had no pictures or conversations in it, `and what is the use of a book,'
thought Alice `without pictures or conversation?'

  So she was considering in her own mind (as well as she could,
for the hot day made her feel very sleepy and stupid), whether
the pleasure of making a daisy-chain would be worth the trouble
of getting up and picking the daisies, when suddenly a White
Rabbit with pink eyes ran close by her.

  There was nothing so VERY remarkable in that; nor did Alice
think it so VERY much out of the way to hear the Rabbit say to
itself, `Oh dear!  Oh dear!  I shall be late!'  (when she thought
it over afterwards, it occurred to her that she ought to have
wondered at this, but at the time it all seemed quite natural);
but when the Rabbit actually TOOK A WATCH OUT OF ITS WAISTCOAT-
POCKET, and looked at it, and then hurried on, Alice started to
her feet, for it flashed across her mind that she had never
before seen a rabbit with either a waistcoat-pocket, or a watch to
take out of it, and burning with curiosity, she ran across the
field after it, and fortunately was just in time to see it pop
down a large rabbit-hole under the hedge.
"""
import string
translator = str.maketrans('', '', string.punctuation)
testdata = testdataRaw.translate(translator).lower()


# In[ ]:





# In[10]:


st = BinarySearchST()
for word in testdata.split():
    if len(word) > 5:
        if st.contains(word):
            st.put(word, st.get(word) + 1)
        else:
            st.put(word, 1)


# Wir können nun das Wort, welches am meisten vorkommt, ganz einfach auslesen. Beachten Sie, dass wir uns dazu eine Variable max führen, die immer auf das wort mit den meisten Einträgen zeigt. Am Anfang wird dies auf ein nicht existierendes Wort, mit 0 Einträgen gesetzt.

# In[11]:


max = ""
st.put("", 0)
for word in st.keys():
    if st.get(word) > st.get(max):
        max = word
print(max, st.get(max))


# In[12]:


st.keys()


# In[ ]: