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

   public AlphabeticalIndexView(Context context, @Nullable AttributeSet attrs) {
       this(context, attrs, 0);
   }

   public AlphabeticalIndexView(Context context, @Nullable AttributeSet attrs, int defStyleAttr) {
       super(context, attrs, defStyleAttr);
       init(context);
   }

   @Override
   protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
       super.onMeasure(widthMeasureSpec, heightMeasureSpec);
       int w = (int) (getPaddingLeft() + getPaddingRight() + DisplayUtil.getTextWidth("W", mPaint));
       int h = getMeasuredHeight();
       setMeasuredDimension(w, h);
   }


   private void init(Context context) {
       mPaint = new Paint();
       mPaint.setAntiAlias(true);
       mPaint.setTextSize(DisplayUtil.sp2px(context, 15));
   }

@Override
    protected void onDraw(Canvas canvas) {
        super.onDraw(canvas);
        // 每个字母所占用的高度
        for (int i = 0; i < mLetters.length; i++) {
            String letter = mLetters[i];
            if (letter.equals(mCurrentTouchLetter))
                mPaint.setColor(Color.BLUE);
            else
                mPaint.setColor(Color.GRAY);

            // 获取字体的宽度
            float measureTextWidth = mPaint.measureText(letter);
            // 获取内容的宽度
            int contentWidth = getWidth() - getPaddingLeft() - getPaddingRight();

            canvas.drawText(letter, getPaddingLeft() + (contentWidth - measureTextWidth) / 2, getPaddingTop()  + mSingLetterHeight * i + DisplayUtil.getTextBaseLine(mPaint), mPaint);
        }
    }

@Override
   public boolean onTouchEvent(MotionEvent ev) {

       switch (ev.getAction()) {
           case MotionEvent.ACTION_DOWN:
           case MotionEvent.ACTION_MOVE:
               // 获取当前手指触摸的Y位置
               float fingerY = ev.getY();
               int pos = (int) (fingerY / mSingLetterHeight);
               if (pos > -1 && pos < mLetters.length && !mLetters[pos].equals(mCurrentTouchLetter)) {
                   mCurrentTouchLetter = mLetters[pos];
                   triggerTouchListener(true);
                   invalidate();
               }
               break;
           case MotionEvent.ACTION_UP:
               triggerTouchListener(false);
               break;
       }

       return true;
   }

   private void triggerTouchListener(boolean isTouch) {
       if (mTouchListener != null)
           mTouchListener.onTouch(mCurrentTouchLetter, isTouch);
   }

   // 设置触摸监听
   private SideBarTouchListener mTouchListener;

   public void setOnSideBarTouchListener(SideBarTouchListener touchListener) {
       this.mTouchListener = touchListener;
   }

   public interface SideBarTouchListener {
       void onTouch(String letter, boolean isTouch);
   }

@Override
   protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
       super.onMeasure(widthMeasureSpec, heightMeasureSpec);
       setMeasuredDimension(measureWidth(widthMeasureSpec),
               measureHeight(heightMeasureSpec));
   }

   /**
    * Determines the width of this view
    *
    * @param measureSpec A measureSpec packed into an int
    * @return The width of the view, honoring constraints from measureSpec
    */
   private int measureWidth(int measureSpec) {
       int result = 0;
       int specMode = MeasureSpec.getMode(measureSpec);
       int specSize = MeasureSpec.getSize(measureSpec);

       if (specMode == MeasureSpec.EXACTLY) {
           result = specSize;
       } else {
           result = mRadio * 2;
       }

       return result;
   }

   /**
    * Determines the height of this view
    *
    * @param measureSpec A measureSpec packed into an int
    * @return The height of the view, honoring constraints from measureSpec
    */
   private int measureHeight(int measureSpec) {
       int result = 0;
       int specMode = MeasureSpec.getMode(measureSpec);
       int specSize = MeasureSpec.getSize(measureSpec);
       if (specMode == MeasureSpec.EXACTLY) {
           result = specSize;
       } else {
           result = 2 * mRadio;
       }
       return result;
   }

