Sponsored Links

Sponsored Links

Page 26 of 30 FirstFirst ... 162425262728 ... LastLast
Results 251 to 260 of 291



  1. #251
    Contributor laker's Avatar
    Join Date
    Jan 2010
    Posts
    25
    Sponsored Links
    Sponsored Links
    Could someone upload the sdk to multiupload? I can't access usenet to download the files.

  2. #252
    Contributor Roxanne's Avatar
    Join Date
    Dec 2011
    Posts
    8
    Sponsored Links
    Sponsored Links
    Upload in progress!
    Attached Images<br><br> Attached Images


  3. #253
    Senior Member cfwprophet's Avatar
    Join Date
    Jul 2008
    Posts
    1,815
    Sponsored Links
    Sponsored Links
    Thx for sharing with me Roxanne my love

  4. #254
    Member SanctumSlayer's Avatar
    Join Date
    Jan 2012
    Posts
    79
    Question. What was acomplished for cfw by Johnathon's 3.60 sdk leak last?

    Isn't this sdk leak just like another update?

    Or are devs seeing more potential for an exploit in this leak?

  5. #255
    Contributor Roxanne's Avatar
    Join Date
    Dec 2011
    Posts
    8
    Download link: [Register or Login to view links]

  6. #256
    Banned User
    Join Date
    Feb 2011
    Posts
    278
    Thanks but RapidPAY is no good as it tells you the file is too big unless you pay.

  7. #257
    Senior Member Ezio's Avatar
    Join Date
    Aug 2011
    Posts
    355
    Thanks for uploading, Roxanne, +Rep for you!
    Last edited by Ezio; 01-31-2012 at 10:05 AM Reason: Automerged Doublepost

  8. #258
    Junior Member zadow30's Avatar
    Join Date
    Sep 2010
    Posts
    18

    Cool algorithm from sdk 370

    well here you go.. well this look a hell of a lot interesting: pastebin.com/sje1NrRG
    Code:
    /* SCE CONFIDENTIAL
    PlayStation(R)3 Programmer Tool Runtime Library 370.001
    * Copyright (C) 2007 Sony Computer Entertainment Inc. 
    * All Rights Reserved.
    */
    #ifndef _TT800_H
    #define _TT800_H
    
    /* The algorithm is taken from the following: */
    /* C version of TT800 random number generator developed */
    /* by M. Matsumoto, email: matumoto[MENTION=8731]math[/MENTION].keio.ac.jp */
    /* See: ACM Transactions on Modelling and Computer Simulation, */
    /* Vol. 4, No. 3, 1994, pages 254-266. */
    // This version supports getting and saving of the state vector
    // which is encapsulated in a global structure.  Also added functions to
    // seed the generator from an integer or array. And to produce output numbers
    // scaled into various ranges.
    
    #include <bits/tt800_globals.h>
    
    // Returns the address and size (in bytes) of the TT800 state vector.
    // This lets you to save and restore the state of the random number generator
    // when code is swapped on or off of the SPU.  This allows you to unload an SPU applet,
    // load it back up later and have it continue from where it left off in the
    // random number sequence, rather than having it start from the beginning.
    // This is a better, faster and more statistically correct than reseeding the random
    // number generator each time the SPU applet is reloaded.
    // 
    // To save the state, call this function to get the address and size of the state
    // vector then memcopy or DMA that data to some safe location.  To restore it, do 
    // do the same thing but copy the data into the address provided.
    //
    // DO NOT use this to seed the generator as you could put in values would cause the
    // generator output to be non-random or degenerate to zero.  Always use the init_
    // functions to seed the generator, they protect against bad seed values.
    //
    // The internal format of this data may change so avoid putting it in long-term
    // storage or making assumptions about it's size/format till the library is finalized.
    //
    
    _FUNC_DEF(int, get_state_TT800,(void **state))
    {
      *state = (void *)&__TT800;
      return(sizeof(__TT800));
    }
    
    /* initializes TT800 a seed (Needs to be checked) */
    // !!!GAC THIS INITIALIZER MAY NOT BE STATISTICALLY SOUND, it didn't come with the generator
    _FUNC_DEF(void, init_TT800,(unsigned int s))
    {
      int i;
      unsigned int *p = (unsigned int *)__TT800.State;
      for(i=0; i < _N_TT800; i++)
      {
        *(p++) ^= s;
      }
      __TT800.Next_Number = 0;
    }
    
    /* initializes TT800 an array (Needs to be checked) */
    // !!!GAC THIS INITIALIZER MAY NOT BE STATISTICALLY SOUND, it didn't come with the generator
    _FUNC_DEF(void, init_by_array_TT800,(unsigned int init_key[], int key_length))
    {
      int i,j;
      unsigned int *p = (unsigned int *)__TT800.State;
      for(i=0,j=0; i < _N_TT800; i++, j++)
      {
        if(j > key_length) j=0;
        *(p++) ^= init_key[j];
      }
      __TT800.Next_Number = 0;
    }
    
    // Core random number generator, generates numbers in batches and returns them one at a time.
    _FUNC_DEF(unsigned int, rand_int32_TT800,(void))
    {
      unsigned int y;
      static const unsigned int mag01[2]={0x0, 0x8ebfd028 } ; // This is a magic number, do not change
    
      // Do we need to generate a new batch of numbers?
      if (__TT800.Next_Number==_N_TT800)
      { 
        // generate _N_TT800 words at one time 
        int kk;
        for (kk=0;kk<_N_TT800-_M_TT800;kk++)
        {
          __TT800.State[kk] = __TT800.State[kk+_M_TT800] ^ (__TT800.State[kk] >> 1) ^ mag01[__TT800.State[kk] % 2];
        }
        for (; kk<_N_TT800;kk++)
        {
          __TT800.State[kk] = __TT800.State[kk+(_M_TT800-_N_TT800)] ^ (__TT800.State[kk] >> 1) ^ mag01[__TT800.State[kk] % 2];
        }
        __TT800.Next_Number=0;
      }
      // Get the next available number from the array
      y = __TT800.State[__TT800.Next_Number];
      // Temper the number using some more magic numbers from Matsumoto's algorithm
      y ^= (y << 7) & 0x2b5b2500; 
      y ^= (y << 15) & 0xdb8b0000;
      y &= 0xffffffff; // Only required if word size != 32 
      y ^= (y >> 16); 
      __TT800.Next_Number++;
      return( y );
    }
    /* generates a random number on [0,0x7fffffff]-interval */
    _FUNC_DEF(unsigned int, rand_int31_TT800, (void))
    {
        return (long)(rand_int32_TT800()>>1);
    }
    
    /* generates a random number on [0,1]-real-interval */
    _FUNC_DEF(float, rand_real1_TT800, (void))
    {
        return rand_int32_TT800()*(1.0f/4294967295.0f); 
        /* divided by 2^32-1 */ 
    }
    
    /* generates a random number on [0,1)-real-interval */
    _FUNC_DEF(float, rand_real2_TT800, (void))
    {
        return rand_int32_TT800()*(1.0f/4294967296.0f); 
        /* divided by 2^32 */
    }
    
    /* generates a random number on (0,1)-real-interval */
    _FUNC_DEF(float, rand_real3_TT800, (void))
    {
      unsigned int dr = rand_int32_TT800();
        return (((float)dr) + 0.5f)*(1.0f/4294967296.0f); 
        /* divided by 2^32 */
    }
    
    #endif /* _TT800_H */

    Code:
    /* SCE CONFIDENTIAL
    PlayStation(R)3 Programmer Tool Runtime Library 370.001
    * Copyright (C) 2007 Sony Computer Entertainment Inc. 
    * All Rights Reserved.
    */
    #ifndef _TT800_GLOBALS_H_
    #define _TT800_GLOBALS_H_
    
    #include <yvals.h>
    
    // These are global values and typedefs needed in the tt800 random number generator
    // implementation and in the definitions of it's global state vector
    
    #define _N_TT800 25
    #define _N_TT800_QWORDS ((25/4)+1)
    #define _M_TT800 7
    
    typedef struct 
    {
      // Current batch of TT800 generated numbers
      unsigned int State[_N_TT800]; 
      // Next number in the state vector to be returned to the caller
      int Next_Number;
    } __TT800_State_t;
    
    _C_LIB_DECL
    extern __TT800_State_t __TT800;
    _END_C_LIB_DECL
    find that book

    from the book:
    Code:
    /* A C-program for TT800 : July 8th 1996 Version */
    /* by M. Matsumoto, email: [Register or Login to view links] */
    /* genrand() generate one pseudorandom number with double precision */
    /* which is uniformly distributed on [0,1]-interval */
    /* for each call.  One may choose any initial 25 seeds */
    /* except all zeros. */
    
    /* See: ACM Transactions on Modelling and Computer Simulation, */
    /* Vol. 4, No. 3, 1994, pages 254-266. */
    
    #include <stdio.h>
    #define N 25
    #define M 7
    
    double
    genrand()
    {
        unsigned long y;
        static int k = 0;
        static unsigned long x[N]={ /* initial 25 seeds, change as you wish */
    	0x95f24dab, 0x0b685215, 0xe76ccae7, 0xaf3ec239, 0x715fad23,
    	0x24a590ad, 0x69e4b5ef, 0xbf456141, 0x96bc1b7b, 0xa7bdf825,
    	0xc1de75b7, 0x8858a9c9, 0x2da87693, 0xb657f9dd, 0xffdc8a9f,
    	0x8121da71, 0x8b823ecb, 0x885d05f5, 0x4e20cd47, 0x5a9ad5d9,
    	0x512c0c03, 0xea857ccd, 0x4cc1d30f, 0x8891a8a1, 0xa6b7aadb
        };
        static unsigned long mag01[2]={ 
            0x0, 0x8ebfd028 /* this is magic vector `a', don't change */
        };
        if (k==N) { /* generate N words at one time */
          int kk;
          for (kk=0;kk<N-M;kk++) {
    	x[kk] = x[kk+M] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];
          }
          for (; kk<N;kk++) {
    	x[kk] = x[kk+(M-N)] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];
          }
          k=0;
        }
        y = x[k];
        y ^= (y << 7) & 0x2b5b2500; /* s and b, magic vectors */
        y ^= (y << 15) & 0xdb8b0000; /* t and c, magic vectors */
        y &= 0xffffffff; /* you may delete this line if word size = 32 */
    /* 
       the following line was added by Makoto Matsumoto in the 1996 version
       to improve lower bit's corellation.
       Delete this line to o use the code published in 1994.
    */
        y ^= (y >> 16); /* added to the 1994 version */
        k++;
        return( (double) y / (unsigned long) 0xffffffff);
    }
    
    /* this main() output first 50 generated numbers */
    main()
    { int j;
      for (j=0; j<50; j++) {
        printf("%5f ", genrand());
        if (j%8==7) printf("\n");
      }
      printf("\n");
    }
    here is more:
    Code:
    /*   SCE CONFIDENTIAL                                       */
    /*   PlayStation(R)3 Programmer Tool Runtime Library 370.001 */
    /*   Copyright (C) 2005 Sony Computer Entertainment Inc.    */
    /*   All Rights Reserved.                                   */
    
    #ifndef __SYS_SYS_SYSCALL_H__
    #define __SYS_SYS_SYSCALL_H__
    
    #define SYS_PROCESS_GETPID                                            1
    #define SYS_PROCESS_WAIT_FOR_CHILD                                    2
    #define SYS_PROCESS_GET_STATUS                                        4
    #define SYS_PROCESS_DETACH_CHILD                                      5
    #define SYS_PROCESS_GET_NUMBER_OF_OBJECT                             12
    #define SYS_PROCESS_GET_ID                                           13
    #define SYS_PROCESS_IS_SPU_LOCK_LINE_RESERVATION_ADDRESS             14
    #define SYS_PROCESS_GETPPID                                          18
    #define SYS_PROCESS_KILL                                             19
    #define SYS_PROCESS_WAIT_FOR_CHILD2                                  23
    #define SYS_PROCESS_GET_SDK_VERSION                                  25
    #define SYS_PROCESS_GET_PPU_GUID                                     31
    #define SYS_PPU_THREAD_YIELD                                         43
    #define SYS_PPU_THREAD_JOIN                                          44
    #define SYS_PPU_THREAD_DETACH                                        45
    #define SYS_PPU_THREAD_GET_JOIN_STATE                                46
    #define SYS_PPU_THREAD_SET_PRIORITY                                  47
    #define SYS_PPU_THREAD_GET_PRIORITY                                  48
    #define SYS_PPU_THREAD_GET_STACK_INFORMATION                         49
    #define SYS_PPU_THREAD_RENAME                                        56
    #define SYS_PPU_THREAD_RECOVER_PAGE_FAULT                            57
    #define SYS_PPU_THREAD_GET_PAGE_FAULT_CONTEXT                        58
    #define SYS_TRACE_ALLOCATE_BUFFER                                    67
    #define SYS_TRACE_FREE_BUFFER                                        68
    #define SYS_TRACE_CREATE2                                            69
    #define SYS_TIMER_CREATE                                             70
    #define SYS_TIMER_DESTROY                                            71
    #define SYS_TIMER_GET_INFORMATION                                    72
    #define _SYS_TIMER_START                                             73
    #define SYS_TIMER_STOP                                               74
    #define SYS_TIMER_CONNECT_EVENT_QUEUE                                75
    #define SYS_TIMER_DISCONNECT_EVENT_QUEUE                             76
    #define SYS_TRACE_CREATE2_IN_CBEPM                                   77
    #define SYS_INTERRUPT_TAG_CREATE                                     80
    #define SYS_INTERRUPT_TAG_DESTROY                                    81
    #define SYS_EVENT_FLAG_CREATE                                        82
    #define SYS_EVENT_FLAG_DESTROY                                       83
    #define _SYS_INTERRUPT_THREAD_ESTABLISH                              84
    #define SYS_EVENT_FLAG_WAIT                                          85
    #define SYS_EVENT_FLAG_TRYWAIT                                       86
    #define SYS_EVENT_FLAG_SET                                           87
    #define SYS_INTERRUPT_THREAD_EOI                                     88
    #define _SYS_INTERRUPT_THREAD_DISESTABLISH                           89
    #define SYS_SEMAPHORE_CREATE                                         90
    #define SYS_SEMAPHORE_DESTROY                                        91
    #define SYS_SEMAPHORE_WAIT                                           92
    #define SYS_SEMAPHORE_TRYWAIT                                        93
    #define SYS_SEMAPHORE_POST                                           94
    #define SYS_MUTEX_CREATE                                            100
    #define SYS_MUTEX_DESTROY                                           101
    #define SYS_MUTEX_LOCK                                              102
    #define SYS_MUTEX_TRYLOCK                                           103
    #define SYS_MUTEX_UNLOCK                                            104
    #define SYS_COND_CREATE                                             105
    #define SYS_COND_DESTROY                                            106
    #define SYS_COND_WAIT                                               107
    #define SYS_COND_SIGNAL                                             108
    #define SYS_COND_SIGNAL_ALL                                         109
    #define SYS_COND_SIGNAL_TO                                          110
    #define SYS_SEMAPHORE_GET_VALUE                                     114
    #define SYS_EVENT_FLAG_CLEAR                                        118
    #define SYS_RWLOCK_CREATE                                           120
    #define SYS_RWLOCK_DESTROY                                          121
    #define SYS_RWLOCK_RLOCK                                            122
    #define SYS_RWLOCK_TRYRLOCK                                         123
    #define SYS_RWLOCK_RUNLOCK                                          124
    #define SYS_RWLOCK_WLOCK                                            125
    #define SYS_RWLOCK_WUNLOCK                                          127
    #define SYS_EVENT_QUEUE_CREATE                                      128
    #define SYS_EVENT_QUEUE_DESTROY                                     129
    #define SYS_EVENT_QUEUE_RECEIVE                                     130
    #define SYS_EVENT_QUEUE_TRYRECEIVE                                  131
    #define SYS_EVENT_FLAG_CANCEL                                       132
    #define SYS_EVENT_QUEUE_DRAIN                                       133
    #define SYS_EVENT_PORT_CREATE                                       134
    #define SYS_EVENT_PORT_DESTROY                                      135
    #define SYS_EVENT_PORT_CONNECT_LOCAL                                136
    #define SYS_EVENT_PORT_DISCONNECT                                   137
    #define SYS_EVENT_PORT_SEND                                         138
    #define SYS_EVENT_FLAG_GET                                          139
    #define SYS_EVENT_PORT_CONNECT_IPC                                  140
    #define SYS_TIMER_USLEEP                                            141
    #define SYS_TIMER_SLEEP                                             142
    #define SYS_TIME_GET_CURRENT_TIME                                   145
    #define SYS_TIME_GET_TIMEBASE_FREQUENCY                             147
    #define SYS_RWLOCK_TRYWLOCK                                         148
    #define SYS_RAW_SPU_CREATE_INTERRUPT_TAG                            150
    #define SYS_RAW_SPU_SET_INT_MASK                                    151
    #define SYS_RAW_SPU_GET_INT_MASK                                    152
    #define SYS_RAW_SPU_SET_INT_STAT                                    153
    #define SYS_RAW_SPU_GET_INT_STAT                                    154
    #define SYS_SPU_IMAGE_OPEN                                          156
    #define SYS_RAW_SPU_CREATE                                          160
    #define SYS_RAW_SPU_DESTROY                                         161
    #define SYS_RAW_SPU_READ_PUINT_MB                                   163
    #define SYS_SPU_THREAD_GET_EXIT_STATUS                              165
    #define SYS_SPU_THREAD_SET_ARGUMENT                                 166
    #define SYS_SPU_THREAD_GROUP_START_ON_EXIT                          167
    #define SYS_SPU_INITIALIZE                                          169
    #define SYS_SPU_THREAD_GROUP_CREATE                                 170
    #define SYS_SPU_THREAD_GROUP_DESTROY                                171
    #define SYS_SPU_THREAD_INITIALIZE                                   172
    #define SYS_SPU_THREAD_GROUP_START                                  173
    #define SYS_SPU_THREAD_GROUP_SUSPEND                                174
    #define SYS_SPU_THREAD_GROUP_RESUME                                 175
    #define SYS_SPU_THREAD_GROUP_YIELD                                  176
    #define SYS_SPU_THREAD_GROUP_TERMINATE                              177
    #define SYS_SPU_THREAD_GROUP_JOIN                                   178
    #define SYS_SPU_THREAD_GROUP_SET_PRIORITY                           179
    #define SYS_SPU_THREAD_GROUP_GET_PRIORITY                           180
    #define SYS_SPU_THREAD_WRITE_LS                                     181
    #define SYS_SPU_THREAD_READ_LS                                      182
    #define SYS_SPU_THREAD_WRITE_SNR                                    184
    #define SYS_SPU_THREAD_GROUP_CONNECT_EVENT                          185
    #define SYS_SPU_THREAD_GROUP_DISCONNECT_EVENT                       186
    #define SYS_SPU_THREAD_SET_SPU_CFG                                  187
    #define SYS_SPU_THREAD_GET_SPU_CFG                                  188
    #define SYS_SPU_THREAD_WRITE_SPU_MB                                 190
    #define SYS_SPU_THREAD_CONNECT_EVENT                                191
    #define SYS_SPU_THREAD_DISCONNECT_EVENT                             192
    #define SYS_SPU_THREAD_BIND_QUEUE                                   193
    #define SYS_SPU_THREAD_UNBIND_QUEUE                                 194
    #define SYS_RAW_SPU_SET_SPU_CFG                                     196
    #define SYS_RAW_SPU_GET_SPU_CFG                                     197
    #define SYS_SPU_THREAD_RECOVER_PAGE_FAULT                           198
    #define SYS_RAW_SPU_RECOVER_PAGE_FAULT                              199
    #define SYS_SPU_THREAD_GROUP_SET_COOPERATIVE_VICTIMS                250
    #define SYS_SPU_THREAD_GROUP_CONNECT_EVENT_ALL_THREADS              251
    #define SYS_SPU_THREAD_GROUP_DISCONNECT_EVENT_ALL_THREADS           252
    #define SYS_SPU_THREAD_GROUP_LOG                                    254
    #define SYS_SPU_IMAGE_OPEN_BY_FD                                    260
    #define SYS_VM_MEMORY_MAP                                           300
    #define SYS_VM_UNMAP                                                301
    #define SYS_VM_APPEND_MEMORY                                        302
    #define SYS_VM_RETURN_MEMORY                                        303
    #define SYS_VM_LOCK                                                 304
    #define SYS_VM_UNLOCK                                               305
    #define SYS_VM_TOUCH                                                306
    #define SYS_VM_FLUSH                                                307
    #define SYS_VM_INVALIDATE                                           308
    #define SYS_VM_STORE                                                309
    #define SYS_VM_SYNC                                                 310
    #define SYS_VM_TEST                                                 311
    #define SYS_VM_GET_STATISTICS                                       312
    #define SYS_MEMORY_CONTAINER_CREATE                                 324
    #define SYS_MEMORY_CONTAINER_DESTROY                                325
    #define SYS_MMAPPER_ALLOCATE_FIXED_ADDRESS                          326
    #define SYS_MMAPPER_ENABLE_PAGE_FAULT_NOTIFICATION                  327
    #define SYS_MMAPPER_ALLOCATE_ADDRESS                                330
    #define SYS_MMAPPER_FREE_ADDRESS                                    331
    #define SYS_MMAPPER_CHANGE_ADDRESS_ACCESS_RIGHT                     336
    #define SYS_MMAPPER_SEARCH_AND_MAP                                  337
    #define SYS_MEMORY_CONTAINER_GET_SIZE                               343
    #define SYS_MEMORY_ALLOCATE                                         348
    #define SYS_MEMORY_FREE                                             349
    #define SYS_MEMORY_ALLOCATE_FROM_CONTAINER                          350
    #define SYS_MEMORY_GET_PAGE_ATTRIBUTE                               351
    #define SYS_MEMORY_GET_USER_MEMORY_SIZE                             352
    #define SYS_TTY_READ                                                402
    #define SYS_TTY_WRITE                                               403
    #define SYS_OVERLAY_LOAD_MODULE                                     450
    #define SYS_OVERLAY_UNLOAD_MODULE                                   451
    #define SYS_OVERLAY_GET_MODULE_LIST                                 452
    #define SYS_OVERLAY_GET_MODULE_INFO                                 453
    #define SYS_OVERLAY_LOAD_MODULE_BY_FD                               454
    #define SYS_OVERLAY_GET_MODULE_INFO2                                455
    #define SYS_OVERLAY_GET_SDK_VERSION                                 456
    #define _SYS_PRX_GET_MODULE_ID_BY_ADDRESS                           461
    #define _SYS_PRX_LOAD_MODULE_BY_FD                                  463
    #define _SYS_PRX_LOAD_MODULE_ON_MEMCONTAINER_BY_FD                  464
    #define _SYS_PRX_LOAD_MODULE_LIST                                   465
    #define _SYS_PRX_LOAD_MODULE_LIST_ON_MEMCONTAINER                   466
    #define SYS_PRX_GET_PPU_GUID                                        467
    #define _SYS_PRX_LOAD_MODULE                                        480
    #define _SYS_PRX_START_MODULE                                       481
    #define _SYS_PRX_STOP_MODULE                                        482
    #define _SYS_PRX_UNLOAD_MODULE                                      483
    #define _SYS_PRX_REGISTER_MODULE                                    484
    #define _SYS_PRX_QUERY_MODULE                                       485
    #define _SYS_PRX_REGISTER_LIBRARY                                   486
    #define _SYS_PRX_UNREGISTER_LIBRARY                                 487
    #define _SYS_PRX_LINK_LIBRARY                                       488
    #define _SYS_PRX_UNLINK_LIBRARY                                     489
    #define _SYS_PRX_QUERY_LIBRARY                                      490
    #define _SYS_PRX_GET_MODULE_LIST                                    494
    #define _SYS_PRX_GET_MODULE_INFO                                    495
    #define _SYS_PRX_GET_MODULE_ID_BY_NAME                              496
    #define _SYS_PRX_LOAD_MODULE_ON_MEMCONTAINER                        497
    #define _SYS_PRX_START                                              498
    #define _SYS_PRX_STOP                                               499
    #define SYS_STORAGE_OPEN                                            600
    #define SYS_STORAGE_CLOSE                                           601
    #define SYS_STORAGE_READ                                            602
    #define SYS_STORAGE_WRITE                                           603
    #define SYS_STORAGE_SEND_DEVICE_COMMAND                             604
    #define SYS_STORAGE_ASYNC_CONFIGURE                                 605
    #define SYS_STORAGE_ASYNC_READ                                      606
    #define SYS_STORAGE_ASYNC_WRITE                                     607
    #define SYS_STORAGE_ASYNC_CANCEL                                    608
    #define SYS_STORAGE_GET_DEVICE_INFO                                 609
    #define SYS_STORAGE_GET_DEVICE_CONFIG                               610
    #define SYS_STORAGE_REPORT_DEVICES                                  611
    #define SYS_STORAGE_CONFIGURE_MEDIUM_EVENT                          612
    #define SYS_STORAGE_SET_MEDIUM_POLLING_INTERVAL                     613
    #define SYS_STORAGE_CREATE_REGION                                   614
    #define SYS_STORAGE_DELETE_REGION                                   615
    #define SYS_STORAGE_EXECUTE_DEVICE_COMMAND                          616
    #define SYS_STORAGE_GET_REGION_ACL                                  617
    #define SYS_STORAGE_SET_REGION_ACL                                  618
    #define SYS_STORAGE_ASYNC_SEND_DEVICE_COMMAND                       619
    #define SYS_STORAGE_GET_REGION_OFFSET                               622
    #define SYS_STORAGE_SET_EMULATED_SPEED                              623
    #define SYS_IO_BUFFER_CREATE                                        624
    #define SYS_IO_BUFFER_DESTROY                                       625
    #define SYS_IO_BUFFER_ALLOCATE                                      626
    #define SYS_IO_BUFFER_FREE                                          627
    #define SYS_GPIO_SET                                                630
    #define SYS_GPIO_GET                                                631
    #define SYS_FSW_CONNECT_EVENT                                       633
    #define SYS_FSW_DISCONNECT_EVENT                                    634
    #define SYS_RSX_DEVICE_OPEN                                         666
    #define SYS_RSX_DEVICE_CLOSE                                        667
    #define SYS_RSX_MEMORY_ALLOCATE                                     668
    #define SYS_RSX_MEMORY_FREE                                         669
    #define SYS_RSX_CONTEXT_ALLOCATE                                    670
    #define SYS_RSX_CONTEXT_FREE                                        671
    #define SYS_RSX_CONTEXT_IOMAP                                       672
    #define SYS_RSX_CONTEXT_IOUNMAP                                     673
    #define SYS_RSX_CONTEXT_ATTRIBUTE                                   674
    #define SYS_RSX_DEVICE_MAP                                          675
    #define SYS_RSX_DEVICE_UNMAP                                        676
    #define SYS_RSX_ATTRIBUTE                                           677
    #define SYS_BDEMU_SEND_COMMAND                                      699
    #define SYS_SS_GET_OPEN_PSID                                        872
    #define SYS_DECI3_OPEN                                              880
    #define SYS_DECI3_CREATE_EVENT_PATH                                 881
    #define SYS_DECI3_CLOSE                                             882
    #define SYS_DECI3_SEND                                              883
    #define SYS_DECI3_RECEIVE                                           884
    
    #define MAX_NUM_OF_SYSTEM_CALLS                                    1024
    
    /* The following macros represent the numbers for the SPU library functions. */
    #define SYS_SPU_THREAD_EXIT                                           1
    #define SYS_SPU_THREAD_GROUP_EXIT                                     2
    #define SYS_SPU_THREAD_YIELD                                          3
    #define SYS_SPU_THREAD_RECEIVE_EVENT                                  4
    #define SYS_SPU_THREAD_TRYRECEIVE_EVENT                               5
    #define SYS_SPU_THREAD_SEND_EVENT                                     6
    #define SYS_SPU_THREAD_THROW_EVENT                                    7
    #define SYS_EVENT_FLAG_SET_BIT                                        8
    #define SYS_EVENT_FLAG_SET_BIT_IMPATIENT                              9
    #define SYS_SPU_THREAD_SWITCH_TO_SYSTEM_MODULE                       10
    
    #include <sys/types.h>
    
    
    #if defined(__SNC__)
    
    /* __system_call_NNN is converted to an inline "sc" instruction */
    #define __system_call_( n ) __system_call_##n
    
    #define system_call_8(syscall_num, a1, a2, a3, a4, a5, a6, a7, a8) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t , uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2, a3, a4, a5, a6, a7, a8);
    
    #define system_call_7(syscall_num, a1, a2, a3, a4, a5, a6, a7) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2, a3, a4, a5, a6, a7);
    
    #define system_call_6(syscall_num, a1, a2, a3, a4, a5, a6) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t, uint64_t, uint64_t, uint64_t, uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2, a3, a4, a5, a6);
    
    #define system_call_5(syscall_num, a1, a2, a3, a4, a5) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t, uint64_t, uint64_t, uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2, a3, a4, a5);
    
    #define system_call_4(syscall_num, a1, a2, a3, a4) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t, uint64_t, uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2, a3, a4);
    
    #define system_call_3(syscall_num, a1, a2, a3) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t, uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2, a3);
    
    #define system_call_2(syscall_num, a1, a2) \
      extern uint64_t __system_call_(syscall_num)(uint64_t, uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1, a2);
    
    #define system_call_1(syscall_num, a1) \
      extern uint64_t __system_call_(syscall_num)(uint64_t); \
      uint64_t p1 = __system_call_(syscall_num)(a1);
    
    #define system_call_0(syscall_num) \
      extern uint64_t __system_call_(syscall_num)(void); \
      uint64_t p1 = __system_call_(syscall_num)();
    
    /*
     * Calling this macro lets the stub return to the user program.
     * 
     * \param ret_type The return parameter type
     */
    #define return_to_user_prog(ret_type) return (ret_type)(p1)
    
    /*
     * Macros to obtain the register passing return arguments.
     * 
     * __reg( n ) intrinsic gets the returned register value from the previous call/syscall
     */
    #define register_passing_1(type) (type)( __reg( 4 ) )
    #define register_passing_2(type) (type)( __reg( 5 ) )
    #define register_passing_3(type) (type)( __reg( 6 ) )
    #define register_passing_4(type) (type)( __reg( 7 ) )
    #define register_passing_5(type) (type)( __reg( 8 ) )
    #define register_passing_6(type) (type)( __reg( 9 ) )
    #define register_passing_7(type) (type)( __reg( 10 ) )
    
    #else /* !SNC */
    
    
    /*
     * Load the arguments and system call numbers to the registers, and issue
     * the "sc" instruction.
     *
     * \param nr The number of arguments
     * \param syscall_num The system call number
     * \param args The argument list
     */
    #define system_call_8(syscall_num, a1, a2, a3, a4, a5, a6, a7, a8)          \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5") = a3;                                   \
    register uint64_t p4 __asm__ ("6") = a4;                                   \
    register uint64_t p5 __asm__ ("7") = a5;                                   \
    register uint64_t p6 __asm__ ("8") = a6;                                   \
    register uint64_t p7 __asm__ ("9") = a7;                                   \
    register uint64_t p8 __asm__ ("10") = a8;                                  \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (p3), "r" (p4),                \
                        "r" (p5), "r" (p6), "r" (p7), "r" (p8), "r" (n)        \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_7(syscall_num, a1, a2, a3, a4, a5, a6, a7)             \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5") = a3;                                   \
    register uint64_t p4 __asm__ ("6") = a4;                                   \
    register uint64_t p5 __asm__ ("7") = a5;                                   \
    register uint64_t p6 __asm__ ("8") = a6;                                   \
    register uint64_t p7 __asm__ ("9") = a7;                                   \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (p3), "r" (p4),                \
                        "r" (p5), "r" (p6), "r" (p7), "r" (n)                  \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_6(syscall_num, a1, a2, a3, a4, a5, a6)                 \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5") = a3;                                   \
    register uint64_t p4 __asm__ ("6") = a4;                                   \
    register uint64_t p5 __asm__ ("7") = a5;                                   \
    register uint64_t p6 __asm__ ("8") = a6;                                   \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (p3), "r" (p4),                \
                        "r" (p5), "r" (p6), "r" (n)                            \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_5(syscall_num, a1, a2, a3, a4, a5)                     \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5") = a3;                                   \
    register uint64_t p4 __asm__ ("6") = a4;                                   \
    register uint64_t p5 __asm__ ("7") = a5;                                   \
    register uint64_t p6 __asm__ ("8");                                        \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (p3), "r" (p4),                \
                        "r" (p5), "r" (n)                                      \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_4(syscall_num, a1, a2, a3, a4)                         \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5") = a3;                                   \
    register uint64_t p4 __asm__ ("6") = a4;                                   \
    register uint64_t p5 __asm__ ("7");                                        \
    register uint64_t p6 __asm__ ("8");                                        \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (p3), "r" (p4),                \
                        "r" (n)                                                \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_3(syscall_num, a1, a2, a3)                             \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5") = a3;                                   \
    register uint64_t p4 __asm__ ("6");                                        \
    register uint64_t p5 __asm__ ("7");                                        \
    register uint64_t p6 __asm__ ("8");                                        \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (p3), "r" (n)                  \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_2(syscall_num, a1, a2)                                 \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4") = a2;                                   \
    register uint64_t p3 __asm__ ("5");                                        \
    register uint64_t p4 __asm__ ("6");                                        \
    register uint64_t p5 __asm__ ("7");                                        \
    register uint64_t p6 __asm__ ("8");                                        \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1), "r" (p2), "r" (n)                            \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_1(syscall_num, a1)                                     \
    register uint64_t p1 __asm__ ("3") = a1;                                   \
    register uint64_t p2 __asm__ ("4");                                        \
    register uint64_t p3 __asm__ ("5");                                        \
    register uint64_t p4 __asm__ ("6");                                        \
    register uint64_t p5 __asm__ ("7");                                        \
    register uint64_t p6 __asm__ ("8");                                        \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (p1),  "r" (n)                                     \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    #define system_call_0(syscall_num)                                         \
    register uint64_t p1 __asm__ ("3");                                        \
    register uint64_t p2 __asm__ ("4");                                        \
    register uint64_t p3 __asm__ ("5");                                        \
    register uint64_t p4 __asm__ ("6");                                        \
    register uint64_t p5 __asm__ ("7");                                        \
    register uint64_t p6 __asm__ ("8");                                        \
    register uint64_t p7 __asm__ ("9");                                        \
    register uint64_t p8 __asm__ ("10");                                       \
    register uint64_t n  __asm__ ("11") = syscall_num;                         \
                                                                               \
    __asm__ volatile ("sc"                                                     \
                      : "=r" (p1), "=r" (p2), "=r" (p3), "=r" (p4),            \
                        "=r" (p5), "=r" (p6), "=r" (p7), "=r" (p8), "=r" (n)   \
                      : "r" (n)                                                \
                      : "0", "12", "lr", "ctr", "xer", "cr0", "cr1", "cr5", "cr6", "cr7", "memory") \
    
    
    /*
     * Calling this macro lets the stub return to the user program.
     * 
     * \param ret_type The return parameter type
     */
    #define return_to_user_prog(ret_type) return (ret_type)(p1)
    
    
    /*
     * Macros to obtain the register passing return arguments.
     */
    #define register_passing_1(type) (type)(p2)
    #define register_passing_2(type) (type)(p3)
    #define register_passing_3(type) (type)(p4)
    #define register_passing_4(type) (type)(p5)
    #define register_passing_5(type) (type)(p6)
    #define register_passing_6(type) (type)(p7)
    #define register_passing_7(type) (type)(p8)
    
    #endif /* SNC */
    
    /*
     * Macros used for register passing output arguments.
     */
    #define REG_PASS_SYS_EVENT_QUEUE_RECEIVE      \
    event->source = register_passing_1(uint64_t); \
    event->data1  = register_passing_2(uint64_t); \
    event->data2  = register_passing_3(uint64_t); \
    event->data3  = register_passing_4(uint64_t)
    
    
    #endif /* __SYS_SYS_SYSCALL_H__ */
    well wher would the ps3 use an algorithm mmmhhhhh. i'm not that good at math anybody ? what does the algorithm lead to?

    found something more, algorithm for the header in the compiler.. not exactly sure what it means:
    Code:
    // algorithm standard header
    #ifndef _ALGORITHM_
    #define _ALGORITHM_
    #include <memory>
    _STD_BEGIN
    
    		// COMMON SORT PARAMETERS
    const int _ISORT_MAX = 32;	// maximum size for insertion sort
    
    		// TEMPLATE FUNCTION for_each
    template<class _InIt,
    	class _Fn1> inline
    	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
    	{	// perform function for each element
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Func);
    	for (; _First != _Last; ++_First)
    		_Func(*_First);
    	return (_Func);
    	}
    
    		// TEMPLATE FUNCTION find
    template<class _InIt,
    	class _Ty> inline
    	_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
    	{	// find first matching _Val
    	_DEBUG_RANGE(_First, _Last);
    	for (; _First != _Last; ++_First)
    		if (*_First == _Val)
    			break;
    	return (_First);
    	}
    
    inline const char *find(const char *_First, const char *_Last, int _Val)
    	{	// find first char that matches _Val
    	_DEBUG_RANGE(_First, _Last);
    	_First = (const char *)_CSTD memchr(_First, _Val, _Last - _First);
    	return (_First == 0 ? _Last : _First);
    	}
    
    inline const signed char *find(const signed char *_First,
    	const signed char *_Last, int _Val)
    	{	// find first signed char that matches _Val
    	_DEBUG_RANGE(_First, _Last);
    	_First = (const signed char *)_CSTD memchr(_First, _Val,
    		_Last - _First);
    	return (_First == 0 ? _Last : _First);
    	}
    
    inline const unsigned char *find(const unsigned char *_First,
    	const unsigned char *_Last, int _Val)
    	{	// find first unsigned char that matches _Val
    	_DEBUG_RANGE(_First, _Last);
    	_First = (const unsigned char *)_CSTD memchr(_First, _Val,
    		_Last - _First);
    	return (_First == 0 ? _Last : _First);
    	}
    
    		// TEMPLATE FUNCTION find_if
    template<class _InIt,
    	class _Pr> inline
    	_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
    	{	// find first satisfying _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	for (; _First != _Last; ++_First)
    		if (_Pred(*_First))
    			break;
    	return (_First);
    	}
    
    		// TEMPLATE FUNCTION adjacent_find
    template<class _FwdIt> inline
    	_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
    	{	// find first matching successor
    	_DEBUG_RANGE(_First, _Last);
    	for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
    		if (*_Firstb == *_First)
    			return (_Firstb);
    	return (_Last);
    	}
    
    		// TEMPLATE FUNCTION adjacent_find WITH PRED
    template<class _FwdIt,
    	class _Pr> inline
    	_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    	{	// find first satisfying _Pred with successor
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
    		if (_Pred(*_Firstb, *_First))
    			return (_Firstb);
    	return (_Last);
    	}
    
    		// TEMPLATE FUNCTION count
    template<class _InIt,
    	class _Ty> inline
    	typename iterator_traits<_InIt>::difference_type
    		count(_InIt _First, _InIt _Last, const _Ty& _Val)
    	{	// count elements that match _Val
    	_DEBUG_RANGE(_First, _Last);
    	typename iterator_traits<_InIt>::difference_type _Count = 0;
    
    	for (; _First != _Last; ++_First)
    		if (*_First == _Val)
    			++_Count;
    	return (_Count);
    	}
    
    		// TEMPLATE FUNCTION count_if
    template<class _InIt,
    	class _Pr> inline
    	typename iterator_traits<_InIt>::difference_type
    		count_if(_InIt _First, _InIt _Last, _Pr _Pred)
    	{	// count elements satisfying _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	typename iterator_traits<_InIt>::difference_type _Count = 0;
    
    	for (; _First != _Last; ++_First)
    		if (_Pred(*_First))
    			++_Count;
    	return (_Count);
    	}
    
     #if _HAS_TRADITIONAL_STL
    		// TEMPLATE FUNCTION count
    template<class _InIt,
    	class _Ty,
    	class _Diff> inline
    	void count(_InIt _First, _InIt _Last, const _Ty& _Val, _Diff &_Ans)
    	{	// count elements that match _Val
    	_DEBUG_RANGE(_First, _Last);
    	_Diff _Count = 0;
    
    	for (; _First != _Last; ++_First)
    		if (*_First == _Val)
    			++_Count;
    	_Ans = _Count;
    	}
    
    		// TEMPLATE FUNCTION count_if
    template<class _InIt,
    	class _Pr,
    	class _Diff> inline
    	void count_if(_InIt _First, _InIt _Last, _Pr _Pred, _Diff &_Ans)
    	{	// count elements satisfying _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_Diff _Count = 0;
    
    	for (; _First != _Last; ++_First)
    		if (_Pred(*_First))
    			++_Count;
    	_Ans = _Count;
    	}
     #endif /* _HAS_TRADITIONAL_STL */
    
    		// TEMPLATE FUNCTION search
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Diff1,
    	class _Diff2> inline
    	_FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
    	{	// find first [_First2, _Last2) match
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_Diff1 _Count1 = 0;
    	_Distance(_First1, _Last1, _Count1);
    	_Diff2 _Count2 = 0;
    	_Distance(_First2, _Last2, _Count2);
    
    	for (; _Count2 <= _Count1; ++_First1, --_Count1)
    		{	// room for match, try it
    		_FwdIt1 _Mid1 = _First1;
    		for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
    			if (_Mid2 == _Last2)
    				return (_First1);
    			else if (!(*_Mid1 == *_Mid2))
    				break;
    		}
    	return (_Last1);
    	}
    
    template<class _FwdIt1,
    	class _FwdIt2> inline
    	_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2)
    	{	// find first [_First2, _Last2) match
    	return (_Search(_First1, _Last1, _First2, _Last2,
    		_Dist_type(_First1), _Dist_type(_First2)));
    	}
    
    		// TEMPLATE FUNCTION search WITH PRED
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Diff1,
    	class _Diff2,
    	class _Pr> inline
    	_FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
    	{	// find first [_First2, _Last2) satisfying _Pred
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_DEBUG_POINTER(_Pred);
    	_Diff1 _Count1 = 0;
    	_Distance(_First1, _Last1, _Count1);
    	_Diff2 _Count2 = 0;
    	_Distance(_First2, _Last2, _Count2);
    
    	for (; _Count2 <= _Count1; ++_First1, --_Count1)
    		{	// room for match, try it
    		_FwdIt1 _Mid1 = _First1;
    		for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
    			if (_Mid2 == _Last2)
    				return (_First1);
    			else if (!_Pred(*_Mid1, *_Mid2))
    				break;
    		}
    	return (_Last1);
    	}
    
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Pr> inline
    	_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
    	{	// find first [_First2, _Last2) satisfying _Pred
    	return (_Search(_First1, _Last1, _First2, _Last2, _Pred,
    		_Dist_type(_First1), _Dist_type(_First2)));
    	}
    
    		// TEMPLATE FUNCTION search_n
    template<class _FwdIt1,
    	class _Diff2,
    	class _Ty,
    	class _Diff1> inline
    	_FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_Diff2 _Count, const _Ty& _Val, _Diff1 *)
    	{	// find first _Count * _Val match
    	_DEBUG_RANGE(_First1, _Last1);
    	_Diff1 _Count1 = 0;
    	_Distance(_First1, _Last1, _Count1);
    
    	for (; _Count <= _Count1; ++_First1, --_Count1)
    		{	// room for match, try it
    		_FwdIt1 _Mid1 = _First1;
    		for (_Diff2 _Count2 = _Count; ; ++_Mid1, --_Count2)
    			if (_Count2 == 0)
    				return (_First1);
    			else if (!(*_Mid1 == _Val))
    				break;
    		}
    	return (_Last1);
    	}
    
    template<class _FwdIt1,
    	class _Diff2,
    	class _Ty> inline
    	_FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_Diff2 _Count, const _Ty& _Val)
    	{	// find first _Count * _Val match
    	return (_Search_n(_First1, _Last1, _Count, _Val, _Dist_type(_First1)));
    	}
    
    		// TEMPLATE FUNCTION search_n WITH PRED
    template<class _FwdIt1,
    	class _Diff2,
    	class _Ty,
    	class _Diff1,
    	class _Pr> inline
    	_FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_Diff2 _Count, const _Ty& _Val, _Pr _Pred, _Diff1 *)
    	{	// find first _Count * _Val satisfying _Pred
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_POINTER(_Pred);
    	_Diff1 _Count1 = 0;
    	_Distance(_First1, _Last1, _Count1);
    
    	for (; _Count <= _Count1; ++_First1, --_Count1)
    		{	// room for match, try it
    		_FwdIt1 _Mid1 = _First1;
    		for (_Diff2 _Count2 = _Count; ; ++_Mid1, --_Count2)
    			if (_Count2 == 0)
    				return (_First1);
    			else if (!_Pred(*_Mid1, _Val))
    				break;
    		}
    	return (_Last1);
    	}
    
    template<class _FwdIt1,
    	class _Diff2,
    	class _Ty,
    	class _Pr> inline
    	_FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_Diff2 _Count, const _Ty& _Val, _Pr _Pred)
    	{	// find first _Count * _Val satisfying _Pred
    	return (_Search_n(_First1, _Last1,
    		_Count, _Val, _Pred, _Dist_type(_First1)));
    	}
    
    		// TEMPLATE FUNCTION find_end
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Diff1,
    	class _Diff2> inline
    	_FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
    	{	// find last [_First2, _Last2) match
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_Diff1 _Count1 = 0;
    	_Distance(_First1, _Last1, _Count1);
    	_Diff2 _Count2 = 0;
    	_Distance(_First2, _Last2, _Count2);
    	_FwdIt1 _Ans = _Last1;
    
    	if (0 < _Count2)
    		for (; _Count2 <= _Count1; ++_First1, --_Count1)
    			{	// room for match, try it
    			_FwdIt1 _Mid1 = _First1;
    			for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
    				if (!(*_Mid1 == *_Mid2))
    					break;
    				else if (++_Mid2 == _Last2)
    					{	// potential answer, save it
    					_Ans = _First1;
    					break;
    					}
    			}
    	return (_Ans);
    	}
    
    template<class _FwdIt1,
    	class _FwdIt2> inline
    	_FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2)
    	{	// find last [_First2, _Last2) match
    	return (_Find_end(_First1, _Last1, _First2, _Last2,
    		_Dist_type(_First1), _Dist_type(_First2)));
    	}
    
    		// TEMPLATE FUNCTION find_end WITH PRED
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Diff1,
    	class _Diff2,
    	class _Pr> inline
    	_FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
    	{	// find last [_First2, _Last2) satisfying _Pred
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_DEBUG_POINTER(_Pred);
    	_Diff1 _Count1 = 0;
    	_Distance(_First1, _Last1, _Count1);
    	_Diff2 _Count2 = 0;
    	_Distance(_First2, _Last2, _Count2);
    	_FwdIt1 _Ans = _Last1;
    
    	if (0 < _Count2)
    		for (; _Count2 <= _Count1; ++_First1, --_Count1)
    			{	// room for match, try it
    			_FwdIt1 _Mid1 = _First1;
    			for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
    				if (!_Pred(*_Mid1, *_Mid2))
    					break;
    				else if (++_Mid2 == _Last2)
    					{	// potential answer, save it
    					_Ans = _First1;
    					break;
    					}
    			}
    	return (_Ans);
    	}
    
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Pr> inline
    	_FwdIt1 find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
    	{	// find last [_First2, _Last2) satisfying _Pred
    	return (_Find_end(_First1, _Last1, _First2, _Last2, _Pred,
    		_Dist_type(_First1), _Dist_type(_First2)));
    	}
    
    		// TEMPLATE FUNCTION find_first_of
    template<class _FwdIt1,
    	class _FwdIt2> inline
    	_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2)
    	{	// look for one of [_First2, _Last2) that matches element
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	for (; _First1 != _Last1; ++_First1)
    		for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
    			if (*_First1 == *_Mid2)
    				return (_First1);
    	return (_First1);
    	}
    
    		// TEMPLATE FUNCTION find_first_of WITH PRED
    template<class _FwdIt1,
    	class _FwdIt2,
    	class _Pr> inline
    	_FwdIt1 find_first_of(_FwdIt1 _First1, _FwdIt1 _Last1,
    		_FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred)
    	{	// look for one of [_First2, _Last2) satisfying _Pred with element
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_DEBUG_POINTER(_Pred);
    	for (; _First1 != _Last1; ++_First1)
    		for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
    			if (_Pred(*_First1, *_Mid2))
    				return (_First1);
    	return (_First1);
    	}
    
    		// TEMPLATE FUNCTION iter_swap
    template<class _FwdIt1,
    	class _FwdIt2> inline
    	void iter_swap(_FwdIt1 _Left, _FwdIt2 _Right)
    	{	// swap *_Left and *_Right
    	_STD swap(*_Left, *_Right);
    	}
    
    		// TEMPLATE FUNCTION swap_ranges
    template<class _FwdIt1,
    	class _FwdIt2> inline
    	_FwdIt2 swap_ranges(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2)
    	{	// swap [_First1, _Last1) with [_First2, ...)
    	_DEBUG_RANGE(_First1, _Last1);
    	for (; _First1 != _Last1; ++_First1, ++_First2)
    		_STD iter_swap(_First1, _First2);
    	return (_First2);
    	}
    
    		// TEMPLATE FUNCTION transform WITH UNARY OP
    template<class _InIt,
    	class _OutIt,
    	class _Fn1> inline
    	_OutIt transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
    	{	// transform [_First, _Last) with _Func
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Func);
    	for (; _First != _Last; ++_First, ++_Dest)
    		*_Dest = _Func(*_First);
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION transform WITH BINARY OP
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt,
    	class _Fn2> inline
    	_OutIt transform(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2,
    		_OutIt _Dest, _Fn2 _Func)
    	{	// transform [_First1, _Last1) and [_First2, _Last2) with _Func
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Func);
    	for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest)
    		*_Dest = _Func(*_First1, *_First2);
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION replace
    template<class _FwdIt,
    	class _Ty> inline
    	void replace(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Oldval, const _Ty& _Newval)
    	{	// replace each matching _Oldval with _Newval
    	_DEBUG_RANGE(_First, _Last);
    	for (; _First != _Last; ++_First)
    		if (*_First == _Oldval)
    			*_First = _Newval;
    	}
    
    		// TEMPLATE FUNCTION replace_if
    template<class _FwdIt,
    	class _Pr,
    	class _Ty> inline
    	void replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)
    	{	// replace each satisfying _Pred with _Val
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	for (; _First != _Last; ++_First)
    		if (_Pred(*_First))
    			*_First = _Val;
    	}
    
    		// TEMPLATE FUNCTION replace_copy
    template<class _InIt,
    	class _OutIt,
    	class _Ty> inline
    	_OutIt replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
    		const _Ty& _Oldval, const _Ty& _Newval)
    	{	// copy replacing each matching _Oldval with _Newval
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	for (; _First != _Last; ++_First, ++_Dest)
    		*_Dest = *_First == _Oldval ? _Newval : *_First;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION replace_copy_if
    template<class _InIt,
    	class _OutIt,
    	class _Pr,
    	class _Ty> inline
    	_OutIt replace_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest,
    		_Pr _Pred, const _Ty& _Val)
    	{	// copy replacing each satisfying _Pred with _Val
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Pred);
    	for (; _First != _Last; ++_First, ++_Dest)
    		*_Dest = _Pred(*_First) ? _Val : *_First;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION generate
    template<class _FwdIt,
    	class _Fn0> inline
    	void generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
    	{	// replace [_First, _Last) with _Func()
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Func);
    	for (; _First != _Last; ++_First)
    		*_First = _Func();
    	}
    
    		// TEMPLATE FUNCTION generate_n
    template<class _OutIt,
    	class _Diff,
    	class _Fn0> inline
    	void generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
    	{	// replace [_Dest, _Dest + _Count) with _Func()
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Func);
    	for (; 0 < _Count; --_Count, ++_Dest)
    		*_Dest = _Func();
    	}
    
    		// TEMPLATE FUNCTION remove_copy
    template<class _InIt,
    	class _OutIt,
    	class _Ty> inline
    	_OutIt remove_copy(_InIt _First, _InIt _Last,
    		_OutIt _Dest, const _Ty& _Val)
    	{	// copy omitting each matching _Val
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	for (; _First != _Last; ++_First)
    		if (!(*_First == _Val))
    			*_Dest++ = *_First;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION remove_copy_if
    template<class _InIt,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt remove_copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
    	{	// copy omitting each element satisfying _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Pred);
    	for (; _First != _Last; ++_First)
    		if (!_Pred(*_First))
    			*_Dest++ = *_First;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION remove
    template<class _FwdIt,
    	class _Ty> inline
    	_FwdIt remove(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    	{	// remove each matching _Val
    	_First = find(_First, _Last, _Val);
    	if (_First == _Last)
    		return (_First);	// empty sequence, all done
    	else
    		{	// nonempty sequence, worth doing
    		_FwdIt _First1 = _First;
    		return (_STD remove_copy(++_First1, _Last, _First, _Val));
    		}
    	}
    
    		// TEMPLATE FUNCTION remove_if
    template<class _FwdIt,
    	class _Pr> inline
    	_FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    	{	// remove each satisfying _Pred
    	_First = _STD find_if(_First, _Last, _Pred);
    	if (_First == _Last)
    		return (_First);	// empty sequence, all done
    	else
    		{	// nonempty sequence, worth doing
    		_FwdIt _First1 = _First;
    		return (_STD remove_copy_if(++_First1, _Last, _First, _Pred));
    		}
    	}
    
    		// TEMPLATE FUNCTION unique
    template<class _FwdIt> inline
    	_FwdIt unique(_FwdIt _First, _FwdIt _Last)
    	{	// remove each matching previous
    	_DEBUG_RANGE(_First, _Last);
    	for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
    		if (*_Firstb == *_First)
    			{	// copy down
    			for (; ++_First != _Last; )
    				if (!(*_Firstb == *_First))
    					*++_Firstb = *_First;
    			return (++_Firstb);
    			}
    	return (_Last);
    	}
    
    		// TEMPLATE FUNCTION unique WITH PRED
    template<class _FwdIt,
    	class _Pr> inline
    	_FwdIt unique(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    	{	// remove each satisfying _Pred with previous
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; )
    		if (_Pred(*_Firstb, *_First))
    			{	// copy down
    			for (; ++_First != _Last; )
    				if (!_Pred(*_Firstb, *_First))
    					*++_Firstb = *_First;
    			return (++_Firstb);
    			}
    	return (_Last);
    	}
    
    		// TEMPLATE FUNCTION unique_copy
    template<class _InIt,
    	class _OutIt,
    	class _Ty> inline
    	_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Ty *)
    	{	// copy compressing pairs that match, input iterators
    	_DEBUG_POINTER(_Dest);
    	_Ty _Val = *_First;
    
    	for (*_Dest++ = _Val; ++_First != _Last; )
    		if (!(_Val == *_First))
    			_Val = *_First, *_Dest++ = _Val;
    	return (_Dest);
    	}
    
    template<class _InIt,
    	class _OutIt> inline
    	_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest,
    		input_iterator_tag)
    	{	// copy compressing pairs that match, input iterators
    	return (_Unique_copy(_First, _Last, _Dest, _Val_type(_First)));
    	}
    
    template<class _FwdIt,
    	class _OutIt> inline
    	_OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest,
    		forward_iterator_tag)
    	{	// copy compressing pairs that match, forward iterators
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	_FwdIt _Firstb = _First;
    	for (*_Dest++ = *_Firstb; ++_First != _Last; )
    		if (!(*_Firstb == *_First))
    			_Firstb = _First, *_Dest++ = *_Firstb;
    	return (_Dest);
    	}
    
    template<class _BidIt,
    	class _OutIt> inline
    	_OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest,
    		bidirectional_iterator_tag)
    	{	// copy compressing pairs that match, bidirectional iterators
    	return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag()));
    	}
    
    template<class _RanIt,
    	class _OutIt> inline
    	_OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest,
    		random_access_iterator_tag)
    	{	// copy compressing pairs that match, random-access iterators
    	return (_Unique_copy(_First, _Last, _Dest, forward_iterator_tag()));
    	}
    
    template<class _InIt,
    	class _OutIt> inline
    	_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest)
    	{	// copy compressing pairs that match
    	return (_First == _Last ? _Dest :
    		_Unique_copy(_First, _Last, _Dest, _Iter_cat(_First)));
    	}
    
    		// TEMPLATE FUNCTION unique_copy WITH PRED
    template<class _InIt,
    	class _OutIt,
    	class _Ty,
    	class _Pr> inline
    	_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
    		_Ty *)
    	{	// copy compressing pairs satisfying _Pred, input iterators
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Pred);
    	_Ty _Val = *_First;
    
    	for (*_Dest++ = _Val; ++_First != _Last; )
    		if (!_Pred(_Val, *_First))
    			_Val = *_First, *_Dest++ = _Val;
    	return (_Dest);
    	}
    
    template<class _InIt,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt _Unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred,
    		input_iterator_tag)
    	{	// copy compressing pairs satisfying _Pred, input iterators
    	return (_Unique_copy(_First, _Last, _Dest, _Pred, _Val_type(_First)));
    	}
    
    template<class _FwdIt,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt _Unique_copy(_FwdIt _First, _FwdIt _Last, _OutIt _Dest, _Pr _Pred,
    		forward_iterator_tag)
    	{	// copy compressing pairs satisfying _Pred, forward iterators
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	_DEBUG_POINTER(_Pred);
    	_FwdIt _Firstb = _First;
    
    	for (*_Dest++ = *_Firstb; ++_First != _Last; )
    		if (!_Pred(*_Firstb, *_First))
    			_Firstb = _First, *_Dest++ = *_Firstb;
    	return (_Dest);
    	}
    
    template<class _BidIt,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt _Unique_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest, _Pr _Pred,
    		bidirectional_iterator_tag)
    	{	// copy compressing pairs satisfying _Pred, bidirectional iterators
    	return (_Unique_copy(_First, _Last, _Dest, _Pred,
    		forward_iterator_tag()));
    	}
    
    template<class _RanIt,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt _Unique_copy(_RanIt _First, _RanIt _Last, _OutIt _Dest, _Pr _Pred,
    		random_access_iterator_tag)
    	{	// copy compressing pairs satisfying _Pred, random-access iterators
    	return (_Unique_copy(_First, _Last, _Dest, _Pred,
    		forward_iterator_tag()));
    	}
    
    template<class _InIt,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt unique_copy(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred)
    	{	// copy compressing pairs satisfying _Pred
    	return (_First == _Last ? _Dest
    		: _Unique_copy(_First, _Last, _Dest, _Pred, _Iter_cat(_First)));
    	}
    
    		// TEMPLATE FUNCTION reverse
    template<class _BidIt> inline
    	void _Reverse(_BidIt _First, _BidIt _Last, bidirectional_iterator_tag)
    	{	// reverse elements in [_First, _Last), bidirectional iterators
    	for (; _First != _Last && _First != --_Last; ++_First)
    		_STD iter_swap(_First, _Last);
    	}
    
    template<class _RanIt> inline
    	void _Reverse(_RanIt _First, _RanIt _Last, random_access_iterator_tag)
    	{	// reverse elements in [_First, _Last), random-access iterators
    	_DEBUG_RANGE(_First, _Last);
    	for (; _First < _Last; ++_First)
    		_STD iter_swap(_First, --_Last);
    	}
    
    template<class _BidIt> inline
    	void reverse(_BidIt _First, _BidIt _Last)
    	{	// reverse elements in [_First, _Last)
    	_Reverse(_First, _Last, _Iter_cat(_First));
    	}
    
    		// TEMPLATE FUNCTION reverse_copy
    template<class _BidIt,
    	class _OutIt> inline
    	_OutIt reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)
    	{	// copy reversing elements in [_First, _Last)
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Dest);
    	for (; _First != _Last; ++_Dest)
    		*_Dest = *--_Last;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION rotate
    template<class _FwdIt> inline
    	void _Rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last,
    		forward_iterator_tag)
    	{	// rotate [_First, _Last), forward iterators
    	for (_FwdIt _Next = _Mid; ; )
    		{	// swap [_First, ...) into place
    		_STD iter_swap(_First, _Next);
    		if (++_First == _Mid)
    			if (++_Next == _Last)
    				break;	// done, quit
    			else
    				_Mid = _Next;	// mark end of next interval
    		else if (++_Next == _Last)
    			_Next = _Mid;	// wrap to last end
    		}
    	}
    
    template<class _BidIt> inline
    	void _Rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
    		bidirectional_iterator_tag)
    	{	// rotate [_First, _Last), bidirectional iterators
    	_STD reverse(_First, _Mid);
    	_STD reverse(_Mid, _Last);
    	_STD reverse(_First, _Last);
    	}
    
    template<class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Diff *, _Ty *)
    	{	// rotate [_First, _Last), random-access iterators
    	_DEBUG_RANGE(_First, _Mid);
    	_DEBUG_RANGE(_Mid, _Last);
    	_Diff _Shift = _Mid - _First;
    	_Diff _Count = _Last - _First;
    
    	for (_Diff _Factor = _Shift; _Factor != 0; )
    		{	// find subcycle count as GCD of shift count and length
    		_Diff _Tmp = _Count % _Factor;
    		_Count = _Factor, _Factor = _Tmp;
    		}
    
    	if (_Count < _Last - _First)
    		for (; 0 < _Count; --_Count)
    			{	// rotate each subcycle
    			_RanIt _Hole = _First + _Count;
    			_RanIt _Next = _Hole;
    			_Ty _Holeval = *_Hole;
    			_RanIt _Next1 = _Next + _Shift == _Last ? _First : _Next + _Shift;
    			while (_Next1 != _Hole)
    				{	// percolate elements back around subcycle
    				*_Next = *_Next1;
    				_Next = _Next1;
    				_Next1 = _Shift < _Last - _Next1 ? _Next1 + _Shift
    					: _First + (_Shift - (_Last - _Next1));
    				}
    			*_Next = _Holeval;
    			}
    	}
    
    template<class _RanIt> inline
    	void _Rotate(_RanIt _First, _RanIt _Mid, _RanIt _Last,
    			random_access_iterator_tag)
    	{	// rotate [_First, _Last), random-access iterators
    	_Rotate(_First, _Mid, _Last, _Dist_type(_First), _Val_type(_First));
    	}
    
    template<class _FwdIt> inline
    	void rotate(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last)
    	{	// rotate [_First, _Last)
    	if (_First != _Mid && _Mid != _Last)
    		_Rotate(_First, _Mid, _Last, _Iter_cat(_First));
    	}
    
    		// TEMPLATE FUNCTION rotate_copy
    template<class _FwdIt,
    	class _OutIt> inline
    	_OutIt rotate_copy(_FwdIt _First, _FwdIt _Mid, _FwdIt _Last, _OutIt _Dest)
    	{	// copy rotating [_First, _Last)
    	_Dest = _STD copy(_Mid, _Last, _Dest);
    	return (_STD copy(_First, _Mid, _Dest));
    	}
    
    		// TEMPLATE FUNCTION random_shuffle
    template<class _RanIt,
    	class _Diff> inline
    	void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *)
    	{	// shuffle [_First, _Last)
    	_DEBUG_RANGE(_First, _Last);
    	const int _RANDOM_BITS = 15;	// minimum random bits from rand()
    	const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1;
    
    	_RanIt _Next = _First;
    	for (unsigned long _Index = 2; ++_Next != _Last; ++_Index)
    		{	// assume unsigned long big enough for _Diff count
    		unsigned long _Rm = _RANDOM_MAX;
    		unsigned long _Rn = _CSTD rand() & _RANDOM_MAX;
    		for (; _Rm < _Index && _Rm != ~0UL;
    			_Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX)
    			_Rn = _Rn << _RANDOM_BITS | _RANDOM_MAX;	// build random value
    
    		_STD iter_swap(_Next, _First + _Diff(_Rn % _Index));	// swap a pair
    		}
    	}
    
    template<class _RanIt> inline
    	void random_shuffle(_RanIt _First, _RanIt _Last)
    	{	// shuffle [_First, _Last)
    	if (_First != _Last)
    		_Random_shuffle(_First, _Last, _Dist_type(_First));
    	}
    
    		// TEMPLATE FUNCTION random_shuffle WITH RANDOM FN
    template<class _RanIt,
    	class _Fn1,
    	class _Diff> inline
    	void _Random_shuffle(_RanIt _First, _RanIt _Last, _Fn1& _Func, _Diff *)
    	{	// shuffle nonempty [_First, _Last) using random function _Func
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Func);
    	_RanIt _Next = _First;
    
    	for (_Diff _Index = 2; ++_Next != _Last; ++_Index)
    		_STD iter_swap(_Next, _First + _Diff(_Func(_Index)));
    	}
    
    template<class _RanIt,
    	class _Fn1> inline
    	void random_shuffle(_RanIt _First, _RanIt _Last, _Fn1& _Func)
    	{	// shuffle [_First, _Last) using random function _Func
    	if (_First != _Last)
    		_Random_shuffle(_First, _Last, _Func, _Dist_type(_First));
    	}
    
    		// TEMPLATE FUNCTION partition
    template<class _BidIt,
    	class _Pr> inline
    	_BidIt partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
    	{	// move elements satisfying _Pred to beginning of sequence
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	for (; ; ++_First)
    		{	// find any out-of-order pair
    		for (; _First != _Last && _Pred(*_First); ++_First)
    			;	// skip in-place elements at beginning
    		if (_First == _Last)
    			break;	// done
    
    		for (; _First != --_Last && !_Pred(*_Last); )
    			;	// skip in-place elements at end
    		if (_First == _Last)
    			break;	// done
    
    		_STD iter_swap(_First, _Last);	// swap out-of-place pair and loop
    		}
    	return (_First);
    	}
    
    		// TEMPLATE FUNCTION stable_partition
    template<class _BidIt,
    	class _Pr,
    	class _Diff,
    	class _Ty> inline
    	_BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
    		_Diff _Count, _Temp_iterator<_Ty>& _Tempbuf)
    	{	// partition preserving order of equivalents, using _Pred
    	if (_Count == 1)
    		return (_Pred(*_First) ? _Last : _First);
    	else if (_Count <= _Tempbuf._Maxlen())
    		{	// temp buffer big enough, copy right partition out and back
    		_BidIt _Next = _First;
    		for (_Tempbuf._Init(); _First != _Last; ++_First)
    			if (_Pred(*_First))
    				*_Next++ = *_First;
    			else
    				*_Tempbuf++ = *_First;
    
    		_STD copy(_Tempbuf._First(), _Tempbuf._Last(), _Next);	// copy back
    		return (_Next);
    		}
    	else
    		{	// temp buffer not big enough, divide and conquer
    		_BidIt _Mid = _First;
    		_STD advance(_Mid, _Count / 2);
    
    		_BidIt _Left = _Stable_partition(_First, _Mid, _Pred,
    			_Count / 2, _Tempbuf);	// form L1R1 in left half
    		_BidIt _Right = _Stable_partition(_Mid, _Last, _Pred,
    			_Count - _Count / 2, _Tempbuf);	// form L2R2 in right half
    
    		_Diff _Count1 = 0;
    		_Distance(_Left, _Mid, _Count1);
    		_Diff _Count2 = 0;
    		_Distance(_Mid, _Right, _Count2);
    
    		return (_Buffered_rotate(_Left, _Mid, _Right,
    			_Count1, _Count2, _Tempbuf));	// rotate L1R1L2R2 to L1L2R1R2
    		}
    	}
    
    template<class _BidIt,
    	class _Pr,
    	class _Diff,
    	class _Ty> inline
    	_BidIt _Stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
    		_Diff *, _Ty *)
    	{	// partition preserving order of equivalents, using _Pred
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    	_Temp_iterator<_Ty> _Tempbuf(_Count);
    	return (_Stable_partition(_First, _Last, _Pred, _Count, _Tempbuf));
    	}
    
    template<class _BidIt,
    	class _Pr> inline
    	_BidIt stable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred)
    	{	// partition preserving order of equivalents, using _Pred
    	return (_First == _Last ? _First : _Stable_partition(_First, _Last, _Pred,
    		_Dist_type(_First), _Val_type(_First)));
    	}
    
     #if defined(_HAS_ITERATOR_DEBUGGING)
    		// TEMPLATE FUNCTION _Debug_heap
    template<class _RanIt,
    	class _Diff> inline
    	void _Debug_heap(_RanIt _First, _RanIt _Last, _Diff *)
    	{	// test if range is a heap ordered by operator<
    	_DEBUG_RANGE(_First, _Last);
    	_Diff _Size = _Last - _First;
    
    	if (2 <= _Size)
    		for (_Diff _Off = 0; ++_Off < _Size; )
    			if (_DEBUG_LT(*(_First + (_Off - 1) / 2), *(_First + _Off)))
    				_DEBUG_ERROR("invalid heap");
    	}
    
    		// TEMPLATE FUNCTION _Debug_heap WITH PRED
    template<class _RanIt,
    	class _Diff,
    	class _Pr> inline
    	void _Debug_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *)
    	{	// test if range is a heap ordered by _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_Diff _Size = _Last - _First;
    
    	if (2 <= _Size)
    		for (_Diff _Off = 0; ++_Off < _Size; )
    			if (_DEBUG_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
    				*(_First + _Off)))
    				_DEBUG_ERROR("invalid heap");
    	}
    
     #define _DEBUG_HEAP(first, last)	\
    	_Debug_heap(first, last, _Dist_type(first))
     #define _DEBUG_HEAP_PRED(first, last, pred)	\
    	_Debug_heap(first, last, pred, _Dist_type(first))
    
     #else /* _HAS_ITERATOR_DEBUGGING */
     #define _DEBUG_HEAP(first, last)
     #define _DEBUG_HEAP_PRED(first, last, pred)
     #endif /* _HAS_ITERATOR_DEBUGGING */
    
    		// TEMPLATE FUNCTION push_heap
    template<class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	void _Push_heap(_RanIt _First, _Diff _Hole,
    		_Diff _Top, _Ty _Val)
    	{	// percolate _Hole to _Top or where _Val belongs, using operator<
    	for (_Diff _Idx = (_Hole - 1) / 2;
    		_Top < _Hole && _DEBUG_LT(*(_First + _Idx), _Val);
    		_Idx = (_Hole - 1) / 2)
    		{	// move _Hole up to parent
    		*(_First + _Hole) = *(_First + _Idx);
    		_Hole = _Idx;
    		}
    
    	*(_First + _Hole) = _Val;	// drop _Val into final hole
    	}
    
    template<class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	void _Push_heap_0(_RanIt _First, _RanIt _Last, _Diff *, _Ty *)
    	{	// push *_Last onto heap at [_First, _Last), using operator<
    	_DEBUG_HEAP(_First, _Last);
    	_Diff _Count = _Last - _First;
    	if (0 < _Count)
    		_Push_heap(_First, _Count, _Diff(0), _Ty(*_Last));
    	}
    
    template<class _RanIt> inline
    	void push_heap(_RanIt _First, _RanIt _Last)
    	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using operator<
    
     #if defined(_HAS_ITERATOR_DEBUGGING)
    	if (_First == _Last)
    		_DEBUG_ERROR("empty push_heap sequence");
    	else
    
     #else /* _HAS_ITERATOR_DEBUGGING */
    	if (_First != _Last)
     #endif /* _HAS_ITERATOR_DEBUGGING */
    
    		_Push_heap_0(_First, --_Last,
    			_Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION push_heap WITH PRED
    template<class _RanIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Push_heap(_RanIt _First, _Diff _Hole,
    		_Diff _Top, _Ty _Val, _Pr _Pred)
    	{	// percolate _Hole to _Top or where _Val belongs, using operator<
    	for (_Diff _Idx = (_Hole - 1) / 2;
    		_Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val);
    		_Idx = (_Hole - 1) / 2)
    		{	// move _Hole up to parent
    		*(_First + _Hole) = *(_First + _Idx);
    		_Hole = _Idx;
    		}
    
    	*(_First + _Hole) = _Val;	// drop _Val into final hole
    	}
    
    template<class _RanIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Push_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
    	{	// push *_Last onto heap at [_First, _Last), using _Pred
    	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
    	_Diff _Count = _Last - _First;
    	if (0 < _Count)
    		_Push_heap(_First, _Count, _Diff(0), _Ty(*_Last), _Pred);
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
    	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
    
     #if defined(_HAS_ITERATOR_DEBUGGING)
    	if (_First == _Last)
    		_DEBUG_ERROR("empty push_heap sequence");
    	else
    
     #else /* _HAS_ITERATOR_DEBUGGING */
    	if (_First != _Last)
     #endif /* _HAS_ITERATOR_DEBUGGING */
    
    		_Push_heap_0(_First, --_Last, _Pred,
    			_Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION pop_heap
    template<class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom, _Ty _Val)
    	{	// percolate _Hole to _Bottom, then push _Val, using operator<
    	_Diff _Top = _Hole;
    	_Diff _Idx = 2 * _Hole + 2;
    
    	for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
    		{	// move _Hole down to larger child
    		if (_DEBUG_LT(*(_First + _Idx), *(_First + (_Idx - 1))))
    			--_Idx;
    		*(_First + _Hole) = *(_First + _Idx), _Hole = _Idx;
    		}
    
    	if (_Idx == _Bottom)
    		{	// only child at bottom, move _Hole down to it
    		*(_First + _Hole) = *(_First + (_Bottom - 1));
    		_Hole = _Bottom - 1;
    		}
    	_Push_heap(_First, _Hole, _Top, _Val);
    	}
    
    template<class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	void _Pop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
    		_Ty _Val, _Diff *)
    	{	// pop *_First to *_Dest and reheap, using operator<
    	*_Dest = *_First;
    	_Adjust_heap(_First, _Diff(0), _Diff(_Last - _First), _Val);
    	}
    
    template<class _RanIt,
    	class _Ty> inline
    	void _Pop_heap_0(_RanIt _First, _RanIt _Last, _Ty *)
    	{	// pop *_First to *(_Last - 1) and reheap, using operator<
    	_Pop_heap(_First, _Last - 1, _Last - 1,
    		_Ty(*(_Last - 1)), _Dist_type(_First));
    	}
    
    template<class _RanIt> inline
    	void pop_heap(_RanIt _First, _RanIt _Last)
    	{	// pop *_First to *(_Last - 1) and reheap, using operator<
    	_DEBUG_HEAP(_First, _Last);
    	if (1 < _Last - _First)
    		_Pop_heap_0(_First, _Last, _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION pop_heap WITH PRED
    template<class _RanIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom,
    		_Ty _Val, _Pr _Pred)
    	{	// percolate _Hole to _Bottom, then push _Val, using _Pred
    	_Diff _Top = _Hole;
    	_Diff _Idx = 2 * _Hole + 2;
    
    	for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
    		{	// move _Hole down to larger child
    		if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1))))
    			--_Idx;
    		*(_First + _Hole) = *(_First + _Idx), _Hole = _Idx;
    		}
    
    	if (_Idx == _Bottom)
    		{	// only child at bottom, move _Hole down to it
    		*(_First + _Hole) = *(_First + (_Bottom - 1));
    		_Hole = _Bottom - 1;
    		}
    	_Push_heap(_First, _Hole, _Top, _Val, _Pred);
    	}
    
    template<class _RanIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Pop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
    		_Ty _Val, _Pr _Pred, _Diff *)
    	{	// pop *_First to *_Dest and reheap, using _Pred
    	*_Dest = *_First;
    	_Adjust_heap(_First, _Diff(0), _Diff(_Last - _First), _Val, _Pred);
    	}
    
    template<class _RanIt,
    	class _Ty,
    	class _Pr> inline
    	void _Pop_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Ty *)
    	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
    	_Pop_heap(_First, _Last - 1, _Last - 1,
    		_Ty(*(_Last - 1)), _Pred, _Dist_type(_First));
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
    	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
    	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
    	if (1 < _Last - _First)
    		_Pop_heap_0(_First, _Last, _Pred, _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION make_heap
    template<class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	void _Make_heap(_RanIt _First, _RanIt _Last, _Diff *, _Ty *)
    	{	// make nontrivial [_First, _Last) into a heap, using operator<
    	_Diff _Bottom = _Last - _First;
    
    	for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
    		{	// reheap top half, bottom to top
    		--_Hole;
    		_Adjust_heap(_First, _Hole, _Bottom, _Ty(*(_First + _Hole)));
    		}
    	}
    
    template<class _RanIt> inline
    	void make_heap(_RanIt _First, _RanIt _Last)
    	{	// make [_First, _Last) into a heap, using operator<
    	if (1 < _Last - _First)
    		_Make_heap(_First, _Last,
    			_Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION make_heap WITH PRED
    template<class _RanIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
    	{	// make nontrivial [_First, _Last) into a heap, using _Pred
    	_Diff _Bottom = _Last - _First;
    	for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
    		{	// reheap top half, bottom to top
    		--_Hole;
    		_Adjust_heap(_First, _Hole, _Bottom,
    			_Ty(*(_First + _Hole)), _Pred);
    		}
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
    	{	// make [_First, _Last) into a heap, using _Pred
    	if (1 < _Last - _First)
    		_Make_heap(_First, _Last, _Pred,
    			_Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION sort_heap
    template<class _RanIt> inline
    	void sort_heap(_RanIt _First, _RanIt _Last)
    	{	// order heap by repeatedly popping, using operator<
    	_DEBUG_HEAP(_First, _Last);
    	for (; 1 < _Last - _First; --_Last)
    		_STD pop_heap(_First, _Last);
    	}
    
    		// TEMPLATE FUNCTION sort_heap WITH PRED
    template<class _RanIt,
    	class _Pr> inline
    	void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
    	{	// order heap by repeatedly popping, using _Pred
    	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
    	for (; 1 < _Last - _First; --_Last)
    		_STD pop_heap(_First, _Last, _Pred);
    	}
    
    		// TEMPLATE FUNCTION lower_bound
    template<class _FwdIt,
    	class _Ty,
    	class _Diff> inline
    	_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
    	{	// find first element not before _Val, using operator<
    	_DEBUG_ORDER(_First, _Last);
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    
    	for (; 0 < _Count; )
    		{	// divide and conquer, find half that contains answer
    		_Diff _Count2 = _Count / 2;
    		_FwdIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (_DEBUG_LT(*_Mid, _Val))
    			_First = ++_Mid, _Count -= _Count2 + 1;
    		else
    			_Count = _Count2;
    		}
    	return (_First);
    	}
    
    template<class _FwdIt,
    	class _Ty> inline
    	_FwdIt lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    	{	// find first element not before _Val, using operator<
    	return (_Lower_bound(_First, _Last, _Val, _Dist_type(_First)));
    	}
    
    		// TEMPLATE FUNCTION lower_bound WITH PRED
    template<class _FwdIt,
    	class _Ty,
    	class _Diff,
    	class _Pr> inline
    	_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred, _Diff *)
    	{	// find first element not before _Val, using _Pred
    	_DEBUG_ORDER_PRED(_First, _Last, _Pred);
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    	for (; 0 < _Count; )
    		{	// divide and conquer, find half that contains answer
    		_Diff _Count2 = _Count / 2;
    		_FwdIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
    			_First = ++_Mid, _Count -= _Count2 + 1;
    		else
    			_Count = _Count2;
    		}
    	return (_First);
    	}
    
    template<class _FwdIt,
    	class _Ty,
    	class _Pr> inline
    	_FwdIt lower_bound(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred)
    	{	// find first element not before _Val, using _Pred
    	return (_Lower_bound(_First, _Last, _Val, _Pred, _Dist_type(_First)));
    	}
    
    		// TEMPLATE FUNCTION upper_bound
    template<class _FwdIt,
    	class _Ty,
    	class _Diff> inline
    	_FwdIt _Upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
    	{	// find first element that _Val is before, using operator<
    	_DEBUG_ORDER(_First, _Last);
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    	for (; 0 < _Count; )
    		{	// divide and conquer, find half that contains answer
    		_Diff _Count2 = _Count / 2;
    		_FwdIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (!_DEBUG_LT(_Val, *_Mid))
    			_First = ++_Mid, _Count -= _Count2 + 1;
    		else
    			_Count = _Count2;
    		}
    	return (_First);
    	}
    
    template<class _FwdIt,
    	class _Ty> inline
    	_FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    	{	// find first element that _Val is before, using operator<
    	return (_Upper_bound(_First, _Last, _Val, _Dist_type(_First)));
    	}
    
    		// TEMPLATE FUNCTION upper_bound WITH PRED
    template<class _FwdIt,
    	class _Ty,
    	class _Diff,
    	class _Pr> inline
    	_FwdIt _Upper_bound(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred, _Diff *)
    	{	// find first element that _Val is before, using _Pred
    	_DEBUG_ORDER_PRED(_First, _Last, _Pred);
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    	for (; 0 < _Count; )
    		{	// divide and conquer, find half that contains answer
    		_Diff _Count2 = _Count / 2;
    		_FwdIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (!_DEBUG_LT_PRED(_Pred, _Val, *_Mid))
    			_First = ++_Mid, _Count -= _Count2 + 1;
    		else
    			_Count = _Count2;
    		}
    	return (_First);
    	}
    
    template<class _FwdIt,
    	class _Ty,
    	class _Pr> inline
    	_FwdIt upper_bound(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred)
    	{	// find first element that _Val is before, using _Pred
    	return (_Upper_bound(_First, _Last, _Val, _Pred, _Dist_type(_First)));
    	}
    
    		// TEMPLATE FUNCTION equal_range
    template<class _FwdIt,
    	class _Ty,
    	class _Diff> inline
    	pair<_FwdIt, _FwdIt> _Equal_range(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Diff *)
    	{	// find range equivalent to _Val, using operator<
    	_DEBUG_ORDER(_First, _Last);
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    
    	for (; 0 < _Count; )
    		{	// divide and conquer, check midpoint
    		_Diff _Count2 = _Count / 2;
    		_FwdIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (_DEBUG_LT(*_Mid, _Val))
    			{	// range begins above _Mid, loop
    			_First = ++_Mid;
    			_Count -= _Count2 + 1;
    			}
    		else if (_Val < *_Mid)
    			_Count = _Count2;	// range in first half, loop
    		else
    			{	// range straddles mid, find each end and return
    			_FwdIt _First2 = lower_bound(_First, _Mid, _Val);
    			_STD advance(_First, _Count);
    			_FwdIt _Last2 = upper_bound(++_Mid, _First, _Val);
    			return (pair<_FwdIt, _FwdIt>(_First2, _Last2));
    			}
    		}
    
    	return (pair<_FwdIt, _FwdIt>(_First, _First));	// empty range
    	}
    
    template<class _FwdIt,
    	class _Ty> inline
    	pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val)
    	{	// find range equivalent to _Val, using operator<
    	return (_Equal_range(_First, _Last, _Val, _Dist_type(_First)));
    	}
    
    		// TEMPLATE FUNCTION equal_range WITH PRED
    template<class _FwdIt,
    	class _Ty,
    	class _Diff,
    	class _Pr> inline
    	pair<_FwdIt, _FwdIt> _Equal_range(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred, _Diff *)
    	{	// find range equivalent to _Val, using _Pred
    	_DEBUG_ORDER_PRED(_First, _Last, _Pred);
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    
    	for (; 0 < _Count; )
    		{	// divide and conquer, check midpoint
    		_Diff _Count2 = _Count / 2;
    		_FwdIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (_DEBUG_LT_PRED(_Pred, *_Mid, _Val))
    			{	// range begins above _Mid, loop
    			_First = ++_Mid;
    			_Count -= _Count2 + 1;
    			}
    		else if (_Pred(_Val, *_Mid))
    			_Count = _Count2;	// range in first half, loop
    		else
    			{	// range straddles _Mid, find each end and return
    			_FwdIt _First2 = lower_bound(_First, _Mid, _Val, _Pred);
    			_STD advance(_First, _Count);
    			_FwdIt _Last2 = upper_bound(++_Mid, _First, _Val, _Pred);
    			return (pair<_FwdIt, _FwdIt>(_First2, _Last2));
    			}
    		}
    
    	return (pair<_FwdIt, _FwdIt>(_First, _First));	// empty range
    	}
    
    template<class _FwdIt,
    	class _Ty,
    	class _Pr> inline
    	pair<_FwdIt, _FwdIt> equal_range(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred)
    	{	// find range equivalent to _Val, using _Pred
    	return (_Equal_range(_First, _Last, _Val, _Pred, _Dist_type(_First)));
    	}
    
    		// TEMPLATE FUNCTION binary_search
    template<class _FwdIt,
    	class _Ty> inline
    	bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    	{	// test if _Val equivalent to some element, using operator<
    	_First = _STD lower_bound(_First, _Last, _Val);
    	return (_First != _Last && !(_Val < *_First));
    	}
    
    		// TEMPLATE FUNCTION binary_search WITH PRED
    template<class _FwdIt,
    	class _Ty,
    	class _Pr> inline
    	bool binary_search(_FwdIt _First, _FwdIt _Last,
    		const _Ty& _Val, _Pr _Pred)
    	{	// test if _Val equivalent to some element, using _Pred
    	_First = _STD lower_bound(_First, _Last, _Val, _Pred);
    	return (_First != _Last && !_Pred(_Val, *_First));
    	}
    
    		// TEMPLATE FUNCTION merge
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt> inline
    	_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
    	{	// copy merging ranges, both using operator<
    	_DEBUG_ORDER(_First1, _Last1);
    	_DEBUG_ORDER(_First2, _Last2);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
    		if (_DEBUG_LT(*_First2, *_First1))
    			*_Dest = *_First2, ++_First2;
    		else
    			*_Dest = *_First1, ++_First1;
    
    	_Dest = _STD copy(_First1, _Last1, _Dest);	// copy any tail
    	return (_STD copy(_First2, _Last2, _Dest));
    	}
    
    		// TEMPLATE FUNCTION merge WITH PRED
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
    	{	//  copy merging ranges, both using _Pred
    	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
    	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
    		if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
    			*_Dest = *_First2, ++_First2;
    		else
    			*_Dest = *_First1, ++_First1;
    
    	_Dest = _STD copy(_First1, _Last1, _Dest);	// copy any tail
    	return (_STD copy(_First2, _Last2, _Dest));
    	}
    
    		// TEMPLATE FUNCTION inplace_merge
    template<class _BidIt,
    	class _Diff,
    	class _Ty> inline
    	_BidIt _Buffered_rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
    		_Diff _Count1, _Diff _Count2, _Temp_iterator<_Ty>& _Tempbuf)
    	{	// rotate [_First, _Last) using temp buffer
    	if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
    		{	// buffer left partition, then copy parts
    		_STD copy(_First, _Mid, _Tempbuf._Init());
    		_STD copy(_Mid, _Last, _First);
    		return (_STD copy_backward(_Tempbuf._First(), _Tempbuf._Last(),
    			_Last));
    		}
    	else if (_Count2 <= _Tempbuf._Maxlen())
    		{	// buffer right partition, then copy parts
    		_STD copy(_Mid, _Last, _Tempbuf._Init());
    		_STD copy_backward(_First, _Mid, _Last);
    		return (_STD copy(_Tempbuf._First(), _Tempbuf._Last(), _First));
    		}
    	else
    		{	// buffer too small, rotate in place
    		_STD rotate(_First, _Mid, _Last);
    		_STD advance(_First, _Count2);
    		return (_First);
    		}
    	}
    
    template<class _BidIt1,
    	class _BidIt2,
    	class _BidIt3> inline
    	_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
    		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
    	{	// merge backwards to _Dest, using operator<
    	for (; ; )
    		if (_First1 == _Last1)
    			return (_STD copy_backward(_First2, _Last2, _Dest));
    		else if (_First2 == _Last2)
    			return (_STD copy_backward(_First1, _Last1, _Dest));
    		else if (_DEBUG_LT(*--_Last2, *--_Last1))
    			*--_Dest = *_Last1, ++_Last2;
    		else
    			*--_Dest = *_Last2, ++_Last1;
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty> inline
    	void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
    		_Diff _Count1, _Diff _Count2,
    			_Temp_iterator<_Ty>& _Tempbuf)
    	{	// merge [_First, _Mid) with [_Mid, _Last), using operator<
    	if (_Count1 + _Count2 == 2)
    		{	// order two one-element partitions
    		if (_DEBUG_LT(*_Mid, *_First))
    			_STD iter_swap(_First, _Mid);
    		}
    	else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
    		{	// buffer left partition, then merge
    		_STD copy(_First, _Mid, _Tempbuf._Init());
    		_STD merge(_Tempbuf._First(), _Tempbuf._Last(), _Mid, _Last, _First);
    		}
    	else if (_Count2 <= _Tempbuf._Maxlen())
    		{	// buffer right partition, then merge
    		_STD copy(_Mid, _Last, _Tempbuf._Init());
    		_Merge_backward(_First, _Mid,
    			_Tempbuf._First(), _Tempbuf._Last(), _Last);
    		}
    	else
    		{	// buffer too small, divide and conquer
    		_BidIt _Firstn, _Lastn;
    		_Diff _Count1n, _Count2n;
    
    		if (_Count2 < _Count1)
    			{	// left larger, cut it in half and partition right to match
    			_Count1n = _Count1 / 2, _Count2n = 0;
    			_Firstn = _First;
    			_STD advance(_Firstn, _Count1n);
    			_Lastn = _STD lower_bound(_Mid, _Last, *_Firstn);
    			_Distance(_Mid, _Lastn, _Count2n);
    			}
    		else
    			{	// right larger, cut it in half and partition left to match
    			_Count1n = 0, _Count2n = _Count2 / 2;
    			_Lastn = _Mid;
    			_STD advance(_Lastn, _Count2n);
    			_Firstn = _STD upper_bound(_First, _Mid, *_Lastn);
    			_Distance(_First, _Firstn, _Count1n);
    			}
    
    		_BidIt _Midn = _Buffered_rotate(_Firstn, _Mid, _Lastn,
    			_Count1 - _Count1n, _Count2n, _Tempbuf);	// rearrange middle
    		_Buffered_merge(_First, _Firstn, _Midn,
    			_Count1n, _Count2n, _Tempbuf);	// merge each new part
    		_Buffered_merge(_Midn, _Lastn, _Last,
    			_Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf);
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty> inline
    	void _Inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
    		_Diff *, _Ty *)
    	{	// merge [_First, _Mid) with [_Mid, _Last), using operator<
    	_DEBUG_ORDER(_First, _Mid);
    	_DEBUG_ORDER(_Mid, _Last);
    	_Diff _Count1 = 0;
    	_Distance(_First, _Mid, _Count1);
    	_Diff _Count2 = 0;
    	_Distance(_Mid, _Last, _Count2);
    	_Temp_iterator<_Ty> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
    	_Buffered_merge(_First, _Mid, _Last,
    		_Count1, _Count2, _Tempbuf);
    	}
    
    template<class _BidIt> inline
    	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
    	{	// merge [_First, _Mid) with [_Mid, _Last), using operator<
    	if (_First != _Mid && _Mid != _Last)
    		_Inplace_merge(_First, _Mid, _Last,
    			_Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION inplace_merge WITH PRED
    template<class _BidIt1,
    	class _BidIt2,
    	class _BidIt3,
    	class _Pr> inline
    	_BidIt3 _Merge_backward(_BidIt1 _First1, _BidIt1 _Last1,
    		_BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
    	{	// merge backwards to _Dest, using _Pred
    	for (; ; )
    		if (_First1 == _Last1)
    			return (_STD copy_backward(_First2, _Last2, _Dest));
    		else if (_First2 == _Last2)
    			return (_STD copy_backward(_First1, _Last1, _Dest));
    		else if (_DEBUG_LT_PRED(_Pred, *--_Last2, *--_Last1))
    			*--_Dest = *_Last1, ++_Last2;
    		else
    			*--_Dest = *_Last2, ++_Last1;
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Buffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
    		_Diff _Count1, _Diff _Count2,
    			_Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
    	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
    	if (_Count1 + _Count2 == 2)
    		{	// order two one-element partitions
    		if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
    			_STD iter_swap(_First, _Mid);
    		}
    	else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
    		{	// buffer left partition, then merge
    		_STD copy(_First, _Mid, _Tempbuf._Init());
    		_STD merge(_Tempbuf._First(), _Tempbuf._Last(),
    			_Mid, _Last, _First, _Pred);
    		}
    	else if (_Count2 <= _Tempbuf._Maxlen())
    		{	// buffer right partition, then merge
    		_STD copy(_Mid, _Last, _Tempbuf._Init());
    		_Merge_backward(_First, _Mid, _Tempbuf._First(), _Tempbuf._Last(),
    			_Last, _Pred);
    		}
    	else
    		{	// buffer too small, divide and conquer
    		_BidIt _Firstn, _Lastn;
    		_Diff _Count1n, _Count2n;
    		if (_Count2 < _Count1)
    			{	// left larger, cut it in half and partition right to match
    			_Count1n = _Count1 / 2, _Count2n = 0;
    			_Firstn = _First;
    			_STD advance(_Firstn, _Count1n);
    			_Lastn = lower_bound(_Mid, _Last, *_Firstn, _Pred);
    			_Distance(_Mid, _Lastn, _Count2n);
    			}
    		else
    			{	// right larger, cut it in half and partition left to match
    			_Count1n = 0, _Count2n = _Count2 / 2;
    			_Lastn = _Mid;
    			_STD advance(_Lastn, _Count2n);
    			_Firstn = upper_bound(_First, _Mid, *_Lastn, _Pred);
    			_Distance(_First, _Firstn, _Count1n);
    			}
    		_BidIt _Midn = _Buffered_rotate(_Firstn, _Mid, _Lastn,
    			_Count1 - _Count1n, _Count2n, _Tempbuf);	// rearrange middle
    		_Buffered_merge(_First, _Firstn, _Midn,
    			_Count1n, _Count2n, _Tempbuf, _Pred);	// merge each new part
    		_Buffered_merge(_Midn, _Lastn, _Last,
    			_Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf, _Pred);
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred,
    		_Diff *, _Ty *)
    	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
    	_DEBUG_ORDER_PRED(_First, _Mid, _Pred);
    	_DEBUG_ORDER_PRED(_Mid, _Last, _Pred);
    	_Diff _Count1 = 0;
    	_Distance(_First, _Mid, _Count1);
    	_Diff _Count2 = 0;
    	_Distance(_Mid, _Last, _Count2);
    	_Temp_iterator<_Ty> _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
    	_Buffered_merge(_First, _Mid, _Last,
    		_Count1, _Count2, _Tempbuf, _Pred);
    	}
    
    template<class _BidIt,
    	class _Pr> inline
    	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred)
    	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
    	if (_First != _Mid && _Mid != _Last)
    		_Inplace_merge(_First, _Mid, _Last, _Pred,
    			_Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION sort
    template<class _BidIt> inline
    	void _Insertion_sort(_BidIt _First, _BidIt _Last)
    	{	// insertion sort [_First, _Last), using operator<
    	if (_First != _Last)
    		for (_BidIt _Next = _First; ++_Next != _Last; )
    			if (_DEBUG_LT(*_Next, *_First))
    				{	// found new earliest element, rotate to front
    				_BidIt _Next1 = _Next;
    				_STD rotate(_First, _Next, ++_Next1);
    				}
    			else
    				{	// look for insertion point after first
    				_BidIt _Dest = _Next;
    				for (_BidIt _Dest0 = _Dest; _DEBUG_LT(*_Next, *--_Dest0); )
    					_Dest = _Dest0;
    				if (_Dest != _Next)
    					{	// rotate into place
    					_BidIt _Next1 = _Next;
    					_STD rotate(_Dest, _Next, ++_Next1);
    					}
    				}
    	}
    
    template<class _RanIt> inline
    	void _Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last)
    	{	// sort median of three elements to middle
    	if (_DEBUG_LT(*_Mid, *_First))
    		_STD iter_swap(_Mid, _First);
    	if (_DEBUG_LT(*_Last, *_Mid))
    		_STD iter_swap(_Last, _Mid);
    	if (_DEBUG_LT(*_Mid, *_First))
    		_STD iter_swap(_Mid, _First);
    	}
    
    template<class _RanIt> inline
    	void _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last)
    	{	// sort median element to middle
    	if (40 < _Last - _First)
    		{	// median of nine
    		int _Step = (_Last - _First + 1) / 8;
    		_Med3(_First, _First + _Step, _First + 2 * _Step);
    		_Med3(_Mid - _Step, _Mid, _Mid + _Step);
    		_Med3(_Last - 2 * _Step, _Last - _Step, _Last);
    		_Med3(_First + _Step, _Mid, _Last - _Step);
    		}
    	else
    		_Med3(_First, _Mid, _Last);
    	}
    
    template<class _RanIt> inline
    	pair<_RanIt, _RanIt> _Unguarded_partition(_RanIt _First, _RanIt _Last)
    	{	// partition [_First, _Last), using operator<
    	_RanIt _Mid = _First + (_Last - _First) / 2;	// sort median to _Mid
    	_Median(_First, _Mid, _Last - 1);
    	_RanIt _Pfirst = _Mid;
    	_RanIt _Plast = _Pfirst + 1;
    
    	while (_First < _Pfirst
    		&& !_DEBUG_LT(*(_Pfirst - 1), *_Pfirst)
    		&& !(*_Pfirst < *(_Pfirst - 1)))
    		--_Pfirst;
    	while (_Plast < _Last
    		&& !_DEBUG_LT(*_Plast, *_Pfirst)
    		&& !(*_Pfirst < *_Plast))
    		++_Plast;
    
    	_RanIt _Gfirst = _Plast;
    	_RanIt _Glast = _Pfirst;
    
    	for (; ; )
    		{	// partition
    		for (; _Gfirst < _Last; ++_Gfirst)
    			if (_DEBUG_LT(*_Pfirst, *_Gfirst))
    				;
    			else if (*_Gfirst < *_Pfirst)
    				break;
    			else
    				_STD iter_swap(_Plast++, _Gfirst);
    		for (; _First < _Glast; --_Glast)
    			if (_DEBUG_LT(*(_Glast - 1), *_Pfirst))
    				;
    			else if (*_Pfirst < *(_Glast - 1))
    				break;
    			else
    				_STD iter_swap(--_Pfirst, _Glast - 1);
    		if (_Glast == _First && _Gfirst == _Last)
    			return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));
    
    		if (_Glast == _First)
    			{	// no room at bottom, rotate pivot upward
    			if (_Plast != _Gfirst)
    				_STD iter_swap(_Pfirst, _Plast);
    			++_Plast;
    			_STD iter_swap(_Pfirst++, _Gfirst++);
    			}
    		else if (_Gfirst == _Last)
    			{	// no room at top, rotate pivot downward
    			if (--_Glast != --_Pfirst)
    				_STD iter_swap(_Glast, _Pfirst);
    			_STD iter_swap(_Pfirst, --_Plast);
    			}
    		else
    			_STD iter_swap(_Gfirst++, --_Glast);
    		}
    	}
    
    template<class _RanIt,
    	class _Diff> inline
    	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
    	{	// order [_First, _Last), using operator<
    	_Diff _Count;
    	for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
    		{	// divide and conquer by quicksort
    		pair<_RanIt, _RanIt> _Mid = _Unguarded_partition(_First, _Last);
    		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions
    
    		if (_Mid.first - _First < _Last - _Mid.second)	// loop on larger half
    			_Sort(_First, _Mid.first, _Ideal), _First = _Mid.second;
    		else
    			_Sort(_Mid.second, _Last, _Ideal), _Last = _Mid.first;
    		}
    
    	if (_ISORT_MAX < _Count)
    		{	// heap sort if too many divisions
    		_STD make_heap(_First, _Last);
    		_STD sort_heap(_First, _Last);
    		}
    	else if (1 < _Count)
    		_Insertion_sort(_First, _Last);	// small, insertion sort
    	}
    
    template<class _RanIt> inline
    	void sort(_RanIt _First, _RanIt _Last)
    	{	// order [_First, _Last), using operator<
    	_DEBUG_RANGE(_First, _Last);
    	_Sort(_First, _Last, _Last - _First);
    	}
    
    		// TEMPLATE FUNCTION sort WITH PRED
    template<class _BidIt,
    	class _Pr> inline
    	void _Insertion_sort(_BidIt _First, _BidIt _Last, _Pr _Pred)
    	{	// insertion sort [_First, _Last), using _Pred
    	if (_First != _Last)
    		for (_BidIt _Next = _First; ++_Next != _Last; )
    			if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
    				{	// found new earliest element, rotate to front
    				_BidIt _Next1 = _Next;
    				_STD rotate(_First, _Next, ++_Next1);
    				}
    			else
    				{	// look for insertion point after first
    				_BidIt _Dest = _Next;
    				for (_BidIt _Dest0 = _Dest;
    					_DEBUG_LT_PRED(_Pred,*_Next, *--_Dest0); )
    					_Dest = _Dest0;
    				if (_Dest != _Next)
    					{	// rotate into place
    					_BidIt _Next1 = _Next;
    					_STD rotate(_Dest, _Next, ++_Next1);
    					}
    				}
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void _Med3(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
    	{	// sort median of three elements to middle
    	if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
    		_STD iter_swap(_Mid, _First);
    	if (_DEBUG_LT_PRED(_Pred, *_Last, *_Mid))
    		_STD iter_swap(_Last, _Mid);
    	if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First))
    		_STD iter_swap(_Mid, _First);
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void _Median(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
    	{	// sort median element to middle
    	if (40 < _Last - _First)
    		{	// median of nine
    		int _Step = (_Last - _First + 1) / 8;
    		_Med3(_First, _First + _Step, _First + 2 * _Step, _Pred);
    		_Med3(_Mid - _Step, _Mid, _Mid + _Step, _Pred);
    		_Med3(_Last - 2 * _Step, _Last - _Step, _Last, _Pred);
    		_Med3(_First + _Step, _Mid, _Last - _Step, _Pred);
    		}
    	else
    		_Med3(_First, _Mid, _Last, _Pred);
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	pair<_RanIt, _RanIt> _Unguarded_partition(_RanIt _First, _RanIt _Last,
    		_Pr _Pred)
    	{	// partition [_First, _Last), using _Pred
    	_RanIt _Mid = _First + (_Last - _First) / 2;
    	_Median(_First, _Mid, _Last - 1, _Pred);
    	_RanIt _Pfirst = _Mid;
    	_RanIt _Plast = _Pfirst + 1;
    
    	while (_First < _Pfirst
    		&& !_DEBUG_LT_PRED(_Pred, *(_Pfirst - 1), *_Pfirst)
    		&& !_Pred(*_Pfirst, *(_Pfirst - 1)))
    		--_Pfirst;
    	while (_Plast < _Last
    		&& !_DEBUG_LT_PRED(_Pred, *_Plast, *_Pfirst)
    		&& !_Pred(*_Pfirst, *_Plast))
    		++_Plast;
    
    	_RanIt _Gfirst = _Plast;
    	_RanIt _Glast = _Pfirst;
    
    	for (; ; )
    		{	// partition
    		for (; _Gfirst < _Last; ++_Gfirst)
    			if (_DEBUG_LT_PRED(_Pred, *_Pfirst, *_Gfirst))
    				;
    			else if (_Pred(*_Gfirst, *_Pfirst))
    				break;
    			else
    				_STD iter_swap(_Plast++, _Gfirst);
    		for (; _First < _Glast; --_Glast)
    			if (_DEBUG_LT_PRED(_Pred, *(_Glast - 1), *_Pfirst))
    				;
    			else if (_Pred(*_Pfirst, *(_Glast - 1)))
    				break;
    			else
    				_STD iter_swap(--_Pfirst, _Glast - 1);
    		if (_Glast == _First && _Gfirst == _Last)
    			return (pair<_RanIt, _RanIt>(_Pfirst, _Plast));
    
    		if (_Glast == _First)
    			{	// no room at bottom, rotate pivot upward
    			if (_Plast != _Gfirst)
    				_STD iter_swap(_Pfirst, _Plast);
    			++_Plast;
    			_STD iter_swap(_Pfirst++, _Gfirst++);
    			}
    		else if (_Gfirst == _Last)
    			{	// no room at top, rotate pivot downward
    			if (--_Glast != --_Pfirst)
    				_STD iter_swap(_Glast, _Pfirst);
    			_STD iter_swap(_Pfirst, --_Plast);
    			}
    		else
    			_STD iter_swap(_Gfirst++, --_Glast);
    		}
    	}
    
    template<class _RanIt,
    	class _Diff,
    	class _Pr> inline
    	void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
    	{	// order [_First, _Last), using _Pred
    	_Diff _Count;
    	for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
    		{	// divide and conquer by quicksort
    		pair<_RanIt, _RanIt> _Mid =
    			_Unguarded_partition(_First, _Last, _Pred);
    		_Ideal /= 2, _Ideal += _Ideal / 2;	// allow 1.5 log2(N) divisions
    
    		if (_Mid.first - _First < _Last - _Mid.second)	// loop on larger half
    			_Sort(_First, _Mid.first, _Ideal, _Pred), _First = _Mid.second;
    		else
    			_Sort(_Mid.second, _Last, _Ideal, _Pred), _Last = _Mid.first;
    		}
    
    	if (_ISORT_MAX < _Count)
    		{	// heap sort if too many divisions
    		_STD make_heap(_First, _Last, _Pred);
    		_STD sort_heap(_First, _Last, _Pred);
    		}
    	else if (1 < _Count)
    		_Insertion_sort(_First, _Last, _Pred);	// small, insertion sort
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
    	{	// order [_First, _Last), using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_Sort(_First, _Last, _Last - _First, _Pred);
    	}
    
    		// TEMPLATE FUNCTION stable_sort
    template<class _BidIt,
    	class _OutIt,
    	class _Diff> inline
    	void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
    		_Diff _Chunk, _Diff _Count)
    	{	// copy merging chunks, using operator<
    	for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
    		{	// copy merging pairs of adjacent chunks
    		_BidIt _Mid1 = _First;
    		_STD advance(_Mid1, _Chunk);
    		_BidIt _Mid2 = _Mid1;
    		_STD advance(_Mid2, _Chunk);
    
    		_Dest = _STD merge(_First, _Mid1, _Mid1, _Mid2, _Dest);
    		_First = _Mid2;
    		}
    
    	if (_Count <= _Chunk)
    		_STD copy(_First, _Last, _Dest);	// copy partial last chunk
    	else
    		{	// copy merging whole and partial last chunk
    		_BidIt _Mid = _First;
    		_STD advance(_Mid, _Chunk);
    
    		_STD merge(_First, _Mid, _Mid, _Last, _Dest);
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty> inline
    	void _Buffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
    		_Temp_iterator<_Ty>& _Tempbuf)
    	{	// sort using temp buffer for merges, using operator<
    	_BidIt _Mid = _First;
    	for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
    		{	// sort chunks
    		_BidIt _Midend = _Mid;
    		_STD advance(_Midend, (int)_ISORT_MAX);
    
    		_Insertion_sort(_Mid, _Midend);
    		_Mid = _Midend;
    		}
    	_Insertion_sort(_Mid, _Last);	// sort partial last chunk
    
    	for (_Diff _Chunk = _ISORT_MAX; _Chunk < _Count; _Chunk *= 2)
    		{	// merge adjacent pairs of chunks to and from temp buffer
    		_Chunked_merge(_First, _Last, _Tempbuf._Init(),
    			_Chunk, _Count);
    		_Chunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
    			_Chunk *= 2, _Count);
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty> inline
    	void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
    		_Temp_iterator<_Ty>& _Tempbuf)
    	{	//  sort preserving order of equivalents, using operator<
    	if (_Count <= _ISORT_MAX)
    		_Insertion_sort(_First, _Last);	// small, insertion sort
    	else
    		{	// sort halves and merge
    		_Diff _Count2 = (_Count + 1) / 2;
    		_BidIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (_Count2 <= _Tempbuf._Maxlen())
    			{	// temp buffer big enough, sort each half using buffer
    			_Buffered_merge_sort(_First, _Mid, _Count2, _Tempbuf);
    			_Buffered_merge_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
    			}
    		else
    			{	// temp buffer not big enough, divide and conquer
    			_Stable_sort(_First, _Mid, _Count2, _Tempbuf);
    			_Stable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
    			}
    
    		_Buffered_merge(_First, _Mid, _Last,
    			_Count2, _Count - _Count2, _Tempbuf);	// merge sorted halves
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty> inline
    	void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff *, _Ty *)
    	{	// sort preserving order of equivalents, using operator<
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    	_Temp_iterator<_Ty> _Tempbuf(_Count);
    	_Stable_sort(_First, _Last, _Count, _Tempbuf);
    	}
    
    template<class _BidIt> inline
    	void stable_sort(_BidIt _First, _BidIt _Last)
    	{	// sort preserving order of equivalents, using operator<
    	_DEBUG_RANGE(_First, _Last);
    	if (_First != _Last)
    		_Stable_sort(_First, _Last, _Dist_type(_First), _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION stable_sort WITH PRED
    template<class _BidIt,
    	class _OutIt,
    	class _Diff,
    	class _Pr> inline
    	void _Chunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
    		_Diff _Chunk, _Diff _Count, _Pr _Pred)
    	{	// copy merging chunks, using _Pred
    	for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
    		{	// copy merging pairs of adjacent chunks
    		_BidIt _Mid1 = _First;
    		_STD advance(_Mid1, _Chunk);
    		_BidIt _Mid2 = _Mid1;
    		_STD advance(_Mid2, _Chunk);
    
    		_Dest = _STD merge(_First, _Mid1, _Mid1, _Mid2, _Dest, _Pred);
    		_First = _Mid2;
    		}
    
    	if (_Count <= _Chunk)
    		_STD copy(_First, _Last, _Dest);	// copy partial last chunk
    	else
    		{	// copy merging whole and partial last chunk
    		_BidIt _Mid1 = _First;
    		_STD advance(_Mid1, _Chunk);
    
    		_STD merge(_First, _Mid1, _Mid1, _Last, _Dest, _Pred);
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Buffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
    		_Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
    	{	// sort using temp buffer for merges, using _Pred
    	_BidIt _Mid = _First;
    	for (_Diff _Nleft = _Count; _ISORT_MAX <= _Nleft; _Nleft -= _ISORT_MAX)
    		{	// sort chunks
    		_BidIt _Midn = _Mid;
    		_STD advance(_Midn, (int)_ISORT_MAX);
    
    		_Insertion_sort(_Mid, _Midn, _Pred);
    		_Mid = _Midn;
    		}
    	_Insertion_sort(_Mid, _Last, _Pred);	// sort partial last chunk
    
    	for (_Diff _Chunk = _ISORT_MAX; _Chunk < _Count; _Chunk *= 2)
    		{	// merge adjacent pairs of chunks to and from temp buffer
    		_Chunked_merge(_First, _Last, _Tempbuf._Init(),
    			_Chunk, _Count, _Pred);
    		_Chunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
    			_Chunk *= 2, _Count, _Pred);
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
    		_Temp_iterator<_Ty>& _Tempbuf, _Pr _Pred)
    	{	// sort preserving order of equivalents, using _Pred
    	if (_Count <= _ISORT_MAX)
    		_Insertion_sort(_First, _Last, _Pred);	// small, insertion sort
    	else
    		{	// sort halves and merge
    		_Diff _Count2 = (_Count + 1) / 2;
    		_BidIt _Mid = _First;
    		_STD advance(_Mid, _Count2);
    
    		if (_Count2 <= _Tempbuf._Maxlen())
    			{	// temp buffer big enough, sort each half using buffer
    			_Buffered_merge_sort(_First, _Mid, _Count2, _Tempbuf, _Pred);
    			_Buffered_merge_sort(_Mid, _Last, _Count - _Count2,
    				_Tempbuf, _Pred);
    			}
    		else
    			{	// temp buffer not big enough, divide and conquer
    			_Stable_sort(_First, _Mid, _Count2, _Tempbuf, _Pred);
    			_Stable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf, _Pred);
    			}
    
    		_Buffered_merge(_First, _Mid, _Last,
    			_Count2, _Count - _Count2, _Tempbuf, _Pred);	// merge halves
    		}
    	}
    
    template<class _BidIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	void _Stable_sort(_BidIt _First, _BidIt _Last, _Diff *, _Ty *, _Pr _Pred)
    	{	// sort preserving order of equivalents, using _Pred
    	_Diff _Count = 0;
    	_Distance(_First, _Last, _Count);
    	_Temp_iterator<_Ty> _Tempbuf(_Count);
    	_Stable_sort(_First, _Last, _Count, _Tempbuf, _Pred);
    	}
    
    template<class _BidIt,
    	class _Pr> inline
    	void stable_sort(_BidIt _First, _BidIt _Last, _Pr _Pred)
    	{	// sort preserving order of equivalents, using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	if (_First != _Last)
    		_Stable_sort(_First, _Last,
    			_Dist_type(_First), _Val_type(_First), _Pred);
    	}
    
    		// TEMPLATE FUNCTION partial_sort
    template<class _RanIt,
    	class _Ty> inline
    	void _Partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Ty *)
    	{	// order [First, _Last) up to _Mid, using operator<
    	_DEBUG_RANGE(_First, _Mid);
    	_DEBUG_RANGE(_Mid, _Last);
    	_STD make_heap(_First, _Mid);
    
    	for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
    		if (_DEBUG_LT(*_Next, *_First))
    			_Pop_heap(_First, _Mid, _Next, _Ty(*_Next),
    				_Dist_type(_First));	// replace top with new largest
    	_STD sort_heap(_First, _Mid);
    	}
    
    template<class _RanIt> inline
    	void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last)
    	{	// order [First, _Last) up to _Mid, using operator<
    	_Partial_sort(_First, _Mid, _Last, _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION partial_sort WITH PRED
    template<class _RanIt,
    	class _Ty,
    	class _Pr> inline
    	void _Partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last,
    		_Pr _Pred, _Ty *)
    	{	// order [First, _Last) up to _Mid, using _Pred
    	_DEBUG_RANGE(_First, _Mid);
    	_DEBUG_RANGE(_Mid, _Last);
    	_DEBUG_POINTER(_Pred);
    	_STD make_heap(_First, _Mid, _Pred);
    
    	for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
    		if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
    			_Pop_heap(_First, _Mid, _Next, _Ty(*_Next), _Pred,
    				_Dist_type(_First));	// replace top with new largest
    	_STD sort_heap(_First, _Mid, _Pred);
    	}
    
    template<class _RanIt,
    	class _Pr> inline
    	void partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last, _Pr _Pred)
    	{	// order [First, _Last) up to _Mid, using _Pred
    	_Partial_sort(_First, _Mid, _Last, _Pred, _Val_type(_First));
    	}
    
    		// TEMPLATE FUNCTION partial_sort_copy
    template<class _InIt,
    	class _RanIt,
    	class _Diff,
    	class _Ty> inline
    	_RanIt _Partial_sort_copy(_InIt _First1, _InIt _Last1,
    		_RanIt _First2, _RanIt _Last2, _Diff *, _Ty *)
    	{	// copy [First1, _Last1) into [_First2, _Last2), using operator<
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_RanIt _Mid2 = _First2;
    	for (; _First1 != _Last1 && _Mid2 != _Last2; ++_First1, ++_Mid2)
    		*_Mid2 = *_First1;	// copy min(_Last1 - _First1, _Last2 - _First2)
    	_STD make_heap(_First2, _Mid2);
    
    	for (; _First1 != _Last1; ++_First1)
    		if (_DEBUG_LT(*_First1, *_First2))
    			_Adjust_heap(_First2, _Diff(0), _Diff(_Mid2 - _First2),
    				_Ty(*_First1));	// replace top with new largest
    
    	_STD sort_heap(_First2, _Mid2);
    	return (_Mid2);
    	}
    
    template<class _InIt,
    	class _RanIt> inline
    	_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1,
    		_RanIt _First2, _RanIt _Last2)
    	{	// copy [First1, _Last1) into [_First2, _Last2), using operator<
    	return (_First1 == _Last1 || _First2 == _Last2 ? _First2
    		: _Partial_sort_copy(_First1, _Last1, _First2, _Last2,
    			_Dist_type(_First2), _Val_type(_First1)));
    	}
    
    		// TEMPLATE FUNCTION partial_sort_copy WITH PRED
    template<class _InIt,
    	class _RanIt,
    	class _Diff,
    	class _Ty,
    	class _Pr> inline
    	_RanIt _Partial_sort_copy(_InIt _First1, _InIt _Last1,
    		_RanIt _First2, _RanIt _Last2, _Pr _Pred, _Diff *, _Ty *)
    	{	// copy [First1, _Last1) into [_First2, _Last2) using _Pred
    	_DEBUG_RANGE(_First1, _Last1);
    	_DEBUG_RANGE(_First2, _Last2);
    	_DEBUG_POINTER(_Pred);
    	_RanIt _Mid2 = _First2;
    	for (; _First1 != _Last1 && _Mid2 != _Last2; ++_First1, ++_Mid2)
    		*_Mid2 = *_First1;	// copy min(_Last1 - _First1, _Last2 - _First2)
    	_STD make_heap(_First2, _Mid2, _Pred);
    
    	for (; _First1 != _Last1; ++_First1)
    		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
    			_Adjust_heap(_First2, _Diff(0), _Diff(_Mid2 - _First2),
    				_Ty(*_First1), _Pred);	// replace top with new largest
    
    	_STD sort_heap(_First2, _Mid2, _Pred);
    	return (_Mid2);
    	}
    
    template<class _InIt,
    	class _RanIt,
    	class _Pr> inline
    	_RanIt partial_sort_copy(_InIt _First1, _InIt _Last1,
    		_RanIt _First2, _RanIt _Last2, _Pr _Pred)
    	{	// copy [First1, _Last1) into [_First2, _Last2) using _Pred
    	return (_First1 == _Last1 || _First2 == _Last2 ? _First2
    		: _Partial_sort_copy(_First1, _Last1, _First2, _Last2, _Pred,
    			_Dist_type(_First2), _Val_type(_First1)));
    	}
    
    		// TEMPLATE FUNCTION nth_element
    template<class _RanIt> inline
    	void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last)
    	{	// order Nth element, using operator<
    	_DEBUG_RANGE(_First, _Last);
    	for (; _ISORT_MAX < _Last - _First; )
    		{	// divide and conquer, ordering partition containing Nth
    		pair<_RanIt, _RanIt> _Mid =
    			_Unguarded_partition(_First, _Last);
    
    		if (_Mid.second <= _Nth)
    			_First = _Mid.second;
    		else if (_Mid.first <= _Nth)
    			return;	// Nth inside fat pivot, done
    		else
    			_Last = _Mid.first;
    		}
    
    	_Insertion_sort(_First, _Last);	// sort any remainder
    	}
    
    		// TEMPLATE FUNCTION nth_element WITH PRED
    template<class _RanIt,
    	class _Pr> inline
    	void nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
    	{	// order Nth element, using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	for (; _ISORT_MAX < _Last - _First; )
    		{	// divide and conquer, ordering partition containing Nth
    		pair<_RanIt, _RanIt> _Mid =
    			_Unguarded_partition(_First, _Last, _Pred);
    
    		if (_Mid.second <= _Nth)
    			_First = _Mid.second;
    		else if (_Mid.first <= _Nth)
    			return;	// Nth inside fat pivot, done
    		else
    			_Last = _Mid.first;
    		}
    
    	_Insertion_sort(_First, _Last, _Pred);	// sort any remainder
    	}
    
    		// TEMPLATE FUNCTION includes
    template<class _InIt1,
    	class _InIt2> inline
    	bool includes(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2)
    	{	// test if all [_First1, _Last1) in [_First2, _Last2), using operator<
    	_DEBUG_ORDER(_First1, _Last1);
    	_DEBUG_ORDER(_First2, _Last2);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT(*_First2, *_First1))
    			return (false);
    		else if (*_First1 < *_First2)
    			++_First1;
    		else
    			++_First1, ++_First2;
    	return (_First2 == _Last2);
    	}
    
    		// TEMPLATE FUNCTION includes WITH PRED
    template<class _InIt1,
    	class _InIt2,
    	class _Pr> inline
    	bool includes(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
    	{	// test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
    	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
    	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
    			return (false);
    		else if (_Pred(*_First1, *_First2))
    			++_First1;
    		else
    			++_First1, ++_First2;
    	return (_First2 == _Last2);
    	}
    
    		// TEMPLATE FUNCTION set_union
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt> inline
    	_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
    	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
    	_DEBUG_ORDER(_First1, _Last1);
    	_DEBUG_ORDER(_First2, _Last2);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT(*_First1, *_First2))
    			*_Dest++ = *_First1, ++_First1;
    		else if (*_First2 < *_First1)
    			*_Dest++ = *_First2, ++_First2;
    		else
    			*_Dest++ = *_First1, ++_First1, ++_First2;
    	_Dest = _STD copy(_First1, _Last1, _Dest);
    	return (_STD copy(_First2, _Last2, _Dest));
    	}
    
    		// TEMPLATE FUNCTION set_union WITH PRED
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
    	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
    	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
    	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
    			*_Dest++ = *_First1, ++_First1;
    		else if (_Pred(*_First2, *_First1))
    			*_Dest++ = *_First2, ++_First2;
    		else
    			*_Dest++ = *_First1, ++_First1, ++_First2;
    	_Dest = _STD copy(_First1, _Last1, _Dest);
    	return (_STD copy(_First2, _Last2, _Dest));
    	}
    
    		// TEMPLATE FUNCTION set_intersection
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt> inline
    	_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
    	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using operator<
    	_DEBUG_ORDER(_First1, _Last1);
    	_DEBUG_ORDER(_First2, _Last2);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT(*_First1, *_First2))
    			++_First1;
    		else if (*_First2 < *_First1)
    			++_First2;
    		else
    			*_Dest++ = *_First1++, ++_First2;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION set_intersection WITH PRED
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
    	{	// AND sets [_First1, _Last1) and [_First2, _Last2), using _Pred
    	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
    	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
    			++_First1;
    		else if (_Pred(*_First2, *_First1))
    			++_First2;
    		else
    			*_Dest++ = *_First1++, ++_First2;
    	return (_Dest);
    	}
    
    		// TEMPLATE FUNCTION set_difference
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt> inline
    	_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2,	_OutIt _Dest)
    	{	// take set [_First2, _Last2) from [_First1, _Last1), using operator<
    	_DEBUG_ORDER(_First1, _Last1);
    	_DEBUG_ORDER(_First2, _Last2);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT(*_First1, *_First2))
    			*_Dest++ = *_First1, ++_First1;
    		else if (*_First2 < *_First1)
    			++_First2;
    		else
    			++_First1, ++_First2;
    	return (_STD copy(_First1, _Last1, _Dest));
    	}
    
    		// TEMPLATE FUNCTION set_difference WITH PRED
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
    	{	//  take set [_First2, _Last2) from [_First1, _Last1), using _Pred
    	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
    	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
    			*_Dest++ = *_First1, ++_First1;
    		else if (_Pred(*_First2, *_First1))
    			++_First2;
    		else
    			++_First1, ++_First2;
    	return (_STD copy(_First1, _Last1, _Dest));
    	}
    
    		// TEMPLATE FUNCTION set_symmetric_difference
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt> inline
    	_OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
    	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), using operator<
    	_DEBUG_ORDER(_First1, _Last1);
    	_DEBUG_ORDER(_First2, _Last2);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT(*_First1, *_First2))
    			*_Dest++ = *_First1, ++_First1;
    		else if (*_First2 < *_First1)
    			*_Dest++ = *_First2, ++_First2;
    		else
    			++_First1, ++_First2;
    	_Dest = _STD copy(_First1, _Last1, _Dest);
    	return (_STD copy(_First2, _Last2, _Dest));
    	}
    
    		// TEMPLATE FUNCTION set_symmetric_difference WITH PRED
    template<class _InIt1,
    	class _InIt2,
    	class _OutIt,
    	class _Pr> inline
    	_OutIt set_symmetric_difference(_InIt1 _First1, _InIt1 _Last1,
    		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
    	{	// XOR sets [_First1, _Last1) and [_First2, _Last2), using _Pred
    	_DEBUG_ORDER_PRED(_First1, _Last1, _Pred);
    	_DEBUG_ORDER_PRED(_First2, _Last2, _Pred);
    	_DEBUG_POINTER(_Dest);
    	for (; _First1 != _Last1 && _First2 != _Last2; )
    		if (_DEBUG_LT_PRED(_Pred, *_First1, *_First2))
    			*_Dest++ = *_First1, ++_First1;
    		else if (_Pred(*_First2, *_First1))
    			*_Dest++ = *_First2, ++_First2;
    		else
    			++_First1, ++_First2;
    	_Dest = _STD copy(_First1, _Last1, _Dest);
    	return (_STD copy(_First2, _Last2, _Dest));
    	}
    
    		// TEMPLATE FUNCTION max_element
    template<class _FwdIt> inline
    	_FwdIt max_element(_FwdIt _First, _FwdIt _Last)
    	{	// find largest element, using operator<
    	_DEBUG_RANGE(_First, _Last);
    	_FwdIt _Found = _First;
    	if (_First != _Last)
    		for (; ++_First != _Last; )
    			if (_DEBUG_LT(*_Found, *_First))
    				_Found = _First;
    	return (_Found);
    	}
    
    		// TEMPLATE FUNCTION max_element WITH PRED
    template<class _FwdIt,
    	class _Pr> inline
    	_FwdIt max_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    	{	// find largest element, using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_FwdIt _Found = _First;
    	if (_First != _Last)
    		for (; ++_First != _Last; )
    			if (_DEBUG_LT_PRED(_Pred, *_Found, *_First))
    				_Found = _First;
    	return (_Found);
    	}
    
    		// TEMPLATE FUNCTION min_element
    template<class _FwdIt> inline
    	_FwdIt min_element(_FwdIt _First, _FwdIt _Last)
    	{	// find smallest element, using operator<
    	_DEBUG_RANGE(_First, _Last);
    	_FwdIt _Found = _First;
    	if (_First != _Last)
    		for (; ++_First != _Last; )
    			if (_DEBUG_LT(*_First, *_Found))
    				_Found = _First;
    	return (_Found);
    	}
    
    		// TEMPLATE FUNCTION min_element WITH PRED
    template<class _FwdIt,
    	class _Pr> inline
    	_FwdIt min_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    	{	// find smallest element, using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_FwdIt _Found = _First;
    	if (_First != _Last)
    		for (; ++_First != _Last; )
    			if (_DEBUG_LT_PRED(_Pred, *_First, *_Found))
    				_Found = _First;
    	return (_Found);
    	}
    
    		// TEMPLATE FUNCTION next_permutation
    template<class _BidIt> inline
    	bool next_permutation(_BidIt _First, _BidIt _Last)
    	{	// permute and test for pure ascending, using operator<
    	_DEBUG_RANGE(_First, _Last);
    	_BidIt _Next = _Last;
    	if (_First == _Last || _First == --_Next)
    		return (false);
    
    	for (; ; )
    		{	// find rightmost element smaller than successor
    		_BidIt _Next1 = _Next;
    		if (_DEBUG_LT(*--_Next, *_Next1))
    			{	// swap with rightmost element that's smaller, flip suffix
    			_BidIt _Mid = _Last;
    			for (; !_DEBUG_LT(*_Next, *--_Mid); )
    				;
    			_STD iter_swap(_Next, _Mid);
    			_STD reverse(_Next1, _Last);
    			return (true);
    			}
    
    		if (_Next == _First)
    			{	// pure descending, flip all
    			_STD reverse(_First, _Last);
    			return (false);
    			}
    		}
    	}
    
    		// TEMPLATE FUNCTION next_permutation WITH PRED
    template<class _BidIt,
    	class _Pr> inline
    	bool next_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
    	{	// permute and test for pure ascending, using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_BidIt _Next = _Last;
    	if (_First == _Last || _First == --_Next)
    		return (false);
    
    	for (; ; )
    		{	// find rightmost element smaller than successor
    		_BidIt _Next1 = _Next;
    		if (_DEBUG_LT_PRED(_Pred, *--_Next, *_Next1))
    			{	// swap with rightmost element that's smaller, flip suffix
    			_BidIt _Mid = _Last;
    			for (; !_DEBUG_LT_PRED(_Pred, *_Next, *--_Mid); )
    				;
    			_STD iter_swap(_Next, _Mid);
    			_STD reverse(_Next1, _Last);
    			return (true);
    			}
    
    		if (_Next == _First)
    			{	// pure descending, flip all
    			_STD reverse(_First, _Last);
    			return (false);
    			}
    		}
    	}
    
    		// TEMPLATE FUNCTION prev_permutation
    template<class _BidIt> inline
    	bool prev_permutation(_BidIt _First, _BidIt _Last)
    	{	// reverse permute and test for pure descending, using operator<
    	_DEBUG_RANGE(_First, _Last);
    	_BidIt _Next = _Last;
    	if (_First == _Last || _First == --_Next)
    		return (false);
    	for (; ; )
    		{	// find rightmost element not smaller than successor
    		_BidIt _Next1 = _Next;
    		if (!_DEBUG_LT(*--_Next, *_Next1))
    			{	// swap with rightmost element that's not smaller, flip suffix
    			_BidIt _Mid = _Last;
    			for (; _DEBUG_LT(*_Next, *--_Mid); )
    				;
    			_STD iter_swap(_Next, _Mid);
    			_STD reverse(_Next1, _Last);
    			return (true);
    			}
    
    		if (_Next == _First)
    			{	// pure ascending, flip all
    			_STD reverse(_First, _Last);
    			return (false);
    			}
    		}
    	}
    
    		// TEMPLATE FUNCTION prev_permutation WITH PRED
    template<class _BidIt,
    	class _Pr> inline
    	bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
    	{	// reverse permute and test for pure descending, using _Pred
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	_BidIt _Next = _Last;
    	if (_First == _Last || _First == --_Next)
    		return (false);
    
    	for (; ; )
    		{	// find rightmost element not smaller than successor
    		_BidIt _Next1 = _Next;
    		if (!_DEBUG_LT_PRED(_Pred, *--_Next, *_Next1))
    			{	// swap with rightmost element that's not smaller, flip suffix
    			_BidIt _Mid = _Last;
    			for (; _DEBUG_LT_PRED(_Pred, *_Next, *--_Mid); )
    				;
    			_STD iter_swap(_Next, _Mid);
    			_STD reverse(_Next1, _Last);
    			return (true);
    			}
    
    		if (_Next == _First)
    			{	// pure ascending, flip all
    			_STD reverse(_First, _Last);
    			return (false);
    			}
    		}
    	}
    _STD_END
    #endif /* _ALGORITHM_ */
    
    /*
     * Copyright (c) 1992-2003 by P.J. Plauger.  ALL RIGHTS RESERVED.
     * Consult your license regarding permissions and restrictions.
     */
    
    /*
     * This file is derived from software bearing the following
     * restrictions:
     *
     * Copyright (c) 1994
     * Hewlett-Packard Company
     *
     * Permission to use, copy, modify, distribute and sell this
     * software and its documentation for any purpose is hereby
     * granted without fee, provided that the above copyright notice
     * appear in all copies and that both that copyright notice and
     * this permission notice appear in supporting documentation.
     * Hewlett-Packard Company makes no representations about the
     * suitability of this software for any purpose. It is provided
     * "as is" without express or implied warranty.
    V4.02:0216 */
    Attached Files Attached Files

  9. #259
    Junior Member spawnofjago's Avatar
    Join Date
    Nov 2010
    Posts
    35
    Found this --> [Register or Login to view links]
    Code:
    /* A C-program for TT800 : July 8th 1996 Version */
    /* by M. Matsumoto, email: matumoto@math.keio.ac.jp */
    /* genrand() generate one pseudorandom number with double precision */
    /* which is uniformly distributed on [0,1]-interval */
    /* for each call.  One may choose any initial 25 seeds */
    /* except all zeros. */
    
    /* See: ACM Transactions on Modelling and Computer Simulation, */
    /* Vol. 4, No. 3, 1994, pages 254-266. */
    
    #include <stdio.h>
    #define N 25
    #define M 7
    
    double
    genrand()
    {
        unsigned long y;
        static int k = 0;
        static unsigned long x[N]={ /* initial 25 seeds, change as you wish */
    	0x95f24dab, 0x0b685215, 0xe76ccae7, 0xaf3ec239, 0x715fad23,
    	0x24a590ad, 0x69e4b5ef, 0xbf456141, 0x96bc1b7b, 0xa7bdf825,
    	0xc1de75b7, 0x8858a9c9, 0x2da87693, 0xb657f9dd, 0xffdc8a9f,
    	0x8121da71, 0x8b823ecb, 0x885d05f5, 0x4e20cd47, 0x5a9ad5d9,
    	0x512c0c03, 0xea857ccd, 0x4cc1d30f, 0x8891a8a1, 0xa6b7aadb
        };
        static unsigned long mag01[2]={ 
            0x0, 0x8ebfd028 /* this is magic vector `a', don't change */
        };
        if (k==N) { /* generate N words at one time */
          int kk;
          for (kk=0;kk<N-M;kk++) {
    	x[kk] = x[kk+M] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];
          }
          for (; kk<N;kk++) {
    	x[kk] = x[kk+(M-N)] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];
          }
          k=0;
        }
        y = x[k];
        y ^= (y << 7) & 0x2b5b2500; /* s and b, magic vectors */
        y ^= (y << 15) & 0xdb8b0000; /* t and c, magic vectors */
        y &= 0xffffffff; /* you may delete this line if word size = 32 */
    /* 
       the following line was added by Makoto Matsumoto in the 1996 version
       to improve lower bit's corellation.
       Delete this line to o use the code published in 1994.
    */
        y ^= (y >> 16); /* added to the 1994 version */
        k++;
        return( (double) y / (unsigned long) 0xffffffff);
    }
    
    /* this main() output first 50 generated numbers */
    main()
    { int j;
      for (j=0; j<50; j++) {
        printf("%5f ", genrand());
        if (j%8==7) printf("\n");
      }
      printf("\n");
    }
    Also found pg. 254-266 here --> [Register or Login to view links]
    Last edited by spawnofjago; 01-31-2012 at 03:26 PM Reason: Automerged Doublepost

  10. #260
    Forum Moderator PS3 News's Avatar
    Join Date
    Apr 2005
    Posts
    27,377
    I merged these posts, please keep all PS3 SDK related discussion in this thread only guys.

 

Sponsored Links

Page 26 of 30 FirstFirst ... 162425262728 ... LastLast
Affiliates - Contact Us - PS3 Downloads - Privacy Statement - Site Rules - Top - © 2014 PlayStation 3 News