// -*- c++ -*- /* * Jakelib2 - General purpose C++ library * Copyright (C) 2001 Florian Wolff (florian@donuz.de) * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * * This library 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 * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * $Id: ArrayList.jlc,v 1.11 2006-01-14 11:34:22 florian Exp $ */ #include "jakelib2.h" #include "jakelib2/util/ArrayList.h" #include "jakelib2/util/ArrayListIterator.h" #include "jakelib2/util/Comparator.h" #include using namespace jakelib::lang; using namespace jakelib::util; JAKELIB_IMPLEMENT_CLASS("jakelib.util.ArrayList", ArrayList, AbstractList); #pragma javasyntax /*****************************************************************************\ * ArrayList | *****************************************************************************/ ArrayList::ArrayList(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal capacity: " .. (jlong) initialCapacity .. JAKELIB_AT2("jakelib.util.ArrayList.ArrayList")); elementData = (Object**) GC_MALLOC(initialCapacity * sizeof(Object*)); elementCount = 0; capacity = initialCapacity; } /*****************************************************************************\ * ~ArrayList | *****************************************************************************/ ArrayList::~ArrayList() { destroy(); } /*****************************************************************************\ * destroy | *****************************************************************************/ void ArrayList::destroy() { clear(); GC_FREE(elementData); elementData = null; capacity = 0; } /*****************************************************************************\ * add | *****************************************************************************/ jboolean ArrayList::add(Object* object) { ensureCapacity(elementCount + 1); elementData[elementCount++] = object; return true; } /*****************************************************************************\ * addAll | *****************************************************************************/ jboolean ArrayList::addAll(int index, Collection* c) { return AbstractList::addAll(index, c); } jboolean ArrayList::addAll(Collection* c) { return AbstractList::addAll(c); } /*****************************************************************************\ * ensureCapacity | *****************************************************************************/ void ArrayList::ensureCapacity(int minCapacity) { if (minCapacity > capacity) { int newCapacity = capacity * 2; if (newCapacity < minCapacity) newCapacity = minCapacity; Object** newElementData = (Object**) GC_REALLOC(elementData, sizeof(Object*) * newCapacity); if (newElementData == null) throw new MemoryException("Allocating " .. (jlong) (sizeof(Object*) * newCapacity) .. " bytes of memory" .. JAKELIB_AT2("jakelib.util.ArrayList.ensureCapacity")); elementData = newElementData; capacity = newCapacity; } } /*****************************************************************************\ * trimToSize | *****************************************************************************/ void ArrayList::trimToSize() { if (capacity > elementCount) { Object** newElementData = (Object**) GC_REALLOC(elementData, sizeof(Object*) * elementCount); if (newElementData != null) { elementData = newElementData; capacity = elementCount; } } } /*****************************************************************************\ * get | *****************************************************************************/ Object* ArrayList::get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException("" .. (jlong) index .. " >= " .. (jlong) elementCount .. JAKELIB_AT2("jakelib.util.ArrayList.get")); if (index < 0) throw new IllegalArgumentException("" ..(jlong) index .. " < 0" .. JAKELIB_AT2("jakelib.util.ArrayList.get")); return elementData[index]; } /*****************************************************************************\ * size | *****************************************************************************/ int ArrayList::size() { return elementCount; } /*****************************************************************************\ * set | *****************************************************************************/ Object* ArrayList::set(int index, Object* object) { if (index < 0) throw new ArrayIndexOutOfBoundsException("" .. (jlong) index .. " < 0" .. JAKELIB_AT2("jakelib.util.ArrayList.set")); if (index >= elementCount) throw new ArrayIndexOutOfBoundsException("" .. (jlong) index .. " >= " .. (jlong) elementCount .. JAKELIB_AT2("jakelib.util.ArrayList.set")); Object* old = elementData[index]; elementData[index] = object; return old; } /*****************************************************************************\ * insert | *****************************************************************************/ void ArrayList::insert(int index, Object* object) { if (index < 0) throw new IllegalArgumentException("" .. (jlong) index .. " < 0" .. JAKELIB_AT2("jakelib.util.ArrayList.insert")); if (index > elementCount) throw new IllegalArgumentException("" .. (jlong) index .. " > " .. (jlong) elementCount .. JAKELIB_AT2("jakelib.util.ArrayList.insert")); ensureCapacity(elementCount +1); for (int idx = elementCount; idx > index; idx--) { elementData[idx] = elementData[idx - 1]; } elementData[index] = object; elementCount ++; } /*****************************************************************************\ * clear | *****************************************************************************/ void ArrayList::clear() { memset(elementData, 0, sizeof(Object*) * elementCount); elementCount = 0; } /*****************************************************************************\ * indexOf | *****************************************************************************/ int ArrayList::indexOf(Object* object) { for (int idx = 0; idx < elementCount; idx++) if (elementData[idx] == object || (object != null && object->equals(elementData[idx]))) return idx; return -1; } /*****************************************************************************\ * contains | *****************************************************************************/ jboolean ArrayList::contains(Object* object) { return (indexOf(object) != -1); } /*****************************************************************************\ * removeLastElement | *****************************************************************************/ void ArrayList::removeLastElement() { if (elementCount == 0) return; elementCount --; elementData[elementCount] = null; } /*****************************************************************************\ * remove | *****************************************************************************/ jboolean ArrayList::remove(Object* object) { int idx = indexOf(object); if (idx >= 0) { remove(idx); return true; } return false; } /*****************************************************************************\ * remove | *****************************************************************************/ Object* ArrayList::remove(int index) { if (index >= elementCount) { throw new ArrayIndexOutOfBoundsException("" .. (jlong) index .. " >= " .. (jlong) elementCount .. JAKELIB_AT2("jakelib.util.ArrayList.remove")); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException("" .. (jlong) index .. " < 0" .. JAKELIB_AT2("jakelib.util.ArrayList.remove")); } int j = elementCount - index - 1; Object* old = elementData[index]; if (j > 0) { for (int idx = index; idx < elementCount - 1; idx++) elementData[idx] = elementData[idx + 1]; } elementCount--; elementData[elementCount] = null; return old; } /*****************************************************************************\ * isEmpty | *****************************************************************************/ jboolean ArrayList::isEmpty() { return (elementCount == 0); } /*****************************************************************************\ * iterator | *****************************************************************************/ Iterator* ArrayList::iterator() { return new ArrayListIterator(this); } /*****************************************************************************\ * qsort | *****************************************************************************/ void ArrayList::qsort(Comparator* comparator) { qsorti(comparator, 0, elementCount -1); } void ArrayList::qsorti(Comparator* comparator, int left, int right) { int part, j; Object* tmp; if (right > left) { /* Watch our bounds */ part = left; j = right - 1; /* Loop to determine partition */ for (;;) { /* Part (partition) towards the right while it's < rightmost */ while (comparator->compare( elementData[part], elementData[right] ) < 0 ) part ++; /* Move j from right-1 to Part */ while (j > part && comparator->compare(elementData[j], elementData[right] ) >= 0) j --; /* If Part and j crossed paths, or j is out of bounds, we got the Part */ if (part >= j || j<0) break; /* Otherwise, swap these lines (here's where data is moved far) */ //Swap( Lines+part, Lines+j); tmp = elementData[part]; elementData[part] = elementData[j]; elementData[j] = tmp; } if ( part != right ) { //Swap( Lines+Part, Lines+Right); tmp = elementData[part]; elementData[part] = elementData[right]; elementData[right] = tmp; } qsorti(comparator, left, part-1 ); /* Sort the left of the partition */ qsorti(comparator, part+1, right ); /* sort the right of the partition */ } } /*****************************************************************************\ * bubbleSort | *****************************************************************************/ void ArrayList::bubbleSort(Comparator* comparator, SortDirection dir) { jboolean finished; int lastElement; Object* a; Object* b; if (dir == ASCENDING) { lastElement = elementCount - 1; do { finished = true; for (int idx = 0; idx < lastElement; idx++) { a = elementData[idx]; b = elementData[idx + 1]; if (comparator->compare(a, b) > 0) { elementData[idx + 1] = a; elementData[idx] = b; finished = false; } } lastElement --; } while (!finished && lastElement > 0); } else { lastElement = 0; do { finished = true; for (int idx = elementCount -1; idx > lastElement; idx--) { a = elementData[idx]; b = elementData[idx - 1]; if (comparator->compare(a, b) > 0) { elementData[idx - 1] = a; elementData[idx] = b; finished = false; } } lastElement ++; } while (!finished && lastElement > 0); } } /*****************************************************************************\ * toString | *****************************************************************************/ String* ArrayList::toString() { StringBuffer buf("["); for (int idx = 0; idx < elementCount; idx++) { if (elementData[idx] == null) buf.append("null"); else buf.append(elementData[idx]->toString()); if (idx < elementCount -1) buf.append(", "); } buf.append("]"); return buf.toString(); }