def test_everseen(self):
     """ensure duplicate elements are ignored"""
     u = mi.unique_everseen('AAAABBBBCCDAABBB')
     self.assertEqual(
         ['A', 'B', 'C', 'D'],
         list(u)
     )

def kth_smallest_elem(node, k):
    ls = inorder_traversal(node)
    # unique_everseen removes duplicates from a list in O(N) time accorinding
    # to
    # http://stackoverflow.com/questions/480214/how-do-you-remove-duplicates-from-a-list-in-python-whilst-preserving-order
    result = list(unique_everseen(ls))
    return result[k - 1]

def fetch_skill_api():
    
    list_of_files = ['pre_6.txt']
    
    #list_of_letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' ']
    
    for i in list_of_files:
      master_skills_list = []
      i_path_join = os.path.join(os.path.abspath(os.path.dirname(__file__)), "..", "static", "data", i)
      with open(i_path_join, 'r') as fp:
        contents = fp.readlines()
        #print contents
        for line in contents:
          print line
          master_skills_list.extend(autosuggest_api(line))
      
      print master_skills_list
      
      
      c = list(unique_everseen(master_skills_list))
      ioutput_path_join = os.path.join(os.path.abspath(os.path.dirname(__file__)), "..", "static", "data", i + 'out')
      
      with open(ioutput_path_join, 'w') as fp:
        for item in c:
          fp.write("%s\n" % item)

def main():
	names = []
	types = ['Grass', 'Poison', 'Fire', 'Dragon', 'Flying', 'Water', 'Bug', 'Normal', 'Electric', 'Ground', 'Fairy', 'Fighting', 'Psychic', 'Rock', 'Steel', 'Ice', 'Ghost', 'Dark']
	scrapeNames(names, types)

	pokemon = {
		'images': {},
		'heights': {},
		'weights': {},
		'powers': {},
		'names': []
	}

	scrapePowers(pokemon, names)
	scrapeHeightsWeights(pokemon, names)

	names = list(unique_everseen(names))
	pokemon['names'] = names

	scrapeImages(pokemon, names)

	fileName = 'stats/stats.json'
	file = open(fileName, 'w')
	json.dump(pokemon, file, indent = 2)
	file.close()

    def get_tree(self, node=None, filtered_ids=[]):
        """
        node - головной объект, от которого строим дерево,
        если он не указан, то строим дерево из всех объектов.
        """
        def get_descendants(node):
            descendents = []
            children = node.get_children()
            children.filter(pk__in=filtered_ids)
            for n in children:
                n_descendents = get_descendants(n)
                n_descendents = [n for n in n_descendents if n.pk in filtered_ids]
                descendents += n_descendents
            return [node] + descendents

        if node:
            tree = get_descendants(node)
        else:
            tree = []
            lev1_pages = self.filter(level=1)
            if filtered_ids:
                lev1_pages = self.filter(pk__in=filtered_ids)
            for node in lev1_pages:
                tree += get_descendants(node)
        from  more_itertools import unique_everseen
        tree = list(unique_everseen(tree))
        return tree

def interpret(atom_index, grammar, user_input):
    stripped_input = strip_punctuation(user_input)

    base_atoms_raw = atom_index.query(stripped_input)
    base_atoms = []
    for a in base_atoms_raw:
        base_atoms.append(a.clone_nonstopword())

    stop_words = filter(lambda a: a.get_stopword(), grammar.get_atoms())
    extra_atoms = []
    for stop_word in stop_words:
        if not stop_word in base_atoms:
            extra_atoms.append(stop_word)
    expanded_atoms = base_atoms + extra_atoms

    result = []
    for query_pattern in grammar.get_query_patterns():
        phrases = generate_phrases(grammar, expanded_atoms)
        queries = query_pattern.resolve(phrases)
        for query in queries:
            result.append(query)
    result = filter(lambda q: q.get_score() > 0, result)
    result = filter(lambda q: q.validate(base_atoms), result)
    result = list(unique_everseen(result, lambda q: q.get_english()))
    result.sort(key=lambda q: q.get_score())
    result.reverse()
    for q in result:
        q.set_base_atoms(base_atoms)
    return result

