framework/cayenne-jdk1.5-unpublished/src/main/java/org/apache/cayenne/util/IndexPropertyList.java

/*****************************************************************
 *   Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License.
 ****************************************************************/

package org.apache.cayenne.util;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import org.apache.cayenne.CayenneRuntimeException;
import org.apache.cayenne.ValueHolder;
import org.apache.cayenne.reflect.PropertyUtils;

/**
 * A List implementation that would maintain its internal ordering based on some object
 * numeric "index" property. When objects are added to the list at a certain index, an
 * "index" property is modified to reflect list order, when objects are removed, their
 * index property is set to the negative number.
 * <p>
 * For performance reasons this implementation does not guarantee that there is no gaps in
 * the integer ordering sequence (i.e. generally
 * <code>object.getIndexProperty() != list.indexOf(object)</code>). However it
 * guarantees the right ordering based on index property.
 * 
 * @since 1.2
 */
public class IndexPropertyList extends AbstractList implements ValueHolder {

    /**
     * A default gap maintained between elements index property values. Gaps bigger than 1
     * ensure faster and less intrusive additions and removals.
     */
    static final int DEFAULT_GAP = 3;

    /**
     * A list used for the actual objects storage.
     */
    protected List list;
    protected String indexProperty;

    boolean dirty;
    Comparator comparator;

    /**
     * Creates an empty NumericPropertyOrderedList.
     */
    public IndexPropertyList(String indexProperty) {
        this(indexProperty, new ArrayList(), false);
    }

    /**
     * Creates a NumericPropertyOrderedList that decorates another list. If the list is
     * not known to be properly sorted, caller must set <em>sortNeeded</em> to true.
     * This will result in sorting the original list on first access attempt.
     */
    public IndexPropertyList(String indexProperty, List objects, boolean sortNeeded) {

        if (indexProperty == null) {
            throw new IllegalArgumentException("Null sortProperty");
        }

        if (objects == null) {
            throw new IllegalArgumentException("Null objects list.");
        }

        this.indexProperty = indexProperty;
        this.list = objects;

        // be lazy - don't sort here, as (a) it may never be needed and (b) a list can be
        // a Cayenne fault, so resolving it too early is undesirable
        this.dirty = sortNeeded;
    }

    ValueHolder getWrappedValueHolder() {
        return (list instanceof ValueHolder) ? (ValueHolder) list : null;
    }

    public boolean isFault() {
        ValueHolder h = getWrappedValueHolder();
        return (h != null) ? h.isFault() : false;
    }

    public Object setValueDirectly(Object value) throws CayenneRuntimeException {
        ValueHolder h = getWrappedValueHolder();
        return h != null ? h.setValueDirectly(value) : null;
    }

    public Object setValue(Object value) throws CayenneRuntimeException {
        ValueHolder h = getWrappedValueHolder();
        return h != null ? h.setValue(value) : null;
    }

    public Object getValue() throws CayenneRuntimeException {
        ValueHolder h = getWrappedValueHolder();
        return h != null ? h.getValue() : null;
    }
    
    public Object getValueDirectly() throws CayenneRuntimeException {
        ValueHolder h = getWrappedValueHolder();
        return h != null ? h.getValueDirectly() : null;
    }

    public void invalidate() {
        ValueHolder h = getWrappedValueHolder();
        if (h != null) {
            h.invalidate();
        }
    }

    /**
     * Changes list state to "dirty" forcing reordering on next access.
     */
    public void touch() {
        this.dirty = true;
    }

    @Override
    public Object get(int index) {
        if (dirty) {
            sort();
        }

        return list.get(index);
    }

    @Override
    public int size() {
        if (dirty) {
            sort();
        }

        return list.size();
    }

    @Override
    public Object set(int index, Object element) {
        if (dirty) {
            sort();
        }

        Object removed = list.set(index, element);

        if (element != null) {
            int indexValue = (removed != null)
                    ? getIndexValue(removed)
                    : calculateIndexValue(index);

            setIndexValue(element, indexValue);
            shift(index + 1, indexValue);
        }

        if (removed != null && removed != element) {
            setIndexValue(removed, -1);
        }

        return removed;
    }

    @Override
    public void add(int index, Object element) {
        if (dirty) {
            sort();
        }

        list.add(index, element);

        if (element != null) {
            int indexValue = calculateIndexValue(index);

            setIndexValue(element, indexValue);
            shift(index + 1, indexValue);
        }
    }

    @Override
    public Object remove(int index) {
        if (dirty) {
            sort();
        }

        Object removed = list.remove(index);

        if (removed != null) {
            setIndexValue(removed, -1);
        }

        return removed;
    }

    // ============================================
    // ***** Methods to maintain ordering ******
    // ============================================

    /**
     * Calculates an index value at the specified list index. Note that using this value
     * may require a shift of the objects following this index.
     */
    protected int calculateIndexValue(int listIndex) {
        if (list.isEmpty()) {
            throw new ArrayIndexOutOfBoundsException(listIndex);
        }

        if (list.size() == 1 && listIndex == 0) {
            return 0;
        }

        // handle lists with teo or more elements...

        // last element
        if (listIndex == list.size() - 1) {
            return getIndexValue(get(listIndex - 1)) + DEFAULT_GAP;
        }

        int from = (listIndex == 0) ? -1 : getIndexValue(get(listIndex - 1));
        int to = getIndexValue(get(listIndex + 1));
        return (to - from > 1) ? (to - from) / 2 + from : from + DEFAULT_GAP;
    }

    protected int getIndexValue(Object object) {
        Number n = (Number) PropertyUtils.getProperty(object, indexProperty);
        if (n == null) {
            throw new CayenneRuntimeException("Null index property '"
                    + indexProperty
                    + "' for object "
                    + object);
        }

        return n.intValue();
    }

    protected void setIndexValue(Object object, int index) {
        PropertyUtils.setProperty(object, indexProperty, Integer.valueOf(index));
    }

    protected void shift(int startIndex, int afterIndexValue) {
        int size = size();
        for (int i = startIndex; i < size; i++) {
            Object object = get(i);

            int indexValue = getIndexValue(object);
            if (indexValue > afterIndexValue) {
                break;
            }

            int newValue = calculateIndexValue(i);
            setIndexValue(object, newValue);
            afterIndexValue = newValue;
        }
    }

    /**
     * Sorts internal list.
     */
    protected void sort() {
        if (!dirty) {
            return;
        }

        // do not directly sort Cayenne lists, sort the underlying list instead to avoid a
        // bunch of additions/removals
        Collections.sort(unwrapList(), getComparator());
        dirty = false;
    }

    List unwrapList() {
        if (list instanceof PersistentObjectList) {
            return ((PersistentObjectList) list).resolvedObjectList();
        }
        else {
            return list;
        }
    }

    /**
     * Returns a property Comaparator, creating it on demand.
     */
    Comparator getComparator() {
        if (comparator == null) {
            comparator = new Comparator() {

                public int compare(Object o1, Object o2) {
                    if ((o1 == null && o2 == null) || o1 == o2) {
                        return 0;
                    }
                    else if (o1 == null) {
                        return -1;
                    }
                    else if (o2 == null) {
                        return 1;
                    }

                    Comparable p1 = (Comparable) PropertyUtils.getProperty(
                            o1,
                            indexProperty);
                    Comparable p2 = (Comparable) PropertyUtils.getProperty(
                            o2,
                            indexProperty);
                    return (p1 == null) ? -1 : p1.compareTo(p2);
                }
            };
        }
        return comparator;
    }
}