def bfstree(s0):
    # s0 = initial state

    # create the initial node
    n0 = node(s0, None, None, 0, 0) 

    # initizlize #visited nodes
    nvisited = 0
    
    # initialize the frontier list
    frontier = deque([n0])

    while True:
        # the search fails when the frontier is empty
        if not frontier:
            return (None, nvisited)
        else:
            # get one node from the frontier
            n = frontier.popleft()
            # count the number of visited nodes
            nvisited+=1
            # check if the state in n is a goal
            if n.state.isgoal():
                return (n, nvisited)
            else:
                # generate successor states
                S = n.state.successors()
                # create new nodes and add to the frontier
                for (s, a, c) in S:
                    p = node(s, n, a, n.cost+c, n.depth+1)
                    frontier.append(p)

def gen():
    '''
    The nodeList of type 'node' will be created, including numNode sensors
    the root node is located at the center of the area
    :return:
    '''
    nodeList = []
    root = node.node(0, 0)
    nodeList.append(root)
    for i in range(1, numNode):
        while True:
            #generata new pair of (x,y) until it's not same with any added node
            newPos = (random.randint(0, xRange), random.randint(0, yRange))
            if not checkPosDup(newPos, nodeList):
                break
        newNode = node.node(*newPos)
        nodeList.append(newNode)

    # open file for outputing the topology information
    topoFile = open('topo.txt', 'w')
    for i in range(0, numNode-1):
        for j in range(i+1, numNode):
            if distance(nodeList[i], nodeList[j]) == 0:
                # should remove one of the two, but becareful with the 'out of range' loop
                print "Oh, there are two nodes with same location..."
                print nodeList[i].x, nodeList[i].y, "|||", nodeList[j].x, nodeList[j].y
            else:
                # write to file: [node1 , node2, link quality, node1.x, node1.y, node2.x, node2.y]
                topoFile.write("%u, %u, %f, %u, %u, %u, %u\n" % (
                i, j, quality(nodeList[i], nodeList[j]), nodeList[i].x, nodeList[i].y, nodeList[j].x, nodeList[j].y))

 def prepend(self, num):
     if self.head == None:
         self.head = node.node(num)
     else:
         temp = node.node(num)
         temp.set_next(self.head)
         self.head = temp

def sum_by_bit(e,t):
    mod = 0
    i = 1
    while e != None or t != None:
       if e != None:
           e_data = e.data
       else: e_data = 0
       if t != None:
           t_data = t.data
       else: t_data = 0
       (mod,remain) = divmod(e_data+t_data+mod,10)
       if i == 1:
           head = node(remain)
           tail = head
       else:
           tail.next_element = node(remain)
           tail = tail.next_element
       if e != None:
        e = e.next_element
       if t != None:
        t = t.next_element
       i = i+1
    if mod != 0:
        tail.next_element = node(mod)
    return head

    def get_map(self, n, set_x, set_y, exclude):

        # print(n,set_x,set_y)
        children = []
        next_exclude = exclude
        if n == 1:
            for x in set_x:
                for y in set_y:
                    print("exclude: {}".format(exclude))
                    if self.Point_valid((x,y), exclude):
                        node_child = node((x,y))
                        children.append(node_child)
            return children
        else:
            for x in set_x:
                for y in set_y:
                    s_x = set([x])
                    s_y = set([y])
                    # print("gaaga")
                    # print(set_x,set_y,s_x,s_y)
                    if self.Point_valid((x,y),exclude):
                        if exclude:
                            print("get exclude")
                            print(exclude)
                            next_exclude.append((x,y))
                            print("next exclude: {}".format(next_exclude))
                        else:
                            next_exclude = [(x,y)]
                        print("next exclude: {}".format(next_exclude))
                        node_child = node((x, y))
                        if n-1 >0:
                            node_child.add_child(*self.get_map(n-1, set_x - s_x, set_y - s_y, next_exclude))
                        children.append(node_child)
            return children

 def append(self, num):
     if self.head == None:
         self.head = node.node(num)
     else:
         current = self.head
         while(current.get_next() != None):
             current = current.get_next()
         temp = node.node(num)
         current.set_next(temp)
         temp.set_next(None)

def sum(e, t):
    e_sum = assemble(e)
    t_sum = assemble(t)
    sum =  e_sum + t_sum
    head = node(str(sum)[-1])
    tail = head
    for i in str(sum)[-2::-1]:
        temp = node(i)
        tail.next_element = temp
        tail = temp
    return head

 def jump_step(self, n):
     children = []
     if n == 1 :
         node_child = node(1)
         children.append(node_child)
         return children
     if n >=2 :
         for i in [1,2]:
             node_child = node(i)
             if self.jump_step(n-i):
                 node_child.add_child(*self.jump_step(n-i))
             children.append(node_child)
         return children

