ObjectiveLib  1.0.0
Transformations
Algorithms

Algorithms for transforming ranges. More...

Collaboration diagram for Transformations:

Transformations

(void) + fillFrom:count:value:
 Assign a given value to a number of elements.
(void) + fillFrom:to:value:
 Assign a value to a range of elements.
(void) + forEachFrom:to:function:
 Perform an operation on each element in a given range.
(BOOL) + nextPermutationFrom:to:
 Turn a range into its next permutation.
(BOOL) + nextPermutationFrom:to:predicate:
 Turn a range into its next permutation.
(BOOL) + prevPermutationFrom:to:
 Turn a range into its previous permutation.
(BOOL) + prevPermutationFrom:to:predicate:
 Turn a range into its previous permutation.
(void) + randomShuffleFrom:to:
 Reorder a sequence of elements randomly.
(void) + randomShuffleFrom:to:randGen:
 Reorder a sequence of elements randomly.
(OLForwardIterator *) + removeCopyFrom:to:destination:if:
 Copy a range while selectively removing elements.
(OLForwardIterator *) + removeCopyFrom:to:destination:value:
 Copy a range while selectively removing elements.
(OLForwardIterator *) + removeFrom:to:if:
 Remove elements from a range.
(OLForwardIterator *) + removeFrom:to:value:
 Remove elements from a range.
(OLForwardIterator *) + replaceCopyFrom:to:destination:if:newValue:
 Copy a range while selectively replacing elements.
(OLForwardIterator *) + replaceCopyFrom:to:destination:oldValue:newValue:
 Copy a range while selectively replacing elements.
(void) + replaceFrom:to:if:newValue:
 Replace values in a range.
(void) + replaceFrom:to:oldValue:newValue:
 Replace values in a range.
(OLForwardIterator *) + reverseCopyFrom:to:destination:
 Copy a range in reverse order.
(void) + reverseFrom:to:
 Reverse the order of a range of elements.
(OLForwardIterator *) + rotateCopyFrom:middle:to:destination:
 Copy a range and rotate it in one step.
(OLForwardIterator *) + rotateFrom:middle:to:
 Rotate a given range.
(OLForwardIterator *) + transformFrom:to:destination:function:
 Transform a range.
(OLForwardIterator *) + transformFrom:to:withArgsFrom:destination:function:
 Transform a range.
(OLForwardIterator *) + uniqueCopyFrom:to:destination:
 Copy a range while eliminating duplicates.
(OLForwardIterator *) + uniqueCopyFrom:to:destination:predicate:
 Copy a range while eliminating duplicates.
(OLForwardIterator *) + uniqueFrom:to:
 Remove consecutive elements from a range.
(OLForwardIterator *) + uniqueFrom:to:predicate:
 Remove consecutive elements from a range.

Swapping

(OLForwardIterator *) + swapRangesFrom:to:with:
 Swap elements in two ranges.

Detailed Description

Algorithms for transforming ranges.

Ranges can be transformed in a wide variety of ways including selectively removing and replacing, permuting, reversing, and many others.

See also:
OLAlgorithm

Function Documentation

+ (void) fillFrom: (OLForwardIterator *)  first
count: (unsigned)  num
value: (id)  object 

Assign a given value to a number of elements.

The operation assigns object to num elements starting at first.

Parameters:
firstthe first element from which to begin assignment
numthe number of times to assign object
objectthe value to assign
+ (void) fillFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Assign a value to a range of elements.

The value object is assigned to every iterator in the range [first, last).

Parameters:
firstthe first in the range of elements to assign
lastone position beyond the last in the range of elements to assign
objectthe value to assign
+ (void) forEachFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
function: (id< OLUnaryFunction >)  func 

Perform an operation on each element in a given range.

Each element in the range [first, last) is passed as an argument to the function object func.

Parameters:
firstthe first in the range of elements
lastone position beyond the last in the range of elements
functhe function object operating on the elements
+ (BOOL) nextPermutationFrom: (OLBidirectionalIterator *)  first
to: (OLBidirectionalIterator *)  last 