@Override
    protected void onDraw(Canvas canvas) {
        super.onDraw(canvas);
        initCenterPoint();

        if (mFlog == 0)
            drawCircle(canvas);
        else if (mFlog == 1)
            drawRect(canvas);
        else
            drawTriangle(canvas);
    }

    private void initCenterPoint() {
        if (mCenterX == -1 || mCenterY == -1) {
            mCenterX = getMeasuredWidth() / 2;
            mCenterY = getMeasuredHeight() / 2;
         //   setPivotX(mCenterX);
         //  setPivotY(mCenterY);
        }
    }

    /**
     * 画圆
     *
     * @param canvas
     */
    private void drawCircle(Canvas canvas) {
        canvas.drawCircle(mCenterX, mCenterY, mRadio, mCirclePaint);
    }

   


    /**
     * 画正方形
     *
     * @param canvas
     */
    private void drawRect(Canvas canvas) {
        Rect rect = new Rect(mCenterX - mRadio,
                mCenterY - mRadio,
                mCenterX + mRadio,
                mCenterY + mRadio);
        canvas.drawRect(rect, mRectPaint);
    }


    public void setFlog(int mFlog) {
        this.mFlog = mFlog;
        invalidate();
    }

    /**
     * 绘制三角形
     *
     * @param canvas
     */
    private void drawTriangle(Canvas canvas) {
        Path path = new Path();
        path.moveTo(mCenterX, mCenterY - mRadio);
        path.lineTo(mCenterX - mRadio, mCenterY + mRadio);
        path.lineTo(mCenterX + mRadio, mCenterY + mRadio);
        canvas.drawPath(path, mTrianglePaint);
    }

@Override
   protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
       super.onMeasure(widthMeasureSpec, heightMeasureSpec);
       setMeasuredDimension(measureWidth(widthMeasureSpec),
               measureHeight(heightMeasureSpec));
   }

   /**
    * Determines the width of this view
    *
    * @param measureSpec A measureSpec packed into an int
    * @return The width of the view, honoring constraints from measureSpec
    */
   private int measureWidth(int measureSpec) {
       int result = 0;
       int specMode = MeasureSpec.getMode(measureSpec);
       int specSize = MeasureSpec.getSize(measureSpec);

       if (specMode == MeasureSpec.EXACTLY) {
           result = specSize;
       } else {
           result = mRadio * 2;
       }

       return result;
   }

   /**
    * Determines the height of this view
    *
    * @param measureSpec A measureSpec packed into an int
    * @return The height of the view, honoring constraints from measureSpec
    */
   private int measureHeight(int measureSpec) {
       int result = 0;
       int specMode = MeasureSpec.getMode(measureSpec);
       int specSize = MeasureSpec.getSize(measureSpec);
       if (specMode == MeasureSpec.EXACTLY) {
           result = specSize;
       } else {
           result = 2 * mRadio / 3;
       }
       return result;
   }

int left = getWidth() / 2 - mRadio;
 int top = -getHeight() / 2;
 int right = getWidth() / 2 + mRadio;
 int bottom = getHeight() / 2;
 mRectF = new RectF(left, top, right, bottom);