def f(s1, s2):
    if not s1:
        return s2
    if not s2:
        return s1

    it1 = s1
    it2 = s2

    res = None
    carry = 0

    while it1 and it2:
        curr = it1.value + it2.value + carry
        carry = curr / 10
        value = curr % 10
        if not res:
            res = node(value)
            prev = res
        else:
            prev.next = node(value)
            prev = prev.next
        it1 = it1.next
        it2 = it2.next

    while it1:
        curr = it1.value + carry
        carry = curr / 10
        value = curr % 10
        prev.next = node(value)
        prev = prev.next
        it1 = it1.next

    while it2:
        curr = it2.value + carry
        carry = curr / 10
        value = curr % 10
        prev.next = node(value)
        prev = prev.next
        it2 = it2.next

    if carry:
        prev.next = node(carry)

    it = res
    while it:
        print it.value
        it = it.next
    return res

def get_node_peb():
    name = pal_get_platform_name()
    info = {
            "Description": name + " PCIe Expansion Board",
    }

    return node(info)

 def copynode( self, parent, nod ):
     thisnode = node( self, parent, leaf=nod.isLeaf, op=nod.operator, copy=True )
     parent.children.append( thisnode )
     
     if not thisnode.isLeaf:
         self.copynode( thisnode, nod.children[0] )
         self.copynode( thisnode, nod.children[1] )

	def test_hasNeighbor(self):
		neighbors = []
		n = node("0xfaca", "00:00:00:00:00:00:00:00", "0xffff")
		
		nei_nwk = ["0x0001", "0x0002", "0x0003"]
		nei_in = [7, 5, 3]
		nei_out = [7, 5, 3]

		for i in range(0,3):
			neighbors.append({"nwkAdr" : nei_nwk[i], "in_cost" : int(nei_in[i]), "out_cost" : int(nei_out[i])})
	
		nei_nwk = ["0x0001", "0x0002", "0x0003", "0x0004"]
		nei_in = [1, 3, 5, 1]
		nei_out = [1, 3, 5, 3]

		for i in range(0,4):
			neighbors.append({"nwkAdr" : nei_nwk[i], "in_cost" : int(nei_in[i]), "out_cost" : int(nei_out[i])})
	
		n.setCurNeighbors(neighbors)
		n.addNpPreNeighbors()
		n.processPreNeighbors()

		assert n.hasNeighbor("0x0001", n.getHistoricalNeighbors()) == True
		assert n.hasNeighbor("0x0002", n.getHistoricalNeighbors()) == True
		assert n.hasNeighbor("0x0003", n.getHistoricalNeighbors()) == True
		assert n.hasNeighbor("0x0004", n.getHistoricalNeighbors()) == True
		assert n.hasNeighbor("0x0005", n.getHistoricalNeighbors()) == False
		assert n.hasNeighbor("0x0000", n.getHistoricalNeighbors()) == False
		assert n.hasNeighbor("0xFFFF", n.getHistoricalNeighbors()) == False

def extract_title(url):
    page = urllib2.urlopen(url)
    if not page:
     print "Error down page" + url
    else:
        soup = BeautifulSoup(page, 'lxml')

        # get head title, this title is noisy
        head_title = soup.find('title').string

        # append h1 ~ h6 p a
        node_list = []
        for tag in tags:
            all_content = soup.find_all(tag)
            for content in all_content:
                if type(content) == None:
                    continue
                tmp = content.string
                if tmp == None:
                    continue
                else:
                    nod = node.node(tmp.rstrip('\n').lstrip('\n').rstrip(' ').lstrip(' '))
                    node_list.append(nod)

        for nod in node_list:
            nod.calculate_LCS(head_title)
            nod.calculate_pureness(head_title)
            nod.calculate_prefix_ratio()
        node_list.sort(key=lambda x: x.lcs_length, reverse=True)

        nod = node_list[0]
        if float(nod.pureness) > 0.5 and float(nod.prefix_ratio) == 0:
            return nod.lcs
        else:
            return head_title

    def rootify(self,center_branch):

	# remember the old branch:
	self.root_branch = center_branch

	# create a new node
	center_name = center_branch.ends[0].name
	center_name += "-" + center_branch.ends[1].name
	center_node = node.node(center_name,self)
	self.root = center_node
	
	# give it children branches
	child1 = branch.branch(center_branch.length/2)
	child1.addNode(center_node)
	child1.addNode(center_branch.ends[0])
	child2 = branch.branch(center_branch.length/2)
	child2.addNode(center_node)
	child2.addNode(center_branch.ends[1])
	center_node.child_branches.append(child1)
	center_node.child_branches.append(child2)

	# erase the original branch from the child nodes branch_list
	for kids in center_branch.ends:
	    kids.branch_list.remove(center_branch)

	# impose a hierarchy from the root
	center_node.imposeHierarchy()
        self.labelSubtrees()
        self.Get_Subnodes()
        self.root.Fill_Node_Dict()

  def generate_children(self, current):
    """ Generate the child nodes of the current node. This will
        apply the transformations listed above to the blank
        tile in the order specified in self.moves. The
        legal ones will be kept and states that have not
        been explored will be returned.
    """

    children = []
    blank_tile_index = None

    # Find the blank tile we will use to create new states
    for index in range(len(current.state)):
      if current.state[index] == "0":
        blank_tile_index = index
    
    # Get legal operations -
    operations = [blank_tile_index + move for move in self.moves if
                  self.test_operator(blank_tile_index, move)]
      
    # Create the new states
    for transformation in operations:

      child_state = copy.deepcopy(current.state)
      child_state[transformation] = "0"
      child_state[blank_tile_index] = current.state[transformation]

      # If these have not been explored, create the node
      if tuple(child_state) not in self._explored:
        child = node(child_state)
        child.parent = current
        child.operator = transformation - blank_tile_index
        children.append(child)
 
    return children