Turn a range into its next permutation.

This message simple sends the message nextPermutationFrom:to:predicate: using OLLess as the predicate.

Parameters:
firstthe first in the range of elements
lastone beyond the last in the range of elements
Returns:
YES if a next permutation was found, NO otherwise
+ (BOOL) nextPermutationFrom: (OLBidirectionalIterator *)  first
to: (OLBidirectionalIterator *)  last
predicate: (id< OLBoolBinaryFunction >)  pred 

Turn a range into its next permutation.

Each range of elements has a finite number of permutations. Where n is the distance from the first in the range to the last, each range will have n! permutations. The next permutation is computed lexicographically, so if the range is ordered using lexicographicalCompareFrom:to:andFrom:andTo:predicate:, then the result of finding the next permutation will be unambiguous. If there is no next permutation in the order defined by pred, then NO is returned and the sequence is placed in the order of its first permutation in the order defined by pred. If a next permutation is found, then the message returns YES and the sequence is placed in the order of the next permutation as defined by pred.

See also:
+ prevPermutationFrom:to:predicate:
Parameters:
firstthe first in the range of elements
lastone beyond the last in the range of elements
predthe predicate used to define the lexicographical order of permutations
Returns:
YES if a next permutation was found, NO otherwise
+ (BOOL) prevPermutationFrom: (OLBidirectionalIterator *)  first
to: (OLBidirectionalIterator *)  last 

Turn a range into its previous permutation.

This message simple sends the message prevPermutationFrom:to:predicate: using OLLess as the predicate.

Parameters:
firstthe first in the range of elements
lastone beyond the last in the range of elements
Returns:
YES if a next permutation was found, NO otherwise
+ (BOOL) prevPermutationFrom: (OLBidirectionalIterator *)  first
to: (OLBidirectionalIterator *)  last
predicate: (id< OLBoolBinaryFunction >)  pred 

Turn a range into its previous permutation.

Each range of elements has a finite number of permutations. Where n is the distance from the first in the range to the last, each range will have n! permutations. The previous permutation is computed lexicographically, so if the range is ordered using lexicographicalCompareFrom:to:andFrom:andTo:predicate:, then the result of finding the previous permutation will be unambiguous. If there is no previous permutation in the order defined by pred, then NO is returned and the sequence is placed in the order of its last permutation in the order defined by pred. If a previous permutation is found, then the message returns YES and the sequence is placed in the order of the previous permutation as defined by pred.

See also:
+ nextPermutationFrom:to:predicate:
Parameters:
firstthe first in the range of elements
lastone beyond the last in the range of elements
predthe predicate used to define the lexicographical order of permutations
Returns:
YES if a next permutation was found, NO otherwise
+ (void) randomShuffleFrom: (OLRandomAccessIterator *)  first
to: (OLRandomAccessIterator *)  last 

Reorder a sequence of elements randomly.

The elements in the range [first, last) are placed in a random order. The message uses one of the following functions to generate random numbers:

  • random()
  • lrand48()
  • rand_s()
  • rand()

You must properly seed the random number generator prior to using this algorithm, and you can find out which random number generator is in use by checking for a defined macro from the following list:

  • OL_HAVE_RANDOM
  • OL_HAVE_LRAND48
  • OL_HAVE_RAND_S
  • OL_HAVE_RAND

Only one of those will be defined in the file ObjectiveLib/Config.h.

Precondition:
The random number generator must have been seeded.
Parameters:
firstthe first in the range to shuffle
lastone beyond the last in the range to shuffle
+ (void) randomShuffleFrom: (OLRandomAccessIterator *)  first
to: (OLRandomAccessIterator *)  last
randGen: (id< OLUnaryFunction >)  gen 

Reorder a sequence of elements randomly.

The elements in the range [first, last) are placed in a random order. The random number generator gen is a special kind of function object. The argument to the unary function must respond to the message unsignedIntValue, which will return an integer greater than or equal to zero. The result of the unary function must also respond to the message unsignedIntValue, which will return an integer greater than or equal to zero and less than the value of the unsignedIntValue which is the argument to the unary function.

