/*

 * Copyright (c) 1998, 2008, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package javax.swing.text;

import java.util.Vector;

import java.io.IOException;

import java.io.ObjectInputStream;

import java.io.Serializable;

import javax.swing.undo.AbstractUndoableEdit;

import javax.swing.undo.CannotRedoException;

import javax.swing.undo.CannotUndoException;

import javax.swing.undo.UndoableEdit;

import javax.swing.SwingUtilities;

import java.lang.ref.WeakReference;

import java.lang.ref.ReferenceQueue;

/**

 * An implementation of the AbstractDocument.Content interface

 * implemented using a gapped buffer similar to that used by emacs.

 * The underlying storage is a array of unicode characters with

 * a gap somewhere.  The gap is moved to the location of changes

 * to take advantage of common behavior where most changes are

 * in the same location.  Changes that occur at a gap boundary are

 * generally cheap and moving the gap is generally cheaper than

 * moving the array contents directly to accomodate the change.

 * <p>

 * The positions tracking change are also generally cheap to

 * maintain.  The Position implementations (marks) store the array

 * index and can easily calculate the sequential position from

 * the current gap location.  Changes only require update to the

 * the marks between the old and new gap boundaries when the gap

 * is moved, so generally updating the marks is pretty cheap.

 * The marks are stored sorted so they can be located quickly

 * with a binary search.  This increases the cost of adding a

 * mark, and decreases the cost of keeping the mark updated.

 *

 * @author  Timothy Prinzing

 */

public class GapContent extends GapVector implements AbstractDocument.Content, Serializable {

    /**

     * Creates a new GapContent object.  Initial size defaults to 10.

     */

    public GapContent() {

        this(10);

    }

    /**

     * Creates a new GapContent object, with the initial

     * size specified.  The initial size will not be allowed

     * to go below 2, to give room for the implied break and

     * the gap.

     *

     * @param initialLength the initial size

     */

    public GapContent(int initialLength) {

        super(Math.max(initialLength,2));

        char[] implied = new char[1];

        implied[0] = '\n';

        replace(0, 0, implied, implied.length);

        marks = new MarkVector();

        search = new MarkData(0);

        queue = new ReferenceQueue<StickyPosition>();

    }

    /**

     * Allocate an array to store items of the type

     * appropriate (which is determined by the subclass).

     */

    protected Object allocateArray(int len) {

        return new char[len];

    }

    /**

     * Get the length of the allocated array.

     */

    protected int getArrayLength() {

        char[] carray = (char[]) getArray();

        return carray.length;

    }

    // --- AbstractDocument.Content methods -------------------------

    /**

     * Returns the length of the content.

     *

     * @return the length >= 1

     * @see AbstractDocument.Content#length

     */

    public int length() {

        int len = getArrayLength() - (getGapEnd() - getGapStart());

        return len;

    }

    /**

     * Inserts a string into the content.

     *

     * @param where the starting position >= 0, < length()

     * @param str the non-null string to insert

     * @return an UndoableEdit object for undoing

     * @exception BadLocationException if the specified position is invalid

     * @see AbstractDocument.Content#insertString

     */

    public UndoableEdit insertString(int where, String str) throws BadLocationException {

        if (where > length() || where < 0) {

            throw new BadLocationException("Invalid insert", length());

        }

        char[] chars = str.toCharArray();

        replace(where, 0, chars, chars.length);

        return new InsertUndo(where, str.length());

    }

    /**

     * Removes part of the content.

     *

     * @param where the starting position >= 0, where + nitems < length()

     * @param nitems the number of characters to remove >= 0

     * @return an UndoableEdit object for undoing

     * @exception BadLocationException if the specified position is invalid

     * @see AbstractDocument.Content#remove

     */

    public UndoableEdit remove(int where, int nitems) throws BadLocationException {

        if (where + nitems >= length()) {

            throw new BadLocationException("Invalid remove", length() + 1);

        }

        String removedString = getString(where, nitems);

        UndoableEdit edit = new RemoveUndo(where, removedString);

        replace(where, nitems, empty, 0);

        return edit;

    }

    /**

     * Retrieves a portion of the content.

     *

     * @param where the starting position >= 0

     * @param len the length to retrieve >= 0

     * @return a string representing the content

     * @exception BadLocationException if the specified position is invalid

     * @see AbstractDocument.Content#getString

     */

    public String getString(int where, int len) throws BadLocationException {

        Segment s = new Segment();

        getChars(where, len, s);

        return new String(s.array, s.offset, s.count);

    }

