import numpy as np
class BinaryTree:
    def __init__(self):
        self.data = [None]
        
    def insert(self, val):
        # keep track of idx we're at traversing the tree
        idx = 0
        while self.data[idx] is not None:
            idx = idx * 2 + (1 if self.data[idx] > val else 2)
            if idx >= len(self.data):
                self.data = self.data + [None]*(idx + 1 - len(self.data))
        self.data[idx] = val
        
    def find(self, val):
        idx = 0
        while self.data[idx] is not None and self.data[idx] != val:
            idx = idx * 2 + (1 if self.data[idx] > val else 2)
            if len(self.data) <= idx:
                return -1
        return idx if self.data[idx] is not None else -1
    
    def levelUp(self, idx):
        self.data[idx] = None
        leftChild = idx * 2 + 1
        rightChild = (idx + 1) * 2
        if len(self.data) > leftChild:
            if self.data[leftChild] is not None:
                self.data[idx] = self.data[leftChild]
                self.levelUp(leftChild)
            elif len(self.data) > rightChild and self.data[rightChild] is not None:
                self.data[idx] = self.data[rightChild]
                self.levelUp(rightChild)
                
    def getValues(self, level):
        values = []
        for x in range(2**level - 1, 2**(level + 1) - 1):
            if len(self.data) <= x:
                values.append(None)
            else:
                values.append(self.data[x])
        return values

class DFSTraversalInterator_post:
    def __init__(self,tree):
        import numpy as np
        self.tree=tree
        self.index=0
        self.visited=np.zeros(len(tree.data))
    def __iter__(self):
        return self
    def __next__(self):
        if self.index<0:
            raise StopIteration()
        flag1=True
        flag2=True
        while flag1 or flag2:
            flag1=False
            flag2=False
            if self.index*2+1<len(self.tree.data) and self.tree.data[self.index*2+1]!=None and self.visited[self.index*2+1]==0:
                self.index=self.index*2+1
                flag1=True
            elif self.index*2+2<len(self.tree.data) and self.tree.data[self.index*2+2]!=None and self.visited[self.index*2+2]==0:
                self.index=self.index*2+2
                flag2=True
 
        now_ele=self.tree.data[self.index]
        self.visited[self.index]=1
        self.index=(self.index+1)//2-1
        return now_ele
        
class DFSTraversalInterator_pre:
    def __init__(self,tree):
        import numpy as np
        self.tree=tree
        self.index=0
        self.visited=np.zeros(len(tree.data))
    def __iter__(self):
        return self
    def __next__(self):
        if self.index<0:
            raise StopIteration()
        now_ele=self.tree.data[self.index]
        self.visited[self.index]=1
        while 1!=0:
            if self.index*2+1<len(self.tree.data) and self.tree.data[self.index*2+1]!=None and self.visited[self.index*2+1]==0:
                self.index=self.index*2+1
                break
            elif self.index*2+2<len(self.tree.data) and self.tree.data[self.index*2+2]!=None and self.visited[self.index*2+2]==0:
                self.index=self.index*2+2
                break
            self.index=(self.index+1)//2-1
            if self.index<0:
                break
        return now_ele
        