Precondition:
gen must take an argument that responds to the message unsignedIntValue, and must return a result that responds to the message unsignedIntValue.
Parameters:
firstthe first in the range to shuffle
lastone beyond the last in the range to shuffle
genthe random number generator to use
+ (OLForwardIterator*) removeCopyFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest
if: (id< OLBoolUnaryFunction >)  pred 

Copy a range while selectively removing elements.

All elements in the range [first, last) for which the predicate pred does not return YES when passed each element as an argument are copied to the range that begins from dest. An iterator that points to one position beyond the last element copied is returned.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range to copy
lastone beyond the last in the range to copy
destthe first in the range to which to copy elements
predthe predicate that, when passed each element in the range [first, last) as an argument, returns YES for those that should not be copied to dest
Returns:
an iterator pointing to one position beyond the last element copied to dest
+ (OLForwardIterator*) removeCopyFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest
value: (id)  object 

Copy a range while selectively removing elements.

All elements in the range [first, last) for which the message isEqual:, when passed object as an argument, returns NO are copied to the range that begins from dest. An iterator that points to one position beyond the last element copied is returned.

Precondition:
  • All elements in the range [first, last) must respond to the message isEqual:.
  • The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range to copy
lastone beyond the last in the range to copy
destthe first in the range to which to copy elements
objectthe object against which to test each of the elements in the range for equality
Returns:
an iterator pointing to one position beyond the last element copied to dest
+ (OLForwardIterator*) removeFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
if: (id< OLBoolUnaryFunction >)  pred 

Remove elements from a range.

Naturally, a generic algorithm cannot erase elements from a range. What the message does instead is to organize the range such that for no element in the new range [first, middle) the predicate pred will return YES. The iterator middle is returned by the message after reorganizing the range [first, last). The range from [middle, last) will still contain valid elements, but the exact contents are undefined.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range from which to remove elements
lastone beyond the last in the range from which to remove elements
predthe function object that returns YES for each element that should be removed
Returns:
an iterator indicating one position beyond the new last element in the range after removing all elements identified by the predicate pred
+ (OLForwardIterator*) removeFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
value: (id)  object 

Remove elements from a range.

This message is similar to removeFrom:to:if: except that rather than using a function object the message isEqual: is sent to each element in the range [first, last) with object as the argument. If the message returns YES, then the element will not appear in the resulting range [first, middle) where middle points to one position beyond the last element not equal to object. The elements in the range [middle, last) are still valid, but the contents are undefined. The iterator middle is returned.

Precondition:
All elements in the range [first, last) must respond to the message isEqual:.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range from which to remove elements
lastone beyond the last in the range from which to remove elements
objectthe object that should be removed from the range [first, last)
Returns:
an iterator indicating one position beyond the new last element in the range after removing all elements identified comparing elements to object
+ (OLForwardIterator*) replaceCopyFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest
if: (id< OLBoolUnaryFunction >)  pred
newValue: (id)  newv 

Copy a range while selectively replacing elements.

All elements from the range [first, last) are copied to the range that begins at dest, but those elements for which the predicate pred returns YES are replaced in the destination range with the value newv. An iterator that points to one position beyond the last element copied is returned.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range from which to copy elements
lastone beyond the last in the range from which to copy elements
destthe first in the range to which to copy elements
predthe predicate that, when passed each element in the range [first, last) as an argument, returns YES for those that should be replaced by newv
newvthe value used to replace values in the destination range
Returns:
an iterator that points to one position beyond the last element copied to the destination
+ (OLForwardIterator*) replaceCopyFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest
oldValue: (id)  oldv
newValue: (id)  newv 

Copy a range while selectively replacing elements.

All elements from the range [first, last) are copied to the range that begins at dest, but those elements for which the message isEqual: returns YES when passed oldv as an argument are replaced with the value newv. An iterator that points to one position beyond the last element copied is returned.

