def find(**kwargs):
    """Find VPCs by name or ID across all regions."""
    vpc_ids = kwargs.get("ids", list())
    vpc_names = kwargs.get("names", list())
    vpcs = list()

    if type(vpc_ids) == str:
        vpc_ids = [vpc_ids]
    if type(vpc_names) == str:
        vpc_names = [vpc_names]

    for vpc_name in vpc_names:
        n_list = vpc_name.split("-")
        if len(n_list) != 4:
            raise NameError, "Invalid VPC name: " + vpc_name
        (reg, env) = ("-".join(n_list[:3]), n_list[3])
        res = Region(name=reg).find_vpcs(env=env)
        for v in res:
            if not v in vpcs:
                vpcs.append(v)

    for vpc_id in vpc_ids:
        for region in get_regions():
            res = region.find_vpcs(id=vpc_id)
            if res:
                for v in res:
                    if not v in vpcs:
                        vpcs.append(v)
                break

    if not vpc_id and not vpc_ids:
        for region in get_regions():
            res.extend(region.find_vpcs())

    return vpcs

	def open(self, region=None, exemptions=None, open_border=True):
		'''
		Method: open
		Description: Opens (visits all cells and destroys all walls within) the given region, avoiding the given exempt regions.
		Parameters: region=None, exemptions=None
			region: Region - A region for maze opening to span
			exemptions: Regions - A collection of regions for maze opening to avoid
		Return: None
		'''

		# Ensure that valid boundaries are set.
		if region is None:
			region = Region((0, 0), (self.get_width(), self.get_height()))

		# Construct a set of valid cells.
		valid_cells = self.valid_cell_set(region, exemptions)

		# Visit all valid cells and open the walls as necessary (region borders only open if open_border is True).
		for cell in valid_cells:
			cell.visit()
			border_directions = region.on_border(cell.m_position)
			for direction in list(Direction):

				# Ensure that the border is allowed to be destroyed.
				if (self.get_neighbor_cell(cell, direction) is not None) and (open_border) or (direction not in border_directions):
					self.set_wall(cell, direction, False)

    def _divideAndCount(self, n):
        # devide the region into n*n grids to compute the entropy
        # p(i) = # of elements in that grid, to the total number of grids
        # it returns the list of subregions associated with the number elements falling into that region
        element_number = self.getElementNumber()
        region = Region(self._event["region"])
        subregions = region.divideRegions(n, n)

        # Laplacian smoothed
        pro = [1.0] * n * n
        s = n * n
        elements = self._event[self._element_type]
        for element in elements:
            lat = element["location"]["latitude"]
            lng = element["location"]["longitude"]
            flag = False
            i = 0
            for subregion in subregions:
                if subregion.insideRegion([lat, lng]):
                    pro[i] += 1.0
                    s += 1
                    if flag == True:
                        raise Exception("bad data")
                    flag = True
                i += 1
        for i in xrange(0, n * n):
            pro[i] /= s
        return pro

	def overUnder(self, point, onThresh=0):
		"""
		Arguments:
			point: [Vector] A point
			onThresh: [float] The permitted error when testing for being "on" a line
		Returns: 1 if this point lies on or vertically over segment, -1 if
			lies vertically under, 0 if out of range over x
		"""
		
		rx = Region(self.p1.x, self.p2.x)
		ry = Region(self.p1.y, self.p2.y)
		
		if (not rx.contains(point.x)) or self.p1.x == self.p2.x:
			# Point is out of range over x
			return 0
		
		# y at the point where point is
		yThresh = self.p1.y + \
			(self.p2.y - self.p1.y) * \
			(point.x - self.p1.x) / (self.p2.x - self.p1.x)
		
		if abs(point.y - yThresh) < onThresh:
			# On segment
			return 1
		if point.y >= yThresh:
			# Over segment
			return 1
		else:
			# Under segment
			return -1