def ref_insert_line(line, form):
    """
    Inserts \ref{} functions into tex files by substituting for a regex.

    :param line: a line from a tex file, in the form of a string,
        which we want to process and insert references into
    :param form: a regular expression specification
        for a string to be replaced.
    :return: a string, wherein all of the strings specified by
        form are replaced by \ref{form}
    """
    # lineIterator = form.search(line)
    # searchAndSub = []
    # lineNew = line
     # while searchAndSub is not None:
    #     searchAndSub = form.search(line)
    #     lineNew = lineNew.replace()

    searchresults = form.findall(line)
    iterableStrings = list(unique_everseen(searchresults))
    lineNew = line
    for substring in iterableStrings:
        lineNew = lineNew.replace(substring, r'(\ref{' + substring[1:-1] + r'})')

    return lineNew

    def create_a_pb_unit_cell(self,
                              fpb_prop,
                              uc_name
                              ):
        '''
        fpb_prop: a tuple contains:
            fuel_temps: temperature list for unique pebbles in the unit cell
            a matrix of unique pebbles x n layers of fuel in a triso
            coating_temps: a list that contains temp for each of the non-fuel layers in triso, e.g. 4x5
            cgt: central graphite temperature
            sht: shell temperature
            burnups: a list of 14 burnups
        uc_name: unit cell name
        '''
        fuel_temps, coating_temps, cgt, sht, uc_name, burnups, pb_comp_dir = fpb_prop
        fpb_list = []
        unique_fpb_list = {}
        unique_burnups = list(unique_everseen(burnups))
        unique_burnup_nb = len(unique_burnups)
        assert fuel_temps.shape[0] == unique_burnup_nb, 'wrong dimension %s' %str(fuel_temps.shape)
        assert coating_temps.shape[0] == unique_burnup_nb, 'wrong dimension' 

        # create a list of unique pebbles
        for i, bu in enumerate(unique_burnups):
            pb_name = 'pb%s%d' % (uc_name, bu)
            unique_fpb_list[bu] = self.create_a_fuel_pebble(fuel_temps[bu-1, :], 
                                                            coating_temps[unique_burnups[i]-1, :],
                                                            cgt, sht,
                                                            pb_name,
                                                            unique_burnups[i], 
                                                            pb_comp_dir)
        # create a list of all the 14 fuel pebbles, some of them are exactly the same
        for bu in burnups:
            fpb_list.append(unique_fpb_list[bu])
        return fpb_list

def _countEntities(cols):
	for i in range(len(cols)):
		entries = cols[i]["entries"]
		entityCount = 0
		multipleEnts = False
		for entry in entries:
			entrySoup = BeautifulSoup(entry, "lxml")
			links = entrySoup.findAll("a")
			linksHref = [aTag["href"] for aTag in links]
			linksHref = list(unique_everseen(linksHref))
			linksCount = len(links)
			for link in links:
				# Image werden nicht gezählt
				if link.find("img") != None:
					linksCount -= 1
				# Ebenso dürfen es nur Wikipedia-interne Links sein
				elif link["href"][0:5] != "/wiki":
					linksCount -= 1
				# Manche Tabellen setzen doppelte Verlinkunden (e.g. TableID = 513, List of Olympic medalists in basketball)
				elif link["href"] in linksHref:
					linksHref.remove(link["href"]) # Beim ersten Mal löschen
				elif link["href"] not in linksHref:
					linksCount -= 1 # Bei jedem weiteren Mal, die Anzahl korrigieren
			if linksCount > 0:
				entityCount += 1
				if linksCount > 1:
					multipleEnts = True

		# Bewertung: Maximal 50 Punkte möglich (100% sind Entitäten)
		cols[i]["rating"] = int(math.floor(MAX_ENTITIES_POINTS * (entityCount / len(entries))))
		cols[i]["entityCount"] = entityCount
		cols[i]["multipleEntities"] = multipleEnts

