/**
 * @return Retrun index of number in array.
 * If number not found in array return false.
 */
- (NSNumber *)binarySearchIndexInArray:(NSArray <NSNumber *>*)array forNumber:(NSNumber *)number leftRange:(NSInteger)left rightRange:(NSInteger)right {
    
    if (left > right) {
        return [NSNumber numberWithBool:false];
    }
    
    NSInteger midIndex = (left+right)/2;
    NSNumber* mid = array[midIndex];
    
    if (number.floatValue > mid.floatValue) { // 對切的右邊
        return [self binarySearchIndexInArray:array forNumber:number leftRange:midIndex+1 rightRange:right];
    }else if (number.floatValue < mid.floatValue){ // 對切的左邊
        return [self binarySearchIndexInArray:array forNumber:number leftRange:left rightRange:midIndex-1];
    }else{ // equal，找到了
        return  [NSNumber numberWithInteger:midIndex];
    }
}

- (NSArray *)quickSortUseExtraMemoryWithData:(NSArray *)data {

    if (data.count <= 1) { // 到底部了, 不需要排序, 直接回傳
        return data;
    }
    
    int random = arc4random() % data.count;  // 隨機取用某index當pivot，避免比如排序已經排好的陣列，每次都取index0，會造成時間複雜度O(N^2)，worst case
    NSNumber *pivot = data[random];
    
    NSMutableArray *less = [[NSMutableArray alloc]init];
    NSMutableArray *greater = [[NSMutableArray alloc]init];
    
    for (int i=1; i<=data.count-1; i++ ) {
        if ([(NSNumber *)data[i]floatValue] >= [pivot floatValue]) {
            [greater addObject:data[i]];
        }else {
            [less addObject:data[i]];
        }
    }
    
    NSMutableArray *result = [[NSMutableArray alloc]init];
    [result addObjectsFromArray:[self quickSortUseExtraMemoryWithData:less]];
    [result addObject:pivot];
    [result addObjectsFromArray:[self quickSortUseExtraMemoryWithData:greater]];
    
    return result;
}

- (NSMutableArray *)quickSortInPlaceWithData:(NSMutableArray <NSNumber *>*)data leftIndex:(NSInteger)left rightIndex:(NSInteger)right{
    // 使用in-place法，操作同一個陣列，避免額外消耗多餘記憶體，硬體限制嚴格的環境下使用
    
    if (left > right) { // 底部。代表上一層遞迴切出來，這個sub-array已經只有一個元素，就不用排列了，'這個元素也會是已經就定位的'。
        return nil;
    }
    
    NSNumber *pivot = data[right];
    
    NSInteger processIndexAKAWall = left;
    [data exchangeObjectAtIndex:right withObjectAtIndex:right];// 把pivot移到最後面
    for (int i=(int)left; i<right; i++ ) { // left ... right-1
        if ([data[i]floatValue] < [pivot floatValue]) {
            [data exchangeObjectAtIndex:processIndexAKAWall withObjectAtIndex:i];// 擺到牆的右邊
            processIndexAKAWall = processIndexAKAWall + 1;// 牆往前
        }
    }
    [data exchangeObjectAtIndex:processIndexAKAWall withObjectAtIndex:right];// 把pivot移到牆的右邊。這個pivot目前已經在正確的index上了。
    
    // 切兩段
    // start by left, end by processIndexAKAWall - 1
    // start by processIndexAKAWall + 1, end by right
    [self quickSortInPlaceWithData:data leftIndex:left rightIndex:processIndexAKAWall - 1];
    [self quickSortInPlaceWithData:data leftIndex:processIndexAKAWall + 1 rightIndex:right];
    
    return data;
}

NSMutableArray *result = [self quickSortInPlaceWithData:[data mutableCopy] leftIndex:0 rightIndex:data.count-1];

- (NSArray *)quickSort:(NSArray *)data {
    return [self quickSortInPlaceWithData:[data mutableCopy]  leftIndex:0 rightIndex:data.count-1];
}