@Override
 protected void onDraw(Canvas canvas) {
     if (mRectF == null) {
         int left = getWidth() / 2 - mRadio;
         int top = -getHeight() / 2;
         int right = getWidth() / 2 + mRadio;
         int bottom = getHeight() / 2;
         mRectF = new RectF(left, top, right, bottom);
     }
     canvas.drawArc(mRectF, 0, 180, false, mArcPaint);
 }

 public void startAnim() {
    if (mAnimatorSet == null) {
        mAnimatorSet = new AnimatorSet();
        //up
        ObjectAnimator rotationAnim = ObjectAnimator.ofFloat(mShapeView, "rotation", 0.0f, 360.0f);
        rotationAnim.setDuration(JUMP_UP_TIME);
        rotationAnim.setInterpolator(new AccelerateDecelerateInterpolator());//先快后慢

        ObjectAnimator translationAnimUp = ObjectAnimator.ofFloat(mShapeView, "translationY", 0, -JUMP_MAX_HEIGHT);
        translationAnimUp.setDuration(JUMP_UP_TIME);
        translationAnimUp.setInterpolator(new AccelerateDecelerateInterpolator());//先快后慢

        ObjectAnimator scaleXAnimUp = ObjectAnimator.ofFloat(mArcView, "scaleX", 1.0f, 0.2f);
        scaleXAnimUp.setDuration(JUMP_UP_TIME);
        scaleXAnimUp.setInterpolator(new AccelerateDecelerateInterpolator());//先快后慢

        ObjectAnimator scaleYAnimUp = ObjectAnimator.ofFloat(mArcView, "scaleY", 1.0f, 0.2f);
        scaleYAnimUp.setDuration(JUMP_UP_TIME);
        scaleYAnimUp.setInterpolator(new AccelerateDecelerateInterpolator());//先快后慢

        //down
        ObjectAnimator translationAnimDown = ObjectAnimator.ofFloat(mShapeView, "translationY", -JUMP_MAX_HEIGHT, 0);
        translationAnimDown.setDuration(JUMP_UP_TIME);
        translationAnimDown.setInterpolator(new AccelerateInterpolator());//先慢后快

        ObjectAnimator scaleXAnimXDown = ObjectAnimator.ofFloat(mArcView, "scaleX", 0.2f, 1.0f);
        scaleXAnimXDown.setDuration(JUMP_UP_TIME);
        scaleXAnimXDown.setInterpolator(new AccelerateInterpolator());//先慢后快

        ObjectAnimator scaleYAnimDown = ObjectAnimator.ofFloat(mArcView, "scaleY", 0.2f, 1.0f);
        scaleYAnimDown.setDuration(JUMP_UP_TIME);
        scaleYAnimDown.setInterpolator(new AccelerateInterpolator());//先慢后快

        mAnimatorSet.play(translationAnimUp)
                .with(rotationAnim)
                .with(scaleXAnimUp)
                .with(scaleYAnimUp)
                .before(translationAnimDown)
                .before(scaleXAnimXDown)
                .before(scaleYAnimDown);
        mAnimatorSet.addListener(new AnimatorListenerAdapter() {
            @Override
            public void onAnimationEnd(Animator animation) {
                super.onAnimationEnd(animation);
                mFlog++;//圆形 0-->1方形 -->2 三角形 -->3->0---->
                if (mFlog > 2) {
                    mFlog = 0;
                }
                mShapeView.setFlog(mFlog);
                startAnim();
            }
        });
    }
    mAnimatorSet.start();
}

@Override
   protected void onAttachedToWindow() {
       mActivity.getApplication().registerActivityLifecycleCallbacks(animLifecyleCallback);
       super.onAttachedToWindow();
   }

   @Override
   protected void onDetachedFromWindow() {
       mActivity.getApplication().unregisterActivityLifecycleCallbacks(animLifecyleCallback);
       super.onDetachedFromWindow();
   }
   
   private SimpleActivityLifecycleCallbacks animLifecyleCallback = new SimpleActivityLifecycleCallbacks() {
       @Override
       public void onActivityResumed(Activity activity) { // 页面第一次启动的时候不会执行
           if (activity == mActivity)
               startAnim();
           super.onActivityResumed(activity);
       }

       @Override
       public void onActivityPaused(Activity activity) {
           if (activity == mActivity)
               stopAnim();
           super.onActivityPaused(activity);
       }
   };

private int mBottomColor;//底层圆的颜色
private int mTopColor;//顶层圆的颜色
private int mTextColor;//文字颜色

private int mMaxStepNum;//最大步数
private int mCurrentStepNum;//当前步数

private int mTextSize;//文字大小
private int mCircleRadio;//圆的半径
private int mCircleStrokeWidth;//圆线条的宽度

private float mArcAngle;//弧度大小
private float mStartAngle;//通过幅度计算出开始的角度位置

private void initAttrs(Context context, AttributeSet attrs) {
    TypedArray ta = context.obtainStyledAttributes(attrs, R.styleable.QQSportStep);
    mBottomColor = ta.getColor(R.styleable.QQSportStep_bottomColor, Color.BLUE);
    mTopColor = ta.getColor(R.styleable.QQSportStep_topColor, Color.RED);
    mTextColor = ta.getColor(R.styleable.QQSportStep_textColor, Color.RED);
    mMaxStepNum = ta.getInteger(R.styleable.QQSportStep_maxStepNum, 0);
    mCurrentStepNum = ta.getInteger(R.styleable.QQSportStep_currentStepNum, 0);
    mTextSize = ta.getDimensionPixelSize(R.styleable.QQSportStep_textSize, DisplayUtil.sp2px(context, 17));
    mCircleRadio = ta.getDimensionPixelSize(R.styleable.QQSportStep_circleRadio, DisplayUtil.dip2px(context, 100));
    mArcAngle = ta.getFloat(R.styleable.QQSportStep_arcAngle, 270.0f);
    if (mArcAngle > 360.0f || mArcAngle < -360.0f)
        mArcAngle = 360.0f;

    mCircleStrokeWidth = ta.getDimensionPixelOffset(R.styleable.QQSportStep_circleStrokeWidth, DisplayUtil.dip2px(context, 5));
    ta.recycle();
}