def buildAllCorpus(element_type='photos', time_interval_length=14, debug=False, paras={}):
    # return a dict = {region : its local corpus}
    assert element_type in ['photos', 'tweets']

    all_corpus = {}
    if element_type == 'photos':
        config = InstagramConfig
    else:
        config = TwitterConfig

    coordinates = [config.min_lat, config.min_lng,
                   config.max_lat, config.max_lng]

    nyc = Region(coordinates)
    region_list = nyc.divideRegions(25, 25)
    region_list = nyc.filterRegions(region_list, test=True, n=25, m=25, element_type=element_type)

    # 14 days ago
    now = int(tool.getCurrentStampUTC())

    num = 0
    for region in region_list:
        if debug and num > 0:
            # speed up the debugging
            pass
        else:
            cor = Corpus()
            cor.buildCorpus(region, [now - time_interval_length * 3600 * 24, now], element_type, paras)
        all_corpus[region.getKey()] = cor
        num += 1
        print 'build corpus %d' % (num)
    return all_corpus

    def _divideAndCount(self, n):
        # devide the region into n*n grids to compute the entropy
        # p(i) = # of photos in that grid, to the total number of grids
        # it returns the list of subregions associated with the number photos falling into that region
        photo_number = self.getPhotoNumber()
        region = Region(self._event["region"])
        subregions = region.divideRegions(n, n)

        # Laplacian smoothed
        pro = [1.0 / n / n] * n * n

        photos = self._event["photos"]
        for photo in photos:
            lat = photo["location"]["latitude"]
            lng = photo["location"]["longitude"]
            flag = False
            i = 0
            for subregion in subregions:
                if subregion.insideRegion([lat, lng]):
                    pro[i] += 1.0 / n / n
                    if flag == True:
                        raise Exception("bad data")
                    flag = True
                i += 1
        return pro

    def _divideAndCount(self, n):
        # devide the region into n*n grids to compute the entropy
        # p(i) = # of photos in that grid, to the total number of grids
        # it returns the list of subregions associated with the number photos falling into that region
        photo_number = self.getPhotoNumber()
        region = Region(self._event['region'])
        subregions = region.divideRegions(n, n)

        # Laplacian smoothed
        pro = [1.0] * n * n
        s = n * n
        photos = self._event['photos']
        for photo in photos:
            lat = photo['location']['latitude']
            lng = photo['location']['longitude']
            flag = False
            i = 0
            for subregion in subregions:
                if subregion.insideRegion([lat, lng]):
                    pro[i] += 1.0
                    s += 1
                    if flag == True:
                        raise Exception('bad data')
                    flag = True
                i += 1
        for i in xrange(0, n * n):
            pro[i] /= s
        return pro

	def intersect(self, other, pThresh=0):
		"""Determines the intersection point of self and other
		Arguments:
			other: [Segment] A segment
			pThresh: [float] The permitted error when testing for parallel
				lines (default: 0) 
		Returns: [List [Vector]] Empty list for no intersect, one Vector for a
			point-intersect, two for a segment-intersect 
		"""
		
		# Manually handles zero-length lines
		if self.len() == 0 or other.len() == 0: return [] 
		
		# Manually handles point overlaps
		if self == other: return [self.p1, self.p2]
		if self.p1 == other.p1 or self.p1 == other.p2: return []
		if self.p2 == other.p1 or self.p2 == other.p2: return []
		
		# Maps problem to problem of locating other's x-intersect
		toMove = self.p1.mul(-1)
		toRotate = -1 * self.angle()
		s1 = self.copy()
		s2 = other.copy()
		s1.move(toMove)
		s2.move(toMove)
		s1.rotate(toRotate)
		s2.rotate(toRotate)
		
		# No x-intersect -- s2 does not cross s1's line
		if abs(s2.p1.y) > pThresh and numpy.sign(s2.p1.y) == numpy.sign(s2.p2.y):
			return []
		
		# Segments are parallel
		if abs(s2.p1.y) <= pThresh and abs(s2.p1.y) <= pThresh:
			s1region = Region(s1.p1.x, s1.p2.x)
			s2region = Region(s2.p1.x, s2.p2.x)
			overlap = s1region.overlapRegion(s2region)
			
			if overlap is False:
				# No intersection
				return []
			else:
				# Calculates segment of intersection
				p1Intersect = fromPolar(overlap.left, self.angle()) \
					.add(self.p1)
				p2Intersect = fromPolar(overlap.len(), self.angle()) \
					.add(p1Intersect)
				return [p1Intersect, p2Intersect]
		
		# Calculates the x-intersect
		xIntersect = s2.p1.x + (s2.p2.x - s2.p1.x) * (s2.p1.y / (s2.p1.y - s2.p2.y))
		
		if not Region(s1.p1.x, s1.p2.x).contains(xIntersect):
			# No x-intersect -- s2 crosses s1's line out of range of s1
			return []
		
		# Calculates and returns the intersection point
		pIntersect = fromPolar(xIntersect, self.angle()).add(self.p1)
		return [pIntersect]