def wordNetNER(document):
	plant_sns = (wn.synsets('plant', pos="n"))
	plant = plant_sns[1] #(botany) a living organism lacking the power of locomotion #hardcoded

	wordnet_names = []
	#wordnet_lemmatizer = WordNetLemmatizer   ##Lematizer doesn't work....
	for word in document:
		#word = wordnet_lemmatizer.lemmatize(word) ##Lematizer doesn't work...
		mySynsets = wn.synsets(word, pos="n")

		i = 0
		for i in range(0, 3):
			try:
				given_word = mySynsets[i] #tries first 3 synsets
				definition = (given_word.definition())
				p1 = re.compile('plant(s?)\s')
				p2 = re.compile('organism(s?)\s')
				p3 = re.compile('animal(s?)\s')
				match1 = p1.search(definition)
				match2 = p2.search(definition)
				match3 = p3.search(definition)

				if match1 or match2 or match3:  #if the given word has "plants" or "animals" in the def, check to see how similar it is to "plant"
					similarity_score = (given_word.path_similarity(plant)) #check similarity score
					if similarity_score >= 0.2:
						#print(similarity_score)
						#print ("The words: "+(str(given_word)) + "  has a sim score of:  " +str(similarity_score))
						wordnet_names.append(word)
						named_entities.append(word)
			#hypernym = given_word.hypernyms() #hypernym is list #synset 'organism' exists #can't search in the hypernyms....hmm...
				i += 1
			except IndexError:
				pass
	wordnet_ner = (list(unique_everseen(wordnet_names)))
	return wordnet_ner

 def keys(self, pattern):
     """Aggregated keys method."""
     def _keys(node, pattern):
         for result in node.keys(pattern):
             self._output_queue.put(result)
     results = self._runner(_keys, pattern)
     # return list(OrderedDict.fromkeys(results))
     return sorted(list(unique_everseen(results)))

	def clash_table(self,i,j):
		units = [];
		units.extend(self.row(i));
		units.extend(self.col(j));
		units.extend(self.box(which_box(i,j)));
		units = list(unique_everseen(units));
		values = list(chain(*[ list(unit.available_values) for unit in units ]));
		return(table(values));

 def __init__(self, data=np.asarray([[0, 0]]), cls_label=np.asarray([0]),
              ses_label=np.asarray([0]), buff_size=BUFF_SIZE,
              n_components=(K_CLS, K_SES, K_RES), beta=BETA,
              NMF_updates='beta', n_iter=N_ITER, lambdas=[0, 0, 0],
              normalize=False, fixed_factors=None, verbose=0,
              dist_mode='segment',Wn=None):
     self.data_shape = data.shape
     self.buff_size = np.min((buff_size, data.shape[0]))
     self.n_components = np.asarray(n_components, dtype='int32')
     self.beta = theano.shared(np.asarray(beta, theano.config.floatX),
                               name="beta")
     self.verbose = verbose
     self.normalize = normalize
     self.lambdas = np.asarray(lambdas, dtype=theano.config.floatX)
     self.n_iter = n_iter
     self.NMF_updates = NMF_updates
     self.iters = {}
     self.scores = []
     self.dist_mode = dist_mode
     if fixed_factors is None:
         fixed_factors = []
     self.fixed_factors = fixed_factors
     fact_ = np.asarray([base.nnrandn((self.data_shape[1],
                                       np.sum(self.n_components)))
                         for i in more_itertools.unique_everseen(itertools.izip(cls_label,
                                                                                ses_label))])
     self.W = theano.shared(fact_.astype(theano.config.floatX), name="W",
                            borrow=True, allow_downcast=True)
     fact_ = np.asarray(base.nnrandn((self.data_shape[0],
                                      np.sum(self.n_components))))
     self.H = theano.shared(fact_.astype(theano.config.floatX), name="H",
                            borrow=True, allow_downcast=True)
     self.factors_ = [self.H, self.W]
     if Wn is not None:
         self.Wn = Wn
     self.X_buff = theano.shared(np.zeros((self.buff_size,
                                           self.data_shape[1])).astype(theano.config.floatX),
                                 name="X_buff")
     if (self.NMF_updates == 'groupNMF') & (self.dist_mode == 'iter'):
         self.cls_sums = theano.shared(np.zeros((np.max(cls_label)+1,
                                                self.data_shape[1],
                                                self.n_components[0])
                                                ).astype(theano.config.floatX),
                                       name="cls_sums",
                                       borrow=True,
                                       allow_downcast=True)
         self.ses_sums = theano.shared(np.zeros((np.max(ses_label)+1,
                                                self.data_shape[1],
                                                self.n_components[1])
                                                ).astype(theano.config.floatX),
                                       name="ses_sums",
                                       borrow=True,
                                       allow_downcast=True)
         self.get_sum_function()
     self.get_updates_functions()
     self.get_norm_function()
     self.get_div_function()