if (mRectF == null) {
     int centerX = getWidth() / 2;
     int centerY = getHeight() / 2;
     mRectF = new RectF(centerX - mCircleRadio, centerY   mCircleRadio, centerX + mCircleRadio, centerY + mCircleRadio);
 }

 //1.画底部的圆
 float gapAngle = mArcAngle - 180.0f;
 if (mArcAngle >= 0) {//大于0表示在上方
     mStartAngle = 180.0f - gapAngle / 2;
 } else {//小于0表示在下方
     mStartAngle = -gapAngle / 2;
 }
 canvas.drawArc(mRectF, mStartAngle, mArcAngle, false, mBottomPaint);

//2.画顶部的圆弧
  float currentAngle = (float) mCurrentStepNum / mMaxStepNum * mArcAngle;
  canvas.drawArc(mRectF, mStartAngle, currentAngle, false, mTopPaint);

  if (mMaxStepNum <= 0)
      return;

String step = String.valueOf(mCurrentStepNum);
        int dx = (getWidth() - DisplayUtil.getTextWidth(step, mTextPaint)) / 2;
        int baseLine = getHeight() / 2 + DisplayUtil.getTextBaseLine(mTextPaint);
        // 绘制步数文字
        canvas.drawText(step, dx, baseLine, mTextPaint);

int maxStepNun = 100000;
qqSportStepView.setMaxStepNum(maxStepNun);
ValueAnimator valueAnimator = new ValueAnimator();
valueAnimator.setDuration(2000);
valueAnimator.setIntValues(0, maxStepNun);
valueAnimator.setInterpolator(new DecelerateInterpolator());
valueAnimator.addUpdateListener(new ValueAnimator.AnimatorUpdateListener() {
    @Override
    public void onAnimationUpdate(ValueAnimator animation) {
        int value = (int) animation.getAnimatedValue();
        qqSportStepView.setCurrentStepNum(value);
    }
});
valueAnimator.start();

public class Graph {

    private int vertexSize;//顶点数量  5个顶点
    private int[] vertexs;//顶点  v0 v1 v2 v3 v4
    private int[][] matrix;//邻接矩阵
    private static final int MAX_WEIGHT = 1000; //表示无穷

    public Graph(int vertexSize) {
        this.vertexSize = vertexSize;
        matrix = new int[vertexSize][vertexSize];
        vertexs = new int[vertexSize];
        for (int i = 0; i < vertexSize; i++) {
            vertexs[i] = i;
        }
    }

    /**
     * 获取index顶点的的出度
     *
     * @param index 顶点index
     */
    public int getOutDegree(int index) {
        int degree = 0;
        for (int i = 0; i < matrix[index].length; i++) {
            int weight = matrix[index][i];
            if (weight != 0 && weight != MAX_WEIGHT) {
                degree++;
            }
        }
        return degree;
    }


    /**
     * 获取index顶点的的入度
     *
     * @param index 顶点index
     */
    public int getInDegree(int index) {
        int degree = 0;
        for (int i = 0; i < matrix[index].length; i++) {
            int weight = matrix[i][index];
            if (weight != 0 && weight != MAX_WEIGHT) {
                degree++;
            }
        }
        return degree;
    }

    /**
     * 获取v1到v2的权值
     *
     * @return v1到v2的权值权值
     */
    public int getWeight(int v1, int v2) {
        int weight = matrix[v1][v2];
        return weight == 0 ? 0 : (weight == MAX_WEIGHT ? -1 : weight);
    }


    public static void main(String[] args) {
        Graph graph = new Graph(5);//v0 -> v4
        int[] v0 = new int[]{0, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 6};
        int[] v1 = new int[]{9, 0, 3, MAX_WEIGHT, MAX_WEIGHT};
        int[] v2 = new int[]{2, MAX_WEIGHT, 0, 5, MAX_WEIGHT};
        int[] v3 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0, 1};
        int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0};


        graph.matrix[0] = v0;
        graph.matrix[1] = v1;
        graph.matrix[2] = v2;
        graph.matrix[3] = v3;
        graph.matrix[4] = v4;


        int v1OutDegree = graph.getOutDegree(1);
        System.out.println("v1的出度 = " + v1OutDegree);//v1的出度 = 2

        int v0InDegree = graph.getInDegree(1);
        System.out.println("v0的入度 = " + v0InDegree);//v0的入度 = 2

        int v02v4Weight = graph.getWeight(0, 4);
        System.out.println("v0到v4的权值 = " + v02v4Weight);//v0到v4的权值 = 6
    }

}