Precondition:
  • All elements in the range [first, last) must respond to the message isEqual:.
  • The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range from which to copy elements
lastone beyond the last in the range from which to copy elements
destthe first in the range to which to copy elements
oldvthe value that should be replaced with newv in the destination range
newvthe value used to replace values in the destination range
Returns:
an iterator that points to one position beyond the last element copied to the destination
+ (void) replaceFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
if: (id< OLBoolUnaryFunction >)  pred
newValue: (id)  newv 

Replace values in a range.

Each element in the range [first, last) is tested using the predicate pred, and for each case where YES is returned that value is replaced with the value newv.

Parameters:
firstthe first in the range to check for replacements
lastone beyond the last in the range to check for replacements
predthe function object used to test each element in the range
newvthe value with which to replace the candidate values
+ (void) replaceFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
oldValue: (id)  oldv
newValue: (id)  newv 

Replace values in a range.

Each element in the range [first, last) is sent the message isEqual: using oldv as an argument. For each case where isEqual: returns YES the value is replaced with the value of newv.

Precondition:
Each element in the range [first, last) must respond to the message isEqual:.
Parameters:
firstthe first in the range to check for replacements
lastone beyond the last in the range to check for replacements
oldvthe value with which to compare the values in the range
newvthe value with which to replace the candidate values
+ (OLForwardIterator*) reverseCopyFrom: (OLBidirectionalIterator *)  first
to: (OLBidirectionalIterator *)  last
destination: (OLForwardIterator *)  dest 

Copy a range in reverse order.

The elements in the range [first, last) are copied to the range starting at dest in reverse order. An iterator pointing to one position beyond the last element copied in the destination range is returned.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range from which to copy elements
lastone beyond the last in the range from which to copy elements
destthe first element in the range to which to copy elements
Returns:
an iterator that points to one position beyond the last element copied to the destination range
+ (void) reverseFrom: (OLBidirectionalIterator *)  first
to: (OLBidirectionalIterator *)  last 

Reverse the order of a range of elements.

The range [first, last) is placed in reverse order.

Parameters:
firstthe first in the range to reverse
lastone beyond the last in the range to reverse
+ (OLForwardIterator*) rotateCopyFrom: (OLForwardIterator *)  first
middle: (OLForwardIterator *)  mid
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest 

Copy a range and rotate it in one step.

Rotation in this context is roughly equivilent to the idea of "left shifting". As it is copied the range is shifted to the left by the distance between first and mid. The value of mid is copied to the position of first, mid plus one is copied to first plus one, and so on. The existing values at first and the values that follow it are copied to mid, and so on. Another way of thinking of it is that the two ranges [first, mid) and [mid, last) are swapped. An iterator pointing to one position beyond the last element copied to the destination range is returned.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first element in the range from which to copy
midthe position at which to perform the pivot of rotation in the range from which to copy
lastone beyond the last element in the range from which to copy
destthe first in the destination range to which to copy
Returns:
an iterator pointing to one position beyond the last element copied to the destination range
+ (OLForwardIterator*) rotateFrom: (OLForwardIterator *)  first
middle: (OLForwardIterator *)  mid
to: (OLForwardIterator *)  last 

Rotate a given range.

Rotation in this context is roughly equivilent to the idea of "left shifting". The range is shifted to the left by the distance between first and mid. The value of mid is copied to the position of first, mid plus one is copied to first plus one, and so on. The existing values at first and the values that follow it are copied to mid, and so on. Another way of thinking of it is that the two ranges [first, mid) and [mid, last) are swapped. An iterator pointing to the new position of the element originally pointed to by mid is returned. In other words the returned iterator is equal to the position of first plus the distance between mid and last.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first element in the range from which to copy
midthe position at which to perform the pivot of rotation in the range from which to copy
lastone beyond the last element in the range from which to copy
Returns:
an iterator pointing to the new position of the element originally pointed to by mid
+ (OLForwardIterator*) swapRangesFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last1
with: (OLForwardIterator *)  first2 

Swap elements in two ranges.