def testCount():
	rows = 5
	cols = 5
	coverage = 20
	numbits = 10
	numRounds = 500
	trainingRounds = numRounds/4
	originalInputVector = InputVector(numbits)
	inputVector = InputVector(0)

	predictions = dict()
	#repeat several times to increase activity:
	for i in range(3):
		inputVector.extendVector(originalInputVector)

	desiredLocalActivity = DESIRED_LOCAL_ACTIVITY

	newRegion = Region(rows,cols,inputVector,coverage,desiredLocalActivity)
	outputVector = newRegion.getOutputVector()
	correctBitPredictions = 0
 
	for round in range(numRounds): # This test executes the CLA for a set number of rounds. 
     
		#print("Round: " + str(round))
		# if (round % 2 == 0):
		# 	val = 682
		# else:
		# 	val = 341
		val = Ultrasonic(brick, PORT_1).get_sample()
		setInput(originalInputVector,val)
		inputString = inputVector.toString()
		outputString = outputVector.toString()
		#print(originalInputVector.toString())
           
		#for bit in originalInputVector.getVector():
		# 	print(bit.bit)
		# print('')
		# print(inputString)


		if outputString in predictions:
			currentPredictionString = predictions[outputString]
		else:
			currentPredictionString = "[New input]"
		pred[outputString] = inputString
		print("Round: %d" % round) # Prints the number of the round
		printStats(inputString, currentPredictionString)
		if (round > trainingRounds):
			correctBitPredictions += stringOverlap(currentPredictionString, predictions[outputString])
				 

		newRegion.doRound()
		printColumnStats(newRegion)
	for key in predictions:
		print("key: " + key + " predictions: " + predictions[key])

	print("Accuracy: " + str(float(correctBitPredictions)/float((30*(numRounds-trainingRounds)))))

 def _getRandomCenters(self, leftTop, rightBottom):
     dummyRegion = Region(leftTop, rightBottom)
     childRegionCount = int(round(pow(Settings.numberOfcenters, 0.5)))
     dummyRegion.segmentByChildCount(childRegionCount, childRegionCount)
     randomCenters = []
     for childRegionRow in dummyRegion.getChildRegions():
         for childRegion in childRegionRow:
             randomCenter = self._getRandomCenter(childRegion.getLeftTop(), childRegion.getRightBottom())
             randomCenters.append(randomCenter)
     return randomCenters

def generateData2():
#   if sparse:
    #rep = Representor()

    all_corpus = buildAllCorpus(time_interval_length=14, debug=True)
    true_event_list, false_event_list = loadUnbalancedData()
    BaseFeatureProduction.GenerateArffFileHeader()

    for event in true_event_list + false_event_list:
        r = Region(event['region'])
        corpus = all_corpus[r.getKey()]
        BaseFeatureProduction(event, corpus, None).printFeatures()

    def setup_map(self, options):
        '''
        Method to set up essential map data given by the server.
        '''
        map_type = options[0]

        for i in range(1, len(options), 2):

            if map_type == 'super_regions':

                super_region = SuperRegion(options[i], int(options[i + 1]))
                self.map.super_regions.append(super_region)

            elif map_type == 'regions':

                super_region = self.map.get_super_region_by_id(options[i + 1])
                region = Region(options[i], super_region)
                
                self.map.regions.append(region)
                super_region.regions.append(region)

            elif map_type == 'neighbors':

                region = self.map.get_region_by_id(options[i])
                neighbours = [self.map.get_region_by_id(region_id) for region_id in options[i + 1].split(',')]

                for neighbour in neighbours:
                    region.neighbours.append(neighbour)
                    neighbour.neighbours.append(region)
            
        if map_type == 'wastelands':

            for i in range(1, len(options)):

                region = self.map.get_region_by_id(options[i])
                region.is_wasteland = True


        if map_type == 'neighbors':
            
            for region in self.map.regions:

                if region.is_on_super_region_border:
                    continue

                for neighbour in region.neighbours:

                    if neighbour.super_region.id != region.super_region.id:

                        region.is_on_super_region_border = True
                        neighbour.is_on_super_region_border = True

def test():
    coordinates = [InstagramConfig.photo_min_lat,
            InstagramConfig.photo_min_lng,
            InstagramConfig.photo_max_lat,
            InstagramConfig.photo_max_lng
            ]
    huge_region = Region(coordinates)
    regions = huge_region.divideRegions(5,5)  #Warning: DO NOT SET THIS BELOW 5 OR MEMORY OVERFLOW
    
    for i in range(25):
        test_region = regions[i]
        test_region.display()
        ts = InstagramTimeSeries(test_region, 1355765315, 1355765315+30*24*3600)
        print ts.buildTimeSeries()

def main():
    """Creates a specified region and downloads files from USGS."""
    # example:
    # ./GetRegion.py --name BlockIsland --ymax 41.2378 --ymin 41.1415 --xmin -71.6202 --xmax -71.5332

    # defaults
    default_orthoIDs     = ','.join(Region.productIDs['ortho'])
    default_elevationIDs = ','.join(Region.productIDs['elevation'])
    default_landcoverIDs = ','.join(Region.productIDs['landcover'])

    # parse options and get results
    parser = argparse.ArgumentParser(description='Create regions and download files from USGS.')
    parser.add_argument('--name', required=True, type=str, help='name of the region to be generated')
    parser.add_argument('--xmax', required=True, type=float, help='easternmost longitude (west is negative)')
    parser.add_argument('--xmin', required=True, type=float, help='westernmost longitude (west is negative)')
    parser.add_argument('--ymax', required=True, type=float, help='northernmost latitude (south is negative)')
    parser.add_argument('--ymin', required=True, type=float, help='southernmost longitude (south is negative)')
    parser.add_argument('--tilesize', type=int, help='tilesize value (default %d)' % Region.tilesize)
    parser.add_argument('--scale', type=int, help='scale value (default %d)' % Region.scale)
    parser.add_argument('--vscale', type=int, help='vscale value (default %d)' % Region.vscale)
    parser.add_argument('--trim', type=int, help='trim value (default %d)' % Region.trim)
    parser.add_argument('--sealevel', type=int, help='sealevel value (default %d)' % Region.sealevel)
    parser.add_argument('--maxdepth', type=int, help='maxdepth value (default %d)' % Region.maxdepth)
    parser.add_argument('--orthoIDs', default=default_orthoIDs, type=checkOrthoIDs, help='ordered list of product IDs (default %s)' % default_orthoIDs)
    parser.add_argument('--elevationIDs', default=default_elevationIDs, type=checkElevationIDs, help='ordered list of product IDs (default %s)' % default_elevationIDs)
    parser.add_argument('--landcoverIDs', default=default_landcoverIDs, type=checkLandcoverIDs, help='ordered list of product IDs (default %s)' % default_landcoverIDs)
    parser.add_argument('--enable-ore', action='store_true', dest='doOre', default=False, help='enable ore generation')
    parser.add_argument('--enable-schematics', action='store_true', dest='doSchematics', default=False, help='enable schematic usage')
    parser.add_argument("-v", "--verbosity", action="count", \
                        help="increase output verbosity")
    parser.add_argument("-q", "--quiet", action="store_true", \
                        help="suppress informational output")
    args = parser.parse_args()

    # set up logging
    log_level = klog_levels.LOG_INFO
    if args.quiet:
        log_level = klog_levels.LOG_ERROR
    if args.verbosity:
        # v=1 is DEBUG 1, v=2 is DEBUG 2, and so on
        log_level += args.verbosity
    log = klogger(log_level)

    # create the region
    log.log_info("Creating new region %s..." % args.name)
    myRegion = Region(name=args.name, xmax=args.xmax, xmin=args.xmin, ymax=args.ymax, ymin=args.ymin, scale=args.scale, vscale=args.vscale, trim=args.trim, tilesize=args.tilesize, sealevel=args.sealevel, maxdepth=args.maxdepth, oiIDs=args.orthoIDs, lcIDs=args.landcoverIDs, elIDs=args.elevationIDs, doOre=args.doOre, doSchematics=args.doSchematics)

    log.log_info("Retrieving files...")
    myRegion.log = log
    myRegion.getfiles()

    def range(self, event):
        """Initiate a range search using a selected rectangular region."""
        
        p = (event.x, self.toCartesian(event.y))
         
        if self.selectedRegion is None:
            self.selectedStart = Region(p[X],p[Y],  p[X],p[Y])
        self.selectedRegion = self.selectedStart.unionPoint(p)
        
        self.paint()
        
        # return (node,sub-tree) where sub-tree is True if draining entire tree
        # rooted at node. Draw these as shaded red rectangle to identify whole
        # sub-tree is selected.
        for pair in self.tree.range(self.selectedRegion):
            p = pair[0].point
            
            if pair[1]:
                self.canvas.create_rectangle(pair[0].region.x_min, self.toTk(pair[0].region.y_min), 
                                             pair[0].region.x_max, self.toTk(pair[0].region.y_max),
                                             fill='Red', stipple='gray12')
            else:
                self.canvas.create_rectangle(p[X] - BoxSize, self.toTk(p[Y]) - BoxSize, 
                                             p[X] + BoxSize, self.toTk(p[Y]) + BoxSize, fill='Red')

        self.queryRect = self.canvas.create_rectangle(self.selectedRegion.x_min, self.toTk(self.selectedRegion.y_min),  
                                                     self.selectedRegion.x_max, self.toTk(self.selectedRegion.y_max), 
                                                     outline='Red', dash=(2, 4))

 def range(self, event):
     """Initiate a range search using a selected rectangular region."""
     
     p = (event.x, self.toCartesian(event.y))
      
     if self.selectedRegion is None:
         self.selectedStart = Region(p[X],p[Y],  p[X],p[Y])
     self.selectedRegion = self.selectedStart.unionPoint(p)
     
     self.paint()
     
     # return (node,status) where status is True if draining entire tree rooted at node. Draw these
     # all in Yellow using another inorder traversal
     for pair in self.tree.range(self.selectedRegion):
         
         if pair[1]:
             self.canvas.create_rectangle(pair[0].region.x_min, self.toTk(pair[0].region.y_min), 
                                          pair[0].region.x_max, self.toTk(pair[0].region.y_max),
                                          fill='Red', stipple='gray12')
         else:
             p = pair[0][0]   # ignore data and grab point
             self.canvas.create_rectangle(p[X] - RectangleSize, self.toTk(p[Y]) - RectangleSize, 
                                          p[X] + RectangleSize, self.toTk(p[Y]) + RectangleSize, fill='Red')
     
     
     self.queryRect = self.canvas.create_rectangle(self.selectedRegion.x_min, self.toTk(self.selectedRegion.y_min),  
                                                  self.selectedRegion.x_max, self.toTk(self.selectedRegion.y_max), 
                                                  outline='Red', dash=(2, 4))

	def doubleCut(self, other, doreverse=True):
		'''takes self and another AngularDomain, and slices both of them,
		i.e.: cuts each region in the endpoints of the other AngularDomains
		regions, i.e.: ater this operation, for each region R1 in one
		AngularDomain, if there exists an Region R2 in the other so that R1
		contains R2 or R2 contains R1, the endpoints of R1 and R2 are the
		same.'''
		i,j= 0,0
		while i<len(self) and j<len(other):
			p= Region.relativePosition(self[i],other[j])
			if p==1:
				i+=1
			elif p==2:
				j+=1
			elif p==3:
				self.cutRegionOnPoint(i, other[j][0])
				i+=1
				other.cutRegionOnPoint(j, self[i][1])
				j+=1
			elif p==4:
				other.cutRegionOnPoint(j, self[i][0])
				j+=1
				self.cutRegionOnPoint(i, other[j][1])
				i+=1
			elif p==5:
				i= self.cutRegionOnPoint(i, other[j][0])
				i= self.cutRegionOnPoint(i, other[j][1])
				j+=1
			elif p==6:
				j= other.cutRegionOnPoint(j, self[i][0])
				j= other.cutRegionOnPoint(j, self[i][1])
				i+=1

	def reset(self, region=None, exemptions=None):
		'''
		Method: reset
		Description: Reset cells inside the provided region whose coordinates do not also fall within any of the provided exemption ranges.
		Parameters: region=None, exemptions=None
			region: Region - A region for maze reset to span
			exemptions: Regions - A collection of regions for maze reset to avoid
		Return: None
		'''

		# Ensure that valid boundaries are set.
		if region is None:
			region = Region((0, 0), (self.get_width(), self.get_height()))

		# Reset all cells that do not fall inside any of the provided exempt ranges.
		for row in self.m_cells:

			# If the current row is inside the reset boundary, check for cells to reset inside that row.
			for cell in row:
				exempt = False

				# If the current cell is outside the reset boundary, move on to the next cell.
				if not region.contains(cell.m_position):
					continue

				# Check for the inclusion of each cell in each provided exempt range.
				if exemptions is not None:
					for exemption in exemptions:

						# Reset the boundary walls of the provided exempt ranges.
						border_directions = exemption.on_border(cell.m_position)
						for border_direction in border_directions:
							self.set_wall(cell, border_direction, True)

						# If the cell falls inside any of the provided exempt ranges, do not reset it.
						if exemption.contains(cell.m_position):
							exempt = True
							break

					# Do not reset exempt cells.
					if exempt:
						continue

				# Completely reset non-exempt cells.
				self.unvisit(cell)
				for direction in list(Direction):
					self.set_wall(cell, direction, True)

    def __init__(self, element_type, event=None):
        assert element_type in ['photos', 'tweets']
        self._element_type = element_type
        if not event is None:
            if type(event) is types.DictType:
                self._event = event
            else:
                self._event = event.toDict()

            r = Region(self._event['region'])
            r._roundTo8Digits()
            self._event['region'] = r.toDict()

            self.setActualValue(self._getActualValueByCounting())
        else:
            self._event = {}
            self._event[self._element_type] = []

def testWithTweet():
    cnt = 0
    corpus_all = buildAllCorpus(element_type='tweets', debug=False)
    ei = EventInterface()
    ei.setDB('citybeat_experiment')
    ei.setCollection('twitter_candidate_events')
    cur = ei.getAllDocuments()
    print TwitterFeature.GenerateArffFileHeader()
    for event in cur:
        region = Region(event['region'])
        event = TwitterFeature(event, corpus=corpus_all[region.getKey()])
        if event.getActualValue() < 8:
            print '< 8'
            continue
        cnt += 1
        print event.extractFeatures()
    print  cnt, cur.count()