Quadcap Embeddable Database

com/quadcap/sql/lock/SortedArray.java

Go to the documentation of this file.

package com.quadcap.sql.lock;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.util.Comparator;

import com.quadcap.util.Debug;

/**
 * 
 *
 * @author Stan Bailes
 */
public class SortedArray {
    Comparator                  compare;
    int                         size;
    Object[]                    array           = new Object[32];
    
    public SortedArray(Comparator compare) {
        this.compare = compare;
    }

    public final int find(Object obj) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            Object m = array[mid];
            int cmp = compare.compare(m, obj);
            if (cmp < 0) {
                lo = mid + 1;
            } else if (cmp > 0) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return 0 - (lo + 1);
    }

    //#ifdef PARANOID
//-    final void check() {
//-        for (int i = 0; i < size; i++) {
//-            //Debug.println("   check " + i + ": " + array[i]);
//-            if (i < size - 1) {
//-                int cmp = compare.compare(array[i], array[i+1]);
//-                if (cmp != -1) {
//-                    Debug.println("CHECK ERROR: " + i + ": " + array[i] + " vs " +
//-                                  array[i+1] + " = " + cmp);
//-                    Debug.println("Array = " + this);
//-                    throw new RuntimeException("CHECK Failed");
//-                }
//-            }
//-        }
//-    }
    //#endif
    
    public void add(Object obj) {
        //#ifdef PARANOID
//-        if (obj instanceof HeldLock) {
//-            HeldLock lock = (HeldLock)obj;
//-            if (lock.trans == null) {
//-                try {
//-                    throw new RuntimeException("lock.trans null: " + lock);
//-                } catch (Throwable t) {
//-                    Debug.print(t);
//-                }
//-            }
//-        }
        //#endif
        int pos = find(obj);
        if (pos < 0) {
            pos = 0 - (pos + 1);
            checkSizeForAdd();

            if (pos < size) {
                System.arraycopy(array, pos, array, pos+1, size - pos);
            }
            array[pos] = obj;
            size++;
        }
    }

    public void remove(Object obj) {
        removeAt(find(obj));
    }

    public void removeAt(int pos) {
        if (pos >= 0) {
            int next = pos + 1;
            if (next < size) {
                System.arraycopy(array, next, array, pos, size - next);
            }
            size--;
        }
    }        

    public int size() {
        return size;
    }

    public final Object get(int i) {
        return array[i];
    }

    final void checkSizeForAdd() {
        if (size >= array.length) {
            Object[] old = array;
            array = new Object[old.length + (old.length >> 2)];
            System.arraycopy(old, 0, array, 0, old.length);
        }
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("");
        for (int i = 0; i < size; i++) {
            sb.append("\n");
            sb.append(String.valueOf(i));
            sb.append(": ");
            sb.append(array[i]);
        }
        sb.append("\n");
        return sb.toString();
    }
        
}