def getLessonList(courselink, quality):
    global session
    coursehtml = (session.get(courselink)).text

    lessonLinkRegex = re.compile('https?://www.cybrary.it/video/\w+(?:-[\w]+)*/')
    matchedLessonLink = list(unique_everseen(lessonLinkRegex.findall(coursehtml)))

    for link in matchedLessonLink:
        print "Downloading "+link
        downloadVideos(getVideoLink(link), quality)

def reorder_cls_ses(data, cls, ses, with_index=False):
    """reorder the data such that there is only
    one continuous bloc for each pair class/session

    Parameters
    ----------
    data : array
        the data
    cls : array
        the class labels for the data
    ses : array
        the session label for the data
    with_index : Boolean (default False)
        if True, the function returns the reordered indexes together
        with data and labels

    Returns
    -------
    data : array with the same shape as data
        reordered data
    cls : array with the same shape as cls
        reordered class labels
    ses : array with the same shape as ses
        reordered session labels
    ind : array with the same shape as data.shape[1]
        reordered indexes (only if with_index==True)
    """

    data_ordered = np.zeros((data.shape))
    cls_ordered = np.zeros((cls.shape))
    ses_ordered = np.zeros((ses.shape))
    if with_index:
        index = np.arange((data.shape[1],))
        index_ordered = np.zeros((index.shape))
    data_fill = 0
    for i in more_itertools.unique_everseen(itertools.izip(cls, ses)):
        ind = np.where((cls == i[0]) & (ses == i[1]))[0]
        bloc_length = data[(cls == i[0]) & (ses == i[1]), :].shape[0]
        data_ordered[data_fill:data_fill+bloc_length, ] = data[ind, :]
        cls_ordered[data_fill:data_fill+bloc_length] = cls[ind]
        ses_ordered[data_fill:data_fill+bloc_length] = ses[ind]
        if with_index:
            index_ordered[data_fill:data_fill+bloc_length] = index[ind]
        data_fill += bloc_length
    if with_index:
        return {
            'data': data_ordered,
            'cls': cls_ordered,
            'ses': ses_ordered,
            'ind': index_ordered}
    else:
        return {
            'data': data_ordered,
            'cls': cls_ordered,
            'ses': ses_ordered}

def onlymonths(wordfile,months):
    if len(wordfile) == months:
        return map(lambda x:x.split("\n")[0],wordfile)
    splt = map(lambda x: x.split(","),wordfile)
    startdate = map(lambda x: x[0],splt)
    times = map(lambda x: int(x[1]),splt)
    times = mergedate(startdate,times)
    startdate = list(unique_everseen(startdate))
    wordfile = map(lambda x:x[0]+ "," + str(x[1]),zip(startdate,times))


    return wordfile