public class BinaryTree {
	private TreeNode  root = null;
	
	public BinaryTree(){
		root = new TreeNode(1, "A");
	}
	
	/**
	 * 构建二叉树
	 *         A
	 *     B       C
	 * D      E        F
	 */
	public void createBinaryTree(){
		TreeNode nodeB = new TreeNode(2, "B");
		TreeNode nodeC = new TreeNode(3, "C");
		TreeNode nodeD = new TreeNode(4, "D");
		TreeNode nodeE = new TreeNode(5, "E");
		TreeNode nodeF = new TreeNode(6, "F");
		root.leftChild = nodeB;
		root.rightChild = nodeC;
		nodeB.leftChild = nodeD;
		nodeB.rightChild = nodeE;
		nodeC.rightChild = nodeF;
	}
	
	/**
	 * 求二叉树的高度
	 * @author Administrator
	 *
	 */
	public int getHeight(){
		return getHeight(root);
	}
	
	private int getHeight(TreeNode node) {
		if(node == null){
			return 0;
		}else{
			int i = getHeight(node.leftChild);
			int j = getHeight(node.rightChild);
			return (i<j)?j+1:i+1;
		}
	}

	/**
	 * 获取二叉树的结点数
	 * @author Administrator
	 *
	 */
	public int getSize(){
		return getSize(root);
	}
	
	
	private int getSize(TreeNode node) {
		if(node == null){
			return 0;
		}else{
			return 1+getSize(node.leftChild)+getSize(node.rightChild);
		}
	}

	/**
	 * 前序遍历——迭代
	 * @author Administrator
	 *
	 */
	public void preOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			System.out.println("preOrder data:"+node.getData());
			preOrder(node.leftChild);
			preOrder(node.rightChild);
		}
	}
	
	/**
	 * 前序遍历——非迭代
	 */
	
	public void nonRecOrder(TreeNode node){
		if(node == null){
			return;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(node);
		while(!stack.isEmpty()){
			//出栈和进栈
			TreeNode n = stack.pop();//弹出根结点
			//压入子结点
			System.out.println("nonRecOrder data"+n.getData());
			if(n.rightChild!=null){
				stack.push(n.rightChild);
				
			}
			if(n.leftChild!=null){
				stack.push(n.leftChild);
			}
		}
	}
	/**
	 * 中序遍历——迭代
	 * @author Administrator
	 *
	 */
	public void midOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			midOrder(node.leftChild);
			System.out.println("midOrder data:"+node.getData());
			midOrder(node.rightChild);
		}
	}
	
	/**
	 * 后序遍历——迭代
	 * @author Administrator
	 *
	 */
	public void postOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			postOrder(node.leftChild);
			postOrder(node.rightChild);
			System.out.println("postOrder data:"+node.getData());
		}
	}
	public class TreeNode{
		private int index;
		private String data;
		private TreeNode leftChild;
		private TreeNode rightChild;
		
	
		public int getIndex() {
			return index;
		}


		public void setIndex(int index) {
			this.index = index;
		}


		public String getData() {
			return data;
		}


		public void setData(String data) {
			this.data = data;
		}


		public TreeNode(int index,String data){
			this.index = index;
			this.data = data;
			this.leftChild = null;
			this.rightChild = null;
		}
	}
	
	
	public static void main(String[] args){
		BinaryTree binaryTree = new BinaryTree();
		binaryTree.createBinaryTree();
		int height = binaryTree.getHeight();
		System.out.println("treeHeihgt:"+height);
		int size = binaryTree.getSize();
		System.out.println("treeSize:"+size);
//		binaryTree.preOrder(binaryTree.root);
//		binaryTree.midOrder(binaryTree.root);
//		binaryTree.postOrder(binaryTree.root);
		binaryTree.nonRecOrder(binaryTree.root);
	}
}

E push(E item)   
         把项压入堆栈顶部。   
E pop()   
         移除堆栈顶部的对象，并作为此函数的值返回该对象。   
E peek()   
         查看堆栈顶部的对象，但不从堆栈中移除它。   