    /**

     * Retrieves a portion of the content.  If the desired content spans

     * the gap, we copy the content.  If the desired content does not

     * span the gap, the actual store is returned to avoid the copy since

     * it is contiguous.

     *

     * @param where the starting position >= 0, where + len <= length()

     * @param len the number of characters to retrieve >= 0

     * @param chars the Segment object to return the characters in

     * @exception BadLocationException if the specified position is invalid

     * @see AbstractDocument.Content#getChars

     */

    public void getChars(int where, int len, Segment chars) throws BadLocationException {

        int end = where + len;

        if (where < 0 || end < 0) {

            throw new BadLocationException("Invalid location", -1);

        }

        if (end > length() || where > length()) {

            throw new BadLocationException("Invalid location", length() + 1);

        }

        int g0 = getGapStart();

        int g1 = getGapEnd();

        char[] array = (char[]) getArray();

        if ((where + len) <= g0) {

            // below gap

            chars.array = array;

            chars.offset = where;

        } else if (where >= g0) {

            // above gap

            chars.array = array;

            chars.offset = g1 + where - g0;

        } else {

            // spans the gap

            int before = g0 - where;

            if (chars.isPartialReturn()) {

                // partial return allowed, return amount before the gap

                chars.array = array;

                chars.offset = where;

                chars.count = before;

                return;

            }

            // partial return not allowed, must copy

            chars.array = new char[len];

            chars.offset = 0;

            System.arraycopy(array, where, chars.array, 0, before);

            System.arraycopy(array, g1, chars.array, before, len - before);

        }

        chars.count = len;

    }

    /**

     * Creates a position within the content that will

     * track change as the content is mutated.

     *

     * @param offset the offset to track >= 0

     * @return the position

     * @exception BadLocationException if the specified position is invalid

     */

    public Position createPosition(int offset) throws BadLocationException {

        while ( queue.poll() != null ) {

            unusedMarks++;

        }

        if (unusedMarks > Math.max(5, (marks.size() / 10))) {

            removeUnusedMarks();

        }

        int g0 = getGapStart();

        int g1 = getGapEnd();

        int index = (offset < g0) ? offset : offset + (g1 - g0);

        search.index = index;

        int sortIndex = findSortIndex(search);

        MarkData m;

        StickyPosition position;

        if (sortIndex < marks.size()

            && (m = marks.elementAt(sortIndex)).index == index

            && (position = m.getPosition()) != null) {

            //position references the correct StickyPostition

        } else {

            position = new StickyPosition();

            m = new MarkData(index,position,queue);

            position.setMark(m);

            marks.insertElementAt(m, sortIndex);

        }

        return position;

    }

    /**

     * Holds the data for a mark... separately from

     * the real mark so that the real mark (Position

     * that the caller of createPosition holds) can be

     * collected if there are no more references to

     * it.  The update table holds only a reference

     * to this data.

     */

    final class MarkData extends WeakReference<StickyPosition> {

        MarkData(int index) {

            super(null);

            this.index = index;

        }

        MarkData(int index, StickyPosition position, ReferenceQueue<? super StickyPosition> queue) {

            super(position, queue);

            this.index = index;

        }

        /**

         * Fetch the location in the contiguous sequence

         * being modeled.  The index in the gap array

         * is held by the mark, so it is adjusted according

         * to it's relationship to the gap.

         */

        public final int getOffset() {

            int g0 = getGapStart();

            int g1 = getGapEnd();

            int offs = (index < g0) ? index : index - (g1 - g0);

            return Math.max(offs, 0);

        }

        StickyPosition getPosition() {

            return get();

        }

        int index;

    }

    final class StickyPosition implements Position {

        StickyPosition() {

        }

        void setMark(MarkData mark) {

            this.mark = mark;

        }

        public final int getOffset() {

            return mark.getOffset();

        }

        public String toString() {

            return Integer.toString(getOffset());

        }

        MarkData mark;

    }

    // --- variables --------------------------------------

    private static final char[] empty = new char[0];

    private transient MarkVector marks;

    /**

     * Record used for searching for the place to

     * start updating mark indexs when the gap

     * boundaries are moved.

     */

    private transient MarkData search;

    /**

     * The number of unused mark entries

     */

    private transient int unusedMarks = 0;

    private transient ReferenceQueue<StickyPosition> queue;

    final static int GROWTH_SIZE = 1024 * 512;

    // --- gap management -------------------------------

    /**

     * Make the gap bigger, moving any necessary data and updating

     * the appropriate marks

     */

    protected void shiftEnd(int newSize) {

        int oldGapEnd = getGapEnd();

        super.shiftEnd(newSize);

        // Adjust marks.

        int dg = getGapEnd() - oldGapEnd;

        int adjustIndex = findMarkAdjustIndex(oldGapEnd);

        int n = marks.size();

        for (int i = adjustIndex; i < n; i++) {

            MarkData mark = marks.elementAt(i);

            mark.index += dg;

        }

    }

