Searches
[Algorithms]

Collaboration diagram for Searches:

Algorithms for performing searches. More...

Searches

(OLForwardIterator *) + adjacentFindFrom:to:
 Find the first instance of adjacent elements.
(OLForwardIterator *) + adjacentFindFrom:to:predicate:
 Find the first instance of adjacent elements.
(BOOL) + binarySearchFrom:to:value:
 Perform a binary search.
(BOOL) + binarySearchFrom:to:value:predicate:
 Perform a binary search.
(unsigned) + countFrom:to:predicate:
 Count elements.
(unsigned) + countFrom:to:value:
 Count elements.
(OLPair *) + equalRangeFrom:to:value:
 Find the equal range of a given value.
(OLPair *) + equalRangeFrom:to:value:predicate:
 Find the equal range of a given value.
(OLForwardIterator *) + findEndFrom:to:subFrom:subTo:
 Find the last occurrence of a subsequence in a given range.
(OLForwardIterator *) + findEndFrom:to:subFrom:subTo:predicate:
 Find the last occurrence of a subsequence in a given range.
(OLForwardIterator *) + findFirstFrom:to:ofFrom:ofTo:
 Find any of a set of values.
(OLForwardIterator *) + findFirstFrom:to:ofFrom:ofTo:predicate:
 Find any of a set of values.
(OLForwardIterator *) + findFrom:to:if:
 Find an element.
(OLForwardIterator *) + findFrom:to:value:
 Find an element.
(BOOL) + includesFrom:to:subFrom:subTo:
 Determine whether one range exists in another range.
(BOOL) + includesFrom:to:subFrom:subTo:predicate:
 Determine whether one range exists in another range.
(OLForwardIterator *) + lowerBoundFrom:to:value:
 Find the first position at which a value may be inserted without disturbing the sorting order.
(OLForwardIterator *) + lowerBoundFrom:to:value:predicate:
 Find the first position at which a value may be inserted without disturbing the sorting order.
(OLForwardIterator *) + maxElementFrom:to:
 Find the element with the highest value.
(OLForwardIterator *) + maxElementFrom:to:predicate:
 Find the element with the highest value.
(OLForwardIterator *) + minElementFrom:to:
 Find the element with the lowest value.
(OLForwardIterator *) + minElementFrom:to:predicate:
 Find the element with the lowest value.
(OLPair *) + mismatchFrom:to:with:
 Find the first position where two ranges differ.
(OLPair *) + mismatchFrom:to:with:predicate:
 Find the first position where two ranges differ.
(OLForwardIterator *) + searchFrom:to:count:value:
 Search for a number of consecutive instances of an object.
(OLForwardIterator *) + searchFrom:to:count:value:predicate:
 Search for a number of consecutive instances of an object.
(OLForwardIterator *) + searchFrom:to:subFrom:subTo:
 Find a subsequence within a given range.
(OLForwardIterator *) + searchFrom:to:subFrom:subTo:predicate:
 Find a subsequence within a given range.
(OLForwardIterator *) + upperBoundFrom:to:value:
 Find the last position at which a value may be inserted without disturbing the sorting order.
(OLForwardIterator *) + upperBoundFrom:to:value:predicate:
 Find the last position at which a value may be inserted without disturbing the sorting order.

Detailed Description

Algorithms for performing searches.

Numerous types of searches are provided including linear searches, binary searches, subsequence searches, searches for mismatches and many others. All searches operate using forward iterators, thus they can be used with any type of container. However, bear in mind that some containers provide optimized versions of some algorithms, which should be preferred to the generic version when they exist. For example, associative containers, like OLMap, OLSet, and so forth, provide optimized versions of binary searches. Please use those when they are provided.

See also:
OLAlgorithm

Function Documentation

+ (OLForwardIterator*) adjacentFindFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Find the first instance of adjacent elements.

This message sends the message adjacentFindFrom:to:predicate: with OLEqualTo as the predicate.

Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search

+ (OLForwardIterator*) adjacentFindFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the first instance of adjacent elements.

Two elements, a and b, are considered adjacent if a and b are next to each other in the range [first, last) and the predicate object, pred, returns YES when a and b are passed as arguments. An iterator pointing to the first of the pair is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
pred the function object to use to compare elements
Returns:
an iterator pointing to the first in pair of adjacent elements, or an iterator equal to last if adjacent elements could not be found