boolean empty()   
         测试堆栈是否为空。    
int search(Object o)   
         返回对象在堆栈中的位置，以 1 为基数。

/**
    * Pushes an item onto the top of this stack. This has exactly
    * the same effect as:
    * <blockquote><pre>
    * addElement(item)</pre></blockquote>
    *
    * @param   item   the item to be pushed onto this stack.
    * @return  the <code>item</code> argument.
    * @see     java.util.Vector#addElement
    */
   public E push(E item) {
       addElement(item);

       return item;
   }

/**
     * Adds the specified component to the end of this vector,
     * increasing its size by one. The capacity of this vector is
     * increased if its size becomes greater than its capacity.
     *
     * <p>This method is identical in functionality to the
     * {@link #add(Object) add(E)}
     * method (which is part of the {@link List} interface).
     *
     * @param   obj   the component to be added
     */
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

/**
     * This implements the unsynchronized semantics of ensureCapacity.
     * Synchronized methods in this class can internally call this
     * method for ensuring capacity without incurring the cost of an
     * extra synchronization.
     *
     * @see #ensureCapacity(int)
     */
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }


    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

/**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

 /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

 /**
     * Deletes the component at the specified index. Each component in
     * this vector with an index greater or equal to the specified
     * {@code index} is shifted downward to have an index one
     * smaller than the value it had previously. The size of this vector
     * is decreased by {@code 1}.
     *
     * <p>The index must be a value greater than or equal to {@code 0}
     * and less than the current size of the vector.
     *
     * <p>This method is identical in functionality to the {@link #remove(int)}
     * method (which is part of the {@link List} interface).  Note that the
     * {@code remove} method returns the old value that was stored at the
     * specified position.
     *
     * @param      index   the index of the object to remove
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }
    
/**
     * Returns the component at the specified index.
     *
     * <p>This method is identical in functionality to the {@link #get(int)}
     * method (which is part of the {@link List} interface).
     *
     * @param      index   an index into this vector
     * @return     the component at the specified index
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }

        return elementData(index);
    }

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

/**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }

/**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

 private Node top = null;
private int number = 0;

class Node {
    public T Item;
    public Node Next;
}

public void push(T node) {
        Node oldFirst = top;
        top = new Node();
        top.Item = node;
        top.Next = oldFirst;
        number++;
    }

public T pop() {
       T item = top.Item;
       top = top.Next;
       number--;
       return item;
   }

/**
 * Created by zzw on 2017/6/27.
 * Version:
 * Des:
 */

public class StackLinkedList<T> {

    private Node top = null;
    private int number = 0;

   class Node {
        public T Item;
        public Node Next;
    }

    public void push(T node) {
        Node oldFirst = top;
        top = new Node();
        top.Item = node;
        top.Next = oldFirst;
        number++;
    }

    public T pop() {
        T item = top.Item;
        top = top.Next;
        number--;
        return item;
    }
}

/**
    * LinkedHashMap entry.
    */
   private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
       // These fields comprise the doubly linked list used for iteration.
       LinkedHashMapEntry<K,V> before, after;

       LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
           super(hash, key, value, next);
       }

       /**
        * Removes this entry from the linked list.
        */
       // 对自身在链表中进行移除
       private void remove() {
           before.after = after;
           after.before = before;
       }

       /**
        * Inserts this entry before the specified existing entry in the list.
        */
         //插入到LinkedHashMapEntry existingEntry之前
       private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
           after  = existingEntry;
           before = existingEntry.before;
           before.after = this;
           after.before = this;
       }

       /**
        * This method is invoked by the superclass whenever the value
        * of a pre-existing entry is read by Map.get or modified by Map.set.
        * If the enclosing Map is access-ordered, it moves the entry
        * to the end of the list; otherwise, it does nothing.
        */
       void recordAccess(HashMap<K,V> m) {
           LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
           if (lm.accessOrder) {
               lm.modCount++;
               remove();
               addBefore(lm.header);
           }
       }

       void recordRemoval(HashMap<K,V> m) {
           remove();
       }
   }

 /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                //调用子类LinkedHashMapEntry的recordAccess方法
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //调用LinkedHashMap.addEntry方法
        addEntry(hash, key, value, i);
        return null;
    }
    