- (NSArray *)mergeSortWithData:(NSArray *)data {
    
    if (data.count == 1) {
        // div done here
        // 這裡已經把問題分解成最小單位了，所以就告一段落
        return data;
    }
    
    NSInteger divLength = data.count/2;
    NSArray *left = [data subarrayWithRange:NSMakeRange(0, divLength)];
    NSArray *rigth = [data subarrayWithRange:NSMakeRange(divLength, data.count-divLength)];
    
    NSArray<NSNumber*> *mergeArrayA = [self mergeSortWithData:left];
    NSArray<NSNumber*> *mergeArrayB = [self mergeSortWithData:rigth];
    
    NSInteger headOfMergeArrayA = 0;
    NSInteger headOfMergeArrayB = 0;
    
    NSMutableArray *resultArray = [[NSMutableArray alloc]initWithCapacity:mergeArrayA.count+mergeArrayB.count];
    
    Boolean control = true;
    while (control) {
        
        if (headOfMergeArrayA == mergeArrayA.count) {
            //MergeArrayA沒東西了
            //把剩餘的MergeArrayB直接append到resultArray後面
            [resultArray addObjectsFromArray:[mergeArrayB subarrayWithRange:NSMakeRange(headOfMergeArrayB, mergeArrayB.count-headOfMergeArrayB)]];
            control = false;
            break;
        }else if(headOfMergeArrayB == mergeArrayB.count){
            [resultArray addObjectsFromArray:[mergeArrayA subarrayWithRange:NSMakeRange(headOfMergeArrayA, mergeArrayA.count-headOfMergeArrayA)]];
            control = false;
            break;
        }
        
        if ([mergeArrayA[headOfMergeArrayA]floatValue] > [mergeArrayB[headOfMergeArrayB]floatValue]) {
            [resultArray addObject:mergeArrayB[headOfMergeArrayB]];
            headOfMergeArrayB = headOfMergeArrayB + 1;
        }else{
            [resultArray addObject:mergeArrayA[headOfMergeArrayA]];
            headOfMergeArrayA = headOfMergeArrayA + 1;
        }
    }
    
    return resultArray;
}

// 購買SKProduct
// Create and add a payment request to the payment queue
-(void)buy:(SKProduct *)product
{
    SKMutablePayment *payment = [SKMutablePayment paymentWithProduct:product];
  [[SKPaymentQueue defaultQueue] addPayment:payment];
}

// 取回過去完成交易的非消耗品購買與自動續訂紀錄
-(void)restore
{
    [[SKPaymentQueue defaultQueue] restoreCompletedTransactions];
}

+ (StoreObserver *)sharedInstance
{
    static dispatch_once_t onceToken;
    static StoreObserver * storeObserverSharedInstance;
    
    dispatch_once(&onceToken, ^{
        storeObserverSharedInstance = [[StoreObserver alloc] init];
    });
    return storeObserverSharedInstance;
}


- (instancetype)init
{
  self = [super init];
  if (self != nil)
    {
        _productsRestored = [[NSMutableArray alloc] initWithCapacity:0];
    }
  return self;
}

NSString * const TNIAPPurchaseNotification = @"TNIAPPurchaseNotification";

typedef NS_ENUM(NSInteger, TNIAPPurchaseNotificationStatus)
{
    TNIAPPurchaseFailed, // Indicate that the purchase was unsuccessful
    TNIAPPurchaseSucceeded, // Indicate that the purchase was successful
    TNIAPRestoredFailed, // Indicate that restore products was unsuccessful
    TNIAPRestoredSucceeded // Indicate that restore products was successful
};

@property (nonatomic) TNIAPPurchaseNotificationStatus status;
@property (nonatomic, copy) NSString *purchasedID;
@property (nonatomic, copy) NSString *message;

// Called when an error occur while restoring purchases. Notify the user about the error.
- (void)paymentQueue:(SKPaymentQueue *)queue restoreCompletedTransactionsFailedWithError:(NSError *)error
{
    if (error.code != SKErrorPaymentCancelled)
    {
        self.status = IAPRestoredFailed;
        self.message = error.localizedDescription;
        [[NSNotificationCenter defaultCenter] postNotificationName:TNIAPPurchaseNotification object:self];
    }
}

SKProduct *product = (SKProduct *)productRequestResponse[indexPath.row];
        // Attempt to purchase the tapped product
        [[TNStoreObserver sharedInstance] buy:product];

[[NSNotificationCenter defaultCenter] addObserver:self
                                             selector:@selector(handlePurchasesNotification:)
                                                 name:TNIAPPurchaseNotification
                                               object:[StoreObserver sharedInstance]];

// Update the UI according to the purchase request notification result
-(void)handlePurchasesNotification:(NSNotification *)notification
{
    StoreObserver *purchasesNotification = (StoreObserver *)notification.object;
    
    IAPPurchaseNotificationStatus status = (IAPPurchaseNotificationStatus)purchasesNotification.status;
    NSString *message = purchasesNotification.message;
    NSString *purchasedID = purchasesNotification.purchasedID;
   

  switch (status)
    {
        case IAPPurchaseFailed:
            //購買失敗...
          break;
            
        case IAPDownloadSucceeded:
        {
            //購買成功...
        }
          break;
        
        case IAPRestoredSucceeded:
        {
            //回復成功...
        }
            break;
            
        case IAPRestoredFailed:
            //回復失敗...
            break;
  } 
}

// If you are loading it from a nib file (or a storyboard), initWithCoder: will be used.
- (instancetype)initWithCoder:(NSCoder *)aDecoder
{
    self = [super initWithCoder:aDecoder];
    if (self) {
        [self addSubview:[[[NSBundle mainBundle] loadNibNamed:NSStringFromClass([self class]) owner:self options:nil] objectAtIndex:0]];
    }
    return self;
}

- (id)initWithFrame:(CGRect)frame
{
    self = [super initWithFrame:frame];
    if (self) {
        // Initialization code
        self.autoresizesSubviews = YES;
    }
    return self;
}

desc "Submit a new Beta Build to Apple TestFlight"
  desc "This will also make sure the profile is up to date"
  lane :beta do
    increment_build_number
    # match(type: "appstore") # more information: https://codesigning.guide
    gym(scheme: "SecureMedia", use_legacy_build_api: true) # Build your app - more options available
    pilot(team_name: "CUTE LIMITED")

    # sh "your_script.sh"
    # You can also use other beta testing services here (run `fastlane actions`)
  end

<key>ITSAppUsesNonExemptEncryption</key>
<false/>

- (UIPresentationController *)presentationControllerForPresentedViewController:(UIViewController *)presented presentingViewController:(UIViewController *)presenting sourceViewController:(UIViewController *)source{

1.透過if ([presented isKindOfClass:AlbumMenuViewController class])來分別要提供對應PresentationController{
2.建立一個subclass UIPresentationController的class。(怎麼建請看段B)
3.透過UIPresentationController的父方法initWithPresentedViewController...(略)去instance這個PresentationController object。
}

}

- (id<UIViewControllerAnimatedTransitioning> _Nullable)animationControllerForPresentedController:(UIViewController * _Nonnull)presented presentingController:(UIViewController * _Nonnull)presenting sourceController:(UIViewController * _Nonnull)source{

1.用if去知道你等等要回傳那個對應的animator
if([presented isKindOfClass:[HelperTableViewController class]]){
2.SlideMenuAnimator *animator = [[SlideMenuAnimator alloc]init];//製作一個實作UIViewControllerAnimatedTransitioning協議的animator class，怎麼做看段C
3.[animator setPresenting:YES];// 我設計的animator可以同時包含出場與離場的動畫，這樣就不用寫兩個animator了，所以裡面有個參數可以選擇要回傳哪種動畫，這裡是出場就設定YES。
}

}

- (id<UIViewControllerAnimatedTransitioning> _Nullable)animationControllerForDismissedController:(UIViewController * _Nonnull)dismissed{
1.用if去知道你等等要回傳那個對應的animator
if([presented isKindOfClass:[HelperTableViewController class]]){
2.SlideMenuAnimator *animator = [[SlideMenuAnimator alloc]init];//前面解釋過
3.[animator setPresenting:NO];//前面解釋過
}
}

(CGRect)frameOfPresentedViewInContainerView
{
CGRect presentedViewFrame = CGRectZero;//我們要回傳的數值
CGRect containerBounds = [[self containerView] bounds];//得到prestingVC的bounds
// 到這裡你已經可以運加減乘除算出你要顯示的VC的大小，下面示範的是要根據ipad跟iphone做特別處理的做法

if (self.traitCollection.userInterfaceIdiom == UIUserInterfaceIdiomPhone) {
presentedViewFrame.size = CGSizeMake(floorf(containerBounds.size.width * 0.75),
containerBounds.size.height);
}else if(self.traitCollection.userInterfaceIdiom == UIUserInterfaceIdiomPad){
presentedViewFrame.size = CGSizeMake(floorf(300),
containerBounds.size.height);
}

return presentedViewFrame;//最後當然是回傳
}

- (void)presentationTransitionWillBegin {

self.dimmingView = [[UIView alloc]init];
[self.dimmingView setFrame:self.containerView.frame];
[self.dimmingView setBackgroundColor:[UIColor blackColor]];
[self.dimmingView setAlpha:0.3f];

// Add a custom dimming view behind the presented view controller's view
[[self containerView] addSubview:self.dimmingView];
[self.dimmingView addSubview:[[self presentedViewController] view]];

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wundeclared-selector"
UITapGestureRecognizer *dimmingViewSingleTap =
[[UITapGestureRecognizer alloc] initWithTarget:self.presentingViewController
action:@selector(handleDimmingViewSingleTap)];
#pragma clang diagnostic pop
[self.dimmingView addGestureRecognizer:dimmingViewSingleTap];

// Fade in the dimming view during the transition.
[self.dimmingView setAlpha:0.0];
// Use the transition coordinator to set up the animations.
[[[self presentingViewController] transitionCoordinator] animateAlongsideTransition:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {
[self.dimmingView setAlpha:0.55];
} completion:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {

}];
}

- (void)dismissalTransitionWillBegin {
[[[self presentingViewController] transitionCoordinator] animateAlongsideTransition:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {
[self.dimmingView setAlpha:0.0];
} completion:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {

}];
}

- (void)viewWillTransitionToSize:(CGSize)size withTransitionCoordinator:(id<UIViewControllerTransitionCoordinator>)coordinator 

//製作實作UIViewControllerAnimatedTransitioning協議的animator，系統會去這裡要VC的初始位置跟Final位置，系統再去補齊動畫。
//1 override 下面function來提供動畫內容（兩個位置）
- (void)animateTransition:(id<UIViewControllerContextTransitioning> _Nonnull)transitionContext {
1.// 主畫布
UIView *containerView = [transitionContext containerView];

2.// 對進場來說（toVC是prestedVC），拿到後可以再去拿VC的view
UIViewController *toVC   = [transitionContext
viewControllerForKey:UITransitionContextToViewControllerKey];

3.// 對進場來說（fromVC是prestingVC)，拿到後可以再去拿VC的view
UIViewController *fromVC = [transitionContext
viewControllerForKey:UITransitionContextFromViewControllerKey];

4.//取得view，後面動畫主要就是都在操作這裡
UIView *toView = [transitionContext viewForKey:UITransitionContextToViewKey];
UIView *fromView = [transitionContext viewForKey:UITransitionContextFromViewKey];

5.//取得兩個VC的最終大小，大小是在frameOfPresentedViewInContainerView決定。
// Set up some variables for the animation.
CGRect containerFrame = containerView.frame;
CGRect toViewStartFrame = [transitionContext initialFrameForViewController:toVC];
CGRect fromViewStartFrame = [transitionContext initialFrameForViewController:fromVC];
CGRect toViewFinalFrame = [transitionContext finalFrameForViewController:toVC];
CGRect fromViewFinalFrame = [transitionContext finalFrameForViewController:fromVC];

6.// 開始作畫 Add toVC's view to containerView
// 把toView加進來
[containerView addSubview:toView];

7.//決定一開始的frame
if (self.presenting) {
//這邊直接用預設的
CGSize size = toViewFinalFrame.size;
[toView setFrame:CGRectMake(0, containerFrame.size.height+toViewFinalFrame.size.height, size.width, size.height)];//size一樣。x=0,y=總高度+toView的高
}

//決定最終的frame
if (self.presenting) {
[UIView animateWithDuration:[self transitionDuration:transitionContext] animations:^{
//大小一樣。位置就只要到x=0, y=總高度-toView高度
CGSize size = toViewFinalFrame.size;
CGPoint point = CGPointMake(0, containerFrame.size.height-toViewFinalFrame.size.height);
[toView setFrame:CGRectMake(point.x, point.y, size.width, size.height)];
}completion:^(BOOL finished) {
// 3.Cleaning up and completing the transition.
[transitionContext completeTransition:YES];
}];
}
}

- (NSTimeInterval)transitionDuration:(id<UIViewControllerContextTransitioning> _Nullable)transitionContext {
return 0.2f;
}

@interface SlideLeftCustomSegue : UIStoryboardSegue

// 系統調用prepareForSegue就是調用這裡
- (void)perform{

    UIViewController *srcViewController = (UIViewController *) self.sourceViewController;
    SettingTableViewController *destViewController = (SettingTableViewController *) self.destinationViewController;

    SlideMenuShowTransition *trainstionDelegate = [[SlideMenuShowTransition alloc]init];
    [destViewController setTd:trainstionDelegate];

  //把Presented View Controller的`ModalPresentationStyle屬性改成UIModalPresentationCustom
    [destViewController setModalPresentationStyle:UIModalPresentationCustom];
    
    //設置TransitioningDelegate。這個代理主要用來提供待會兒切換會用到的所有物件。下面會介紹到
    [destViewController setTransitioningDelegate:trainstionDelegate];
    
    //最後呼叫presentViewController，來呼叫UIKit做開始切換
    [srcViewController presentViewController:destViewController animated:YES completion:nil];
}

// present時uikit會從這裡拿資料<過場動畫>
- (id<UIViewControllerAnimatedTransitioning> _Nullable)animationControllerForPresentedController:(UIViewController * _Nonnull)presented presentingController:(UIViewController * _Nonnull)presenting sourceController:(UIViewController * _Nonnull)source {
    SlideMenuAnimator *animator = [[SlideMenuAnimator alloc]init];
    [animator setPresenting:YES];
    return animator;
}

// dismiss時uikit會從這裡拿資料<過場動畫>
- (id<UIViewControllerAnimatedTransitioning> _Nullable)animationControllerForDismissedController:(UIViewController * _Nonnull)dismissed {
    SlideMenuAnimator *animator = [[SlideMenuAnimator alloc]init];
    [animator setPresenting:NO];
    return animator;
}

// UIKit在切換之初從這裡要UIPresentationController
- (UIPresentationController *)presentationControllerForPresentedViewController:
(UIViewController *)presented
                                                      presentingViewController:(UIViewController *)presenting
                                                          sourceViewController:(UIViewController *)source {

    SlideMenuPresentaionController* myPresentation = [[SlideMenuPresentaionController alloc]
                                                initWithPresentedViewController:presented presentingViewController:presenting];

    return myPresentation;
}

// 決定了使用UIModalPresentationCustom這樣的Model切換方式，就可以在這裡直接指定PresentedView的frame
- (CGRect)frameOfPresentedViewInContainerView {
    CGRect presentedViewFrame = CGRectZero;
    CGRect containerBounds = [[self containerView] bounds];

    presentedViewFrame.size = CGSizeMake(floorf(containerBounds.size.width * 0.7),
                                         containerBounds.size.height);
    return presentedViewFrame;
}