class DFSTraversalInterator_in:
    def __init__(self,tree):
        self.tree=tree
        self.index=0
        self.visited=np.zeros(len(tree.data))
    def __iter__(self):
        return self
    def __next__(self):
        if self.index<0:
            raise StopIteration()
        while self.index*2+1<len(self.tree.data) and self.tree.data[self.index*2+1]!=None and self.visited[self.index*2+1]==0:
            self.index=self.index*2+1

        now_ele=self.tree.data[self.index]
        self.visited[self.index]=1
        if self.index*2+2<len(self.tree.data) and self.tree.data[self.index*2+2]!=None and self.visited[self.index*2+2]==0:
            self.index=self.index*2+2       
        else:
            while self.visited[(self.index+1)//2-1]==1 and (self.index+1)//2-1>=0:
                self.index=(self.index+1)//2-1
            self.index=(self.index+1)//2-1
        return now_ele
            
  



from enum import Enum

class DFSTraversalTypes(Enum):
    PREORDER = 1
    INORDER = 2
    POSTORDER = 3


class DFSTraversal:
    def __init__(self,bt,Ttype):
        self.tree=bt
        self.type=Ttype
    def changeTraversalType(self,Ttype):
        sefl.type=Ttype
    def __iter__(self):
        if self.type==DFSTraversalTypes.PREORDER:
            return DFSTraversalInterator_pre(self.tree)
        if self.type==DFSTraversalTypes.INORDER:
            return DFSTraversalInterator_in(self.tree)
        if self.type==DFSTraversalTypes.POSTORDER:
            return DFSTraversalInterator_post(self.tree)
        

input_array = [3, 9, 2, 11]
bt = BinaryTree()

for val in input_array:
    bt.insert(val)
traversal = DFSTraversal(bt, DFSTraversalTypes.INORDER)
for val in traversal:
    print(val)

    

"""
Explanation: Homework 8
Due Date:  Tuesday, October 31st at 11:59 PM
Problem 1:  BST Traversal
This problem builds on Problem 1 of Homework 7 in which you wrote a binary search tree.
Part 1
As discussed in lecture, three different types to do a depth-first traversal are: preorder, inorder, and postorder. Here is a reference: Tree Traversal.
Write an iterator class called DFSTraversal with the following specifications:

__init__(self, tree, traversalType): Constructor takes a BinaryTree object and one of the enums from DFSTraversalTypes

```python
from enum import Enum
class DFSTraversalTypes(Enum):
    PREORDER = 1
    INORDER = 2
    POSTORDER = 3
```

changeTraversalType(self, traversalType): Change the traversal type
__iter__(self): This is the initialization of an iterator
__next__(self): This is called in the iterator for getting the next value

Here's how you might use your DFSTraversal class:
python
input_array = [3, 9, 2, 11]
bt = BinaryTree()
for val in input_array:
    bt.insert(val)
traversal = DFSTraversal(bt, DFSTraversalTypes.INORDER)
for val in traversal:
    print(val)
2
3
9
11
Part 2
Put your BinaryTree class (from homework 7) and your DFSTraversal class (from Part 1 of this homework) in a file titled TreeTraversal.py.
End of explanation
"""


#Load CSV file -- hint: you can use np.genfromtxt()
import numpy as np
w=np.genfromtxt("weather.csv",delimiter=",")

"""
Explanation: Problem 2: Markov Chains
Markov Chains are widely used to model and predict discrete events. Underlying Markov chains are Markov processes which make the assumption that the outcome of a future event only depends on the event immediately preceeding it. In this exercise, we will be assuming that weather has Markov properties (e.g. today's weather is dependent only on yesterday's weather). We will use the Markov assumption to create a basic model for predicting weather.
To begin, let's categorize weather into 7 types: ['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing'].
In the weather.csv file accompanying this homework, each row corresponds to one type of weather (in the order given above) and each column is the probability of one type of weather occurring the following day (also in the order given above).
The $ij$th element is the probability that the $j$th weather type occurs after the $i$th weather type. So for example, (1,2) is the probability a cloudy day occurs after a sunny day.
Take a look at the data. Make sure you see how if the previous day was sunny, the following day will have a 0.4 probability of being sunny as well. If the previous day was raining (index $i = 3$), then the following day (index $j$) has a 0.05 probability of being windy ($j = 5$).
Part 1:  Parse the .csv file into a Numpy array
End of explanation
"""


class Markov:
    def __init__(self):
        # implement here
        self.array=[]
        self.weather_name=['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing']
        self.start=0
    def load_data(self, array):
        # implement here
        self.array=array
    def set_initial(self,start):
        self.start=start
    def get_prob(self, previous_day, following_day):
        # implement here -- returns a probability
        return(self.array[previous_day,following_day])
    def __iter__(self):
        return MarkovIterator(self.start,self.array,self.weather_name)

class MarkovIterator:
    def __init__(self,start,array,name):
        self.current=start
        self.array=array
        self.weather_name=name
    def __iter__(self):
        return self
    def __next__(self):
        r=np.random.rand()
        temp=self.array[self.current,:]
        accu=0
        for i in range(len(temp)):
            if accu+temp[i]<r:
                accu+=temp[i]
            else:
                self.current=i
                
                return self.weather_name[i]
        
                

"""
Explanation: Part 2:  Create a class called Markov that has the following methods:

load_data(array): loads the Numpy 2D array and stores it as a class variable.
get_prob(previous_day, following_day): returns the probability of following_day weather given previous_day weather. 

Note: previous_day and following_day should be passed in string form (e.g. "sunny"), as opposed to an index (e.g. 0).
End of explanation
"""


m1=Markov()
m1.load_data(w)
for i in m1:
    print(i)

iter_m=iter(m1)

"""
Explanation: Problem 3: Iterators
Iterators are a convenient way to walk along your Markov chain.
Part 1: Using your Markov class from Problem 3, write Markov as an iterator by implementing the __iter__() and __next__() methods.
Remember:
* __iter__() should return the iterator object and should be implicitly called when the loop begins
* The __next()__ method should return the next value.
Each 'next' step should be stochastic (i.e. randomly selected based on the relative probabilities of the following day weather types) and should return the next day's weather as a string (e.g. "sunny") rather than an index (e.g. 0).
End of explanation
"""


city_weather = {
    'New York': 'rainy',
    'Chicago': 'snowy',
    'Seattle': 'rainy',
    'Boston': 'hailing',
    'Miami': 'windy',
    'Los Angeles': 'cloudy',
    'San Fransisco': 'windy'
}

m1.load_data(w)
weather_name=['sunny', 'cloudy', 'rainy', 'snowy', 'windy', 'hailing']
city_weather_predictions={}
for city in city_weather.keys():
    city_weather_count={}
    for i in range(len(weather_name)):
        city_weather_count[weather_name[i]]=0
    m1.set_initial(weather_name.index(city_weather[city]))
    
    for i in range(100):
        w_iter=iter(m1)
        for j in range(7):
            kk=next(w_iter)
        del w_iter
        city_weather_count[kk]+=1
    chosen=max(city_weather_count, key=city_weather_count.get)
    city_weather_predictions[city]=chosen

city_weather_predictions

np.dot(w,w)

"""
Explanation: Part 2: We want to predict what weather will be like in a week for 5 different cities.
Now that we have our Markov iterator, we can try to predict what the weather will be like in seven days from now.
Given each city's current weather in the dictionary city_weather (see below), simulate what the weather will be like in 7 days from now.  Rather than just producing one prediction per city, simulate 100 such predictions per city and store the most commonly occuring prediction.
In your submission, print a dictionary city_weather_predictions that has each city as a key and the most commonly predicted weather as the corresponding value.
Note: Don't worry if your values don't seem to make intuitive sense.  We made up the weather probabilities.
End of explanation
"""