def matchOrganisms2(bigrams):
	latin_names = []
	for grams in bigrams:
		(w1, w2) = grams.split(" ")
		p1 = re.compile('[a-z]{2,}[b-df-hj-np-tv-z]{1,}(i$|is$|ia$|ae$|um$|us$|es$|arum$)') #wont pick up ones that match in 'a'; too many false positives
		match1 = p1.search(w1)
		p2 = re.compile('[a-z]{2,}[b-df-hj-np-tv-z]{1,}(a$|i$|is$|ia$|ae$|um$|us$|es$|arum$)') #picks up the word 'genes'
		match2 = p2.search(w2)
		if match1 and match2:
			latin_names.append(grams)
			named_entities.append(grams)
	return (list(unique_everseen(latin_names)))

def bootstrap(region, environment, domain, instance_type, coreos_channel,
              coreos_version, available, flotilla_container):
    coreos = CoreOsAmiIndex()
    cloudformation = FlotillaCloudFormation(environment, domain, coreos)
    region_meta = RegionMetadata(environment)
    regions = [r for r in unique_everseen(region)]
    cloudformation.tables(regions)
    region_params = region_meta.store_regions(regions, available, instance_type,
                                              coreos_channel, coreos_version,
                                              flotilla_container)
    cloudformation.schedulers(region_params)
    logger.info('Bootstrap complete')

def monte_carlo(forward_,reverse_):
	forward=[]
	reverse=[]
	fasta_sequences = SeqIO.parse(open(forward_),'fasta')
	for fasta in fasta_sequences:
		name, sequence = fasta.id, fasta.seq
		forward.append(str(sequence).replace('\n', ''))
	fasta_sequences = SeqIO.parse(open(reverse_),'fasta')
	for fasta in fasta_sequences:
		name, sequence = fasta.id, fasta.seq
		reverse.append(str(sequence).replace('\n', ''))
	seed=1000 # Iterations
	matches=[]
	count=0
	cytosine=0
	fh=open('forward_d/monte.carlo', 'w+')
	match = 2
	mismatch = -1
	scoring = swalign.NucleotideScoringMatrix(match, mismatch)
	sw = swalign.LocalAlignment(scoring)
	while seed != 0:
		sequence=forward[int(random.random()*(len(forward)-1))] # get a random sequence from [ 0, N ] contigs
		width= int(random.random()*(len(sequence)-1) *0.20+13) # Take lower 13+[0-20] % of sequence length
		first=int(random.random()*(len(sequence)-1-width)) 
		subsequence=sequence[first:first+width]
		for x in reverse:
			index=x.find(subsequence)
			if  index != -1 :
				count_=ccount(reverse,reverse.index(x))+index
				fh.write(str(count_)+"\t"+str(eval(str(count_+width)))+"\n")
				for i in range(0,width):
					matches.append(count_+i)
					count+=1
			else:
				count_=ccount(reverse,reverse.index(x))+index
				alignment = sw.align(x,subsequence)
				cytosine+=alignment.dump()
		seed-=1
	fh.close()
	forward_length=ccount(forward,"1",True)
	xlim=ccount(reverse,"1",True)
	plt.hlines(1,1,xlim)  # Draw a horizontal line
	plt.xlim(0,xlim)
	plt.ylim(0.5,1.5)
	matches=list(unique_everseen(matches))
	y = np.ones(np.shape(matches))   # Make all y values the same
	plt.plot(matches,y,'|',ms = 40)  # Plot a line at each location specified in `matches`
	plt.axis('off')
	plt.show()
	print "[",count,"/ ",forward_length,"]  hits, [",cytosine,"]"

def get_image_url_list(category, data_type=None):
    """
    For a given data type, returns a list of filenames.

    Args:
        category (string): Category name as a string (from list_image_sets())
        data_type (string, optional): "train" or "val"

    Returns:
        list of strings: list of all filenames for that particular category
    """
    df = _load_data(category, data_type=data_type)
    image_url_list = list(
        unique_everseen(list(img_dir + df['fname'])))
    return image_url_list