All elements in the range [first1, last1) are assigned to the corresponding element in the range starting at first2 and vice versa. An iterator is returned pointing to one position beyond the last element swapped in the range starting from first2.

Precondition:
The range starting at first2 must have at least as many valid elements as the range [first1, last1).
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first1the first in the first range to swap
last1one beyond the last in the first range to swap
first2the first in the second range to swap
Returns:
an iterator pointing to one beyond the last element swapped in the range starting from first2
+ (OLForwardIterator*) transformFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest
function: (id< OLUnaryFunction >)  func 

Transform a range.

The message performs the unary function func on each element in the range [first, last) and copies the result to the range that begins from dest. Each element is passed as the argument to the unary function's performUnaryFunctionWithArg: message, which presumably will do something to the argument and return another object as the result. An iterator is returned that points to one position beyond the last element copied to the destination range.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first element in the range to transform
lastone beyond the last element in the range to transform
destthe first element in the range to which to copy the results of the transformation
functhe function object used to transform the range
Returns:
an iterator pointing to one position beyond the last element copied to the destination range
+ (OLForwardIterator*) transformFrom: (OLForwardIterator *)  first1
to: (OLForwardIterator *)  last
withArgsFrom: (OLForwardIterator *)  first2
destination: (OLForwardIterator *)  dest
function: (id< OLBinaryFunction >)  func 

Transform a range.

This message is very similar to transformFrom:to:destination:function: except that another argument to the function object, which is now a binary function, is plucked from the range starting from first2 and passed as the second argument to func. As with transformFrom:to:destination:function:, each element in the range [first1, last) is passed to func as the first argument to the performBinaryFunctionWithArg:andArg: message. An iterator is returned that points to one position beyond the last element copied to the destination range.

Precondition:
  • The range starting from first2 must have at least as many valid elements as the range starting from first1.
  • The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first1the first element in the range to transform
lastone beyond the last element in the range to transform
first2the first in the range of elements to use as second arguments to func
destthe first element in the range to which to copy the results of the transformation
functhe function object used to transform the range
Returns:
an iterator pointing to one position beyond the last element copied to the destination range
+ (OLForwardIterator*) uniqueCopyFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest 

Copy a range while eliminating duplicates.

This message simple sends the message uniqueCopyFrom:to:destination:predicate: using OLEqualTo as the predicate.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Parameters:
firstthe first in the range to copy
lastone beyond the last in the range to copy
destthe first in the range to which to copy
+ (OLForwardIterator*) uniqueCopyFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
destination: (OLForwardIterator *)  dest
predicate: (id< OLBoolBinaryFunction >)  pred 

Copy a range while eliminating duplicates.

Elements from the range [first, last) are copied to the range starting at dest, except that where there is a series of consecutive elements for which the predicate pred returns YES, only the first is copied. An iterator is returned that points to one position beyond the last element copied to the destination range.

Precondition:
The range starting from dest must either have enough valid elements to hold the result, or dest be a type of insert iterator.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range to copy
lastone beyond the last in the range to copy
destthe first in the range to which to copy
predthe function object used to test for consecutive elements
+ (OLForwardIterator*) uniqueFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Remove consecutive elements from a range.

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

Parameters:
firstthe first in the range to transform
lastone beyond the last in the range to transform
Returns:
an iterator pointing to one beyond the last in the range of unique elements
+ (OLForwardIterator*) uniqueFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
predicate: (id< OLBoolBinaryFunction >)  pred 

Remove consecutive elements from a range.

The message returns an iterator end that is in the range [first, last), and all elements in the range [first, end) will be unique. Uniqueness is tested using the predicate pred, and for any two consecutive elements which for which the predicate returns YES, only the first will appear in the resulting range [first, end). The elements that remain in the range [end, last) will be valid, but the contents are undefined.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range to transform
lastone beyond the last in the range to transform
predthe function object used to test elements for equality
Returns:
an iterator pointing to one beyond the last in the range of unique elements

ObjectiveLibGenerated Sat Feb 15 2014 07:45:33, © 2004-2007 Will Mason