+ (BOOL) binarySearchFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Perform a binary search.

This message sends the message binarySearchFrom:to:value:predicate: using a predicate of OLLess.

Precondition:
The elements in the range [first, last) must already be sorted using the predicate object OLLess.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the value for which to search
Returns:
YES if object was found, NO otherwise

+ (BOOL) binarySearchFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object
predicate: (id< OLBoolBinaryFunction >)  pred 

Perform a binary search.

A binary search is performed for the value object with the function object pred for comparing objects. Specifically, pred indicates what sorted order the elements in the range [first, last) are in.

Precondition:
The elements in the range [first, last) must already be sorted using the predicate object pred.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the value for which to search
pred the predicate object that indicates the sorting order of the range
Returns:
YES if object was found, NO otherwise

+ (unsigned) countFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (id< OLBoolUnaryFunction >)  pred 

Count elements.

The number of elements in the range [first, last) for which the predicate, pred, returns YES is returned.

Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
pred the function object used to test each element
Returns:
the number of elements for which pred returned YES

+ (unsigned) countFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Count elements.

The number of elements in the range [first, last) for which object returns YES to the message isEqual:.

Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object with which to compare each element
Returns:
the number of elements equal to object

+ (OLPair*) equalRangeFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Find the equal range of a given value.

This message sends the message equalRangeFrom:to:value:predicate: with OLLess as the predicate.

Precondition:
The range [first, last) must be sorted by OLLess.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object for which to search
Returns:
a pair of iterators representing the equal range

+ (OLPair*) equalRangeFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the equal range of a given value.

A pair of iterators is returned, one of which represents the first position where object can be inserted without disturbing the sorting order, and the other of which represents the last position where object can be inserted without disturbing the sorting order. A side effect of this operation is that it will return a range of elements that are all equal to object. Additionally, it is simply a combination of lowerBoundFrom:to:value:predicate: and upperBoundFrom:to:value:predicate: with the results of those two messages contained in the resulting pair.

The returned pair has an instance of OLForwardIterator representing the lower bound as its first value and another instance of OLForwardIterator representing the upper bound as its second value.

Precondition:
The range [first, last) must be sorted by pred.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object for which to search
pred the function object used as the sorting operation for the range [first, last)
Returns:
a pair of iterators representing the equal range

+ (OLForwardIterator*) findEndFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
subFrom: (OLForwardIterator *)  first2
subTo: (OLForwardIterator *)  last2 

Find the last occurrence of a subsequence in a given range.

This message sends the message findEndFrom:to:subFrom:subTo:predicate: using OLEqualTo as the predicate.

Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the subsequence for which to search
last2 one position beyond the last in the subsequence for which to search
Returns:
an iterator pointing to the last instance found of the subsequence, or an iterator equal to last1 if the subsequence cannot be found

+ (OLForwardIterator*) findEndFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
subFrom: (OLForwardIterator *)  first2
subTo: (OLForwardIterator *)  last2
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the last occurrence of a subsequence in a given range.

The last matching subsequence of values in [first2, last2) is found in the sequence [first1, last1) and an iterator pointing to the beginning of the subsequence is returned. Values are compared using the function object pred. If the subsequence cannot be found, then an iterator equal to last1 is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the subsequence for which to search
last2 one position beyond the last in the subsequence for which to search
pred the function object used to compare elements
Returns:
an iterator pointing to the last instance found of the subsequence, or an iterator equal to last1 if the subsequence cannot be found

+ (OLForwardIterator*) findFirstFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
ofFrom: (OLForwardIterator *)  first2
ofTo: (OLForwardIterator *)  last2 

Find any of a set of values.

This message sends the message findFirstFrom:to:ofFrom:ofTo:predicate: using OLEqualTo as the predicate.

Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the range of candidates
last2 one position beyond the last in the range of candidates
Returns:
an iterator pointing to the first match found, or an iterator equal to last1 if no match can be found

+ (OLForwardIterator*) findFirstFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
ofFrom: (OLForwardIterator *)  first2
ofTo: (OLForwardIterator *)  last2
predicate: (id< OLBoolBinaryFunction >)  pred 

Find any of a set of values.

