 | Generated Sun Apr 22 15:17:58 2007, © 2004-2007 Will Mason |
00001 // 00002 // $Id: Algorithm.h,v 1.30 2007/04/22 17:47:25 will_mason Exp $ 00003 // 00004 // vi: set ft=objc: 00005 00006 /* 00007 * ObjectiveLib - a library of containers and algorithms for Objective-C 00008 * 00009 * Copyright (c) 2004-2007 00010 * Will Mason 00011 * 00012 * Portions: 00013 * 00014 * Copyright (c) 1994 00015 * Hewlett-Packard Company 00016 * 00017 * Copyright (c) 1996,1997 00018 * Silicon Graphics Computer Systems, Inc. 00019 * 00020 * Copyright (c) 1997 00021 * Moscow Center for SPARC Technology 00022 * 00023 * Copyright (c) 1999 00024 * Boris Fomitchev 00025 * 00026 * This library is free software; you can redistribute it and/or 00027 * modify it under the terms of the GNU Lesser General Public 00028 * License as published by the Free Software Foundation; either 00029 * version 2.1 of the License, or (at your option) any later version. 00030 * 00031 * This library is distributed in the hope that it will be useful, 00032 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00033 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00034 * Lesser General Public License for more details. 00035 * 00036 * You should have received a copy of the GNU Lesser General Public 00037 * License along with this library; if not, write to the Free Software 00038 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00039 * 00040 * You may contact the author at will_mason@users.sourceforge.net. 00041 */ 00042 00043 #if !defined(ALGORITHM_OL_GUARD) 00044 #define ALGORITHM_OL_GUARD 00045 00046 #include <ObjectiveLib/Functional.h> 00047 #include <ObjectiveLib/Iterator.h> 00048 00209 @interface OLAlgorithm : 00210 #if defined(OL_NO_OPENSTEP) 00211 Object 00212 #else 00213 NSObject 00214 #endif 00215 { 00216 } 00217 00221 /* @{ */ 00231 + (OLForwardIterator*) adjacentFindFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last; 00232 00250 + (OLForwardIterator*) adjacentFindFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolBinaryFunction>) pred; 00251 00266 + (BOOL) binarySearchFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 00267 00284 + (BOOL) binarySearchFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object predicate: (id<OLBoolBinaryFunction>)pred; 00285 00297 + (unsigned) countFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolUnaryFunction>)pred; 00298 00310 + (unsigned) countFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 00311 00325 + (OLPair*) equalRangeFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 00326 00354 + (OLPair*) equalRangeFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object predicate: (id<OLBoolBinaryFunction>)pred; 00355 00370 + (OLForwardIterator*) findEndFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 subFrom: (OLForwardIterator*)first2 subTo: (OLForwardIterator*)last2; 00371 00392 + (OLForwardIterator*) findEndFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 subFrom: (OLForwardIterator*)first2 subTo: (OLForwardIterator*)last2 predicate: (id<OLBoolBinaryFunction>)pred; 00393 00407 + (OLForwardIterator*) findFirstFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 ofFrom: (OLForwardIterator*)first2 ofTo: (OLForwardIterator*)last2; 00408 00427 + (OLForwardIterator*) findFirstFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 ofFrom: (OLForwardIterator*)first2 ofTo: (OLForwardIterator*)last2 predicate: (id<OLBoolBinaryFunction>)pred; 00428 00445 + (OLForwardIterator*) findFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last if: (id<OLBoolUnaryFunction>)pred; 00446 00463 + (OLForwardIterator*) findFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 00464 00481 + (BOOL) includesFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 subFrom: (OLForwardIterator*)first2 subTo: (OLForwardIterator*)last2; 00482 00504 + (BOOL) includesFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 subFrom: (OLForwardIterator*)first2 subTo: (OLForwardIterator*)last2 predicate: (id<OLBoolBinaryFunction>)pred; 00505 00521 + (OLForwardIterator*) lowerBoundFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 00522 00543 + (OLForwardIterator*) lowerBoundFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object predicate: (id<OLBoolBinaryFunction>)pred; 00544 00555 + (OLForwardIterator*) maxElementFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last; 00556 00572 + (OLForwardIterator*) maxElementFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00573 00584 + (OLForwardIterator*) minElementFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last; 00585 00601 + (OLForwardIterator*) minElementFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00602 00615 + (OLPair*) mismatchFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 with: (OLForwardIterator*)first2; 00616 00637 + (OLPair*) mismatchFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 with: (OLForwardIterator*)first2 predicate: (id<OLBoolBinaryFunction>)pred; 00638 00652 + (OLForwardIterator*) searchFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last count: (unsigned)num value: (id)object; 00653 00673 + (OLForwardIterator*) searchFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last count: (unsigned)num value: (id)object predicate: (id<OLBoolBinaryFunction>)pred; 00674 00687 + (OLForwardIterator*) searchFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 subFrom: (OLForwardIterator*)first2 subTo: (OLForwardIterator*)last2; 00688 00707 + (OLForwardIterator*) searchFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 subFrom: (OLForwardIterator*)first2 subTo: (OLForwardIterator*)last2 predicate: (id<OLBoolBinaryFunction>)pred; 00708 00724 + (OLForwardIterator*) upperBoundFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 00725 00747 + (OLForwardIterator*) upperBoundFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object predicate: (id<OLBoolBinaryFunction>)pred; 00748 /* @} */ 00749 00753 /* @{ */ 00764 + (BOOL) isSortedFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last; 00765 00777 + (BOOL) isSortedFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00778 00789 + (void) nthElementFrom: (OLRandomAccessIterator*)first nth: (OLRandomAccessIterator*)mid to: (OLRandomAccessIterator*)last; 00790 00810 + (void) nthElementFrom: (OLRandomAccessIterator*)first nth: (OLRandomAccessIterator*)mid to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00811 00825 + (OLRandomAccessIterator*) partialSortCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destinationFrom: (OLRandomAccessIterator*)rFirst destinationTo: (OLRandomAccessIterator*)rLast; 00826 00848 + (OLRandomAccessIterator*) partialSortCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destinationFrom: (OLRandomAccessIterator*)rFirst destinationTo: (OLRandomAccessIterator*)rLast predicate: (id<OLBoolBinaryFunction>)pred; 00849 00861 + (void) partialSortFrom: (OLRandomAccessIterator*)first middle: (OLRandomAccessIterator*)mid to: (OLRandomAccessIterator*)last; 00862 00879 + (void) partialSortFrom: (OLRandomAccessIterator*)first middle: (OLRandomAccessIterator*)mid to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00880 00890 + (void) sortFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 00891 00902 + (void) sortFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00903 00919 + (void) sortHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 00920 00937 + (void) sortHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00938 00948 + (void) stableSortFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 00949 00963 + (void) stableSortFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00964 /* @} */ 00965 00969 /* @{ */ 00982 + (BOOL) isHeapFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last; 00983 00997 + (BOOL) isHeapFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 00998 01010 + (void) makeHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 01011 01024 + (void) makeHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 01025 01040 + (void) popHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 01041 01062 + (void) popHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 01063 01078 + (void) pushHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 01079 01095 + (void) pushHeapFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 01096 /* @} */ 01097 01101 /* @{ */ 01123 + (OLForwardIterator*) setDifferenceFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest; 01124 01151 + (OLForwardIterator*) setDifferenceFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest predicate: (id<OLBoolBinaryFunction>)pred; 01152 01174 + (OLForwardIterator*) setIntersectionFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest; 01175 01202 + (OLForwardIterator*) setIntersectionFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest predicate: (id<OLBoolBinaryFunction>)pred; 01203 01225 + (OLForwardIterator*) setSymmetricDifferenceFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest; 01226 01255 + (OLForwardIterator*) setSymmetricDifferenceFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest predicate: (id<OLBoolBinaryFunction>)pred; 01256 01278 + (OLForwardIterator*) setUnionFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest; 01279 01307 + (OLForwardIterator*) setUnionFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest predicate: (id<OLBoolBinaryFunction>)pred; 01308 /* @} */ 01309 01313 /* @{ */ 01328 + (void) inPlaceMergeFrom: (OLBidirectionalIterator*)first middle: (OLBidirectionalIterator*)middle to: (OLBidirectionalIterator*)last; 01329 01348 + (void) inPlaceMergeFrom: (OLBidirectionalIterator*)first middle: (OLBidirectionalIterator*)middle to: (OLBidirectionalIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 01349 01370 + (OLForwardIterator*) mergeFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest; 01371 01400 + (OLForwardIterator*) mergeFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 destination: (OLForwardIterator*)dest predicate: (id<OLBoolBinaryFunction>)pred; 01401 /* @} */ 01402 01406 /* @{ */ 01425 + (OLBidirectionalIterator*) partitionFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last predicate: (id<OLBoolUnaryFunction>)pred; 01426 01441 + (OLForwardIterator*) stablePartitionFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolUnaryFunction>)pred; 01442 /* @} */ 01443 01447 /* @{ */ 01459 + (BOOL) equalFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last with: (OLForwardIterator*)first2; 01460 01475 + (BOOL) equalFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last with: (OLForwardIterator*)first2 predicate: (id<OLBoolBinaryFunction>)pred; 01476 01491 + (BOOL) lexicographicalCompareFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2; 01492 01510 + (BOOL) lexicographicalCompareFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 andFrom: (OLForwardIterator*)first2 andTo: (OLForwardIterator*)last2 predicate: (id<OLBoolBinaryFunction>)pred; 01511 01522 + (id) max: (id)left or: (id)right; 01523 01537 + (id) max: (id)left or: (id)right predicate: (id<OLBoolBinaryFunction>)pred; 01538 01549 + (id) min: (id)left or: (id)right; 01550 01564 + (id) min: (id)left or: (id)right predicate: (id<OLBoolBinaryFunction>)pred; 01565 /* @} */ 01566 01570 /* @{ */ 01593 + (OLBidirectionalIterator*) copyBackwardFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last destination: (OLBidirectionalIterator*)dest; 01594 01616 + (OLForwardIterator*) copyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest; 01617 /* @} */ 01618 01622 /* @{ */ 01633 + (void) fillFrom: (OLForwardIterator*)first count: (unsigned)num value: (id)object; 01634 01645 + (void) fillFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 01646 01658 + (void) forEachFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last function: (id<OLUnaryFunction>)func; 01659 01670 + (BOOL) nextPermutationFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last; 01671 01692 + (BOOL) nextPermutationFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 01693 01704 + (BOOL) prevPermutationFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last; 01705 01726 + (BOOL) prevPermutationFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 01727 01754 + (void) randomShuffleFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last; 01755 01775 + (void) randomShuffleFrom: (OLRandomAccessIterator*)first to: (OLRandomAccessIterator*)last randGen: (id<OLUnaryFunction>)gen; 01776 01799 + (OLForwardIterator*) removeCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest if: (id<OLBoolUnaryFunction>)pred; 01800 01826 + (OLForwardIterator*) removeCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest value: (id)object; 01827 01847 + (OLForwardIterator*) removeFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last if: (id<OLBoolUnaryFunction>)pred; 01848 01871 + (OLForwardIterator*) removeFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last value: (id)object; 01872 01896 + (OLForwardIterator*) replaceCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest if: (id<OLBoolUnaryFunction>)pred newValue: (id)newv; 01897 01923 + (OLForwardIterator*) replaceCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest oldValue: (id)oldv newValue: (id)newv; 01924 01937 + (void) replaceFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last if: (id<OLBoolUnaryFunction>)pred newValue: (id)newv; 01938 01954 + (void) replaceFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last oldValue: (id)oldv newValue: (id)newv; 01955 01974 + (OLForwardIterator*) reverseCopyFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last destination: (OLForwardIterator*)dest; 01975 01985 + (void) reverseFrom: (OLBidirectionalIterator*)first to: (OLBidirectionalIterator*)last; 01986 02012 + (OLForwardIterator*) rotateCopyFrom: (OLForwardIterator*)first middle: (OLForwardIterator*)mid to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest; 02013 02037 + (OLForwardIterator*) rotateFrom: (OLForwardIterator*)first middle: (OLForwardIterator*)mid to: (OLForwardIterator*)last; 02038 02062 + (OLForwardIterator*) transformFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest function: (id<OLUnaryFunction>)func; 02063 02092 + (OLForwardIterator*) transformFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last withArgsFrom: (OLForwardIterator*)first2 destination: (OLForwardIterator*)dest function: (id<OLBinaryFunction>)func; 02093 02107 + (OLForwardIterator*) uniqueCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest; 02108 02128 + (OLForwardIterator*) uniqueCopyFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last destination: (OLForwardIterator*)dest predicate: (id<OLBoolBinaryFunction>)pred; 02129 02140 + (OLForwardIterator*) uniqueFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last; 02141 02159 + (OLForwardIterator*) uniqueFrom: (OLForwardIterator*)first to: (OLForwardIterator*)last predicate: (id<OLBoolBinaryFunction>)pred; 02160 /* @} */ 02161 02165 /* @{ */ 02175 + (void) swap: (id*)left and: (id*)right; 02176 02186 + (void) swapIterators: (OLIterator*)left and: (OLIterator*)right; 02187 02207 + (OLForwardIterator*) swapRangesFrom: (OLForwardIterator*)first1 to: (OLForwardIterator*)last1 with: (OLForwardIterator*)first2; 02208 /* @} */ 02209 02210 @end 02211 02212 #endif
|