// Present的時候可以增加一些Coustom View，靠animateAlongsideTransition來顯示新增的Coustom過場動畫
// 這裡用dimmingView來做Coustom View的例子
- (void)presentationTransitionWillBegin {

    self.dimmingView = [[UIView alloc]init];
    [self.dimmingView setFrame:self.containerView.frame];
    [self.dimmingView setBackgroundColor:[UIColor blackColor]];
    [self.dimmingView setAlpha:0.3f];

    // Add a custom dimming view behind the presented view controller's view
    [[self containerView] addSubview:self.dimmingView];
    [self.dimmingView addSubview:[[self presentedViewController] view]];

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wundeclared-selector"
    UITapGestureRecognizer *dimmingViewSingleTap =
    [[UITapGestureRecognizer alloc] initWithTarget:self.presentingViewController
                                            action:@selector(handleDimmingViewSingleTap)];
#pragma clang diagnostic pop
    [self.dimmingView addGestureRecognizer:dimmingViewSingleTap];

    // Fade in the dimming view during the transition.
    [self.dimmingView setAlpha:0.0];
    // Use the transition coordinator to set up the animations.
    [[[self presentingViewController] transitionCoordinator] animateAlongsideTransition:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {
        [self.dimmingView setAlpha:0.55];
    } completion:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {

    }];
}

- (void)dismissalTransitionWillBegin {
    [[[self presentingViewController] transitionCoordinator] animateAlongsideTransition:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {
        [self.dimmingView setAlpha:0.0];
    } completion:^(id<UIViewControllerTransitionCoordinatorContext>  _Nonnull context) {

    }];
}

@interface SlideMenuAnimator : NSObject<UIViewControllerAnimatedTransitioning>
@property (nonatomic) Boolean presenting;
@end

// 這裡UIKit會給我們兩個View，包在transitionContext裡面，只要取出來玩就好了
// 這裡是真的作動畫的地方
- (void)animateTransition:(id<UIViewControllerContextTransitioning> _Nonnull)transitionContext {

    // Get the set of relevant objects.
    UIView *containerView = [transitionContext containerView];
    UIViewController *fromVC = [transitionContext
                                viewControllerForKey:UITransitionContextFromViewControllerKey];
    UIViewController *toVC   = [transitionContext
                                viewControllerForKey:UITransitionContextToViewControllerKey];

    UIView *toView = [transitionContext viewForKey:UITransitionContextToViewKey];
    UIView *fromView = [transitionContext viewForKey:UITransitionContextFromViewKey];

    // Set up some variables for the animation.
    //CGRect containerFrame = containerView.frame;
    //CGRect toViewStartFrame = [transitionContext initialFrameForViewController:toVC];
    CGRect fromViewStartFrame = [transitionContext initialFrameForViewController:fromVC];
    CGRect toViewFinalFrame = [transitionContext finalFrameForViewController:toVC];
    CGRect fromViewFinalFrame = [transitionContext finalFrameForViewController:fromVC];

    // 3. Add toVC's view to containerView
    [containerView addSubview:toView];
    if (self.presenting) {
        [toView setFrame:CGRectOffset(toViewFinalFrame, -1*toViewFinalFrame.size.width, 0)];
    }else {
        [fromView setFrame:fromViewStartFrame];
    }

    // Creating the animations using Core Animation or UIView animation methods.
    [UIView animateWithDuration:[self transitionDuration:transitionContext] animations:^{
        if (self.presenting) {
            toView.frame = toViewFinalFrame;
        }else {
            fromView.frame = CGRectOffset(fromViewFinalFrame, -1*fromViewFinalFrame.size.width, 0);
        }
    } completion:^(BOOL finished) {
        // 3.Cleaning up and completing the transition.
        [transitionContext completeTransition:YES];
    }];

}