The range [first1, last1) is searched for the first instance of any value from the range [first2, last2) using pred as the comparison function. An iterator pointing to the first match is returned, or an iterator equal to last1 is returned if no match is found.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the range of candidates
last2 one position beyond the last in the range of candidates
pred the function object used to compare elements
Returns:
an iterator pointing to the first match found, or an iterator equal to last1 if no match can be found

+ (OLForwardIterator*) findFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
if: (id< OLBoolUnaryFunction >)  pred 

Find an element.

An iterator pointing to the first element in the range [first, last) for which the function object pred returns YES is returned. If pred does not return YES for any elements, then an iterator equal to last is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
pred the function that tests elements
Returns:
an iterator pointing to the first element for which pred returns YES, or an iterator equal to last if no match is found

+ (OLForwardIterator*) findFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Find an element.

The range [first, last) is searched for an element equal to object. Equality is tested using the message isEqual:. An iterator pointing to the first equal element, or an iterator equal to last if no match is found, is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object for which to search
Returns:
an iterator pointing to the first element equal to object, or or an iterator equal to last if no match is found

+ (BOOL) includesFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
subFrom: (OLForwardIterator *)  first2
subTo: (OLForwardIterator *)  last2 

Determine whether one range exists in another range.

This message simply sends the message includesFrom:to:subFrom:subTo:predicate: using OLLess as the predicate.

Precondition:
Both [first1, last1) and [first2, last2) must be sorted using the predicate OLLess.
Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the range of elements for which to search
last2 one position beyond the last in the range of elements for which to search
Returns:
YES if the sub-range is found, NO otherwise

+ (BOOL) includesFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
subFrom: (OLForwardIterator *)  first2
subTo: (OLForwardIterator *)  last2
predicate: (id< OLBoolBinaryFunction >)  pred 

Determine whether one range exists in another range.

This message differs from findFirstFrom:to:ofFrom:ofTo:predicate: in that it simply determines whether all of the elements in the range [first2, last2) exist in the range [first1, last1) in the same order, although the elements do not need to be contiguous in [first1, last1). The function object pred indicates the sorting order of both [first1, last1) and [first2, last2).

Precondition:
Both [first1, last1) and [first2, last2) must be sorted using the predicate pred.
Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the range of elements for which to search
last2 one position beyond the last in the range of elements for which to search
pred the function object by which both ranges are sorted
Returns:
YES if the sub-range is found, NO otherwise

+ (OLForwardIterator*) lowerBoundFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Find the first position at which a value may be inserted without disturbing the sorting order.

This message simply sends the message lowerBoundFrom:to:value:predicate: using OLLess as the predicate.

Precondition:
The range [first, last) must be sorted using the predicate OLLess.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object with which to compare objects in the range
Returns:
an iterator indicating the first position at which object may be inserted without disturbing the sorting order

+ (OLForwardIterator*) lowerBoundFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the first position at which a value may be inserted without disturbing the sorting order.

Using a binary search, the message locates the first position at which object may be inserted without disturbing the order defined by pred. A side effect of this message is that the iterator returned will be the first position of an object equal to object, if such an object exists in the range.

Precondition:
The range [first, last) must be sorted using the predicate pred.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object with which to compare objects in the range
pred the function object with which the range is sorted
Returns:
an iterator indicating the first position at which object may be inserted without disturbing the sorting order

+ (OLForwardIterator*) maxElementFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Find the element with the highest value.

This message simply sends the message maxElementFrom:to:predicate: using OLLess as the predicate.

Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
Returns:
an iterator pointing to the highest element

+ (OLForwardIterator*) maxElementFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the element with the highest value.

Specifically, the message finds the first element i in the range [first, last) for which every other element j the predicate pred message performBinaryFunctionWithArg: i andArg: j returns NO. An iterator pointing to the highest value is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
pred the function object used for comparison
Returns:
an iterator pointing to the highest element

+ (OLForwardIterator*) minElementFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Find the element with the lowest value.

This message simply sends the message minElementFrom:to:predicate: using OLLess as the predicate.

Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
Returns:
an iterator pointing to the lowest element

+ (OLForwardIterator*) minElementFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the element with the lowest value.

Specifically, the message finds the first element i in the range [first, last) for which every other element j the predicate pred message performBinaryFunctionWithArg: j andArg: i returns NO. An iterator pointing to the highest value is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
pred the function object used for comparison
Returns:
an iterator pointing to the lowest element