    /**

     * Overridden to make growth policy less agressive for large

     * text amount.

     */

    int getNewArraySize(int reqSize) {

        if (reqSize < GROWTH_SIZE) {

            return super.getNewArraySize(reqSize);

        } else {

            return reqSize + GROWTH_SIZE;

        }

    }

    /**

     * Move the start of the gap to a new location,

     * without changing the size of the gap.  This

     * moves the data in the array and updates the

     * marks accordingly.

     */

    protected void shiftGap(int newGapStart) {

        int oldGapStart = getGapStart();

        int dg = newGapStart - oldGapStart;

        int oldGapEnd = getGapEnd();

        int newGapEnd = oldGapEnd + dg;

        int gapSize = oldGapEnd - oldGapStart;

        // shift gap in the character array

        super.shiftGap(newGapStart);

        // update the marks

        if (dg > 0) {

            // Move gap up, move data and marks down.

            int adjustIndex = findMarkAdjustIndex(oldGapStart);

            int n = marks.size();

            for (int i = adjustIndex; i < n; i++) {

                MarkData mark = marks.elementAt(i);

                if (mark.index >= newGapEnd) {

                    break;

                }

                mark.index -= gapSize;

            }

        } else if (dg < 0) {

            // Move gap down, move data and marks up.

            int adjustIndex = findMarkAdjustIndex(newGapStart);

            int n = marks.size();

            for (int i = adjustIndex; i < n; i++) {

                MarkData mark = marks.elementAt(i);

                if (mark.index >= oldGapEnd) {

                    break;

                }

                mark.index += gapSize;

            }

        }

        resetMarksAtZero();

    }

    /**

     * Resets all the marks that have an offset of 0 to have an index of

     * zero as well.

     */

    protected void resetMarksAtZero() {

        if (marks != null && getGapStart() == 0) {

            int g1 = getGapEnd();

            for (int counter = 0, maxCounter = marks.size();

                 counter < maxCounter; counter++) {

                MarkData mark = marks.elementAt(counter);

                if (mark.index <= g1) {

                    mark.index = 0;

                }

                else {

                    break;

                }

            }

        }

    }

    /**

     * Adjust the gap end downward.  This doesn't move

     * any data, but it does update any marks affected

     * by the boundary change.  All marks from the old

     * gap start down to the new gap start are squeezed

     * to the end of the gap (their location has been

     * removed).

     */

    protected void shiftGapStartDown(int newGapStart) {

        // Push aside all marks from oldGapStart down to newGapStart.

        int adjustIndex = findMarkAdjustIndex(newGapStart);

        int n = marks.size();

        int g0 = getGapStart();

        int g1 = getGapEnd();

        for (int i = adjustIndex; i < n; i++) {

            MarkData mark = marks.elementAt(i);

            if (mark.index > g0) {

                // no more marks to adjust

                break;

            }

            mark.index = g1;

        }

        // shift the gap in the character array

        super.shiftGapStartDown(newGapStart);

        resetMarksAtZero();

    }

    /**

     * Adjust the gap end upward.  This doesn't move

     * any data, but it does update any marks affected

     * by the boundary change. All marks from the old

     * gap end up to the new gap end are squeezed

     * to the end of the gap (their location has been

     * removed).

     */

    protected void shiftGapEndUp(int newGapEnd) {

        int adjustIndex = findMarkAdjustIndex(getGapEnd());

        int n = marks.size();

        for (int i = adjustIndex; i < n; i++) {

            MarkData mark = marks.elementAt(i);

            if (mark.index >= newGapEnd) {

                break;

            }

            mark.index = newGapEnd;

        }

        // shift the gap in the character array

        super.shiftGapEndUp(newGapEnd);

        resetMarksAtZero();

    }

    /**

     * Compares two marks.

     *

     * @param o1 the first object

     * @param o2 the second object

     * @return < 0 if o1 < o2, 0 if the same, > 0 if o1 > o2

     */

    final int compare(MarkData o1, MarkData o2) {

        if (o1.index < o2.index) {

            return -1;

        } else if (o1.index > o2.index) {

            return 1;

        } else {

            return 0;

        }

    }

    /**

     * Finds the index to start mark adjustments given

     * some search index.

     */

    final int findMarkAdjustIndex(int searchIndex) {

        search.index = Math.max(searchIndex, 1);

        int index = findSortIndex(search);

        // return the first in the series

        // (ie. there may be duplicates).

        for (int i = index - 1; i >= 0; i--) {

            MarkData d = marks.elementAt(i);

            if (d.index != search.index) {

                break;

            }

            index -= 1;

        }

        return index;

    }

    /**

     * Finds the index of where to insert a new mark.

     *