text:
package com.lee.main.view.screenscroll;

import android.content.Context;
import android.graphics.Bitmap;
import android.graphics.Canvas;
import android.graphics.PixelFormat;
import android.graphics.PointF;
import android.graphics.Rect;
import android.graphics.drawable.Drawable;
import android.support.v4.view.ViewCompat;
import android.support.v4.widget.EdgeEffectCompat;
import android.util.AttributeSet;
import android.view.Gravity;
import android.view.MotionEvent;
import android.view.VelocityTracker;
import android.view.View;
import android.view.ViewConfiguration;
import android.view.ViewGroup;
import android.view.WindowManager;
import android.view.animation.Animation;
import android.view.animation.Animation.AnimationListener;
import android.view.animation.Interpolator;
import android.view.animation.TranslateAnimation;
import android.widget.ImageView;
import android.widget.Scroller;

import com.noobyang.log.LogUtil;

import java.util.HashMap;

/**
 * 分页 滑动
 * <p/>
 * Created by LiYang on 2016/6/16.
 */
public class ScreenScrollLayout extends ViewGroup implements OnDataChangeListener {

    private static final int FADE_ALPHA_INT_MAX = 255; // 255 means fully opaque
    private static final int FADE_ALPHA_INT_MIN = 0; // 0 means fully transparent
    private static final int FADE_ALPHA_INT = 180; // 0 means fully transparent, and 255 means fully opaque

    private static final float FADE_ALPHA_FLOAT = 0.8f; // 0 means fully transparent, and 1 means fully opaque

    private static final int ANIMATION_CHANGE_POSITION_CROSS_SCREEN_DURATION = 800;
    private static final int ANIMATION_CHANGE_POSITION_NEIGHBOR_DURATION = 500;

    private static final int ANIMATION_DROP_DURATION = 150;
    private static final int ANIMATION_SHOW_DURATION = 650;

    private static final int MIN_FLING_ANIMATION_DURATION = 200;
    private static final int MAX_FLING_ANIMATION_DURATION = 400;

    private static final int ANIMATION_DRAG_CHANGE_SCREEN_DURATION = 500;

    private AbsAdapter adapter;
    /**
     * 页面滚动的Scroll管理器
     */
    private Scroller scroller;

    private EdgeEffectCompat edgeGlowLeft;
    private EdgeEffectCompat edgeGlowRight;

    /**
     * 用户滑动的最小距离
     */
    private int touchSlop;

    // 行、列间距
    private int rowSpace = 0;
    private int colSpace = 0;

    // 边距
    private int leftPadding = 0;
    private int topPadding = 0;
    private int rightPadding = 0;
    private int bottomPadding = 0;

    // Layout 尺寸
    private int layoutWidth = 0;
    private int layoutHeight = 0;

    // Item 尺寸
    private int itemWidth = 0;
    private int itemHeight = 0;

    // item 图片尺寸一半,用于松下手指时的动画
    private int halfBitmapWidth;
    private int halfBitmapHeight;

    /**
     * 当前屏数,默认为第一屏幕
     */
    private int currentScreenNum = 0;
    /**
     * 总屏数
     */
    private int totalScreenSize = 0;
    /**
     * 每一屏幕的 item 个数
     */
    private int screenItemCount = 4;
    // 每一屏幕的行、列数
    private int rowCount = 2;
    private int colCount = 2;

    //手势落下的X坐标
    private float downX = 0f;
    //手势落下的Y坐标
    private float downY = 0f;

    //上次滑动坐标位置
    private float lastMotionX;
    private float lastMotionY;

    /*
     * 负责随手势显示拖拽View
     */
    private WindowManager windowManager;
    private WindowManager.LayoutParams windowParams;
    /**
     * 拖动点的X坐标(加上当前屏数 * layoutWidth)
     */
    private int dragPointX;
    /**
     * 拖动点的Y坐标
     */
    private int dragPointY;
    /**
     * X坐标偏移量
     */
    private float dragOffsetX;
    /**
     * Y坐标偏移量
     */
    private float dragOffsetY;
    /**
     * 拖拽点的位置编号,每个Item对应一个位置编号,自增
     */
    private int dragPosition = -1;
    /**
     * 临时交换位置的编号
     */
    private int oldChangPosition = -1;
    /**
     * 拖拽Item的子View
     */
    private ImageView dragImageView;

    enum DragMode{
        /**
         * 初始状态
         */
        DRAG_MODE_IDLE,
        /**
         * 拖动
         */
        DRAG_MODE_DRAG,
        /**
         * 滑动
         */
        DRAG_MODE_SLIDE,
    }
    /**
     * 拖动状态
     */
    private DragMode dragMode = DragMode.DRAG_MODE_IDLE;

    private enum SlideState {
        /**
         * 正常状态
         */
        SLIDE_STATE_NORMAL,
        /**
         * 向左滑动
         */
        SLIDE_STATE_LEFT_ING,
        /**
         * 向右滑动
         */
        SLIDE_STATE_RIGHT_ING,
    }
    /**
     * 滑动状态
     */
    private SlideState slideState = SlideState.SLIDE_STATE_NORMAL;

    private OnChangeScreenListener changeScreenListener;
    private OnScreenSizeChangeListener screenSizeChangeListener;
    private OnTouchChangeListener touchChangeListener;
    private OnItemClickListener itemClickListener;

    private boolean isForbidDrag = false;

    private VelocityTracker velocityTracker;

    private float effectVelocity;
    // 触发切屏距离
    private int dragChangeScreenDistance = 0;
    private int scrollChangeScreenDistance = 0;

    public ScreenScrollLayout(Context context) {
        this(context, null);
    }

    public ScreenScrollLayout(Context context, AttributeSet attrs) {
        this(context, attrs, 0);
    }

    public ScreenScrollLayout(Context context, AttributeSet attrs, int defStyle) {
        super(context, attrs, defStyle);
        init(context);
    }

    private void init(Context context) {
        scroller = new Scroller(context);
        touchSlop = ViewConfiguration.get(getContext()).getScaledTouchSlop();

        effectVelocity = 1.5f;

        edgeGlowLeft = new EdgeEffectCompat(context);
        edgeGlowRight = new EdgeEffectCompat(context);
        setWillNotDraw(false);
        if (adapter != null) {
            refreshView();
        }

        windowParams = new WindowManager.LayoutParams();
        windowParams.gravity = Gravity.TOP | Gravity.LEFT;
        windowParams.height = LayoutParams.WRAP_CONTENT;
        windowParams.width = LayoutParams.WRAP_CONTENT;
        windowParams.flags = WindowManager.LayoutParams.FLAG_NOT_FOCUSABLE
                | WindowManager.LayoutParams.FLAG_NOT_TOUCHABLE
                | WindowManager.LayoutParams.FLAG_KEEP_SCREEN_ON
                | WindowManager.LayoutParams.FLAG_LAYOUT_IN_SCREEN;
        windowParams.format = PixelFormat.TRANSLUCENT;
        windowParams.windowAnimations = 0;
        windowParams.alpha = FADE_ALPHA_FLOAT;

        windowManager = (WindowManager) getContext().getSystemService(
                Context.WINDOW_SERVICE);
    }

    /**
     * 设置禁止拖动
     * @param isForbidDrag true 禁止拖动
     */
    public void setForbidDrag(boolean isForbidDrag) {
        this.isForbidDrag = isForbidDrag;
    }

    /**
     * 设置 adapter
     * @param adapter adapter
     */
    public void setAdapter(AbsAdapter adapter) {
        this.adapter = adapter;
        this.adapter.setOnDataChangeListener(this);
    }

    /**
     * 获取 adapter
     * @return adapter
     */
    public AbsAdapter getSaAdapter() {
        return adapter;
    }

    /**
     * 设置一屏显示的行、列数
     * @param rowCount 行数
     * @param colCount 列数
     */
    public void setScreenCount(int rowCount, int colCount) {
        this.rowCount = rowCount;
        this.colCount = colCount;
        screenItemCount = colCount * rowCount;
    }

    /**
     * 设置 item 间距
     * @param row 行间距
     * @param col 列间距
     */
    public void setItemSpace(int row, int col) {
        rowSpace = row;
        colSpace = col;
    }

    /**
     * 设置 Layout 的边距
     * @param left 左边距
     * @param top 上边距
     * @param right 右边距
     * @param bottom 下边距
     */
    public void setLayoutPadding(int left, int top, int right, int bottom) {
        leftPadding = left;
        topPadding = top;
        rightPadding = right;
        bottomPadding = bottom;
    }

    /**
     * 获取当前屏数
     * @return 当前屏数
     */
    public int getCurrentScreenNum() {
        return currentScreenNum;
    }

    /**
     * 获取总屏数
     * @return 总屏数
     */
    public int getTotalScreenSize() {
        return totalScreenSize;
    }

    /**
     * 设置屏数变化监听
     * @param screenSizeChangeListener 屏数变化监听
     */
    public void setOnScreenSizeChangeListener(OnScreenSizeChangeListener screenSizeChangeListener) {
        this.screenSizeChangeListener = screenSizeChangeListener;
    }

    private void dealScreenSizeChange(int screenNum, boolean isAdd) {
        if (screenSizeChangeListener != null) {
            screenSizeChangeListener.onScreenSizeChange(screenNum, isAdd);
        }
    }

    /**
     * 设置切屏监听
     * @param changeScreenListener 切屏监听
     */
    public void setOnChangeScreenListener(OnChangeScreenListener changeScreenListener) {
        this.changeScreenListener = changeScreenListener;
    }

    private void dealChangeScreen(int fromScreen, int toScreen) {
        if (changeScreenListener != null) {
            changeScreenListener.onChangeScreen(fromScreen, toScreen);
        }
    }

    /**
     * 设置 touch 事件监听
     * @param touchChangeListener touch 事件监听
     */
    public void setOnTouchChangeListener(OnTouchChangeListener touchChangeListener) {
        this.touchChangeListener = touchChangeListener;
    }

    private void dealTouchChange(boolean isHandled) {
        if (touchChangeListener != null) {
            touchChangeListener.onHandledTouch(isHandled);
        }
    }

    /**
     * 设置 tem 点击事件监听
     * @param itemClickListener tem 点击事件监听
     */
    public void setOnItemClickListener(OnItemClickListener itemClickListener) {
        this.itemClickListener = itemClickListener;
    }

    private void dealItemClick(int position) {
        if (itemClickListener != null) {
            itemClickListener.onItemClick(position);
        }
    }

    /**
     * 刷新所有 view
     */
    public void refreshView() {
        if (adapter != null) {
            removeAllViews();
            int count = adapter.getCount();
            for (int i = 0; i < count; i++) {
                this.addView(getView(i));
            }
            requestLayout();
            if (currentScreenNum >= totalScreenSize) {
                currentScreenNum = totalScreenSize - 1;
                scrollTo(currentScreenNum * layoutWidth, 0);
            }
        }
    }