+ (OLPair*) mismatchFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
with: (OLForwardIterator *)  first2 

Find the first position where two ranges differ.

This message simply sends the message mismatchFrom:to:with:predicate: using OLEqualTo as the predicate.

Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the second range of elements to search
Returns:
a pair of instances of OLForwardIterator pointing to the mismatch in both ranges

+ (OLPair*) mismatchFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
with: (OLForwardIterator *)  first2
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the first position where two ranges differ.

The range [first1, last) is compared with the range that begins at first2, and the first position where the two differ is returned. The predicate pred is used to determine equality. A pair of instances of OLForwardIterator is returned: the first element of the pair points to the mismatch in the range [first1, last), and the second element of the pair points to the mismatch in the range starting from first2. If no mismatch is found then the pair contains iterators equal to last1 and last2.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the second range of elements to search
pred the function object used to test objects for equality
Returns:
a pair of instances of OLForwardIterator pointing to the mismatch in both ranges

+ (OLForwardIterator*) searchFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
count: (unsigned)  num
value: (id)  object 

Search for a number of consecutive instances of an object.

This message simply sends the message searchFrom:to:count:value:predicate: using OLEqualTo as the predicate.

Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
num the number of instances of object for which to search
object the object for which to search
Returns:
an iterator pointing to the beginning of the range of num instances of object

+ (OLForwardIterator*) searchFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
count: (unsigned)  num
value: (id)  object
predicate: (id< OLBoolBinaryFunction >)  pred 

Search for a number of consecutive instances of an object.

The message searches the range [first, last) for num consecutive instances of object using pred to test objects for equality. An iterator pointing to the beginning of the range of consecutive objects is returned, or if no match is found an iterator equal to last is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
num the number of instances of object for which to search
object the object for which to search
pred the function object used to test for equality
Returns:
an iterator pointing to the beginning of the range of num instances of object

+ (OLForwardIterator*) searchFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
subFrom: (OLForwardIterator *)  first2
subTo: (OLForwardIterator *)  last2 

Find a subsequence within a given range.

This message simply sends the message searchFrom:to:subFrom:subTo:predicate: using OLEqualTo as the predicate.

Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the subsequence for which to search
last2 one position beyond the last in the subsequence for which to search
Returns:
an iterator pointing to the first instance of the subsequence

+ (OLForwardIterator*) searchFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
subFrom: (OLForwardIterator *)  first2
subTo: (OLForwardIterator *)  last2
predicate: (id< OLBoolBinaryFunction >)  pred 

Find a subsequence within a given range.

The first instance of the subsequence described by the range [first2, last2) is searched for in the range [first1, last1) and an iterator to its position is returned. The predicate pred is used to test objects for equality. If no match is found, then an iterator equal to last1 is returned.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first1 the first in the range of elements to search
last1 one position beyond the last in the range of elements to search
first2 the first in the subsequence for which to search
last2 one position beyond the last in the subsequence for which to search
pred the function object used to test objects for equality
Returns:
an iterator pointing to the first instance of the subsequence

+ (OLForwardIterator*) upperBoundFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Find the last position at which a value may be inserted without disturbing the sorting order.

This message simply sends the message upperBoundFrom:to:value:predicate: using OLLess as the predicate.

Precondition:
The range [first, last) must be sorted using the predicate OLLess.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object with which to compare objects in the range
Returns:
an iterator indicating the last position at which object may be inserted without disturbing the sorting order

+ (OLForwardIterator*) upperBoundFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object
predicate: (id< OLBoolBinaryFunction >)  pred 

Find the last position at which a value may be inserted without disturbing the sorting order.

Using a binary search, the message locates the last position at which object may be inserted without disturbing the order defined by pred. A side effect of this message is that the iterator returned will be one beyond the last position of an object equal to object, if such an object exists in the range.

Precondition:
The range [first, last) must be sorted using the predicate pred.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to search
last one position beyond the last in the range of elements to search
object the object with which to compare objects in the range
pred the function object with which the range is sorted
Returns:
an iterator indicating the last position at which object may be inserted without disturbing the sorting order

ObjectiveLibGenerated Sun Apr 22 15:18:02 2007, © 2004-2007 Will Mason
 SourceForge.net Logo