def get_node_fcb():
    name = pal_get_platform_name()
    info = {
            "Description": name + " Fan Control Board",
           }

    return node(info)

def main():
    #Declaring global variables                                                                                                                                                                                                                                                                                                                     
    global date
    global temp
    global nodes
    global f

    #Setting variables                                                                                                                                                                                                                                                                                                                              
    date = datetime.datetime.now()
    nodes = []
    f = open('data/time table', 'ar+')

    for line in f:
        nodes.append(node(str(line)))

    difference = calcdifference()

    print "The date is " + str(date) + " coffee was last brewed " + str(difference) + " hour(s) ago"

    temp = gettemp(difference)
    print "[Coffee is " + temp + "]"

    #Set up the GPIO                                                                                                                                                                                                                                                                                                                                
    GPIO.setmode(GPIO.BOARD)
    GPIO.setup(18, GPIO.OUT)

    print "Welcome to WOU Coffee! Your request is being processed..."

    findargs()

    #Close file                                                                                                                                                                                                                                                                                                                                     
    f.close()

    #Clean up GPIO                                                                                                                                                                                                                                                                                                                                  
    GPIO.cleanup()

def control(fileObjectXML, fileObjectXSD):
    '''the main control of the tree builder and validator'''
    lineXML = ""
    for line in fileObjectXML:
        lineXML = lineXML + line
                
    lineXSD = ""
    for line in fileObjectXSD:
        lineXSD = lineXSD + line
    
    lineXML = remove_comments(lineXML)
    lineXSD = remove_comments(lineXSD)
    lineXML = remove_extra_spaces(lineXML)
    lineXSD = remove_extra_spaces(lineXSD)
    lineXML = lineXML.replace('\n','')
    lineXSD = lineXSD.replace('\n','')  
      
    listXMLTags = makeNodeList(lineXML)  
    listXSDTags = makeNodeList(lineXSD)         
    
    rootXML = makeTree(listXMLTags)    
    rootXSD = makeTree(listXSDTags)    
    
    newrootXSD = node.node("","","",{},[],0)
    augmentXSDTree(rootXSD,newrootXSD, 0)
    #printTree(newrootXSD)
    tree_validator.treeCompare(rootXML.childList[0],newrootXSD.childList[0])  
    
    print("Successfully matched!!")
    print("No errors found")

def makeNode(line, d, adata):   
    ''' makes a object of type node from a string '''
    closing = line.find('</')
    if(closing != -1):
        d.depth = d.depth - 1
        line = line[2:len(line)-1]
    else:
        d.depth = d.depth + 1
        line = line[1:len(line)-1]        

    entities = line.split(' ')    
    if entities[0].find(':') != -1:
        tempName = entities[0].split(':')
        elementName = tempName[1]
        namespace  = tempName[0]
    else:
        elementName = entities[0]
        namespace = ""
        
        
    data = adata
    attrDict = {}
    childList = []
    i=1
    while(i<len(entities)):
        try:
            tempattr = entities[i].split('=')   
        except:
            print('Syntax Error in XSD :' + entities[i])
            exit(-1)        
        attrDict[tempattr[0]] = tempattr[1]
        i = i + 1
    
    newnode = node.node(elementName, namespace, data, attrDict, childList, d.depth)
    return newnode

def get_node_pdpb():
    name = pal_get_platform_name()
    info = {
            "Description": name + " PCIe Drive Plane Board",
    }

    return node(info)