    /**
     * 可见时显示的动画
     */
    public void showVisibleAnimation() {
        int startIndex = currentScreenNum * screenItemCount;
        int endIndex = startIndex;
        if (totalScreenSize > currentScreenNum) {
            endIndex = startIndex + screenItemCount;
        } else {
            if (adapter != null) {
                endIndex = adapter.getCount();
            }
        }

        for (int i=startIndex; i<endIndex; i++) {
            View view = getChildAt(i);
            if (view != null) {
                view.clearAnimation();
                Animation animation = getVisibleAnimation(startIndex, i);
                LogUtil.d("getVisibleAnimation i = " + i + "---view = " + view + "---animation = " + animation);
                if (animation != null) {
                    view.startAnimation(animation);
                }
            }
        }
    }

    /**
     * 可见时显示动画
     */
    private Animation getVisibleAnimation(int startIndex, int position) {
        TranslateAnimation animation = null;
        switch (position-startIndex) {
            case 0:
                animation = new TranslateAnimation( - itemWidth, 0, - itemHeight, 0);
                animation.setStartOffset(0);
                break;

            case 1:
                animation = new TranslateAnimation(itemWidth, 0, - itemHeight, 0);
                animation.setStartOffset(140);
                break;

            case 2:
                animation = new TranslateAnimation( - itemWidth, 0, itemHeight, 0);
                animation.setStartOffset(210);
                break;

            case 3:
                animation = new TranslateAnimation(itemWidth, 0, itemHeight, 0);
                animation.setStartOffset(70);
                break;

            default:
                LogUtil.e("error type");
                break;
        }
        if (animation != null) {
            animation.setInterpolator(interpolator);
            animation.setDuration(ANIMATION_SHOW_DURATION);
            animation.setFillAfter(true);
        }
        return animation;
    }

    private Interpolator interpolator = new Interpolator() {

        @Override
        public float getInterpolation(float input) {
            if ((input*=2) < 1.0f) {
                return 0.5f * input * input * input;
            }
            input -= 2;
            return 0.5f*input*input*input + 1;
        }
    };

    private View getView(final int position) {
        View view = null;
        if (adapter != null) {
            view = adapter.getView(position);
            view.setOnLongClickListener(new OnLongClickListener() {
                @Override
                public boolean onLongClick(View view) {
                    return dealItemLongClick(view);
                }
            });
        }
        return view;
    }

    private boolean dealItemLongClick(View view) {
        if (isForbidDrag) {
            return false;
        }
        oldChangPosition = dragPosition = viewToPosition(view);
        LogUtil.d("dealItemLongClick view = " + view + "---oldChangPosition = " + oldChangPosition);
        if (scroller.isFinished() && dragMode != DragMode.DRAG_MODE_DRAG) {
            dragMode = DragMode.DRAG_MODE_DRAG;
            //fadeChildren();
            dealTouchChange(true);

            view.destroyDrawingCache();
            view.setDrawingCacheEnabled(true);
            Bitmap bitmap = Bitmap.createBitmap(view.getDrawingCache());

            view.clearAnimation();
            view.setVisibility(View.INVISIBLE);

            startDrag(bitmap, (int) (lastMotionX), (int) (lastMotionY), view);
            return true;
        }
        return false;
    }

    private void dealItemClick(float x, float y) {
        if (Math.abs(downX - x) <= touchSlop &&
                Math.abs(downY - y) <= touchSlop) {
            int position = pointToPosition(downX, downY);
            if (position != -1) {
                dealItemClick(position);
            }
        }
    }

    /**
     * 使所有的 Item 暗掉
     */
    private void fadeChildren() {
        final int count = getChildCount();
        for (int i = count-1; i >= 0; i--) {
            setItemViewBackgroundAlpha(getChildAt(i), FADE_ALPHA_INT);
        }
    }

    /**
     * 恢复 Item 的透明度
     */
    private void recoverChildren() {
        final int count = getChildCount() - 1;
        for (int i = count; i >= 0; i--) {
            setItemViewBackgroundAlpha(getChildAt(i), FADE_ALPHA_INT_MAX);
        }
    }

    private void setItemViewBackgroundAlpha(View view, int alpha) {
        if (view == null) {
            return;
        }
        Drawable drawable = view.getBackground();
        if (drawable != null) {
            drawable.setAlpha(alpha);
        }
    }

    /**
     * 获取去子 View 的索引
     * @param view 子 View
     * @return 子 View 的索引
     */
    public int getChildViewIndex(View view) {
        if (view != null) {
            final int childCount = getChildCount();
            for (int i = 0; i < childCount; i++) {
                if (view == getChildAt(i)) {
                    return i;
                }
            }
        }
        return -1;
    }

    @Override
    public void onDataChange() {
        refreshView();
    }

    @Override
    protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
        super.onMeasure(widthMeasureSpec, heightMeasureSpec);
        layoutWidth = MeasureSpec.getSize(widthMeasureSpec);
        layoutHeight = MeasureSpec.getSize(heightMeasureSpec);
        // 获取可用的尺寸
        int usableWidth = getUsableWidth(layoutWidth);
        int usableHeight = getUsableHeight(layoutHeight);
        dragChangeScreenDistance = Math.round(layoutWidth / 8);
        scrollChangeScreenDistance = Math.round(layoutWidth / 4);

        // measure child
        int childWidth = usableWidth / colCount;
        int childHeight = usableHeight / rowCount;
        measureChildView(childWidth, childHeight);