/**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        //增加新的key  value  调用LinkedHashMap.createEntry
        createEntry(hash, key, value, bucketIndex);
    }

 /**
     * This override alters behavior of superclass put method. It causes newly
     * allocated entry to get inserted at the end of the linked list and
     * removes the eldest entry if appropriate.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        // Previous Android releases called removeEldestEntry() before actually
        // inserting a value but after increasing the size.
        // The RI is documented to call it afterwards.
        // **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
        
        //得到需要移除的对象
        // Remove eldest entry if instructed
        LinkedHashMapEntry<K,V> eldest = header.after;
        //需要移除的对象是否是自身
        if (eldest != header) {
            boolean removeEldest;
            size++;
            try {
                  //得到是否移除的对象的标识
                removeEldest = removeEldestEntry(eldest);
            } finally {
                size--;
            }
            if (removeEldest) {
                //调用HashMap的removeEntryForKey进行移除
                removeEntryForKey(eldest.key);
            }
        }
        //调用HashMap的addEntry
        super.addEntry(hash, key, value, bucketIndex);
    }
    
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

    /**
     * Like addEntry except that this version is used when creating entries
     * as part of Map construction or "pseudo-construction" (cloning,
     * deserialization).  This version needn't worry about resizing the table.
     *
     * Subclass overrides this to alter the behavior of HashMap(Map),
     * clone, and readObject.
     */
       //增加新的key  value
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
    }

/**
     * Removes the mapping for the specified key from this map if present.
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.getValue());
    }

    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        HashMapEntry<K,V> prev = table[i];
        HashMapEntry<K,V> e = prev;

        while (e != null) {
            HashMapEntry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                //调用LinkedHashMapEntry.recordRemoval
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

/**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

void recordRemoval(HashMap<K,V> m) {
            remove();
        }

/**
    * Returns the value to which the specified key is mapped,
    * or {@code null} if this map contains no mapping for the key.
    *
    * <p>More formally, if this map contains a mapping from a key
    * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
    * key.equals(k))}, then this method returns {@code v}; otherwise
    * it returns {@code null}.  (There can be at most one such mapping.)
    *
    * <p>A return value of {@code null} does not <i>necessarily</i>
    * indicate that the map contains no mapping for the key; it's also
    * possible that the map explicitly maps the key to {@code null}.
    * The {@link #containsKey containsKey} operation may be used to
    * distinguish these two cases.
    */
   public V get(Object key) {
       //调用HashMap的getEntry
       LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
       if (e == null)
           return null;
       e.recordAccess(this);
       return e.value;
   }

/**
    * Caches {@code value} for {@code key}. The value is moved to the head of
    * the queue.
    *
    * @return the previous value mapped by {@code key}.
    */
   public final V put(K key, V value) {
       if (key == null || value == null) {
           throw new NullPointerException("key == null || value == null");
       }

       V previous;
       synchronized (this) {
           putCount++;
           //根据key, value获取大小，我们需要重写sizeOf自行赋值
           size += safeSizeOf(key, value);
           //加入到LinkedHashMap
           previous = map.put(key, value);
           //如果key已经存在了previous 就！=null  就移除刚加的大小
           if (previous != null) {
               size -= safeSizeOf(key, previous);
           }
       }

       if (previous != null) {
           //重写移除的逻辑 
           entryRemoved(false, key, previous, value);
       }
       //根据maxSize去除多余的元素
       trimToSize(maxSize);
       return previous;
   }

/**
    * Removes the entry for {@code key} if it exists.
    *
    * @return the previous value mapped by {@code key}.
    */
   public final V remove(K key) {
       if (key == null) {
           throw new NullPointerException("key == null");
       }

       V previous;
       synchronized (this) {
           //从LinkedHashMap中移除
           previous = map.remove(key);
           if (previous != null) {
               size -= safeSizeOf(key, previous);
           }
       }

       if (previous != null) {
           entryRemoved(false, key, previous, null);
       }

       return previous;
   }

/**
     * Returns the value for {@code key} if it exists in the cache or can be
     * created by {@code #create}. If a value was returned, it is moved to the
     * head of the queue. This returns null if a value is not cached and cannot
     * be created.
     */
    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            //从LinkedHashMap中取出元素
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        /*
         * Attempt to create a value. This may take a long time, and the map
         * may be different when create() returns. If a conflicting value was
         * added to the map while create() was working, we leave that value in
         * the map and release the created value.
         */
        //如果没有这个key，那么你可以重写create来创建一个新的value 
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
      
      //新的创建的value 添加到LinkedHashMap
        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }