// FindMatching returns the closest Value/Pointer in the quadtree for which
// the given filter function returns true. This function is thread safe.
// Multiple goroutines can read from a pre-created tree.
176709
func (q *Quadtree) FindMatching(p *geo.Point, f Filter) geo.Pointer {
	if q.root == nil {
		return nil
	}

	v := &findVisitor{
		point:          p,
		filter:         f,
		closestBound:   q.bound.Clone(),
		maxDistSquared: math.MaxFloat64,
	}

	newVisit(v).Visit(q.root,
		q.bound.Left(), q.bound.Right(),
		q.bound.Bottom(), q.bound.Top(),
	)

	return v.closest
}
126693
func (s *Selection) PrevMatcherUntilNodes(filter Matcher, nodes ...*html.Node) *Selection {
	return filterAndPush(s, getSiblingNodes(s.Nodes, siblingPrevUntil,
		nil, nodes), filter)
}
1141025
func removeMatching(name string, start, end byte) string {
	s := string(start) + string(end)
	var nesting, first, current int
	for index := strings.IndexAny(name[current:], s); index != -1; index = strings.IndexAny(name[current:], s) {
		switch current += index; name[current] {
		case start:
			nesting++
			if nesting == 1 {
				first = current
			}
		case end:
			nesting--
			switch {
			case nesting < 0:
				return name // Mismatch, abort
			case nesting == 0:
				name = name[:first] + name[current+1:]
				current = first - 1
			}
		}
		current++
	}
	return name
}
33430
func (mr *MatchRules) RuleMatching(r *Rule) (abort bool, err error) {
	metas := r.Metas()
	// convert int to int32 for code that relies on previous behavior
	for s := range metas {
		if i, ok := metas[s].(int); ok {
			metas[s] = int32(i)
		}
	}
	*mr = append(*mr, MatchRule{
		Rule:      r.Identifier(),
		Namespace: r.Namespace(),
		Tags:      r.Tags(),
		Meta:      metas,
		Strings:   r.getMatchStrings(),
	})
	return
}
889404
func (n *node) findAll(f func(fn *node) (bool, error)) ([]*node, error) {
	var allFound []*node
	hasFound, err := f(n)
	if err != nil {
		return nil, errors.Annotate(err, ErrNodeFindAll, errorMessages)
	}
	if hasFound {
		allFound = append(allFound, n)
	}
	for _, child := range n.children {
		found, err := child.findAll(f)
		if err != nil {
			return nil, errors.Annotate(err, ErrNodeFindAll, errorMessages)
		}
		if found != nil {
			allFound = append(allFound, found...)
		}
	}
	return allFound, nil
}
1137875
func GetMatch(c C) Match {
	if c.Env == nil {
		return Match{}
	}
	mi, ok := c.Env[MatchKey]
	if !ok {
		return Match{}
	}
	if m, ok := mi.(Match); ok {
		return m
	}
	return Match{}
}
884872
func Find(root string, pattern *regexp.Regexp) (paths []string) {
	if Exists(root) {
		filepath.Walk(root, func(path string, info os.FileInfo, e error) error {
			if pattern.MatchString(path) {
				paths = append(paths, info.Name())
			}
			return e
		})
	}
	return
}
1246999
func findValue(v reflect.Value) (reflect.Value, bool) {
	for ; v.Kind() == reflect.Ptr || v.Kind() == reflect.Interface; v = v.Elem() {
		if v.IsNil() {
			return v, true
		}
		if v.Kind() == reflect.Interface && v.NumMethod() > 0 {
			break
		}
	}
	return v, false
}
453595
func (t *PairTree) Find(key string) *Pair {
	v := t.ObjectTree.Find(Pair{key, nil})
	if v != nil {
		x := v.(Pair)
		return &x
	}
	return nil
}
143978
func findMatchInFile(file *object.File, treeName string, opts *GrepOptions) ([]GrepResult, error) {
	var grepResults []GrepResult

	content, err := file.Contents()
	if err != nil {
		return grepResults, err
	}

	// Split the file content and parse line-by-line.
	contentByLine := strings.Split(content, "\n")
	for lineNum, cnt := range contentByLine {
		addToResult := false

		// Match the patterns and content. Break out of the loop once a
		// match is found.
		for _, pattern := range opts.Patterns {
			if pattern != nil && pattern.MatchString(cnt) {
				// Add to result only if invert match is not enabled.
				if !opts.InvertMatch {
					addToResult = true
					break
				}
			} else if opts.InvertMatch {
				// If matching fails, and invert match is enabled, add to
				// results.
				addToResult = true
				break
			}
		}

		if addToResult {
			grepResults = append(grepResults, GrepResult{
				FileName:   file.Name,
				LineNumber: lineNum + 1,
				Content:    cnt,
				TreeName:   treeName,
			})
		}
	}

	return grepResults, nil
}
534257
func NewWhileMatchFilter(matchingFilter Filter) *WhileMatchFilter {
	f, err := matchingFilter.ConstructPBFilter()
	if err != nil {
		panic(err)
	}
	return &WhileMatchFilter{
		Filter: f,
	}
}
1276535
func findFirst(vs []string, predicate func(string) bool) int {
	l, h := -1, len(vs)
	// Invariant: vs[l] does not match, vs[h] does.
	// -1 and len(vs) are sentinal values, never tested but assumed to mismatch and match, respectively.
	for l+1 < h {
		m := (l + h) / 2 // Must now be a valid value
		// //debugf("%d %d %d", l, m, h)
		if predicate(vs[m]) {
			h = m
		} else {
			l = m
		}
	}
	//debugf("==> %d", h)
	return h
}
198015
func (t *Tree) Find(key interface{}) interface{} {
	if key != nil && t.root != nil {
		d := &findData{key, t.compare}
		node := d.finder(t.root)
		if node != nil {
			return node.value
		}
	}

	return nil
}
63606
func find(tree *Tree, pattern string) ([]*Node, error) {
	var nodes []string
	if strings.Index(pattern, ";") == -1 {
		nodes = strings.Split(pattern, ".")
	} else {
		nodes = strings.SplitN(pattern, ";", 2)
		tags := nodes[1]
		nodes = strings.Split(nodes[0], ".")
		nodes[len(nodes)-1] += ";" + tags
	}

	// pos is the index of the first node with special chars, or one past the last node if exact
	// for a query like foo.bar.baz, pos is 3
	// for a query like foo.bar.* or foo.bar, pos is 2
	// for a query like foo.b*.baz, pos is 1
	pos := len(nodes)
	for i := 0; i < len(nodes); i++ {
		if strings.ContainsAny(nodes[i], "*{}[]?") {
			log.Debugf("memory-idx: found first pattern sequence at node %s pos %d", nodes[i], i)
			pos = i
			break
		}
	}
	var branch string
	if pos != 0 {
		branch = strings.Join(nodes[:pos], ".")
	}
	log.Debugf("memory-idx: starting search at node %q", branch)
	startNode, ok := tree.Items[branch]

	if !ok {
		log.Debugf("memory-idx: branch %q does not exist in the index", branch)
		return nil, nil
	}

	if startNode == nil {
		corruptIndex.Inc()
		log.Errorf("memory-idx: startNode is nil. patt=%q,pos=%d,branch=%q", pattern, pos, branch)
		return nil, errors.NewInternal("hit an empty path in the index")
	}

	children := []*Node{startNode}
	for i := pos; i < len(nodes); i++ {
		p := nodes[i]

		matcher, err := getMatcher(p)

		if err != nil {
			return nil, err
		}

		var grandChildren []*Node
		for _, c := range children {
			if !c.HasChildren() {
				log.Debugf("memory-idx: end of branch reached at %s with no match found for %s", c.Path, pattern)
				// expecting a branch
				continue
			}
			log.Debugf("memory-idx: searching %d children of %s that match %s", len(c.Children), c.Path, nodes[i])
			matches := matcher(c.Children)
			for _, m := range matches {
				newBranch := c.Path + "." + m
				if c.Path == "" {
					newBranch = m
				}
				grandChild := tree.Items[newBranch]
				if grandChild == nil {
					corruptIndex.Inc()
					log.Errorf("memory-idx: grandChild is nil. patt=%q,i=%d,pos=%d,p=%q,path=%q", pattern, i, pos, p, newBranch)
					return nil, errors.NewInternal("hit an empty path in the index")
				}

				grandChildren = append(grandChildren, grandChild)
			}
		}
		children = grandChildren
		if len(children) == 0 {
			log.Debug("memory-idx: pattern does not match any series.")
			break
		}
	}

	log.Debugf("memory-idx: reached pattern length. %d nodes matched", len(children))
	return children, nil
}
1229816
func (s *Store) UpdateMatching(dataType interface{}, query *Query, update func(record interface{}) error) error {
	return s.Bolt().Update(func(tx *bolt.Tx) error {
		return s.TxUpdateMatching(tx, dataType, query, update)
	})
}
1043374
func (q *Quadtree) FindKNearest(p *geo.Point, k int, maxDistance ...float64) []geo.Pointer {
	return q.FindKNearestMatching(p, k, nil, maxDistance...)
}
672309
func (s strings) Find(in []string, what string) int {
	for i, entry := range in {
		if entry == what {
			return i
		}
	}

	return -1
}