        scrollTo(currentScreenNum * layoutWidth, 0);
    }

    private int getUsableWidth(int layoutWidth) {
        return layoutWidth - leftPadding - rightPadding - (colCount - 1) * colSpace;
    }

    private int getUsableHeight(int layoutHeight) {
        return layoutHeight - topPadding - bottomPadding - (rowCount - 1) * rowSpace;
    }

    private void measureChildView(int childWidth, int childHeight) {
        int specWidth = MeasureSpec.makeMeasureSpec(childWidth, MeasureSpec.EXACTLY);
        int specHeight = MeasureSpec.makeMeasureSpec(childHeight, MeasureSpec.EXACTLY);
        final int count = getChildCount();
        for (int i = 0; i < count; i++) {
            View child = getChildAt(i);
            int childWidthSpec = getChildMeasureSpec(specWidth, 0, childWidth);
            int childHeightSpec = getChildMeasureSpec(specHeight, 0, childHeight);
            child.measure(childWidthSpec, childHeightSpec);
        }
    }

    @Override
    protected void onLayout(boolean changed, int l, int t, int r, int b) {
        LogUtil.d("onLayout changed = " + changed);
        layoutChildView();
    }

    private void layoutChildView() {
        final int childCount = getChildCount();
        for (int i = 0; i < childCount; i++) {
            final View childView = getChildAt(i);
            if (childView.getVisibility() != View.GONE) {
                itemWidth = childView.getMeasuredWidth();
                itemHeight = childView.getMeasuredHeight();
                int page = i / screenItemCount;
                int row = i / colCount % rowCount;
                int col = i % colCount;
                int left = leftPadding + page * layoutWidth + col * (colSpace + itemWidth);
                int top = topPadding + row * (rowSpace + itemHeight);
                childView.layout(left, top, left + itemWidth, top + itemHeight);
            } else {
                LogUtil.e("childView is gone");
            }
        }
    }

    @Override
    public void addView(View child, int index, LayoutParams params) {
        child.setClickable(true);
        if (child.getVisibility() != View.VISIBLE) {
            child.setVisibility(View.VISIBLE);
        }
        super.addView(child, index, params);
        dealTotalScreenSizeChange(true);
    }

    @Override
    public void removeView(View view) {
        super.removeView(view);
        dealTotalScreenSizeChange(false);
    }

    @Override
    public void removeViewAt(int index) {
        super.removeViewAt(index);
        dealTotalScreenSizeChange(false);
    }

    private void dealTotalScreenSizeChange(boolean isAdd) {
        int pages = (int) Math.ceil(getChildCount() * 1.0 / screenItemCount);
        if (pages < totalScreenSize) {
            dealScreenSizeChange(totalScreenSize, isAdd);
        }
        totalScreenSize = pages;
    }

    @Override
    public void computeScroll() {
        if (scroller.computeScrollOffset()) {
            dealScrollOffset();
        }
    }

    @Override
    protected void onDraw(Canvas canvas) {
        super.onDraw(canvas);
        boolean needsInvalidate = false;
        if (!edgeGlowLeft.isFinished()) {
            final int restoreCount = canvas.save();
            final int scrollX = getScrollX();
            final int width = getWidth();
            final int height = getHeight();
            canvas.rotate(270, 0, 0);
            canvas.translate(-height, scrollX);
            edgeGlowLeft.setSize(height, width);
            needsInvalidate = edgeGlowLeft.draw(canvas);
            canvas.restoreToCount(restoreCount);
        }
        if (!edgeGlowRight.isFinished()) {
            final int restoreCount = canvas.save();
            final int scrollX = getScrollX();
            final int width = getWidth();
            final int height = getHeight();
            canvas.rotate(90, 0, 0);
            canvas.translate(0, -scrollX - width);
            edgeGlowRight.setSize(height, width);
            needsInvalidate = edgeGlowRight.draw(canvas);
            canvas.restoreToCount(restoreCount);
        }

        if (needsInvalidate) {
            ViewCompat.postInvalidateOnAnimation(this);
        }
    }

    @Override
    protected void onVisibilityChanged(View changedView, int visibility) {
        super.onVisibilityChanged(changedView, visibility);
        LogUtil.d("onVisibilityChanged visibility = " + visibility);
        if (visibility == GONE) {
            cancelTouch();
        }
    }

    @Override
    public void onWindowFocusChanged(boolean hasWindowFocus) {
        super.onWindowFocusChanged(hasWindowFocus);
        LogUtil.d("onWindowFocusChanged = hasWindowFocus = " + hasWindowFocus);
        if (!hasWindowFocus) {
            cancelTouch();
        }
    }

    private void cancelTouch() {
        LogUtil.d("cancelTouch dragImageView = " + dragImageView + "---dragMode = " + dragMode);
        showDragApp();

        edgeGlowRight.onRelease();
        edgeGlowLeft.onRelease();

        clearAppAnimation();
        removeDragView();

        dealTouchChange(false);
        recycleVelocityTracker();
    }

    private boolean isIntercept = false;
    @Override
    public boolean onInterceptTouchEvent(MotionEvent event) {
        if (!hasWindowFocus()) {
            LogUtil.d("onInterceptTouchEvent hasWindowFocus = false");
            return true;
        }
        int action = event.getAction() & MotionEvent.ACTION_MASK;
        LogUtil.d("onInterceptTouchEvent action = " + action + "---isIntercept = " + isIntercept);
        switch (action) {
            case MotionEvent.ACTION_DOWN:
                interceptDown(event);
                obtainVelocityTracker();
                addMovement(event);
                break;

            case MotionEvent.ACTION_MOVE:
                interceptMove(event);
                addMovement(event);
                break;

            case MotionEvent.ACTION_UP:
                dealClick(event);
            case MotionEvent.ACTION_CANCEL:
                dealDrop(event);
                dealTouchChange(false);
                recycleVelocityTracker();
                break;

            default:
                break;
        }
        return isIntercept;
    }

    private void interceptDown(MotionEvent event) {
        isIntercept = false;
        final float x = event.getX();
        final float y = event.getY();
        abortAnimation();
        slideState = SlideState.SLIDE_STATE_NORMAL;
        dragOffsetX = event.getRawX() - x;
        dragOffsetY = event.getRawY() - y;

        lastMotionX = x;
        lastMotionY = y;
        downX = x;
        downY = y;
    }

    private void interceptMove(MotionEvent event) {
        final float x = event.getX();
        int deltaX = Math.round(lastMotionX - x);
        if (Math.abs(deltaX) > touchSlop) {
            if (deltaX > 0) {
                setSlideState(SlideState.SLIDE_STATE_LEFT_ING);
            } else {
                setSlideState(SlideState.SLIDE_STATE_RIGHT_ING);
            }
            dealTouchChange(true);
            isIntercept = true;
        }
    }

    private void setSlideState(SlideState slideState) {
        this.slideState = slideState;
    }

    private void dealClick(MotionEvent event) {
        final float x = event.getX();
        final float y = event.getY();
        if (dragMode == DragMode.DRAG_MODE_DRAG){
            showDragApp();
        } else {
            dealItemClick(x, y);
        }
    }

    private void obtainVelocityTracker() {
        LogUtil.d("obtainVelocityTracker");
        if (velocityTracker == null) {
            velocityTracker = VelocityTracker.obtain();
        } else {
            velocityTracker.clear();
            velocityTracker.recycle();
            velocityTracker = VelocityTracker.obtain();
        }
    }

    private void addMovement(MotionEvent event) {
        if (velocityTracker != null) {
            velocityTracker.addMovement(event);
        }
    }

    private float getXVelocity() {
        if (velocityTracker != null) {
            velocityTracker.computeCurrentVelocity(1000);
            return velocityTracker.getXVelocity() / 1000;
        }
        return 0f;
    }

    private void recycleVelocityTracker() {
        LogUtil.d("recycleVelocityTracker");
        if (velocityTracker != null) {
            velocityTracker.clear();
            velocityTracker.recycle();
            velocityTracker = null;
        }
    }

    private void dealDrop(MotionEvent event) {
        if (dragImageView != null) {
            clearAppAnimation();
            removeDragView();
            showDropAnimation(event);
        }
    }

    @Override
    public boolean onTouchEvent(MotionEvent event) {
        if (!hasWindowFocus()) {
            LogUtil.d("onTouchEvent hasWindowFocus = false");
            return true;
        }
        int action = event.getAction() & MotionEvent.ACTION_MASK;
        boolean needsInvalidate = false;
        switch (action) {
            case MotionEvent.ACTION_DOWN:
                dealDown(event);
                obtainVelocityTracker();
                addMovement(event);
                break;

            case MotionEvent.ACTION_MOVE:
                if (isIntercept) {
                    needsInvalidate = dealMove(event);
                } else {
                    interceptMove(event);
                }
                addMovement(event);
                break;

            case MotionEvent.ACTION_UP:
            case MotionEvent.ACTION_CANCEL:
                needsInvalidate = dealUp(event);
                dealDrop(event);
                recycleVelocityTracker();
                break;

            default:
                break;
        }
        if (needsInvalidate) {
            ViewCompat.postInvalidateOnAnimation(this);
        }
        return true;
    }

    private void dealDown(MotionEvent event) {
        final float x = event.getX();
        final float y = event.getY();
        abortAnimation();
        dragOffsetX = event.getRawX() - x;
        dragOffsetY = event.getRawY() - y;

        lastMotionX = x;
        lastMotionY = y;
        downX = x;
        downY = y;
    }

    private void abortAnimation() {
        if (!scroller.isFinished()) {
            LogUtil.d("abortAnimation scroll not isFinished");
            scroller.abortAnimation();
            dealScrollOffset();
        }
    }

    private void dealScrollOffset() {
        scrollTo(scroller.getCurrX(), scroller.getCurrY());
        postInvalidate();
        if (scroller.isFinished()) {
            slideState = SlideState.SLIDE_STATE_NORMAL;
        }
    }

    private boolean dealMove(MotionEvent event) {
        final float x = event.getX();
        final float y = event.getY();
        boolean needsInvalidate = false;

        if (dragMode == DragMode.DRAG_MODE_DRAG) {// 拖动
            dealDrag(x, y);
        } else {// 滑动
            int deltaX = Math.round(lastMotionX - x);
            LogUtil.d("dealMove deltaX = " + deltaX);
            if (isCanMove(deltaX)) {
                scrollBy(deltaX, 0);
                lastMotionX = x;
                dragMode = DragMode.DRAG_MODE_SLIDE;
            } else {
                if (getScrollX() <= 0 && deltaX < 0) {
                    needsInvalidate = edgeGlowLeft.onPull(Math.abs((float) deltaX / getWidth()), 1.f - event.getY() / getHeight());
                    if (!edgeGlowRight.isFinished()) {
                        edgeGlowRight.onRelease();
                    }
                } else if (getScrollX() >= (totalScreenSize - 1) * layoutWidth && deltaX > 0) {
                    needsInvalidate = edgeGlowRight.onPull(Math.abs((float) deltaX / getWidth()), event.getY() / getHeight());
                    if (!edgeGlowLeft.isFinished()) {
                        edgeGlowLeft.onRelease();
                    }
                }
            }
        }
        return needsInvalidate;
    }

    private boolean dealUp(MotionEvent event) {
        if (dragMode == DragMode.DRAG_MODE_DRAG) {
            showDragApp();
        } else {
            dealFling(event);
        }
        downX = 0;
        downY = 0;
        dealTouchChange(false);
        return edgeGlowLeft.onRelease() | edgeGlowRight.onRelease();
    }

    private void dealFling(MotionEvent event) {
        float xVelocity = getXVelocity();
        float distance = downX - event.getRawX();
        LogUtil.d("dealFling slideState = " + slideState + "---xVelocity = " + xVelocity + "---distance = " + distance);
        if (slideState == SlideState.SLIDE_STATE_LEFT_ING) {
            if ((distance > scrollChangeScreenDistance || xVelocity > effectVelocity) && (currentScreenNum < totalScreenSize - 1)) {
                flingChangeScreen(currentScreenNum + 1, xVelocity);
            } else {
                flingToOriginal(xVelocity);
            }
        } else if (slideState == SlideState.SLIDE_STATE_RIGHT_ING) {
            if ((distance < -scrollChangeScreenDistance || xVelocity < -effectVelocity) && (currentScreenNum > 0)) {
                flingChangeScreen(currentScreenNum - 1, xVelocity);
            } else {
                flingToOriginal(xVelocity);
            }
        } else {
            flingToOriginal(xVelocity);
        }
    }

    private void flingChangeScreen(int destScreenNum, float xVelocity) {
        destScreenNum = Math.max(0, Math.min(destScreenNum, totalScreenSize - 1));// 有效性处理
        final int destScreenX = destScreenNum * getWidth();
        final int currentScrollX = getScrollX();
        if (currentScrollX != destScreenX) {
            final int delta = destScreenX - currentScrollX;
            scroller.startScroll(currentScrollX, 0, delta, 0, getFlingDuration(delta, xVelocity));
            postInvalidate();
            currentScreenNum = destScreenNum;
            dealChangeScreen(currentScreenNum, destScreenNum);
        }
    }

    private void flingToOriginal(float xVelocity) {
        final int destScreenX = currentScreenNum * getWidth();
        final int currentScrollX = getScrollX();
        if (currentScrollX != destScreenX) {
            final int delta = destScreenX - currentScrollX;
            scroller.startScroll(currentScrollX, 0, delta, 0, getFlingDuration(delta, xVelocity));
            postInvalidate();
        }
    }

    private int getFlingDuration(int distance, float xVelocity) {
        int duration = MAX_FLING_ANIMATION_DURATION;
        if (Math.abs(xVelocity) != 0) {
            int temp = Math.round(Math.abs(distance / xVelocity)) * 4;
            duration = Math.max(MIN_FLING_ANIMATION_DURATION, temp);
        }
        LogUtil.d("getFlingDuration duration = " + duration + "---distance = " + distance + "---xVelocity = " + xVelocity);
        return Math.min(MAX_FLING_ANIMATION_DURATION, duration);
    }

    private Rect frame = new Rect();
    private int pointToPosition(float x, float y) {
        float actualX = x + currentScreenNum * getWidth();
        final int count = getChildCount();
        for (int i = count - 1; i >= 0; i--) {
            final View child = getChildAt(i);
            child.getHitRect(frame);
            if (frame.contains(Math.round(actualX), Math.round(y))) {
                return i;
            }
        }
        return -1;
    }

    private int viewToPosition(View view) {
        final int count = getChildCount();
        for (int i = count - 1; i >= 0; i--) {
            if (view.equals(getChildAt(i))) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 滑动合法性的判断,防止滑动到空白区域
     */
    private boolean isCanMove(int deltaX) {
        if (getScrollX() <= 0 && deltaX < 0) {
            return false;
        }
        if (getScrollX() >= (totalScreenSize - 1) * layoutWidth && deltaX > 0) {
            return false;
        }
        return true;
    }

    /**
     * 开始拖动
     */
    private void startDrag(Bitmap bitmap, int x, int y, View itemView) {
        dragPointX = x - itemView.getLeft() + currentScreenNum * layoutWidth;
        dragPointY = y - itemView.getTop();
        windowParams.x = Math.round(x - dragPointX + dragOffsetX);
        windowParams.y = Math.round(y - dragPointY + dragOffsetY);

        ImageView imageView = new ImageView(getContext());
        imageView.setImageBitmap(bitmap);
        windowManager.addView(imageView, windowParams);
        dragImageView = imageView;

        halfBitmapWidth = bitmap.getWidth() / 2;
        halfBitmapHeight = bitmap.getHeight() / 2;
    }

    /**
     * 根据手势绘制不断变化位置的 dragView
     */
    private void dealDrag(float x, float y) {
        if (dragImageView != null) {
            windowParams.x = Math.round(x - dragPointX + dragOffsetX);
            windowParams.y = Math.round(y - dragPointY + dragOffsetY);
            windowManager.updateViewLayout(dragImageView, windowParams);
        }
        int tempPosition = pointToPosition(x, y);
        if (tempPosition != -1) {
            dragPosition = tempPosition;
        }
        LogUtil.d("dealDrag oldChangPosition = " + oldChangPosition + "---dragPosition = " + dragPosition);
        View view = getChildAt(oldChangPosition);
        if (view == null) {
            LogUtil.e("dealDrag view is null");
            showDragApp();
            return;
        }

        view.setVisibility(View.INVISIBLE);
        if (oldChangPosition != dragPosition) {
            View dragView = getChildAt(oldChangPosition);
            movePositionAnimation(oldChangPosition, dragPosition);
            removeViewAt(oldChangPosition);
            addView(dragView, dragPosition);
            dragView.setVisibility(View.INVISIBLE);

            getSaAdapter().exchange(oldChangPosition, dragPosition);
            oldChangPosition = dragPosition;
        }

        // 实现切换屏幕
        if (x > getRight() - dragChangeScreenDistance
                && currentScreenNum < totalScreenSize - 1 && scroller.isFinished()
                && x - downX > 10) {
            dragChangeScreen(currentScreenNum + 1);
        } else if (x - getLeft() < dragChangeScreenDistance
                && currentScreenNum > 0 && scroller.isFinished() && x - downX < -10) {
            dragChangeScreen(currentScreenNum - 1);
        } else {
            LogUtil.e("drag to change screen failure");
        }
    }

    private void dragChangeScreen(int destScreenNum) {
        destScreenNum = Math.max(0, Math.min(destScreenNum, getChildCount() - 1));// 有效性处理
        final int destScreenX = destScreenNum * getWidth();
        final int currentScrollX = getScrollX();
        if (currentScrollX != destScreenX) {
            final int delta = destScreenX - currentScrollX;
            scroller.startScroll(currentScrollX, 0, delta, 0, ANIMATION_DRAG_CHANGE_SCREEN_DURATION);
            postInvalidate();
            currentScreenNum = destScreenNum;
            dealChangeScreen(currentScreenNum, destScreenNum);
        }
    }

    /**
     * 执行换位置动画
     */
    private void movePositionAnimation(int oldP, int newP) {
        LogUtil.d("movePositionAnimation oldP = " + oldP + "---newP = " + newP);
        int moveNum = newP - oldP;
        boolean isCrossScreen = false;
        boolean isBackwards = false;
        if (moveNum != 0 && !isMovingFastConflict(moveNum)) {
            int absMoveNum = Math.abs(moveNum);
            for (int i = Math.min(oldP, newP) + 1; i <= Math.max(oldP, newP); i++) {
                if (i % screenItemCount == 0) {
                    isCrossScreen = true;
                }
            }
            if (isCrossScreen) {
                isBackwards = moveNum >= 0;
            }
            // 循环遍历实现换位置动画
            for (int i = 0; i < absMoveNum; i++) {
                int holdPosition = (moveNum > 0) ? oldP + 1 : oldP - 1;
                View view = getChildAt(holdPosition);
                if (view != null) {
                    view.startAnimation(animationPositionToPosition(oldP,
                            holdPosition, isCrossScreen, isBackwards));
                }
                oldP = holdPosition;
            }
        }
    }

    /**
     * 判断滑动的一系列动画是否有冲突
     */
    private boolean isMovingFastConflict(int moveNum) {
        int itemsMoveNum = Math.abs(moveNum);
        int temp = dragPosition;
        for (int i = 0; i < itemsMoveNum; i++) {
            int holdPosition = moveNum > 0 ? temp + 1 : temp - 1;
            if (animationMap.containsKey(holdPosition)) {
                return true;
            }
            temp = holdPosition;
        }
        return false;
    }

    /**
     * 互换位置动画
     */
    private Animation animationPositionToPosition(int oldP, int newP, boolean isCrossScreen, boolean isBackwards) {
        PointF oldPF = positionToPoint(oldP);
        PointF newPF = positionToPoint(newP);
        TranslateAnimation animation;

        if (oldP != 0 && (oldP + 1) % screenItemCount == 0 && isBackwards && isCrossScreen) {// 向后跨屏滑动
            LogUtil.d("向后跨屏滑动 oldP = " + oldP + "---newP = " + newP);
            animation = new TranslateAnimation(layoutWidth - oldPF.x, 0, dragChangeScreenDistance - layoutHeight, 0);
            animation.setDuration(ANIMATION_CHANGE_POSITION_CROSS_SCREEN_DURATION);
        } else if (oldP != 0 && oldP % screenItemCount == 0 && !isBackwards  && isCrossScreen) {// 向前跨屏滑动
            LogUtil.d("向前跨屏滑动 oldP = " + oldP + "---newP = " + newP);
            animation = new TranslateAnimation(newPF.x - layoutWidth, 0, layoutHeight - dragChangeScreenDistance, 0);
            animation.setDuration(ANIMATION_CHANGE_POSITION_CROSS_SCREEN_DURATION);
        } else {
            LogUtil.d("正常互换位置动画 oldP = " + oldP + "---newP = " + newP);
            animation = new TranslateAnimation(newPF.x - oldPF.x, 0, newPF.y - oldPF.y, 0);
            animation.setDuration(ANIMATION_CHANGE_POSITION_NEIGHBOR_DURATION);
        }

        animation.setFillAfter(true);
        animation.setAnimationListener(new NotifyDataSetListener(oldP));

        return animation;
    }

    private PointF positionToPoint(int position) {
        PointF point = new PointF();
        int row = position / colCount % rowCount;
        int col = position % colCount;
        int left = leftPadding + col * (colSpace + itemWidth);
        int top = topPadding + row * (rowSpace + itemHeight);

        point.x = left;
        point.y = top;
        return point;
    }

    /**
     * 使用Map集合记录,防止动画执行混乱
     */
    private HashMap<Integer, Boolean> animationMap = new HashMap<>();
    private class NotifyDataSetListener implements AnimationListener {
        private int movedPosition;

        public NotifyDataSetListener(int primaryPosition) {
            this.movedPosition = primaryPosition;
        }

        @Override
        public void onAnimationEnd(Animation animation) {
            if (animationMap.containsKey(movedPosition)) {
                // remove from map when end
                animationMap.remove(movedPosition);
            }
        }

        @Override
        public void onAnimationRepeat(Animation animation) {
        }

        @Override
        public void onAnimationStart(Animation animation) {
            // put into map when start
            animationMap.put(movedPosition, true);
        }
    }

    /**
     * 显示被拖动的 APP
     */
    private void showDragApp() {
        //recoverChildren();
        View dragView = getChildAt(dragPosition);
        LogUtil.d("showDragApp dragPosition = " + dragPosition + "---dragView = " + dragView);
        if (dragView != null && dragView.getVisibility() != View.VISIBLE) {
            dragView.setVisibility(View.VISIBLE);
        }
        dragMode = DragMode.DRAG_MODE_IDLE;
    }

    /**
     * 清除 APP 动画
     */
    private synchronized void clearAppAnimation() {
        for (int i = 0; i < getChildCount(); i++) {
            getChildAt(i).clearAnimation();
        }
        animationMap.clear();
    }

    /**
     * 清除 drag view
     */
    private synchronized void removeDragView() {
        if (dragImageView != null) {
            windowManager.removeView(dragImageView);
            dragImageView = null;
        }
    }

    /**
     * 执行松手动画
     */
    private void showDropAnimation(MotionEvent event) {
        ViewGroup dragView = (ViewGroup) getChildAt(dragPosition);
        if (dragView != null) {
            LogUtil.d("showDropAnimation dragPosition = " + dragPosition);
            final float fromX = getDropViewFromX(dragView, event);
            final float fromY = getDropViewFromY(dragView, event);
            TranslateAnimation animation = new TranslateAnimation(fromX, 0, fromY, 0);
            animation.setFillAfter(false);
            animation.setDuration(ANIMATION_DROP_DURATION);
            dragView.setAnimation(animation);
        }
    }

    private float getDropViewFromX(ViewGroup childView, MotionEvent event) {
        final int left = childView.getLeft() % layoutWidth;
        float fromX = event.getX() - left - dragPointX;
        LogUtil.d("showDropAnimation fromX = " + fromX + "---dragPointX = " + dragPointX);
        return 0;
    }

    private float getDropViewFromY(ViewGroup childView, MotionEvent event) {
        final int top = childView.getTop();
        float fromY = event.getY() - top - dragPointY;
        LogUtil.d("showDropAnimation fromY = " + fromY + "---dragPointY = " + dragPointY);
        return 0;
    }
}


text:
#ifndef _CONTACT_H_
#define _CONTACT_H_

#include <oasys/debug/DebugUtils.h>
#include <oasys/debug/Formatter.h>
#include <oasys/serialize/Serialize.h>
#include <oasys/util/Ref.h>
#include <oasys/util/RefCountedObject.h>
#include <oasys/util/Time.h>

namespace dtn {

class Bundle;
class ConvergenceLayer;
class CLInfo;
class Link;

// re-defined from Link.h
typedef oasys::Ref<Link> LinkRef;

/**
 * Encapsulation of an active connection to a next-hop DTN contact.
 * This is basically a repository for any state about the contact
 * opportunity including start time, estimations for bandwidth or
 * latency, etc.
 *
 * It also contains the CLInfo slot for the convergence layer to put
 * any state associated with the active connection.
 *
 * Since the contact object may be used by multiple threads in the
 * case of a connection-oriented convergence layer, and because the
 * object is intended to be deleted when the contact opportunity ends,
 * all object instances are reference counted and will be deleted when
 * the last reference is removed.
 */
class Contact : public oasys::RefCountedObject,
                public oasys::Logger,
                public oasys::SerializableObject
{
public:
    /**
     * Constructor
     */
    Contact(const LinkRef& link);

private:
    /**
     * Destructor -- private since the class is reference counted and
     * therefore is never explicitly deleted.
     */
    virtual ~Contact();
    friend class oasys::RefCountedObject;

public:
    /**
     * Store the convergence layer state associated with the contact.
     */
    void set_cl_info(CLInfo* cl_info)
    {
        ASSERT((cl_info_ == NULL && cl_info != NULL) ||
               (cl_info_ != NULL && cl_info == NULL));

        cl_info_ = cl_info;
    }

    /**
     * Accessor to the convergence layer info.
     */
    CLInfo* cl_info() { return cl_info_; }

    /**
     * Accessor to the link
     */
    const LinkRef& link() { return link_; }

    /**
     * Virtual from formatter
     */
    int format(char* buf, size_t sz) const;

    /**
     * Virtual from SerializableObject
     */
    virtual void serialize( oasys::SerializeAction *a );

    /// @{ Accessors
    const oasys::Time& start_time() const { return start_time_; }
    u_int32_t          duration()   const { return duration_; }
    u_int32_t          bps()        const { return bps_; }
    u_int32_t          latency()    const { return latency_; }

    void set_start_time(const oasys::Time& t) { start_time_ = t; }
    void set_duration(u_int32_t duration)     { duration_ = duration; }
    void set_bps(u_int32_t bps)               { bps_ = bps; }
    void set_latency(u_int32_t latency)       { latency_ = latency; }
    /// @}

protected:
    /// Time when the contact begin
    oasys::Time start_time_;

    /// Contact duration (0 if unknown)
    u_int32_t duration_;

    /// Approximate bandwidth
    u_int32_t bps_;

    /// Approximate latency
    u_int32_t latency_;

    LinkRef link_ ; 	///< Parent link on which this contact exists

    CLInfo* cl_info_;	///< convergence layer specific info
};

/**
 * Typedef for a reference on a contact.
 */
typedef oasys::Ref<Contact> ContactRef;

} // namespace dtn

#endif /* _CONTACT_H_ */

redpajama_set_name: RedPajamaGithub


text:
package org.apache.flink.table.api.batch.sql

import org.apache.flink.api.scala._
import org.apache.flink.table.api.scala._
import org.apache.flink.table.utils.TableTestUtil._
import org.apache.flink.table.utils.TableTestBase
import org.junit.Test

class CalcTest extends TableTestBase {

  @Test
  def testMultipleFlattening(): Unit = {
    val util = batchTestUtil()
    val table = util.addTable[((Int, Long), (String, Boolean), String)]("MyTable", 'a, 'b, 'c)

    val expected = unaryNode(
      "DataSetCalc",
      batchTableNode(table),
      term("select",
        "a._1 AS _1",
        "a._2 AS _2",
        "c",
        "b._1 AS _10",
        "b._2 AS _20"
      )
    )

    util.verifySql(
      "SELECT MyTable.a.*, c, MyTable.b.* FROM MyTable",
      expected)
  }

  @Test
  def testIn(): Unit = {
    val util = batchTestUtil()
    val table = util.addTable[(Int, Long, String)]("MyTable", 'a, 'b, 'c)

    val resultStr = (1 to 30).mkString(", ")
    val expected = unaryNode(
      "DataSetCalc",
      batchTableNode(table),
      term("select", "a", "b", "c"),
      term("where", s"IN(b, $resultStr)")
    )

    util.verifySql(
      s"SELECT * FROM MyTable WHERE b in ($resultStr)",
      expected)
  }

  @Test
  def testNotIn(): Unit = {
    val util = batchTestUtil()
    val table = util.addTable[(Int, Long, String)]("MyTable", 'a, 'b, 'c)

    val resultStr = (1 to 30).mkString(", ")
    val expected = unaryNode(
      "DataSetCalc",
      batchTableNode(table),
      term("select", "a", "b", "c"),
      term("where", s"NOT IN(b, $resultStr)")
    )

    util.verifySql(
      s"SELECT * FROM MyTable WHERE b NOT IN ($resultStr)",
      expected)
  }
}


text:
using System;
using Lunt;

namespace Lake.Commands
{
    internal sealed class ShowHelpCommand : ICommand
    {
        private readonly IConsoleWriter _console;

        public ShowHelpCommand(IConsoleWriter console)
        {
            if (console == null)
            {
                throw new ArgumentNullException("console");
            }
            _console = console;
        }

        public int Execute(LakeOptions options)
        {
            _console.WriteLine("Usage: Lake.exe [-input=target] [-output=target] [-probing=target]");
            _console.WriteLine("                [-verbosity=target] [-help] [-version] [-colors]");
            _console.WriteLine("                [-rebuild] <build_configuration>");
            _console.WriteLine("");
            _console.WriteLine("Example: Lake.exe build.config");
            _console.WriteLine("Example: Lake.exe -verbosity=quiet -output=\"../out\" build.config");
            _console.WriteLine("         Lake.exe -output=\"../out\" -rebuild build.config");
            _console.WriteLine("");
            _console.WriteLine("Options:");
            _console.WriteLine("    -input=target       Sets the input directory.");
            _console.WriteLine("    -output=target      Sets the output directory.");
            _console.WriteLine("    -probing=target     Sets the assembly probing directory.");
            _console.WriteLine("    -verbosity=value    Specifies the amount of information to be displayed.");
            _console.WriteLine("    -help               Displays usage information.");
            _console.WriteLine("    -version            Displays detailed version information.");
            _console.WriteLine("    -colors             Outputs the build log with colors.");
            _console.WriteLine("    -rebuild            Performs a non incremental build.");

            return (int)ExitCode.Success;
        }
    }
}


text:
package org.apache.jackrabbit.webdav.header;

import org.apache.jackrabbit.webdav.DavConstants;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import javax.servlet.http.HttpServletRequest;
import java.io.IOException;
import java.io.Reader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

/**
 * The IfHeader class represents the state lists defined
 * through the HTTP If header, which is specified in RFC 2518 as
 * follows :
 *

     If = "If" ":" ( 1*No-tag-list | 1*Tagged-list)
     No-tag-list = List
     Tagged-list = Resource 1*List
     Resource = Coded-URL
     List = "(" 1*(["Not"](State-etag | "[" entity-tag "]")) ")"
     State-etag = Coded-URL
     Coded-URL = "<" absoluteURI ">"
 *

 *

 * Reformulating this specification into proper EBNF as specified by N. Wirth
 * we get the following productions, which map to the parse METHODS of this
 * class. Any whitespace is ignored except for white space surrounding and
 * within words which is considered significant.
 *

     If = "If:" ( Tagged | Untagged ).
     Tagged = { "<" Word ">" Untagged } .
     Untagged = { "(" IfList ")" } .
     IfList = { [ "Not" ] ( ("<" Word ">" ) | ( "[" Word "]" ) ) } .
     Word = characters .
 *

 *

 * An If header either contains untagged IfList entries or
 * tagged IfList entries but not a mixture of both. An If
 * header containing tagged entries is said to be of tagged type while
 * an If header containing untagged entries is said to be of
 * untagged type.
 *

 * An IfList is a list of tokens - words enclosed in < >
 * - and etags - words enclosed in [ ]. An IfList matches a
 * (token, etag) tuple if all entries in the list match. If an entry in the list
 * is prefixed with the word Not (parsed case insensitively) the entry
 * must not match the concrete token or etag.
 *

 * Example: The ifList (<token> [etag]) only matches
 * if the concret token has the value token and the conrete etag
 * has the value etag. On the other hand, the ifList
 * (Not <notoken>) matches any token which is not
 * notoken (in this case the concrete value of the etag is
 * not taken into consideration).
 *
 * @author Felix Meschberger
 */
public class IfHeader implements Header {

    /**
     * default logger
     */
    private static final Logger log = LoggerFactory.getLogger(IfHeader.class);

    /**
     * The string representation of the header value
     */
    private final String headerValue;

    /**
     * The list of untagged state entries
     */
    private final IfHeaderInterface ifHeader;

    /**
     * The list of all positive tokens present in the If header.
     */
    private List<String> allTokens = new ArrayList<String>();
    /**
     * The list of all NOT tokens present in the If header.
     */
    private List<String> allNotTokens = new ArrayList<String>();

    /**
     * Create a Untagged IfHeader if the given lock tokens.
     *
     * @param tokens
     */
    public IfHeader(String[] tokens) {
        allTokens.addAll(Arrays.asList(tokens));
        StringBuffer b = new StringBuffer();
        for (String token : tokens) {
            b.append("(").append("<");
            b.append(token);
            b.append(">").append(")");
        }
        headerValue = b.toString();
        ifHeader = parse();
    }

    /**
     * Parses the If header and creates and internal representation
     * which is easy to query.
     *
     * @param req The request object
     */
    public IfHeader(HttpServletRequest req) {
        headerValue = req.getHeader(DavConstants.HEADER_IF);
        ifHeader = parse();
    }

    /**
     * Return {@link DavConstants#HEADER_IF If}
     *
     * @return {@link DavConstants#HEADER_IF If}
     * @see DavConstants#HEADER_IF
     */
    public String getHeaderName() {
        return DavConstants.HEADER_IF;
    }

    /**
     * Return the String representation of the If header present on
     * the given request or null.
     *
     * @return If header value as String or null.
     */
    public String getHeaderValue() {
        return headerValue;
    }

    /**
     * Returns true if an If header was present in the given request. False otherwise.
     *
     * @return  true if an If header was present.
     */
    public boolean hasValue() {
        return ifHeader != null;
    }

    /**
     * Tries to match the contents of the If header with the given
     * token and etag values with the restriction to only check for the tag.
     *

     * If the If header is of untagged type, the untagged IfList
     * is matched against the token and etag given: A match of the token and
     * etag is found if at least one of the IfList entries match the
     * token and etag tuple.
     *
     * @param tag The tag to identify the IfList to match the token
     * and etag against.
     * @param token The token to compare.
     * @param etag The ETag value to compare.
     *
     * @return If the If header is of untagged type the result is
     *      true if any of the IfList entries matches
     *      the token and etag values. For tagged type If header the
     *      result is true if either no entry for the given tag
     *      exists in the If header or if the IfList for the
     *      given tag matches the token and etag given.
     */
    public boolean matches(String tag, String token, String etag) {
        if (ifHeader == null) {
            log.debug("matches: No If header, assume match");
            return true;
        } else {
            return ifHeader.matches(tag, token, etag);
        }
    }

    /**
     * @return an iterator over all tokens present in the if header, that were
     * not denied by a leading NOT statement.
     */
    public Iterator<String> getAllTokens() {
        return allTokens.iterator();
    }

    /**
     * @return an iterator over all NOT tokens present in the if header, that
     * were explicitly denied.
     */
    public Iterator<String> getAllNotTokens() {
        return allNotTokens.iterator();
    }

    /**
     * Parse the original header value and build the internal IfHeaderInterface
     * object that is easy to query.
     */
    private IfHeaderInterface parse() {
        IfHeaderInterface ifHeader;
        if (headerValue != null && headerValue.length() > 0) {
            StringReader reader = null;
            int firstChar = 0;

            try {
                reader = new StringReader(headerValue);
                // get the first character to decide - expect '(' or '<'
                try {
                    reader.mark(1);
                    firstChar = readWhiteSpace(reader);
                    reader.reset();
                } catch (IOException ignore) {
                    // may be thrown according to API but is only thrown by the
                    // StringReader class if the reader is already closed.
                }

                if (firstChar == '(') {
                    ifHeader = parseUntagged(reader);
                } else if (firstChar == '<') {
                    ifHeader = parseTagged(reader);
                } else {
                    logIllegalState("If", firstChar, "(<", null);
                    ifHeader = null;
                }

            } finally  {
                if (reader != null) {
                    reader.close();
                }
            }

        } else {
            log.debug("IfHeader: No If header in request");
            ifHeader = null;
        }
        return ifHeader;
    }

    //---------- internal IF header parser -------------------------------------
    /**
     * Parses a tagged type If header. This method implements the
     * Tagged production given in the class comment :
     *

         Tagged = { "<" Word ">" Untagged } .
     *

     *
     * @param reader
     * @return
     */
    private IfHeaderMap parseTagged(StringReader reader) {
        IfHeaderMap map = new IfHeaderMap();
        try {
            while (true) {
                // read next non-white space
                int c = readWhiteSpace(reader);
                if (c < 0) {
                    // end of input, no more entries
                    break;
                } else if (c == '<') {
                    // start a tag with an IfList
                    String resource = readWord(reader, '>');
                    if (resource != null) {
                        // go to untagged after reading the resource
                        map.put(resource, parseUntagged(reader));
                    } else {
                        break;
                    }
                } else {
                    // unexpected character
                    // catchup to end of input or start of a tag
                    logIllegalState("Tagged", c, "<", reader);
                }
            }
        } catch (IOException ioe) {
            log.error("parseTagged: Problem parsing If header: "+ioe.toString());
        }

        return map;
    }

    /**
     * Parses an untagged type If header. This method implements the
     * Untagged production given in the class comment :
     *

         Untagged = { "(" IfList ")" } .
     *

     *
     * @param reader The StringReader to read from for parsing
     *
     * @return An ArrayList of {@link IfList} entries.
     */
    private IfHeaderList parseUntagged(StringReader reader) {
        IfHeaderList list = new IfHeaderList();
        try {
            while (true) {
                // read next non white space
                reader.mark(1);
                int c = readWhiteSpace(reader);
                if (c < 0) {
                    // end of input, no more IfLists
                    break;

                } else if (c == '(') {
                    // start of an IfList, parse
                    list.add(parseIfList(reader));

                } else if (c == '<') {
                    // start of a tag, return current list
                    reader.reset();
                    break;

                } else {
                    // unexpected character
                    // catchup to end of input or start of an IfList
                    logIllegalState("Untagged", c, "(", reader);
                }
            }
        } catch (IOException ioe) {
            log.error("parseUntagged: Problem parsing If header: "+ioe.toString());
        }
        return list;
    }

    /**
     * Parses an IfList in the If header. This method
     * implements the Tagged production given in the class comment :
     *

         IfList = { [ "Not" ] ( ("<" Word ">" ) | ( "[" Word "]" ) ) } .
     *

     *
     * @param reader The StringReader to read from for parsing
     *
     * @return The {@link IfList} for the input IfList.
     *
     * @throws IOException if a problem occurs during reading.
     */
    private IfList parseIfList(StringReader reader) throws IOException {
        IfList res = new IfList();
        boolean positive = true;
        String word;

        ReadLoop:
        while (true) {
            int nextChar = readWhiteSpace(reader);
            switch (nextChar) {
                case 'N':
                case 'n':
                    // read not

                    // check whether o or O
                    int not = reader.read();
                    if (not != 'o' && not != 'O') {
                        logIllegalState("IfList-Not", not, "o", null);
                        break;
                    }

                    // check whether t or T
                    not = reader.read();
                    if (not !='t' && not != 'T') {
                        logIllegalState("IfList-Not", not, "t", null);
                        break;
                    }

                    // read Not ok
                    positive = false;
                    break;

                case '<':
                    // state token
                    word = readWord(reader, '>');
                    if (word != null) {
                        res.add(new IfListEntryToken(word, positive));
                        // also add the token to the list of all tokens
                        if (positive) {
                            allTokens.add(word);
                        } else {
                            allNotTokens.add(word);
                        }
                        positive = true;
                    }
                    break;

                case '[':
                    // etag
                    word = readWord(reader, ']');
                    if (word != null) {
                        res.add(new IfListEntryEtag(word, positive));
                        positive = true;
                    }
                    break;

                case ')':
                    // correct end of list, end the loop
                    log.debug("parseIfList: End of If list, terminating loop");
                    break ReadLoop;

                default:
                    logIllegalState("IfList", nextChar, "nN<[)", reader);

                    // abort loop if EOF
                    if (nextChar < 0) {
                        break ReadLoop;
                    }

                    break;
            }
        }

        // return the current list anyway
        return res;
    }

    /**
     * Returns the first non-whitespace character from the reader or -1 if
     * the end of the reader is encountered.
     *
     * @param reader The Reader to read from
     *
     * @return The first non-whitespace character or -1 in case of EOF.
     *
     * @throws IOException if a problem occurs during reading.
     */
    private int readWhiteSpace(Reader reader) throws IOException {
        int c = reader.read();
        while (c >= 0 && Character.isWhitespace((char) c)) {
             c = reader.read();
        }
        return c;
    }

    /**
     * Reads from the input until the end character is encountered and returns
     * the string up to but not including this end character. If the end of input
     * is reached before reading the end character null is
     * returned.
     *

     * Note that this method does not support any escaping.
     *
     * @param reader The Reader to read from
     * @param end The ending character limiting the word.
     *
     * @return The string read up to but not including the ending character or
     *      null if the end of input is reached before the ending
     *      character has been read.
     *
     * @throws IOException if a problem occurs during reading.
     */
    private String readWord(Reader reader, char end) throws IOException {
        StringBuffer buf = new StringBuffer();

        // read the word value
        int c = reader.read();
        for (; c >= 0 && c != end; c=reader.read()) {
            buf.append((char) c);
        }

        // check whether we succeeded
        if (c < 0) {
            log.error("readWord: Unexpected end of input reading word");
            return null;
        }

        // build the string and return it
        return buf.toString();
    }

    /**
     * Logs an unexpected character with the corresponding state and list of
     * expected characters. If the reader parameter is not null, characters
     * are read until either the end of the input is reached or any of the
     * characters in the expChar string is read.
     *
     * @param state The name of the current parse state. This method logs this
     *      name in the message. The intended value would probably be the
     *      name of the EBNF production during which the error occurs.
     * @param effChar The effective character read.
     * @param expChar The list of characters acceptable in the current state.
     * @param reader The reader to be caught up to any of the expected
     *      characters. If null the input is not caught up to
     *      any of the expected characters (of course ;-).
     */
    private void logIllegalState(String state, int effChar, String expChar,
                                 StringReader reader) {

        // format the effective character to be logged
        String effString = (effChar < 0) ? "<EOF>" : String.valueOf((char) effChar);

        // log the error
        log.error("logIllegalState: Unexpected character '"+effString+"' in state "+state+", expected any of "+expChar);

        // catch up if a reader is given
        if (reader != null && effChar >= 0) {
            try {
                log.debug("logIllegalState: Catch up to any of "+expChar);
                do {
                    reader.mark(1);
                    effChar = reader.read();
                } while (effChar >= 0 && expChar.indexOf(effChar) < 0);
                if (effChar >= 0) {
                    reader.reset();
                }
            } catch (IOException ioe) {
                log.error("logIllegalState: IO Problem catching up to any of "+expChar);
            }
        }
    }

    //---------- internal If header structure ----------------------------------

    /**
     * The IfListEntry abstract class is the base class for
     * entries in an IfList production. This abstract base class
     * provides common functionality to both types of entries, namely tokens
     * enclosed in angle brackets (< >) and etags enclosed
     * in square brackets ([ ]).
     */
    private static abstract class IfListEntry {

        /**
         * The entry string value - the semantics of this value depends on the
         * implementing class.
         */
        protected final String value;

        /** Flag to indicate, whether this is a positive match or not */
        protected final boolean positive;

        /** The cached result of the {@link #toString} method. */
        protected String stringValue;

        /**
         * Sets up the final fields of this abstract class. The meaning of
         * value parameter depends solely on the implementing class. From the
         * point of view of this abstract class, it is simply a string value.
         *
         * @param value The string value of this instance
         * @param positive true if matches are positive
         */
        protected IfListEntry(String value, boolean positive) {
            this.value = value;
            this.positive = positive;
        }

        /**
         * Matches the value from the parameter to the internal string value.
         * If the parameter and the {@link #value} field match, the method
         * returns true for positive matches and false
         * for negative matches.
         *

         * This helper method can be called by implementations to evaluate the
         * concrete match on the correct value parameter. See
         * {@link #match(String, String)} for the external API method.
         *
         * @param value The string value to compare to the {@link #value}
         *      field.
         *
         * @return true if the value parameter and the
         *      {@link #value} field match and the {@link #positive} field is
         *      true or if the values do not match and the
         *      {@link #positive} field is false.
         */
        protected boolean match(String value) {
            return positive == this.value.equals(value);
        }

        /**
         * Matches the entry's value to the the token or etag. Depending on the
         * concrete implementation, only one of the parameters may be evaluated
         * while the other may be ignored.
         *

         * Implementing METHODS may call the helper method {@link #match(String)}
         * for the actual matching.
         *
         * @param token The token value to compare
         * @param etag The etag value to compare
         *
         * @return true if the token/etag matches the IfList
         *      entry.
         */
        public abstract boolean match(String token, String etag);

        /**
         * Returns a short type name for the implementation. This method is
         * used by the {@link #toString} method to build the string representation
         * if the instance.
         *
         * @return The type name of the implementation.
         */
        protected abstract String getType();

        /**
         * Returns the value of this entry.
         *
         * @return the value
         */
        protected String getValue() {
            return value;
        }

        /**
         * Returns the String representation of this entry. This method uses the
         * {@link #getType} to build the string representation.
         *
         * @return the String representation of this entry.
         */
        @Override
        public String toString() {
            if (stringValue == null) {
                stringValue = getType() + ": " + (positive?"":"!") + value;
            }
            return stringValue;
        }
    }

    /**
     * The IfListEntryToken extends the {@link IfListEntry}
     * abstract class to represent an entry for token matching.
     */
    private static class IfListEntryToken extends IfListEntry {

        /**
         * Creates a token matching entry.
         *
         * @param token The token value pertinent to this instance.
         * @param positive true if this is a positive match entry.
         */
        IfListEntryToken(String token, boolean positive) {
            super(token, positive);
        }

        /**
         * Matches the token parameter to the stored token value and returns
         * true if the values match and if the match is positive.
         * true is also returned for negative matches if the values
         * do not match.
         *
         * @param token The token value to compare
         * @param etag The etag value to compare, which is ignored in this
         *      implementation.
         *
         * @return true if the token matches the IfList
         *      entry's token value.
         */
        @Override
        public boolean match(String token, String etag) {
            return super.match(token);
        }

        /**
         * Returns the type name of this implementation, which is fixed to
         * be Token.
         *
         * @return The fixed string Token as the type name.
         */
        @Override
        protected String getType() {
            return "Token";
        }
    }

    /**
     * The IfListEntryToken extends the {@link IfListEntry}
     * abstract class to represent an entry for etag matching.
     */
    private static class IfListEntryEtag extends IfListEntry {

        /**
         * Creates an etag matching entry.
         *
         * @param etag The etag value pertinent to this instance.
         * @param positive true if this is a positive match entry.
         */
        IfListEntryEtag(String etag, boolean positive) {
            super(etag, positive);
        }

        /**
         * Matches the etag parameter to the stored etag value and returns
         * true if the values match and if the match is positive.
         * true is also returned for negative matches if the values
         * do not match.
         *
         * @param token The token value to compare, which is ignored in this
         *      implementation.
         * @param etag The etag value to compare
         *
         * @return true if the etag matches the IfList
         *      entry's etag value.
         */
        @Override
        public boolean match(String token, String etag) {
            return super.match(etag);
        }

        /**
         * Returns the type name of this implementation, which is fixed to
         * be ETag.
         *
         * @return The fixed string ETag as the type name.
         */
        @Override
        protected String getType() {
            return "ETag";
        }
    }

    /**
     * The IfList class extends the ArrayList class
     * with the limitation to only support adding {@link IfListEntry} objects
     * and adding a {@link #match} method.
     *

     * This class is a container for data contained in the If
     * production IfList
     *

         IfList = { [ "Not" ] ( ("<" Word ">" ) | ( "[" Word "]" ) ) } .
     *

     *

     */
    private static class IfList extends ArrayList<IfListEntry> {

        /**
         * Adds the {@link IfListEntry} at the end of the list.
         *
         * @param entry The {@link IfListEntry} to add to the list
         *
         * @return true (as per the general contract of Collection.add).
         */
        @Override
        public boolean add(IfListEntry entry) {
            return super.add(entry);
        }

        /**
         * Adds the {@link IfListEntry} at the indicated position of the list.
         *
         * @param index
         * @param entry
         *
         * @throws IndexOutOfBoundsException if index is out of range
         *      (index < 0 || index > size()).
         */
        @Override
        public void add(int index, IfListEntry entry) {
            super.add(index, entry);
        }

        /**
         * Returns true if all {@link IfListEntry} objects in the
         * list match the given token and etag. If the list is entry, it is
         * considered to match the token and etag.
         *
         * @param token The token to compare.
         * @param etag The etag to compare.
         *
         * @return true if all entries in the list match the
         *      given tag and token.
         */
        public boolean match(String token, String etag) {
            log.debug("match: Trying to match token="+token+", etag="+etag);
            for (int i=0; i < size(); i++) {
                IfListEntry ile = get(i);
                if (!ile.match(token, etag)) {
                    log.debug("match: Entry "+i+"-"+ile+" does not match");
                    return false;
                }
            }
            // invariant: all entries matched

            return true;
        }
    }

    /**
     * The IfHeaderInterface interface abstracts away the difference of
     * tagged and untagged If header lists. The single method provided
     * by this interface is to check whether a request may be applied to a
     * resource with given token and etag.
     */
    private static interface IfHeaderInterface {

        /**
         * Matches the resource, token, and etag against this
         * IfHeaderInterface instance.
         *
         * @param resource The resource to match this instance against. This
         *      must be absolute URI of the resource as defined in Section 3
         *      (URI Syntactic Components) of RFC 2396 Uniform Resource
         *      Identifiers (URI): Generic Syntax.
         * @param token The resource's lock token to match
         * @param etag The resource's etag to match
         *
         * @return true if the header matches the resource with
         *      token and etag, which means that the request is applicable
         *      to the resource according to the If header.
         */
        public boolean matches(String resource, String token, String etag);
    }

    /**
     * The IfHeaderList class implements the {@link IfHeaderInterface}
     * interface to support untagged lists of {@link IfList}s. This class
     * implements the data container for the production :
     *

         Untagged = { "(" IfList ")" } .
     *

     */
    private static class IfHeaderList extends ArrayList<IfList> implements IfHeaderInterface {

        /**
         * Matches a list of {@link IfList}s against the token and etag. If any of
         * the {@link IfList}s matches, the method returns true.
         * On the other hand false is only returned if non of the
         * {@link IfList}s match.
         *
         * @param resource The resource to match, which is ignored by this
         *      implementation. A value of null is therefor
         *      acceptable.
         * @param token The token to compare.
         * @param etag The ETag value to compare.
         *
         * @return True if any of the {@link IfList}s matches the token
         *      and etag, else false is returned.
         */
        public boolean matches(String resource, String token, String etag) {
            log.debug("matches: Trying to match token="+token+", etag="+etag);

            for (IfList il : this) {
                if (il.match(token, etag)) {
                    log.debug("matches: Found match with " + il);
                    return true;
                }
            }
            // invariant: no match found

            return false;
        }
    }

    /**
     * The IfHeaderMap class implements the {@link IfHeaderInterface}
     * interface to support tagged lists of {@link IfList}s. This class
     * implements the data container for the production :
     *

         Tagged = { "<" Word ">" "(" IfList ")" } .
     *

     */
    private static class IfHeaderMap extends HashMap<String, IfHeaderList> implements IfHeaderInterface {

        /**
         * Matches the token and etag for the given resource. If the resource is
         * not mentioned in the header, a match is assumed and true
         * is returned in this case.
         *
         * @param resource The absolute URI of the resource for which to find
         *      a match.
         * @param token The token to compare.
         * @param etag The etag to compare.
         *
         * @return true if either no entry exists for the resource
         *      or if the entry for the resource matches the token and etag.
         */
        public boolean matches(String resource, String token, String etag) {
            log.debug("matches: Trying to match resource="+resource+", token="+token+","+etag);

            IfHeaderList list = get(resource);
            if (list == null) {
                log.debug("matches: No entry for tag "+resource+", assuming match");
                return true;
            } else {
                return list.matches(resource, token, etag);
            }
        }
    }
}


text:
"""A module that implements the ADADELTA optimizer.
"""

import numpy
import theano.tensor as tensor

from theanolm.backend import Parameters
from theanolm.training.basicoptimizer import BasicOptimizer

class AdadeltaOptimizer(BasicOptimizer):
    """ADADELTA Optimization Method

    ADADELTA optimization method has been derived from AdaGrad. AdaGrad
    accumulates the sum of squared gradients over all time, which is used to
    scale the learning rate smaller and smaller. ADADELTA uses an exponentially
    decaying average of the squared gradients.

    This implementation scales the parameter updates by the learning rate
    hyperparameter. The original paper does not include such scaling,
    corresponding to learning rate 1.

    M. D. Zeiler (2012)
    ADADELTA: An adaptive learning rate method
    http://arxiv.org/abs/1212.5701
    """

    def __init__(self, optimization_options, network, *args, **kwargs):
        """Creates an Adadelta optimizer.

        :type optimization_options: dict
        :param optimization_options: a dictionary of optimization options

        :type network: Network
        :param network: the neural network object
        """

        self._params = Parameters()
        for path, param in network.get_variables().items():
            self._params.add(path + '_mean_sqr_gradient',
                             numpy.zeros_like(param.get_value()))
            self._params.add(path + '_mean_sqr_delta',
                             numpy.zeros_like(param.get_value()))

        # geometric rate for averaging gradients
        if 'gradient_decay_rate' not in optimization_options:
            raise ValueError("Gradient decay rate is not given in optimization "
                             "options.")
        self._gamma = optimization_options['gradient_decay_rate']

        super().__init__(optimization_options, network, *args, **kwargs)

    def _get_param_updates(self, alpha):
        """Returns Theano expressions for updating the model parameters and any
        additional parameters required by the optimizer.

        :type alpha: Variable
        :param alpha: a scale to be applied to the model parameter updates

        :rtype: iterable over pairs (shared variable, new expression)
        :returns: expressions how to update the optimizer parameters
        """

        result = []
        deltas = dict()
        for path, gradient in zip(self.network.get_variables(),
                                  self._gradients):
            ms_gradient_old = self._params[path + '_mean_sqr_gradient']
            ms_gradient = self._gamma * ms_gradient_old + \
                          (1.0 - self._gamma) * tensor.sqr(gradient)
            result.append((ms_gradient_old, ms_gradient))

            # New delta is expressed recursively using the current RMS gradient
            # and the old delta.
            ms_delta_old = self._params[path + '_mean_sqr_delta']
            rms_delta_old = tensor.sqrt(ms_delta_old + self._epsilon)
            rms_gradient = tensor.sqrt(ms_gradient + self._epsilon)
            deltas[path] = -gradient * rms_delta_old / rms_gradient
        self._normalize(deltas)

        for path, param_old in self.network.get_variables().items():
            delta = deltas[path]
            ms_delta_old = self._params[path + '_mean_sqr_delta']
            ms_delta = self._gamma * ms_delta_old + \
                       (1.0 - self._gamma) * tensor.sqr(delta)
            result.append((ms_delta_old, ms_delta))
            result.append((param_old, param_old + alpha * delta))
        return result


text:
/*
 Author:     King, wangjingui@outlook.com
 Date:       Dec 20, 2014
 Problem:    Recover Binary Search Tree
 Difficulty: High
 Source:     https://oj.leetcode.com/problems/recover-binary-search-tree/
 Notes:
 Two elements of a binary search tree (BST) are swapped by mistake.
 Recover the tree without changing its structure.
 Note:
 A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

 Solution: 1. recursive solution. O(n) space. get inorder list first.
           2. recursive solution. O(n) space. with only auxiliary two pointers.
           3. Use a stack. Iteration.
           4. Morris inorder traversal. O(1) space. with only auxiliary two pointers.
*/

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree_1(TreeNode root) {
        if (root == null) return;
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        inorderTraversal(root, res);
        TreeNode first = null, second = null;
        for (int i = 1; i < res.size(); ++i) {
            if (res.get(i).val > res.get(i-1).val)
                continue;
            if (first == null) first = res.get(i-1);
            second = res.get(i);
        }
        if (first == null) return;
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    public void inorderTraversal(TreeNode root, ArrayList<TreeNode> res) {
        if (root == null) return;
        inorderTraversal(root.left, res);
        res.add(root);
        inorderTraversal(root.right, res);
    }
    public void recoverTree_2(TreeNode root) {
        if (root == null) return;
        TreeNode[] res = new TreeNode[3];// 0->pre, 1->first, 2->second
        recoverRe2(root, res);
        int tmp = res[1].val;
        res[1].val = res[2].val;
        res[2].val = tmp;
    }
    public void recoverRe2(TreeNode root, TreeNode[] res) {
        if (root == null) return;
        recoverRe2(root.left, res);
        if (res[0] != null && res[0].val > root.val) {
            if (res[1] == null) res[1] = res[0];
            res[2] = root;
        }
        res[0] = root;
        recoverRe2(root.right, res);
    }

    public void recoverTree_3(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stk = new Stack<TreeNode>();
        TreeNode cur = root, pre = null, first = null, second = null;
        while (stk.isEmpty() == false || cur != null) {
            if (cur != null) {
                stk.push(cur);
                cur = cur.left;
            } else {
                cur = stk.pop();
                if (pre != null && pre.val > cur.val) {
                    if (first == null) first = pre;
                    second = cur;
                }
                pre = cur;
                cur = cur.right;
            }
        }
        if (first == null) return;
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

    public void recoverTree_4(TreeNode root) {
        if (root == null) return;
        TreeNode cur = root, pre = null, first = null, second = null;
        while (cur != null) {
            if (cur.left == null) {
                if (pre != null && pre.val > cur.val) {
                    if (first == null) first = pre;
                    second = cur;
                }
                pre = cur;
                cur = cur.right;
            } else {
                TreeNode node = cur.left;
                while (node.right != null && node.right != cur)
                    node = node.right;
                if (node.right != null) {
                    if (pre != null && pre.val > cur.val) {
                        if (first == null) first = pre;
                        second = cur;
                    }
                    pre = cur;
                    node.right = null;
                    cur = cur.right;
                } else {
                    node.right = cur;
                    cur = cur.left;
                }
            }
        }
        if (first == null) return;
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
}


text:
package network

import (
	"net/http"

	"github.com/docker/go-plugins-helpers/sdk"
)

const (
	manifest = `{"Implements": ["NetworkDriver"]}`
	// LocalScope is the correct scope response for a local scope driver
	LocalScope = `local`
	// GlobalScope is the correct scope response for a global scope driver
	GlobalScope = `global`

	capabilitiesPath    = "/NetworkDriver.GetCapabilities"
	allocateNetworkPath = "/NetworkDriver.AllocateNetwork"
	freeNetworkPath     = "/NetworkDriver.FreeNetwork"
	createNetworkPath   = "/NetworkDriver.CreateNetwork"
	deleteNetworkPath   = "/NetworkDriver.DeleteNetwork"
	createEndpointPath  = "/NetworkDriver.CreateEndpoint"
	endpointInfoPath    = "/NetworkDriver.EndpointOperInfo"
	deleteEndpointPath  = "/NetworkDriver.DeleteEndpoint"
	joinPath            = "/NetworkDriver.Join"
	leavePath           = "/NetworkDriver.Leave"
	discoverNewPath     = "/NetworkDriver.DiscoverNew"
	discoverDeletePath  = "/NetworkDriver.DiscoverDelete"
	programExtConnPath  = "/NetworkDriver.ProgramExternalConnectivity"
	revokeExtConnPath   = "/NetworkDriver.RevokeExternalConnectivity"
)

// Driver represent the interface a driver must fulfill.
type Driver interface {
	GetCapabilities() (*CapabilitiesResponse, error)
	CreateNetwork(*CreateNetworkRequest) error
	AllocateNetwork(*AllocateNetworkRequest) (*AllocateNetworkResponse, error)
	DeleteNetwork(*DeleteNetworkRequest) error
	FreeNetwork(*FreeNetworkRequest) error
	CreateEndpoint(*CreateEndpointRequest) (*CreateEndpointResponse, error)
	DeleteEndpoint(*DeleteEndpointRequest) error
	EndpointInfo(*InfoRequest) (*InfoResponse, error)
	Join(*JoinRequest) (*JoinResponse, error)
	Leave(*LeaveRequest) error
	DiscoverNew(*DiscoveryNotification) error
	DiscoverDelete(*DiscoveryNotification) error
	ProgramExternalConnectivity(*ProgramExternalConnectivityRequest) error
	RevokeExternalConnectivity(*RevokeExternalConnectivityRequest) error
}

// CapabilitiesResponse returns whether or not this network is global or local
type CapabilitiesResponse struct {
	Scope             string
	ConnectivityScope string
}

// AllocateNetworkRequest requests allocation of new network by manager
type AllocateNetworkRequest struct {
	// A network ID that remote plugins are expected to store for future
	// reference.
	NetworkID string

	// A free form map->object interface for communication of options.
	Options map[string]string

	// IPAMData contains the address pool information for this network
	IPv4Data, IPv6Data []IPAMData
}

// AllocateNetworkResponse is the response to the AllocateNetworkRequest.
type AllocateNetworkResponse struct {
	// A free form plugin specific string->string object to be sent in
	// CreateNetworkRequest call in the libnetwork agents
	Options map[string]string
}

// FreeNetworkRequest is the request to free allocated network in the manager
type FreeNetworkRequest struct {
	// The ID of the network to be freed.
	NetworkID string
}

// CreateNetworkRequest is sent by the daemon when a network needs to be created
type CreateNetworkRequest struct {
	NetworkID string
	Options   map[string]interface{}
	IPv4Data  []*IPAMData
	IPv6Data  []*IPAMData
}

// IPAMData contains IPv4 or IPv6 addressing information
type IPAMData struct {
	AddressSpace string
	Pool         string
	Gateway      string
	AuxAddresses map[string]interface{}
}

// DeleteNetworkRequest is sent by the daemon when a network needs to be removed
type DeleteNetworkRequest struct {
	NetworkID string
}

// CreateEndpointRequest is sent by the daemon when an endpoint should be created
type CreateEndpointRequest struct {
	NetworkID  string
	EndpointID string
	Interface  *EndpointInterface
	Options    map[string]interface{}
}

// CreateEndpointResponse is sent as a response to a CreateEndpointRequest
type CreateEndpointResponse struct {
	Interface *EndpointInterface
}

// EndpointInterface contains endpoint interface information
type EndpointInterface struct {
	Address     string
	AddressIPv6 string
	MacAddress  string
}

// DeleteEndpointRequest is sent by the daemon when an endpoint needs to be removed
type DeleteEndpointRequest struct {
	NetworkID  string
	EndpointID string
}

// InterfaceName consists of the name of the interface in the global netns and
// the desired prefix to be appended to the interface inside the container netns
type InterfaceName struct {
	SrcName   string
	DstPrefix string
}

// InfoRequest is send by the daemon when querying endpoint information
type InfoRequest struct {
	NetworkID  string
	EndpointID string
}

// InfoResponse is endpoint information sent in response to an InfoRequest
type InfoResponse struct {
	Value map[string]string
}

// JoinRequest is sent by the Daemon when an endpoint needs be joined to a network
type JoinRequest struct {
	NetworkID  string
	EndpointID string
	SandboxKey string
	Options    map[string]interface{}
}

// StaticRoute contains static route information
type StaticRoute struct {
	Destination string
	RouteType   int
	NextHop     string
}

// JoinResponse is sent in response to a JoinRequest
type JoinResponse struct {
	InterfaceName         InterfaceName
	Gateway               string
	GatewayIPv6           string
	StaticRoutes          []*StaticRoute
	DisableGatewayService bool
}

// LeaveRequest is send by the daemon when a endpoint is leaving a network
type LeaveRequest struct {
	NetworkID  string
	EndpointID string
}

// ErrorResponse is a formatted error message that libnetwork can understand
type ErrorResponse struct {
	Err string
}

// DiscoveryNotification is sent by the daemon when a new discovery event occurs
type DiscoveryNotification struct {
	DiscoveryType int
	DiscoveryData interface{}
}

// ProgramExternalConnectivityRequest specifies the L4 data
// and the endpoint for which programming has to be done
type ProgramExternalConnectivityRequest struct {
	NetworkID  string
	EndpointID string
	Options    map[string]interface{}
}

// RevokeExternalConnectivityRequest specifies the endpoint
// for which the L4 programming has to be removed
type RevokeExternalConnectivityRequest struct {
	NetworkID  string
	EndpointID string
}

// NewErrorResponse creates an ErrorResponse with the provided message
func NewErrorResponse(msg string) *ErrorResponse {
	return &ErrorResponse{Err: msg}
}

// Handler forwards requests and responses between the docker daemon and the plugin.
type Handler struct {
	driver Driver
	sdk.Handler
}

// NewHandler initializes the request handler with a driver implementation.
func NewHandler(driver Driver) *Handler {
	h := &Handler{driver, sdk.NewHandler(manifest)}
	h.initMux()
	return h
}

func (h *Handler) initMux() {
	h.HandleFunc(capabilitiesPath, func(w http.ResponseWriter, r *http.Request) {
		res, err := h.driver.GetCapabilities()
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		if res == nil {
			sdk.EncodeResponse(w, NewErrorResponse("Network driver must implement GetCapabilities"), true)
			return
		}
		sdk.EncodeResponse(w, res, false)
	})
	h.HandleFunc(createNetworkPath, func(w http.ResponseWriter, r *http.Request) {
		req := &CreateNetworkRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.CreateNetwork(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(allocateNetworkPath, func(w http.ResponseWriter, r *http.Request) {
		req := &AllocateNetworkRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		res, err := h.driver.AllocateNetwork(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, res, false)
	})
	h.HandleFunc(deleteNetworkPath, func(w http.ResponseWriter, r *http.Request) {
		req := &DeleteNetworkRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.DeleteNetwork(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(freeNetworkPath, func(w http.ResponseWriter, r *http.Request) {
		req := &FreeNetworkRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.FreeNetwork(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(createEndpointPath, func(w http.ResponseWriter, r *http.Request) {
		req := &CreateEndpointRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		res, err := h.driver.CreateEndpoint(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, res, false)
	})
	h.HandleFunc(deleteEndpointPath, func(w http.ResponseWriter, r *http.Request) {
		req := &DeleteEndpointRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.DeleteEndpoint(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(endpointInfoPath, func(w http.ResponseWriter, r *http.Request) {
		req := &InfoRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		res, err := h.driver.EndpointInfo(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, res, false)
	})
	h.HandleFunc(joinPath, func(w http.ResponseWriter, r *http.Request) {
		req := &JoinRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		res, err := h.driver.Join(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, res, false)
	})
	h.HandleFunc(leavePath, func(w http.ResponseWriter, r *http.Request) {
		req := &LeaveRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.Leave(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(discoverNewPath, func(w http.ResponseWriter, r *http.Request) {
		req := &DiscoveryNotification{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.DiscoverNew(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(discoverDeletePath, func(w http.ResponseWriter, r *http.Request) {
		req := &DiscoveryNotification{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.DiscoverDelete(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(programExtConnPath, func(w http.ResponseWriter, r *http.Request) {
		req := &ProgramExternalConnectivityRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.ProgramExternalConnectivity(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
	h.HandleFunc(revokeExtConnPath, func(w http.ResponseWriter, r *http.Request) {
		req := &RevokeExternalConnectivityRequest{}
		err := sdk.DecodeRequest(w, r, req)
		if err != nil {
			return
		}
		err = h.driver.RevokeExternalConnectivity(req)
		if err != nil {
			sdk.EncodeResponse(w, NewErrorResponse(err.Error()), true)
			return
		}
		sdk.EncodeResponse(w, struct{}{}, false)
	})
}